Allow impl's to have late-bound regions. Introduces another level of

region binding at the impl site, so for method types that come from impls,
it is necessary to liberate/instantiate late-bound regions at multiple
depths.

19 files changed, 729 insertions, 261 deletions

diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs
index 20a29465bbd..a1257caf47f 100644
--- a/src/librustc/middle/resolve_lifetime.rs
+++ b/src/librustc/middle/resolve_lifetime.rs
@@ -105,8 +105,7 @@ impl<'a, 'v> Visitor<'v> for LifetimeContext<'a> {
             ast::ItemTy(_, ref generics) |
             ast::ItemEnum(_, ref generics) |
             ast::ItemStruct(_, ref generics) |
-            ast::ItemTrait(ref generics, _, _, _) |
-            ast::ItemImpl(ref generics, _, _, _) => {
+            ast::ItemTrait(ref generics, _, _, _) => {
                 // These kinds of items have only early bound lifetime parameters.
                 let lifetimes = &generics.lifetimes;
                 self.with(EarlyScope(subst::TypeSpace, lifetimes, &ROOT_SCOPE), |this| {
@@ -114,6 +113,13 @@ impl<'a, 'v> Visitor<'v> for LifetimeContext<'a> {
                     visit::walk_item(this, item);
                 });
             }
+            ast::ItemImpl(ref generics, _, _, _) => {
+                // Impls have both early- and late-bound lifetimes.
+                self.visit_early_late(subst::TypeSpace, generics, |this| {
+                    this.check_lifetime_defs(&generics.lifetimes);
+                    visit::walk_item(this, item);
+                })
+            }
         }
     }
 
@@ -493,10 +499,10 @@ fn early_bound_lifetime_names(generics: &ast::Generics) -> Vec<ast::Name> {
             FreeLifetimeCollector { early_bound: &mut early_bound,
                                     late_bound: &mut late_bound };
         for ty_param in generics.ty_params.iter() {
-            visit::walk_ty_param_bounds(&mut collector, &ty_param.bounds);
+            visit::walk_ty_param_bounds_helper(&mut collector, &ty_param.bounds);
         }
         for predicate in generics.where_clause.predicates.iter() {
-            visit::walk_ty_param_bounds(&mut collector, &predicate.bounds);
+            visit::walk_ty_param_bounds_helper(&mut collector, &predicate.bounds);
         }
     }
 
diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index ae7cb8645e1..4fabdabf3db 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -100,6 +100,17 @@ impl Substs {
         regions_is_noop && self.types.is_empty()
     }
 
+    pub fn has_regions_escaping_depth(&self, depth: uint) -> bool {
+        self.types.iter().any(|&t| ty::type_escapes_depth(t, depth)) || {
+            match self.regions {
+                ErasedRegions =>
+                    false,
+                NonerasedRegions(ref regions) =>
+                    regions.iter().any(|r| r.escapes_depth(depth)),
+            }
+        }
+    }
+
     pub fn self_ty(&self) -> Option<ty::t> {
         self.types.get_self().map(|&t| t)
     }
@@ -165,6 +176,13 @@ impl RegionSubsts {
             NonerasedRegions(r) => NonerasedRegions(op(r, a))
         }
     }
+
+    pub fn is_erased(&self) -> bool {
+        match *self {
+            ErasedRegions => true,
+            NonerasedRegions(_) => false,
+        }
+    }
 }
 
 ///////////////////////////////////////////////////////////////////////////
@@ -391,6 +409,10 @@ impl<T> VecPerParamSpace<T> {
         self.content.iter()
     }
 
+    pub fn iter_enumerated<'a>(&'a self) -> EnumeratedItems<'a,T> {
+        EnumeratedItems::new(self)
+    }
+
     pub fn as_slice(&self) -> &[T] {
         self.content.as_slice()
     }
@@ -420,6 +442,14 @@ impl<T> VecPerParamSpace<T> {
                                        self.assoc_limit)
     }
 
+    pub fn map_enumerated<U>(&self, pred: |(ParamSpace, uint, &T)| -> U) -> VecPerParamSpace<U> {
+        let result = self.iter_enumerated().map(pred).collect();
+        VecPerParamSpace::new_internal(result,
+                                       self.type_limit,
+                                       self.self_limit,
+                                       self.assoc_limit)
+    }
+
     pub fn map_move<U>(self, pred: |T| -> U) -> VecPerParamSpace<U> {
         let SeparateVecsPerParamSpace {
             types: t,
@@ -456,6 +486,49 @@ impl<T> VecPerParamSpace<T> {
     }
 }
 
+pub struct EnumeratedItems<'a,T:'a> {
+    vec: &'a VecPerParamSpace<T>,
+    space_index: uint,
+    elem_index: uint
+}
+
+impl<'a,T> EnumeratedItems<'a,T> {
+    fn new(v: &'a VecPerParamSpace<T>) -> EnumeratedItems<'a,T> {
+        let mut result = EnumeratedItems { vec: v, space_index: 0, elem_index: 0 };
+        result.adjust_space();
+        result
+    }
+
+    fn adjust_space(&mut self) {
+        let spaces = ParamSpace::all();
+        while
+            self.space_index < spaces.len() &&
+            self.elem_index >= self.vec.len(spaces[self.space_index])
+        {
+            self.space_index += 1;
+            self.elem_index = 0;
+        }
+    }
+}
+
+impl<'a,T> Iterator<(ParamSpace, uint, &'a T)> for EnumeratedItems<'a,T> {
+    fn next(&mut self) -> Option<(ParamSpace, uint, &'a T)> {
+        let spaces = ParamSpace::all();
+        if self.space_index < spaces.len() {
+            let space = spaces[self.space_index];
+            let index = self.elem_index;
+            let item = self.vec.get(space, index);
+
+            self.elem_index += 1;
+            self.adjust_space();
+
+            Some((space, index, item))
+        } else {
+            None
+        }
+    }
+}
+
 ///////////////////////////////////////////////////////////////////////////
 // Public trait `Subst`
 //
@@ -485,7 +558,8 @@ impl<T:TypeFoldable> Subst for T {
                                        substs: substs,
                                        span: span,
                                        root_ty: None,
-                                       ty_stack_depth: 0 };
+                                       ty_stack_depth: 0,
+                                       region_binders_passed: 0 };
         (*self).fold_with(&mut folder)
     }
 }
diff --git a/src/librustc/middle/traits/coherence.rs b/src/librustc/middle/traits/coherence.rs
index be5a007c1eb..405f6509e59 100644
--- a/src/librustc/middle/traits/coherence.rs
+++ b/src/librustc/middle/traits/coherence.rs
@@ -17,7 +17,7 @@ use super::util;
 use middle::subst;
 use middle::subst::Subst;
 use middle::ty;
-use middle::typeck::infer::InferCtxt;
+use middle::typeck::infer::{mod, InferCtxt};
 use syntax::ast;
 use syntax::codemap::DUMMY_SP;
 use util::ppaux::Repr;
@@ -38,14 +38,18 @@ pub fn impl_can_satisfy(infcx: &InferCtxt,
         util::fresh_substs_for_impl(infcx, DUMMY_SP, impl1_def_id);
     let impl1_trait_ref =
         ty::impl_trait_ref(infcx.tcx, impl1_def_id).unwrap()
-            .subst(infcx.tcx, &impl1_substs);
+                                                   .subst(infcx.tcx, &impl1_substs);
+    let impl1_trait_ref =
+        infcx.replace_late_bound_regions_with_fresh_var(DUMMY_SP,
+                                                        infer::FnCall,
+                                                        &impl1_trait_ref).0;
 
     // Determine whether `impl2` can provide an implementation for those
     // same types.
     let param_env = ty::empty_parameter_environment();
     let mut selcx = SelectionContext::intercrate(infcx, &param_env, infcx.tcx);
     let obligation = Obligation::misc(DUMMY_SP, impl1_trait_ref);
-    debug!("impl_can_satisfy obligation={}", obligation.repr(infcx.tcx));
+    debug!("impl_can_satisfy(obligation={})", obligation.repr(infcx.tcx));
     selcx.evaluate_impl(impl2_def_id, &obligation)
 }
 
diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index 9e0abb897f7..c9c9e3bd4ff 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -281,33 +281,28 @@ pub fn overlapping_impls(infcx: &InferCtxt,
     coherence::impl_can_satisfy(infcx, impl2_def_id, impl1_def_id)
 }
 
-pub fn impl_obligations(tcx: &ty::ctxt,
-                        cause: ObligationCause,
-                        impl_def_id: ast::DefId,
-                        impl_substs: &subst::Substs)
-                        -> subst::VecPerParamSpace<Obligation>
-{
-    let impl_generics = ty::lookup_item_type(tcx, impl_def_id).generics;
-    obligations_for_generics(tcx, cause, &impl_generics, impl_substs)
-}
-
 pub fn obligations_for_generics(tcx: &ty::ctxt,
                                 cause: ObligationCause,
-                                generics: &ty::Generics,
-                                substs: &subst::Substs)
+                                generic_bounds: &ty::GenericBounds,
+                                type_substs: &subst::VecPerParamSpace<ty::t>)
                                 -> subst::VecPerParamSpace<Obligation>
 {
     /*!
-     * Given generics for an impl like:
+     * Given generic bounds from an impl like:
      *
      *    impl<A:Foo, B:Bar+Qux> ...
      *
-     * and a substs vector like `<A=A0, B=B0>`, yields a result like
+     * along with the bindings for the types `A` and `B` (e.g.,
+     * `<A=A0, B=B0>`), yields a result like
      *
      *    [[Foo for A0, Bar for B0, Qux for B0], [], []]
+     *
+     * Expects that `generic_bounds` have already been fully
+     * substituted, late-bound regions liberated and so forth,
+     * so that they are in the same namespace as `type_substs`.
      */
 
-    util::obligations_for_generics(tcx, cause, 0, generics, substs)
+    util::obligations_for_generics(tcx, cause, 0, generic_bounds, type_substs)
 }
 
 pub fn obligation_for_builtin_bound(tcx: &ty::ctxt,
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index 38e70ec389e..a941d2b079e 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -2017,10 +2017,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                         impl_substs: &Substs)
                         -> VecPerParamSpace<Obligation>
     {
-        let impl_generics = ty::lookup_item_type(self.tcx(),
-                                                 impl_def_id).generics;
+        let impl_generics = ty::lookup_item_type(self.tcx(), impl_def_id).generics;
+        let bounds = impl_generics.to_bounds(self.tcx(), impl_substs);
         util::obligations_for_generics(self.tcx(), cause, recursion_depth,
-                                       &impl_generics, impl_substs)
+                                       &bounds, &impl_substs.types)
     }
 }
 
