Auto merge of #21523 - nikomatsakis:issue-21245-japaric-ti-failure, r=eddyb

This also includes some miscellaneous cleanup. This is kind of a band-aid but it fixes the problems @japaric was encountering.

r? @eddyb 

19 files changed, 326 insertions, 125 deletions

diff --git a/src/librustc/middle/infer/mod.rs b/src/librustc/middle/infer/mod.rs
index 8fd44f144e1..eaec4fac0a3 100644
--- a/src/librustc/middle/infer/mod.rs
+++ b/src/librustc/middle/infer/mod.rs
@@ -79,16 +79,13 @@ pub struct InferCtxt<'a, 'tcx: 'a> {
     type_variables: RefCell<type_variable::TypeVariableTable<'tcx>>,
 
     // Map from integral variable to the kind of integer it represents
-    int_unification_table:
-        RefCell<UnificationTable<ty::IntVid, Option<IntVarValue>>>,
+    int_unification_table: RefCell<UnificationTable<ty::IntVid>>,
 
     // Map from floating variable to the kind of float it represents
-    float_unification_table:
-        RefCell<UnificationTable<ty::FloatVid, Option<ast::FloatTy>>>,
+    float_unification_table: RefCell<UnificationTable<ty::FloatVid>>,
 
     // For region variables.
-    region_vars:
-        RegionVarBindings<'a, 'tcx>,
+    region_vars: RegionVarBindings<'a, 'tcx>,
 }
 
 /// A map returned by `skolemize_late_bound_regions()` indicating the skolemized
diff --git a/src/librustc/middle/infer/type_variable.rs b/src/librustc/middle/infer/type_variable.rs
index 3f3e4c50e70..4bbc5035799 100644
--- a/src/librustc/middle/infer/type_variable.rs
+++ b/src/librustc/middle/infer/type_variable.rs
@@ -19,7 +19,7 @@ use std::u32;
 use util::snapshot_vec as sv;
 
 pub struct TypeVariableTable<'tcx> {
-    values: sv::SnapshotVec<TypeVariableData<'tcx>,UndoEntry,Delegate>,
+    values: sv::SnapshotVec<Delegate<'tcx>>,
 }
 
 struct TypeVariableData<'tcx> {
@@ -42,7 +42,7 @@ enum UndoEntry {
     Relate(ty::TyVid, ty::TyVid),
 }
 
-struct Delegate;
+struct Delegate<'tcx>;
 
 type Relation = (RelationDir, ty::TyVid);
 
@@ -195,9 +195,12 @@ impl<'tcx> TypeVariableTable<'tcx> {
     }
 }
 
