typeck: leak auto trait obligations through impl Trait.

13 files changed, 613 insertions, 163 deletions

diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs
index 23ffa4db96f..5ba7b914d65 100644
--- a/src/librustc/traits/fulfill.rs
+++ b/src/librustc/traits/fulfill.rs
@@ -10,7 +10,8 @@
 
 use dep_graph::DepGraph;
 use infer::{InferCtxt, InferOk};
-use ty::{self, Ty, TypeFoldable, ToPolyTraitRef, TyCtxt};
+use ty::{self, Ty, TypeFoldable, ToPolyTraitRef, TyCtxt, ToPredicate};
+use ty::subst::{Substs, Subst};
 use rustc_data_structures::obligation_forest::{ObligationForest, Error};
 use rustc_data_structures::obligation_forest::{ForestObligation, ObligationProcessor};
 use std::marker::PhantomData;
@@ -22,10 +23,9 @@ use util::nodemap::{FnvHashSet, NodeMap};
 use super::CodeAmbiguity;
 use super::CodeProjectionError;
 use super::CodeSelectionError;
-use super::FulfillmentError;
-use super::FulfillmentErrorCode;
-use super::ObligationCause;
-use super::PredicateObligation;
+use super::{FulfillmentError, FulfillmentErrorCode, SelectionError};
+use super::{ObligationCause, BuiltinDerivedObligation};
+use super::{PredicateObligation, TraitObligation, Obligation};
 use super::project;
 use super::select::SelectionContext;
 use super::Unimplemented;
@@ -51,6 +51,7 @@ pub struct GlobalFulfilledPredicates<'tcx> {
 /// along. Once all type inference constraints have been generated, the
 /// method `select_all_or_error` can be used to report any remaining
 /// ambiguous cases as errors.
+
 pub struct FulfillmentContext<'tcx> {
     // A list of all obligations that have been registered with this
     // fulfillment context.
@@ -84,6 +85,10 @@ pub struct FulfillmentContext<'tcx> {
     // obligations (otherwise, it's easy to fail to walk to a
     // particular node-id).
     region_obligations: NodeMap<Vec<RegionObligation<'tcx>>>,
+
+    // A list of obligations that need to be deferred to
+    // a later time for them to be properly fulfilled.
+    deferred_obligations: Vec<DeferredObligation<'tcx>>,
 }
 
 #[derive(Clone)]
@@ -99,6 +104,90 @@ pub struct PendingPredicateObligation<'tcx> {
     pub stalled_on: Vec<Ty<'tcx>>,
 }
 
+/// An obligation which cannot be fulfilled in the context
+/// it was registered in, such as auto trait obligations on
+/// `impl Trait`, which require the concrete type to be
+/// available, only guaranteed after finishing type-checking.
+#[derive(Clone, Debug)]
+pub struct DeferredObligation<'tcx> {
+    pub predicate: ty::PolyTraitPredicate<'tcx>,
+    pub cause: ObligationCause<'tcx>
+}
+
+impl<'a, 'gcx, 'tcx> DeferredObligation<'tcx> {
+    /// If possible, create a `DeferredObligation` from
+    /// a trait predicate which had failed selection,
+    /// but could succeed later.
+    pub fn from_select_error(tcx: TyCtxt<'a, 'gcx, 'tcx>,
+                             obligation: &TraitObligation<'tcx>,
+                             selection_err: &SelectionError<'tcx>)
+                             -> Option<DeferredObligation<'tcx>> {
+        if let Unimplemented = *selection_err {
+            if DeferredObligation::must_defer(tcx, &obligation.predicate) {
+                return Some(DeferredObligation {
+                    predicate: obligation.predicate.clone(),
+                    cause: obligation.cause.clone()
+                });
+            }
+        }
+
+        None
+    }
+
+    /// Returns true if the given trait predicate can be
+    /// fulfilled at a later time.
+    pub fn must_defer(tcx: TyCtxt<'a, 'gcx, 'tcx>,
+                      predicate: &ty::PolyTraitPredicate<'tcx>)
+                      -> bool {
+        // Auto trait obligations on `impl Trait`.
+        if tcx.trait_has_default_impl(predicate.def_id()) {
+            let substs = predicate.skip_binder().trait_ref.substs;
+            if substs.types.as_slice().len() == 1 && substs.regions.is_empty() {
+                if let ty::TyAnon(..) = predicate.skip_binder().self_ty().sty {
+                    return true;
+                }
+            }
+        }
+
+        false
+    }
+
+    /// If possible, return the nested obligations required
+    /// to fulfill this obligation.
+    pub fn try_select(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>)
+                      -> Option<Vec<PredicateObligation<'tcx>>> {
+        if let ty::TyAnon(def_id, substs) = self.predicate.skip_binder().self_ty().sty {
+            // We can resolve the `impl Trait` to its concrete type.
+            if let Some(ty_scheme) = tcx.opt_lookup_item_type(def_id) {
+                let concrete_ty = ty_scheme.ty.subst(tcx, substs);
+                let concrete_substs = Substs::new_trait(vec![], vec![], concrete_ty);
+                let predicate = ty::TraitRef {
+                    def_id: self.predicate.def_id(),
+                    substs: tcx.mk_substs(concrete_substs)
+                }.to_predicate();
+
+                let original_obligation = Obligation::new(self.cause.clone(),
+                                                          self.predicate.clone());
+                let cause = original_obligation.derived_cause(BuiltinDerivedObligation);
+                return Some(vec![Obligation::new(cause, predicate)]);
+            }
+        }
+
+        None
+    }
+
+    /// Return the `PredicateObligation` this was created from.
+    pub fn to_obligation(&self) -> PredicateObligation<'tcx> {
+        let predicate = ty::Predicate::Trait(self.predicate.clone());
+        Obligation::new(self.cause.clone(), predicate)
+    }
+
+    /// Return an error as if this obligation had failed.
+    pub fn to_error(&self) -> FulfillmentError<'tcx> {
+        FulfillmentError::new(self.to_obligation(), CodeSelectionError(Unimplemented))
+    }
+}
+
 impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
     /// Creates a new fulfillment context.
     pub fn new() -> FulfillmentContext<'tcx> {
@@ -106,6 +195,7 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
             predicates: ObligationForest::new(),
             rfc1592_obligations: Vec::new(),
             region_obligations: NodeMap(),
+            deferred_obligations: vec![],
         }
     }
 
