Extend the implicator so it produces general obligations and also so

that it produces "outlives" relations for associated types. Add
several tests relating to #22246.

12 files changed, 527 insertions, 132 deletions

diff --git a/src/librustc/middle/infer/unify.rs b/src/librustc/middle/infer/unify.rs
index 923f7d2d4ef..235f3f994c6 100644
--- a/src/librustc/middle/infer/unify.rs
+++ b/src/librustc/middle/infer/unify.rs
@@ -212,7 +212,7 @@ impl<K:UnifyKey> UnificationTable<K> {
     }
 }
 
-impl<K> sv::SnapshotVecDelegate for Delegate<K> {
+impl<K:UnifyKey> sv::SnapshotVecDelegate for Delegate<K> {
     type Value = VarValue<K>;
     type Undo = ();
 
diff --git a/src/librustc_borrowck/borrowck/gather_loans/gather_moves.rs b/src/librustc_borrowck/borrowck/gather_loans/gather_moves.rs
index da53e9fac11..d0f5aa8cf00 100644
--- a/src/librustc_borrowck/borrowck/gather_loans/gather_moves.rs
+++ b/src/librustc_borrowck/borrowck/gather_loans/gather_moves.rs
@@ -16,7 +16,6 @@ use borrowck::gather_loans::move_error::{MoveError, MoveErrorCollector};
 use borrowck::move_data::*;
 use rustc::middle::expr_use_visitor as euv;
 use rustc::middle::mem_categorization as mc;
-use rustc::middle::mem_categorization::Typer;
 use rustc::middle::mem_categorization::InteriorOffsetKind as Kind;
 use rustc::middle::ty;
 use rustc::util::ppaux::Repr;
diff --git a/src/librustc_borrowck/borrowck/gather_loans/move_error.rs b/src/librustc_borrowck/borrowck/gather_loans/move_error.rs
index 10ffb89e728..da5c847a046 100644
--- a/src/librustc_borrowck/borrowck/gather_loans/move_error.rs
+++ b/src/librustc_borrowck/borrowck/gather_loans/move_error.rs
@@ -10,7 +10,6 @@
 
 use borrowck::BorrowckCtxt;
 use rustc::middle::mem_categorization as mc;
-use rustc::middle::mem_categorization::Typer;
 use rustc::middle::mem_categorization::InteriorOffsetKind as Kind;
 use rustc::middle::ty;
 use rustc::util::ppaux::UserString;
diff --git a/src/librustc_typeck/check/implicator.rs b/src/librustc_typeck/check/implicator.rs
index 5c4ca97ec8e..da25719baaa 100644
--- a/src/librustc_typeck/check/implicator.rs
+++ b/src/librustc_typeck/check/implicator.rs
@@ -11,13 +11,17 @@
 // #![warn(deprecated_mode)]
 
 use astconv::object_region_bounds;
-use middle::infer::GenericKind;
-use middle::subst::{ParamSpace, Subst, Substs};
-use middle::ty::{self, Ty};
-use middle::ty_fold::{TypeFolder};
+use middle::infer::{InferCtxt, GenericKind};
+use middle::subst::{Substs};
+use middle::traits;
+use middle::ty::{self, ToPolyTraitRef, Ty};
+use middle::ty_fold::{TypeFoldable, TypeFolder};
 
+use std::rc::Rc;
 use syntax::ast;
+use syntax::codemap::Span;
 
+use util::common::ErrorReported;
 use util::ppaux::Repr;
 
 // Helper functions related to manipulating region types.
@@ -25,35 +29,55 @@ use util::ppaux::Repr;
 pub enum Implication<'tcx> {
     RegionSubRegion(Option<Ty<'tcx>>, ty::Region, ty::Region),
     RegionSubGeneric(Option<Ty<'tcx>>, ty::Region, GenericKind<'tcx>),
+    Predicate(ast::DefId, ty::Predicate<'tcx>),
 }
 
 struct Implicator<'a, 'tcx: 'a> {
-    tcx: &'a ty::ctxt<'tcx>,
+    infcx: &'a InferCtxt<'a,'tcx>,
+    closure_typer: &'a (ty::ClosureTyper<'tcx>+'a),
+    body_id: ast::NodeId,
     stack: Vec<(ty::Region, Option<Ty<'tcx>>)>,
+    span: Span,
     out: Vec<Implication<'tcx>>,
 }
 
 /// This routine computes the well-formedness constraints that must hold for the type `ty` to
 /// appear in a context with lifetime `outer_region`
-pub fn implications<'tcx>(
-    tcx: &ty::ctxt<'tcx>,
+pub fn implications<'a,'tcx>(
+    infcx: &'a InferCtxt<'a,'tcx>,
+    closure_typer: &ty::ClosureTyper<'tcx>,
+    body_id: ast::NodeId,
     ty: Ty<'tcx>,
-    outer_region: ty::Region)
+    outer_region: ty::Region,
+    span: Span)
     -> Vec<Implication<'tcx>>
 {
+    debug!("implications(body_id={}, ty={}, outer_region={})",
+           body_id,
+           ty.repr(closure_typer.tcx()),
+           outer_region.repr(closure_typer.tcx()));
+
     let mut stack = Vec::new();
     stack.push((outer_region, None));
-    let mut wf = Implicator { tcx: tcx,
-                      stack: stack,
-                      out: Vec::new() };
+    let mut wf = Implicator { closure_typer: closure_typer,
+                              infcx: infcx,
+                              body_id: body_id,
+                              span: span,
+                              stack: stack,
+                              out: Vec::new() };
     wf.accumulate_from_ty(ty);
+    debug!("implications: out={}", wf.out.repr(closure_typer.tcx()));
     wf.out
 }
 
 impl<'a, 'tcx> Implicator<'a, 'tcx> {
+    fn tcx(&self) -> &'a ty::ctxt<'tcx> {
+        self.infcx.tcx
+    }
+
     fn accumulate_from_ty(&mut self, ty: Ty<'tcx>) {
         debug!("accumulate_from_ty(ty={})",
-               ty.repr(self.tcx));
+               ty.repr(self.tcx()));
 
         match ty.sty {
             ty::ty_bool |
@@ -94,13 +118,13 @@ impl<'a, 'tcx> Implicator<'a, 'tcx> {
 
             ty::ty_trait(ref t) => {
                 let required_region_bounds =
-                    object_region_bounds(self.tcx, &t.principal, t.bounds.builtin_bounds);
+                    object_region_bounds(self.tcx(), &t.principal, t.bounds.builtin_bounds);
                 self.accumulate_from_object_ty(ty, t.bounds.region_bound, required_region_bounds)
             }
 
             ty::ty_enum(def_id, substs) |
             ty::ty_struct(def_id, substs) => {
-                let item_scheme = ty::lookup_item_type(self.tcx, def_id);
+                let item_scheme = ty::lookup_item_type(self.tcx(), def_id);
                 self.accumulate_from_adt(ty, def_id, &item_scheme.generics, substs)
             }
 
@@ -139,9 +163,9 @@ impl<'a, 'tcx> Implicator<'a, 'tcx> {
             }
 
             ty::ty_open(_) => {
-                self.tcx.sess.bug(
+                self.tcx().sess.bug(
                     &format!("Unexpected type encountered while doing wf check: {}",
-                            ty.repr(self.tcx))[]);
+                            ty.repr(self.tcx()))[]);
             }
         }
     }
@@ -225,103 +249,113 @@ impl<'a, 'tcx> Implicator<'a, 'tcx> {
     fn accumulate_from_adt(&mut self,
                            ty: Ty<'tcx>,
                            def_id: ast::DefId,
-                           generics: &ty::Generics<'tcx>,
+                           _generics: &ty::Generics<'tcx>,
                            substs: &Substs<'tcx>)
     {
-        // The generic declarations from the type, appropriately
-        // substituted for the actual substitutions.
-        let generics = generics.subst(self.tcx, substs);
-
-        // Variance of each type/region parameter.
-        let variances = ty::item_variances(self.tcx, def_id);
-
-        for &space in &ParamSpace::all() {
-            let region_params = substs.regions().get_slice(space);
-            let region_variances = variances.regions.get_slice(space);
-            let region_param_defs = generics.regions.get_slice(space);
-            assert_eq!(region_params.len(), region_variances.len());
-            for (&region_param, (&region_variance, region_param_def)) in
-                region_params.iter().zip(
-                    region_variances.iter().zip(
-                        region_param_defs.iter()))
-            {
-                match region_variance {
-                    ty::Covariant | ty::Bivariant => {
-                        // Ignore covariant or bivariant region
-                        // parameters.  To understand why, consider a
-                        // struct `Foo<'a>`. If `Foo` contains any
-                        // references with lifetime `'a`, then `'a` must
-                        // be at least contravariant (and possibly
-                        // invariant). The only way to have a covariant
-                        // result is if `Foo` contains only a field with a
-                        // type like `fn() -> &'a T`; i.e., a bare
-                        // function that can produce a reference of
-                        // lifetime `'a`. In this case, there is no
-                        // *actual data* with lifetime `'a` that is
-                        // reachable. (Presumably this bare function is
-                        // really returning static data.)
-                    }
-
-                    ty::Contravariant | ty::Invariant => {
-                        // If the parameter is contravariant or
-                        // invariant, there may indeed be reachable
-                        // data with this lifetime. See other case for
-                        // more details.
-                        self.push_region_constraint_from_top(region_param);
+        let predicates =
+            ty::lookup_predicates(self.tcx(), def_id).instantiate(self.tcx(), substs);
+        let predicates = match self.fully_normalize(&predicates) {
+            Ok(predicates) => predicates,
+            Err(ErrorReported) => { return; }
+        };
+
+        for predicate in predicates.predicates.as_slice() {
+            match *predicate {
+                ty::Predicate::Trait(ref data) => {
+                    self.accumulate_from_assoc_types_transitive(data);
+                }
+                ty::Predicate::Equate(..) => { }
+                ty::Predicate::Projection(..) => { }
+                ty::Predicate::RegionOutlives(ref data) => {
+                    match ty::no_late_bound_regions(self.tcx(), data) {
+                        None => { }
+                        Some(ty::OutlivesPredicate(r_a, r_b)) => {
+                            self.push_sub_region_constraint(Some(ty), r_b, r_a);
+                        }
                     }
                 }
-
-                for &region_bound in &region_param_def.bounds {
-                    // The type declared a constraint like
-                    //
-                    //     'b : 'a
-                    //
-                    // which means that `'a <= 'b` (after
-                    // substitution).  So take the region we
-                    // substituted for `'a` (`region_bound`) and make
-                    // it a subregion of the region we substituted
-                    // `'b` (`region_param`).
-                    self.push_sub_region_constraint(
-                        Some(ty), region_bound, region_param);
+                ty::Predicate::TypeOutlives(ref data) => {
+                    match ty::no_late_bound_regions(self.tcx(), data) {
+                        None => { }
+                        Some(ty::OutlivesPredicate(ty_a, r_b)) => {
+                            self.stack.push((r_b, Some(ty)));
+                            self.accumulate_from_ty(ty_a);
+                            self.stack.pop().unwrap();
+                        }
+                    }
                 }
             }
+        }
 
-            let types = substs.types.get_slice(space);
-            let type_variances = variances.types.get_slice(space);
-            let type_param_defs = generics.types.get_slice(space);
-            assert_eq!(types.len(), type_variances.len());
-            for (&type_param_ty, (&variance, type_param_def)) in
-                types.iter().zip(
-                    type_variances.iter().zip(
-                        type_param_defs.iter()))
-            {
-                debug!("type_param_ty={} variance={}",
-                       type_param_ty.repr(self.tcx),
-                       variance.repr(self.tcx));
-
-                match variance {
-                    ty::Contravariant | ty::Bivariant => {
-                        // As above, except that in this it is a
-                        // *contravariant* reference that indices that no
-                        // actual data of type T is reachable.
-                    }
+        let obligations = predicates.predicates
+                                    .into_iter()
+                                    .map(|pred| Implication::Predicate(def_id, pred));
+        self.out.extend(obligations);
 
-                    ty::Covariant | ty::Invariant => {
-                        self.accumulate_from_ty(type_param_ty);
-                    }
+        let variances = ty::item_variances(self.tcx(), def_id);
+
+        for (&region, &variance) in substs.regions().iter().zip(variances.regions.iter()) {
+            match variance {
+                ty::Contravariant | ty::Invariant => {
+                    // If any data with this lifetime is reachable
+                    // within, it must be at least contravariant.
+                    self.push_region_constraint_from_top(region)
                 }
+                ty::Covariant | ty::Bivariant => { }
+            }
+        }
 
-                // Inspect bounds on this type parameter for any
-                // region bounds.
-                for &r in &type_param_def.bounds.region_bounds {
-                    self.stack.push((r, Some(ty)));
-                    self.accumulate_from_ty(type_param_ty);
-                    self.stack.pop().unwrap();
+        for (&ty, &variance) in substs.types.iter().zip(variances.types.iter()) {
+            match variance {
+                ty::Covariant | ty::Invariant => {
+                    // If any data of this type is reachable within,
+                    // it must be at least covariant.
+                    self.accumulate_from_ty(ty);
                 }
+                ty::Contravariant | ty::Bivariant => { }
             }
         }
     }
 
+    /// Given that there is a requirement that `Foo<X> : 'a`, where
+    /// `Foo` is declared like `struct Foo<T> where T : SomeTrait`,
+    /// this code finds all the associated types defined in
+    /// `SomeTrait` (and supertraits) and adds a requirement that `<X
+    /// as SomeTrait>::N : 'a` (where `N` is some associated type
+    /// defined in `SomeTrait`). This rule only applies to
+    /// trait-bounds that are not higher-ranked, because we cannot
+    /// project out of a HRTB. This rule helps code using associated
+    /// types to compile, see Issue #22246 for an example.
+    fn accumulate_from_assoc_types_transitive(&mut self,
+                                              data: &ty::PolyTraitPredicate<'tcx>)
+    {
+        for poly_trait_ref in traits::supertraits(self.tcx(), data.to_poly_trait_ref()) {
+            match ty::no_late_bound_regions(self.tcx(), &poly_trait_ref) {
+                Some(trait_ref) => { self.accumulate_from_assoc_types(trait_ref); }
+                None => { }
+            }
+        }
+    }
+
+    fn accumulate_from_assoc_types(&mut self,
+                                   trait_ref: Rc<ty::TraitRef<'tcx>>)
+    {
+        let trait_def_id = trait_ref.def_id;
+        let trait_def = ty::lookup_trait_def(self.tcx(), trait_def_id);
+        let assoc_type_projections: Vec<_> =
+            trait_def.associated_type_names
+                     .iter()
+                     .map(|&name| ty::mk_projection(self.tcx(), trait_ref.clone(), name))
+                     .collect();
+        let tys = match self.fully_normalize(&assoc_type_projections) {
+            Ok(tys) => { tys }
+            Err(ErrorReported) => { return; }
+        };
+        for ty in tys {
+            self.accumulate_from_ty(ty);
+        }
+    }
+
     fn accumulate_from_object_ty(&mut self,
                                  ty: Ty<'tcx>,
                                  region_bound: ty::Region,
@@ -373,6 +407,28 @@ impl<'a, 'tcx> Implicator<'a, 'tcx> {
             self.out.push(Implication::RegionSubRegion(Some(ty), r_d, r_c));
         }
     }
+
+    fn fully_normalize<T>(&self, value: &T) -> Result<T,ErrorReported>
+        where T : TypeFoldable<'tcx> + ty::HasProjectionTypes + Clone + Repr<'tcx>
+    {
+        let value =
+            traits::fully_normalize(self.infcx,
+                                    self.closure_typer,
+                                    traits::ObligationCause::misc(self.span, self.body_id),
+                                    value);
+        match value {
+            Ok(value) => Ok(value),
+            Err(errors) => {
+                // I don't like reporting these errors here, but I
+                // don't know where else to report them just now. And
+                // I don't really expect errors to arise here
+                // frequently. I guess the best option would be to
+                // propagate them out.
+                traits::report_fulfillment_errors(self.infcx, &errors);
+                Err(ErrorReported)
+            }
+        }
+    }
 }
 
 impl<'tcx> Repr<'tcx> for Implication<'tcx> {
@@ -389,6 +445,12 @@ impl<'tcx> Repr<'tcx> for Implication<'tcx> {
                         r.repr(tcx),
                         p.repr(tcx))
             }
+
+            Implication::Predicate(ref def_id, ref p) => {
+                format!("Predicate({}, {})",
+                        def_id.repr(tcx),
+                        p.repr(tcx))
+            }
         }
     }
 }
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 7bb2af606f5..3c2888e2278 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -481,7 +481,8 @@ pub fn check_item_types(ccx: &CrateCtxt) {
 fn check_bare_fn<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                            decl: &'tcx ast::FnDecl,
                            body: &'tcx ast::Block,
-                           id: ast::NodeId,
+                           fn_id: ast::NodeId,
+                           fn_span: Span,
                            raw_fty: Ty<'tcx>,
                            param_env: ty::ParameterEnvironment<'a, 'tcx>)
 {
@@ -499,13 +500,13 @@ fn check_bare_fn<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
             let fn_sig =
                 inh.normalize_associated_types_in(&inh.param_env, body.span, body.id, &fn_sig);
 
-            let fcx = check_fn(ccx, fn_ty.unsafety, id, &fn_sig,
-                               decl, id, body, &inh);
+            let fcx = check_fn(ccx, fn_ty.unsafety, fn_id, &fn_sig,
+                               decl, fn_id, body, &inh);
 
             vtable::select_all_fcx_obligations_and_apply_defaults(&fcx);
-            upvar::closure_analyze_fn(&fcx, id, decl, body);
+            upvar::closure_analyze_fn(&fcx, fn_id, decl, body);
             vtable::select_all_fcx_obligations_or_error(&fcx);
-            regionck::regionck_fn(&fcx, id, decl, body);
+            regionck::regionck_fn(&fcx, fn_id, fn_span, decl, body);
             writeback::resolve_type_vars_in_fn(&fcx, decl, body);
         }
         _ => ccx.tcx.sess.impossible_case(body.span,
@@ -718,7 +719,7 @@ pub fn check_item<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>, it: &'tcx ast::Item) {
       ast::ItemFn(ref decl, _, _, _, ref body) => {
         let fn_pty = ty::lookup_item_type(ccx.tcx, ast_util::local_def(it.id));
         let param_env = ParameterEnvironment::for_item(ccx.tcx, it.id);
-        check_bare_fn(ccx, &**decl, &**body, it.id, fn_pty.ty, param_env);
+        check_bare_fn(ccx, &**decl, &**body, it.id, it.span, fn_pty.ty, param_env);
       }
       ast::ItemImpl(_, _, _, _, _, ref impl_items) => {
         debug!("ItemImpl {} with id {}", token::get_ident(it.ident), it.id);
@@ -865,6 +866,7 @@ fn check_method_body<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                   &*method.pe_fn_decl(),
                   &*method.pe_body(),
                   method.id,
+                  method.span,
                   fty,
                   param_env);
 }
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index f8d32cd17f3..4e5550a2106 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -97,6 +97,7 @@ use middle::infer::{self, GenericKind};
 use middle::pat_util;
 use util::ppaux::{ty_to_string, Repr};
 
+use std::mem;
 use syntax::{ast, ast_util};
 use syntax::codemap::Span;
 use syntax::visit;
@@ -128,18 +129,18 @@ pub fn regionck_item(fcx: &FnCtxt, item: &ast::Item) {
     rcx.resolve_regions_and_report_errors();
 }
 
-pub fn regionck_fn(fcx: &FnCtxt, id: ast::NodeId, decl: &ast::FnDecl, blk: &ast::Block) {
-    debug!("regionck_fn(id={})", id);
-    let mut rcx = Rcx::new(fcx, RepeatingScope(blk.id), blk.id, Subject(id));
+pub fn regionck_fn(fcx: &FnCtxt,
+                   fn_id: ast::NodeId,
+                   fn_span: Span,
+                   decl: &ast::FnDecl,
+                   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(id, decl, blk, blk.span); // TODO suboptimal span
+        rcx.visit_fn_body(fn_id, decl, blk, fn_span);
     }
 
-    // Region checking a fn can introduce new trait obligations,
-    // particularly around closure bounds.
-    vtable::select_all_fcx_obligations_or_error(fcx);
-
     rcx.resolve_regions_and_report_errors();
 }
 
@@ -167,6 +168,9 @@ pub struct Rcx<'a, 'tcx: 'a> {
 
     region_bound_pairs: Vec<(ty::Region, GenericKind<'tcx>)>,
 
+    // id of innermost fn body id
+    body_id: ast::NodeId,
+
     // id of innermost fn or loop
     repeating_scope: ast::NodeId,
 
@@ -195,10 +199,12 @@ pub enum SubjectNode { Subject(ast::NodeId), None }
 impl<'a, 'tcx> Rcx<'a, 'tcx> {
     pub fn new(fcx: &'a FnCtxt<'a, 'tcx>,
                initial_repeating_scope: RepeatingScope,
+               initial_body_id: ast::NodeId,
                subject: SubjectNode) -> Rcx<'a, 'tcx> {
         let RepeatingScope(initial_repeating_scope) = initial_repeating_scope;
         Rcx { fcx: fcx,
               repeating_scope: initial_repeating_scope,
+              body_id: initial_body_id,
               subject: subject,
               region_bound_pairs: Vec::new()
         }
@@ -208,6 +214,10 @@ impl<'a, 'tcx> Rcx<'a, 'tcx> {
         self.fcx.ccx.tcx
     }
 
+    fn set_body_id(&mut self, body_id: ast::NodeId) -> ast::NodeId {
+        mem::replace(&mut self.body_id, body_id)
+    }
+
     fn set_repeating_scope(&mut self, scope: ast::NodeId) -> ast::NodeId {
         mem::replace(&mut self.repeating_scope, scope)
     }
@@ -267,9 +277,11 @@ impl<'a, 'tcx> Rcx<'a, 'tcx> {
     fn visit_fn_body(&mut self,
                      id: ast::NodeId,
                      fn_decl: &ast::FnDecl,
-                     body: &ast::Block)
+                     body: &ast::Block,
+                     span: Span)
     {
         // When we enter a function, we can derive
+        debug!("visit_fn_body(id={})", id);
 
         let fn_sig_map = self.fcx.inh.fn_sig_map.borrow();
         let fn_sig = match fn_sig_map.get(&id) {
@@ -281,17 +293,24 @@ impl<'a, 'tcx> Rcx<'a, 'tcx> {
         };
 
         let len = self.region_bound_pairs.len();
-        self.relate_free_regions(&fn_sig[], body.id);
+        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.set_body_id(old_body_id);
     }
 
     fn visit_region_obligations(&mut self, node_id: ast::NodeId)
     {
         debug!("visit_region_obligations: node_id={}", node_id);
 
+        // region checking can introduce new pending obligations
+        // which, when processed, might generate new region
+        // obligations. So make sure we process those.
+        vtable::select_all_fcx_obligations_or_error(self.fcx);
+
         // Make a copy of the region obligations vec because we'll need
         // to be able to borrow the fulfillment-cx below when projecting.
         let region_obligations =
@@ -324,7 +343,8 @@ impl<'a, 'tcx> Rcx<'a, 'tcx> {
     /// Tests: `src/test/compile-fail/regions-free-region-ordering-*.rs`
     fn relate_free_regions(&mut self,
                            fn_sig_tys: &[Ty<'tcx>],
-                           body_id: ast::NodeId) {
+                           body_id: ast::NodeId,
+                           span: Span) {
         debug!("relate_free_regions >>");
         let tcx = self.tcx();
 
@@ -333,18 +353,19 @@ impl<'a, 'tcx> Rcx<'a, 'tcx> {
             debug!("relate_free_regions(t={})", ty.repr(tcx));
             let body_scope = CodeExtent::from_node_id(body_id);
             let body_scope = ty::ReScope(body_scope);
-            let implications = implicator::implications(tcx, ty, body_scope);
+            let implications = implicator::implications(self.fcx.infcx(), self.fcx, body_id,
+                                                        ty, body_scope, span);
             for implication in implications {
                 debug!("implication: {}", implication.repr(tcx));
                 match implication {
                     implicator::Implication::RegionSubRegion(_,
-                                              ty::ReFree(free_a),
-                                              ty::ReFree(free_b)) => {
+                                                             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))) => {
+                                                             ty::ReFree(free_a),
+                                                             ty::ReInfer(ty::ReVar(vid_b))) => {
                         self.fcx.inh.infcx.add_given(free_a, vid_b);
                     }
                     implicator::Implication::RegionSubRegion(..) => {
@@ -364,6 +385,7 @@ impl<'a, 'tcx> Rcx<'a, 'tcx> {
 
                         self.region_bound_pairs.push((r_a, generic_b.clone()));
                     }
+                    implicator::Implication::Predicate(..) => { }
                 }
             }
         }
@@ -394,8 +416,8 @@ impl<'a, 'tcx, 'v> Visitor<'v> for Rcx<'a, 'tcx> {
     // regions, until regionck, as described in #3238.
 
     fn visit_fn(&mut self, _fk: visit::FnKind<'v>, fd: &'v ast::FnDecl,
-                b: &'v ast::Block, _s: Span, id: ast::NodeId) {
-        self.visit_fn_body(id, fd, b)
+                b: &'v ast::Block, span: Span, id: ast::NodeId) {
+        self.visit_fn_body(id, fd, b, span)
     }
 
     fn visit_item(&mut self, i: &ast::Item) { visit_item(self, i); }
@@ -1475,7 +1497,8 @@ pub fn type_must_outlive<'a, 'tcx>(rcx: &mut Rcx<'a, 'tcx>,
            ty.repr(rcx.tcx()),
            region.repr(rcx.tcx()));
 
-    let implications = implicator::implications(rcx.tcx(), ty, region);
+    let implications = implicator::implications(rcx.fcx.infcx(), rcx.fcx, rcx.body_id,
+                                                ty, region, origin.span());
     for implication in implications {
         debug!("implication: {}", implication.repr(rcx.tcx()));
         match implication {
@@ -1493,6 +1516,13 @@ pub fn type_must_outlive<'a, 'tcx>(rcx: &mut Rcx<'a, 'tcx>,
                 let o1 = infer::ReferenceOutlivesReferent(ty, origin.span());
                 generic_must_outlive(rcx, o1, r_a, generic_b);
             }
+            implicator::Implication::Predicate(def_id, predicate) => {
+                let cause = traits::ObligationCause::new(origin.span(),
+                                                         rcx.body_id,
+                                                         traits::ItemObligation(def_id));
+                let obligation = traits::Obligation::new(cause, predicate);
+                rcx.fcx.register_predicate(obligation);
+            }
         }
     }
 }
diff --git a/src/librustc_typeck/check/wf.rs b/src/librustc_typeck/check/wf.rs
index 2adc809f7ac..d124282d391 100644
--- a/src/librustc_typeck/check/wf.rs
+++ b/src/librustc_typeck/check/wf.rs
@@ -97,14 +97,10 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
                 self.check_item_type(item);
             }
             ast::ItemStruct(ref struct_def, _) => {
-                self.check_type_defn(item, |fcx| {
-                    vec![struct_variant(fcx, &**struct_def)]
-                });
+                self.check_type_defn(item, |fcx| vec![struct_variant(fcx, &**struct_def)]);
             }
             ast::ItemEnum(ref enum_def, _) => {
-                self.check_type_defn(item, |fcx| {
-                    enum_variants(fcx, enum_def)
-                });
+                self.check_type_defn(item, |fcx| enum_variants(fcx, enum_def));
             }
             ast::ItemTrait(..) => {
                 let trait_predicates =
diff --git a/src/test/compile-fail/regions-assoc-type-in-supertrait-outlives-container.rs b/src/test/compile-fail/regions-assoc-type-in-supertrait-outlives-container.rs
new file mode 100644
index 00000000000..fa26c9c54c8
--- /dev/null
+++ b/src/test/compile-fail/regions-assoc-type-in-supertrait-outlives-container.rs
@@ -0,0 +1,59 @@
+// Copyright 2015 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 that we are imposing the requirement that every associated
+// type of a bound that appears in the where clause on a struct must
+// outlive the location in which the type appears, even when the
+// associted type is in a supertype. Issue #22246.
+
+#![allow(dead_code)]
+
+use std::mem::transmute;
+use std::ops::Deref;
+
+///////////////////////////////////////////////////////////////////////////
+
+pub trait TheTrait {
+    type TheAssocType;
+
+    fn dummy(&self) { }
+}
+
+pub trait TheSubTrait : TheTrait {
+}
+
+pub struct TheType<'b> {
+    m: [fn(&'b()); 0]
+}
+
+impl<'b> TheTrait for TheType<'b> {
+    type TheAssocType = &'b ();
+}
+
+impl<'b> TheSubTrait for TheType<'b> {
+}
+
+///////////////////////////////////////////////////////////////////////////
+
+pub struct WithAssoc<T:TheSubTrait> {
+    m: [T; 0]
+}
+
+fn with_assoc<'a,'b>() {
+    // For this type to be valid, the rules require that all
+    // associated types of traits that appear in `WithAssoc` must
+    // outlive 'a. In this case, that means TheType<'b>::TheAssocType,
+    // which is &'b (), must outlive 'a.
+
+    let _: &'a WithAssoc<TheType<'b>> = loop { }; //~ ERROR cannot infer
+}
+
+fn main() {
+}
diff --git a/src/test/compile-fail/regions-assoc-type-outlives-container-hrtb.rs b/src/test/compile-fail/regions-assoc-type-outlives-container-hrtb.rs
new file mode 100644
index 00000000000..5e02aae672d
--- /dev/null
+++ b/src/test/compile-fail/regions-assoc-type-outlives-container-hrtb.rs
@@ -0,0 +1,69 @@
+// Copyright 2015 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 that structs with higher-ranked where clauses don't generate
+// "outlives" requirements. Issue #22246.
+
+#![allow(dead_code)]
+
+///////////////////////////////////////////////////////////////////////////
+
+pub trait TheTrait<'b> {
+    type TheAssocType;
+
+    fn dummy(&'b self) { }
+}
+
+pub struct TheType<'b> {
+    m: [fn(&'b()); 0]
+}
+
+impl<'a,'b> TheTrait<'a> for TheType<'b> {
+    type TheAssocType = &'b ();
+}
+
+///////////////////////////////////////////////////////////////////////////
+
+pub struct WithHrAssoc<T>
+    where for<'a> T : TheTrait<'a>
+{
+    m: [T; 0]
+}
+
+fn with_assoc<'a,'b>() {
+    // We get no error here because the where clause has a higher-ranked assoc type,
+    // which could not be projected from.
+
+    let _: &'a WithHrAssoc<TheType<'b>> = loop { };
+}
+
+///////////////////////////////////////////////////////////////////////////
+
+pub trait TheSubTrait : for<'a> TheTrait<'a> {
+}
+
+impl<'b> TheSubTrait for TheType<'b> { }
+
+pub struct WithHrAssocSub<T>
+    where T : TheSubTrait
+{
+    m: [T; 0]
+}
+
+fn with_assoc_sub<'a,'b>() {
+    // Same here, because although the where clause is not HR, it
+    // extends a trait in a HR way.
+
+    let _: &'a WithHrAssocSub<TheType<'b>> = loop { };
+}
+
+#[rustc_error]
+fn main() { //~ ERROR compilation successful
+}
diff --git a/src/test/compile-fail/regions-assoc-type-outlives-container-wc.rs b/src/test/compile-fail/regions-assoc-type-outlives-container-wc.rs
new file mode 100644
index 00000000000..6ee65fbdf91
--- /dev/null
+++ b/src/test/compile-fail/regions-assoc-type-outlives-container-wc.rs
@@ -0,0 +1,53 @@
+// Copyright 2015 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 that we are imposing the requirement that every associated
+// type of a bound that appears in the where clause on a struct must
+// outlive the location in which the type appears, even when the
+// constraint is in a where clause not a bound. Issue #22246.
+
+#![allow(dead_code)]
+
+use std::mem::transmute;
+use std::ops::Deref;
+
+///////////////////////////////////////////////////////////////////////////
+
+pub trait TheTrait {
+    type TheAssocType;
+
+    fn dummy(&self) { }
+}
+
+pub struct TheType<'b> {
+    m: [fn(&'b()); 0]
+}
+
+impl<'b> TheTrait for TheType<'b> {
+    type TheAssocType = &'b ();
+}
+
+///////////////////////////////////////////////////////////////////////////
+
+pub struct WithAssoc<T> where T : TheTrait {
+    m: [T; 0]
+}
+
+fn with_assoc<'a,'b>() {
+    // For this type to be valid, the rules require that all
+    // associated types of traits that appear in `WithAssoc` must
+    // outlive 'a. In this case, that means TheType<'b>::TheAssocType,
+    // which is &'b (), must outlive 'a.
+
+    let _: &'a WithAssoc<TheType<'b>> = loop { }; //~ ERROR cannot infer
+}
+
+fn main() {
+}
diff --git a/src/test/compile-fail/regions-assoc-type-outlives-container.rs b/src/test/compile-fail/regions-assoc-type-outlives-container.rs
new file mode 100644
index 00000000000..49a0726fa3b
--- /dev/null
+++ b/src/test/compile-fail/regions-assoc-type-outlives-container.rs
@@ -0,0 +1,91 @@
+// Copyright 2015 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 that we are imposing the requirement that every associated
+// type of a bound that appears in the where clause on a struct must
+// outlive the location in which the type appears. Issue #22246.
+
+#![allow(dead_code)]
+
+use std::mem::transmute;
+use std::ops::Deref;
+
+///////////////////////////////////////////////////////////////////////////
+
+pub trait TheTrait {
+    type TheAssocType;
+
+    fn dummy(&self) { }
+}
+
+pub struct TheType<'b> {
+    m: [fn(&'b()); 0]
+}
+
+impl<'b> TheTrait for TheType<'b> {
+    type TheAssocType = &'b ();
+}
+
+///////////////////////////////////////////////////////////////////////////
+
+pub struct WithAssoc<T:TheTrait> {
+    m: [T; 0]
+}
+
+pub struct WithoutAssoc<T> {
+    m: [T; 0]
+}
+
+fn with_assoc<'a,'b>() {
+    // For this type to be valid, the rules require that all
+    // associated types of traits that appear in `WithAssoc` must
+    // outlive 'a. In this case, that means TheType<'b>::TheAssocType,
+    // which is &'b (), must outlive 'a.
+
+    let _: &'a WithAssoc<TheType<'b>> = loop { }; //~ ERROR cannot infer
+}
+
+fn with_assoc1<'a,'b>() where 'b : 'a {
+    // For this type to be valid, the rules require that all
+    // associated types of traits that appear in `WithAssoc` must
+    // outlive 'a. In this case, that means TheType<'b>::TheAssocType,
+    // which is &'b (), must outlive 'a, so 'b : 'a must hold, and
+    // that is in the where clauses, so we're fine.
+
+    let _: &'a WithAssoc<TheType<'b>> = loop { };
+}
+
+fn without_assoc<'a,'b>() {
+    // Here there are no associated types and the `'b` appearing in
+    // `TheType<'b>` is purely covariant, so there is no requirement
+    // that `'b:'a` holds.
+
+    let _: &'a WithoutAssoc<TheType<'b>> = loop { };
+}
+
+fn call_with_assoc<'a,'b>() {
+    // As `with_assoc`, but just checking that we impose the same rule
+    // on the value supplied for the type argument, even when there is
+    // no data.
+
+    call::<&'a WithAssoc<TheType<'b>>>();
+    //~^ ERROR cannot infer
+}
+
+fn call_without_assoc<'a,'b>() {
+    // As `without_assoc`, but in a distinct scenario.
+
+    call::<&'a WithoutAssoc<TheType<'b>>>();
+}
+
+fn call<T>() { }
+
+fn main() {
+}
diff --git a/src/test/run-pass/regions-issue-22246.rs b/src/test/run-pass/regions-issue-22246.rs
new file mode 100644
index 00000000000..f5c34d6b34e
--- /dev/null
+++ b/src/test/run-pass/regions-issue-22246.rs
@@ -0,0 +1,35 @@
+// Copyright 2015 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 #22246 -- we should be able to deduce
+// that `&'a B::Owned` implies that `B::Owned : 'a`.
+
+#![allow(dead_code)]
+
+use std::ops::Deref;
+
+pub trait ToOwned {
+    type Owned: Borrow<Self>;
+    fn to_owned(&self) -> Self::Owned;
+}
+
+pub trait Borrow<Borrowed> {
+    fn borrow(&self) -> &Borrowed;
+}
+
+pub struct Foo<B:ToOwned> {
+    owned: B::Owned
+}
+
+fn foo<B:ToOwned>(this: &Foo<B>) -> &B {
+    this.owned.borrow()
+}
+
+fn main() { }