Auto merge of #24553 - nikomatsakis:issue-22779-overconstrained-impl, r=pnkfelix

Rather than storing the relations between free-regions in a global
table, introduce a `FreeRegionMap` data structure. regionck computes the
`FreeRegionMap` for each fn and stores the result into the tcx so that
borrowck can use it (this could perhaps be refactored to have borrowck
recompute the map, but it's a bid tedious to recompute due to the
interaction of closures and free fns). The main reason to do this is
because of #22779 -- using a global table was incorrect because when
validating impl method signatures, we want to use the free region
relationships from the *trait*, not the impl.

Fixes #22779.

19 files changed, 447 insertions, 234 deletions

diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index 9093b3b9f5c..d4012f2057b 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -106,8 +106,10 @@ pub mod middle {
     pub mod entry;
     pub mod expr_use_visitor;
     pub mod fast_reject;
+    pub mod free_region;
     pub mod intrinsicck;
     pub mod infer;
+    pub mod implicator;
     pub mod lang_items;
     pub mod liveness;
     pub mod mem_categorization;
diff --git a/src/librustc/middle/free_region.rs b/src/librustc/middle/free_region.rs
new file mode 100644
index 00000000000..0c8a956f686
--- /dev/null
+++ b/src/librustc/middle/free_region.rs
@@ -0,0 +1,127 @@
+// Copyright 2012-2014 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.
+
+//! This file defines
+
+use middle::implicator::Implication;
+use middle::ty::{self, FreeRegion};
+use util::common::can_reach;
+use util::nodemap::FnvHashMap;
+use util::ppaux::Repr;
+
+#[derive(Clone)]
+pub struct FreeRegionMap {
+    /// `free_region_map` maps from a free region `a` to a list of
+    /// free regions `bs` such that `a <= b for all b in bs`
+    map: FnvHashMap<FreeRegion, Vec<FreeRegion>>,
+}
+
+impl FreeRegionMap {
+    pub fn new() -> FreeRegionMap {
+        FreeRegionMap { map: FnvHashMap() }
+    }
+
+    pub fn relate_free_regions_from_implications<'tcx>(&mut self,
+                                                       tcx: &ty::ctxt<'tcx>,
+                                                       implications: &[Implication<'tcx>])
+    {
+        for implication in implications {
+            debug!("implication: {}", implication.repr(tcx));
+            match *implication {
+                Implication::RegionSubRegion(_, ty::ReFree(free_a), ty::ReFree(free_b)) => {
+                    self.relate_free_regions(free_a, free_b);
+                }
+                Implication::RegionSubRegion(..) |
+                Implication::RegionSubClosure(..) |
+                Implication::RegionSubGeneric(..) |
+                Implication::Predicate(..) => {
+                }
+            }
+        }
+    }
+
+    pub fn relate_free_regions_from_predicates<'tcx>(&mut self,
+                                                     tcx: &ty::ctxt<'tcx>,
+                                                     predicates: &[ty::Predicate<'tcx>]) {
+        debug!("relate_free_regions_from_predicates(predicates={})", predicates.repr(tcx));
+        for predicate in predicates {
+            match *predicate {
+                ty::Predicate::Projection(..) |
+                ty::Predicate::Trait(..) |
+                ty::Predicate::Equate(..) |
+                ty::Predicate::TypeOutlives(..) => {
+                    // No region bounds here
+                }
+                ty::Predicate::RegionOutlives(ty::Binder(ty::OutlivesPredicate(r_a, r_b))) => {
+                    match (r_a, r_b) {
+                        (ty::ReFree(fr_a), ty::ReFree(fr_b)) => {
+                            // Record that `'a:'b`. Or, put another way, `'b <= 'a`.
+                            self.relate_free_regions(fr_b, fr_a);
+                        }
+                        _ => {
+                            // All named regions are instantiated with free regions.
+                            tcx.sess.bug(
+                                &format!("record_region_bounds: non free region: {} / {}",
+                                         r_a.repr(tcx),
+                                         r_b.repr(tcx)));
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    pub fn relate_free_regions(&mut self, sub: FreeRegion, sup: FreeRegion) {
+        let mut sups = self.map.entry(sub).or_insert(Vec::new());
+        if !sups.contains(&sup) {
+            sups.push(sup);
+        }
+    }
+
+    /// Determines whether two free regions have a subregion relationship
+    /// by walking the graph encoded in `map`.  Note that
+    /// it is possible that `sub != sup` and `sub <= sup` and `sup <= sub`
+    /// (that is, the user can give two different names to the same lifetime).
+    pub fn sub_free_region(&self, sub: FreeRegion, sup: FreeRegion) -> bool {
+        can_reach(&self.map, sub, sup)
+    }
+
+    /// Determines whether one region is a subregion of another.  This is intended to run *after
+    /// inference* and sadly the logic is somewhat duplicated with the code in infer.rs.
+    pub fn is_subregion_of(&self,
+                           tcx: &ty::ctxt,
+                           sub_region: ty::Region,
+                           super_region: ty::Region)
+                           -> bool {
+        debug!("is_subregion_of(sub_region={:?}, super_region={:?})",
+               sub_region, super_region);
+
+        sub_region == super_region || {
+            match (sub_region, super_region) {
+                (ty::ReEmpty, _) |
+                (_, ty::ReStatic) =>
+                    true,
+
+                (ty::ReScope(sub_scope), ty::ReScope(super_scope)) =>
+                    tcx.region_maps.is_subscope_of(sub_scope, super_scope),
+
+                (ty::ReScope(sub_scope), ty::ReFree(ref fr)) =>
+                    tcx.region_maps.is_subscope_of(sub_scope, fr.scope.to_code_extent()),
+
+                (ty::ReFree(sub_fr), ty::ReFree(super_fr)) =>
+                    self.sub_free_region(sub_fr, super_fr),
+
+                _ =>
+                    false,
+            }
+        }
+    }
+}
+
diff --git a/src/librustc_typeck/check/implicator.rs b/src/librustc/middle/implicator.rs
index a4a18c7cfde..0d6a1df7237 100644
--- a/src/librustc_typeck/check/implicator.rs
+++ b/src/librustc/middle/implicator.rs
@@ -10,11 +10,10 @@
 
 // #![warn(deprecated_mode)]
 
-use astconv::object_region_bounds;
 use middle::infer::{InferCtxt, GenericKind};
 use middle::subst::Substs;
 use middle::traits;
-use middle::ty::{self, ToPolyTraitRef, Ty};
+use middle::ty::{self, RegionEscape, ToPolyTraitRef, Ty};
 use middle::ty_fold::{TypeFoldable, TypeFolder};
 
 use std::rc::Rc;
@@ -423,6 +422,39 @@ impl<'a, 'tcx> Implicator<'a, 'tcx> {
     }
 }
 
+/// Given an object type like `SomeTrait+Send`, computes the lifetime
+/// bounds that must hold on the elided self type. These are derived
+/// from the declarations of `SomeTrait`, `Send`, and friends -- if
+/// they declare `trait SomeTrait : 'static`, for example, then
+/// `'static` would appear in the list. The hard work is done by
+/// `ty::required_region_bounds`, see that for more information.
+pub fn object_region_bounds<'tcx>(
+    tcx: &ty::ctxt<'tcx>,
+    principal: &ty::PolyTraitRef<'tcx>,
+    others: ty::BuiltinBounds)
+    -> Vec<ty::Region>
+{
+    // Since we don't actually *know* the self type for an object,
+    // this "open(err)" serves as a kind of dummy standin -- basically
+    // a skolemized type.
+    let open_ty = ty::mk_infer(tcx, ty::FreshTy(0));
+
+    // Note that we preserve the overall binding levels here.
+    assert!(!open_ty.has_escaping_regions());
+    let substs = tcx.mk_substs(principal.0.substs.with_self_ty(open_ty));
+    let trait_refs = vec!(ty::Binder(Rc::new(ty::TraitRef::new(principal.0.def_id, substs))));
+
+    let param_bounds = ty::ParamBounds {
+        region_bounds: Vec::new(),
+        builtin_bounds: others,
+        trait_bounds: trait_refs,
+        projection_bounds: Vec::new(), // not relevant to computing region bounds
+    };
+
+    let predicates = ty::predicates(tcx, open_ty, &param_bounds);
+    ty::required_region_bounds(tcx, open_ty, predicates)
+}
+
 impl<'tcx> Repr<'tcx> for Implication<'tcx> {
     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
         match *self {
diff --git a/src/librustc/middle/infer/mod.rs b/src/librustc/middle/infer/mod.rs
index b0921a266f3..63e4a5c8a2a 100644
--- a/src/librustc/middle/infer/mod.rs
+++ b/src/librustc/middle/infer/mod.rs
@@ -22,6 +22,7 @@ pub use middle::ty::IntVarValue;
 pub use self::freshen::TypeFreshener;
 pub use self::region_inference::GenericKind;
 
+use middle::free_region::FreeRegionMap;
 use middle::subst;
 use middle::subst::Substs;
 use middle::ty::{TyVid, IntVid, FloatVid, RegionVid, UnconstrainedNumeric};
@@ -855,8 +856,10 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         self.region_vars.new_bound(debruijn)
     }
 
-    pub fn resolve_regions_and_report_errors(&self, subject_node_id: ast::NodeId) {
-        let errors = self.region_vars.resolve_regions(subject_node_id);
+    pub fn resolve_regions_and_report_errors(&self,
+                                             free_regions: &FreeRegionMap,
+                                             subject_node_id: ast::NodeId) {
+        let errors = self.region_vars.resolve_regions(free_regions, subject_node_id);
         self.report_region_errors(&errors); // see error_reporting.rs
     }
 
diff --git a/src/librustc/middle/infer/region_inference/mod.rs b/src/librustc/middle/infer/region_inference/mod.rs
index e76468131e0..9de362fe360 100644
--- a/src/librustc/middle/infer/region_inference/mod.rs
+++ b/src/librustc/middle/infer/region_inference/mod.rs
@@ -21,6 +21,7 @@ use self::Classification::*;
 use super::{RegionVariableOrigin, SubregionOrigin, TypeTrace, MiscVariable};
 
 use rustc_data_structures::graph::{self, Direction, NodeIndex};
+use middle::free_region::FreeRegionMap;
 use middle::region;
 use middle::ty::{self, Ty};
 use middle::ty::{BoundRegion, FreeRegion, Region, RegionVid};
@@ -711,19 +712,19 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     /// fixed-point iteration to find region values which satisfy all
     /// constraints, assuming such values can be found; if they cannot,
     /// errors are reported.
-    pub fn resolve_regions(&self, subject_node: ast::NodeId) -> Vec<RegionResolutionError<'tcx>> {
+    pub fn resolve_regions(&self,
+                           free_regions: &FreeRegionMap,
+                           subject_node: ast::NodeId)
+                           -> Vec<RegionResolutionError<'tcx>>
+    {
         debug!("RegionVarBindings: resolve_regions()");
         let mut errors = vec!();
-        let v = self.infer_variable_values(&mut errors, subject_node);
+        let v = self.infer_variable_values(free_regions, &mut errors, subject_node);
         *self.values.borrow_mut() = Some(v);
         errors
     }
 
-    fn is_subregion_of(&self, sub: Region, sup: Region) -> bool {
-        self.tcx.region_maps.is_subregion_of(sub, sup)
-    }
-
-    fn lub_concrete_regions(&self, a: Region, b: Region) -> Region {
+    fn lub_concrete_regions(&self, free_regions: &FreeRegionMap, a: Region, b: Region) -> Region {
         match (a, b) {
           (ReLateBound(..), _) |
           (_, ReLateBound(..)) |
@@ -781,7 +782,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
           }
 
           (ReFree(ref a_fr), ReFree(ref b_fr)) => {
-             self.lub_free_regions(a_fr, b_fr)
+             self.lub_free_regions(free_regions, a_fr, b_fr)
           }
 
           // For these types, we cannot define any additional
@@ -796,23 +797,25 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     /// Computes a region that encloses both free region arguments. Guarantee that if the same two
     /// regions are given as argument, in any order, a consistent result is returned.
     fn lub_free_regions(&self,
+                        free_regions: &FreeRegionMap,
                         a: &FreeRegion,
                         b: &FreeRegion)
                         -> ty::Region
     {
         return match a.cmp(b) {
-            Less => helper(self, a, b),
-            Greater => helper(self, b, a),
+            Less => helper(self, free_regions, a, b),
+            Greater => helper(self, free_regions, b, a),
             Equal => ty::ReFree(*a)
         };
 
-        fn helper(this: &RegionVarBindings,
+        fn helper(_this: &RegionVarBindings,
+                  free_regions: &FreeRegionMap,
                   a: &FreeRegion,
                   b: &FreeRegion) -> ty::Region
         {
-            if this.tcx.region_maps.sub_free_region(*a, *b) {
+            if free_regions.sub_free_region(*a, *b) {
                 ty::ReFree(*b)
-            } else if this.tcx.region_maps.sub_free_region(*b, *a) {
+            } else if free_regions.sub_free_region(*b, *a) {
                 ty::ReFree(*a)
             } else {
                 ty::ReStatic
@@ -821,6 +824,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     }
 
     fn glb_concrete_regions(&self,
+                            free_regions: &FreeRegionMap,
                             a: Region,
                             b: Region)
                             -> RelateResult<'tcx, Region>
@@ -878,7 +882,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
             }
 
             (ReFree(ref a_fr), ReFree(ref b_fr)) => {
-                self.glb_free_regions(a_fr, b_fr)
+                self.glb_free_regions(free_regions, a_fr, b_fr)
             }
 
             // For these types, we cannot define any additional
@@ -898,23 +902,25 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     /// if the same two regions are given as argument, in any order, a consistent result is
     /// returned.
     fn glb_free_regions(&self,
+                        free_regions: &FreeRegionMap,
                         a: &FreeRegion,
                         b: &FreeRegion)
                         -> RelateResult<'tcx, ty::Region>
     {
         return match a.cmp(b) {
-            Less => helper(self, a, b),
-            Greater => helper(self, b, a),
+            Less => helper(self, free_regions, a, b),
+            Greater => helper(self, free_regions, b, a),
             Equal => Ok(ty::ReFree(*a))
         };
 
         fn helper<'a, 'tcx>(this: &RegionVarBindings<'a, 'tcx>,
+                            free_regions: &FreeRegionMap,
                             a: &FreeRegion,
                             b: &FreeRegion) -> RelateResult<'tcx, ty::Region>
         {
-            if this.tcx.region_maps.sub_free_region(*a, *b) {
+            if free_regions.sub_free_region(*a, *b) {
                 Ok(ty::ReFree(*a))
-            } else if this.tcx.region_maps.sub_free_region(*b, *a) {
+            } else if free_regions.sub_free_region(*b, *a) {
                 Ok(ty::ReFree(*b))
             } else {
                 this.intersect_scopes(ty::ReFree(*a), ty::ReFree(*b),
@@ -970,6 +976,7 @@ type RegionGraph = graph::Graph<(), Constraint>;
 
 impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     fn infer_variable_values(&self,
+                             free_regions: &FreeRegionMap,
                              errors: &mut Vec<RegionResolutionError<'tcx>>,
                              subject: ast::NodeId) -> Vec<VarValue>
     {
@@ -980,12 +987,13 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
         debug!("----() End constraint listing {:?}---", self.dump_constraints());
         graphviz::maybe_print_constraints_for(self, subject);
 
-        self.expansion(&mut var_data);
-        self.contraction(&mut var_data);
+        self.expansion(free_regions, &mut var_data);
+        self.contraction(free_regions, &mut var_data);
         let values =
-            self.extract_values_and_collect_conflicts(&var_data[..],
+            self.extract_values_and_collect_conflicts(free_regions,
+                                                      &var_data[..],
                                                       errors);
-        self.collect_concrete_region_errors(&values, errors);
+        self.collect_concrete_region_errors(free_regions, &values, errors);
         values
     }
 
@@ -1009,7 +1017,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
         }
     }
 
-    fn expansion(&self, var_data: &mut [VarData]) {
+    fn expansion(&self, free_regions: &FreeRegionMap, var_data: &mut [VarData]) {
         self.iterate_until_fixed_point("Expansion", |constraint| {
             debug!("expansion: constraint={} origin={}",
                    constraint.repr(self.tcx),
@@ -1020,14 +1028,14 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
             match *constraint {
               ConstrainRegSubVar(a_region, b_vid) => {
                 let b_data = &mut var_data[b_vid.index as usize];
-                self.expand_node(a_region, b_vid, b_data)
+                self.expand_node(free_regions, a_region, b_vid, b_data)
               }
               ConstrainVarSubVar(a_vid, b_vid) => {
                 match var_data[a_vid.index as usize].value {
                   NoValue | ErrorValue => false,
                   Value(a_region) => {
                     let b_node = &mut var_data[b_vid.index as usize];
-                    self.expand_node(a_region, b_vid, b_node)
+                    self.expand_node(free_regions, a_region, b_vid, b_node)
                   }
                 }
               }
@@ -1040,6 +1048,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     }
 
     fn expand_node(&self,
+                   free_regions: &FreeRegionMap,
                    a_region: Region,
                    b_vid: RegionVid,
                    b_data: &mut VarData)
@@ -1072,7 +1081,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
           }
 
           Value(cur_region) => {
-            let lub = self.lub_concrete_regions(a_region, cur_region);
+            let lub = self.lub_concrete_regions(free_regions, a_region, cur_region);
             if lub == cur_region {
                 return false;
             }
@@ -1093,6 +1102,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     }
 
     fn contraction(&self,
+                   free_regions: &FreeRegionMap,
                    var_data: &mut [VarData]) {
         self.iterate_until_fixed_point("Contraction", |constraint| {
             debug!("contraction: constraint={} origin={}",
@@ -1111,19 +1121,20 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
                   NoValue | ErrorValue => false,
                   Value(b_region) => {
                     let a_data = &mut var_data[a_vid.index as usize];
-                    self.contract_node(a_vid, a_data, b_region)
+                    self.contract_node(free_regions, a_vid, a_data, b_region)
                   }
                 }
               }
               ConstrainVarSubReg(a_vid, b_region) => {
                 let a_data = &mut var_data[a_vid.index as usize];
-                self.contract_node(a_vid, a_data, b_region)
+                self.contract_node(free_regions, a_vid, a_data, b_region)
               }
             }
         })
     }
 
     fn contract_node(&self,
+                     free_regions: &FreeRegionMap,
                      a_vid: RegionVid,
                      a_data: &mut VarData,
                      b_region: Region)
@@ -1143,19 +1154,23 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
 
             Value(a_region) => {
                 match a_data.classification {
-                    Expanding => check_node(self, a_vid, a_data, a_region, b_region),
-                    Contracting => adjust_node(self, a_vid, a_data, a_region, b_region),
+                    Expanding =>
+                        check_node(self, free_regions, a_vid, a_data, a_region, b_region),
+                    Contracting =>
+                        adjust_node(self, free_regions, a_vid, a_data, a_region, b_region),
                 }
             }
         };
 
         fn check_node(this: &RegionVarBindings,
+                      free_regions: &FreeRegionMap,
                       a_vid: RegionVid,
                       a_data: &mut VarData,
                       a_region: Region,
                       b_region: Region)
-                      -> bool {
-            if !this.is_subregion_of(a_region, b_region) {
+                      -> bool
+        {
+            if !free_regions.is_subregion_of(this.tcx, a_region, b_region) {
                 debug!("Setting {:?} to ErrorValue: {} not subregion of {}",
                        a_vid,
                        a_region.repr(this.tcx),
@@ -1166,12 +1181,13 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
         }
 
         fn adjust_node(this: &RegionVarBindings,
+                       free_regions: &FreeRegionMap,
                        a_vid: RegionVid,
                        a_data: &mut VarData,
                        a_region: Region,
                        b_region: Region)
                        -> bool {
-            match this.glb_concrete_regions(a_region, b_region) {
+            match this.glb_concrete_regions(free_regions, a_region, b_region) {
                 Ok(glb) => {
                     if glb == a_region {
                         false
@@ -1197,6 +1213,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
     }
 
     fn collect_concrete_region_errors(&self,
+                                      free_regions: &FreeRegionMap,
                                       values: &Vec<VarValue>,
                                       errors: &mut Vec<RegionResolutionError<'tcx>>)
     {
@@ -1204,7 +1221,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
         for verify in &*self.verifys.borrow() {
             match *verify {
                 VerifyRegSubReg(ref origin, sub, sup) => {
-                    if self.is_subregion_of(sub, sup) {
+                    if free_regions.is_subregion_of(self.tcx, sub, sup) {
                         continue;
                     }
 
@@ -1222,7 +1239,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
                     let sub = normalize(values, sub);
                     if sups.iter()
                            .map(|&sup| normalize(values, sup))
-                           .any(|sup| self.is_subregion_of(sub, sup))
+                           .any(|sup| free_regions.is_subregion_of(self.tcx, sub, sup))
                     {
                         continue;
                     }
@@ -1239,6 +1256,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
 
     fn extract_values_and_collect_conflicts(
         &self,
+        free_regions: &FreeRegionMap,
         var_data: &[VarData],
         errors: &mut Vec<RegionResolutionError<'tcx>>)
         -> Vec<VarValue>
@@ -1304,12 +1322,12 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
                     match var_data[idx].classification {
                         Expanding => {
                             self.collect_error_for_expanding_node(
-                                graph, var_data, &mut dup_vec,
+                                free_regions, graph, var_data, &mut dup_vec,
                                 node_vid, errors);
                         }
                         Contracting => {
                             self.collect_error_for_contracting_node(
-                                graph, var_data, &mut dup_vec,
+                                free_regions, graph, var_data, &mut dup_vec,
                                 node_vid, errors);
                         }
                     }
@@ -1355,13 +1373,13 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
         return graph;
     }
 
-    fn collect_error_for_expanding_node(
-        &self,
-        graph: &RegionGraph,
-        var_data: &[VarData],
-        dup_vec: &mut [u32],
-        node_idx: RegionVid,
-        errors: &mut Vec<RegionResolutionError<'tcx>>)
+    fn collect_error_for_expanding_node(&self,
+                                        free_regions: &FreeRegionMap,
+                                        graph: &RegionGraph,
+                                        var_data: &[VarData],
+                                        dup_vec: &mut [u32],
+                                        node_idx: RegionVid,
+                                        errors: &mut Vec<RegionResolutionError<'tcx>>)
     {
         // Errors in expanding nodes result from a lower-bound that is
         // not contained by an upper-bound.
@@ -1394,8 +1412,9 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
 
         for lower_bound in &lower_bounds {
             for upper_bound in &upper_bounds {
-                if !self.is_subregion_of(lower_bound.region,
-                                         upper_bound.region) {
+                if !free_regions.is_subregion_of(self.tcx,
+                                                 lower_bound.region,
+                                                 upper_bound.region) {
                     debug!("pushing SubSupConflict sub: {:?} sup: {:?}",
                            lower_bound.region, upper_bound.region);
                     errors.push(SubSupConflict(
@@ -1420,6 +1439,7 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
 
     fn collect_error_for_contracting_node(
         &self,
+        free_regions: &FreeRegionMap,
         graph: &RegionGraph,
         var_data: &[VarData],
         dup_vec: &mut [u32],
@@ -1438,7 +1458,8 @@ impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
 
         for upper_bound_1 in &upper_bounds {
             for upper_bound_2 in &upper_bounds {
-                match self.glb_concrete_regions(upper_bound_1.region,
+                match self.glb_concrete_regions(free_regions,
+                                                upper_bound_1.region,
                                                 upper_bound_2.region) {
                   Ok(_) => {}
                   Err(_) => {
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index 2f7296051c5..2c510b5f1d3 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -17,9 +17,8 @@
 //! `middle/typeck/infer/region_inference.rs`
 
 use session::Session;
-use middle::ty::{self, Ty, FreeRegion};
+use middle::ty::{self, Ty};
 use util::nodemap::{FnvHashMap, FnvHashSet, NodeMap};
-use util::common::can_reach;
 
 use std::cell::RefCell;
 use syntax::codemap::{self, Span};
@@ -234,14 +233,6 @@ pub struct RegionMaps {
     /// which that variable is declared.
     var_map: RefCell<NodeMap<CodeExtent>>,
 
-    /// `free_region_map` maps from a free region `a` to a list of
-    /// free regions `bs` such that `a <= b for all b in bs`
-    ///
-    /// NB. the free region map is populated during type check as we
-    /// check each function. See the function `relate_free_regions`
-    /// for more information.
-    free_region_map: RefCell<FnvHashMap<FreeRegion, Vec<FreeRegion>>>,
-
     /// `rvalue_scopes` includes entries for those expressions whose cleanup scope is
     /// larger than the default. The map goes from the expression id
     /// to the cleanup scope id. For rvalues not present in this
@@ -390,13 +381,6 @@ impl RegionMaps {
             e(child, parent)
         }
     }
-    pub fn each_encl_free_region<E>(&self, mut e:E) where E: FnMut(&FreeRegion, &FreeRegion) {
-        for (child, parents) in self.free_region_map.borrow().iter() {
-            for parent in parents.iter() {
-                e(child, parent)
-            }
-        }
-    }
     pub fn each_rvalue_scope<E>(&self, mut e:E) where E: FnMut(&ast::NodeId, &CodeExtent) {
         for (child, parent) in self.rvalue_scopes.borrow().iter() {
             e(child, parent)
@@ -408,21 +392,6 @@ impl RegionMaps {
         }
     }
 
-    pub fn relate_free_regions(&self, sub: FreeRegion, sup: FreeRegion) {
-        match self.free_region_map.borrow_mut().get_mut(&sub) {
-            Some(sups) => {
-                if !sups.iter().any(|x| x == &sup) {
-                    sups.push(sup);
-                }
-                return;
-            }
-            None => {}
-        }
-
-        debug!("relate_free_regions(sub={:?}, sup={:?})", sub, sup);
-        self.free_region_map.borrow_mut().insert(sub, vec!(sup));
-    }
-
     /// Records that `sub_fn` is defined within `sup_fn`. These ids
     /// should be the id of the block that is the fn body, which is
     /// also the root of the region hierarchy for that fn.
@@ -567,56 +536,6 @@ impl RegionMaps {
         return true;
     }
 
-    /// Determines whether two free regions have a subregion relationship
-    /// by walking the graph encoded in `free_region_map`.  Note that
-    /// it is possible that `sub != sup` and `sub <= sup` and `sup <= sub`
-    /// (that is, the user can give two different names to the same lifetime).
-    pub fn sub_free_region(&self, sub: FreeRegion, sup: FreeRegion) -> bool {
-        can_reach(&*self.free_region_map.borrow(), sub, sup)
-    }
-
-    /// Determines whether one region is a subregion of another.  This is intended to run *after
-    /// inference* and sadly the logic is somewhat duplicated with the code in infer.rs.
-    pub fn is_subregion_of(&self,
-                           sub_region: ty::Region,
-                           super_region: ty::Region)
-                           -> bool {
-        debug!("is_subregion_of(sub_region={:?}, super_region={:?})",
-               sub_region, super_region);
-
-        sub_region == super_region || {
-            match (sub_region, super_region) {
-                (ty::ReEmpty, _) |
-                (_, ty::ReStatic) => {
-                    true
-                }
-
-                (ty::ReScope(sub_scope), ty::ReScope(super_scope)) => {
-                    self.is_subscope_of(sub_scope, super_scope)
-                }
-
-                (ty::ReScope(sub_scope), ty::ReFree(ref fr)) => {
-                    self.is_subscope_of(sub_scope, fr.scope.to_code_extent())
-                }
-
-                (ty::ReFree(sub_fr), ty::ReFree(super_fr)) => {
-                    self.sub_free_region(sub_fr, super_fr)
-                }
-
-                (ty::ReEarlyBound(data_a), ty::ReEarlyBound(data_b)) => {
-                    // This case is used only to make sure that explicitly-
-                    // specified `Self` types match the real self type in
-                    // implementations. Yuck.
-                    data_a == data_b
-                }
-
-                _ => {
-                    false
-                }
-            }
-        }
-    }
-
     /// Finds the nearest common ancestor (if any) of two scopes.  That is, finds the smallest
     /// scope which is greater than or equal to both `scope_a` and `scope_b`.
     pub fn nearest_common_ancestor(&self,
@@ -1291,7 +1210,6 @@ pub fn resolve_crate(sess: &Session, krate: &ast::Crate) -> RegionMaps {
     let maps = RegionMaps {
         scope_map: RefCell::new(FnvHashMap()),
         var_map: RefCell::new(NodeMap()),
-        free_region_map: RefCell::new(FnvHashMap()),
         rvalue_scopes: RefCell::new(NodeMap()),
         terminating_scopes: RefCell::new(FnvHashSet()),
         fn_tree: RefCell::new(NodeMap()),
diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index 8809abdd70e..b221c4bb685 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -15,6 +15,7 @@ pub use self::FulfillmentErrorCode::*;
 pub use self::Vtable::*;
 pub use self::ObligationCauseCode::*;
 
+use middle::free_region::FreeRegionMap;
 use middle::subst;
 use middle::ty::{self, HasProjectionTypes, Ty};
 use middle::ty_fold::TypeFoldable;
@@ -424,7 +425,8 @@ pub fn normalize_param_env_or_error<'a,'tcx>(unnormalized_env: ty::ParameterEnvi
         }
     };
 
-    infcx.resolve_regions_and_report_errors(body_id);
+    let free_regions = FreeRegionMap::new();
+    infcx.resolve_regions_and_report_errors(&free_regions, body_id);
     let predicates = match infcx.fully_resolve(&predicates) {
         Ok(predicates) => predicates,
         Err(fixup_err) => {
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 2c94399f921..232e962ed4d 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -45,12 +45,14 @@ use middle::check_const;
 use middle::const_eval;
 use middle::def::{self, DefMap, ExportMap};
 use middle::dependency_format;
+use middle::free_region::FreeRegionMap;
 use middle::lang_items::{FnTraitLangItem, FnMutTraitLangItem, FnOnceTraitLangItem};
 use middle::mem_categorization as mc;
 use middle::region;
 use middle::resolve_lifetime;
 use middle::infer;
 use middle::pat_util;
+use middle::region::RegionMaps;
 use middle::stability;
 use middle::subst::{self, ParamSpace, Subst, Substs, VecPerParamSpace};
 use middle::traits;
@@ -620,7 +622,14 @@ pub struct ctxt<'tcx> {
 
     pub named_region_map: resolve_lifetime::NamedRegionMap,
 
-    pub region_maps: middle::region::RegionMaps,
+    pub region_maps: RegionMaps,
+
+    // For each fn declared in the local crate, type check stores the
+    // free-region relationships that were deduced from its where
+    // clauses and parameter types. These are then read-again by
+    // borrowck. (They are not used during trans, and hence are not
+    // serialized or needed for cross-crate fns.)
+    free_region_maps: RefCell<NodeMap<FreeRegionMap>>,
 
     /// Stores the types for various nodes in the AST.  Note that this table
     /// is not guaranteed to be populated until after typeck.  See
@@ -795,6 +804,15 @@ impl<'tcx> ctxt<'tcx> {
     pub fn node_type_insert(&self, id: NodeId, ty: Ty<'tcx>) {
         self.node_types.borrow_mut().insert(id, ty);
     }
+
+    pub fn store_free_region_map(&self, id: NodeId, map: FreeRegionMap) {
+        self.free_region_maps.borrow_mut()
+                             .insert(id, map);
+    }
+
+    pub fn free_region_map(&self, id: NodeId) -> FreeRegionMap {
+        self.free_region_maps.borrow()[&id].clone()
+    }
 }
 
 // Flags that we track on types. These flags are propagated upwards
@@ -2546,7 +2564,7 @@ pub fn mk_ctxt<'tcx>(s: Session,
                      named_region_map: resolve_lifetime::NamedRegionMap,
                      map: ast_map::Map<'tcx>,
                      freevars: RefCell<FreevarMap>,
-                     region_maps: middle::region::RegionMaps,
+                     region_maps: RegionMaps,
                      lang_items: middle::lang_items::LanguageItems,
                      stability: stability::Index) -> ctxt<'tcx>
 {
@@ -2561,11 +2579,12 @@ pub fn mk_ctxt<'tcx>(s: Session,
         region_interner: RefCell::new(FnvHashMap()),
         types: common_types,
         named_region_map: named_region_map,
+        region_maps: region_maps,
+        free_region_maps: RefCell::new(FnvHashMap()),
         item_variance_map: RefCell::new(DefIdMap()),
         variance_computed: Cell::new(false),
         sess: s,
         def_map: def_map,
-        region_maps: region_maps,
         node_types: RefCell::new(FnvHashMap()),
         item_substs: RefCell::new(NodeMap()),
         impl_trait_refs: RefCell::new(NodeMap()),
@@ -6537,14 +6556,6 @@ pub fn construct_parameter_environment<'a,'tcx>(
     let bounds = liberate_late_bound_regions(tcx, free_id_outlive, &ty::Binder(bounds));
     let predicates = bounds.predicates.into_vec();
 
-    //
-    // Compute region bounds. For now, these relations are stored in a
-    // global table on the tcx, so just enter them there. I'm not
-    // crazy about this scheme, but it's convenient, at least.
-    //
-
-    record_region_bounds(tcx, &*predicates);
-
     debug!("construct_parameter_environment: free_id={:?} free_subst={:?} predicates={:?}",
            free_id,
            free_substs.repr(tcx),
@@ -6573,37 +6584,7 @@ pub fn construct_parameter_environment<'a,'tcx>(
     };
 
     let cause = traits::ObligationCause::misc(span, free_id);
-    return traits::normalize_param_env_or_error(unnormalized_env, cause);
-
-    fn record_region_bounds<'tcx>(tcx: &ty::ctxt<'tcx>, predicates: &[ty::Predicate<'tcx>]) {
-        debug!("record_region_bounds(predicates={:?})", predicates.repr(tcx));
-
-        for predicate in predicates {
-            match *predicate {
-                Predicate::Projection(..) |
-                Predicate::Trait(..) |
-                Predicate::Equate(..) |
-                Predicate::TypeOutlives(..) => {
-                    // No region bounds here
-                }
-                Predicate::RegionOutlives(ty::Binder(ty::OutlivesPredicate(r_a, r_b))) => {
-                    match (r_a, r_b) {
-                        (ty::ReFree(fr_a), ty::ReFree(fr_b)) => {
-                            // Record that `'a:'b`. Or, put another way, `'b <= 'a`.
-                            tcx.region_maps.relate_free_regions(fr_b, fr_a);
-                        }
-                        _ => {
-                            // All named regions are instantiated with free regions.
-                            tcx.sess.bug(
-                                &format!("record_region_bounds: non free region: {} / {}",
-                                         r_a.repr(tcx),
-                                         r_b.repr(tcx)));
-                        }
-                    }
-                }
-            }
-        }
-    }
+    traits::normalize_param_env_or_error(unnormalized_env, cause)
 }
 
 impl BorrowKind {
diff --git a/src/librustc_borrowck/borrowck/mod.rs b/src/librustc_borrowck/borrowck/mod.rs
index 502321d0759..aedc0d23cfe 100644
--- a/src/librustc_borrowck/borrowck/mod.rs
+++ b/src/librustc_borrowck/borrowck/mod.rs
@@ -27,9 +27,11 @@ use rustc::middle::dataflow::DataFlowOperator;
 use rustc::middle::dataflow::KillFrom;
 use rustc::middle::expr_use_visitor as euv;
 use rustc::middle::mem_categorization as mc;
+use rustc::middle::free_region::FreeRegionMap;
 use rustc::middle::region;
 use rustc::middle::ty::{self, Ty};
 use rustc::util::ppaux::{note_and_explain_region, Repr, UserString};
+use std::mem;
 use std::rc::Rc;
 use std::string::String;
 use syntax::ast;
@@ -56,7 +58,20 @@ pub type LoanDataFlow<'a, 'tcx> = DataFlowContext<'a, 'tcx, LoanDataFlowOperator
 impl<'a, 'tcx, 'v> Visitor<'v> for BorrowckCtxt<'a, 'tcx> {
     fn visit_fn(&mut self, fk: FnKind<'v>, fd: &'v FnDecl,
                 b: &'v Block, s: Span, id: ast::NodeId) {
-        borrowck_fn(self, fk, fd, b, s, id);
+        match fk {
+            visit::FkItemFn(..) |
+            visit::FkMethod(..) => {
+                let new_free_region_map = self.tcx.free_region_map(id);
+                let old_free_region_map =
+                    mem::replace(&mut self.free_region_map, new_free_region_map);
+                borrowck_fn(self, fk, fd, b, s, id);
+                self.free_region_map = old_free_region_map;
+            }
+
+            visit::FkFnBlock => {
+                borrowck_fn(self, fk, fd, b, s, id);
+            }
+        }
     }
 
     fn visit_item(&mut self, item: &ast::Item) {
@@ -67,6 +82,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for BorrowckCtxt<'a, 'tcx> {
 pub fn check_crate(tcx: &ty::ctxt) {
     let mut bccx = BorrowckCtxt {
         tcx: tcx,
+        free_region_map: FreeRegionMap::new(),
         stats: BorrowStats {
             loaned_paths_same: 0,
             loaned_paths_imm: 0,
@@ -129,11 +145,13 @@ fn borrowck_fn(this: &mut BorrowckCtxt,
     let cfg = cfg::CFG::new(this.tcx, body);
     let AnalysisData { all_loans,
                        loans: loan_dfcx,
-                       move_data:flowed_moves } =
+                       move_data: flowed_moves } =
         build_borrowck_dataflow_data(this, fk, decl, &cfg, body, sp, id);
 
     move_data::fragments::instrument_move_fragments(&flowed_moves.move_data,
-                                                    this.tcx, sp, id);
+                                                    this.tcx,
+                                                    sp,
+                                                    id);
 
     check_loans::check_loans(this,
                              &loan_dfcx,
@@ -152,7 +170,9 @@ fn build_borrowck_dataflow_data<'a, 'tcx>(this: &mut BorrowckCtxt<'a, 'tcx>,
                                           cfg: &cfg::CFG,
                                           body: &ast::Block,
                                           sp: Span,
-                                          id: ast::NodeId) -> AnalysisData<'a, 'tcx> {
+                                          id: ast::NodeId)
+                                          -> AnalysisData<'a, 'tcx>
+{
     // Check the body of fn items.
     let id_range = ast_util::compute_id_range_for_fn_body(fk, decl, body, sp, id);
     let (all_loans, move_data) =
@@ -203,10 +223,13 @@ impl<'a> FnPartsWithCFG<'a> {
 /// the `BorrowckCtxt` itself , e.g. the flowgraph visualizer.
 pub fn build_borrowck_dataflow_data_for_fn<'a, 'tcx>(
     tcx: &'a ty::ctxt<'tcx>,
-    input: FnPartsWithCFG<'a>) -> (BorrowckCtxt<'a, 'tcx>, AnalysisData<'a, 'tcx>) {
+    input: FnPartsWithCFG<'a>)
+    -> (BorrowckCtxt<'a, 'tcx>, AnalysisData<'a, 'tcx>)
+{
 
     let mut bccx = BorrowckCtxt {
         tcx: tcx,
+        free_region_map: FreeRegionMap::new(),
         stats: BorrowStats {
             loaned_paths_same: 0,
             loaned_paths_imm: 0,
@@ -234,6 +257,18 @@ pub fn build_borrowck_dataflow_data_for_fn<'a, 'tcx>(
 pub struct BorrowckCtxt<'a, 'tcx: 'a> {
     tcx: &'a ty::ctxt<'tcx>,
 
+    // Hacky. As we visit various fns, we have to load up the
+    // free-region map for each one. This map is computed by during
+    // typeck for each fn item and stored -- closures just use the map
+    // from the fn item that encloses them. Since we walk the fns in
+    // order, we basically just overwrite this field as we enter a fn
+    // item and restore it afterwards in a stack-like fashion. Then
+    // the borrow checking code can assume that `free_region_map` is
+    // always the correct map for the current fn. Feels like it'd be
+    // better to just recompute this, rather than store it, but it's a
+    // bit of a pain to factor that code out at the moment.
+    free_region_map: FreeRegionMap,
+
     // Statistics:
     stats: BorrowStats
 }
@@ -518,8 +553,9 @@ pub enum MovedValueUseKind {
 
 impl<'a, 'tcx> BorrowckCtxt<'a, 'tcx> {
     pub fn is_subregion_of(&self, r_sub: ty::Region, r_sup: ty::Region)
-                           -> bool {
-        self.tcx.region_maps.is_subregion_of(r_sub, r_sup)
+                           -> bool
+    {
+        self.free_region_map.is_subregion_of(self.tcx, r_sub, r_sup)
     }
 
     pub fn report(&self, err: BckError<'tcx>) {
diff --git a/src/librustc_driver/test.rs b/src/librustc_driver/test.rs
index 12b16e95a71..a8cf7533179 100644
--- a/src/librustc_driver/test.rs
+++ b/src/librustc_driver/test.rs
@@ -16,6 +16,7 @@ use driver;
 use rustc_lint;
 use rustc_resolve as resolve;
 use rustc_typeck::middle::lang_items;
+use rustc_typeck::middle::free_region::FreeRegionMap;
 use rustc_typeck::middle::region::{self, CodeExtent, DestructionScopeData};
 use rustc_typeck::middle::resolve_lifetime;
 use rustc_typeck::middle::stability;
@@ -138,7 +139,8 @@ fn test_env<F>(source_string: &str,
                           stability::Index::new(krate));
     let infcx = infer::new_infer_ctxt(&tcx);
     body(Env { infcx: &infcx });
-    infcx.resolve_regions_and_report_errors(ast::CRATE_NODE_ID);
+    let free_regions = FreeRegionMap::new();
+    infcx.resolve_regions_and_report_errors(&free_regions, ast::CRATE_NODE_ID);
     assert_eq!(tcx.sess.err_count(), expected_err_count);
 }
 
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 78797d086c6..9dbf918ddb5 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -51,6 +51,7 @@
 use middle::astconv_util::{prim_ty_to_ty, check_path_args, NO_TPS, NO_REGIONS};
 use middle::const_eval;
 use middle::def;
+use middle::implicator::object_region_bounds;
 use middle::resolve_lifetime as rl;
 use middle::privacy::{AllPublic, LastMod};
 use middle::subst::{FnSpace, TypeSpace, SelfSpace, Subst, Substs};
@@ -2087,39 +2088,6 @@ fn compute_object_lifetime_bound<'tcx>(
     return r;
 }
 
-/// Given an object type like `SomeTrait+Send`, computes the lifetime
-/// bounds that must hold on the elided self type. These are derived
-/// from the declarations of `SomeTrait`, `Send`, and friends -- if
-/// they declare `trait SomeTrait : 'static`, for example, then
-/// `'static` would appear in the list. The hard work is done by
-/// `ty::required_region_bounds`, see that for more information.
-pub fn object_region_bounds<'tcx>(
-    tcx: &ty::ctxt<'tcx>,
-    principal: &ty::PolyTraitRef<'tcx>,
-    others: ty::BuiltinBounds)
-    -> Vec<ty::Region>
-{
-    // Since we don't actually *know* the self type for an object,
-    // this "open(err)" serves as a kind of dummy standin -- basically
-    // a skolemized type.
-    let open_ty = ty::mk_infer(tcx, ty::FreshTy(0));
-
-    // Note that we preserve the overall binding levels here.
-    assert!(!open_ty.has_escaping_regions());
-    let substs = tcx.mk_substs(principal.0.substs.with_self_ty(open_ty));
-    let trait_refs = vec!(ty::Binder(Rc::new(ty::TraitRef::new(principal.0.def_id, substs))));
-
-    let param_bounds = ty::ParamBounds {
-        region_bounds: Vec::new(),
-        builtin_bounds: others,
-        trait_bounds: trait_refs,
-        projection_bounds: Vec::new(), // not relevant to computing region bounds
-    };
-
-    let predicates = ty::predicates(tcx, open_ty, &param_bounds);
-    ty::required_region_bounds(tcx, open_ty, predicates)
-}
-
 pub struct PartitionedBounds<'a> {
     pub builtin_bounds: ty::BuiltinBounds,
     pub trait_bounds: Vec<&'a ast::PolyTraitRef>,
diff --git a/src/librustc_typeck/check/compare_method.rs b/src/librustc_typeck/check/compare_method.rs
index 532277d75b2..c4ee7e79570 100644
--- a/src/librustc_typeck/check/compare_method.rs
+++ b/src/librustc_typeck/check/compare_method.rs
@@ -8,6 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use middle::free_region::FreeRegionMap;
 use middle::infer;
 use middle::traits;
 use middle::ty::{self};
@@ -354,9 +355,19 @@ pub fn compare_impl_method<'tcx>(tcx: &ty::ctxt<'tcx>,
         Ok(_) => {}
     }
 
-    // Finally, resolve all regions. This catches wily misuses of lifetime
-    // parameters.
-    infcx.resolve_regions_and_report_errors(impl_m_body_id);
+    // Finally, resolve all regions. This catches wily misuses of
+    // lifetime parameters. We have to build up a plausible lifetime
+    // environment based on what we find in the trait. We could also
+    // include the obligations derived from the method argument types,
+    // but I don't think it's necessary -- after all, those are still
+    // in effect when type-checking the body, and all the
+    // where-clauses in the header etc should be implied by the trait
+    // anyway, so it shouldn't be needed there either. Anyway, we can
+    // always add more relations later (it's backwards compat).
+    let mut free_regions = FreeRegionMap::new();
+    free_regions.relate_free_regions_from_predicates(tcx, &trait_param_env.caller_bounds);
+
+    infcx.resolve_regions_and_report_errors(&free_regions, impl_m_body_id);
 
     fn check_region_bounds_on_impl_method<'tcx>(tcx: &ty::ctxt<'tcx>,
                                                 span: Span,
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 348846b8ad4..e87deba2808 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -132,7 +132,6 @@ pub mod dropck;
 pub mod _match;
 pub mod vtable;
 pub mod writeback;
-pub mod implicator;
 pub mod regionck;
 pub mod coercion;
 pub mod demand;
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index 6dfc1e0ea6c..2e8c5730e67 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -85,8 +85,9 @@
 use astconv::AstConv;
 use check::dropck;
 use check::FnCtxt;
-use check::implicator;
 use check::vtable;
+use middle::free_region::FreeRegionMap;
+use middle::implicator;
 use middle::mem_categorization as mc;
 use middle::region::CodeExtent;
 use middle::subst::Substs;
@@ -124,6 +125,8 @@ pub fn regionck_expr(fcx: &FnCtxt, e: &ast::Expr) {
 
 pub fn regionck_item(fcx: &FnCtxt, item: &ast::Item) {
     let mut rcx = Rcx::new(fcx, RepeatingScope(item.id), item.id, Subject(item.id));
+    let tcx = fcx.tcx();
+    rcx.free_region_map.relate_free_regions_from_predicates(tcx, &fcx.inh.param_env.caller_bounds);
     rcx.visit_region_obligations(item.id);
     rcx.resolve_regions_and_report_errors();
 }
@@ -135,12 +138,21 @@ pub fn regionck_fn(fcx: &FnCtxt,
                    blk: &ast::Block) {
     debug!("regionck_fn(id={})", fn_id);
     let mut rcx = Rcx::new(fcx, RepeatingScope(blk.id), blk.id, Subject(fn_id));
+
     if fcx.err_count_since_creation() == 0 {
         // regionck assumes typeck succeeded
         rcx.visit_fn_body(fn_id, decl, blk, fn_span);
     }
 
+    let tcx = fcx.tcx();
+    rcx.free_region_map.relate_free_regions_from_predicates(tcx, &fcx.inh.param_env.caller_bounds);
+
     rcx.resolve_regions_and_report_errors();
+
+    // For the top-level fn, store the free-region-map. We don't store
+    // any map for closures; they just share the same map as the
+    // function that created them.
+    fcx.tcx().store_free_region_map(fn_id, rcx.free_region_map);
 }
 
 /// Checks that the types in `component_tys` are well-formed. This will add constraints into the
@@ -167,6 +179,8 @@ pub struct Rcx<'a, 'tcx: 'a> {
 
     region_bound_pairs: Vec<(ty::Region, GenericKind<'tcx>)>,
 
+    free_region_map: FreeRegionMap,
+
     // id of innermost fn body id
     body_id: ast::NodeId,
 
@@ -191,7 +205,8 @@ impl<'a, 'tcx> Rcx<'a, 'tcx> {
               repeating_scope: initial_repeating_scope,
               body_id: initial_body_id,
               subject: subject,
-              region_bound_pairs: Vec::new()
+              region_bound_pairs: Vec::new(),
+              free_region_map: FreeRegionMap::new(),
         }
     }
 
@@ -277,13 +292,16 @@ impl<'a, 'tcx> Rcx<'a, 'tcx> {
             }
         };
 
-        let len = self.region_bound_pairs.len();
+        let old_region_bounds_pairs_len = self.region_bound_pairs.len();
+
         let old_body_id = self.set_body_id(body.id);
         self.relate_free_regions(&fn_sig[..], body.id, span);
         link_fn_args(self, CodeExtent::from_node_id(body.id), &fn_decl.inputs[..]);
         self.visit_block(body);
         self.visit_region_obligations(body.id);
-        self.region_bound_pairs.truncate(len);
+
+        self.region_bound_pairs.truncate(old_region_bounds_pairs_len);
+
         self.set_body_id(old_body_id);
     }
 
@@ -340,16 +358,18 @@ impl<'a, 'tcx> Rcx<'a, 'tcx> {
             let body_scope = ty::ReScope(body_scope);
             let implications = implicator::implications(self.fcx.infcx(), self.fcx, body_id,
                                                         ty, body_scope, span);
+
+            // Record any relations between free regions that we observe into the free-region-map.
+            self.free_region_map.relate_free_regions_from_implications(tcx, &implications);
+
+            // But also record other relationships, such as `T:'x`,
+            // that don't go into the free-region-map but which we use
+            // here.
             for implication in implications {
                 debug!("implication: {}", implication.repr(tcx));
                 match implication {
                     implicator::Implication::RegionSubRegion(_,
                                                              ty::ReFree(free_a),
-                                                             ty::ReFree(free_b)) => {
-                        tcx.region_maps.relate_free_regions(free_a, free_b);
-                    }
-                    implicator::Implication::RegionSubRegion(_,
-                                                             ty::ReFree(free_a),
                                                              ty::ReInfer(ty::ReVar(vid_b))) => {
                         self.fcx.inh.infcx.add_given(free_a, vid_b);
                     }
@@ -388,7 +408,8 @@ impl<'a, 'tcx> Rcx<'a, 'tcx> {
             }
         };
 
-        self.fcx.infcx().resolve_regions_and_report_errors(subject_node_id);
+        self.fcx.infcx().resolve_regions_and_report_errors(&self.free_region_map,
+                                                           subject_node_id);
     }
 }
 
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 5ed93703d97..23959d578bf 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -68,6 +68,7 @@ use astconv::{self, AstConv, ty_of_arg, ast_ty_to_ty, ast_region_to_region};
 use middle::def;
 use constrained_type_params as ctp;
 use middle::lang_items::SizedTraitLangItem;
+use middle::free_region::FreeRegionMap;
 use middle::region;
 use middle::resolve_lifetime;
 use middle::subst::{Substs, FnSpace, ParamSpace, SelfSpace, TypeSpace, VecPerParamSpace};
@@ -2158,7 +2159,16 @@ fn check_method_self_type<'a, 'tcx, RS:RegionScope>(
                 format!("mismatched self type: expected `{}`",
                         ppaux::ty_to_string(tcx, required_type))
         }));
-        infcx.resolve_regions_and_report_errors(body_id);
+
+        // We could conceviably add more free-reion relations here,
+        // but since this code is just concerned with checking that
+        // the `&Self` types etc match up, it's not really necessary.
+        // It would just allow people to be more approximate in some
+        // cases. In any case, we can do it later as we feel the need;
+        // I'd like this function to go away eventually.
+        let free_regions = FreeRegionMap::new();
+
+        infcx.resolve_regions_and_report_errors(&free_regions, body_id);
     }
 
     fn liberate_early_bound_regions<'tcx,T>(
diff --git a/src/test/compile-fail/region-bound-extra-bound-in-impl.rs b/src/test/compile-fail/region-bound-extra-bound-in-impl.rs
new file mode 100644
index 00000000000..5bcc6be4c3d
--- /dev/null
+++ b/src/test/compile-fail/region-bound-extra-bound-in-impl.rs
@@ -0,0 +1,25 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Regression test for issue #22779. An extra where clause was
+// permitted on the impl that is not present on the trait.
+
+trait Tr<'a, T> {
+    fn renew<'b: 'a>(self) -> &'b mut [T];
+}
+
+impl<'a, T> Tr<'a, T> for &'a mut [T] {
+    fn renew<'b: 'a>(self) -> &'b mut [T] where 'a: 'b {
+        //~^ ERROR lifetime bound not satisfied
+        &mut self[..]
+    }
+}
+
+fn main() { }
diff --git a/src/test/compile-fail/region-bound-extra-bound-in-inherent-impl.rs b/src/test/compile-fail/region-bound-extra-bound-in-inherent-impl.rs
new file mode 100644
index 00000000000..c1df057b396
--- /dev/null
+++ b/src/test/compile-fail/region-bound-extra-bound-in-inherent-impl.rs
@@ -0,0 +1,26 @@
+// Copyright 2014 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.
+
+// Test related to #22779. In this case, the impl is an inherent impl,
+// so it doesn't have to match any trait, so no error results.
+
+#![feature(rustc_attrs)]
+#![allow(dead_code)]
+
+struct MySlice<'a, T:'a>(&'a mut [T]);
+
+impl<'a, T> MySlice<'a, T> {
+    fn renew<'b: 'a>(self) -> &'b mut [T] where 'a: 'b {
+        &mut self.0[..]
+    }
+}
+
+#[rustc_error]
+fn main() { } //~ ERROR compilation successful
diff --git a/src/test/compile-fail/region-bound-same-bounds-in-trait-and-impl.rs b/src/test/compile-fail/region-bound-same-bounds-in-trait-and-impl.rs
new file mode 100644
index 00000000000..3115e5a9a43
--- /dev/null
+++ b/src/test/compile-fail/region-bound-same-bounds-in-trait-and-impl.rs
@@ -0,0 +1,27 @@
+// Copyright 2014 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.
+
+// Test related to #22779, but where the `'a:'b` relation
+// appears in the trait too. No error here.
+
+#![feature(rustc_attrs)]
+
+trait Tr<'a, T> {
+    fn renew<'b: 'a>(self) -> &'b mut [T] where 'a: 'b;
+}
+
+impl<'a, T> Tr<'a, T> for &'a mut [T] {
+    fn renew<'b: 'a>(self) -> &'b mut [T] where 'a: 'b {
+        &mut self[..]
+    }
+}
+
+#[rustc_error]
+fn main() { } //~ ERROR compilation successful
diff --git a/src/test/compile-fail/regions-bound-missing-bound-in-impl.rs b/src/test/compile-fail/regions-bound-missing-bound-in-impl.rs
index 278ccd3c119..abffd33e3f8 100644
--- a/src/test/compile-fail/regions-bound-missing-bound-in-impl.rs
+++ b/src/test/compile-fail/regions-bound-missing-bound-in-impl.rs
@@ -50,7 +50,9 @@ impl<'a, 't> Foo<'a, 't> for &'a isize {
     fn okay_bound<'b,'c,'e:'b+'c>(self, b: Inv<'b>, c: Inv<'c>, e: Inv<'e>) {
     }
 
-    fn another_bound<'x: 't>(self, x: Inv<'x>, y: Inv<'t>) {}
+    fn another_bound<'x: 't>(self, x: Inv<'x>, y: Inv<'t>) {
+        //~^ ERROR lifetime bound not satisfied
+    }
 }
 
 fn main() { }