@@ -224,10 +314,16 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
     {
         self.select_where_possible(infcx)?;
 
+        // Fail all of the deferred obligations that haven't
+        // been otherwise removed from the context.
+        let deferred_errors = self.deferred_obligations.iter()
+                                  .map(|d| d.to_error());
+
         let errors: Vec<_> =
             self.predicates.to_errors(CodeAmbiguity)
                            .into_iter()
                            .map(|e| to_fulfillment_error(e))
+                           .chain(deferred_errors)
                            .collect();
         if errors.is_empty() {
             Ok(())
@@ -248,6 +344,10 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
         self.predicates.pending_obligations()
     }
 
+    pub fn take_deferred_obligations(&mut self) -> Vec<DeferredObligation<'tcx>> {
+        mem::replace(&mut self.deferred_obligations, vec![])
+    }
+
     /// Attempts to select obligations using `selcx`. If `only_new_obligations` is true, then it
     /// only attempts to select obligations that haven't been seen before.
     fn select(&mut self, selcx: &mut SelectionContext<'a, 'gcx, 'tcx>)
@@ -261,9 +361,10 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
 
             // Process pending obligations.
             let outcome = self.predicates.process_obligations(&mut FulfillProcessor {
-                    selcx: selcx,
-                    region_obligations: &mut self.region_obligations,
-                    rfc1592_obligations: &mut self.rfc1592_obligations
+                selcx: selcx,
+                region_obligations: &mut self.region_obligations,
+                rfc1592_obligations: &mut self.rfc1592_obligations,
+                deferred_obligations: &mut self.deferred_obligations
             });
             debug!("select: outcome={:?}", outcome);
 
@@ -298,7 +399,8 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
 struct FulfillProcessor<'a, 'b: 'a, 'gcx: 'tcx, 'tcx: 'b> {
     selcx: &'a mut SelectionContext<'b, 'gcx, 'tcx>,
     region_obligations: &'a mut NodeMap<Vec<RegionObligation<'tcx>>>,
-    rfc1592_obligations: &'a mut Vec<PredicateObligation<'tcx>>
+    rfc1592_obligations: &'a mut Vec<PredicateObligation<'tcx>>,
+    deferred_obligations: &'a mut Vec<DeferredObligation<'tcx>>
 }
 
 impl<'a, 'b, 'gcx, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'gcx, 'tcx> {
