store type values in the unification table directly

5 files changed, 176 insertions, 98 deletions

diff --git a/src/librustc/infer/combine.rs b/src/librustc/infer/combine.rs
index 8997e7d99da..959fefbe6b6 100644
--- a/src/librustc/infer/combine.rs
+++ b/src/librustc/infer/combine.rs
@@ -402,7 +402,7 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
                     // `vid` are related via subtyping.
                     return Err(TypeError::CyclicTy(self.root_ty));
                 } else {
-                    match variables.probe_root(vid) {
+                    match variables.probe(vid) {
                         Some(u) => {
                             drop(variables);
                             self.relate(&u, &u)
@@ -423,7 +423,7 @@ impl<'cx, 'gcx, 'tcx> TypeRelation<'cx, 'gcx, 'tcx> for Generalizer<'cx, 'gcx, '
                                 ty::Covariant | ty::Contravariant => (),
                             }
 
-                            let origin = variables.origin(vid);
+                            let origin = *variables.var_origin(vid);
                             let new_var_id = variables.new_var(false, origin);
                             let u = self.tcx().mk_var(new_var_id);
                             debug!("generalize: replacing original vid={:?} with new={:?}",
diff --git a/src/librustc/infer/higher_ranked/mod.rs b/src/librustc/infer/higher_ranked/mod.rs
index 57e237fb913..a317e0699b4 100644
--- a/src/librustc/infer/higher_ranked/mod.rs
+++ b/src/librustc/infer/higher_ranked/mod.rs
@@ -244,7 +244,7 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
 
         fn generalize_region<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
                                              span: Span,
-                                             snapshot: &CombinedSnapshot,
+                                             snapshot: &CombinedSnapshot<'a, 'tcx>,
                                              debruijn: ty::DebruijnIndex,
                                              new_vars: &[ty::RegionVid],
                                              a_map: &BTreeMap<ty::BoundRegion, ty::Region<'tcx>>,
@@ -340,7 +340,7 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
 
         fn generalize_region<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
                                              span: Span,
-                                             snapshot: &CombinedSnapshot,
+                                             snapshot: &CombinedSnapshot<'a, 'tcx>,
                                              debruijn: ty::DebruijnIndex,
                                              new_vars: &[ty::RegionVid],
                                              a_map: &BTreeMap<ty::BoundRegion, ty::Region<'tcx>>,
@@ -479,7 +479,7 @@ fn fold_regions_in<'a, 'gcx, 'tcx, T, F>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 
 impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
     fn tainted_regions(&self,
-                       snapshot: &CombinedSnapshot,
+                       snapshot: &CombinedSnapshot<'a, 'tcx>,
                        r: ty::Region<'tcx>,
                        directions: TaintDirections)
                        -> FxHashSet<ty::Region<'tcx>> {
@@ -491,7 +491,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
     }
 
     fn region_vars_confined_to_snapshot(&self,
-                                        snapshot: &CombinedSnapshot)
+                                        snapshot: &CombinedSnapshot<'a, 'tcx>)
                                         -> Vec<ty::RegionVid>
     {
         /*!
@@ -583,7 +583,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
     /// See `README.md` for more details.
     pub fn skolemize_late_bound_regions<T>(&self,
                                            binder: &ty::Binder<T>,
-                                           snapshot: &CombinedSnapshot)
+                                           snapshot: &CombinedSnapshot<'a, 'tcx>)
                                            -> (T, SkolemizationMap<'tcx>)
         where T : TypeFoldable<'tcx>
     {
@@ -609,7 +609,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                       overly_polymorphic: bool,
                       _span: Span,
                       skol_map: &SkolemizationMap<'tcx>,
-                      snapshot: &CombinedSnapshot)
+                      snapshot: &CombinedSnapshot<'a, 'tcx>)
                       -> RelateResult<'tcx, ()>
     {
         debug!("leak_check: skol_map={:?}",
@@ -684,7 +684,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
     /// predicate is `for<'a> &'a int : Clone`.
     pub fn plug_leaks<T>(&self,
                          skol_map: SkolemizationMap<'tcx>,
-                         snapshot: &CombinedSnapshot,
+                         snapshot: &CombinedSnapshot<'a, 'tcx>,
                          value: T) -> T
         where T : TypeFoldable<'tcx>
     {
@@ -770,8 +770,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
     /// Note: popping also occurs implicitly as part of `leak_check`.
     pub fn pop_skolemized(&self,
                           skol_map: SkolemizationMap<'tcx>,
-                          snapshot: &CombinedSnapshot)
-    {
+                          snapshot: &CombinedSnapshot<'a, 'tcx>) {
         debug!("pop_skolemized({:?})", skol_map);
         let skol_regions: FxHashSet<_> = skol_map.values().cloned().collect();
         self.borrow_region_constraints()
diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index 72a4dfbb7e0..fa224b575a3 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -475,7 +475,7 @@ impl<'tcx, T> InferOk<'tcx, T> {
 #[must_use = "once you start a snapshot, you should always consume it"]
 pub struct CombinedSnapshot<'a, 'tcx:'a> {
     projection_cache_snapshot: traits::ProjectionCacheSnapshot,
-    type_snapshot: type_variable::Snapshot,
+    type_snapshot: type_variable::Snapshot<'tcx>,
     int_snapshot: ut::Snapshot<ut::InPlace<ty::IntVid>>,
     float_snapshot: ut::Snapshot<ut::InPlace<ty::FloatVid>>,
     region_constraints_snapshot: RegionSnapshot,
@@ -765,7 +765,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         result
     }
 
-    fn start_snapshot<'b>(&'b self) -> CombinedSnapshot<'b, 'tcx> {
+    fn start_snapshot(&self) -> CombinedSnapshot<'a, 'tcx> {
         debug!("start_snapshot()");
 
         let in_snapshot = self.in_snapshot.get();
@@ -787,7 +787,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         }
     }
 
-    fn rollback_to(&self, cause: &str, snapshot: CombinedSnapshot) {
+    fn rollback_to(&self, cause: &str, snapshot: CombinedSnapshot<'a, 'tcx>) {
         debug!("rollback_to(cause={})", cause);
         let CombinedSnapshot { projection_cache_snapshot,
                                type_snapshot,
@@ -819,7 +819,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
             .rollback_to(region_constraints_snapshot);
     }
 
-    fn commit_from(&self, snapshot: CombinedSnapshot) {
+    fn commit_from(&self, snapshot: CombinedSnapshot<'a, 'tcx>) {
         debug!("commit_from()");
         let CombinedSnapshot { projection_cache_snapshot,
                                type_snapshot,
@@ -861,7 +861,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
 
     /// Execute `f` and commit the bindings if closure `f` returns `Ok(_)`
     pub fn commit_if_ok<T, E, F>(&self, f: F) -> Result<T, E> where
-        F: FnOnce(&CombinedSnapshot) -> Result<T, E>
+        F: FnOnce(&CombinedSnapshot<'a, 'tcx>) -> Result<T, E>
     {
         debug!("commit_if_ok()");
         let snapshot = self.start_snapshot();
@@ -876,7 +876,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
 
     // Execute `f` in a snapshot, and commit the bindings it creates
     pub fn in_snapshot<T, F>(&self, f: F) -> T where
-        F: FnOnce(&CombinedSnapshot) -> T
+        F: FnOnce(&CombinedSnapshot<'a, 'tcx>) -> T
     {
         debug!("in_snapshot()");
         let snapshot = self.start_snapshot();
@@ -887,7 +887,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
 
     /// Execute `f` then unroll any bindings it creates
     pub fn probe<R, F>(&self, f: F) -> R where
-        F: FnOnce(&CombinedSnapshot) -> R,
+        F: FnOnce(&CombinedSnapshot<'a, 'tcx>) -> R,
     {
         debug!("probe()");
         let snapshot = self.start_snapshot();
diff --git a/src/librustc/infer/type_variable.rs b/src/librustc/infer/type_variable.rs
index 423b18823b1..261cd396fce 100644
--- a/src/librustc/infer/type_variable.rs
+++ b/src/librustc/infer/type_variable.rs
@@ -8,25 +8,24 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use self::TypeVariableValue::*;
 use syntax::ast;
 use syntax_pos::Span;
 use ty::{self, Ty};
 
 use std::cmp::min;
 use std::marker::PhantomData;
-use std::mem;
 use std::u32;
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::snapshot_vec as sv;
 use rustc_data_structures::unify as ut;
 
 pub struct TypeVariableTable<'tcx> {
-    values: sv::SnapshotVec<Delegate<'tcx>>,
+    values: sv::SnapshotVec<Delegate>,
 
     /// Two variables are unified in `eq_relations` when we have a
-    /// constraint `?X == ?Y`.
-    eq_relations: ut::UnificationTable<ut::InPlace<ty::TyVid>>,
+    /// constraint `?X == ?Y`. This table also stores, for each key,
+    /// the known value.
+    eq_relations: ut::UnificationTable<ut::InPlace<TyVidEqKey<'tcx>>>,
 
     /// Two variables are unified in `eq_relations` when we have a
     /// constraint `?X <: ?Y` *or* a constraint `?Y <: ?X`. This second
@@ -71,22 +70,20 @@ pub enum TypeVariableOrigin {
 
 pub type TypeVariableMap = FxHashMap<ty::TyVid, TypeVariableOrigin>;
 
-struct TypeVariableData<'tcx> {
-    value: TypeVariableValue<'tcx>,
+struct TypeVariableData {
     origin: TypeVariableOrigin,
     diverging: bool
 }
 
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
 enum TypeVariableValue<'tcx> {
-    Known {
-        value: Ty<'tcx>
-    },
+    Known { value: Ty<'tcx> },
     Unknown,
 }
 
-pub struct Snapshot {
+pub struct Snapshot<'tcx> {
     snapshot: sv::Snapshot,
-    eq_snapshot: ut::Snapshot<ut::InPlace<ty::TyVid>>,
+    eq_snapshot: ut::Snapshot<ut::InPlace<TyVidEqKey<'tcx>>>,
     sub_snapshot: ut::Snapshot<ut::InPlace<ty::TyVid>>,
 }
 
@@ -94,7 +91,7 @@ struct Instantiate {
     vid: ty::TyVid,
 }
 
-struct Delegate<'tcx>(PhantomData<&'tcx ()>);
+struct Delegate;
 
 impl<'tcx> TypeVariableTable<'tcx> {
     pub fn new() -> TypeVariableTable<'tcx> {
@@ -105,10 +102,18 @@ impl<'tcx> TypeVariableTable<'tcx> {
         }
     }
 
+    /// Returns the diverges flag given when `vid` was created.
+    ///
+    /// Note that this function does not return care whether
+    /// `vid` has been unified with something else or not.
     pub fn var_diverges<'a>(&'a self, vid: ty::TyVid) -> bool {
         self.values.get(vid.index as usize).diverging
     }
 
+    /// Returns the origin that was given when `vid` was created.
+    ///
+    /// Note that this function does not return care whether
+    /// `vid` has been unified with something else or not.
     pub fn var_origin(&self, vid: ty::TyVid) -> &TypeVariableOrigin {
         &self.values.get(vid.index as usize).origin
     }
@@ -137,41 +142,49 @@ impl<'tcx> TypeVariableTable<'tcx> {
     /// Precondition: `vid` must not have been previously instantiated.
     pub fn instantiate(&mut self, vid: ty::TyVid, ty: Ty<'tcx>) {
         let vid = self.root_var(vid);
-        debug_assert!(self.probe_root(vid).is_none());
-
-        let old_value = {
-            let vid_data = &mut self.values[vid.index as usize];
-            mem::replace(&mut vid_data.value, TypeVariableValue::Known { value: ty })
-        };
-
-        match old_value {
-            TypeVariableValue::Unknown => {
-                self.values.record(Instantiate { vid: vid });
-            }
-            TypeVariableValue::Known { value: old_ty } => {
-                bug!("instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
-                     vid, ty, old_ty)
-            }
-        }
+        debug_assert!(self.probe(vid).is_none());
+        debug_assert!(self.eq_relations.probe_value(vid) == TypeVariableValue::Unknown,
+                      "instantiating type variable `{:?}` twice: new-value = {:?}, old-value={:?}",
+                      vid, ty, self.eq_relations.probe_value(vid));
+        self.eq_relations.union_value(vid, TypeVariableValue::Known { value: ty });
+
+        // Hack: we only need this so that `types_escaping_snapshot`
+        // can see what has been unified; see the Delegate impl for
+        // more details.
+        self.values.record(Instantiate { vid: vid });
     }
 
+    /// Creates a new type variable.
+    ///
+    /// - `diverging`: indicates if this is a "diverging" type
+    ///   variable, e.g.  one created as the type of a `return`
+    ///   expression. The code in this module doesn't care if a
+    ///   variable is diverging, but the main Rust type-checker will
+    ///   sometimes "unify" such variables with the `!` or `()` types.
+    /// - `origin`: indicates *why* the type variable was created.
+    ///   The code in this module doesn't care, but it can be useful
+    ///   for improving error messages.
     pub fn new_var(&mut self,
                    diverging: bool,
                    origin: TypeVariableOrigin)
                    -> ty::TyVid {
-        debug!("new_var(diverging={:?}, origin={:?})", diverging, origin);
-        self.eq_relations.new_key(());
-        self.sub_relations.new_key(());
+        let eq_key = self.eq_relations.new_key(TypeVariableValue::Unknown);
+
+        let sub_key = self.sub_relations.new_key(());
+        assert_eq!(eq_key.vid, sub_key);
+
         let index = self.values.push(TypeVariableData {
-            value: Unknown,
             origin,
             diverging,
         });
-        let v = ty::TyVid { index: index as u32 };
-        debug!("new_var: diverging={:?} index={:?}", diverging, v);
-        v
+        assert_eq!(eq_key.vid.index, index as u32);
+
+        debug!("new_var(index={:?}, diverging={:?}, origin={:?}", eq_key.vid, diverging, origin);
+
+        eq_key.vid
     }
 
+    /// Returns the number of type variables created thus far.
     pub fn num_vars(&self) -> usize {
         self.values.len()
     }
@@ -182,7 +195,7 @@ impl<'tcx> TypeVariableTable<'tcx> {
     /// algorithm), so `root_var(a) == root_var(b)` implies that `a ==
     /// b` (transitively).
     pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
-        self.eq_relations.find(vid)
+        self.eq_relations.find(vid).vid
     }
 
     /// Returns the "root" variable of `vid` in the `sub_relations`
@@ -202,24 +215,19 @@ impl<'tcx> TypeVariableTable<'tcx> {
         self.sub_root_var(a) == self.sub_root_var(b)
     }
 
+    /// Retrieves the type to which `vid` has been instantiated, if
+    /// any.
     pub fn probe(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
         let vid = self.root_var(vid);
-        self.probe_root(vid)
-    }
-
-    pub fn origin(&self, vid: ty::TyVid) -> TypeVariableOrigin {
-        self.values.get(vid.index as usize).origin.clone()
-    }
-
-    /// Retrieves the type of `vid` given that it is currently a root in the unification table
-    pub fn probe_root(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
-        debug_assert!(self.root_var(vid) == vid);
-        match self.values.get(vid.index as usize).value {
-            Unknown => None,
-            Known { value } => Some(value)
+        match self.eq_relations.probe_value(vid) {
+            TypeVariableValue::Unknown => None,
+            TypeVariableValue::Known { value } => Some(value)
         }
     }
 
+    /// If `t` is a type-inference variable, and it has been
+    /// instantiated, then return the with which it was
+    /// instantiated. Otherwise, returns `t`.
     pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
         match t.sty {
             ty::TyInfer(ty::TyVar(v)) => {
@@ -232,7 +240,11 @@ impl<'tcx> TypeVariableTable<'tcx> {
         }
     }
 
-    pub fn snapshot(&mut self) -> Snapshot {
+    /// Creates a snapshot of the type variable state.  This snapshot
+    /// must later be committed (`commit()`) or rolled back
+    /// (`rollback_to()`).  Nested snapshots are permitted, but must
+    /// be processed in a stack-like fashion.
+    pub fn snapshot(&mut self) -> Snapshot<'tcx> {
         Snapshot {
             snapshot: self.values.start_snapshot(),
             eq_snapshot: self.eq_relations.snapshot(),
@@ -240,7 +252,10 @@ impl<'tcx> TypeVariableTable<'tcx> {
         }
     }
 
-    pub fn rollback_to(&mut self, s: Snapshot) {
+    /// Undoes all changes since the snapshot was created. Any
+    /// snapshots created since that point must already have been
+    /// committed or rolled back.
+    pub fn rollback_to(&mut self, s: Snapshot<'tcx>) {
         debug!("rollback_to{:?}", {
             for action in self.values.actions_since_snapshot(&s.snapshot) {
                 match *action {
@@ -258,7 +273,11 @@ impl<'tcx> TypeVariableTable<'tcx> {
         self.sub_relations.rollback_to(sub_snapshot);
     }
 
-    pub fn commit(&mut self, s: Snapshot) {
+    /// Commits all changes since the snapshot was created, making
+    /// them permanent (unless this snapshot was created within
+    /// another snapshot). Any snapshots created since that point
+    /// must already have been committed or rolled back.
+    pub fn commit(&mut self, s: Snapshot<'tcx>) {
         let Snapshot { snapshot, eq_snapshot, sub_snapshot } = s;
         self.values.commit(snapshot);
         self.eq_relations.commit(eq_snapshot);
@@ -269,7 +288,7 @@ impl<'tcx> TypeVariableTable<'tcx> {
     /// ty-variables created during the snapshot, and the values
     /// `{V2}` are the root variables that they were unified with,
     /// along with their origin.
-    pub fn types_created_since_snapshot(&mut self, s: &Snapshot) -> TypeVariableMap {
+    pub fn types_created_since_snapshot(&mut self, s: &Snapshot<'tcx>) -> TypeVariableMap {
         let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
 
         actions_since_snapshot
@@ -285,16 +304,13 @@ impl<'tcx> TypeVariableTable<'tcx> {
             .collect()
     }
 
-    pub fn types_escaping_snapshot(&mut self, s: &Snapshot) -> Vec<Ty<'tcx>> {
-        /*!
-         * Find the set of type variables that existed *before* `s`
-         * but which have only been unified since `s` started, and
-         * return the types with which they were unified. So if we had
-         * a type variable `V0`, then we started the snapshot, then we
-         * created a type variable `V1`, unifed `V0` with `T0`, and
-         * unified `V1` with `T1`, this function would return `{T0}`.
-         */
-
+    /// Find the set of type variables that existed *before* `s`
+    /// but which have only been unified since `s` started, and
+    /// return the types with which they were unified. So if we had
+    /// a type variable `V0`, then we started the snapshot, then we
+    /// created a type variable `V1`, unifed `V0` with `T0`, and
+    /// unified `V1` with `T1`, this function would return `{T0}`.
+    pub fn types_escaping_snapshot(&mut self, s: &Snapshot<'tcx>) -> Vec<Ty<'tcx>> {
         let mut new_elem_threshold = u32::MAX;
         let mut escaping_types = Vec::new();
         let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
@@ -315,9 +331,9 @@ impl<'tcx> TypeVariableTable<'tcx> {
                     if vid.index < new_elem_threshold {
                         // quick check to see if this variable was
                         // created since the snapshot started or not.
-                        let escaping_type = match self.values.get(vid.index as usize).value {
-                            Unknown => bug!(),
-                            Known { value } => value,
+                        let escaping_type = match self.eq_relations.probe_value(vid) {
+                            TypeVariableValue::Unknown => bug!(),
+                            TypeVariableValue::Known { value } => value,
                         };
                         escaping_types.push(escaping_type);
                     }
@@ -331,6 +347,8 @@ impl<'tcx> TypeVariableTable<'tcx> {
         escaping_types
     }
 
+    /// Returns indices of all variables that are not yet
+    /// instantiated.
     pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
         (0..self.values.len())
             .filter_map(|i| {
@@ -345,19 +363,80 @@ impl<'tcx> TypeVariableTable<'tcx> {
     }
 }
 
-impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> {
-    type Value = TypeVariableData<'tcx>;
+impl sv::SnapshotVecDelegate for Delegate {
+    type Value = TypeVariableData;
     type Undo = Instantiate;
 
-    fn reverse(values: &mut Vec<TypeVariableData<'tcx>>, action: Instantiate) {
-        let Instantiate { vid } = action;
-        values[vid.index as usize].value = Unknown;
+    fn reverse(_values: &mut Vec<TypeVariableData>, _action: Instantiate) {
+        // We don't actually have to *do* anything to reverse an
+        // instanation; the value for a variable is stored in the
+        // `eq_relations` and hence its rollback code will handle
+        // it. In fact, we could *almost* just remove the
+        // `SnapshotVec` entirely, except that we would have to
+        // reproduce *some* of its logic, since we want to know which
+        // type variables have been instantiated since the snapshot
+        // was started, so we can implement `types_escaping_snapshot`.
+        //
+        // (If we extended the `UnificationTable` to let us see which
+        // values have been unified and so forth, that might also
+        // suffice.)
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////
+
+/// These structs (a newtyped TyVid) are used as the unification key
+/// for the `eq_relations`; they carry a `TypeVariableValue` along
+/// with them.
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+struct TyVidEqKey<'tcx> {
+    vid: ty::TyVid,
+
+    // in the table, we map each ty-vid to one of these:
+    phantom: PhantomData<TypeVariableValue<'tcx>>,
+}
+
+impl<'tcx> From<ty::TyVid> for TyVidEqKey<'tcx> {
+    fn from(vid: ty::TyVid) -> Self {
+        TyVidEqKey { vid, phantom: PhantomData }
+    }
+}
+
+impl<'tcx> ut::UnifyKey for TyVidEqKey<'tcx> {
+    type Value = TypeVariableValue<'tcx>;
+    fn index(&self) -> u32 { self.vid.index }
+    fn from_index(i: u32) -> Self { TyVidEqKey::from(ty::TyVid { index: i }) }
+    fn tag() -> &'static str { "TyVidEqKey" }
+}
+
+impl<'tcx> ut::UnifyValue for TypeVariableValue<'tcx> {
+    type Error = ut::NoError;
+
+    fn unify_values(value1: &Self, value2: &Self) -> Result<Self, ut::NoError> {
+        match (value1, value2) {
+            // We never equate two type variables, both of which
+            // have known types.  Instead, we recursively equate
+            // those types.
+            (&TypeVariableValue::Known { .. }, &TypeVariableValue::Known { .. }) => {
+                bug!("equating two type variables, both of which have known types")
+            }
+
+            // If one side is known, prefer that one.
+            (&TypeVariableValue::Known { .. }, &TypeVariableValue::Unknown { .. }) => Ok(*value1),
+            (&TypeVariableValue::Unknown { .. }, &TypeVariableValue::Known { .. }) => Ok(*value2),
+
+            // If both sides are *unknown*, it hardly matters, does it?
+            (&TypeVariableValue::Unknown, &TypeVariableValue::Unknown) => Ok(*value1),
+        }
     }
 }
 
+/// Raw `TyVid` are used as the unification key for `sub_relations`;
+/// they carry no values.
 impl ut::UnifyKey for ty::TyVid {
     type Value = ();
     fn index(&self) -> u32 { self.index }
     fn from_index(i: u32) -> ty::TyVid { ty::TyVid { index: i } }
     fn tag() -> &'static str { "TyVid" }
 }
+
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index f21ec295c5f..e5f05f30fd8 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -496,7 +496,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     /// Wraps the inference context's in_snapshot s.t. snapshot handling is only from the selection
     /// context's self.
     fn in_snapshot<R, F>(&mut self, f: F) -> R
-        where F: FnOnce(&mut Self, &infer::CombinedSnapshot) -> R
+        where F: FnOnce(&mut Self, &infer::CombinedSnapshot<'cx, 'tcx>) -> R
     {
         // The irrefutable nature of the operation means we don't need to snapshot the
         // inferred_obligations vector.
@@ -506,7 +506,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     /// Wraps a probe s.t. obligations collected during it are ignored and old obligations are
     /// retained.
     fn probe<R, F>(&mut self, f: F) -> R
-        where F: FnOnce(&mut Self, &infer::CombinedSnapshot) -> R
+        where F: FnOnce(&mut Self, &infer::CombinedSnapshot<'cx, 'tcx>) -> R
     {
         let inferred_obligations_snapshot = self.inferred_obligations.start_snapshot();
         let result = self.infcx.probe(|snapshot| f(self, snapshot));
@@ -1478,7 +1478,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     fn match_projection_obligation_against_definition_bounds(
         &mut self,
         obligation: &TraitObligation<'tcx>,
-        snapshot: &infer::CombinedSnapshot)
+        snapshot: &infer::CombinedSnapshot<'cx, 'tcx>)
         -> bool
     {
         let poly_trait_predicate =
@@ -1549,7 +1549,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                         trait_bound: ty::PolyTraitRef<'tcx>,
                         skol_trait_ref: ty::TraitRef<'tcx>,
                         skol_map: &infer::SkolemizationMap<'tcx>,
-                        snapshot: &infer::CombinedSnapshot)
+                        snapshot: &infer::CombinedSnapshot<'cx, 'tcx>)
                         -> bool
     {
         assert!(!skol_trait_ref.has_escaping_regions());
@@ -2587,7 +2587,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                    recursion_depth: usize,
                    param_env: ty::ParamEnv<'tcx>,
                    skol_map: infer::SkolemizationMap<'tcx>,
-                   snapshot: &infer::CombinedSnapshot)
+                   snapshot: &infer::CombinedSnapshot<'cx, 'tcx>)
                    -> VtableImplData<'tcx, PredicateObligation<'tcx>>
     {
         debug!("vtable_impl(impl_def_id={:?}, substs={:?}, recursion_depth={}, skol_map={:?})",
@@ -3076,7 +3076,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     fn rematch_impl(&mut self,
                     impl_def_id: DefId,
                     obligation: &TraitObligation<'tcx>,
-                    snapshot: &infer::CombinedSnapshot)
+                    snapshot: &infer::CombinedSnapshot<'cx, 'tcx>)
                     -> (Normalized<'tcx, &'tcx Substs<'tcx>>,
                         infer::SkolemizationMap<'tcx>)
     {
@@ -3093,7 +3093,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     fn match_impl(&mut self,
                   impl_def_id: DefId,
                   obligation: &TraitObligation<'tcx>,
-                  snapshot: &infer::CombinedSnapshot)
+                  snapshot: &infer::CombinedSnapshot<'cx, 'tcx>)
                   -> Result<(Normalized<'tcx, &'tcx Substs<'tcx>>,
                              infer::SkolemizationMap<'tcx>), ()>
     {
@@ -3288,7 +3288,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                                  def_id: DefId, // of impl or trait
                                  substs: &Substs<'tcx>, // for impl or trait
                                  skol_map: infer::SkolemizationMap<'tcx>,
-                                 snapshot: &infer::CombinedSnapshot)
+                                 snapshot: &infer::CombinedSnapshot<'cx, 'tcx>)
                                  -> Vec<PredicateObligation<'tcx>>
     {
         debug!("impl_or_trait_obligations(def_id={:?})", def_id);