message: use im-rs for RemainingDeps
diff: use std::cmp::Ordering;
  -use std::collections::{BinaryHeap, HashMap, HashSet};
  +use std::collections::{HashMap, HashSet};
  use std::ops::Range;
  use std::rc::Rc;
  use std::time::{Duration, Instant};
  @@ -9,6 +9,8 @@ use core::{Dependency, PackageId, PackageIdSpec, Registry, Summary};
  use util::errors::CargoResult;
  use util::Config;
  +use im_rc;
  +
  pub struct ResolverProgress {
  ticks: u16,
  start: Instant,
  @@ -299,33 +301,30 @@ impl Ord for DepsFrame {
  fn cmp(&self, other: &DepsFrame) -> Ordering {
  self.just_for_error_messages
  .cmp(&other.just_for_error_messages)
  - .then_with(||
  - // the frame with the sibling that has the least number of candidates
  - // needs to get bubbled up to the top of the heap we use below, so
  - // reverse comparison here.
  - self.min_candidates().cmp(&other.min_candidates()).reverse())
  + .reverse()
  + .then_with(|| self.min_candidates().cmp(&other.min_candidates()))
  }
  }
  -/// Note that a `BinaryHeap` is used for the remaining dependencies that need
  -/// activation. This heap is sorted such that the "largest value" is the most
  -/// constrained dependency, or the one with the least candidates.
  +/// Note that a `OrdSet` is used for the remaining dependencies that need
  +/// activation. This set is sorted by how many candidates each dependency has.
  ///
  /// This helps us get through super constrained portions of the dependency
  /// graph quickly and hopefully lock down what later larger dependencies can
  /// use (those with more candidates).
  #[derive(Clone)]
  -pub struct RemainingDeps(BinaryHeap<DepsFrame>);
  +pub struct RemainingDeps(usize, im_rc::OrdSet<(DepsFrame, usize)>);
  impl RemainingDeps {
  pub fn new() -> RemainingDeps {
  - RemainingDeps(BinaryHeap::new())
  + RemainingDeps(0, im_rc::OrdSet::new())
  }
  pub fn push(&mut self, x: DepsFrame) {
  - self.0.push(x)
  + self.1.insert((x, self.0));
  + self.0 += 1;
  }
  pub fn pop_most_constrained(&mut self) -> Option<(bool, (Summary, (usize, DepInfo)))> {
  - while let Some(mut deps_frame) = self.0.pop() {
  + while let Some((mut deps_frame, i)) = self.1.remove_min() {
  let just_here_for_the_error_messages = deps_frame.just_for_error_messages;
  // Figure out what our next dependency to activate is, and if nothing is
  @@ -333,14 +332,14 @@ impl RemainingDeps {
  // move on to the next frame.
  if let Some(sibling) = deps_frame.remaining_siblings.next() {
  let parent = Summary::clone(&deps_frame.parent);
  - self.0.push(deps_frame);
  + self.1.insert((deps_frame, i));
  return Some((just_here_for_the_error_messages, (parent, sibling)));
  }
  }
  None
  }
  pub fn iter(&mut self) -> impl Iterator<Item = (&PackageId, Dependency)> {
  - self.0.iter().flat_map(|other| other.flatten())
  + self.1.iter().flat_map(|(other, _)| other.flatten())
  }
  }
  