@@ -312,7 +414,8 @@ impl<'a, 'b, 'gcx, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'gcx,
         process_predicate(self.selcx,
                           obligation,
                           self.region_obligations,
-                          self.rfc1592_obligations)
+                          self.rfc1592_obligations,
+                          self.deferred_obligations)
             .map(|os| os.map(|os| os.into_iter().map(|o| PendingPredicateObligation {
                 obligation: o,
                 stalled_on: vec![]
@@ -354,7 +457,8 @@ fn process_predicate<'a, 'gcx, 'tcx>(
     selcx: &mut SelectionContext<'a, 'gcx, 'tcx>,
     pending_obligation: &mut PendingPredicateObligation<'tcx>,
     region_obligations: &mut NodeMap<Vec<RegionObligation<'tcx>>>,
-    rfc1592_obligations: &mut Vec<PredicateObligation<'tcx>>)
+    rfc1592_obligations: &mut Vec<PredicateObligation<'tcx>>,
+    deferred_obligations: &mut Vec<DeferredObligation<'tcx>>)
     -> Result<Option<Vec<PredicateObligation<'tcx>>>,
               FulfillmentErrorCode<'tcx>>
 {
@@ -422,7 +526,22 @@ fn process_predicate<'a, 'gcx, 'tcx>(
                 Err(selection_err) => {
                     info!("selecting trait `{:?}` at depth {} yielded Err",
                           data, obligation.recursion_depth);
-                    Err(CodeSelectionError(selection_err))
+
+                    let defer = DeferredObligation::from_select_error(selcx.tcx(),
+                                                                      &trait_obligation,
+                                                                      &selection_err);
+                    if let Some(deferred_obligation) = defer {
+                        if let Some(nested) = deferred_obligation.try_select(selcx.tcx()) {
+                            Ok(Some(nested))
+                        } else {
+                            // Pretend that the obligation succeeded,
+                            // but record it for later.
+                            deferred_obligations.push(deferred_obligation);
+                            Ok(Some(vec![]))
+                        }
+                    } else {
+                        Err(CodeSelectionError(selection_err))
+                    }
                 }
             }
         }
@@ -629,6 +748,12 @@ impl<'a, 'gcx, 'tcx> GlobalFulfilledPredicates<'gcx> {
             // already has the required read edges, so we don't need
             // to add any more edges here.
             if data.is_global() {
+                // Don't cache predicates which were fulfilled
+                // by deferring them for later fulfillment.
+                if DeferredObligation::must_defer(tcx, data) {
+                    return;
+                }
+
                 if let Some(data) = tcx.lift_to_global(data) {
                     if self.set.insert(data.clone()) {
                         debug!("add_if_global: global predicate `{:?}` added", data);
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index 693b3c2d1c0..dc0807ba38f 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -30,6 +30,7 @@ pub use self::coherence::orphan_check;
 pub use self::coherence::overlapping_impls;
 pub use self::coherence::OrphanCheckErr;
 pub use self::fulfill::{FulfillmentContext, GlobalFulfilledPredicates, RegionObligation};
+pub use self::fulfill::DeferredObligation;
 pub use self::project::MismatchedProjectionTypes;
 pub use self::project::{normalize, normalize_projection_type, Normalized};
 pub use self::project::{ProjectionCache, ProjectionCacheSnapshot, Reveal};
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index f353c54089d..2df492e507b 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -2128,7 +2128,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                           obligation)
             };
 
-            let cause = self.derived_cause(obligation, BuiltinDerivedObligation);
+            let cause = obligation.derived_cause(BuiltinDerivedObligation);
             self.collect_predicates_for_types(cause,
                                               obligation.recursion_depth+1,
                                               trait_def,
@@ -2208,7 +2208,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
     {
         debug!("vtable_default_impl: nested={:?}", nested);
 
-        let cause = self.derived_cause(obligation, BuiltinDerivedObligation);
+        let cause = obligation.derived_cause(BuiltinDerivedObligation);
         let mut obligations = self.collect_predicates_for_types(
             cause,
             obligation.recursion_depth+1,
@@ -2219,7 +2219,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             let poly_trait_ref = obligation.predicate.to_poly_trait_ref();
             let (trait_ref, skol_map) =
                 this.infcx().skolemize_late_bound_regions(&poly_trait_ref, snapshot);
-            let cause = this.derived_cause(obligation, ImplDerivedObligation);
+            let cause = obligation.derived_cause(ImplDerivedObligation);
             this.impl_or_trait_obligations(cause,
                                            obligation.recursion_depth + 1,
                                            trait_def_id,
@@ -2254,7 +2254,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 this.rematch_impl(impl_def_id, obligation,
                                   snapshot);
             debug!("confirm_impl_candidate substs={:?}", substs);
-            let cause = this.derived_cause(obligation, ImplDerivedObligation);
+            let cause = obligation.derived_cause(ImplDerivedObligation);
             this.vtable_impl(impl_def_id, substs, cause,
                              obligation.recursion_depth + 1,
                              skol_map, snapshot)
@@ -2907,12 +2907,13 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             }).collect();
         self.infcx().plug_leaks(skol_map, snapshot, &predicates)
     }
+}
 
+impl<'tcx> TraitObligation<'tcx> {
     #[allow(unused_comparisons)]
-    fn derived_cause(&self,
-                     obligation: &TraitObligation<'tcx>,
-                     variant: fn(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>)
-                     -> ObligationCause<'tcx>
+    pub fn derived_cause(&self,
+                        variant: fn(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>)
+                        -> ObligationCause<'tcx>
     {
         /*!
          * Creates a cause for obligations that are derived from
@@ -2924,6 +2925,8 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
          * reporting.
          */
 
+        let obligation = self;
+
         // NOTE(flaper87): As of now, it keeps track of the whole error
         // chain. Ideally, we should have a way to configure this either
         // by using -Z verbose or just a CLI argument.
diff --git a/src/librustc/traits/structural_impls.rs b/src/librustc/traits/structural_impls.rs
index e210d2da94c..022566642f6 100644
--- a/src/librustc/traits/structural_impls.rs
+++ b/src/librustc/traits/structural_impls.rs
@@ -14,6 +14,7 @@ use ty::{Lift, TyCtxt};
 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
 
 use std::fmt;
+use std::rc::Rc;
 
 // structural impls for the structs in traits
 
@@ -162,6 +163,86 @@ impl<'a, 'tcx> Lift<'tcx> for traits::SelectionError<'a> {
     }
 }
 
+impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCauseCode<'a> {
+    type Lifted = traits::ObligationCauseCode<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        match *self {
+            super::MiscObligation => Some(super::MiscObligation),
+            super::SliceOrArrayElem => Some(super::SliceOrArrayElem),
+            super::TupleElem => Some(super::TupleElem),
+            super::ProjectionWf(proj) => tcx.lift(&proj).map(super::ProjectionWf),
+            super::ItemObligation(def_id) => Some(super::ItemObligation(def_id)),
+            super::ReferenceOutlivesReferent(ty) => {
+                tcx.lift(&ty).map(super::ReferenceOutlivesReferent)
+            }
+            super::ObjectCastObligation(ty) => {
+                tcx.lift(&ty).map(super::ObjectCastObligation)
+            }
+            super::AssignmentLhsSized => Some(super::AssignmentLhsSized),
+            super::StructInitializerSized => Some(super::StructInitializerSized),
+            super::VariableType(id) => Some(super::VariableType(id)),
+            super::ReturnType => Some(super::ReturnType),
+            super::RepeatVec => Some(super::RepeatVec),
+            super::ClosureCapture(node_id, span, bound) => {
+                Some(super::ClosureCapture(node_id, span, bound))
+            }
+            super::FieldSized => Some(super::FieldSized),
+            super::ConstSized => Some(super::ConstSized),
+            super::SharedStatic => Some(super::SharedStatic),
+            super::BuiltinDerivedObligation(ref cause) => {
+                tcx.lift(cause).map(super::BuiltinDerivedObligation)
+            }
+            super::ImplDerivedObligation(ref cause) => {
+                tcx.lift(cause).map(super::ImplDerivedObligation)
+            }
+            super::CompareImplMethodObligation => {
+                Some(super::CompareImplMethodObligation)
+            }
+        }
+    }
+}
+
+impl<'a, 'tcx> Lift<'tcx> for traits::DerivedObligationCause<'a> {
+    type Lifted = traits::DerivedObligationCause<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        tcx.lift(&self.parent_trait_ref).and_then(|trait_ref| {
+            tcx.lift(&*self.parent_code).map(|code| {
+                traits::DerivedObligationCause {
+                    parent_trait_ref: trait_ref,
+                    parent_code: Rc::new(code)
+                }
+            })
+        })
+    }
+}
+
+impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCause<'a> {
+    type Lifted = traits::ObligationCause<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        tcx.lift(&self.code).map(|code| {
+            traits::ObligationCause {
+                span: self.span,
+                body_id: self.body_id,
+                code: code,
+            }
+        })
+    }
+}
+
+impl<'a, 'tcx> Lift<'tcx> for traits::DeferredObligation<'a> {
+    type Lifted = traits::DeferredObligation<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        tcx.lift(&self.predicate).and_then(|predicate| {
+            tcx.lift(&self.cause).map(|cause| {
+                traits::DeferredObligation {
+                    predicate: predicate,
+                    cause: cause
+                }
+            })
+        })
+    }
+}
+
 // For trans only.
 impl<'a, 'tcx> Lift<'tcx> for traits::Vtable<'a, ()> {
     type Lifted = traits::Vtable<'tcx, ()>;
@@ -361,3 +442,103 @@ impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Normalized<'tcx, T> {
         self.value.visit_with(visitor) || self.obligations.visit_with(visitor)
     }
 }
+
+impl<'tcx> TypeFoldable<'tcx> for traits::ObligationCauseCode<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        match *self {
+            super::MiscObligation |
+            super::SliceOrArrayElem |
+            super::TupleElem |
+            super::ItemObligation(_) |
+            super::AssignmentLhsSized |
+            super::StructInitializerSized |
+            super::VariableType(_) |
+            super::ReturnType |
+            super::RepeatVec |
+            super::ClosureCapture(..) |
+            super::FieldSized |
+            super::ConstSized |
+            super::SharedStatic |
+            super::CompareImplMethodObligation => self.clone(),
+
+            super::ProjectionWf(proj) => super::ProjectionWf(proj.fold_with(folder)),
+            super::ReferenceOutlivesReferent(ty) => {
+                super::ReferenceOutlivesReferent(ty.fold_with(folder))
+            }
+            super::ObjectCastObligation(ty) => {
+                super::ObjectCastObligation(ty.fold_with(folder))
+            }
+            super::BuiltinDerivedObligation(ref cause) => {
+                super::BuiltinDerivedObligation(cause.fold_with(folder))
+            }
+            super::ImplDerivedObligation(ref cause) => {
+                super::ImplDerivedObligation(cause.fold_with(folder))
+            }
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        match *self {
+            super::MiscObligation |
+            super::SliceOrArrayElem |
+            super::TupleElem |
+            super::ItemObligation(_) |
+            super::AssignmentLhsSized |
+            super::StructInitializerSized |
+            super::VariableType(_) |
+            super::ReturnType |
+            super::RepeatVec |
+            super::ClosureCapture(..) |
+            super::FieldSized |
+            super::ConstSized |
+            super::SharedStatic |
+            super::CompareImplMethodObligation => false,
+
+            super::ProjectionWf(proj) => proj.visit_with(visitor),
+            super::ReferenceOutlivesReferent(ty) => ty.visit_with(visitor),
+            super::ObjectCastObligation(ty) => ty.visit_with(visitor),
+            super::BuiltinDerivedObligation(ref cause) => cause.visit_with(visitor),
+            super::ImplDerivedObligation(ref cause) => cause.visit_with(visitor)
+        }
+    }
+}
+
+impl<'tcx> TypeFoldable<'tcx> for traits::DerivedObligationCause<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        traits::DerivedObligationCause {
+            parent_trait_ref: self.parent_trait_ref.fold_with(folder),
+            parent_code: self.parent_code.fold_with(folder)
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        self.parent_trait_ref.visit_with(visitor) || self.parent_code.visit_with(visitor)
+    }
+}
+
+impl<'tcx> TypeFoldable<'tcx> for traits::ObligationCause<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        traits::ObligationCause {
+            span: self.span,
+            body_id: self.body_id,
+            code: self.code.fold_with(folder),
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        self.code.visit_with(visitor)
+    }
+}
+
+impl<'tcx> TypeFoldable<'tcx> for traits::DeferredObligation<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        traits::DeferredObligation {
+            predicate: self.predicate.fold_with(folder),
+            cause: self.cause.fold_with(folder)
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        self.predicate.visit_with(visitor) || self.cause.visit_with(visitor)
+    }
+}
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index fe5c602575b..8e89b3c6087 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -1404,9 +1404,13 @@ impl<'a, 'tcx> ParameterEnvironment<'tcx> {
                     }
                 }
             }
