Add proper support for early/late distinction for lifetime bindings.

Uses newly added Vec::partition method to simplify resolve_lifetime.

20 files changed, 566 insertions, 200 deletions

diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs
index 6a55b05b77e..88eaf256be8 100644
--- a/src/librustc/middle/resolve_lifetime.rs
+++ b/src/librustc/middle/resolve_lifetime.rs
@@ -23,6 +23,8 @@ use std::vec_ng::Vec;
 use util::nodemap::NodeMap;
 use syntax::ast;
 use syntax::codemap::Span;
+use syntax::opt_vec;
+use syntax::opt_vec::OptVec;
 use syntax::parse::token::special_idents;
 use syntax::parse::token;
 use syntax::print::pprust::{lifetime_to_str};
@@ -33,14 +35,25 @@ use syntax::visit::Visitor;
 // that it corresponds to
 pub type NamedRegionMap = NodeMap<ast::DefRegion>;
 
+// Returns an instance of some type that implements std::fmt::Show
+fn lifetime_show(lt_name: &ast::Name) -> token::InternedString {
+    token::get_name(*lt_name)
+}
+
 struct LifetimeContext {
     sess: session::Session,
     named_region_map: @RefCell<NamedRegionMap>,
 }
 
 enum ScopeChain<'a> {
