-

diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index 21af92a25e..1c9f9b487e 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -1160,6 +1160,19 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         value.fold_with(&mut r)
     }
 
+    /// Returns a set of unresolved type variables found by visiting
+    /// `T`. In the process of visiting `T`, this will resolve (where
+    /// possible) type variables in `T`, but it never constructs the
+    /// final, resolved type, so it's more efficient than
+    /// `resolve_type_vars_if_possible()`.
+    pub fn unresolved_type_vars<T>(&self, value: &T) -> Vec<Ty<'tcx>>
+        where T: TypeFoldable<'tcx>
+    {
+        let mut r = resolve::UnresolvedTypeCollector::new(self);
+        value.visit_with(&mut r);
+        r.into_unresolved_ty_vars()
+    }
+
     pub fn resolve_type_and_region_vars_if_possible<T>(&self, value: &T) -> T
         where T: TypeFoldable<'tcx>
     {
diff --git a/src/librustc/infer/resolve.rs b/src/librustc/infer/resolve.rs
index 639a330dc6..f6e835034f 100644
--- a/src/librustc/infer/resolve.rs
+++ b/src/librustc/infer/resolve.rs
@@ -10,7 +10,7 @@
 
 use super::{InferCtxt, FixupError, FixupResult};
 use ty::{self, Ty, TyCtxt, TypeFoldable};
-use ty::fold::TypeFolder;
+use ty::fold::{TypeFolder, TypeVisitor};
 
 ///////////////////////////////////////////////////////////////////////////
 // OPPORTUNISTIC TYPE RESOLVER
@@ -81,6 +81,49 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for OpportunisticTypeAndRegionResolv
 }
 
 ///////////////////////////////////////////////////////////////////////////
+// UNRESOLVED TYPE COLLECTOR
+
+/// The unresolved type **collector** walks your type and searches for
+/// type variables that don't yet have a value. They get pushed into a
+/// vector. It does not construct the fully resolved type (which might
+/// involve some hashing and so forth).
+pub struct UnresolvedTypeCollector<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
+    infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
+    unresolved_ty_vars: Vec<Ty<'tcx>>,
+}
+
+impl<'a, 'gcx, 'tcx> UnresolvedTypeCollector<'a, 'gcx, 'tcx> {
+    pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>) -> Self {
+        UnresolvedTypeCollector { infcx: infcx, unresolved_ty_vars: vec![] }
+    }
+
+    pub fn into_unresolved_ty_vars(self) -> Vec<Ty<'tcx>> {
+        self.unresolved_ty_vars
+    }
+}
+
+impl<'a, 'gcx, 'tcx> TypeVisitor<'tcx> for UnresolvedTypeCollector<'a, 'gcx, 'tcx> {
+    fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
+        let t = self.infcx.shallow_resolve(t);
+        if t.has_infer_types() {
+            if let ty::TyInfer(_) = t.sty {
+                // Since we called `shallow_resolve` above, this must
+                // be an (as yet...) unresolved inference variable. Log it.
+                self.unresolved_ty_vars.push(t);
+            } else {
+                // Otherwise, visit its contents.
+                t.super_visit_with(self);
+            }
+        } else {
+            // Micro-optimize: no inference types here? Don't visit this subtree..
+        }
+
+        // always return false so that we always keep visiting everything
+        false
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////
 // FULL TYPE RESOLUTION
 
 /// Full type resolution replaces all type and region variables with
diff --git a/src/librustc/traits/project.rs b/src/librustc/traits/project.rs
index 512cfee12b..9ea5e9151f 100644
--- a/src/librustc/traits/project.rs
+++ b/src/librustc/traits/project.rs
@@ -25,7 +25,7 @@ use super::VtableImplData;
 use super::util;
 
 use hir::def_id::DefId;
-use infer::InferOk;
+use infer::{InferCtxt, InferOk};
 use infer::type_variable::TypeVariableOrigin;
 use rustc_data_structures::snapshot_map::{Snapshot, SnapshotMap};
 use syntax::ast;