-            Some(ast_map::NodeExpr(..)) => {
+            Some(ast_map::NodeExpr(expr)) => {
                 // This is a convenience to allow closures to work.
-                ParameterEnvironment::for_item(tcx, tcx.map.get_parent(id))
+                if let hir::ExprClosure(..) = expr.node {
+                    ParameterEnvironment::for_item(tcx, tcx.map.get_parent(id))
+                } else {
+                    tcx.empty_parameter_environment()
+                }
             }
             Some(ast_map::NodeForeignItem(item)) => {
                 let def_id = tcx.map.local_def_id(id);
diff --git a/src/librustc/ty/structural_impls.rs b/src/librustc/ty/structural_impls.rs
index e542e8f237f..8c10806fda7 100644
--- a/src/librustc/ty/structural_impls.rs
+++ b/src/librustc/ty/structural_impls.rs
@@ -115,16 +115,26 @@ impl<'tcx, A: Copy+Lift<'tcx>, B: Copy+Lift<'tcx>> Lift<'tcx> for ty::OutlivesPr
     }
 }
 
+impl<'a, 'tcx> Lift<'tcx> for ty::ProjectionTy<'a> {
+    type Lifted = ty::ProjectionTy<'tcx>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
+                             -> Option<ty::ProjectionTy<'tcx>> {
+        tcx.lift(&self.trait_ref).map(|trait_ref| {
+            ty::ProjectionTy {
+                trait_ref: trait_ref,
+                item_name: self.item_name
+            }
+        })
+    }
+}
+
 impl<'a, 'tcx> Lift<'tcx> for ty::ProjectionPredicate<'a> {
     type Lifted = ty::ProjectionPredicate<'tcx>;
     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
                              -> Option<ty::ProjectionPredicate<'tcx>> {
-        tcx.lift(&(self.projection_ty.trait_ref, self.ty)).map(|(trait_ref, ty)| {
+        tcx.lift(&(self.projection_ty, self.ty)).map(|(projection_ty, ty)| {
             ty::ProjectionPredicate {
-                projection_ty: ty::ProjectionTy {
-                    trait_ref: trait_ref,
-                    item_name: self.projection_ty.item_name
-                },
+                projection_ty: projection_ty,
                 ty: ty
             }
         })
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 1734dec7e72..c2c93161ce7 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -178,6 +178,10 @@ pub struct Inherited<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     // variables to get the concrete type, which can be used to
     // deanonymize TyAnon, after typeck is done with all functions.
     anon_types: RefCell<DefIdMap<Ty<'tcx>>>,
+
+    // Obligations which will have to be checked at the end of
+    // type-checking, after all functions have been inferred.
+    deferred_obligations: RefCell<Vec<traits::DeferredObligation<'tcx>>>,
 }
 
 impl<'a, 'gcx, 'tcx> Deref for Inherited<'a, 'gcx, 'tcx> {
@@ -390,12 +394,13 @@ pub struct InheritedBuilder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 }
 
 impl<'a, 'gcx, 'tcx> CrateCtxt<'a, 'gcx> {
-    pub fn inherited(&'a self, param_env: Option<ty::ParameterEnvironment<'gcx>>)
+    pub fn inherited(&'a self, id: ast::NodeId)
                      -> InheritedBuilder<'a, 'gcx, 'tcx> {
+        let param_env = ParameterEnvironment::for_item(self.tcx, id);
         InheritedBuilder {
             ccx: self,
             infcx: self.tcx.infer_ctxt(Some(ty::Tables::empty()),
-                                       param_env,
+                                       Some(param_env),
                                        Reveal::NotSpecializable)
         }
     }
@@ -415,6 +420,7 @@ impl<'a, 'gcx, 'tcx> InheritedBuilder<'a, 'gcx, 'tcx> {
                 deferred_call_resolutions: RefCell::new(DefIdMap()),
                 deferred_cast_checks: RefCell::new(Vec::new()),
                 anon_types: RefCell::new(DefIdMap()),
+                deferred_obligations: RefCell::new(Vec::new()),
             })
         })
     }