-    ItemScope(&'a Vec<ast::Lifetime>),
-    FnScope(ast::NodeId, &'a Vec<ast::Lifetime>, Scope<'a>),
+    /// EarlyScope(i, ['a, 'b, ...], s) extends s with early-bound
+    /// lifetimes, assigning indexes 'a => i, 'b => i+1, ... etc.
+    EarlyScope(uint, &'a Vec<ast::Lifetime>, Scope<'a>),
+    /// LateScope(binder_id, ['a, 'b, ...], s) extends s with late-bound
+    /// lifetimes introduced by the declaration binder_id.
+    LateScope(ast::NodeId, &'a Vec<ast::Lifetime>, Scope<'a>),
+    /// lifetimes introduced by items within a code block are scoped
+    /// to that block.
     BlockScope(ast::NodeId, Scope<'a>),
     RootScope
 }
@@ -62,6 +75,7 @@ impl<'a> Visitor<Scope<'a>> for LifetimeContext {
     fn visit_item(&mut self,
                   item: &ast::Item,
                   _: Scope<'a>) {
+        let root = RootScope;
         let scope = match item.node {
             ast::ItemFn(..) | // fn lifetimes get added in visit_fn below
             ast::ItemMod(..) |
@@ -76,7 +90,7 @@ impl<'a> Visitor<Scope<'a>> for LifetimeContext {
             ast::ItemImpl(ref generics, _, _, _) |
             ast::ItemTrait(ref generics, _, _) => {
                 self.check_lifetime_names(&generics.lifetimes);
-                ItemScope(&generics.lifetimes)
+                EarlyScope(0, &generics.lifetimes, &root)
             }
         };
         debug!("entering scope {:?}", scope);
@@ -90,49 +104,41 @@ impl<'a> Visitor<Scope<'a>> for LifetimeContext {
         match *fk {
             visit::FkItemFn(_, generics, _, _) |
             visit::FkMethod(_, generics, _) => {
-                let scope1 = FnScope(n, &generics.lifetimes, scope);
-                self.check_lifetime_names(&generics.lifetimes);
-                debug!("pushing fn scope id={} due to item/method", n);
-                visit::walk_fn(self, fk, fd, b, s, n, &scope1);
-                debug!("popping fn scope id={} due to item/method", n);
+                self.visit_fn_decl(
+                    n, generics, scope,
+                    |this, scope1| visit::walk_fn(this, fk, fd, b, s, n, scope1))
             }
             visit::FkFnBlock(..) => {
-                visit::walk_fn(self, fk, fd, b, s, n, scope);
+                visit::walk_fn(self, fk, fd, b, s, n, scope)
             }
         }
     }
 
-    fn visit_ty(&mut self, ty: &ast::Ty,
-                scope: Scope<'a>) {
+    fn visit_ty(&mut self, ty: &ast::Ty, scope: Scope<'a>) {
         match ty.node {
-            ast::TyClosure(closure) => {
-                let scope1 = FnScope(ty.id, &closure.lifetimes, scope);
-                self.check_lifetime_names(&closure.lifetimes);
-                debug!("pushing fn scope id={} due to type", ty.id);
-                visit::walk_ty(self, ty, &scope1);
-                debug!("popping fn scope id={} due to type", ty.id);
-            }
-            ast::TyBareFn(bare_fn) => {
-                let scope1 = FnScope(ty.id, &bare_fn.lifetimes, scope);
-                self.check_lifetime_names(&bare_fn.lifetimes);
-                debug!("pushing fn scope id={} due to type", ty.id);
-                visit::walk_ty(self, ty, &scope1);
-                debug!("popping fn scope id={} due to type", ty.id);
-            }
-            _ => {
-                visit::walk_ty(self, ty, scope);
-            }
+            ast::TyClosure(c) => push_fn_scope(self, ty, scope, &c.lifetimes),
+            ast::TyBareFn(c) => push_fn_scope(self, ty, scope, &c.lifetimes),
+            _ => visit::walk_ty(self, ty, scope),
+        }
+
+        fn push_fn_scope(this: &mut LifetimeContext,
+                         ty: &ast::Ty,
+                         scope: Scope,
+                         lifetimes: &Vec<ast::Lifetime>) {
+            let scope1 = LateScope(ty.id, lifetimes, scope);
+            this.check_lifetime_names(lifetimes);
+            debug!("pushing fn scope id={} due to type", ty.id);
+            visit::walk_ty(this, ty, &scope1);
+            debug!("popping fn scope id={} due to type", ty.id);
         }
     }
 
     fn visit_ty_method(&mut self,
                        m: &ast::TypeMethod,
                        scope: Scope<'a>) {
-        let scope1 = FnScope(m.id, &m.generics.lifetimes, scope);
-        self.check_lifetime_names(&m.generics.lifetimes);
-        debug!("pushing fn scope id={} due to ty_method", m.id);
-        visit::walk_ty_method(self, m, &scope1);
-        debug!("popping fn scope id={} due to ty_method", m.id);
+        self.visit_fn_decl(
+            m.id, &m.generics, scope,
+            |this, scope1| visit::walk_ty_method(this, m, scope1))
     }
 
     fn visit_block(&mut self,
@@ -155,7 +161,82 @@ impl<'a> Visitor<Scope<'a>> for LifetimeContext {
     }
 }
 
+impl<'a> ScopeChain<'a> {
+    fn count_early_params(&self) -> uint {
+        /*!
+         * Counts the number of early-bound parameters that are in
+         * scope.  Used when checking methods: the early-bound
+         * lifetime parameters declared on the method are assigned
+         * indices that come after the indices from the type.  Given
+         * something like `impl<'a> Foo { ... fn bar<'b>(...) }`
+         * then `'a` gets index 0 and `'b` gets index 1.
+         */
+
+        match *self {
+            RootScope => 0,
+            EarlyScope(base, lifetimes, _) => base + lifetimes.len(),
+            LateScope(_, _, s) => s.count_early_params(),
+            BlockScope(_, _) => 0,
+        }
+    }
+}
+
 impl LifetimeContext {
+    /// Visits self by adding a scope and handling recursive walk over the contents with `walk`.
+    fn visit_fn_decl(&mut self,
+                     n: ast::NodeId,
+                     generics: &ast::Generics,
+                     scope: Scope,
+                     walk: |&mut LifetimeContext, Scope|) {
+        /*!
+         * Handles visiting fns and methods. These are a bit
+         * complicated because we must distinguish early- vs late-bound
+         * lifetime parameters. We do this by checking which lifetimes
+         * appear within type bounds; those are early bound lifetimes,
+         * and the rest are late bound.
+         *
+         * For example:
+         *
+         *    fn foo<'a,'b,'c,T:Trait<'b>>(...)
+         *
+         * Here `'a` and `'c` are late bound but `'b` is early
+         * bound. Note that early- and late-bound lifetimes may be
+         * interspersed together.
+         *
+         * If early bound lifetimes are present, we separate them into
+         * their own list (and likewise for late bound). They will be
+         * numbered sequentially, starting from the lowest index that
+         * is already in scope (for a fn item, that will be 0, but for
+         * a method it might not be). Late bound lifetimes are
+         * resolved by name and associated with a binder id (`n`), so
+         * the ordering is not important there.
+         */
+
+        self.check_lifetime_names(&generics.lifetimes);
+
+        let early_count = scope.count_early_params();
+        let referenced_idents = free_lifetimes(&generics.ty_params);
+        debug!("pushing fn scope id={} due to fn item/method\
+               referenced_idents={:?} \
+               early_count={}",
+               n,
+               referenced_idents.map(lifetime_show),
+               early_count);
+        if referenced_idents.is_empty() {
+            let scope1 = LateScope(n, &generics.lifetimes, scope);
+            walk(self, &scope1)
+        } else {
+            let (early, late) = generics.lifetimes.clone().partition(
+                |l| referenced_idents.iter().any(|&i| i == l.name));
+
+            let scope1 = EarlyScope(early_count, &early, scope);
+            let scope2 = LateScope(n, &late, &scope1);
+
+            walk(self, &scope2);
+        }
+        debug!("popping fn scope id={} due to fn item/method", n);
+    }
+
     fn resolve_lifetime_ref(&self,
                             lifetime_ref: &ast::Lifetime,
                             scope: Scope) {
@@ -177,23 +258,25 @@ impl LifetimeContext {
                     break;
                 }
 
-                ItemScope(lifetimes) => {
+                EarlyScope(base, lifetimes, s) => {
                     match search_lifetimes(lifetimes, lifetime_ref) {
-                        Some((index, decl_id)) => {
+                        Some((offset, decl_id)) => {
+                            let index = base + offset;
                             let def = ast::DefEarlyBoundRegion(index, decl_id);
                             self.insert_lifetime(lifetime_ref, def);
                             return;
                         }
                         None => {
-                            break;
+                            depth += 1;
+                            scope = s;
                         }
                     }
                 }
 
-                FnScope(id, lifetimes, s) => {
+                LateScope(binder_id, lifetimes, s) => {
                     match search_lifetimes(lifetimes, lifetime_ref) {
                         Some((_index, decl_id)) => {
-                            let def = ast::DefLateBoundRegion(id, depth, decl_id);
+                            let def = ast::DefLateBoundRegion(binder_id, depth, decl_id);
                             self.insert_lifetime(lifetime_ref, def);
                             return;
                         }
@@ -231,12 +314,8 @@ impl LifetimeContext {
                     break;
                 }
 
-                ItemScope(lifetimes) => {
-                    search_result = search_lifetimes(lifetimes, lifetime_ref);
-                    break;
-                }
-
-                FnScope(_, lifetimes, s) => {
+                EarlyScope(_, lifetimes, s) |
+                LateScope(_, lifetimes, s) => {
                     search_result = search_lifetimes(lifetimes, lifetime_ref);
                     if search_result.is_some() {
                         break;
@@ -323,3 +402,44 @@ fn search_lifetimes(lifetimes: &Vec<ast::Lifetime>,
     }
     return None;
 }
+
+///////////////////////////////////////////////////////////////////////////
+
+pub fn early_bound_lifetimes<'a>(generics: &'a ast::Generics) -> Vec<ast::Lifetime> {
+    let referenced_idents = free_lifetimes(&generics.ty_params);
+    if referenced_idents.is_empty() {
+        return Vec::new();
+    }
+
+    generics.lifetimes.iter()
+        .filter(|l| referenced_idents.iter().any(|&i| i == l.name))
+        .map(|l| *l)
+        .collect()
+}
+
+pub fn free_lifetimes(ty_params: &OptVec<ast::TyParam>) -> OptVec<ast::Name> {
+    /*!
+     * Gathers up and returns the names of any lifetimes that appear
+     * free in `ty_params`. Of course, right now, all lifetimes appear
+     * free, since we don't currently have any binders in type parameter
+     * declarations; just being forwards compatible with future extensions.
+     */
+
+    let mut collector = FreeLifetimeCollector { names: opt_vec::Empty };
+    for ty_param in ty_params.iter() {
+        visit::walk_ty_param_bounds(&mut collector, &ty_param.bounds, ());
+    }
+    return collector.names;
+
+    struct FreeLifetimeCollector {
+        names: OptVec<ast::Name>,
+    }
+
+    impl Visitor<()> for FreeLifetimeCollector {
+        fn visit_lifetime_ref(&mut self,
+                              lifetime_ref: &ast::Lifetime,
+                              _: ()) {
+            self.names.push(lifetime_ref.name);
+        }
+    }
+}
diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index 6c48440421f..b0cf17c5b54 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -276,7 +276,7 @@ impl Subst for ty::Region {
         // bound in *fn types*. Region substitution of the bound
         // regions that appear in a function signature is done using
         // the specialized routine
-        // `middle::typeck::check::regionmanip::replace_bound_regions_in_fn_sig()`.
+        // `middle::typeck::check::regionmanip::replace_late_regions_in_fn_sig()`.
         match self {
             &ty::ReEarlyBound(_, i, _) => {
                 match substs.regions {
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 5129d7a8b68..b2a879b1946 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -1008,6 +1008,7 @@ pub struct Generics {
     type_param_defs: Rc<Vec<TypeParameterDef> >,
 
     /// List of region parameters declared on the item.
+    /// For a fn or method, only includes *early-bound* lifetimes.
     region_param_defs: Rc<Vec<RegionParameterDef> >,
 }
 
@@ -5077,6 +5078,7 @@ pub fn construct_parameter_environment(
     item_type_params: &[TypeParameterDef],
     method_type_params: &[TypeParameterDef],
     item_region_params: &[RegionParameterDef],
+    method_region_params: &[RegionParameterDef],
     free_id: ast::NodeId)
     -> ParameterEnvironment
 {
@@ -5104,11 +5106,24 @@ pub fn construct_parameter_environment(
         });
 
     // map bound 'a => free 'a
-    let region_params = item_region_params.iter().
-        map(|r| ty::ReFree(ty::FreeRegion {
-                scope_id: free_id,
-                bound_region: ty::BrNamed(r.def_id, r.name)})).
-        collect();
+    let region_params = {
+        fn push_region_params(accum: OptVec<ty::Region>,
+                              free_id: ast::NodeId,
+                              region_params: &[RegionParameterDef])
+                              -> OptVec<ty::Region> {
+            let mut accum = accum;
+            for r in region_params.iter() {
+                accum.push(
+                    ty::ReFree(ty::FreeRegion {
+                            scope_id: free_id,
+                            bound_region: ty::BrNamed(r.def_id, r.name)}));
+            }
+            accum
+        }
+
+        let t = push_region_params(opt_vec::Empty, free_id, item_region_params);
+        push_region_params(t, free_id, method_region_params)
+    };
 
     let free_substs = substs {
         self_ty: self_ty,
@@ -5130,6 +5145,15 @@ pub fn construct_parameter_environment(
         }
     });
 
+    debug!("construct_parameter_environment: free_id={} \
+           free_subst={} \
+           self_param_bound={} \
+           type_param_bound={}",
+           free_id,
+           free_substs.repr(tcx),
+           self_bound_substd.repr(tcx),
+           type_param_bounds_substd.repr(tcx));
+
     ty::ParameterEnvironment {
         free_substs: free_substs,
         self_param_bound: self_bound_substd,
diff --git a/src/librustc/middle/typeck/check/method.rs b/src/librustc/middle/typeck/check/method.rs
index 0cf0fa5897a..ca36fca687a 100644
--- a/src/librustc/middle/typeck/check/method.rs
+++ b/src/librustc/middle/typeck/check/method.rs
@@ -93,7 +93,7 @@ use middle::typeck::MethodCallee;
 use middle::typeck::{MethodOrigin, MethodParam};
 use middle::typeck::{MethodStatic, MethodObject};
 use middle::typeck::{param_numbered, param_self, param_index};
-use middle::typeck::check::regionmanip::replace_bound_regions_in_fn_sig;
+use middle::typeck::check::regionmanip::replace_late_bound_regions_in_fn_sig;
 use util::common::indenter;
 use util::ppaux::Repr;
 
@@ -428,7 +428,7 @@ impl<'a> LookupContext<'a> {
                                             substs: &ty::substs) {
         debug!("push_inherent_candidates_from_object(did={}, substs={})",
                self.did_to_str(did),
-               substs_to_str(self.tcx(), substs));
+               substs.repr(self.tcx()));
         let _indenter = indenter();
 
         // It is illegal to invoke a method on a trait instance that
@@ -554,7 +554,8 @@ impl<'a> LookupContext<'a> {
 
                     match mk_cand(bound_trait_ref, method, pos, this_bound_idx) {
                         Some(cand) => {
-                            debug!("pushing inherent candidate for param: {:?}", cand);
+                            debug!("pushing inherent candidate for param: {}",
+                                   cand.repr(self.tcx()));
                             self.inherent_candidates.borrow_mut().get().push(cand);
                         }
                         None => {}
@@ -938,8 +939,9 @@ impl<'a> LookupContext<'a> {
             let mut j = i + 1;
             while j < candidates.len() {
                 let candidate_b = &candidates[j];
-                debug!("attempting to merge {:?} and {:?}",
-                       candidate_a, candidate_b);
+                debug!("attempting to merge {} and {}",
+                       candidate_a.repr(self.tcx()),
+                       candidate_b.repr(self.tcx()));
                 let candidates_same = match (&candidate_a.origin,
                                              &candidate_b.origin) {
                     (&MethodParam(ref p1), &MethodParam(ref p2)) => {
@@ -984,9 +986,10 @@ impl<'a> LookupContext<'a> {
 
         let tcx = self.tcx();
 
-        debug!("confirm_candidate(expr={}, candidate={})",
+        debug!("confirm_candidate(expr={}, rcvr_ty={}, candidate={})",
                self.expr.repr(tcx),
-               self.cand_to_str(candidate));
+               self.ty_to_str(rcvr_ty),
+               candidate.repr(self.tcx()));
 
         self.enforce_object_limitations(candidate);
         self.enforce_drop_trait_limitations(candidate);
@@ -994,9 +997,9 @@ impl<'a> LookupContext<'a> {
         // static methods should never have gotten this far:
         assert!(candidate.method_ty.explicit_self != SelfStatic);
 
-        // Determine the values for the type parameters of the method.
+        // Determine the values for the generic parameters of the method.
         // If they were not explicitly supplied, just construct fresh
-        // type variables.
+        // variables.
         let num_supplied_tps = self.supplied_tps.len();
         let num_method_tps = candidate.method_ty.generics.type_param_defs().len();
         let m_substs = {
@@ -1018,12 +1021,26 @@ impl<'a> LookupContext<'a> {
             }
         };
 
+        // Determine values for the early-bound lifetime parameters.
+        // FIXME -- permit users to manually specify lifetimes
+        let mut all_regions = match candidate.rcvr_substs.regions {
+            NonerasedRegions(ref v) => v.clone(),
+            ErasedRegions => tcx.sess.span_bug(self.expr.span, "ErasedRegions")
+        };
+        let m_regions =
+            self.fcx.infcx().region_vars_for_defs(
+                self.expr.span,
+                candidate.method_ty.generics.region_param_defs.borrow().as_slice());
+        for &r in m_regions.iter() {
+            all_regions.push(r);
+        }
+
         // Construct the full set of type parameters for the method,
         // which is equal to the class tps + the method tps.
         let all_substs = substs {
             tps: vec_ng::append(candidate.rcvr_substs.tps.clone(),
                                 m_substs.as_slice()),
-            regions: candidate.rcvr_substs.regions.clone(),
+            regions: NonerasedRegions(all_regions),
             self_ty: candidate.rcvr_substs.self_ty,
         };
 
@@ -1057,10 +1074,10 @@ impl<'a> LookupContext<'a> {
 
         // Replace any bound regions that appear in the function
         // signature with region variables
-        let (_, fn_sig) = replace_bound_regions_in_fn_sig( tcx, &fn_sig, |br| {
-            self.fcx.infcx().next_region_var(
-                infer::BoundRegionInFnCall(self.expr.span, br))
-        });
+        let (_, fn_sig) = replace_late_bound_regions_in_fn_sig(
+            tcx, &fn_sig,
+            |br| self.fcx.infcx().next_region_var(
+                infer::LateBoundRegion(self.expr.span, br)));
         let transformed_self_ty = *fn_sig.inputs.get(0);
         let fty = ty::mk_bare_fn(tcx, ty::BareFnTy {
             sig: fn_sig,
@@ -1245,7 +1262,7 @@ impl<'a> LookupContext<'a> {
     // candidate method's `self_ty`.
     fn is_relevant(&self, rcvr_ty: ty::t, candidate: &Candidate) -> bool {
         debug!("is_relevant(rcvr_ty={}, candidate={})",
-               self.ty_to_str(rcvr_ty), self.cand_to_str(candidate));
+               self.ty_to_str(rcvr_ty), candidate.repr(self.tcx()));
 
         return match candidate.method_ty.explicit_self {
             SelfStatic => {
@@ -1385,13 +1402,6 @@ impl<'a> LookupContext<'a> {
         self.fcx.infcx().ty_to_str(t)
     }
 
-    fn cand_to_str(&self, cand: &Candidate) -> ~str {
-        format!("Candidate(rcvr_ty={}, rcvr_substs={}, origin={:?})",
-             cand.rcvr_match_condition.repr(self.tcx()),
-             ty::substs_to_str(self.tcx(), &cand.rcvr_substs),
-             cand.origin)
-    }
-
     fn did_to_str(&self, did: DefId) -> ~str {
         ty::item_path_str(self.tcx(), did)
     }
@@ -1401,6 +1411,15 @@ impl<'a> LookupContext<'a> {
     }
 }
 
+impl Repr for Candidate {
+    fn repr(&self, tcx: ty::ctxt) -> ~str {
+        format!("Candidate(rcvr_ty={}, rcvr_substs={}, origin={:?})",
+                self.rcvr_match_condition.repr(tcx),
+                self.rcvr_substs.repr(tcx),
+                self.origin)
+    }
+}
+
 impl Repr for RcvrMatchCondition {
     fn repr(&self, tcx: ty::ctxt) -> ~str {
         match *self {
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index b10e1bcd5de..026d2d5d734 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -97,7 +97,7 @@ use middle::typeck::check::method::{AutoderefReceiver};
 use middle::typeck::check::method::{AutoderefReceiverFlag};
 use middle::typeck::check::method::{CheckTraitsAndInherentMethods};
 use middle::typeck::check::method::{DontAutoderefReceiver};
-use middle::typeck::check::regionmanip::replace_bound_regions_in_fn_sig;
+use middle::typeck::check::regionmanip::replace_late_bound_regions_in_fn_sig;
 use middle::typeck::check::regionmanip::relate_free_regions;
 use middle::typeck::check::vtable::{LocationInfo, VtableContext};
 use middle::typeck::CrateCtxt;
@@ -439,7 +439,7 @@ fn check_fn(ccx: @CrateCtxt,
 
     // First, we have to replace any bound regions in the fn type with free ones.
     // The free region references will be bound the node_id of the body block.
-    let (_, fn_sig) = replace_bound_regions_in_fn_sig(tcx, fn_sig, |br| {
+    let (_, fn_sig) = replace_late_bound_regions_in_fn_sig(tcx, fn_sig, |br| {
         ty::ReFree(ty::FreeRegion {scope_id: body.id, bound_region: br})
     });
 
@@ -563,13 +563,13 @@ pub fn check_item(ccx: @CrateCtxt, it: &ast::Item) {
       ast::ItemFn(decl, _, _, _, body) => {
         let fn_tpt = ty::lookup_item_type(ccx.tcx, ast_util::local_def(it.id));
 
-        // FIXME(#5121) -- won't work for lifetimes that appear in type bounds
         let param_env = ty::construct_parameter_environment(
                 ccx.tcx,
                 None,
                 fn_tpt.generics.type_param_defs(),
                 [],
                 [],
+                fn_tpt.generics.region_param_defs.borrow().as_slice(),
                 body.id);
 
         check_bare_fn(ccx, decl, body, it.id, fn_tpt.ty, param_env);
@@ -679,6 +679,7 @@ fn check_method_body(ccx: @CrateCtxt,
             item_generics.type_param_defs(),
             method_generics.type_param_defs(),
             item_generics.region_param_defs(),
+            method_generics.region_param_defs(),
             method.body.id);
 
     // Compute the fty from point of view of inside fn
@@ -1439,21 +1440,17 @@ pub fn impl_self_ty(vcx: &VtableContext,
                  -> ty_param_substs_and_ty {
     let tcx = vcx.tcx();
 
-    let (n_tps, n_rps, raw_ty) = {
-        let ity = ty::lookup_item_type(tcx, did);
+    let ity = ty::lookup_item_type(tcx, did);
+    let (n_tps, rps, raw_ty) =
         (ity.generics.type_param_defs().len(),
-         ity.generics.region_param_defs().len(),
-         ity.ty)
-    };
+         ity.generics.region_param_defs(),
+         ity.ty);
 
-    let rps =
-        vcx.infcx.next_region_vars(
-            infer::BoundRegionInTypeOrImpl(location_info.span),
-            n_rps);
+    let rps = vcx.infcx.region_vars_for_defs(location_info.span, rps);
     let tps = vcx.infcx.next_ty_vars(n_tps);
 
     let substs = substs {
-        regions: ty::NonerasedRegions(opt_vec::from(rps.move_iter().collect())),
+        regions: ty::NonerasedRegions(rps),
         self_ty: None,
         tps: tps,
     };
@@ -1887,9 +1884,8 @@ fn check_expr_with_unifier(fcx: @FnCtxt,
 
         // Replace any bound regions that appear in the function
         // signature with region variables
-        let (_, fn_sig) = replace_bound_regions_in_fn_sig(fcx.tcx(), fn_sig, |br| {
-            fcx.infcx()
-               .next_region_var(infer::BoundRegionInFnCall(call_expr.span, br))
+        let (_, fn_sig) = replace_late_bound_regions_in_fn_sig(fcx.tcx(), fn_sig, |br| {
+            fcx.infcx().next_region_var(infer::LateBoundRegion(call_expr.span, br))
         });
 
         // Call the generic checker.
@@ -2213,7 +2209,7 @@ fn check_expr_with_unifier(fcx: @FnCtxt,
             match expected_sty {
                 Some(ty::ty_closure(ref cenv)) => {
                     let (_, sig) =
-                        replace_bound_regions_in_fn_sig(
+                        replace_late_bound_regions_in_fn_sig(
                             tcx, &cenv.sig,
                             |_| fcx.inh.infcx.fresh_bound_region(expr.id));
                     (Some(sig), cenv.purity, cenv.sigil,
@@ -2461,16 +2457,14 @@ fn check_expr_with_unifier(fcx: @FnCtxt,
         // determine whether the class is region-parameterized.
         let item_type = ty::lookup_item_type(tcx, class_id);
         let type_parameter_count = item_type.generics.type_param_defs().len();
-        let region_parameter_count = item_type.generics.region_param_defs().len();
+        let region_param_defs = item_type.generics.region_param_defs();
         let raw_type = item_type.ty;
 
         // Generate the struct type.
-        let regions = fcx.infcx().next_region_vars(
-            infer::BoundRegionInTypeOrImpl(span),
-            region_parameter_count).move_iter().collect();
+        let regions = fcx.infcx().region_vars_for_defs(span, region_param_defs);
         let type_parameters = fcx.infcx().next_ty_vars(type_parameter_count);
         let substitutions = substs {
-            regions: ty::NonerasedRegions(opt_vec::from(regions)),
+            regions: ty::NonerasedRegions(regions),
             self_ty: None,
             tps: type_parameters
         };
@@ -2519,16 +2513,14 @@ fn check_expr_with_unifier(fcx: @FnCtxt,
         // determine whether the enum is region-parameterized.
         let item_type = ty::lookup_item_type(tcx, enum_id);
         let type_parameter_count = item_type.generics.type_param_defs().len();
-        let region_parameter_count = item_type.generics.region_param_defs().len();
+        let region_param_defs = item_type.generics.region_param_defs();
         let raw_type = item_type.ty;
 
         // Generate the enum type.
-        let regions = fcx.infcx().next_region_vars(
-            infer::BoundRegionInTypeOrImpl(span),
-            region_parameter_count).move_iter().collect();
+        let regions = fcx.infcx().region_vars_for_defs(span, region_param_defs);
         let type_parameters = fcx.infcx().next_ty_vars(type_parameter_count);
         let substitutions = substs {
-            regions: ty::NonerasedRegions(opt_vec::from(regions)),
+            regions: ty::NonerasedRegions(regions),
             self_ty: None,
             tps: type_parameters
         };
@@ -3726,8 +3718,8 @@ pub fn instantiate_path(fcx: @FnCtxt,
     let num_expected_regions = tpt.generics.region_param_defs().len();
     let num_supplied_regions = pth.segments.last().unwrap().lifetimes.len();
     let regions = if num_expected_regions == num_supplied_regions {
-        pth.segments.last().unwrap().lifetimes.map(
-            |l| ast_region_to_region(fcx.tcx(), l))
+        opt_vec::from(pth.segments.last().unwrap().lifetimes.map(
+            |l| ast_region_to_region(fcx.tcx(), l)))
     } else {
         if num_supplied_regions != 0 {
             fcx.ccx.tcx.sess.span_err(
@@ -3740,11 +3732,9 @@ pub fn instantiate_path(fcx: @FnCtxt,
                         nsupplied = num_supplied_regions));
         }
 
-        fcx.infcx().next_region_vars(
-                infer::BoundRegionInTypeOrImpl(span),
-                num_expected_regions).move_iter().collect()
+        fcx.infcx().region_vars_for_defs(span, tpt.generics.region_param_defs.borrow().as_slice())
     };
-    let regions = ty::NonerasedRegions(opt_vec::from(regions));
+    let regions = ty::NonerasedRegions(regions);
 
     // Special case: If there is a self parameter, omit it from the list of
     // type parameters.
diff --git a/src/librustc/middle/typeck/check/regionmanip.rs b/src/librustc/middle/typeck/check/regionmanip.rs
index d0bb1f32fb8..c8a126382f4 100644
--- a/src/librustc/middle/typeck/check/regionmanip.rs
+++ b/src/librustc/middle/typeck/check/regionmanip.rs
@@ -21,12 +21,12 @@ use util::ppaux;
 
 // Helper functions related to manipulating region types.
 
-pub fn replace_bound_regions_in_fn_sig(
+pub fn replace_late_bound_regions_in_fn_sig(
         tcx: ty::ctxt,
         fn_sig: &ty::FnSig,
         mapf: |ty::BoundRegion| -> ty::Region)
         -> (HashMap<ty::BoundRegion,ty::Region>, ty::FnSig) {
-    debug!("replace_bound_regions_in_fn_sig({})", fn_sig.repr(tcx));
+    debug!("replace_late_bound_regions_in_fn_sig({})", fn_sig.repr(tcx));
 
     let mut map = HashMap::new();
     let fn_sig = {
diff --git a/src/librustc/middle/typeck/check/vtable.rs b/src/librustc/middle/typeck/check/vtable.rs
index 32e1dfd98db..57e85ab55d3 100644
--- a/src/librustc/middle/typeck/check/vtable.rs
+++ b/src/librustc/middle/typeck/check/vtable.rs
@@ -777,6 +777,7 @@ pub fn resolve_impl(tcx: ty::ctxt,
         impl_generics.type_param_defs(),
         [],
         impl_generics.region_param_defs(),
+        [],
         impl_item.id);
 
     let impl_trait_ref = @impl_trait_ref.subst(tcx, &param_env.free_substs);
@@ -832,7 +833,7 @@ pub fn trans_resolve_method(tcx: ty::ctxt, id: ast::NodeId,
     if has_trait_bounds(type_param_defs.as_slice()) {
         let vcx = VtableContext {
             infcx: &infer::new_infer_ctxt(tcx),
-            param_env: &ty::construct_parameter_environment(tcx, None, [], [], [], id)
+            param_env: &ty::construct_parameter_environment(tcx, None, [], [], [], [], id)
         };
         let loc_info = LocationInfo {
             id: id,
diff --git a/src/librustc/middle/typeck/coherence.rs b/src/librustc/middle/typeck/coherence.rs
index e85d71fa982..ca5befa8d4e 100644
--- a/src/librustc/middle/typeck/coherence.rs
+++ b/src/librustc/middle/typeck/coherence.rs
@@ -42,7 +42,6 @@ use syntax::ast_map::NodeItem;
 use syntax::ast_map;
 use syntax::ast_util::{def_id_of_def, local_def};
 use syntax::codemap::Span;
-use syntax::opt_vec;
 use syntax::parse::token;
 use syntax::visit;
 
@@ -516,18 +515,17 @@ impl CoherenceChecker {
     // type variables. Returns the monotype and the type variables created.
     fn universally_quantify_polytype(&self, polytype: ty_param_bounds_and_ty)
                                      -> UniversalQuantificationResult {
-        let region_parameter_count = polytype.generics.region_param_defs().len();
         let region_parameters =
-            self.inference_context.next_region_vars(
-                infer::BoundRegionInCoherence,
-                region_parameter_count);
+            polytype.generics.region_param_defs().iter()
+            .map(|d| self.inference_context.next_region_var(
+                infer::BoundRegionInCoherence(d.name)))
+            .collect();
 
         let bounds_count = polytype.generics.type_param_defs().len();
         let type_parameters = self.inference_context.next_ty_vars(bounds_count);
 
         let substitutions = substs {
-            regions: ty::NonerasedRegions(opt_vec::from(
-                             region_parameters.move_iter().collect())),
+            regions: ty::NonerasedRegions(region_parameters),
             self_ty: None,
             tps: type_parameters
         };
diff --git a/src/librustc/middle/typeck/collect.rs b/src/librustc/middle/typeck/collect.rs
index 82246899fb7..234e6e92bac 100644
--- a/src/librustc/middle/typeck/collect.rs
+++ b/src/librustc/middle/typeck/collect.rs
@@ -32,6 +32,7 @@ are represented as `ty_param()` instances.
 
 
 use metadata::csearch;
+use middle::resolve_lifetime;
 use middle::ty::{ImplContainer, MethodContainer, TraitContainer, substs};
 use middle::ty::{ty_param_bounds_and_ty};
 use middle::ty;
@@ -45,7 +46,6 @@ use util::ppaux;
 use util::ppaux::Repr;
 
 use std::rc::Rc;
-use std::vec;
 use std::vec_ng::Vec;
 use std::vec_ng;
 use syntax::abi::AbiSet;
@@ -160,7 +160,7 @@ pub fn get_enum_variant_types(ccx: &CrateCtxt,
 
             ast::StructVariantKind(struct_def) => {
                 let tpt = ty_param_bounds_and_ty {
-                    generics: ty_generics(ccx, generics, 0),
+                    generics: ty_generics_for_type(ccx, generics),
                     ty: enum_ty
                 };
 
@@ -173,7 +173,7 @@ pub fn get_enum_variant_types(ccx: &CrateCtxt,
         };
 
         let tpt = ty_param_bounds_and_ty {
-            generics: ty_generics(ccx, generics, 0),
+            generics: ty_generics_for_type(ccx, generics),
             ty: result_ty
         };
 
@@ -192,7 +192,7 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt, trait_id: ast::NodeId) {
         ast_map::NodeItem(item) => {
             match item.node {
                 ast::ItemTrait(ref generics, _, ref ms) => {
-                    let trait_ty_generics = ty_generics(ccx, generics, 0);
+                    let trait_ty_generics = ty_generics_for_type(ccx, generics);
 
                     // For each method, construct a suitable ty::Method and
                     // store it into the `tcx.methods` table:
@@ -293,7 +293,7 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt, trait_id: ast::NodeId) {
 
         // Represents [A',B',C']
         let num_trait_bounds = trait_ty_generics.type_param_defs().len();
-        let non_shifted_trait_tps = vec::from_fn(num_trait_bounds, |i| {
+        let non_shifted_trait_tps = Vec::from_fn(num_trait_bounds, |i| {
             ty::mk_param(tcx, i, trait_ty_generics.type_param_defs()[i].def_id)
         });
 
@@ -303,7 +303,7 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt, trait_id: ast::NodeId) {
 
         // Represents [E',F',G']
         let num_method_bounds = m.generics.type_param_defs().len();
-        let shifted_method_tps = vec::from_fn(num_method_bounds, |i| {
+        let shifted_method_tps = Vec::from_fn(num_method_bounds, |i| {
             ty::mk_param(tcx, i + num_trait_bounds + 1,
                          m.generics.type_param_defs()[i].def_id)
         });
@@ -326,8 +326,8 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt, trait_id: ast::NodeId) {
         let substs = substs {
             regions: ty::NonerasedRegions(rps_from_trait),
             self_ty: Some(self_param),
-            tps: vec_ng::append(Vec::from_slice(non_shifted_trait_tps),
-                                shifted_method_tps)
+            tps: vec_ng::append(non_shifted_trait_tps,
+                                shifted_method_tps.as_slice())
         };
 
         // create the type of `foo`, applying the substitution above
@@ -394,10 +394,11 @@ pub fn ensure_trait_methods(ccx: &CrateCtxt, trait_id: ast::NodeId) {
         let fty = astconv::ty_of_method(this, *m_id, *m_purity, trait_self_ty,
                                         *m_explicit_self, m_decl);
         let num_trait_type_params = trait_generics.type_param_defs().len();
+        let ty_generics = ty_generics_for_fn_or_method(this, m_generics,
+                                                       num_trait_type_params);
         ty::Method::new(
             *m_ident,
-            // FIXME(#5121) -- distinguish early vs late lifetime params
-            ty_generics(this, m_generics, num_trait_type_params),
+            ty_generics,
             fty,
             m_explicit_self.node,
             // assume public, because this is only invoked on trait methods
@@ -477,7 +478,8 @@ fn convert_methods(ccx: &CrateCtxt,
     let tcx = ccx.tcx;
     for m in ms.iter() {
         let num_rcvr_ty_params = rcvr_ty_generics.type_param_defs().len();
-        let m_ty_generics = ty_generics(ccx, &m.generics, num_rcvr_ty_params);
+        let m_ty_generics = ty_generics_for_fn_or_method(ccx, &m.generics,
+                                                         num_rcvr_ty_params);
         let mty = @ty_of_method(ccx,
                                 container,
                                 *m,
@@ -503,7 +505,9 @@ fn convert_methods(ccx: &CrateCtxt,
                             Vec::from_slice(
                                 rcvr_ty_generics.type_param_defs()),
                             m_ty_generics.type_param_defs())),
-                        region_param_defs: rcvr_ty_generics.region_param_defs.clone(),
+                        region_param_defs: Rc::new(vec_ng::append(
+                                Vec::from_slice(rcvr_ty_generics.region_param_defs()),
+                                m_ty_generics.region_param_defs())),
                     },
                     ty: fty
                 });
@@ -533,10 +537,11 @@ fn convert_methods(ccx: &CrateCtxt,
         let method_vis = m.vis.inherit_from(rcvr_visibility);
 
         let num_rcvr_type_params = rcvr_generics.ty_params.len();
+        let m_ty_generics =
+            ty_generics_for_fn_or_method(ccx, &m.generics, num_rcvr_type_params);
         ty::Method::new(
             m.ident,
-            // FIXME(#5121) -- distinguish early vs late lifetime params
-            ty_generics(ccx, &m.generics, num_rcvr_type_params),
+            m_ty_generics,
             fty,
             m.explicit_self.node,
             method_vis,
@@ -588,7 +593,7 @@ pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
                                    generics);
         },
         ast::ItemImpl(ref generics, ref opt_trait_ref, selfty, ref ms) => {
-            let i_ty_generics = ty_generics(ccx, generics, 0);
+            let ty_generics = ty_generics_for_type(ccx, generics);
             let selfty = ccx.to_ty(&ExplicitRscope, selfty);
             write_ty_to_tcx(tcx, it.id, selfty);
 
@@ -596,7 +601,7 @@ pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
                 let mut tcache = tcx.tcache.borrow_mut();
                 tcache.get().insert(local_def(it.id),
                                     ty_param_bounds_and_ty {
-                                        generics: i_ty_generics.clone(),
+                                        generics: ty_generics.clone(),
                                         ty: selfty});
             }
 
@@ -615,7 +620,7 @@ pub fn convert(ccx: &CrateCtxt, it: &ast::Item) {
                             ImplContainer(local_def(it.id)),
                             ms.as_slice(),
                             selfty,
-                            &i_ty_generics,
+                            &ty_generics,
                             generics,
                             parent_visibility);
 
@@ -813,7 +818,7 @@ pub fn trait_def_of_item(ccx: &CrateCtxt, it: &ast::Item) -> @ty::TraitDef {
     match it.node {
         ast::ItemTrait(ref generics, ref supertraits, _) => {
             let self_ty = ty::mk_self(tcx, def_id);
-            let ty_generics = ty_generics(ccx, generics, 0);
+            let ty_generics = ty_generics_for_type(ccx, generics);
             let substs = mk_item_substs(ccx, &ty_generics, Some(self_ty));
             let bounds = ensure_supertraits(ccx,
                                             it.id,
@@ -857,17 +862,14 @@ pub fn ty_of_item(ccx: &CrateCtxt, it: &ast::Item)
             return tpt;
         }
         ast::ItemFn(decl, purity, abi, ref generics, _) => {
-            let ty_generics = ty_generics(ccx, generics, 0);
+            let ty_generics = ty_generics_for_fn_or_method(ccx, generics, 0);
             let tofd = astconv::ty_of_bare_fn(ccx,
                                               it.id,
                                               purity,
                                               abi,
                                               decl);
             let tpt = ty_param_bounds_and_ty {
-                generics: ty::Generics {
-                    type_param_defs: ty_generics.type_param_defs.clone(),
-                    region_param_defs: Rc::new(Vec::new()),
-                },
+                generics: ty_generics,
                 ty: ty::mk_bare_fn(ccx.tcx, tofd)
             };
             debug!("type of {} (id {}) is {}",
@@ -891,7 +893,7 @@ pub fn ty_of_item(ccx: &CrateCtxt, it: &ast::Item)
             let tpt = {
                 let ty = ccx.to_ty(&ExplicitRscope, t);
                 ty_param_bounds_and_ty {
-                    generics: ty_generics(ccx, generics, 0),
+                    generics: ty_generics_for_type(ccx, generics),
                     ty: ty
                 }
             };
@@ -902,7 +904,7 @@ pub fn ty_of_item(ccx: &CrateCtxt, it: &ast::Item)
         }
         ast::ItemEnum(_, ref generics) => {
             // Create a new generic polytype.
-            let ty_generics = ty_generics(ccx, generics, 0);
+            let ty_generics = ty_generics_for_type(ccx, generics);
             let substs = mk_item_substs(ccx, &ty_generics, None);
             let t = ty::mk_enum(tcx, local_def(it.id), substs);
             let tpt = ty_param_bounds_and_ty {
@@ -920,7 +922,7 @@ pub fn ty_of_item(ccx: &CrateCtxt, it: &ast::Item)
                 format!("invoked ty_of_item on trait"));
         }
         ast::ItemStruct(_, ref generics) => {
-            let ty_generics = ty_generics(ccx, generics, 0);
+            let ty_generics = ty_generics_for_type(ccx, generics);
             let substs = mk_item_substs(ccx, &ty_generics, None);
             let t = ty::mk_struct(tcx, local_def(it.id), substs);
             let tpt = ty_param_bounds_and_ty {
@@ -961,42 +963,51 @@ pub fn ty_of_foreign_item(ccx: &CrateCtxt,
     }
 }
 
+pub fn ty_generics_for_type(ccx: &CrateCtxt,
+                            generics: &ast::Generics)
+                            -> ty::Generics {
+    ty_generics(ccx, &generics.lifetimes, &generics.ty_params, 0)
+}
+
+pub fn ty_generics_for_fn_or_method(ccx: &CrateCtxt,
+                                    generics: &ast::Generics,
+                                    base_index: uint)
+                                    -> ty::Generics {
+    let early_lifetimes = resolve_lifetime::early_bound_lifetimes(generics);
+    ty_generics(ccx, &early_lifetimes, &generics.ty_params, base_index)
+}
+
 pub fn ty_generics(ccx: &CrateCtxt,
-                   generics: &ast::Generics,
+                   lifetimes: &Vec<ast::Lifetime>,
+                   ty_params: &OptVec<ast::TyParam>,
                    base_index: uint) -> ty::Generics {
     return ty::Generics {
-        region_param_defs: Rc::new(generics.lifetimes.iter().map(|l| {
+        region_param_defs: Rc::new(lifetimes.iter().map(|l| {
                 ty::RegionParameterDef { name: l.name,
                                          def_id: local_def(l.id) }
             }).collect()),
-        type_param_defs: Rc::new(generics.ty_params.mapi_to_vec(|offset, param| {
+        type_param_defs: Rc::new(ty_params.mapi_to_vec(|offset, param| {
             let existing_def_opt = {
                 let ty_param_defs = ccx.tcx.ty_param_defs.borrow();
-                ty_param_defs.get().find(&param.id).map(|def| *def)
+                ty_param_defs.get().find(&param.id).map(|&def| def)
             };
-            match existing_def_opt {
-                Some(def) => def,
-                None => {
-                    let param_ty = ty::param_ty {idx: base_index + offset,
-                                                 def_id: local_def(param.id)};
-                    let bounds = @compute_bounds(ccx, param_ty, &param.bounds);
-                    let default = param.default.map(|x| ast_ty_to_ty(ccx, &ExplicitRscope, x));
-                    let def = ty::TypeParameterDef {
-                        ident: param.ident,
-                        def_id: local_def(param.id),
-                        bounds: bounds,
-                        default: default
-                    };
-                    debug!("def for param: {}", def.repr(ccx.tcx));
-
-                    let mut ty_param_defs = ccx.tcx
-                                               .ty_param_defs
-                                               .borrow_mut();
-                    ty_param_defs.get().insert(param.id, def);
-                    def
-                }
-            }
-        }).move_iter().collect())
+            existing_def_opt.unwrap_or_else(|| {
+                let param_ty = ty::param_ty {idx: base_index + offset,
+                                             def_id: local_def(param.id)};
+                let bounds = @compute_bounds(ccx, param_ty, &param.bounds);
+                let default = param.default.map(|x| ast_ty_to_ty(ccx, &ExplicitRscope, x));
+                let def = ty::TypeParameterDef {
+                    ident: param.ident,
+                    def_id: local_def(param.id),
+                    bounds: bounds,
+                    default: default
+                };
+                debug!("def for param: {}", def.repr(ccx.tcx));
+                let mut ty_param_defs = ccx.tcx.ty_param_defs.borrow_mut();
+                ty_param_defs.get().insert(param.id, def);
+                def
+            })
+        }).move_iter().collect()),
     };
 
     fn compute_bounds(
@@ -1056,7 +1067,8 @@ pub fn ty_of_foreign_fn_decl(ccx: &CrateCtxt,
         }
     }
 
-    let ty_generics = ty_generics(ccx, ast_generics, 0);
+    let ty_generics_for_fn_or_method =
+        ty_generics_for_fn_or_method(ccx, ast_generics, 0);
     let rb = BindingRscope::new(def_id.node);
     let input_tys = decl.inputs
                         .iter()
@@ -1076,7 +1088,7 @@ pub fn ty_of_foreign_fn_decl(ccx: &CrateCtxt,
                             variadic: decl.variadic}
         });
     let tpt = ty_param_bounds_and_ty {
-        generics: ty_generics,
+        generics: ty_generics_for_fn_or_method,
         ty: t_fn
     };
 
diff --git a/src/librustc/middle/typeck/infer/error_reporting.rs b/src/librustc/middle/typeck/infer/error_reporting.rs
index 3a3f24a2e2d..0dea3460012 100644
--- a/src/librustc/middle/typeck/infer/error_reporting.rs
+++ b/src/librustc/middle/typeck/infer/error_reporting.rs
@@ -72,6 +72,7 @@ use middle::typeck::infer::region_inference::ConcreteFailure;
 use middle::typeck::infer::region_inference::SubSupConflict;
 use middle::typeck::infer::region_inference::SupSupConflict;
 use syntax::opt_vec::OptVec;
+use syntax::parse::token;
 use util::ppaux::UserString;
 use util::ppaux::bound_region_to_str;
 use util::ppaux::note_and_explain_region;
@@ -479,19 +480,21 @@ impl ErrorReportingHelpers for InferCtxt {
             infer::AddrOfSlice(_) => ~" for slice expression",
             infer::Autoref(_) => ~" for autoref",
             infer::Coercion(_) => ~" for automatic coercion",
-            infer::BoundRegionInFnCall(_, br) => {
+            infer::LateBoundRegion(_, br) => {
                 format!(" for {}in function call",
-                        bound_region_to_str(self.tcx, "region ", true, br))
+                        bound_region_to_str(self.tcx, "lifetime parameter ", true, br))
             }
             infer::BoundRegionInFnType(_, br) => {
                 format!(" for {}in function type",
-                        bound_region_to_str(self.tcx, "region ", true, br))
+                        bound_region_to_str(self.tcx, "lifetime parameter ", true, br))
             }
-            infer::BoundRegionInTypeOrImpl(_) => {
-                format!(" for region in type/impl")
+            infer::EarlyBoundRegion(_, name) => {
+                format!(" for lifetime parameter `{}",
+                        token::get_name(name).get())
             }
-            infer::BoundRegionInCoherence(..) => {
-                format!(" for coherence check")
+            infer::BoundRegionInCoherence(name) => {
+                format!(" for lifetime parameter `{} in coherence check",
+                        token::get_name(name).get())
             }
             infer::UpvarRegion(ref upvar_id, _) => {
                 format!(" for capture of `{}` by closure",
diff --git a/src/librustc/middle/typeck/infer/glb.rs b/src/librustc/middle/typeck/infer/glb.rs
index 68b609000f4..ac73c308025 100644
--- a/src/librustc/middle/typeck/infer/glb.rs
+++ b/src/librustc/middle/typeck/infer/glb.rs
@@ -136,11 +136,11 @@ impl<'f> Combine for Glb<'f> {
 
         // Instantiate each bound region with a fresh region variable.
         let (a_with_fresh, a_map) =
-            self.get_ref().infcx.replace_bound_regions_with_fresh_regions(
+            self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
                 self.get_ref().trace, a);
         let a_vars = var_ids(self, &a_map);
         let (b_with_fresh, b_map) =
-            self.get_ref().infcx.replace_bound_regions_with_fresh_regions(
+            self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
                 self.get_ref().trace, b);
         let b_vars = var_ids(self, &b_map);
 
diff --git a/src/librustc/middle/typeck/infer/lub.rs b/src/librustc/middle/typeck/infer/lub.rs
index 0f2b2da397e..7d772065da6 100644
--- a/src/librustc/middle/typeck/infer/lub.rs
+++ b/src/librustc/middle/typeck/infer/lub.rs
@@ -126,10 +126,10 @@ impl<'f> Combine for Lub<'f> {
 
         // Instantiate each bound region with a fresh region variable.
         let (a_with_fresh, a_map) =
-            self.get_ref().infcx.replace_bound_regions_with_fresh_regions(
+            self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
                 self.get_ref().trace, a);
         let (b_with_fresh, _) =
-            self.get_ref().infcx.replace_bound_regions_with_fresh_regions(
+            self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
                 self.get_ref().trace, b);
 
         // Collect constraints.
diff --git a/src/librustc/middle/typeck/infer/mod.rs b/src/librustc/middle/typeck/infer/mod.rs
index 5500d9afc67..d3ae7d697e6 100644
--- a/src/librustc/middle/typeck/infer/mod.rs
+++ b/src/librustc/middle/typeck/infer/mod.rs
@@ -27,7 +27,7 @@ use middle::ty::{TyVid, IntVid, FloatVid, RegionVid, Vid};
 use middle::ty;
 use middle::ty_fold;
 use middle::ty_fold::TypeFolder;
-use middle::typeck::check::regionmanip::replace_bound_regions_in_fn_sig;
+use middle::typeck::check::regionmanip::replace_late_bound_regions_in_fn_sig;
 use middle::typeck::infer::coercion::Coerce;
 use middle::typeck::infer::combine::{Combine, CombineFields, eq_tys};
 use middle::typeck::infer::region_inference::{RegionVarBindings};
@@ -44,6 +44,7 @@ use syntax::ast::{MutImmutable, MutMutable};
 use syntax::ast;
 use syntax::codemap;
 use syntax::codemap::Span;
+use syntax::opt_vec::OptVec;
 use util::common::indent;
 use util::ppaux::{bound_region_to_str, ty_to_str, trait_ref_to_str, Repr};
 
@@ -221,9 +222,12 @@ pub enum RegionVariableOrigin {
     // Regions created as part of an automatic coercion
     Coercion(TypeTrace),
 
+    // Region variables created as the values for early-bound regions
+    EarlyBoundRegion(Span, ast::Name),
+
     // Region variables created for bound regions
     // in a function or method that is called
-    BoundRegionInFnCall(Span, ty::BoundRegion),
+    LateBoundRegion(Span, ty::BoundRegion),
 
     // Region variables created for bound regions
     // when doing subtyping/lub/glb computations
@@ -231,9 +235,7 @@ pub enum RegionVariableOrigin {
 
     UpvarRegion(ty::UpvarId, Span),
 
-    BoundRegionInTypeOrImpl(Span),
-
-    BoundRegionInCoherence,
+    BoundRegionInCoherence(ast::Name),
 }
 
 pub enum fixup_err {
@@ -663,6 +665,15 @@ impl InferCtxt {
         Vec::from_fn(count, |_| self.next_region_var(origin))
     }
 
+    pub fn region_vars_for_defs(&self,
+                                span: Span,
+                                defs: &[ty::RegionParameterDef])
+                                -> OptVec<ty::Region> {
+        defs.iter()
+            .map(|d| self.next_region_var(EarlyBoundRegion(span, d.name)))
+            .collect()
+    }
+
     pub fn fresh_bound_region(&self, binder_id: ast::NodeId) -> ty::Region {
         self.region_vars.new_bound(binder_id)
     }
@@ -809,14 +820,14 @@ impl InferCtxt {
         self.type_error_message(sp, mk_msg, a, Some(err));
     }
 
-    pub fn replace_bound_regions_with_fresh_regions(&self,
-                                                    trace: TypeTrace,
-                                                    fsig: &ty::FnSig)
+    pub fn replace_late_bound_regions_with_fresh_regions(&self,
+                                                         trace: TypeTrace,
+                                                         fsig: &ty::FnSig)
                                                     -> (ty::FnSig,
                                                         HashMap<ty::BoundRegion,
                                                                 ty::Region>) {
         let (map, fn_sig) =
-            replace_bound_regions_in_fn_sig(self.tcx, fsig, |br| {
+            replace_late_bound_regions_in_fn_sig(self.tcx, fsig, |br| {
                 let rvar = self.next_region_var(
                     BoundRegionInFnType(trace.origin.span(), br));
                 debug!("Bound region {} maps to {:?}",
@@ -932,10 +943,10 @@ impl RegionVariableOrigin {
             AddrOfSlice(a) => a,
             Autoref(a) => a,
             Coercion(a) => a.span(),
-            BoundRegionInFnCall(a, _) => a,
+            EarlyBoundRegion(a, _) => a,
+            LateBoundRegion(a, _) => a,
             BoundRegionInFnType(a, _) => a,
-            BoundRegionInTypeOrImpl(a) => a,
-            BoundRegionInCoherence => codemap::DUMMY_SP,
+            BoundRegionInCoherence(_) => codemap::DUMMY_SP,
             UpvarRegion(_, a) => a
         }
     }
@@ -950,13 +961,14 @@ impl Repr for RegionVariableOrigin {
             AddrOfSlice(a) => format!("AddrOfSlice({})", a.repr(tcx)),
             Autoref(a) => format!("Autoref({})", a.repr(tcx)),
             Coercion(a) => format!("Coercion({})", a.repr(tcx)),
-            BoundRegionInFnCall(a, b) => format!("bound_regionInFnCall({},{})",
+            EarlyBoundRegion(a, b) => format!("EarlyBoundRegion({},{})",
                                               a.repr(tcx), b.repr(tcx)),
+            LateBoundRegion(a, b) => format!("LateBoundRegion({},{})",
+                                             a.repr(tcx), b.repr(tcx)),
             BoundRegionInFnType(a, b) => format!("bound_regionInFnType({},{})",
                                               a.repr(tcx), b.repr(tcx)),
-            BoundRegionInTypeOrImpl(a) => format!("bound_regionInTypeOrImpl({})",
-                                               a.repr(tcx)),
-            BoundRegionInCoherence => format!("bound_regionInCoherence"),
+            BoundRegionInCoherence(a) => format!("bound_regionInCoherence({})",
+                                                 a.repr(tcx)),
             UpvarRegion(a, b) => format!("UpvarRegion({}, {})",
                                          a.repr(tcx),
                                          b.repr(tcx)),
diff --git a/src/librustc/middle/typeck/infer/sub.rs b/src/librustc/middle/typeck/infer/sub.rs
index 57953313324..2233e680bc9 100644
--- a/src/librustc/middle/typeck/infer/sub.rs
+++ b/src/librustc/middle/typeck/infer/sub.rs
@@ -12,7 +12,7 @@
 use middle::ty::{BuiltinBounds};
 use middle::ty;
 use middle::ty::TyVar;
-use middle::typeck::check::regionmanip::replace_bound_regions_in_fn_sig;
+use middle::typeck::check::regionmanip::replace_late_bound_regions_in_fn_sig;
 use middle::typeck::infer::combine::*;
 use middle::typeck::infer::{cres, CresCompare};
 use middle::typeck::infer::glb::Glb;
@@ -166,13 +166,13 @@ impl<'f> Combine for Sub<'f> {
         // First, we instantiate each bound region in the subtype with a fresh
         // region variable.
         let (a_sig, _) =
-            self.get_ref().infcx.replace_bound_regions_with_fresh_regions(
+            self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
                 self.get_ref().trace, a);
 
         // Second, we instantiate each bound region in the supertype with a
         // fresh concrete region.
         let (skol_map, b_sig) = {
-            replace_bound_regions_in_fn_sig(self.get_ref().infcx.tcx, b, |br| {
+            replace_late_bound_regions_in_fn_sig(self.get_ref().infcx.tcx, b, |br| {
                 let skol = self.get_ref().infcx.region_vars.new_skolemized(br);
                 debug!("Bound region {} skolemized to {:?}",
                        bound_region_to_str(self.get_ref().infcx.tcx, "", false, br),
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index c6765bd305a..2f06ab67a3b 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -841,6 +841,12 @@ impl Repr for ty::Method {
     }
 }
 
+impl Repr for ast::Name {
+    fn repr(&self, _tcx: ctxt) -> ~str {
+        token::get_name(*self).get().to_str()
+    }
+}
+
 impl Repr for ast::Ident {
     fn repr(&self, _tcx: ctxt) -> ~str {
         token::get_ident(*self).get().to_str()
@@ -1010,6 +1016,12 @@ impl UserString for ty::t {
     }
 }
 
+impl UserString for ast::Ident {
+    fn user_string(&self, _tcx: ctxt) -> ~str {
+        token::get_name(self.name).get().to_owned()
+    }
+}
+
 impl Repr for AbiSet {
     fn repr(&self, _tcx: ctxt) -> ~str {
         self.to_str()
diff --git a/src/test/compile-fail/regions-early-bound-error-method.rs b/src/test/compile-fail/regions-early-bound-error-method.rs
new file mode 100644
index 00000000000..9c8f8f8c30c
--- /dev/null
+++ b/src/test/compile-fail/regions-early-bound-error-method.rs
@@ -0,0 +1,35 @@
+// Copyright 2012 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.
+
+// Tests that you can use a fn lifetime parameter as part of
+// the value for a type parameter in a bound.
+
+trait GetRef<'a> {
+    fn get(&self) -> &'a int;
+}
+
+struct Box<'a> {
+    t: &'a int
+}
+
+impl<'a> GetRef<'a> for Box<'a> {
+    fn get(&self) -> &'a int {
+        self.t
+    }
+}
+
+impl<'a> Box<'a> {
+    fn or<'b,G:GetRef<'b>>(&self, g2: G) -> &'a int {
+        g2.get() //~ ERROR lifetime mismatch
+    }
+}
+
+fn main() {
+}
diff --git a/src/test/compile-fail/regions-early-bound-error.rs b/src/test/compile-fail/regions-early-bound-error.rs
new file mode 100644
index 00000000000..9cff4849cbe
--- /dev/null
+++ b/src/test/compile-fail/regions-early-bound-error.rs
@@ -0,0 +1,33 @@
+// Copyright 2012 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.
+
+// Tests that you can use a fn lifetime parameter as part of
+// the value for a type parameter in a bound.
+
+trait GetRef<'a, T> {
+    fn get(&self) -> &'a T;
+}
+
+struct Box<'a, T> {
+    t: &'a T
+}
+
+impl<'a,T:Clone> GetRef<'a,T> for Box<'a,T> {
+    fn get(&self) -> &'a T {
+        self.t
+    }
+}
+
+fn get<'a,'b,G:GetRef<'a, int>>(g1: G, b: &'b int) -> &'b int {
+    g1.get() //~ ERROR lifetime mismatch
+}
+
+fn main() {
+}
diff --git a/src/test/run-pass/regions-early-bound-used-in-bound-method.rs b/src/test/run-pass/regions-early-bound-used-in-bound-method.rs
new file mode 100644
index 00000000000..c011d11749b
--- /dev/null
+++ b/src/test/run-pass/regions-early-bound-used-in-bound-method.rs
@@ -0,0 +1,37 @@
+// Copyright 2012 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.
+
+// Tests that you can use a fn lifetime parameter as part of
+// the value for a type parameter in a bound.
+
+trait GetRef<'a> {
+    fn get(&self) -> &'a int;
+}
+
+struct Box<'a> {
+    t: &'a int
+}
+
+impl<'a> GetRef<'a> for Box<'a> {
+    fn get(&self) -> &'a int {
+        self.t
+    }
+}
+
+impl<'a> Box<'a> {
+    fn add<'b,G:GetRef<'b>>(&self, g2: G) -> int {
+        *self.t + *g2.get()
+    }
+}
+
+pub fn main() {
+    let b1 = Box { t: &3 };
+    assert_eq!(b1.add(b1), 6);
+}
diff --git a/src/test/run-pass/regions-early-bound-used-in-bound.rs b/src/test/run-pass/regions-early-bound-used-in-bound.rs
new file mode 100644
index 00000000000..22ea87c8d28
--- /dev/null
+++ b/src/test/run-pass/regions-early-bound-used-in-bound.rs
@@ -0,0 +1,35 @@
+// Copyright 2012 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.
+
+// Tests that you can use a fn lifetime parameter as part of
+// the value for a type parameter in a bound.
+
+trait GetRef<'a, T> {
+    fn get(&self) -> &'a T;
+}
+
+struct Box<'a, T> {
+    t: &'a T
+}
+
+impl<'a,T:Clone> GetRef<'a,T> for Box<'a,T> {
+    fn get(&self) -> &'a T {
+        self.t
+    }
+}
+
+fn add<'a,G:GetRef<'a, int>>(g1: G, g2: G) -> int {
+    *g1.get() + *g2.get()
+}
+
+pub fn main() {
+    let b1 = Box { t: &3 };
+    assert_eq!(add(b1, b1), 6);
+}
diff --git a/src/test/run-pass/regions-early-bound-used-in-type-param.rs b/src/test/run-pass/regions-early-bound-used-in-type-param.rs
new file mode 100644
index 00000000000..592f4822393
--- /dev/null
+++ b/src/test/run-pass/regions-early-bound-used-in-type-param.rs
@@ -0,0 +1,35 @@
+// Copyright 2012 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.
+
+// Tests that you can use a fn lifetime parameter as part of
+// the value for a type parameter in a bound.
+
+trait Get<T> {
+    fn get(&self) -> T;
+}
+
+struct Box<T> {
+    t: T
+}
+
+impl<T:Clone> Get<T> for Box<T> {
+    fn get(&self) -> T {
+        self.t.clone()
+    }
+}
+
+fn add<'a,G:Get<&'a int>>(g1: G, g2: G) -> int {
+    *g1.get() + *g2.get()
+}
+
+pub fn main() {
+    let b1 = Box { t: &3 };
+    assert_eq!(add(b1, b1), 6);
+}