fix dropck performance regression

Turns out that calling `resolve_type_variables_if_possible` in a O(n^2)
loop is a bad idea. Now we just resolve each copy of the region variable
to its lowest name each time (we resolve the region variable to its lowest
name, rather than to its unify-table name to avoid the risk of
the unify-table name changing infinitely many times. That may be
not a problem in practice, but I am not sure of it).

4 files changed, 61 insertions, 25 deletions

diff --git a/src/librustc/middle/infer/region_inference/mod.rs b/src/librustc/middle/infer/region_inference/mod.rs
index 30cf6344e23..e148aecd241 100644
--- a/src/librustc/middle/infer/region_inference/mod.rs
+++ b/src/librustc/middle/infer/region_inference/mod.rs
@@ -18,6 +18,7 @@ pub use self::RegionResolutionError::*;
 pub use self::VarValue::*;
 
 use super::{RegionVariableOrigin, SubregionOrigin, TypeTrace, MiscVariable};
+use super::unify_key;
 
 use rustc_data_structures::graph::{self, Direction, NodeIndex};
 use rustc_data_structures::unify::{self, UnificationTable};
@@ -345,10 +346,13 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     }
 
     pub fn new_region_var(&self, origin: RegionVariableOrigin) -> RegionVid {
-        let id = self.num_vars();
+        let vid = RegionVid { index: self.num_vars() };
         self.var_origins.borrow_mut().push(origin.clone());
-        let vid = self.unification_table.borrow_mut().new_key(());
-        assert_eq!(vid.index, id);
+
+        let u_vid = self.unification_table.borrow_mut().new_key(
+            unify_key::RegionVidKey { min_vid: vid }
+            );
+        assert_eq!(vid, u_vid);
         if self.in_snapshot() {
             self.undo_log.borrow_mut().push(AddVar(vid));
         }
@@ -581,7 +585,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     }
 
     pub fn opportunistic_resolve_var(&self, rid: RegionVid) -> ty::Region {
-        ty::ReVar(self.unification_table.borrow_mut().find(rid))
+        ty::ReVar(self.unification_table.borrow_mut().find_value(rid).min_vid)
     }
 
     fn combine_map(&self, t: CombineMapType) -> &RefCell<CombineMap> {
diff --git a/src/librustc/middle/infer/unify_key.rs b/src/librustc/middle/infer/unify_key.rs
index 85d7d67a0e3..c83231930f5 100644
--- a/src/librustc/middle/infer/unify_key.rs
+++ b/src/librustc/middle/infer/unify_key.rs
@@ -10,7 +10,7 @@
 
 use syntax::ast;
 use middle::ty::{self, IntVarValue, Ty};
-use rustc_data_structures::unify::UnifyKey;
+use rustc_data_structures::unify::{Combine, UnifyKey};
 
 pub trait ToType<'tcx> {
     fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx>;
@@ -23,8 +23,28 @@ impl UnifyKey for ty::IntVid {
     fn tag(_: Option<ty::IntVid>) -> &'static str { "IntVid" }
 }
 
+#[derive(PartialEq, Copy, Clone, Debug)]
+pub struct RegionVidKey {
+    /// The minimum region vid in the unification set. This is needed
+    /// to have a canonical name for a type to prevent infinite
+    /// recursion.
+    pub min_vid: ty::RegionVid
+}
+
+impl Combine for RegionVidKey {
+    fn combine(&self, other: &RegionVidKey) -> RegionVidKey {
+        let min_vid = if self.min_vid.index < other.min_vid.index {
+            self.min_vid
+        } else {
+            other.min_vid
+        };
+
+        RegionVidKey { min_vid: min_vid }
+    }
+}
+
 impl UnifyKey for ty::RegionVid {
-    type Value = ();
+    type Value = RegionVidKey;
     fn index(&self) -> u32 { self.index }
     fn from_index(i: u32) -> ty::RegionVid { ty::RegionVid { index: i } }
     fn tag(_: Option<ty::RegionVid>) -> &'static str { "RegionVid" }
diff --git a/src/librustc_data_structures/unify/mod.rs b/src/librustc_data_structures/unify/mod.rs
index 4d79b1a64c1..c6da70eef75 100644
--- a/src/librustc_data_structures/unify/mod.rs
+++ b/src/librustc_data_structures/unify/mod.rs
@@ -37,6 +37,16 @@ pub trait UnifyKey : Copy + Clone + Debug + PartialEq {
     fn tag(k: Option<Self>) -> &'static str;
 }
 
+/// This trait is implemented for unify values that can be
+/// combined. This relation should be a monoid.
+pub trait Combine {
+    fn combine(&self, other: &Self) -> Self;
+}
+
+impl Combine for () {
+    fn combine(&self, _other: &()) {}
+}
+
 /// Value of a unification key. We implement Tarjan's union-find
 /// algorithm: when two keys are unified, one of them is converted
 /// into a "redirect" pointing at the other. These redirects form a
@@ -243,8 +253,8 @@ impl<K:UnifyKey> sv::SnapshotVecDelegate for Delegate<K> {
 ///////////////////////////////////////////////////////////////////////////
 // Base union-find algorithm, where we are just making sets
 
-impl<'tcx,K> UnificationTable<K>
-    where K : UnifyKey<Value=()>,
+impl<'tcx,K:UnifyKey> UnificationTable<K>
+    where K::Value: Combine
 {
     pub fn union(&mut self, a_id: K, b_id: K) {
         let node_a = self.get(a_id);
@@ -252,7 +262,8 @@ impl<'tcx,K> UnificationTable<K>
         let a_id = node_a.key();
         let b_id = node_b.key();
         if a_id != b_id {
-            self.unify(node_a, node_b, ());
+            let new_value = node_a.value.combine(&node_b.value);
+            self.unify(node_a, node_b, new_value);
         }
     }
 
@@ -260,6 +271,10 @@ impl<'tcx,K> UnificationTable<K>
         self.get(id).key()
     }
 
+    pub fn find_value(&mut self, id: K) -> K::Value {
+        self.get(id).value
+    }
+
     pub fn unioned(&mut self, a_id: K, b_id: K) -> bool {
         self.find(a_id) == self.find(b_id)
     }
diff --git a/src/librustc_typeck/check/dropck.rs b/src/librustc_typeck/check/dropck.rs
index 0fbe8367493..59025346ce3 100644
--- a/src/librustc_typeck/check/dropck.rs
+++ b/src/librustc_typeck/check/dropck.rs
@@ -17,6 +17,7 @@ use middle::region;
 use middle::subst::{self, Subst};
 use middle::traits;
 use middle::ty::{self, Ty};
+use util::nodemap::FnvHashSet;
 
 use syntax::ast;
 use syntax::codemap::{self, Span};
@@ -279,7 +280,7 @@ pub fn check_safety_of_destructor_if_necessary<'a, 'tcx>(rcx: &mut Rcx<'a, 'tcx>
             rcx: rcx,
             span: span,
             parent_scope: parent_scope,
-            breadcrumbs: Vec::new(),
+            breadcrumbs: FnvHashSet()
         },
         TypeContext::Root,
         typ,
@@ -340,7 +341,7 @@ enum TypeContext {
 struct DropckContext<'a, 'b: 'a, 'tcx: 'b> {
     rcx: &'a mut Rcx<'b, 'tcx>,
     /// types that have already been traversed
-    breadcrumbs: Vec<Ty<'tcx>>,
+    breadcrumbs: FnvHashSet<Ty<'tcx>>,
     /// span for error reporting
     span: Span,
     /// the scope reachable dtorck types must outlive
@@ -355,8 +356,6 @@ fn iterate_over_potentially_unsafe_regions_in_type<'a, 'b, 'tcx>(
     depth: usize) -> Result<(), Error<'tcx>>
 {
     let tcx = cx.rcx.tcx();
-    let ty = cx.rcx.infcx().resolve_type_and_region_vars_if_possible(&ty);
-
     // Issue #22443: Watch out for overflow. While we are careful to
     // handle regular types properly, non-regular ones cause problems.
     let recursion_limit = tcx.sess.recursion_limit.get();
@@ -367,19 +366,17 @@ fn iterate_over_potentially_unsafe_regions_in_type<'a, 'b, 'tcx>(
         return Err(Error::Overflow(context, ty))
     }
 
-    for breadcrumb in &mut cx.breadcrumbs {
-        *breadcrumb =
-            cx.rcx.infcx().resolve_type_and_region_vars_if_possible(breadcrumb);
-        if *breadcrumb == ty {
-            debug!("iterate_over_potentially_unsafe_regions_in_type \
-                   {}ty: {} scope: {:?} - cached",
-                   (0..depth).map(|_| ' ').collect::<String>(),
-                   ty, cx.parent_scope);
-            return Ok(()); // we already visited this type
-        }
-    }
-    cx.breadcrumbs.push(ty);
+    // canoncialize the regions in `ty` before inserting - infinitely many
+    // region variables can refer to the same region.
+    let ty = cx.rcx.infcx().resolve_type_and_region_vars_if_possible(&ty);
 
+    if !cx.breadcrumbs.insert(ty) {
+        debug!("iterate_over_potentially_unsafe_regions_in_type \
+               {}ty: {} scope: {:?} - cached",
+               (0..depth).map(|_| ' ').collect::<String>(),
+               ty, cx.parent_scope);
+        return Ok(()); // we already visited this type
+    }
     debug!("iterate_over_potentially_unsafe_regions_in_type \
            {}ty: {} scope: {:?}",
            (0..depth).map(|_| ' ').collect::<String>(),