@@ -449,7 +455,7 @@ impl<'a, 'tcx> Visitor<'tcx> for CheckItemTypesVisitor<'a, 'tcx> {
     fn visit_ty(&mut self, t: &'tcx hir::Ty) {
         match t.node {
             hir::TyFixedLengthVec(_, ref expr) => {
-                check_const_in_type(self.ccx, &expr, self.ccx.tcx.types.usize);
+                check_const_with_type(self.ccx, &expr, self.ccx.tcx.types.usize, expr.id);
             }
             _ => {}
         }
@@ -482,6 +488,31 @@ pub fn check_item_bodies(ccx: &CrateCtxt) -> CompileResult {
     ccx.tcx.sess.track_errors(|| {
         let mut visit = CheckItemBodiesVisitor { ccx: ccx };
         ccx.tcx.visit_all_items_in_krate(DepNode::TypeckItemBody, &mut visit);
+
+        // Process deferred obligations, now that all functions
+        // bodies have been fully inferred.
+        for (&item_id, obligations) in ccx.deferred_obligations.borrow().iter() {
+            // Use the same DepNode as for the body of the original function/item.
+            let def_id = ccx.tcx.map.local_def_id(item_id);
+            let _task = ccx.tcx.dep_graph.in_task(DepNode::TypeckItemBody(def_id));
+
+            let param_env = ParameterEnvironment::for_item(ccx.tcx, item_id);
+            ccx.tcx.infer_ctxt(None, Some(param_env),
+                               Reveal::NotSpecializable).enter(|infcx| {
+                let mut fulfillment_cx = traits::FulfillmentContext::new();
+                for obligation in obligations.iter().map(|o| o.to_obligation()) {
+                    fulfillment_cx.register_predicate_obligation(&infcx, obligation);
+                }
+
+                if let Err(errors) = fulfillment_cx.select_all_or_error(&infcx) {
+                    infcx.report_fulfillment_errors(&errors);
+                }
+
+                if let Err(errors) = fulfillment_cx.select_rfc1592_obligations(&infcx) {
+                    infcx.report_fulfillment_errors_as_warnings(&errors, item_id);
+                }
+            });
+        }
     })
 }
 
@@ -508,17 +539,14 @@ pub fn check_drop_impls(ccx: &CrateCtxt) -> CompileResult {
 fn check_bare_fn<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                            decl: &'tcx hir::FnDecl,
                            body: &'tcx hir::Block,
-                           fn_id: ast::NodeId,
-                           fn_span: Span,
-                           raw_fty: Ty<'tcx>,
-                           param_env: ty::ParameterEnvironment<'tcx>)
-{
+                           fn_id: ast::NodeId) {
+    let raw_fty = ccx.tcx.lookup_item_type(ccx.tcx.map.local_def_id(fn_id)).ty;
     let fn_ty = match raw_fty.sty {
         ty::TyFnDef(_, _, f) => f,
         _ => span_bug!(body.span, "check_bare_fn: function type expected")
     };
 
-    ccx.inherited(Some(param_env)).enter(|inh| {
+    ccx.inherited(fn_id).enter(|inh| {
         // Compute the fty from point of view of inside fn.
         let fn_scope = inh.tcx.region_maps.call_site_extent(fn_id, body.id);
         let fn_sig =
@@ -536,8 +564,8 @@ fn check_bare_fn<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
         fcx.check_casts();
         fcx.select_all_obligations_or_error(); // Casts can introduce new obligations.
 
-        fcx.regionck_fn(fn_id, fn_span, decl, body);
-        fcx.resolve_type_vars_in_fn(decl, body);
+        fcx.regionck_fn(fn_id, decl, body);
+        fcx.resolve_type_vars_in_fn(decl, body, fn_id);
     });
 }
 
@@ -711,7 +739,7 @@ pub fn check_item_type<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>, it: &'tcx hir::Item) {
     match it.node {
       // Consts can play a role in type-checking, so they are included here.
       hir::ItemStatic(_, _, ref e) |
-      hir::ItemConst(_, ref e) => check_const(ccx, it.span, &e, it.id),
+      hir::ItemConst(_, ref e) => check_const(ccx, &e, it.id),
       hir::ItemEnum(ref enum_definition, _) => {
         check_enum_variants(ccx,
                             it.span,
@@ -790,23 +818,18 @@ pub fn check_item_body<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>, it: &'tcx hir::Item) {
     let _indenter = indenter();
     match it.node {
       hir::ItemFn(ref decl, _, _, _, _, ref body) => {
-        let fn_pty = ccx.tcx.lookup_item_type(ccx.tcx.map.local_def_id(it.id));
-        let param_env = ParameterEnvironment::for_item(ccx.tcx, it.id);
-        check_bare_fn(ccx, &decl, &body, it.id, it.span, fn_pty.ty, param_env);
+        check_bare_fn(ccx, &decl, &body, it.id);
       }
       hir::ItemImpl(_, _, _, _, _, ref impl_items) => {
         debug!("ItemImpl {} with id {}", it.name, it.id);
 
-        let impl_pty = ccx.tcx.lookup_item_type(ccx.tcx.map.local_def_id(it.id));
-
         for impl_item in impl_items {
             match impl_item.node {
                 hir::ImplItemKind::Const(_, ref expr) => {
-                    check_const(ccx, impl_item.span, &expr, impl_item.id)
+                    check_const(ccx, &expr, impl_item.id)
                 }
                 hir::ImplItemKind::Method(ref sig, ref body) => {
-                    check_method_body(ccx, &impl_pty.generics, sig, body,
-                                      impl_item.id, impl_item.span);
+                    check_bare_fn(ccx, &sig.decl, body, impl_item.id);
                 }
                 hir::ImplItemKind::Type(_) => {
                     // Nothing to do here.
@@ -815,17 +838,15 @@ pub fn check_item_body<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>, it: &'tcx hir::Item) {
         }
       }
       hir::ItemTrait(_, _, _, ref trait_items) => {
-        let trait_def = ccx.tcx.lookup_trait_def(ccx.tcx.map.local_def_id(it.id));
         for trait_item in trait_items {
             match trait_item.node {
                 hir::ConstTraitItem(_, Some(ref expr)) => {
-                    check_const(ccx, trait_item.span, &expr, trait_item.id)
+                    check_const(ccx, &expr, trait_item.id)
                 }
                 hir::MethodTraitItem(ref sig, Some(ref body)) => {
                     check_trait_fn_not_const(ccx, trait_item.span, sig.constness);
 
-                    check_method_body(ccx, &trait_def.generics, sig, body,
-                                      trait_item.id, trait_item.span);
+                    check_bare_fn(ccx, &sig.decl, body, trait_item.id);
                 }
                 hir::MethodTraitItem(ref sig, None) => {
                     check_trait_fn_not_const(ccx, trait_item.span, sig.constness);
@@ -902,29 +923,6 @@ fn check_on_unimplemented<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
     }
 }
 
-/// Type checks a method body.
-///
-/// # Parameters
-///
-/// * `item_generics`: generics defined on the impl/trait that contains
-///   the method
-/// * `self_bound`: bound for the `Self` type parameter, if any
-/// * `method`: the method definition
-fn check_method_body<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
-                               item_generics: &ty::Generics<'tcx>,
-                               sig: &'tcx hir::MethodSig,
-                               body: &'tcx hir::Block,
-                               id: ast::NodeId, span: Span) {
-    debug!("check_method_body(item_generics={:?}, id={})",
-            item_generics, id);
-    let param_env = ParameterEnvironment::for_item(ccx.tcx, id);
-
-    let fty = ccx.tcx.node_id_to_type(id);
-    debug!("check_method_body: fty={:?}", fty);
-
-    check_bare_fn(ccx, &sig.decl, body, id, span, fty, param_env);
-}
-
 fn report_forbidden_specialization<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                              impl_item: &hir::ImplItem,
                                              parent_impl: DefId)
@@ -1163,30 +1161,39 @@ fn check_impl_items_against_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
     }
 }
 
-/// Checks a constant appearing in a type. At the moment this is just the
-/// length expression in a fixed-length vector, but someday it might be
-/// extended to type-level numeric literals.
-fn check_const_in_type<'a,'tcx>(ccx: &'a CrateCtxt<'a,'tcx>,
-                                expr: &'tcx hir::Expr,
-                                expected_type: Ty<'tcx>) {
-    ccx.inherited(None).enter(|inh| {
+/// Checks a constant with a given type.
+fn check_const_with_type<'a, 'tcx>(ccx: &'a CrateCtxt<'a, 'tcx>,
+                                   expr: &'tcx hir::Expr,
+                                   expected_type: Ty<'tcx>,
+                                   id: ast::NodeId) {
+    ccx.inherited(id).enter(|inh| {
         let fcx = FnCtxt::new(&inh, ty::FnConverging(expected_type), expr.id);
-        fcx.check_const_with_ty(expr.span, expr, expected_type);
+        fcx.require_type_is_sized(expected_type, expr.span, traits::ConstSized);
+
+        // Gather locals in statics (because of block expressions).
+        // This is technically unnecessary because locals in static items are forbidden,
+        // but prevents type checking from blowing up before const checking can properly
+        // emit an error.
+        GatherLocalsVisitor { fcx: &fcx }.visit_expr(expr);
+
+        fcx.check_expr_coercable_to_type(expr, expected_type);
+
+        fcx.select_all_obligations_and_apply_defaults();
+        fcx.closure_analyze_const(expr);
+        fcx.select_obligations_where_possible();
+        fcx.check_casts();
+        fcx.select_all_obligations_or_error();
+
+        fcx.regionck_expr(expr);
+        fcx.resolve_type_vars_in_expr(expr, id);
     });
 }
 
-fn check_const<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
-                        sp: Span,
-                        e: &'tcx hir::Expr,
-                        id: ast::NodeId) {
-    let param_env = ParameterEnvironment::for_item(ccx.tcx, id);
-    ccx.inherited(Some(param_env)).enter(|inh| {
-        let rty = ccx.tcx.node_id_to_type(id);
-        let fcx = FnCtxt::new(&inh, ty::FnConverging(rty), e.id);
-        let declty = fcx.tcx.lookup_item_type(ccx.tcx.map.local_def_id(id)).ty;
-        fcx.require_type_is_sized(declty, e.span, traits::ConstSized);
-        fcx.check_const_with_ty(sp, e, declty);
-    });
+fn check_const<'a, 'tcx>(ccx: &CrateCtxt<'a,'tcx>,
+                         expr: &'tcx hir::Expr,
+                         id: ast::NodeId) {
+    let decl_ty = ccx.tcx.lookup_item_type(ccx.tcx.map.local_def_id(id)).ty;
+    check_const_with_type(ccx, expr, decl_ty, id);
 }
 
 /// Checks whether a type can be represented in memory. In particular, it
@@ -1255,45 +1262,40 @@ pub fn check_enum_variants<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
             "unsupported representation for zero-variant enum");
     }
 
-    ccx.inherited(None).enter(|inh| {
-        let rty = ccx.tcx.node_id_to_type(id);
-        let fcx = FnCtxt::new(&inh, ty::FnConverging(rty), id);
-
-        let repr_type_ty = ccx.tcx.enum_repr_type(Some(&hint)).to_ty(ccx.tcx);
-        for v in vs {
-            if let Some(ref e) = v.node.disr_expr {
-                fcx.check_const_with_ty(e.span, e, repr_type_ty);
-            }
+    let repr_type_ty = ccx.tcx.enum_repr_type(Some(&hint)).to_ty(ccx.tcx);
+    for v in vs {
+        if let Some(ref e) = v.node.disr_expr {
+            check_const_with_type(ccx, e, repr_type_ty, e.id);
         }
+    }
 
-        let def_id = ccx.tcx.map.local_def_id(id);
-
-        let variants = &ccx.tcx.lookup_adt_def(def_id).variants;
-        let mut disr_vals: Vec<ty::Disr> = Vec::new();
-        for (v, variant) in vs.iter().zip(variants.iter()) {
-            let current_disr_val = variant.disr_val;
+    let def_id = ccx.tcx.map.local_def_id(id);
 
-            // Check for duplicate discriminant values
-            if let Some(i) = disr_vals.iter().position(|&x| x == current_disr_val) {
-                let variant_i_node_id = ccx.tcx.map.as_local_node_id(variants[i].did).unwrap();
-                let variant_i = ccx.tcx.map.expect_variant(variant_i_node_id);
-                let i_span = match variant_i.node.disr_expr {
-                    Some(ref expr) => expr.span,
-                    None => ccx.tcx.map.span(variant_i_node_id)
-                };
-                let span = match v.node.disr_expr {
-                    Some(ref expr) => expr.span,
-                    None => v.span
-                };
-                struct_span_err!(ccx.tcx.sess, span, E0081,
-                                 "discriminant value `{}` already exists", disr_vals[i])
-                    .span_label(i_span, &format!("first use of `{}`", disr_vals[i]))
-                    .span_label(span , &format!("enum already has `{}`", disr_vals[i]))
-                    .emit();
-            }
-            disr_vals.push(current_disr_val);
+    let variants = &ccx.tcx.lookup_adt_def(def_id).variants;
+    let mut disr_vals: Vec<ty::Disr> = Vec::new();
+    for (v, variant) in vs.iter().zip(variants.iter()) {
+        let current_disr_val = variant.disr_val;
+
+        // Check for duplicate discriminant values
+        if let Some(i) = disr_vals.iter().position(|&x| x == current_disr_val) {
+            let variant_i_node_id = ccx.tcx.map.as_local_node_id(variants[i].did).unwrap();
+            let variant_i = ccx.tcx.map.expect_variant(variant_i_node_id);
+            let i_span = match variant_i.node.disr_expr {
+                Some(ref expr) => expr.span,
+                None => ccx.tcx.map.span(variant_i_node_id)
+            };
+            let span = match v.node.disr_expr {
+                Some(ref expr) => expr.span,
+                None => v.span
+            };
+            struct_span_err!(ccx.tcx.sess, span, E0081,
+                             "discriminant value `{}` already exists", disr_vals[i])
+                .span_label(i_span, &format!("first use of `{}`", disr_vals[i]))
+                .span_label(span , &format!("enum already has `{}`", disr_vals[i]))
+                .emit();
         }
-    });
+        disr_vals.push(current_disr_val);
+    }
 
     check_representable(ccx.tcx, sp, id, "enum");
 }
@@ -2228,6 +2230,12 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         self.select_all_obligations_and_apply_defaults();
 
         let mut fulfillment_cx = self.fulfillment_cx.borrow_mut();
+
+        // Steal the deferred obligations before the fulfillment
+        // context can turn all of them into errors.
+        let obligations = fulfillment_cx.take_deferred_obligations();
+        self.deferred_obligations.borrow_mut().extend(obligations);
+
         match fulfillment_cx.select_all_or_error(self) {
             Ok(()) => { }
             Err(errors) => { self.report_fulfillment_errors(&errors); }
@@ -4036,29 +4044,6 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         *self.ps.borrow_mut() = prev;
     }
 
-
-    fn check_const_with_ty(&self,
-                           _: Span,
-                           e: &'gcx hir::Expr,
-                           declty: Ty<'tcx>) {
-        // Gather locals in statics (because of block expressions).
-        // This is technically unnecessary because locals in static items are forbidden,
-        // but prevents type checking from blowing up before const checking can properly
-        // emit an error.
-        GatherLocalsVisitor { fcx: self }.visit_expr(e);
-
-        self.check_expr_coercable_to_type(e, declty);
-
-        self.select_all_obligations_and_apply_defaults();
-        self.closure_analyze_const(e);
-        self.select_obligations_where_possible();
-        self.check_casts();
-        self.select_all_obligations_or_error();
-
-        self.regionck_expr(e);
-        self.resolve_type_vars_in_expr(e);
-    }
-
     // Returns the type parameter count and the type for the given definition.
     fn type_scheme_and_predicates_for_def(&self,
                                           sp: Span,
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index 5a7038a0569..f3a6442f35d 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -141,7 +141,6 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
 
     pub fn regionck_fn(&self,
                        fn_id: ast::NodeId,
-                       fn_span: Span,
                        decl: &hir::FnDecl,
                        blk: &hir::Block) {
         debug!("regionck_fn(id={})", fn_id);
@@ -149,7 +148,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
 
         if self.err_count_since_creation() == 0 {
             // regionck assumes typeck succeeded
-            rcx.visit_fn_body(fn_id, decl, blk, fn_span);
+            rcx.visit_fn_body(fn_id, decl, blk, self.tcx.map.span(fn_id));
         }
 
         rcx.free_region_map.relate_free_regions_from_predicates(
diff --git a/src/librustc_typeck/check/wfcheck.rs b/src/librustc_typeck/check/wfcheck.rs
index 34a91b22981..e2080906ca2 100644
--- a/src/librustc_typeck/check/wfcheck.rs
+++ b/src/librustc_typeck/check/wfcheck.rs
@@ -209,9 +209,8 @@ impl<'ccx, 'gcx> CheckTypeWellFormedVisitor<'ccx, 'gcx> {
 
     fn for_id<'tcx>(&self, id: ast::NodeId, span: Span)
                     -> CheckWfFcxBuilder<'ccx, 'gcx, 'tcx> {
-        let param_env = ty::ParameterEnvironment::for_item(self.ccx.tcx, id);
         CheckWfFcxBuilder {
-            inherited: self.ccx.inherited(Some(param_env)),
+            inherited: self.ccx.inherited(id),
             code: self.code.clone(),
             id: id,
             span: span
diff --git a/src/librustc_typeck/check/writeback.rs b/src/librustc_typeck/check/writeback.rs
index 7458e3b9bc7..9026920e7f4 100644
--- a/src/librustc_typeck/check/writeback.rs
+++ b/src/librustc_typeck/check/writeback.rs
@@ -37,7 +37,7 @@ use rustc::hir::{self, PatKind};
 // Entry point functions
 
 impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
-    pub fn resolve_type_vars_in_expr(&self, e: &hir::Expr) {
+    pub fn resolve_type_vars_in_expr(&self, e: &hir::Expr, item_id: ast::NodeId) {
         assert_eq!(self.writeback_errors.get(), false);
         let mut wbcx = WritebackCx::new(self);
         wbcx.visit_expr(e);
@@ -45,9 +45,13 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         wbcx.visit_closures();
         wbcx.visit_liberated_fn_sigs();
         wbcx.visit_fru_field_types();
+        wbcx.visit_deferred_obligations(item_id);
     }
 
-    pub fn resolve_type_vars_in_fn(&self, decl: &hir::FnDecl, blk: &hir::Block) {
+    pub fn resolve_type_vars_in_fn(&self,
+                                   decl: &hir::FnDecl,
+                                   blk: &hir::Block,
+                                   item_id: ast::NodeId) {
         assert_eq!(self.writeback_errors.get(), false);
         let mut wbcx = WritebackCx::new(self);
         wbcx.visit_block(blk);
@@ -65,6 +69,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         wbcx.visit_liberated_fn_sigs();
         wbcx.visit_fru_field_types();
         wbcx.visit_anon_types();
+        wbcx.visit_deferred_obligations(item_id);
     }
 }
 
@@ -445,6 +450,19 @@ impl<'cx, 'gcx, 'tcx> WritebackCx<'cx, 'gcx, 'tcx> {
         }
     }
 
+    fn visit_deferred_obligations(&self, item_id: ast::NodeId) {
+        let deferred_obligations = self.fcx.deferred_obligations.borrow();
+        let obligations: Vec<_> = deferred_obligations.iter().map(|obligation| {
+            let reason = ResolvingDeferredObligation(obligation.cause.span);
+            self.resolve(obligation, reason)
+        }).collect();
+
+        if !obligations.is_empty() {
+            assert!(self.fcx.ccx.deferred_obligations.borrow_mut()
+                                .insert(item_id, obligations).is_none());
+        }
+    }
+
     fn resolve<T>(&self, x: &T, reason: ResolveReason) -> T::Lifted
         where T: TypeFoldable<'tcx> + ty::Lift<'gcx>
     {
@@ -461,7 +479,7 @@ impl<'cx, 'gcx, 'tcx> WritebackCx<'cx, 'gcx, 'tcx> {
 ///////////////////////////////////////////////////////////////////////////
 // Resolution reason.
 
-#[derive(Copy, Clone)]
+#[derive(Copy, Clone, Debug)]
 enum ResolveReason {
     ResolvingExpr(Span),
     ResolvingLocal(Span),
@@ -471,6 +489,7 @@ enum ResolveReason {
     ResolvingFnSig(ast::NodeId),
     ResolvingFieldTypes(ast::NodeId),
     ResolvingAnonTy(DefId),
+    ResolvingDeferredObligation(Span),
 }
 
 impl<'a, 'gcx, 'tcx> ResolveReason {
@@ -492,6 +511,7 @@ impl<'a, 'gcx, 'tcx> ResolveReason {
             ResolvingAnonTy(did) => {
                 tcx.map.def_id_span(did, DUMMY_SP)
             }
+            ResolvingDeferredObligation(span) => span
         }
     }
 }
@@ -564,14 +584,17 @@ impl<'cx, 'gcx, 'tcx> Resolver<'cx, 'gcx, 'tcx> {
                               "cannot determine a type for this closure")
                 }
 
-                ResolvingFnSig(id) | ResolvingFieldTypes(id) => {
+                ResolvingFnSig(_) |
+                ResolvingFieldTypes(_) |
+                ResolvingDeferredObligation(_) => {
                     // any failures here should also fail when
                     // resolving the patterns, closure types, or
                     // something else.
                     let span = self.reason.span(self.tcx);
                     self.tcx.sess.delay_span_bug(
                         span,
-                        &format!("cannot resolve some aspect of data for {:?}", id));
+                        &format!("cannot resolve some aspect of data for {:?}: {}",
+                                 self.reason, e));
                 }
 
                 ResolvingAnonTy(_) => {
diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs
index 78e8c905ab7..0dd4bc41439 100644
--- a/src/librustc_typeck/lib.rs
+++ b/src/librustc_typeck/lib.rs
@@ -107,7 +107,7 @@ use hir::map as hir_map;
 use rustc::infer::TypeOrigin;
 use rustc::ty::subst::Substs;
 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
-use rustc::traits::Reveal;
+use rustc::traits::{self, Reveal};
 use session::{config, CompileResult};
 use util::common::time;
 
@@ -150,6 +150,11 @@ pub struct CrateCtxt<'a, 'tcx: 'a> {
     pub stack: RefCell<Vec<collect::AstConvRequest>>,
 
     pub tcx: TyCtxt<'a, 'tcx, 'tcx>,
+
+    /// Obligations which will have to be checked at the end of
+    /// type-checking, after all functions have been inferred.
+    /// The key is the NodeId of the item the obligations were from.
+    pub deferred_obligations: RefCell<NodeMap<Vec<traits::DeferredObligation<'tcx>>>>,
 }
 
 // Functions that write types into the node type table
@@ -328,7 +333,8 @@ pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>)
         ast_ty_to_ty_cache: RefCell::new(NodeMap()),
         all_traits: RefCell::new(None),
         stack: RefCell::new(Vec::new()),
-        tcx: tcx
+        tcx: tcx,
+        deferred_obligations: RefCell::new(NodeMap()),
     };
 
     // this ensures that later parts of type checking can assume that items
diff --git a/src/test/compile-fail/impl-trait/auto-trait-leak.rs b/src/test/compile-fail/impl-trait/auto-trait-leak.rs
new file mode 100644
index 00000000000..2c78ce2db29
--- /dev/null
+++ b/src/test/compile-fail/impl-trait/auto-trait-leak.rs
@@ -0,0 +1,70 @@
+// Copyright 2016 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.
+
+// ignore-tidy-linelength
+
+#![feature(conservative_impl_trait)]
+
+use std::cell::Cell;
+use std::rc::Rc;
+
+// Fast path, main can see the concrete type returned.
+fn before() -> impl Fn(i32) {
+    let p = Rc::new(Cell::new(0));
+    move |x| p.set(x)
+}
+
+fn send<T: Send>(_: T) {}
+
+fn main() {
+    send(before());
+    //~^ ERROR the trait bound `std::rc::Rc<std::cell::Cell<i32>>: std::marker::Send` is not satisfied
+    //~| NOTE `std::rc::Rc<std::cell::Cell<i32>>` cannot be sent between threads safely
+    //~| NOTE required because it appears within the type `[closure
+    //~| NOTE required because it appears within the type `impl std::ops::Fn<(i32,)>`
+    //~| NOTE required by `send`
+
+    send(after());
+    //~^ ERROR the trait bound `std::rc::Rc<std::cell::Cell<i32>>: std::marker::Send` is not satisfied
+    //~| NOTE `std::rc::Rc<std::cell::Cell<i32>>` cannot be sent between threads safely
+    //~| NOTE required because it appears within the type `[closure
+    //~| NOTE required because it appears within the type `impl std::ops::Fn<(i32,)>`
+    //~| NOTE required by `send`
+}
+
+// Deferred path, main has to wait until typeck finishes,
+// to check if the return type of after is Send.
+fn after() -> impl Fn(i32) {
+    let p = Rc::new(Cell::new(0));
+    move |x| p.set(x)
+}
+
+// Cycles should work as the deferred obligations are
+// independently resolved and only require the concrete
+// return type, which can't depend on the obligation.
+fn cycle1() -> impl Clone {
+    send(cycle2().clone());
+    //~^ ERROR the trait bound `std::rc::Rc<std::string::String>: std::marker::Send` is not satisfied
+    //~| NOTE `std::rc::Rc<std::string::String>` cannot be sent between threads safely
+    //~| NOTE required because it appears within the type `impl std::clone::Clone`
+    //~| NOTE required by `send`
+
+    Rc::new(Cell::new(5))
+}
+
+fn cycle2() -> impl Clone {
+    send(cycle1().clone());
+    //~^ ERROR the trait bound `std::rc::Rc<std::cell::Cell<i32>>: std::marker::Send` is not satisfied
+    //~| NOTE `std::rc::Rc<std::cell::Cell<i32>>` cannot be sent between threads safely
+    //~| NOTE required because it appears within the type `impl std::clone::Clone`
+    //~| NOTE required by `send`
+
+    Rc::new(String::from("foo"))
+}
diff --git a/src/test/run-pass/impl-trait/auto-trait-leak.rs b/src/test/run-pass/impl-trait/auto-trait-leak.rs
new file mode 100644
index 00000000000..c1201e7fa4f
--- /dev/null
+++ b/src/test/run-pass/impl-trait/auto-trait-leak.rs
@@ -0,0 +1,44 @@
+// Copyright 2016 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.
+
+#![feature(conservative_impl_trait)]
+
+// Fast path, main can see the concrete type returned.
+fn before() -> impl FnMut(i32) {
+    let mut p = Box::new(0);
+    move |x| *p = x
+}
+
+fn send<T: Send>(_: T) {}
+
+fn main() {
+    send(before());
+    send(after());
+}
+
+// Deferred path, main has to wait until typeck finishes,
+// to check if the return type of after is Send.
+fn after() -> impl FnMut(i32) {
+    let mut p = Box::new(0);
+    move |x| *p = x
+}
+
+// Cycles should work as the deferred obligations are
+// independently resolved and only require the concrete
+// return type, which can't depend on the obligation.
+fn cycle1() -> impl Clone {
+    send(cycle2().clone());
+    5
+}
+
+fn cycle2() -> impl Clone {
+    send(cycle1().clone());
+    String::from("foo")
+}