@@ -416,7 +416,8 @@ fn opt_normalize_projection_type<'a, 'b, 'gcx, 'tcx>(
     // bounds. It might be the case that we want two distinct caches,
     // or else another kind of cache entry.
 
-    match infcx.projection_cache.borrow_mut().try_start(cache_key) {
+    let cache_result = infcx.projection_cache.borrow_mut().try_start(cache_key);
+    match cache_result {
         Ok(()) => { }
         Err(ProjectionCacheEntry::Ambiguous) => {
             // If we found ambiguity the last time, that generally
@@ -466,7 +467,7 @@ fn opt_normalize_projection_type<'a, 'b, 'gcx, 'tcx>(
                                                     projection_ty);
             selcx.infcx().report_overflow_error(&obligation, false);
         }
-        Err(ProjectionCacheEntry::NormalizedTy(ty)) => {
+        Err(ProjectionCacheEntry::NormalizedTy(mut ty)) => {
             // If we find the value in the cache, then return it along
             // with the obligations that went along with it. Note
             // that, when using a fulfillment context, these
@@ -479,6 +480,15 @@ fn opt_normalize_projection_type<'a, 'b, 'gcx, 'tcx>(
             debug!("opt_normalize_projection_type: \
                     found normalized ty `{:?}`",
                    ty);
+            ty.value = infcx.resolve_type_vars_if_possible(&ty.value);
+
+            // Once we have inferred everything we need to know, we
+            // can ignore the `obligations` from that point on.
+            if !ty.value.has_infer_types() {
+                infcx.projection_cache.borrow_mut().complete(cache_key);
+                ty.obligations = vec![];
+            }
+
             return Some(ty);
         }
         Err(ProjectionCacheEntry::Error) => {
@@ -527,7 +537,11 @@ fn opt_normalize_projection_type<'a, 'b, 'gcx, 'tcx>(
                     obligations,
                 }
             };
-            infcx.projection_cache.borrow_mut().insert_ty(cache_key, &result);
+
+            let mut cache_value = result.clone();
+            prune_cache_value_obligations(infcx, &mut cache_value);
+            infcx.projection_cache.borrow_mut().insert_ty(cache_key, cache_value);
+
             Some(result)
         }
         Ok(ProjectedTy::NoProgress(projected_ty)) => {
@@ -538,7 +552,7 @@ fn opt_normalize_projection_type<'a, 'b, 'gcx, 'tcx>(
                 value: projected_ty,
                 obligations: vec![]
             };
-            infcx.projection_cache.borrow_mut().insert_ty(cache_key, &result);
+            infcx.projection_cache.borrow_mut().insert_ty(cache_key, result.clone());
             Some(result)
         }
         Err(ProjectionTyError::TooManyCandidates) => {
@@ -562,6 +576,29 @@ fn opt_normalize_projection_type<'a, 'b, 'gcx, 'tcx>(
     }
 }
 
+/// If there are unresolved type variables, then we need to include
+/// any subobligations that bind them, at least until those type
+/// variables are fully resolved.
+fn prune_cache_value_obligations<'a, 'gcx, 'tcx>(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
+                                                 cache_value: &mut NormalizedTy<'tcx>) {
+    let unresolved_type_vars = infcx.unresolved_type_vars(&cache_value.value);
+    cache_value.obligations.retain(|obligation| match obligation.predicate {
+        // We found a `T: Foo<X = U>` predicate, let's check if `U`
+        // references one of `unresolved_type_vars`. We can skip the
+        // binder because we only car about looking for
+        // `unresolved_type_vars`, and they are bound outside of this
+        // binder.
+        ty::Predicate::Projection(ref data) => {
+            let unresolved_type_vars_in_data = infcx.unresolved_type_vars(&data.ty());
+            unresolved_type_vars.iter().any(|v| unresolved_type_vars_in_data.contains(&v))
+        }
+
+        // We are only interested in `T: Foo<X = U>` predicates, whre
+        // `U` references one of `unresolved_type_vars`. =)
+        _ => false,
+    });
+}
+
 /// If we are projecting `<T as Trait>::Item`, but `T: Trait` does not
 /// hold. In various error cases, we cannot generate a valid
 /// normalized projection. Therefore, we create an inference variable
@@ -1493,10 +1530,10 @@ impl<'tcx> ProjectionCache<'tcx> {
     }
 
     /// Indicates that `key` was normalized to `value`.
-    fn insert_ty(&mut self, key: ProjectionCacheKey<'tcx>, value: &NormalizedTy<'tcx>) {
+    fn insert_ty(&mut self, key: ProjectionCacheKey<'tcx>, value: NormalizedTy<'tcx>) {
         debug!("ProjectionCacheEntry::insert_ty: adding cache entry: key={:?}, value={:?}",
                key, value);
-        let fresh_key = self.map.insert(key, ProjectionCacheEntry::NormalizedTy(value.clone()));
+        let fresh_key = self.map.insert(key, ProjectionCacheEntry::NormalizedTy(value));
         assert!(!fresh_key, "never started projecting `{:?}`", key);
     }
 
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 1851e1b8d3..1920cdb3f7 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -1017,6 +1017,10 @@ impl<'tcx> PolyProjectionPredicate<'tcx> {
         // levels.
         ty::Binder(self.0.projection_ty.trait_ref(tcx))
     }
+
+    pub fn ty(&self) -> Binder<Ty<'tcx>> {
+        Binder(self.skip_binder().ty) // preserves binding levels
+    }
 }
 
 pub trait ToPolyTraitRef<'tcx> {