diff --git a/src/librustc/middle/traits/util.rs b/src/librustc/middle/traits/util.rs
index d8043fc2aab..8f8203f0281 100644
--- a/src/librustc/middle/traits/util.rs
+++ b/src/librustc/middle/traits/util.rs
@@ -10,7 +10,7 @@
 // except according to those terms.
 
 use middle::subst;
-use middle::subst::{ParamSpace, Subst, Substs, VecPerParamSpace};
+use middle::subst::{ParamSpace, Substs, VecPerParamSpace};
 use middle::typeck::infer::InferCtxt;
 use middle::ty;
 use std::collections::HashSet;
@@ -173,25 +173,25 @@ impl fmt::Show for VtableParamData {
 pub fn obligations_for_generics(tcx: &ty::ctxt,
                                 cause: ObligationCause,
                                 recursion_depth: uint,
-                                generics: &ty::Generics,
-                                substs: &Substs)
+                                generic_bounds: &ty::GenericBounds,
+                                type_substs: &VecPerParamSpace<ty::t>)
                                 -> VecPerParamSpace<Obligation>
 {
     /*! See `super::obligations_for_generics` */
 
-    debug!("obligations_for_generics(generics={}, substs={})",
-           generics.repr(tcx), substs.repr(tcx));
+    debug!("obligations_for_generics(generic_bounds={}, type_substs={})",
+           generic_bounds.repr(tcx), type_substs.repr(tcx));
 
     let mut obligations = VecPerParamSpace::empty();
 
-    for def in generics.types.iter() {
+    for (space, index, bounds) in generic_bounds.types.iter_enumerated() {
         push_obligations_for_param_bounds(tcx,
                                           cause,
                                           recursion_depth,
-                                          def.space,
-                                          def.index,
-                                          &def.bounds,
-                                          substs,
+                                          space,
+                                          index,
+                                          bounds,
+                                          type_substs,
                                           &mut obligations);
     }
 
@@ -207,11 +207,10 @@ fn push_obligations_for_param_bounds(
     space: subst::ParamSpace,
     index: uint,
     param_bounds: &ty::ParamBounds,
-    param_substs: &Substs,
+    param_type_substs: &VecPerParamSpace<ty::t>,
     obligations: &mut VecPerParamSpace<Obligation>)
 {
-    let param_ty = *param_substs.types.get(space, index);
-
+    let param_ty = *param_type_substs.get(space, index);
     for builtin_bound in param_bounds.builtin_bounds.iter() {
         let obligation = obligation_for_builtin_bound(tcx,
                                                       cause,
@@ -225,12 +224,11 @@ fn push_obligations_for_param_bounds(
     }
 
     for bound_trait_ref in param_bounds.trait_bounds.iter() {
-        let bound_trait_ref = bound_trait_ref.subst(tcx, param_substs);
         obligations.push(
             space,
             Obligation { cause: cause,
                          recursion_depth: recursion_depth,
-                         trait_ref: bound_trait_ref });
+                         trait_ref: (*bound_trait_ref).clone() });
     }
 }
 
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index ec8285c33de..9f90afa3749 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -1409,6 +1409,52 @@ impl Generics {
     pub fn has_region_params(&self, space: subst::ParamSpace) -> bool {
         !self.regions.is_empty_in(space)
     }
+
+    pub fn to_bounds(&self, tcx: &ty::ctxt, substs: &Substs) -> GenericBounds {
+        GenericBounds {
+            types: self.types.map(|d| d.bounds.subst(tcx, substs)),
+            regions: self.regions.map(|d| d.bounds.subst(tcx, substs)),
+        }
+    }
+}
+
+/**
+ * Represents the bounds declared on a particular set of type
+ * parameters.  Should eventually be generalized into a flag list of
+ * where clauses.  You can obtain a `GenericBounds` list from a
+ * `Generics` by using the `to_bounds` method. Note that this method
+ * reflects an important semantic invariant of `GenericBounds`: while
+ * the bounds in a `Generics` are expressed in terms of the bound type
+ * parameters of the impl/trait/whatever, a `GenericBounds` instance
+ * represented a set of bounds for some particular instantiation,
+ * meaning that the generic parameters have been substituted with
+ * their values.
+ *
+ * Example:
+ *
+ *     struct Foo<T,U:Bar<T>> { ... }
+ *
+ * Here, the `Generics` for `Foo` would contain a list of bounds like
+ * `[[], [U:Bar<T>]]`.  Now if there were some particular reference
+ * like `Foo<int,uint>`, then the `GenericBounds` would be `[[],
+ * [uint:Bar<int>]]`.
+ */
+#[deriving(Clone, Show)]
+pub struct GenericBounds {
+    pub types: VecPerParamSpace<ParamBounds>,
+    pub regions: VecPerParamSpace<Vec<Region>>,
+}
+
+impl GenericBounds {
+    pub fn empty() -> GenericBounds {
+        GenericBounds { types: VecPerParamSpace::empty(),
+                        regions: VecPerParamSpace::empty() }
+    }
+
+    pub fn has_escaping_regions(&self) -> bool {
+        self.types.any(|pb| pb.trait_bounds.iter().any(|tr| tr.has_escaping_regions())) ||
+            self.regions.any(|rs| rs.iter().any(|r| r.escapes_depth(0)))
+    }
 }
 
 impl TraitRef {
@@ -5632,11 +5678,13 @@ pub fn construct_parameter_environment(
     // Compute the bounds on Self and the type parameters.
     //
 
-    let mut bounds = VecPerParamSpace::empty();
-    for &space in subst::ParamSpace::all().iter() {
-        push_bounds_from_defs(tcx, &mut bounds, space, &free_substs,
-                              generics.types.get_slice(space));
-    }
+    let bounds = generics.to_bounds(tcx, &free_substs);
+    let bounds = liberate_late_bound_regions(tcx, free_id, &bind(bounds)).value;
+    let obligations = traits::obligations_for_generics(tcx,
+                                                       traits::ObligationCause::misc(span),
+                                                       &bounds,
+                                                       &free_substs.types);
+    let type_bounds = bounds.types.subst(tcx, &free_substs);
 
     //
     // Compute region bounds. For now, these relations are stored in a
@@ -5645,24 +5693,20 @@ pub fn construct_parameter_environment(
     //
 
     for &space in subst::ParamSpace::all().iter() {
-        record_region_bounds_from_defs(tcx, space, &free_substs,
-                                       generics.regions.get_slice(space));
+        record_region_bounds(tcx, space, &free_substs, bounds.regions.get_slice(space));
     }
 
 
-    debug!("construct_parameter_environment: free_id={} \
-           free_subst={} \
-           bounds={}",
+    debug!("construct_parameter_environment: free_id={} free_subst={} \
+           obligations={} type_bounds={}",
            free_id,
            free_substs.repr(tcx),
-           bounds.repr(tcx));
-
-    let obligations = traits::obligations_for_generics(tcx, traits::ObligationCause::misc(span),
-                                                       generics, &free_substs);
+           obligations.repr(tcx),
+           type_bounds.repr(tcx));
 
     return ty::ParameterEnvironment {
         free_substs: free_substs,
-        bounds: bounds,
+        bounds: bounds.types,
         implicit_region_bound: ty::ReScope(free_id),
         caller_obligations: obligations,
         selection_cache: traits::SelectionCache::new(),
@@ -5693,28 +5737,16 @@ pub fn construct_parameter_environment(
         }
     }
 
-    fn push_bounds_from_defs(tcx: &ty::ctxt,
-                             bounds: &mut subst::VecPerParamSpace<ParamBounds>,
-                             space: subst::ParamSpace,
-                             free_substs: &subst::Substs,
-                             defs: &[TypeParameterDef]) {
-        for def in defs.iter() {
-            let b = def.bounds.subst(tcx, free_substs);
-            bounds.push(space, b);
-        }
-    }
-
-    fn record_region_bounds_from_defs(tcx: &ty::ctxt,
-                                      space: subst::ParamSpace,
-                                      free_substs: &subst::Substs,
-                                      defs: &[RegionParameterDef]) {
-        for (subst_region, def) in
+    fn record_region_bounds(tcx: &ty::ctxt,
+                            space: subst::ParamSpace,
+                            free_substs: &Substs,
+                            bound_sets: &[Vec<ty::Region>]) {
+        for (subst_region, bound_set) in
             free_substs.regions().get_slice(space).iter().zip(
-                defs.iter())
+                bound_sets.iter())
         {
             // For each region parameter 'subst...
-            let bounds = def.bounds.subst(tcx, free_substs);
-            for bound_region in bounds.iter() {
+            for bound_region in bound_set.iter() {
                 // Which is declared with a bound like 'subst:'bound...
                 match (subst_region, bound_region) {
                     (&ty::ReFree(subst_fr), &ty::ReFree(bound_fr)) => {
@@ -5725,7 +5757,7 @@ pub fn construct_parameter_environment(
                     _ => {
                         // All named regions are instantiated with free regions.
                         tcx.sess.bug(
-                            format!("push_region_bounds_from_defs: \
+                            format!("record_region_bounds: \
                                      non free region: {} / {}",
                                     subst_region.repr(tcx),
                                     bound_region.repr(tcx)).as_slice());
diff --git a/src/librustc/middle/ty_fold.rs b/src/librustc/middle/ty_fold.rs
index 52e6bcf5b6d..4dfee673bca 100644
--- a/src/librustc/middle/ty_fold.rs
+++ b/src/librustc/middle/ty_fold.rs
@@ -410,6 +410,15 @@ impl TypeFoldable for ty::Generics {
     }
 }
 
+impl TypeFoldable for ty::GenericBounds {
+    fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::GenericBounds {
+        ty::GenericBounds {
+            types: self.types.fold_with(folder),
+            regions: self.regions.fold_with(folder),
+        }
+    }
+}
+
 impl TypeFoldable for ty::UnsizeKind {
     fn fold_with<'tcx, F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::UnsizeKind {
         match *self {
diff --git a/src/librustc/middle/typeck/check/method/confirm.rs b/src/librustc/middle/typeck/check/method/confirm.rs
index ba64a1e23a7..b4d22f117d4 100644
--- a/src/librustc/middle/typeck/check/method/confirm.rs
+++ b/src/librustc/middle/typeck/check/method/confirm.rs
@@ -20,6 +20,7 @@ use middle::typeck::{MethodCall, MethodCallee, MethodObject, MethodOrigin,
                      MethodParam, MethodStatic, MethodTraitObject, MethodTypeParam};
 use middle::typeck::infer;
 use middle::typeck::infer::InferCtxt;
+use middle::ty_fold::HigherRankedFoldable;
 use syntax::ast;
 use syntax::codemap::Span;
 use std::rc::Rc;
@@ -32,6 +33,27 @@ struct ConfirmContext<'a, 'tcx:'a> {
     self_expr: &'a ast::Expr,
 }
 
+struct InstantiatedMethodSig {
+    /// Function signature of the method being invoked. The 0th
+    /// argument is the receiver.
+    method_sig: ty::FnSig,
+
+    /// Substitutions for all types/early-bound-regions declared on
+    /// the method.
+    all_substs: subst::Substs,
+
+    /// Substitution to use when adding obligations from the method
+    /// bounds. Normally equal to `all_substs` except for object
+    /// receivers. See FIXME in instantiate_method_sig() for
+    /// explanation.
+    method_bounds_substs: subst::Substs,
+
+    /// Generic bounds on the method's parameters which must be added
+    /// as pending obligations.
+    method_bounds: ty::GenericBounds,
+}
+
+
 pub fn confirm(fcx: &FnCtxt,
                span: Span,
                self_expr: &ast::Expr,
@@ -79,14 +101,16 @@ impl<'a,'tcx> ConfirmContext<'a,'tcx> {
         debug!("all_substs={}", all_substs.repr(self.tcx()));
 
         // Create the final signature for the method, replacing late-bound regions.
-        let method_sig = self.instantiate_method_sig(&pick, &all_substs);
+        let InstantiatedMethodSig {
+            method_sig, all_substs, method_bounds_substs, method_bounds
+        } = self.instantiate_method_sig(&pick, all_substs);
         let method_self_ty = method_sig.inputs[0];
 
         // Unify the (adjusted) self type with what the method expects.
         self.unify_receivers(self_ty, method_self_ty);
 
         // Add any trait/regions obligations specified on the method's type parameters.
-        self.add_obligations(&pick, &all_substs);
+        self.add_obligations(&pick, &method_bounds_substs, &method_bounds);
 
         // Create the final `MethodCallee`.
         let fty = ty::mk_bare_fn(self.tcx(), ty::BareFnTy {
@@ -176,6 +200,10 @@ impl<'a,'tcx> ConfirmContext<'a,'tcx> {
          * where all type and region parameters are instantiated with
          * fresh variables. This substitution does not include any
          * parameters declared on the method itself.
+         *
+         * Note that this substitution may include late-bound regions
+         * from the impl level. If so, these are instantiated later in
+         * the `instantiate_method_sig` routine.
          */
 
         match pick.kind {
@@ -354,20 +382,34 @@ impl<'a,'tcx> ConfirmContext<'a,'tcx> {
 
     fn instantiate_method_sig(&mut self,
                               pick: &probe::Pick,
-                              all_substs: &subst::Substs)
-                              -> ty::FnSig
+                              all_substs: subst::Substs)
+                              -> InstantiatedMethodSig
     {
-        let ref bare_fn_ty = pick.method_ty.fty;
-        let fn_sig = bare_fn_ty.sig.subst(self.tcx(), all_substs);
-        self.infcx().replace_late_bound_regions_with_fresh_var(fn_sig.binder_id,
-                                                               self.span,
-                                                               infer::FnCall,
-                                                               &fn_sig).0
-    }
-
-    fn add_obligations(&mut self,
-                       pick: &probe::Pick,
-                       all_substs: &subst::Substs) {
+        // If this method comes from an impl (as opposed to a trait),
+        // it may have late-bound regions from the impl that appear in
+        // the substitutions, method signature, and
+        // bounds. Instantiate those at this point. (If it comes from
+        // a trait, this step has no effect, as there are no
+        // late-bound regions to instantiate.)
+        //
+        // The binder level here corresponds to the impl.
+        let (all_substs, (method_sig, method_generics)) =
+            self.replace_late_bound_regions_with_fresh_var(
+                &ty::bind((all_substs,
+                           (pick.method_ty.fty.sig.clone(),
+                            pick.method_ty.generics.clone())))).value;
+
+        debug!("late-bound lifetimes from impl instantiated, \
+                all_substs={} method_sig={} method_generics={}",
+               all_substs.repr(self.tcx()),
+               method_sig.repr(self.tcx()),
+               method_generics.repr(self.tcx()));
+
+        // Instantiate the bounds on the method with the
+        // type/early-bound-regions substitutions performed.  The only
+        // late-bound-regions that can appear in bounds are from the
+        // impl, and those were already instantiated above.
+        //
         // FIXME(DST). Super hack. For a method on a trait object
         // `Trait`, the generic signature requires that
         // `Self:Trait`. Since, for an object, we bind `Self` to the
@@ -381,24 +423,54 @@ impl<'a,'tcx> ConfirmContext<'a,'tcx> {
         // obligations.  This causes us to generate the obligation
         // `err:Trait`, and the error type is considered to implement
         // all traits, so we're all good. Hack hack hack.
-        match pick.kind {
+        let method_bounds_substs = match pick.kind {
             probe::ObjectPick(..) => {
                 let mut temp_substs = all_substs.clone();
                 temp_substs.types.get_mut_slice(subst::SelfSpace)[0] = ty::mk_err();
-                self.fcx.add_obligations_for_parameters(
-                    traits::ObligationCause::misc(self.span),
-                    &temp_substs,
-                    &pick.method_ty.generics);
+                temp_substs
             }
             _ => {
-                self.fcx.add_obligations_for_parameters(
-                    traits::ObligationCause::misc(self.span),
-                    all_substs,
-                    &pick.method_ty.generics);
+                all_substs.clone()
             }
+        };
+        let method_bounds =
+            method_generics.to_bounds(self.tcx(), &method_bounds_substs);
+
+        debug!("method_bounds after subst = {}",
+               method_bounds.repr(self.tcx()));
+
+        // Substitute the type/early-bound-regions into the method
+        // signature. In addition, the method signature may bind
+        // late-bound regions, so instantiate those.
+        let method_sig = method_sig.subst(self.tcx(), &all_substs);
+        let method_sig = self.replace_late_bound_regions_with_fresh_var(&method_sig);
+
+        debug!("late-bound lifetimes from method instantiated, method_sig={}",
+               method_sig.repr(self.tcx()));
+
+        InstantiatedMethodSig {
+            method_sig: method_sig,
+            all_substs: all_substs,
+            method_bounds_substs: method_bounds_substs,
+            method_bounds: method_bounds,
         }
     }
 
+    fn add_obligations(&mut self,
+                       pick: &probe::Pick,
+                       method_bounds_substs: &subst::Substs,
+                       method_bounds: &ty::GenericBounds) {
+        debug!("add_obligations: pick={} method_bounds_substs={} method_bounds={}",
+               pick.repr(self.tcx()),
+               method_bounds_substs.repr(self.tcx()),
+               method_bounds.repr(self.tcx()));
+
+        self.fcx.add_obligations_for_parameters(
+            traits::ObligationCause::misc(self.span),
+            method_bounds_substs,
+            method_bounds);
+    }
+
     ///////////////////////////////////////////////////////////////////////////
     // RECONCILIATION
 
@@ -591,6 +663,13 @@ impl<'a,'tcx> ConfirmContext<'a,'tcx> {
                     source_trait_ref.repr(self.tcx()),
                     target_trait_def_id.repr(self.tcx()))[]);
     }
+
+    fn replace_late_bound_regions_with_fresh_var<T>(&self, value: &T) -> T
+        where T : HigherRankedFoldable
+    {
+        self.infcx().replace_late_bound_regions_with_fresh_var(
+            self.span, infer::FnCall, value).0
+    }
 }
 
 fn wrap_autoref(mut deref: ty::AutoDerefRef,
diff --git a/src/librustc/middle/typeck/check/method/mod.rs b/src/librustc/middle/typeck/check/method/mod.rs
index d4f1d4defa3..6c7df2cd07e 100644
--- a/src/librustc/middle/typeck/check/method/mod.rs
+++ b/src/librustc/middle/typeck/check/method/mod.rs
@@ -200,10 +200,12 @@ pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &'a FnCtxt<'a, 'tcx>,
 
     // Substitute the trait parameters into the method type and
     // instantiate late-bound regions to get the actual method type.
+    //
+    // Note that as the method comes from a trait, it can only have
+    // late-bound regions from the fn itself, not the impl.
     let ref bare_fn_ty = method_ty.fty;
     let fn_sig = bare_fn_ty.sig.subst(tcx, &trait_ref.substs);
-    let fn_sig = fcx.infcx().replace_late_bound_regions_with_fresh_var(fn_sig.binder_id,
-                                                                       span,
+    let fn_sig = fcx.infcx().replace_late_bound_regions_with_fresh_var(span,
                                                                        infer::FnCall,
                                                                        &fn_sig).0;
     let transformed_self_ty = fn_sig.inputs[0];
@@ -222,10 +224,15 @@ pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &'a FnCtxt<'a, 'tcx>,
     // so this also effectively registers `obligation` as well.  (We
     // used to register `obligation` explicitly, but that resulted in
     // double error messages being reported.)
+    //
+    // Note that as the method comes from a trait, it should not have
+    // any late-bound regions appearing in its bounds.
+    let method_bounds = method_ty.generics.to_bounds(fcx.tcx(), &trait_ref.substs);
+    assert!(!method_bounds.has_escaping_regions());
     fcx.add_obligations_for_parameters(
         traits::ObligationCause::misc(span),
         &trait_ref.substs,
-        &method_ty.generics);
+        &method_bounds);
 
     // FIXME(#18653) -- Try to resolve obligations, giving us more
     // typing information, which can sometimes be needed to avoid
diff --git a/src/librustc/middle/typeck/check/method/probe.rs b/src/librustc/middle/typeck/check/method/probe.rs
index 2e5397e768e..f9c3fa86752 100644
--- a/src/librustc/middle/typeck/check/method/probe.rs
+++ b/src/librustc/middle/typeck/check/method/probe.rs
@@ -17,6 +17,7 @@ use middle::subst;
 use middle::subst::Subst;
 use middle::traits;
 use middle::ty;
+use middle::ty_fold::HigherRankedFoldable;
 use middle::typeck::check;
 use middle::typeck::check::{FnCtxt, NoPreference};
 use middle::typeck::{MethodObject};
@@ -257,29 +258,28 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
         ty::populate_implementations_for_type_if_necessary(self.tcx(), def_id);
 
         for impl_infos in self.tcx().inherent_impls.borrow().get(&def_id).iter() {
-            for &impl_did in impl_infos.iter() {
-                self.assemble_inherent_impl_probe(impl_did);
+            for &impl_def_id in impl_infos.iter() {
+                self.assemble_inherent_impl_probe(impl_def_id);
             }
         }
     }
 
-    fn assemble_inherent_impl_probe(&mut self, impl_did: ast::DefId) {
-        if !self.impl_dups.insert(impl_did) {
+    fn assemble_inherent_impl_probe(&mut self, impl_def_id: ast::DefId) {
+        if !self.impl_dups.insert(impl_def_id) {
             return; // already visited
         }
 
-        let method = match impl_method(self.tcx(), impl_did, self.method_name) {
+        let method = match impl_method(self.tcx(), impl_def_id, self.method_name) {
             Some(m) => m,
             None => { return; } // No method with correct name on this impl
         };
 
         if !self.has_applicable_self(&*method) {
             // No receiver declared. Not a candidate.
-            return self.record_static_candidate(ImplSource(impl_did));
+            return self.record_static_candidate(ImplSource(impl_def_id));
         }
 
-        let impl_pty = check::impl_self_ty(self.fcx, self.span, impl_did);
-        let impl_substs = impl_pty.substs;
+        let impl_substs = self.impl_substs(impl_def_id);
 
         // Determine the receiver type that the method itself expects.
         let xform_self_ty =
@@ -288,7 +288,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
         self.inherent_candidates.push(Candidate {
             xform_self_ty: xform_self_ty,
             method_ty: method,
-            kind: InherentImplCandidate(impl_did, impl_substs)
+            kind: InherentImplCandidate(impl_def_id, impl_substs)
         });
     }
 
@@ -496,8 +496,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
                 continue;
             }
 
-            let impl_pty = check::impl_self_ty(self.fcx, self.span, impl_def_id);
-            let impl_substs = impl_pty.substs;
+            let impl_substs = self.impl_substs(impl_def_id);
 
             debug!("impl_substs={}", impl_substs.repr(self.tcx()));
 
@@ -675,7 +674,9 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
                            mk_autoref_ty: |ast::Mutability, ty::Region| -> ty::t)
                            -> Option<PickResult>
     {
-        let region = self.infcx().next_region_var(infer::Autoref(self.span));
+        // In general, during probing we erase regions. See
+        // `impl_self_ty()` for an explanation.
+        let region = ty::ReStatic;
 
         // Search through mutabilities in order to find one where pick works:
         [ast::MutImmutable, ast::MutMutable]
@@ -746,6 +747,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
                probe.repr(self.tcx()));
 
         self.infcx().probe(|| {
+            // First check that the self type can be related.
             match self.make_sub_ty(self_ty, probe.xform_self_ty) {
                 Ok(()) => { }
                 Err(_) => {
@@ -754,23 +756,34 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
                 }
             }
 
+            // If so, impls may carry other conditions (e.g., where
+            // clauses) that must be considered. Make sure that those
+            // match as well (or at least may match, sometimes we
+            // don't have enough information to fully evaluate).
             match probe.kind {
                 InherentImplCandidate(impl_def_id, ref substs) |
                 ExtensionImplCandidate(impl_def_id, _, ref substs, _) => {
                     // Check whether the impl imposes obligations we have to worry about.
+                    let impl_generics = ty::lookup_item_type(self.tcx(), impl_def_id).generics;
+                    let impl_bounds = impl_generics.to_bounds(self.tcx(), substs);
+
+                    // Erase any late-bound regions bound in the impl
+                    // which appear in the bounds.
+                    let impl_bounds = self.erase_late_bound_regions(&ty::bind(impl_bounds)).value;
+
+                    // Convert the bounds into obligations.
                     let obligations =
-                        traits::impl_obligations(
+                        traits::obligations_for_generics(
                             self.tcx(),
                             traits::ObligationCause::misc(self.span),
-                            impl_def_id,
-                            substs);
-
+                            &impl_bounds,
+                            &substs.types);
                     debug!("impl_obligations={}", obligations.repr(self.tcx()));
 
+                    // Evaluate those obligations to see if they might possibly hold.
                     let mut selcx = traits::SelectionContext::new(self.infcx(),
                                                                   &self.fcx.inh.param_env,
                                                                   self.fcx);
-
                     obligations.all(|o| selcx.evaluate_obligation(o))
                 }
 
@@ -883,20 +896,78 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> {
                 self.infcx().next_ty_vars(
                     method.generics.types.len(subst::FnSpace));
 
+            // In general, during probe we erase regions. See
+            // `impl_self_ty()` for an explanation.
             let method_regions =
-                self.infcx().region_vars_for_defs(
-                    self.span,
-                    method.generics.regions.get_slice(subst::FnSpace));
+                method.generics.regions.get_slice(subst::FnSpace)
+                .iter()
+                .map(|_| ty::ReStatic)
+                .collect();
 
             placeholder = (*substs).clone().with_method(method_types, method_regions);
             substs = &placeholder;
         }
 
+        // Replace early-bound regions and types.
         let xform_self_ty = method.fty.sig.inputs[0].subst(self.tcx(), substs);
-        self.infcx().replace_late_bound_regions_with_fresh_var(method.fty.sig.binder_id,
-                                                               self.span,
-                                                               infer::FnCall,
-                                                               &xform_self_ty).0
+
+        // Replace late-bound regions bound in the impl or
+        // where-clause (2 levels of binding).
+        let xform_self_ty =
+            self.erase_late_bound_regions(&ty::bind(ty::bind(xform_self_ty))).value.value;
+
+        // Replace late-bound regions bound in the method (1 level of binding).
+        self.erase_late_bound_regions(&ty::bind(xform_self_ty)).value
+    }
+
+    fn impl_substs(&self,
+                   impl_def_id: ast::DefId)
+                   -> subst::Substs
+    {
+        let impl_pty = ty::lookup_item_type(self.tcx(), impl_def_id);
+
+        let type_vars =
+            impl_pty.generics.types.map(
+                |_| self.infcx().next_ty_var());
+
+        let region_placeholders =
+            impl_pty.generics.regions.map(
+                |_| ty::ReStatic); // see erase_late_bound_regions() for an expl of why 'static
+
+        subst::Substs::new(type_vars, region_placeholders)
+    }
+
+    fn erase_late_bound_regions<T>(&self, value: &T) -> T
+        where T : HigherRankedFoldable
+    {
+        /*!
+         * Replace late-bound-regions bound by `value` with `'static`
+         * using `ty::erase_late_bound_regions`.
+         *
+         * This is only a reasonable thing to do during the *probe*
+         * phase, not the *confirm* phase, of method matching. It is
+         * reasonable during the probe phase because we don't consider
+         * region relationships at all. Therefore, we can just replace
+         * all the region variables with 'static rather than creating
+         * fresh region variables. This is nice for two reasons:
+         *
+         * 1. Because the numbers of the region variables would
+         *    otherwise be fairly unique to this particular method
+         *    call, it winds up creating fewer types overall, which
+         *    helps for memory usage. (Admittedly, this is a rather
+         *    small effect, though measureable.)
+         *
+         * 2. It makes it easier to deal with higher-ranked trait
+         *    bounds, because we can replace any late-bound regions
+         *    with 'static. Otherwise, if we were going to replace
+         *    late-bound regions with actual region variables as is
+         *    proper, we'd have to ensure that the same region got
+         *    replaced with the same variable, which requires a bit
+         *    more coordination and/or tracking the substitution and
+         *    so forth.
+         */
+
+        ty::erase_late_bound_regions(self.tcx(), value)
     }
 }
 
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index a21c7929fde..ea6028acf24 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -97,12 +97,12 @@ use middle::ty::{FnSig, VariantInfo};
 use middle::ty::{Polytype};
 use middle::ty::{Disr, ParamTy, ParameterEnvironment};
 use middle::ty;
+use middle::ty::{replace_late_bound_regions, liberate_late_bound_regions};
 use middle::ty_fold::TypeFolder;
 use middle::typeck::astconv::AstConv;
 use middle::typeck::astconv::{ast_region_to_region, ast_ty_to_ty};
 use middle::typeck::astconv;
 use middle::typeck::check::_match::pat_ctxt;
-use middle::typeck::check::regionmanip::replace_late_bound_regions;
 use middle::typeck::CrateCtxt;
 use middle::typeck::infer;
 use middle::typeck::rscope::RegionScope;
@@ -738,6 +738,11 @@ fn check_method_body(ccx: &CrateCtxt,
     let param_env = ParameterEnvironment::for_item(ccx.tcx, method.id);
 
     let fty = ty::node_id_to_type(ccx.tcx, method.id);
+    debug!("fty (raw): {}", fty.repr(ccx.tcx));
+
+    let body_id = method.pe_body().id;
+    let fty = liberate_late_bound_regions(ccx.tcx, body_id, &ty::bind(fty)).value;
+    debug!("fty (liberated): {}", fty.repr(ccx.tcx));
 
     check_bare_fn(ccx,
                   &*method.pe_fn_decl(),
@@ -782,7 +787,7 @@ fn check_impl_items_against_trait(ccx: &CrateCtxt,
                                                     impl_method.span,
                                                     impl_method.pe_body().id,
                                                     &**trait_method_ty,
-                                                    &impl_trait_ref.substs);
+                                                    impl_trait_ref);
                             }
                             _ => {
                                 // This is span_bug as it should have already been
@@ -927,11 +932,36 @@ fn compare_impl_method(tcx: &ty::ctxt,
                        impl_m_span: Span,
                        impl_m_body_id: ast::NodeId,
                        trait_m: &ty::Method,
-                       trait_to_impl_substs: &subst::Substs) {
-    debug!("compare_impl_method(trait_to_impl_substs={})",
-           trait_to_impl_substs.repr(tcx));
+                       impl_trait_ref: &ty::TraitRef) {
+    debug!("compare_impl_method(impl_trait_ref={})",
+           impl_trait_ref.repr(tcx));
+
+    // The impl's trait ref may bind late-bound regions from the impl.
+    // Liberate them and assign them the scope of the method body.
+    //
+    // An example would be:
+    //
+    //     impl<'a> Foo<&'a T> for &'a U { ... }
+    //
+    // Here, the region parameter `'a` is late-bound, so the
+    // trait reference associated with the impl will be
+    //
+    //     for<'a> Foo<&'a T>
+    //
+    // liberating will convert this into:
+    //
+    //     Foo<&'A T>
+    //
+    // where `'A` is the `ReFree` version of `'a`.
+    let impl_trait_ref = liberate_late_bound_regions(tcx, impl_m_body_id, impl_trait_ref);
+
+    debug!("impl_trait_ref (liberated) = {}",
+           impl_trait_ref.repr(tcx));
+
     let infcx = infer::new_infer_ctxt(tcx);
 
+    let trait_to_impl_substs = &impl_trait_ref.substs;
+
     // Try to give more informative error messages about self typing
     // mismatches.  Note that any mismatch will also be detected
     // below, where we construct a canonical function type that
@@ -995,22 +1025,23 @@ fn compare_impl_method(tcx: &ty::ctxt,
 
     // This code is best explained by example. Consider a trait:
     //
-    //     trait Trait<T> {
-    //          fn method<'a,M>(t: T, m: &'a M) -> Self;
+    //     trait Trait<'t,T> {
+    //          fn method<'a,M>(t: &'t T, m: &'a M) -> Self;
     //     }
     //
     // And an impl:
     //
-    //     impl<'i, U> Trait<&'i U> for Foo {
-    //          fn method<'b,N>(t: &'i U, m: &'b N) -> Foo;
+    //     impl<'i, 'j, U> Trait<'j, &'i U> for Foo {
+    //          fn method<'b,N>(t: &'j &'i U, m: &'b N) -> Foo;
     //     }
     //
     // We wish to decide if those two method types are compatible.
     //
-    // We start out with trait_to_impl_substs, that maps the trait type
-    // parameters to impl type parameters:
+    // We start out with trait_to_impl_substs, that maps the trait
+    // type parameters to impl type parameters. This is taken from the
+    // impl trait reference:
     //
-    //     trait_to_impl_substs = {T => &'i U, Self => Foo}
+    //     trait_to_impl_substs = {'t => 'j, T => &'i U, Self => Foo}
     //
     // We create a mapping `dummy_substs` that maps from the impl type
     // parameters to fresh types and regions. For type parameters,
@@ -1065,6 +1096,7 @@ fn compare_impl_method(tcx: &ty::ctxt,
     if !check_region_bounds_on_impl_method(tcx,
                                            impl_m_span,
                                            impl_m,
+                                           impl_m_body_id,
                                            &trait_m.generics,
                                            &impl_m.generics,
                                            &trait_to_skol_substs,
@@ -1072,15 +1104,50 @@ fn compare_impl_method(tcx: &ty::ctxt,
         return;
     }
 
-    // Check bounds.
-    let it = trait_m.generics.types.get_slice(subst::FnSpace).iter()
-        .zip(impl_m.generics.types.get_slice(subst::FnSpace).iter());
-    for (i, (trait_param_def, impl_param_def)) in it.enumerate() {
+    // Check bounds. Note that the bounds from the impl may reference
+    // late-bound regions declared on the impl, so liberate those.
+    // This requires two artificial binding scopes -- one for the impl,
+    // and one for the method.
+    //
+    // An example would be:
+    //
+    //     trait Foo<T> { fn method<U:Bound<T>>() { ... } }
+    //
+    //     impl<'a> Foo<&'a T> for &'a U {
+    //         fn method<U:Bound<&'a T>>() { ... }
+    //     }
+    //
+    // Here, the region parameter `'a` is late-bound, so in the bound
+    // `Bound<&'a T>`, the lifetime `'a` will be late-bound with a
+    // depth of 3 (it is nested within 3 binders: the impl, method,
+    // and trait-ref itself). So when we do the liberation, we have
+    // two introduce two `ty::bind` scopes, one for the impl and one
+    // the method.
+    //
+    // The only late-bounded regions that can possibly appear here are
+    // from the impl, not the method. This is because region
+    // parameters declared on the method which appear in a type bound
+    // would be early bound. On the trait side, there can be no
+    // late-bound lifetimes because trait definitions do not introduce
+    // a late region binder.
+    let trait_bounds =
+        trait_m.generics.types.get_slice(subst::FnSpace).iter()
+        .map(|trait_param_def| &trait_param_def.bounds);
+    let impl_bounds =
+        impl_m.generics.types.get_slice(subst::FnSpace).iter()
+        .map(|impl_param_def|
+             liberate_late_bound_regions(
+                 tcx,
+                 impl_m_body_id,
+                 &ty::bind(ty::bind(impl_param_def.bounds.clone()))).value.value);
+    for (i, (trait_param_bounds, impl_param_bounds)) in
+        trait_bounds.zip(impl_bounds).enumerate()
+    {
         // Check that the impl does not require any builtin-bounds
         // that the trait does not guarantee:
         let extra_bounds =
-            impl_param_def.bounds.builtin_bounds -
-            trait_param_def.bounds.builtin_bounds;
+            impl_param_bounds.builtin_bounds -
+            trait_param_bounds.builtin_bounds;
         if !extra_bounds.is_empty() {
             span_err!(tcx.sess, impl_m_span, E0051,
                 "in method `{}`, type parameter {} requires `{}`, \
@@ -1097,31 +1164,32 @@ fn compare_impl_method(tcx: &ty::ctxt,
         //
         // FIXME(pcwalton): We could be laxer here regarding sub- and super-
         // traits, but I doubt that'll be wanted often, so meh.
-        for impl_trait_bound in impl_param_def.bounds.trait_bounds.iter() {
+        for impl_trait_bound in impl_param_bounds.trait_bounds.iter() {
             debug!("compare_impl_method(): impl-trait-bound subst");
             let impl_trait_bound =
                 impl_trait_bound.subst(tcx, &impl_to_skol_substs);
 
-            let mut ok = false;
-            for trait_bound in trait_param_def.bounds.trait_bounds.iter() {
-                debug!("compare_impl_method(): trait-bound subst");
-                let trait_bound =
-                    trait_bound.subst(tcx, &trait_to_skol_substs);
-                let infcx = infer::new_infer_ctxt(tcx);
-                match infer::mk_sub_trait_refs(&infcx,
-                                               true,
-                                               infer::Misc(impl_m_span),
-                                               trait_bound,
-                                               impl_trait_bound.clone()) {
-                    Ok(_) => {
-                        ok = true;
-                        break
-                    }
-                    Err(_) => continue,
-                }
-            }
+            // There may be late-bound regions from the impl in the
+            // impl's bound, so "liberate" those. Note that the
+            // trait_to_skol_substs is derived from the impl's
+            // trait-ref, and the late-bound regions appearing there
+            // have already been liberated, so the result should match
+            // up.
+
+            let found_match_in_trait =
+                trait_param_bounds.trait_bounds.iter().any(|trait_bound| {
+                    debug!("compare_impl_method(): trait-bound subst");
+                    let trait_bound =
+                        trait_bound.subst(tcx, &trait_to_skol_substs);
+                    let infcx = infer::new_infer_ctxt(tcx);
+                    infer::mk_sub_trait_refs(&infcx,
+                                             true,
+                                             infer::Misc(impl_m_span),
+                                             trait_bound,
+                                             impl_trait_bound.clone()).is_ok()
+                });
 
-            if !ok {
+            if !found_match_in_trait {
                 span_err!(tcx.sess, impl_m_span, E0052,
                     "in method `{}`, type parameter {} requires bound `{}`, which is not \
                      required by the corresponding type parameter in the trait declaration",
@@ -1132,9 +1200,11 @@ fn compare_impl_method(tcx: &ty::ctxt,
         }
     }
 
-    // Compute skolemized form of impl and trait method tys.
+    // Compute skolemized form of impl and trait method tys. Note
+    // that we must liberate the late-bound regions from the impl.
     let impl_fty = ty::mk_bare_fn(tcx, impl_m.fty.clone());
     let impl_fty = impl_fty.subst(tcx, &impl_to_skol_substs);
+    let impl_fty = liberate_late_bound_regions(tcx, impl_m_body_id, &ty::bind(impl_fty)).value;
     let trait_fty = ty::mk_bare_fn(tcx, trait_m.fty.clone());
     let trait_fty = trait_fty.subst(tcx, &trait_to_skol_substs);
 
@@ -1169,6 +1239,7 @@ fn compare_impl_method(tcx: &ty::ctxt,
     fn check_region_bounds_on_impl_method(tcx: &ty::ctxt,
                                           span: Span,
                                           impl_m: &ty::Method,
+                                          impl_m_body_id: ast::NodeId,
                                           trait_generics: &ty::Generics,
                                           impl_generics: &ty::Generics,
                                           trait_to_skol_substs: &Substs,
@@ -1214,9 +1285,13 @@ fn compare_impl_method(tcx: &ty::ctxt,
 
         debug!("check_region_bounds_on_impl_method: \
                trait_generics={} \
-               impl_generics={}",
+               impl_generics={} \
+               trait_to_skol_substs={} \
+               impl_to_skol_substs={}",
                trait_generics.repr(tcx),
-               impl_generics.repr(tcx));
+               impl_generics.repr(tcx),
+               trait_to_skol_substs.repr(tcx),
+               impl_to_skol_substs.repr(tcx));
 
         // Must have same number of early-bound lifetime parameters.
         // Unfortunately, if the user screws up the bounds, then this
@@ -1247,6 +1322,18 @@ fn compare_impl_method(tcx: &ty::ctxt,
             let impl_bounds =
                 impl_param.bounds.subst(tcx, impl_to_skol_substs);
 
+            // The bounds may reference late-bound regions from the
+            // impl declaration. In that case, we want to replace
+            // those with the liberated variety so as to match the
+            // versions appearing in the `trait_to_skol_substs`.
+            // There are two-levels of binder to be aware of: the
+            // impl, and the method.
+            let impl_bounds =
+                ty::liberate_late_bound_regions(
+                    tcx,
+                    impl_m_body_id,
+                    &ty::bind(ty::bind(impl_bounds))).value.value;
+
             debug!("check_region_bounds_on_impl_method: \
                    trait_param={} \
                    impl_param={} \
@@ -1601,15 +1688,6 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
         }
     }
 
-    pub fn write_ty_substs(&self,
-                           node_id: ast::NodeId,
-                           ty: ty::t,
-                           substs: ty::ItemSubsts) {
-        let ty = ty.subst(self.tcx(), &substs.substs);
-        self.write_ty(node_id, ty);
-        self.write_substs(node_id, substs);
-    }
-
     pub fn write_autoderef_adjustment(&self,
                                       node_id: ast::NodeId,
                                       span: Span,
@@ -1707,17 +1785,21 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
         }
     }
 
-    pub fn instantiate_item_type(&self,
-                                 span: Span,
-                                 def_id: ast::DefId)
-                                 -> TypeAndSubsts
+    pub fn instantiate_type(&self,
+                            span: Span,
+                            def_id: ast::DefId)
+                            -> TypeAndSubsts
     {
         /*!
          * Returns the type of `def_id` with all generics replaced by
          * by fresh type/region variables. Also returns the
          * substitution from the type parameters on `def_id` to the
-         * fresh variables.  Registers any trait obligations specified
+         * fresh variables. Registers any trait obligations specified
          * on `def_id` at the same time.
+         *
+         * Note that function is only intended to be used with types
+         * (notably, not impls). This is because it doesn't do any
+         * instantiation of late-bound regions.
          */
 
         let polytype =
@@ -1726,12 +1808,14 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
             self.infcx().fresh_substs_for_generics(
                 span,
                 &polytype.generics);
+        let bounds =
+            polytype.generics.to_bounds(self.tcx(), &substs);
         self.add_obligations_for_parameters(
             traits::ObligationCause::new(
                 span,
                 traits::ItemObligation(def_id)),
             &substs,
-            &polytype.generics);
+            &bounds);
         let monotype =
             polytype.ty.subst(self.tcx(), &substs);
 
@@ -1956,8 +2040,8 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
 
         let mut region_obligations = self.inh.region_obligations.borrow_mut();
         let region_obligation = RegionObligation { sub_region: r,
-                                  sup_type: ty,
-                                  origin: origin };
+                                                   sup_type: ty,
+                                                   origin: origin };
 
         match region_obligations.entry(self.body_id) {
             Vacant(entry) => { entry.set(vec![region_obligation]); },
@@ -1968,12 +2052,13 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     pub fn add_obligations_for_parameters(&self,
                                           cause: traits::ObligationCause,
                                           substs: &Substs,
-                                          generics: &ty::Generics)
+                                          generic_bounds: &ty::GenericBounds)
     {
         /*!
-         * Given a set of generic parameter definitions (`generics`)
-         * and the values provided for each of them (`substs`),
-         * creates and registers suitable region obligations.
+         * Given a fully substituted set of bounds (`generic_bounds`),
+         * and the values with which each type/region parameter was
+         * instantiated (`substs`), creates and registers suitable
+         * trait/region obligations.
          *
          * For example, if there is a function:
          *
@@ -1989,60 +2074,60 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
          * locally.
          */
 
-        debug!("add_obligations_for_parameters(substs={}, generics={})",
+        assert!(!generic_bounds.has_escaping_regions());
+
+        debug!("add_obligations_for_parameters(substs={}, generic_bounds={})",
                substs.repr(self.tcx()),
-               generics.repr(self.tcx()));
+               generic_bounds.repr(self.tcx()));
 
-        self.add_trait_obligations_for_generics(cause, substs, generics);
-        self.add_region_obligations_for_generics(cause, substs, generics);
+        self.add_trait_obligations_for_generics(cause, substs, generic_bounds);
+        self.add_region_obligations_for_generics(cause, substs, generic_bounds);
     }
 
     fn add_trait_obligations_for_generics(&self,
                                           cause: traits::ObligationCause,
                                           substs: &Substs,
-                                          generics: &ty::Generics) {
+                                          generic_bounds: &ty::GenericBounds) {
+        assert!(!generic_bounds.has_escaping_regions());
+        assert!(!substs.has_regions_escaping_depth(0));
+
         let obligations =
             traits::obligations_for_generics(self.tcx(),
                                              cause,
-                                             generics,
-                                             substs);
+                                             generic_bounds,
+                                             &substs.types);
         obligations.map_move(|o| self.register_obligation(o));
     }
 
     fn add_region_obligations_for_generics(&self,
                                            cause: traits::ObligationCause,
                                            substs: &Substs,
-                                           generics: &ty::Generics)
+                                           generic_bounds: &ty::GenericBounds)
     {
-        assert_eq!(generics.types.iter().len(),
-                   substs.types.iter().len());
-        for (type_def, &type_param) in
-            generics.types.iter().zip(
+        assert!(!generic_bounds.has_escaping_regions());
+        assert_eq!(generic_bounds.types.iter().len(), substs.types.iter().len());
+
+        for (type_bounds, &type_param) in
+            generic_bounds.types.iter().zip(
                 substs.types.iter())
         {
-            let param_ty = ty::ParamTy { space: type_def.space,
-                                         idx: type_def.index,
-                                         def_id: type_def.def_id };
-            let bounds = type_def.bounds.subst(self.tcx(), substs);
             self.add_region_obligations_for_type_parameter(
-                cause.span, param_ty, &bounds, type_param);
+                cause.span, type_bounds, type_param);
         }
 
-        assert_eq!(generics.regions.iter().len(),
+        assert_eq!(generic_bounds.regions.iter().len(),
                    substs.regions().iter().len());
-        for (region_def, &region_param) in
-            generics.regions.iter().zip(
+        for (region_bounds, &region_param) in
+            generic_bounds.regions.iter().zip(
                 substs.regions().iter())
         {
-            let bounds = region_def.bounds.subst(self.tcx(), substs);
             self.add_region_obligations_for_region_parameter(
-                cause.span, bounds.as_slice(), region_param);
+                cause.span, region_bounds.as_slice(), region_param);
         }
     }
 
     fn add_region_obligations_for_type_parameter(&self,
                                                  span: Span,
-                                                 param_ty: ty::ParamTy,
                                                  param_bound: &ty::ParamBounds,
                                                  ty: ty::t)
     {
@@ -2054,7 +2139,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                 param_bound.builtin_bounds,
                 param_bound.trait_bounds.as_slice());
         for &r in region_bounds.iter() {
-            let origin = infer::RelateParamBound(span, param_ty, ty);
+            let origin = infer::RelateParamBound(span, ty);
             self.register_region_obligation(origin, ty, r);
         }
     }
@@ -3816,7 +3901,7 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
         let TypeAndSubsts {
             ty: mut struct_type,
             substs: struct_substs
-        } = fcx.instantiate_item_type(span, class_id);
+        } = fcx.instantiate_type(span, class_id);
 
         // Look up and check the fields.
         let class_fields = ty::lookup_struct_fields(tcx, class_id);
@@ -3858,7 +3943,7 @@ fn check_expr_with_unifier(fcx: &FnCtxt,
         let TypeAndSubsts {
             ty: enum_type,
             substs: substitutions
-        } = fcx.instantiate_item_type(span, enum_id);
+        } = fcx.instantiate_type(span, enum_id);
 
         // Look up and check the enum variant fields.
         let variant_fields = ty::lookup_struct_fields(tcx, variant_id);
@@ -5336,14 +5421,39 @@ pub fn instantiate_path(fcx: &FnCtxt,
         assert_eq!(substs.regions().len(space), region_defs.len(space));
     }
 
+    // The things we are substituting into the type should not contain
+    // escaping late-bound regions.
+    assert!(!substs.has_regions_escaping_depth(0));
+
+    // In the case of static items taken from impls, there may be
+    // late-bound regions associated with the impl (not declared on
+    // the fn itself). Those should be replaced with fresh variables
+    // now. These can appear either on the type being referenced, or
+    // on the associated bounds.
+    let bounds = polytype.generics.to_bounds(fcx.tcx(), &substs);
+    let (ty_late_bound, bounds) =
+        fcx.infcx().replace_late_bound_regions_with_fresh_var(
+            span,
+            infer::FnCall,
+            &ty::bind((polytype.ty, bounds))).0.value;
+
+    debug!("after late-bounds have been replaced: ty_late_bound={}", ty_late_bound.repr(fcx.tcx()));
+    debug!("after late-bounds have been replaced: bounds={}", bounds.repr(fcx.tcx()));
+
     fcx.add_obligations_for_parameters(
         traits::ObligationCause::new(span, traits::ItemObligation(def.def_id())),
         &substs,
-        &polytype.generics);
+        &bounds);
 
-    fcx.write_ty_substs(node_id, polytype.ty, ty::ItemSubsts {
-        substs: substs,
-    });
+    // Substitute the values for the type parameters into the type of
+    // the referenced item.
+    let ty_substituted = ty_late_bound.subst(fcx.tcx(), &substs);
+
+    debug!("ty_substituted: ty_substituted={}", ty_substituted.repr(fcx.tcx()));
+
+    fcx.write_ty(node_id, ty_substituted);
+    fcx.write_substs(node_id, ty::ItemSubsts { substs: substs });
+    return;
 
     fn report_error_if_segment_contains_type_parameters(
         fcx: &FnCtxt,
@@ -5736,7 +5846,8 @@ pub fn check_intrinsic_type(ccx: &CrateCtxt, it: &ast::ForeignItem) {
             "move_val_init" => {
                 (1u,
                  vec!(
-                    ty::mk_mut_rptr(tcx, ty::ReLateBound(it.id, ty::BrAnon(0)), param(ccx, 0)),
+                    ty::mk_mut_rptr(tcx, ty::ReLateBound(ty::DebruijnIndex::new(1), ty::BrAnon(0)),
+                                    param(ccx, 0)),
                     param(ccx, 0u)
                   ),
                ty::mk_nil(tcx))
diff --git a/src/librustc/middle/typeck/check/vtable.rs b/src/librustc/middle/typeck/check/vtable.rs
index 498594716e7..041d21a8baf 100644
--- a/src/librustc/middle/typeck/check/vtable.rs
+++ b/src/librustc/middle/typeck/check/vtable.rs
@@ -300,14 +300,14 @@ pub fn select_all_fcx_obligations_or_error(fcx: &FnCtxt) {
 }
 
 fn resolve_trait_ref(fcx: &FnCtxt, obligation: &Obligation)
-                     -> (ty::TraitRef, ty::t)
+                     -> (Rc<ty::TraitRef>, ty::t)
 {
     let trait_ref =
         fcx.infcx().resolve_type_vars_in_trait_ref_if_possible(
             &*obligation.trait_ref);
     let self_ty =
         trait_ref.substs.self_ty().unwrap();
-    (trait_ref, self_ty)
+    (Rc::new(trait_ref), self_ty)
 }
 
 pub fn report_fulfillment_errors(fcx: &FnCtxt,
diff --git a/src/librustc/middle/typeck/check/wf.rs b/src/librustc/middle/typeck/check/wf.rs
index 254f46f8466..8e02f9f7bfd 100644
--- a/src/librustc/middle/typeck/check/wf.rs
+++ b/src/librustc/middle/typeck/check/wf.rs
@@ -12,10 +12,10 @@ use middle::subst;
 use middle::subst::{Subst};
 use middle::traits;
 use middle::ty;
+use middle::ty::liberate_late_bound_regions;
 use middle::ty_fold::{TypeFolder, TypeFoldable};
 use middle::typeck::astconv::AstConv;
 use middle::typeck::check::{FnCtxt, Inherited, blank_fn_ctxt, vtable, regionck};
-use middle::typeck::check::regionmanip::replace_late_bound_regions;
 use middle::typeck::CrateCtxt;
 use util::ppaux::Repr;
 
@@ -166,16 +166,24 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
             let mut bounds_checker = BoundsChecker::new(fcx, item.span,
                                                         item.id, Some(&mut this.cache));
 
+            // Find the impl self type as seen from the "inside" --
+            // that is, with all type parameters converted from bound
+            // to free, and any late-bound regions on the impl
+            // liberated.
             let self_ty = ty::node_id_to_type(fcx.tcx(), item.id);
             let self_ty = self_ty.subst(fcx.tcx(), &fcx.inh.param_env.free_substs);
+            let self_ty = liberate_late_bound_regions(fcx.tcx(), item.id, &ty::bind(self_ty)).value;
 
             bounds_checker.check_traits_in_ty(self_ty);
 
+            // Similarly, obtain an "inside" reference to the trait
+            // that the impl implements.
             let trait_ref = match ty::impl_trait_ref(fcx.tcx(), local_def(item.id)) {
                 None => { return; }
                 Some(t) => { t }
             };
             let trait_ref = (*trait_ref).subst(fcx.tcx(), &fcx.inh.param_env.free_substs);
+            let trait_ref = liberate_late_bound_regions(fcx.tcx(), item.id, &trait_ref);
 
             // There are special rules that apply to drop.
             if
@@ -215,7 +223,6 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
             // FIXME -- This is a bit ill-factored. There is very similar
             // code in traits::util::obligations_for_generics.
             fcx.add_region_obligations_for_type_parameter(item.span,
-                                                          ty::ParamTy::for_self(trait_ref.def_id),
                                                           &trait_def.bounds,
                                                           trait_ref.self_ty());
             for builtin_bound in trait_def.bounds.builtin_bounds.iter() {
@@ -280,12 +287,13 @@ impl<'cx,'tcx> BoundsChecker<'cx,'tcx> {
 
         let trait_def = ty::lookup_trait_def(self.fcx.tcx(), trait_ref.def_id);
 
+        let bounds = trait_def.generics.to_bounds(self.tcx(), &trait_ref.substs);
         self.fcx.add_obligations_for_parameters(
             traits::ObligationCause::new(
                 self.span,
                 traits::ItemObligation(trait_ref.def_id)),
             &trait_ref.substs,
-            &trait_def.generics);
+            &bounds);
 
         for &ty in trait_ref.substs.types.iter() {
             self.check_traits_in_ty(ty);
@@ -335,7 +343,7 @@ impl<'cx,'tcx> TypeFolder<'tcx> for BoundsChecker<'cx,'tcx> {
                         traits::ObligationCause::new(self.span,
                                                      traits::ItemObligation(type_id)),
                         substs,
-                        &polytype.generics);
+                        &polytype.generics.to_bounds(self.tcx(), substs));
                 } else {
                     // There are two circumstances in which we ignore
                     // region obligations.
@@ -363,7 +371,7 @@ impl<'cx,'tcx> TypeFolder<'tcx> for BoundsChecker<'cx,'tcx> {
                         traits::ObligationCause::new(self.span,
                                                      traits::ItemObligation(type_id)),
                         substs,
-                        &polytype.generics);
+                        &polytype.generics.to_bounds(self.tcx(), substs));
                 }
 
                 self.fold_substs(substs);
diff --git a/src/librustc/middle/typeck/collect.rs b/src/librustc/middle/typeck/collect.rs
index 55ed6720dba..a0b198a59c2 100644
--- a/src/librustc/middle/typeck/collect.rs
+++ b/src/librustc/middle/typeck/collect.rs
@@ -1112,10 +1112,12 @@ pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
             for impl_item in impl_items.iter() {
                 match *impl_item {
                     ast::MethodImplItem(ref method) => {
+                        let body_id = method.pe_body().id;
                         check_method_self_type(ccx,
-                                               &BindingRscope::new(method.id),
+                                               &BindingRscope::new(),
                                                selfty,
-                                               method.pe_explicit_self());
+                                               method.pe_explicit_self(),
+                                               body_id);
                         methods.push(&**method);
                     }
                     ast::TypeImplItem(ref typedef) => {
@@ -1170,17 +1172,19 @@ pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
                                              local_def(it.id));
                 match *trait_method {
                     ast::RequiredMethod(ref type_method) => {
-                        let rscope = BindingRscope::new(type_method.id);
+                        let rscope = BindingRscope::new();
                         check_method_self_type(ccx,
                                                &rscope,
                                                self_type,
-                                               &type_method.explicit_self)
+                                               &type_method.explicit_self,
+                                               it.id)
                     }
                     ast::ProvidedMethod(ref method) => {
                         check_method_self_type(ccx,
-                                               &BindingRscope::new(method.id),
+                                               &BindingRscope::new(),
                                                self_type,
-                                               method.pe_explicit_self())
+                                               method.pe_explicit_self(),
+                                               it.id)
                     }
                     ast::TypeTraitItem(ref associated_type) => {
                         convert_associated_type(ccx,
@@ -2132,10 +2136,12 @@ pub fn mk_item_substs(ccx: &CrateCtxt,
 /// Verifies that the explicit self type of a method matches the impl or
 /// trait.
 fn check_method_self_type<RS:RegionScope>(
-                          crate_context: &CrateCtxt,
-                          rs: &RS,
-                          required_type: ty::t,
-                          explicit_self: &ast::ExplicitSelf) {
+    crate_context: &CrateCtxt,
+    rs: &RS,
+    required_type: ty::t,
+    explicit_self: &ast::ExplicitSelf,
+    body_id: ast::NodeId)
+{
     match explicit_self.node {
         ast::SelfExplicit(ref ast_type, _) => {
             let typ = crate_context.to_ty(rs, &**ast_type);
@@ -2144,13 +2150,44 @@ fn check_method_self_type<RS:RegionScope>(
                 ty::ty_uniq(typ) => typ,
                 _ => typ,
             };
+
+            // "Required type" comes from the trait definition. It may
+            // contain late-bound regions from the method, but not the
+            // trait (since traits only have early-bound region
+            // parameters).
+            assert!(!ty::type_escapes_depth(required_type, 1));
+            let required_type_free =
+                ty::liberate_late_bound_regions(
+                    crate_context.tcx,
+                    body_id,
+                    &ty::bind(required_type)).value;
+
+            // The "base type" comes from the impl. It may have late-bound
+            // regions from the impl or the method.
+            let base_type_free = // liberate impl regions:
+                ty::liberate_late_bound_regions(
+                    crate_context.tcx,
+                    body_id,
+                    &ty::bind(ty::bind(base_type))).value.value;
+            let base_type_free = // liberate method regions:
+                ty::liberate_late_bound_regions(
+                    crate_context.tcx,
+                    body_id,
+                    &ty::bind(base_type_free)).value;
+
+            debug!("required_type={} required_type_free={} \
+                    base_type={} base_type_free={}",
+                   required_type.repr(crate_context.tcx),
+                   required_type_free.repr(crate_context.tcx),
+                   base_type.repr(crate_context.tcx),
+                   base_type_free.repr(crate_context.tcx));
             let infcx = infer::new_infer_ctxt(crate_context.tcx);
             drop(typeck::require_same_types(crate_context.tcx,
                                             Some(&infcx),
                                             false,
                                             explicit_self.span,
-                                            base_type,
-                                            required_type,
+                                            base_type_free,
+                                            required_type_free,
                                             || {
                 format!("mismatched self type: expected `{}`",
                         ppaux::ty_to_string(crate_context.tcx, required_type))
diff --git a/src/librustc/middle/typeck/infer/error_reporting.rs b/src/librustc/middle/typeck/infer/error_reporting.rs
index 6012fa43eb5..65bd21b14e0 100644
--- a/src/librustc/middle/typeck/infer/error_reporting.rs
+++ b/src/librustc/middle/typeck/infer/error_reporting.rs
@@ -650,14 +650,12 @@ impl<'a, 'tcx> ErrorReporting for InferCtxt<'a, 'tcx> {
                     sup,
                     "");
             }
-            infer::RelateParamBound(span, param_ty, ty) => {
+            infer::RelateParamBound(span, ty) => {
                 self.tcx.sess.span_err(
                     span,
-                    format!("the type `{}` (provided as the value of \
-                             the parameter `{}`) does not fulfill the \
+                    format!("the type `{}` does not fulfill the \
                              required lifetime",
-                            self.ty_to_string(ty),
-                            param_ty.user_string(self.tcx)).as_slice());
+                            self.ty_to_string(ty)).as_slice());
                 note_and_explain_region(self.tcx,
                                         "type must outlive ",
                                         sub,
@@ -1651,13 +1649,11 @@ impl<'a, 'tcx> ErrorReportingHelpers for InferCtxt<'a, 'tcx> {
                              does not outlive the data it points at",
                             self.ty_to_string(ty)).as_slice());
             }
-            infer::RelateParamBound(span, param_ty, t) => {
+            infer::RelateParamBound(span, t) => {
                 self.tcx.sess.span_note(
                     span,
-                    format!("...so that the parameter `{}`, \
-                             when instantiated with `{}`, \
-                             will meet its declared lifetime bounds.",
-                            param_ty.user_string(self.tcx),
+                    format!("...so that the type `{}` \
+                             will meet the declared lifetime bounds.",
                             self.ty_to_string(t)).as_slice());
             }
             infer::RelateDefaultParamBound(span, t) => {
diff --git a/src/librustc/middle/typeck/infer/mod.rs b/src/librustc/middle/typeck/infer/mod.rs
index b4689ae098c..e69bd215766 100644
--- a/src/librustc/middle/typeck/infer/mod.rs
+++ b/src/librustc/middle/typeck/infer/mod.rs
@@ -184,9 +184,9 @@ pub enum SubregionOrigin {
     // type of the variable outlives the lifetime bound.
     RelateProcBound(Span, ast::NodeId, ty::t),
 
-    // The given type parameter was instantiated with the given type,
+    // Some type parameter was instantiated with the given type,
     // and that type must outlive some region.
-    RelateParamBound(Span, ty::ParamTy, ty::t),
+    RelateParamBound(Span, ty::t),
 
     // The given region parameter was instantiated with a region
     // that must outlive some other region.
@@ -1062,7 +1062,7 @@ impl SubregionOrigin {
             IndexSlice(a) => a,
             RelateObjectBound(a) => a,
             RelateProcBound(a, _, _) => a,
-            RelateParamBound(a, _, _) => a,
+            RelateParamBound(a, _) => a,
             RelateRegionParamBound(a) => a,
             RelateDefaultParamBound(a, _) => a,
             Reborrow(a) => a,
@@ -1112,11 +1112,10 @@ impl Repr for SubregionOrigin {
                         b,
                         c.repr(tcx))
             }
-            RelateParamBound(a, b, c) => {
-                format!("RelateParamBound({},{},{})",
+            RelateParamBound(a, b) => {
+                format!("RelateParamBound({},{})",
                         a.repr(tcx),
-                        b.repr(tcx),
-                        c.repr(tcx))
+                        b.repr(tcx))
             }
             RelateRegionParamBound(a) => {
                 format!("RelateRegionParamBound({})",
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index ec8b49c108c..4ce783b37b7 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -731,6 +731,9 @@ impl Repr for ty::ParamBounds {
 
 impl Repr for ty::TraitRef {
     fn repr(&self, tcx: &ctxt) -> String {
+        // when printing out the debug representation, we don't need
+        // to enumerate the `for<...>` etc because the debruijn index
+        // tells you everything you need to know.
         let base = ty::item_path_str(tcx, self.def_id);
         let trait_def = ty::lookup_trait_def(tcx, self.def_id);
         format!("<{} : {}>",
@@ -921,6 +924,14 @@ impl Repr for ty::Generics {
     }
 }
 
+impl Repr for ty::GenericBounds {
+    fn repr(&self, tcx: &ctxt) -> String {
+        format!("GenericBounds(types: {}, regions: {})",
+                self.types.repr(tcx),
+                self.regions.repr(tcx))
+    }
+}
+
 impl Repr for ty::ItemVariances {
     fn repr(&self, tcx: &ctxt) -> String {
         format!("ItemVariances(types={}, \
@@ -1139,9 +1150,41 @@ impl UserString for ty::BuiltinBounds {
 
 impl UserString for ty::TraitRef {
     fn user_string(&self, tcx: &ctxt) -> String {
-        let base = ty::item_path_str(tcx, self.def_id);
+        // Replace any anonymous late-bound regions with named
+        // variants, using gensym'd identifiers, so that we can
+        // clearly differentiate between named and unnamed regions in
+        // the output. We'll probably want to tweak this over time to
+        // decide just how much information to give.
+        let mut names = Vec::new();
+        let (trait_ref, _) = ty::replace_late_bound_regions(tcx, self, |br, debruijn| {
+            ty::ReLateBound(debruijn, match br {
+                ty::BrNamed(_, name) => {
+                    names.push(token::get_name(name));
+                    br
+                }
+                ty::BrAnon(_) |
+                ty::BrFresh(_) |
+                ty::BrEnv => {
+                    let name = token::gensym("r");
+                    names.push(token::get_name(name));
+                    ty::BrNamed(ast_util::local_def(ast::DUMMY_NODE_ID), name)
+                }
+            })
+        });
+        let names: Vec<_> = names.iter().map(|s| s.get()).collect();
+
+        // Let the base string be either `SomeTrait` for `for<'a,'b> SomeTrait`,
+        // depending on whether there are bound regions.
+        let path_str = ty::item_path_str(tcx, self.def_id);
+        let base =
+            if names.is_empty() {
+                path_str
+            } else {
+                format!("for<{}> {}", names.connect(","), path_str)
+            };
+
         let trait_def = ty::lookup_trait_def(tcx, self.def_id);
-        parameterized(tcx, base.as_slice(), &self.substs, &trait_def.generics)
+        parameterized(tcx, base.as_slice(), &trait_ref.substs, &trait_def.generics)
     }
 }
 
diff --git a/src/librustc_trans/trans/callee.rs b/src/librustc_trans/trans/callee.rs
index cbd0d756f08..de49754fe7f 100644
--- a/src/librustc_trans/trans/callee.rs
+++ b/src/librustc_trans/trans/callee.rs
@@ -467,9 +467,8 @@ pub fn trans_fn_ref_with_substs(
             let impl_or_trait_item = ty::impl_or_trait_item(tcx, source_id);
             match impl_or_trait_item {
                 ty::MethodTraitItem(method) => {
-                    let trait_ref = ty::impl_trait_ref(tcx, impl_id)
-                        .expect("could not find trait_ref for impl with \
-                                 default methods");
+                    let trait_ref = ty::impl_trait_ref(tcx, impl_id).unwrap();
+                    let trait_ref = ty::erase_late_bound_regions(tcx, &trait_ref);
 
                     // Compute the first substitution
                     let first_subst =