-impl<'tcx> sv::SnapshotVecDelegate<TypeVariableData<'tcx>,UndoEntry> for Delegate {
+impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> {
+    type Value = TypeVariableData<'tcx>;
+    type Undo = UndoEntry;
+
     fn reverse(&mut self,
-               values: &mut Vec<TypeVariableData>,
+               values: &mut Vec<TypeVariableData<'tcx>>,
                action: UndoEntry) {
         match action {
             SpecifyVar(vid, relations) => {
diff --git a/src/librustc/middle/infer/unify.rs b/src/librustc/middle/infer/unify.rs
index ed11cafdca9..e15eb9c0576 100644
--- a/src/librustc/middle/infer/unify.rs
+++ b/src/librustc/middle/infer/unify.rs
@@ -19,7 +19,6 @@ use middle::infer::InferCtxt;
 use std::cell::RefCell;
 use std::fmt::Debug;
 use syntax::ast;
-use util::ppaux::Repr;
 use util::snapshot_vec as sv;
 
 /// This trait is implemented by any type that can serve as a type
@@ -32,7 +31,9 @@ use util::snapshot_vec as sv;
 /// (possibly not yet known) sort of integer.
 ///
 /// Implementations of this trait are at the end of this file.
-pub trait UnifyKey<'tcx, V> : Clone + Debug + PartialEq + Repr<'tcx> {
+pub trait UnifyKey : Clone + Debug + PartialEq {
+    type Value : UnifyValue;
+
     fn index(&self) -> uint;
 
     fn from_index(u: uint) -> Self;
@@ -40,7 +41,7 @@ pub trait UnifyKey<'tcx, V> : Clone + Debug + PartialEq + Repr<'tcx> {
     // Given an inference context, returns the unification table
     // appropriate to this key type.
     fn unification_table<'v>(infcx: &'v InferCtxt)
-                             -> &'v RefCell<UnificationTable<Self,V>>;
+                             -> &'v RefCell<UnificationTable<Self>>;
 
     fn tag(k: Option<Self>) -> &'static str;
 }
@@ -51,7 +52,7 @@ pub trait UnifyKey<'tcx, V> : Clone + Debug + PartialEq + Repr<'tcx> {
 /// whose value is not yet set).
 ///
 /// Implementations of this trait are at the end of this file.
-pub trait UnifyValue<'tcx> : Clone + Repr<'tcx> + PartialEq {
+pub trait UnifyValue : Clone + PartialEq + Debug {
 }
 
 /// Value of a unification key. We implement Tarjan's union-find
@@ -62,21 +63,21 @@ pub trait UnifyValue<'tcx> : Clone + Repr<'tcx> + PartialEq {
 /// to keep the DAG relatively balanced, which helps keep the running
 /// time of the algorithm under control. For more information, see
 /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
-#[derive(PartialEq,Clone)]
-pub enum VarValue<K,V> {
+#[derive(PartialEq,Clone,Show)]
+pub enum VarValue<K:UnifyKey> {
     Redirect(K),
-    Root(V, uint),
+    Root(K::Value, uint),
 }
 
 /// Table of unification keys and their values.
-pub struct UnificationTable<K,V> {
+pub struct UnificationTable<K:UnifyKey> {
     /// Indicates the current value of each key.
-    values: sv::SnapshotVec<VarValue<K,V>,(),Delegate>,
+    values: sv::SnapshotVec<Delegate<K>>,
 }
 
 /// At any time, users may snapshot a unification table.  The changes
 /// made during the snapshot may either be *committed* or *rolled back*.
-pub struct Snapshot<K> {
+pub struct Snapshot<K:UnifyKey> {
     // Link snapshot to the key type `K` of the table.
     marker: marker::CovariantType<K>,
     snapshot: sv::Snapshot,
@@ -84,22 +85,22 @@ pub struct Snapshot<K> {
 
 /// Internal type used to represent the result of a `get()` operation.
 /// Conveys the current root and value of the key.
-pub struct Node<K,V> {
+pub struct Node<K:UnifyKey> {
     pub key: K,
-    pub value: V,
+    pub value: K::Value,
     pub rank: uint,
 }
 
 #[derive(Copy)]
-pub struct Delegate;
+pub struct Delegate<K>;
 
 // We can't use V:LatticeValue, much as I would like to,
 // because frequently the pattern is that V=Option<U> for some
 // other type parameter U, and we have no way to say
 // Option<U>:LatticeValue.
 
-impl<'tcx, V:PartialEq+Clone+Repr<'tcx>, K:UnifyKey<'tcx, V>> UnificationTable<K,V> {
-    pub fn new() -> UnificationTable<K,V> {
+impl<K:UnifyKey> UnificationTable<K> {
+    pub fn new() -> UnificationTable<K> {
         UnificationTable {
             values: sv::SnapshotVec::new(Delegate),
         }
@@ -126,7 +127,7 @@ impl<'tcx, V:PartialEq+Clone+Repr<'tcx>, K:UnifyKey<'tcx, V>> UnificationTable<K
         self.values.commit(snapshot.snapshot);
     }
 
-    pub fn new_key(&mut self, value: V) -> K {
+    pub fn new_key(&mut self, value: K::Value) -> K {
         let index = self.values.push(Root(value, 0));
         let k = UnifyKey::from_index(index);
         debug!("{}: created new key: {:?}",
@@ -137,12 +138,12 @@ impl<'tcx, V:PartialEq+Clone+Repr<'tcx>, K:UnifyKey<'tcx, V>> UnificationTable<K
 
     /// Find the root node for `vid`. This uses the standard union-find algorithm with path
     /// compression: http://en.wikipedia.org/wiki/Disjoint-set_data_structure
-    pub fn get(&mut self, tcx: &ty::ctxt, vid: K) -> Node<K,V> {
+    pub fn get(&mut self, tcx: &ty::ctxt, vid: K) -> Node<K> {
         let index = vid.index();
         let value = (*self.values.get(index)).clone();
         match value {
             Redirect(redirect) => {
-                let node: Node<K,V> = self.get(tcx, redirect.clone());
+                let node: Node<K> = self.get(tcx, redirect.clone());
                 if node.key != redirect {
                     // Path compression
                     self.values.set(index, Redirect(node.key.clone()));
@@ -164,16 +165,15 @@ impl<'tcx, V:PartialEq+Clone+Repr<'tcx>, K:UnifyKey<'tcx, V>> UnificationTable<K
 
     /// Sets the value for `vid` to `new_value`. `vid` MUST be a root node! Also, we must be in the
     /// middle of a snapshot.
-    pub fn set(&mut self,
-               tcx: &ty::ctxt<'tcx>,
-               key: K,
-               new_value: VarValue<K,V>)
+    pub fn set<'tcx>(&mut self,
+                     _tcx: &ty::ctxt<'tcx>,
+                     key: K,
+                     new_value: VarValue<K>)
     {
         assert!(self.is_root(&key));
 
-        debug!("Updating variable {} to {}",
-               key.repr(tcx),
-               new_value.repr(tcx));
+        debug!("Updating variable {:?} to {:?}",
+               key, new_value);
 
         self.values.set(key.index(), new_value);
     }
@@ -181,16 +181,16 @@ impl<'tcx, V:PartialEq+Clone+Repr<'tcx>, K:UnifyKey<'tcx, V>> UnificationTable<K
     /// Either redirects node_a to node_b or vice versa, depending on the relative rank. Returns
     /// the new root and rank. You should then update the value of the new root to something
     /// suitable.
-    pub fn unify(&mut self,
-                 tcx: &ty::ctxt<'tcx>,
-                 node_a: &Node<K,V>,
-                 node_b: &Node<K,V>)
-                 -> (K, uint)
+    pub fn unify<'tcx>(&mut self,
+                       tcx: &ty::ctxt<'tcx>,
+                       node_a: &Node<K>,
+                       node_b: &Node<K>)
+                       -> (K, uint)
     {
-        debug!("unify(node_a(id={}, rank={}), node_b(id={}, rank={}))",
-               node_a.key.repr(tcx),
+        debug!("unify(node_a(id={:?}, rank={:?}), node_b(id={:?}, rank={:?}))",
+               node_a.key,
                node_a.rank,
-               node_b.key.repr(tcx),
+               node_b.key,
                node_b.rank);
 
         if node_a.rank > node_b.rank {
@@ -212,8 +212,11 @@ impl<'tcx, V:PartialEq+Clone+Repr<'tcx>, K:UnifyKey<'tcx, V>> UnificationTable<K
     }
 }
 
-impl<K,V> sv::SnapshotVecDelegate<VarValue<K,V>,()> for Delegate {
-    fn reverse(&mut self, _: &mut Vec<VarValue<K,V>>, _: ()) {
+impl<K> sv::SnapshotVecDelegate for Delegate<K> {
+    type Value = VarValue<K>;
+    type Undo = ();
+
+    fn reverse(&mut self, _: &mut Vec<VarValue<K>>, _: ()) {
         panic!("Nothing to reverse");
     }
 }
@@ -224,7 +227,7 @@ impl<K,V> sv::SnapshotVecDelegate<VarValue<K,V>,()> for Delegate {
 
 /// Indicates a type that does not have any kind of subtyping
 /// relationship.
-pub trait SimplyUnifiable<'tcx> : Clone + PartialEq + Repr<'tcx> {
+pub trait SimplyUnifiable<'tcx> : Clone + PartialEq + Debug {
     fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx>;
     fn to_type_err(expected_found<Self>) -> ty::type_err<'tcx>;
 }
@@ -242,8 +245,11 @@ pub fn err<'tcx, V:SimplyUnifiable<'tcx>>(a_is_expected: bool,
     }
 }
 
-pub trait InferCtxtMethodsForSimplyUnifiableTypes<'tcx, V:SimplyUnifiable<'tcx>,
-                                                  K:UnifyKey<'tcx, Option<V>>> {
+pub trait InferCtxtMethodsForSimplyUnifiableTypes<'tcx,K,V>
+    where K : UnifyKey<Value=Option<V>>,
+          V : SimplyUnifiable<'tcx>,
+          Option<V> : UnifyValue,
+{
     fn simple_vars(&self,
                    a_is_expected: bool,
                    a_id: K,
@@ -257,8 +263,10 @@ pub trait InferCtxtMethodsForSimplyUnifiableTypes<'tcx, V:SimplyUnifiable<'tcx>,
     fn probe_var(&self, a_id: K) -> Option<Ty<'tcx>>;
 }
 
-impl<'a,'tcx,V:SimplyUnifiable<'tcx>,K:UnifyKey<'tcx, Option<V>>>
-    InferCtxtMethodsForSimplyUnifiableTypes<'tcx, V, K> for InferCtxt<'a, 'tcx>
+impl<'a,'tcx,V,K> InferCtxtMethodsForSimplyUnifiableTypes<'tcx,K,V> for InferCtxt<'a,'tcx>
+    where K : UnifyKey<Value=Option<V>>,
+          V : SimplyUnifiable<'tcx>,
+          Option<V> : UnifyValue,
 {
     /// Unifies two simple keys. Because simple keys do not have any subtyping relationships, if
     /// both keys have already been associated with a value, then those two values must be the
@@ -271,8 +279,8 @@ impl<'a,'tcx,V:SimplyUnifiable<'tcx>,K:UnifyKey<'tcx, Option<V>>>
     {
         let tcx = self.tcx;
         let table = UnifyKey::unification_table(self);
-        let node_a = table.borrow_mut().get(tcx, a_id);
-        let node_b = table.borrow_mut().get(tcx, b_id);
+        let node_a: Node<K> = table.borrow_mut().get(tcx, a_id);
+        let node_b: Node<K> = table.borrow_mut().get(tcx, b_id);
         let a_id = node_a.key.clone();
         let b_id = node_b.key.clone();
 
@@ -346,14 +354,14 @@ impl<'a,'tcx,V:SimplyUnifiable<'tcx>,K:UnifyKey<'tcx, Option<V>>>
 
 // Integral type keys
 
-impl<'tcx> UnifyKey<'tcx, Option<IntVarValue>> for ty::IntVid {
+impl UnifyKey for ty::IntVid {
+    type Value = Option<IntVarValue>;
+
     fn index(&self) -> uint { self.index as uint }
 
     fn from_index(i: uint) -> ty::IntVid { ty::IntVid { index: i as u32 } }
 
-    fn unification_table<'v>(infcx: &'v InferCtxt)
-        -> &'v RefCell<UnificationTable<ty::IntVid, Option<IntVarValue>>>
-    {
+    fn unification_table<'v>(infcx: &'v InferCtxt) -> &'v RefCell<UnificationTable<ty::IntVid>> {
         return &infcx.int_unification_table;
     }
 
@@ -375,18 +383,18 @@ impl<'tcx> SimplyUnifiable<'tcx> for IntVarValue {
     }
 }
 
-impl<'tcx> UnifyValue<'tcx> for Option<IntVarValue> { }
+impl UnifyValue for Option<IntVarValue> { }
 
 // Floating point type keys
 
-impl<'tcx> UnifyKey<'tcx, Option<ast::FloatTy>> for ty::FloatVid {
+impl UnifyKey for ty::FloatVid {
+    type Value = Option<ast::FloatTy>;
+
     fn index(&self) -> uint { self.index as uint }
 
     fn from_index(i: uint) -> ty::FloatVid { ty::FloatVid { index: i as u32 } }
 
-    fn unification_table<'v>(infcx: &'v InferCtxt)
-        -> &'v RefCell<UnificationTable<ty::FloatVid, Option<ast::FloatTy>>>
-    {
+    fn unification_table<'v>(infcx: &'v InferCtxt) -> &'v RefCell<UnificationTable<ty::FloatVid>> {
         return &infcx.float_unification_table;
     }
 
@@ -395,7 +403,7 @@ impl<'tcx> UnifyKey<'tcx, Option<ast::FloatTy>> for ty::FloatVid {
     }
 }
 
-impl<'tcx> UnifyValue<'tcx> for Option<ast::FloatTy> {
+impl UnifyValue for Option<ast::FloatTy> {
 }
 
 impl<'tcx> SimplyUnifiable<'tcx> for ast::FloatTy {
@@ -407,12 +415,3 @@ impl<'tcx> SimplyUnifiable<'tcx> for ast::FloatTy {
         ty::terr_float_mismatch(err)
     }
 }
-
-impl<'tcx, K:Repr<'tcx>, V:Repr<'tcx>> Repr<'tcx> for VarValue<K,V> {
-    fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
-        match *self {
-            Redirect(ref k) => format!("Redirect({})", k.repr(tcx)),
-            Root(ref v, r) => format!("Root({}, {})", v.repr(tcx), r)
-        }
-    }
-}
diff --git a/src/librustc/middle/traits/fulfill.rs b/src/librustc/middle/traits/fulfill.rs
index d08857c9613..ed058280483 100644
--- a/src/librustc/middle/traits/fulfill.rs
+++ b/src/librustc/middle/traits/fulfill.rs
@@ -394,7 +394,7 @@ fn process_predicate<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
         ty::Predicate::Projection(ref data) => {
             let project_obligation = obligation.with(data.clone());
             let result = project::poly_project_and_unify_type(selcx, &project_obligation);
-            debug!("poly_project_and_unify_type({}) = {}",
+            debug!("process_predicate: poly_project_and_unify_type({}) returned {}",
                    project_obligation.repr(tcx),
                    result.repr(tcx));
             match result {
diff --git a/src/librustc/middle/traits/project.rs b/src/librustc/middle/traits/project.rs
index ffb38091a87..c179153dbde 100644
--- a/src/librustc/middle/traits/project.rs
+++ b/src/librustc/middle/traits/project.rs
@@ -65,7 +65,7 @@ pub fn poly_project_and_unify_type<'cx,'tcx>(
     obligation: &PolyProjectionObligation<'tcx>)
     -> Result<Option<Vec<PredicateObligation<'tcx>>>, MismatchedProjectionTypes<'tcx>>
 {
-    debug!("poly_project(obligation={})",
+    debug!("poly_project_and_unify_type(obligation={})",
            obligation.repr(selcx.tcx()));
 
     let infcx = selcx.infcx();
@@ -109,7 +109,7 @@ fn project_and_unify_type<'cx,'tcx>(
     obligation: &ProjectionObligation<'tcx>)
     -> Result<Option<Vec<PredicateObligation<'tcx>>>, MismatchedProjectionTypes<'tcx>>
 {
-    debug!("project_and_unify(obligation={})",
+    debug!("project_and_unify_type(obligation={})",
            obligation.repr(selcx.tcx()));
 
     let Normalized { value: normalized_ty, obligations } =
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index b2e8bbe059f..b18cb86a2f4 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -526,9 +526,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         // If no match, compute result and insert into cache.
         let candidate = self.candidate_from_obligation_no_cache(stack);
-        debug!("CACHE MISS: cache_fresh_trait_pred={}, candidate={}",
-               cache_fresh_trait_pred.repr(self.tcx()), candidate.repr(self.tcx()));
-        self.insert_candidate_cache(cache_fresh_trait_pred, candidate.clone());
+
+        if self.should_update_candidate_cache(&cache_fresh_trait_pred, &candidate) {
+            debug!("CACHE MISS: cache_fresh_trait_pred={}, candidate={}",
+                   cache_fresh_trait_pred.repr(self.tcx()), candidate.repr(self.tcx()));
+            self.insert_candidate_cache(cache_fresh_trait_pred, candidate.clone());
+        }
+
         candidate
     }
 
@@ -705,6 +709,47 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         hashmap.insert(cache_fresh_trait_pred.0.trait_ref.clone(), candidate);
     }
 
+    fn should_update_candidate_cache(&mut self,
+                                     cache_fresh_trait_pred: &ty::PolyTraitPredicate<'tcx>,
+                                     candidate: &SelectionResult<'tcx, SelectionCandidate<'tcx>>)
+                                     -> bool
+    {
+        // In general, it's a good idea to cache results, even
+        // ambigious ones, to save us some trouble later. But we have
+        // to be careful not to cache results that could be
+        // invalidated later by advances in inference. Normally, this
+        // is not an issue, because any inference variables whose
+        // types are not yet bound are "freshened" in the cache key,
+        // which means that if we later get the same request once that
+        // type variable IS bound, we'll have a different cache key.
+        // For example, if we have `Vec<_#0t> : Foo`, and `_#0t` is
+        // not yet known, we may cache the result as `None`. But if
+        // later `_#0t` is bound to `Bar`, then when we freshen we'll
+        // have `Vec<Bar> : Foo` as the cache key.
+        //
+        // HOWEVER, it CAN happen that we get an ambiguity result in
+        // one particular case around closures where the cache key
+        // would not change. That is when the precise types of the
+        // upvars that a closure references have not yet been figured
+        // out (i.e., because it is not yet known if they are captured
+        // by ref, and if by ref, what kind of ref). In these cases,
+        // when matching a builtin bound, we will yield back an
+        // ambiguous result. But the *cache key* is just the closure type,
+        // it doesn't capture the state of the upvar computation.
+        //
+        // To avoid this trap, just don't cache ambiguous results if
+        // the self-type contains no inference byproducts (that really
+        // shouldn't happen in other circumstances anyway, given
+        // coherence).
+
+        match *candidate {
+            Ok(Some(_)) | Err(_) => true,
+            Ok(None) => {
+                cache_fresh_trait_pred.0.input_types().iter().any(|&t| ty::type_has_ty_infer(t))
+            }
+        }
+    }
+
     fn assemble_candidates<'o>(&mut self,
                                stack: &TraitObligationStack<'o, 'tcx>)
                                -> Result<SelectionCandidateSet<'tcx>, SelectionError<'tcx>>
@@ -788,6 +833,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 // FIXME(#20297) -- being strict about this can cause
                 // inference failures with BorrowFrom, which is
                 // unfortunate. Can we do better here?
+                debug!("assemble_candidates_for_projected_tys: ambiguous self-type");
                 candidates.ambiguous = true;
                 return;
             }
@@ -962,6 +1008,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let (closure_def_id, substs) = match self_ty.sty {
             ty::ty_closure(id, _, ref substs) => (id, substs.clone()),
             ty::ty_infer(ty::TyVar(_)) => {
+                debug!("assemble_unboxed_closure_candidates: ambiguous self-type");
                 candidates.ambiguous = true;
                 return Ok(());
             }
@@ -1000,6 +1047,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let self_ty = self.infcx.shallow_resolve(obligation.self_ty());
         match self_ty.sty {
             ty::ty_infer(ty::TyVar(_)) => {
+                debug!("assemble_fn_pointer_candidates: ambiguous self-type");
                 candidates.ambiguous = true; // could wind up being a fn() type
             }
 
@@ -1270,7 +1318,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 Ok(())
             }
             Ok(ParameterBuiltin) => { Ok(()) }
-            Ok(AmbiguousBuiltin) => { Ok(candidates.ambiguous = true) }
+            Ok(AmbiguousBuiltin) => {
+                debug!("assemble_builtin_bound_candidates: ambiguous builtin");
+                Ok(candidates.ambiguous = true)
+            }
             Err(e) => { Err(e) }
         }
     }
@@ -1476,6 +1527,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                         Ok(If(upvars.iter().map(|c| c.ty).collect()))
                     }
                     None => {
+                        debug!("assemble_builtin_bound_candidates: no upvar types available yet");
                         Ok(AmbiguousBuiltin)
                     }
                 }
@@ -1512,6 +1564,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 // Unbound type variable. Might or might not have
                 // applicable impls and so forth, depending on what
                 // those type variables wind up being bound to.
+                debug!("assemble_builtin_bound_candidates: ambiguous builtin");
                 Ok(AmbiguousBuiltin)
             }
 
diff --git a/src/librustc/util/snapshot_vec.rs b/src/librustc/util/snapshot_vec.rs
index 8fc95529bc0..151173b3a40 100644
--- a/src/librustc/util/snapshot_vec.rs
+++ b/src/librustc/util/snapshot_vec.rs
@@ -22,8 +22,7 @@ use self::UndoLog::*;
 
 use std::mem;
 
-#[derive(PartialEq)]
-pub enum UndoLog<T,U> {
+pub enum UndoLog<D:SnapshotVecDelegate> {
     /// Indicates where a snapshot started.
     OpenSnapshot,
 
@@ -34,15 +33,15 @@ pub enum UndoLog<T,U> {
     NewElem(uint),
 
     /// Variable with given index was changed *from* the given value.
-    SetElem(uint, T),
+    SetElem(uint, D::Value),
 
     /// Extensible set of actions
-    Other(U)
+    Other(D::Undo)
 }
 
-pub struct SnapshotVec<T,U,D> {
-    values: Vec<T>,
-    undo_log: Vec<UndoLog<T,U>>,
+pub struct SnapshotVec<D:SnapshotVecDelegate> {
+    values: Vec<D::Value>,
+    undo_log: Vec<UndoLog<D>>,
     delegate: D
 }
 
@@ -53,12 +52,15 @@ pub struct Snapshot {
     length: uint,
 }
 
-pub trait SnapshotVecDelegate<T,U> {
-    fn reverse(&mut self, values: &mut Vec<T>, action: U);
+pub trait SnapshotVecDelegate {
+    type Value;
+    type Undo;
+
+    fn reverse(&mut self, values: &mut Vec<Self::Value>, action: Self::Undo);
 }
 
-impl<T,U,D:SnapshotVecDelegate<T,U>> SnapshotVec<T,U,D> {
-    pub fn new(delegate: D) -> SnapshotVec<T,U,D> {
+impl<D:SnapshotVecDelegate> SnapshotVec<D> {
+    pub fn new(delegate: D) -> SnapshotVec<D> {
         SnapshotVec {
             values: Vec::new(),
             undo_log: Vec::new(),
@@ -70,13 +72,13 @@ impl<T,U,D:SnapshotVecDelegate<T,U>> SnapshotVec<T,U,D> {
         !self.undo_log.is_empty()
     }
 
-    pub fn record(&mut self, action: U) {
+    pub fn record(&mut self, action: D::Undo) {
         if self.in_snapshot() {
             self.undo_log.push(Other(action));
         }
     }
 
-    pub fn push(&mut self, elem: T) -> uint {
+    pub fn push(&mut self, elem: D::Value) -> uint {
         let len = self.values.len();
         self.values.push(elem);
 
@@ -87,20 +89,20 @@ impl<T,U,D:SnapshotVecDelegate<T,U>> SnapshotVec<T,U,D> {
         len
     }
 
-    pub fn get<'a>(&'a self, index: uint) -> &'a T {
+    pub fn get<'a>(&'a self, index: uint) -> &'a D::Value {
         &self.values[index]
     }
 
     /// Returns a mutable pointer into the vec; whatever changes you make here cannot be undone
     /// automatically, so you should be sure call `record()` with some sort of suitable undo
     /// action.
-    pub fn get_mut<'a>(&'a mut self, index: uint) -> &'a mut T {
+    pub fn get_mut<'a>(&'a mut self, index: uint) -> &'a mut D::Value {
         &mut self.values[index]
     }
 
     /// Updates the element at the given index. The old value will saved (and perhaps restored) if
     /// a snapshot is active.
-    pub fn set(&mut self, index: uint, new_elem: T) {
+    pub fn set(&mut self, index: uint, new_elem: D::Value) {
         let old_elem = mem::replace(&mut self.values[index], new_elem);
         if self.in_snapshot() {
             self.undo_log.push(SetElem(index, old_elem));
@@ -115,7 +117,7 @@ impl<T,U,D:SnapshotVecDelegate<T,U>> SnapshotVec<T,U,D> {
 
     pub fn actions_since_snapshot(&self,
                                   snapshot: &Snapshot)
-                                  -> &[UndoLog<T,U>] {
+                                  -> &[UndoLog<D>] {
         &self.undo_log[snapshot.length..]
     }
 
diff --git a/src/librustc_typeck/check/demand.rs b/src/librustc_typeck/check/demand.rs
index a51e89c1669..8188835718c 100644
--- a/src/librustc_typeck/check/demand.rs
+++ b/src/librustc_typeck/check/demand.rs
@@ -60,7 +60,8 @@ pub fn coerce<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>, sp: Span,
     debug!("demand::coerce(expected = {}, expr_ty = {})",
            expected.repr(fcx.ccx.tcx),
            expr_ty.repr(fcx.ccx.tcx));
-    let expected = fcx.infcx().resolve_type_vars_if_possible(&expected);
+    let expr_ty = fcx.resolve_type_vars_if_possible(expr_ty);
+    let expected = fcx.resolve_type_vars_if_possible(expected);
     match fcx.mk_assignty(expr, expr_ty, expected) {
       Ok(()) => { /* ok */ }
       Err(ref err) => {
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 65560040f47..09b65bcb1fc 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -1242,6 +1242,36 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
         self.ccx.tcx.sess.err_count() - self.err_count_on_creation
     }
 
+    /// Resolves type variables in `ty` if possible. Unlike the infcx
+    /// version, this version will also select obligations if it seems
+    /// useful, in an effort to get more type information.
+    fn resolve_type_vars_if_possible(&self, mut ty: Ty<'tcx>) -> Ty<'tcx> {
+        // No ty::infer()? Nothing needs doing.
+        if !ty::type_has_ty_infer(ty) {
+            return ty;
+        }
+
+        // If `ty` is a type variable, see whether we already know what it is.
+        ty = self.infcx().resolve_type_vars_if_possible(&ty);
+        if !ty::type_has_ty_infer(ty) {
+            return ty;
+        }
+
+        // If not, try resolving any new fcx obligations that have cropped up.
+        vtable::select_new_fcx_obligations(self);
+        ty = self.infcx().resolve_type_vars_if_possible(&ty);
+        if !ty::type_has_ty_infer(ty) {
+            return ty;
+        }
+
+        // If not, try resolving *all* pending obligations as much as
+        // possible. This can help substantially when there are
+        // indirect dependencies that don't seem worth tracking
+        // precisely.
+        vtable::select_fcx_obligations_where_possible(self);
+        self.infcx().resolve_type_vars_if_possible(&ty)
+    }
+
     /// Resolves all type variables in `t` and then, if any were left
     /// unresolved, substitutes an error type. This is used after the
     /// main checking when doing a second pass before writeback. The
@@ -2333,9 +2363,9 @@ fn check_argument_types<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
         let check_blocks = *check_blocks;
         debug!("check_blocks={}", check_blocks);
 
-        // More awful hacks: before we check the blocks, try to do
-        // an "opportunistic" vtable resolution of any trait
-        // bounds on the call.
+        // More awful hacks: before we check argument types, try to do
+        // an "opportunistic" vtable resolution of any trait bounds on
+        // the call. This helps coercions.
         if check_blocks {
             vtable::select_new_fcx_obligations(fcx);
         }
@@ -2875,7 +2905,7 @@ fn check_expr_with_unifier<'a, 'tcx, F>(fcx: &FnCtxt<'a, 'tcx>,
             // Shift is a special case: rhs must be uint, no matter what lhs is
             check_expr(fcx, &**rhs);
             let rhs_ty = fcx.expr_ty(&**rhs);
-            let rhs_ty = fcx.infcx().resolve_type_vars_if_possible(&rhs_ty);
+            let rhs_ty = structurally_resolved_type(fcx, rhs.span, rhs_ty);
             if ty::type_is_integral(rhs_ty) {
                 fcx.write_ty(expr.id, lhs_t);
             } else {
@@ -5127,21 +5157,12 @@ pub fn instantiate_path<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
 
 // Resolves `typ` by a single level if `typ` is a type variable.  If no
 // resolution is possible, then an error is reported.
-pub fn structurally_resolved_type<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>, sp: Span,
-                                            mut ty: Ty<'tcx>) -> Ty<'tcx> {
-    // If `ty` is a type variable, see whether we already know what it is.
-    ty = fcx.infcx().shallow_resolve(ty);
-
-    // If not, try resolve pending fcx obligations. Those can shed light.
-    //
-    // FIXME(#18391) -- This current strategy can lead to bad performance in
-    // extreme cases.  We probably ought to smarter in general about
-    // only resolving when we need help and only resolving obligations
-    // will actually help.
-    if ty::type_is_ty_var(ty) {
-        vtable::select_fcx_obligations_where_possible(fcx);
-        ty = fcx.infcx().shallow_resolve(ty);
-    }
+pub fn structurally_resolved_type<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
+                                            sp: Span,
+                                            ty: Ty<'tcx>)
+                                            -> Ty<'tcx>
+{
+    let mut ty = fcx.resolve_type_vars_if_possible(ty);
 
     // If not, error.
     if ty::type_is_ty_var(ty) {
diff --git a/src/test/compile-fail/associated-type-projection-from-supertrait.rs b/src/test/compile-fail/associated-type-projection-from-supertrait.rs
index abaf79fb4cb..b388b6a28e3 100644
--- a/src/test/compile-fail/associated-type-projection-from-supertrait.rs
+++ b/src/test/compile-fail/associated-type-projection-from-supertrait.rs
@@ -40,8 +40,8 @@ impl Car for ModelU { }
 
 fn dent<C:Car>(c: C, color: C::Color) { c.chip_paint(color) }
 fn a() { dent(ModelT, Black); }
-fn b() { dent(ModelT, Blue); } //~ ERROR type mismatch
-fn c() { dent(ModelU, Black); } //~ ERROR type mismatch
+fn b() { dent(ModelT, Blue); } //~ ERROR mismatched types
+fn c() { dent(ModelU, Black); } //~ ERROR mismatched types
 fn d() { dent(ModelU, Blue); }
 
 ///////////////////////////////////////////////////////////////////////////
diff --git a/src/test/compile-fail/associated-types-path-2.rs b/src/test/compile-fail/associated-types-path-2.rs
index 5cb9aca8beb..55ba65d6102 100644
--- a/src/test/compile-fail/associated-types-path-2.rs
+++ b/src/test/compile-fail/associated-types-path-2.rs
@@ -25,7 +25,7 @@ pub fn f2<T: Foo>(a: T) -> T::A {
 
 pub fn f1_int_int() {
     f1(2is, 4is);
-    //~^ ERROR type mismatch resolving
+    //~^ ERROR mismatched types
     //~| expected usize
     //~| found isize
 }
@@ -51,8 +51,6 @@ pub fn f2_int() {
     //~^ ERROR mismatched types
     //~| expected `isize`
     //~| found `usize`
-    //~| expected isize
-    //~| found usize
 }
 
 pub fn main() { }
diff --git a/src/test/compile-fail/issue-18400.rs b/src/test/compile-fail/issue-18400.rs
index a6662e78f3e..f3b2b3d5667 100644
--- a/src/test/compile-fail/issue-18400.rs
+++ b/src/test/compile-fail/issue-18400.rs
@@ -32,5 +32,8 @@ fn main() {
     let bits: &[_] = &[0, 1];
 
     0.contains(bits);
-//~^ ERROR the trait `Set<_>` is not implemented for the type `_`
+    //~^ ERROR overflow
+    //~| ERROR overflow
+    //~| ERROR overflow
+    //~| ERROR mismatched types
 }
diff --git a/src/test/compile-fail/issue-21160.rs b/src/test/compile-fail/issue-21160.rs
index 0ee38166935..45b7fbbd0b4 100644
--- a/src/test/compile-fail/issue-21160.rs
+++ b/src/test/compile-fail/issue-21160.rs
@@ -16,6 +16,6 @@ impl Bar {
 
 #[derive(Hash)]
 struct Foo(Bar);
-//~^ error: the trait `core::hash::Hash<__S>` is not implemented for the type `Bar`
+//~^ error: the trait `core::hash::Hash<_>` is not implemented for the type `Bar`
 
 fn main() {}
diff --git a/src/test/compile-fail/shift-various-bad-types.rs b/src/test/compile-fail/shift-various-bad-types.rs
index 66aef0ec3a1..901ae1d5e2a 100644
--- a/src/test/compile-fail/shift-various-bad-types.rs
+++ b/src/test/compile-fail/shift-various-bad-types.rs
@@ -29,7 +29,7 @@ fn foo(p: &Panolpy) {
     // known to be an integer, but meh.
     let x;
     22 >> x;
-    //~^ ERROR right-hand-side of a shift operation must have integral type
+    //~^ ERROR the type of this value must be known in this context
 
     22 >> 1;
     // Integer literal types are OK
diff --git a/src/test/compile-fail/slice-mut.rs b/src/test/compile-fail/slice-mut.rs
index a1747f3b6bd..e6acc325451 100644
--- a/src/test/compile-fail/slice-mut.rs
+++ b/src/test/compile-fail/slice-mut.rs
@@ -13,9 +13,10 @@
 fn main() {
     let x: &[isize] = &[1, 2, 3, 4, 5];
     // Immutable slices are not mutable.
+
     let y: &mut[_] = &x[2..4];
     //~^ ERROR mismatched types
     //~| expected `&mut [_]`
-    //~| found `&_`
+    //~| found `&[isize]`
     //~| values differ in mutability
 }
diff --git a/src/test/compile-fail/traits-multidispatch-bad.rs b/src/test/compile-fail/traits-multidispatch-bad.rs
index e9a4005b4b4..2e29a61846e 100644
--- a/src/test/compile-fail/traits-multidispatch-bad.rs
+++ b/src/test/compile-fail/traits-multidispatch-bad.rs
@@ -26,7 +26,7 @@ where T : Convert<U>
 }
 
 fn a() {
-    test(22is, 44is); //~ ERROR not implemented
+    test(22is, 44is); //~ ERROR mismatched types
 }
 
 fn main() {}
diff --git a/src/test/run-pass/into-iterator-type-inference-shift.rs b/src/test/run-pass/into-iterator-type-inference-shift.rs
new file mode 100644
index 00000000000..26a0abc76ae
--- /dev/null
+++ b/src/test/run-pass/into-iterator-type-inference-shift.rs
@@ -0,0 +1,41 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Regression test for type inference failure around shifting. In this
+// case, the iteration yields an int, but we hadn't run the full type
+// propagation yet, and so we just saw a type variable, yielding an
+// error.
+
+use std::u8;
+
+trait IntoIterator {
+    type Iter: Iterator;
+
+    fn into_iter(self) -> Self::Iter;
+}
+
+impl<I> IntoIterator for I where I: Iterator {
+    type Iter = I;
+
+    fn into_iter(self) -> I {
+        self
+    }
+}
+
+fn desugared_for_loop_bad(byte: u8) -> u8 {
+    let mut result = 0;
+    let mut x = IntoIterator::into_iter(range(0, u8::BITS));
+    let mut y = Iterator::next(&mut x);
+    let mut z = y.unwrap();
+    byte >> z;
+    1
+}
+
+fn main() {}
diff --git a/src/test/run-pass/issue-19499.rs b/src/test/run-pass/issue-19499.rs
new file mode 100644
index 00000000000..04017da9775
--- /dev/null
+++ b/src/test/run-pass/issue-19499.rs
@@ -0,0 +1,20 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Regression test for issue #19499. Due to incorrect caching of trait
+// results for closures with upvars whose types were not fully
+// computed, this rather bizarre little program (along with many more
+// reasonable examples) let to ambiguity errors about not being able
+// to infer sufficient type information.
+
+fn main() {
+    let n = 0;
+    let it = Some(1_us).into_iter().inspect(|_| {n;});
+}
diff --git a/src/test/run-pass/issue-21245.rs b/src/test/run-pass/issue-21245.rs
new file mode 100644
index 00000000000..9205b247e13
--- /dev/null
+++ b/src/test/run-pass/issue-21245.rs
@@ -0,0 +1,62 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Regression test for issue #21245. Check that we are able to infer
+// the types in these examples correctly. It used to be that
+// insufficient type propagation caused the type of the iterator to be
+// incorrectly unified with the `*const` type to which it is coerced.
+
+use std::ptr;
+
+trait IntoIterator {
+    type Iter: Iterator;
+
+    fn into_iter(self) -> Self::Iter;
+}
+
+impl<I> IntoIterator for I where I: Iterator {
+    type Iter = I;
+
+    fn into_iter(self) -> I {
+        self
+    }
+}
+
+fn desugared_for_loop_bad<T>(v: Vec<T>) {
+    match IntoIterator::into_iter(v.iter()) {
+        mut iter => {
+            loop {
+                match ::std::iter::Iterator::next(&mut iter) {
+                    ::std::option::Option::Some(x) => {
+                        unsafe { ptr::read(x); }
+                    },
+                    ::std::option::Option::None => break
+                }
+            }
+        }
+    }
+}
+
+fn desugared_for_loop_good<T>(v: Vec<T>) {
+    match v.iter().into_iter() {
+        mut iter => {
+            loop {
+                match ::std::iter::Iterator::next(&mut iter) {
+                    ::std::option::Option::Some(x) => {
+                        unsafe { ptr::read(x); }
+                    },
+                    ::std::option::Option::None => break
+                }
+            }
+        }
+    }
+}
+
+fn main() {}