message: Display dep requirement info for cyclic dependencies
diff: //! that we're implementing something that probably shouldn't be allocating all
  //! over the place.
  -use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
  +use std::collections::{BTreeMap, HashMap, HashSet};
  use std::mem;
  use std::rc::Rc;
  use std::time::{Duration, Instant};
  @@ -1007,13 +1007,15 @@ fn check_cycles(resolve: &Resolve) -> CargoResult<()> {
  // dev-dependency since that doesn't count for cycles.
  let mut graph = BTreeMap::new();
  for id in resolve.iter() {
  - let set = graph.entry(id).or_insert_with(BTreeSet::new);
  - for (dep, listings) in resolve.deps_not_replaced(id) {
  - let is_transitive = listings.iter().any(|d| d.is_transitive());
  + let map = graph.entry(id).or_insert_with(BTreeMap::new);
  + for (dep_id, listings) in resolve.deps_not_replaced(id) {
  + let transitive_dep = listings.iter().find(|d| d.is_transitive());
  - if is_transitive {
  - set.insert(dep);
  - set.extend(resolve.replacement(dep));
  + if let Some(transitive_dep) = transitive_dep.cloned() {
  + map.insert(dep_id, transitive_dep.clone());
  + resolve
  + .replacement(dep_id)
  + .map(|p| map.insert(p, transitive_dep));
  }
  }
  }
  @@ -1033,7 +1035,7 @@ fn check_cycles(resolve: &Resolve) -> CargoResult<()> {
  return Ok(());
  fn visit(
  - graph: &BTreeMap<PackageId, BTreeSet<PackageId>>,
  + graph: &BTreeMap<PackageId, BTreeMap<PackageId, Dependency>>,
  id: PackageId,
  visited: &mut HashSet<PackageId>,
  path: &mut Vec<PackageId>,
  @@ -1041,15 +1043,21 @@ fn check_cycles(resolve: &Resolve) -> CargoResult<()> {
  ) -> CargoResult<()> {
  path.push(id);
  if !visited.insert(id) {
  + let iter = path.iter().rev().skip(1).scan(id, |child, parent| {
  + let dep = graph.get(parent).and_then(|adjacent| adjacent.get(child));
  + *child = *parent;
  + Some((parent, dep))
  + });
  + let iter = std::iter::once((&id, None)).chain(iter);
  anyhow::bail!(
  "cyclic package dependency: package `{}` depends on itself. Cycle:\n{}",
  id,
  - errors::describe_path(&path.iter().rev().collect::<Vec<_>>()),
  + errors::describe_path(iter),
  );
  }
  if checked.insert(id) {
  - for dep in graph[&id].iter() {
  + for dep in graph[&id].keys() {
  visit(graph, *dep, visited, path, checked)?;
  }
  }
  