Auto merge of #22436 - nikomatsakis:issue-22246-bound-lifetimes-of-assoc-types, r=nikomatsakis

Take 2. This PR includes a bunch of refactoring that was part of an experimental branch implementing [implied bounds]. That particular idea isn't ready to go yet, but the refactoring proved useful for fixing #22246. The implied bounds branch also exposed #22110 so a simple fix for that is included here. I still think some more refactoring would be a good idea here -- in particular I think most of the code in wf.rs is kind of duplicating the logic in implicator and should go, but I decided to post this PR and call it a day before diving into that. I'll write a bit more details about the solutions I adopted in the various bugs. I patched the two issues I was concerned about, which was the handling of supertraits and HRTB (the latter turned out to be fine, so I added a comment explaining why.)

r? @pnkfelix (for now, anyway)
cc @aturon 

[implied bounds]: http://smallcultfollowing.com/babysteps/blog/2014/07/06/implied-bounds/

23 files changed, 684 insertions, 296 deletions

diff --git a/src/librustc/middle/expr_use_visitor.rs b/src/librustc/middle/expr_use_visitor.rs
index 5cc7502b512..8dbac7f515e 100644
--- a/src/librustc/middle/expr_use_visitor.rs
+++ b/src/librustc/middle/expr_use_visitor.rs
@@ -838,7 +838,7 @@ impl<'d,'t,'tcx,TYPER:mc::Typer<'tcx>> ExprUseVisitor<'d,'t,'tcx,TYPER> {
                     // the method call infrastructure should have
                     // replaced all late-bound regions with variables:
                     let self_ty = ty::ty_fn_sig(method_ty).input(0);
-                    let self_ty = ty::assert_no_late_bound_regions(self.tcx(), &self_ty);
+                    let self_ty = ty::no_late_bound_regions(self.tcx(), &self_ty).unwrap();
 
                     let (m, r) = match self_ty.sty {
                         ty::ty_rptr(r, ref m) => (m.mutbl, r),
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/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs
index 6c295142c9f..4be7bb9c365 100644
--- a/src/librustc/middle/mem_categorization.rs
+++ b/src/librustc/middle/mem_categorization.rs
@@ -281,7 +281,6 @@ pub type McResult<T> = Result<T, ()>;
 /// know that no errors have occurred, so we simply consult the tcx and we
 /// can be sure that only `Ok` results will occur.
 pub trait Typer<'tcx> : ty::ClosureTyper<'tcx> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>;
     fn node_ty(&self, id: ast::NodeId) -> McResult<Ty<'tcx>>;
     fn expr_ty_adjusted(&self, expr: &ast::Expr) -> McResult<Ty<'tcx>>;
     fn type_moves_by_default(&self, span: Span, ty: Ty<'tcx>) -> bool;
@@ -905,8 +904,8 @@ impl<'t,'tcx,TYPER:Typer<'tcx>> MemCategorizationContext<'t,TYPER> {
         let base_cmt = match method_ty {
             Some(method_ty) => {
                 let ref_ty =
-                    ty::assert_no_late_bound_regions(
-                        self.tcx(), &ty::ty_fn_ret(method_ty)).unwrap();
+                    ty::no_late_bound_regions(
+                        self.tcx(), &ty::ty_fn_ret(method_ty)).unwrap().unwrap();
                 self.cat_rvalue_node(node.id(), node.span(), ref_ty)
             }
             None => base_cmt
@@ -996,7 +995,7 @@ impl<'t,'tcx,TYPER:Typer<'tcx>> MemCategorizationContext<'t,TYPER> {
 
                 // FIXME(#20649) -- why are we using the `self_ty` as the element type...?
                 let self_ty = ty::ty_fn_sig(method_ty).input(0);
-                ty::assert_no_late_bound_regions(self.tcx(), &self_ty)
+                ty::no_late_bound_regions(self.tcx(), &self_ty).unwrap()
             }
             None => {
                 match ty::array_element_ty(self.tcx(), base_cmt.ty) {
@@ -1336,8 +1335,9 @@ impl<'t,'tcx,TYPER:Typer<'tcx>> MemCategorizationContext<'t,TYPER> {
         // types are generated by method resolution and always have
         // all late-bound regions fully instantiated, so we just want
         // to skip past the binder.
-        ty::assert_no_late_bound_regions(self.tcx(), &ty::ty_fn_ret(method_ty))
-            .unwrap() // overloaded ops do not diverge, either
+        ty::no_late_bound_regions(self.tcx(), &ty::ty_fn_ret(method_ty))
+           .unwrap()
+           .unwrap() // overloaded ops do not diverge, either
     }
 }
 
diff --git a/src/librustc/middle/traits/fulfill.rs b/src/librustc/middle/traits/fulfill.rs
index 07c7453783d..a9cac4be3e3 100644
--- a/src/librustc/middle/traits/fulfill.rs
+++ b/src/librustc/middle/traits/fulfill.rs
@@ -9,7 +9,6 @@
 // except according to those terms.
 
 use middle::infer::{InferCtxt};
-use middle::mem_categorization::Typer;
 use middle::ty::{self, RegionEscape, Ty};
 use std::collections::HashSet;
 use std::collections::hash_map::Entry::{Occupied, Vacant};
diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index 83090dd72aa..57c9fa7a4d9 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -15,9 +15,9 @@ pub use self::FulfillmentErrorCode::*;
 pub use self::Vtable::*;
 pub use self::ObligationCauseCode::*;
 
-use middle::mem_categorization::Typer;
 use middle::subst;
-use middle::ty::{self, Ty};
+use middle::ty::{self, HasProjectionTypes, Ty};
+use middle::ty_fold::TypeFoldable;
 use middle::infer::{self, InferCtxt};
 use std::slice::Iter;
 use std::rc::Rc;
@@ -432,18 +432,8 @@ pub fn normalize_param_env<'a,'tcx>(param_env: &ty::ParameterEnvironment<'a,'tcx
     debug!("normalize_param_env(param_env={})",
            param_env.repr(tcx));
 
-    let predicates: Vec<ty::Predicate<'tcx>> = {
-        let infcx = infer::new_infer_ctxt(tcx);
-        let mut selcx = &mut SelectionContext::new(&infcx, param_env);
-        let mut fulfill_cx = FulfillmentContext::new();
-        let Normalized { value: predicates, obligations } =
-            project::normalize(selcx, cause, &param_env.caller_bounds);
-        for obligation in obligations {
-            fulfill_cx.register_predicate_obligation(selcx.infcx(), obligation);
-        }
-        try!(fulfill_cx.select_all_or_error(selcx.infcx(), param_env));
-        predicates.iter().map(|p| infcx.resolve_type_vars_if_possible(p)).collect()
-    };
+    let infcx = infer::new_infer_ctxt(tcx);
+    let predicates = try!(fully_normalize(&infcx, param_env, cause, &param_env.caller_bounds));
 
     debug!("normalize_param_env: predicates={}",
            predicates.repr(tcx));
@@ -451,6 +441,35 @@ pub fn normalize_param_env<'a,'tcx>(param_env: &ty::ParameterEnvironment<'a,'tcx
     Ok(param_env.with_caller_bounds(predicates))
 }
 
+pub fn fully_normalize<'a,'tcx,T>(infcx: &InferCtxt<'a,'tcx>,
+                                  closure_typer: &ty::ClosureTyper<'tcx>,
+                                  cause: ObligationCause<'tcx>,
+                                  value: &T)
+                                  -> Result<T, Vec<FulfillmentError<'tcx>>>
+    where T : TypeFoldable<'tcx> + HasProjectionTypes + Clone + Repr<'tcx>
+{
+    let tcx = closure_typer.tcx();
+
+    debug!("normalize_param_env(value={})",
+           value.repr(tcx));
+
+    let mut selcx = &mut SelectionContext::new(infcx, closure_typer);
+    let mut fulfill_cx = FulfillmentContext::new();
+    let Normalized { value: normalized_value, obligations } =
+        project::normalize(selcx, cause, value);
+    debug!("normalize_param_env: normalized_value={} obligations={}",
+           normalized_value.repr(tcx),
+           obligations.repr(tcx));
+    for obligation in obligations {
+        fulfill_cx.register_predicate_obligation(selcx.infcx(), obligation);
+    }
+    try!(fulfill_cx.select_all_or_error(infcx, closure_typer));
+    let resolved_value = infcx.resolve_type_vars_if_possible(&normalized_value);
+    debug!("normalize_param_env: resolved_value={}",
+           resolved_value.repr(tcx));
+    Ok(resolved_value)
+}
+
 impl<'tcx,O> Obligation<'tcx,O> {
     pub fn new(cause: ObligationCause<'tcx>,
                trait_ref: O)
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index 061557eb7dc..027415de998 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -32,7 +32,6 @@ use super::object_safety;
 use super::{util};
 
 use middle::fast_reject;
-use middle::mem_categorization::Typer;
 use middle::subst::{Subst, Substs, TypeSpace, VecPerParamSpace};
 use middle::ty::{self, RegionEscape, ToPolyTraitRef, Ty};
 use middle::infer;
@@ -653,8 +652,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 let is_dup =
                     (0..candidates.len())
                     .filter(|&j| i != j)
-                    .any(|j| self.candidate_should_be_dropped_in_favor_of(stack,
-                                                                          &candidates[i],
+                    .any(|j| self.candidate_should_be_dropped_in_favor_of(&candidates[i],
                                                                           &candidates[j]));
                 if is_dup {
                     debug!("Dropping candidate #{}/{}: {}",
@@ -1236,31 +1234,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         self.evaluate_predicates_recursively(stack, selection.iter_nested())
     }
 
-    /// Returns true if `candidate_i` should be dropped in favor of `candidate_j`.
-    ///
-    /// This is generally true if either:
-    /// - candidate i and candidate j are equivalent; or,
-    /// - candidate i is a concrete impl and candidate j is a where clause bound,
-    ///   and the concrete impl is applicable to the types in the where clause bound.
-    ///
-    /// The last case refers to cases where there are blanket impls (often conditional
-    /// blanket impls) as well as a where clause. This can come down to one of two cases:
-    ///
-    /// - The impl is truly unconditional (it has no where clauses
-    ///   of its own), in which case the where clause is
-    ///   unnecessary, because coherence requires that we would
-    ///   pick that particular impl anyhow (at least so long as we
-    ///   don't have specialization).
-    ///
-    /// - The impl is conditional, in which case we may not have winnowed it out
-    ///   because we don't know if the conditions apply, but the where clause is basically
-    ///   telling us that there is some impl, though not necessarily the one we see.
-    ///
-    /// In both cases we prefer to take the where clause, which is
-    /// essentially harmless.  See issue #18453 for more details of
-    /// a case where doing the opposite caused us harm.
+    /// Returns true if `candidate_i` should be dropped in favor of
+    /// `candidate_j`.  Generally speaking we will drop duplicate
+    /// candidates and prefer where-clause candidates.
     fn candidate_should_be_dropped_in_favor_of<'o>(&mut self,
-                                                   stack: &TraitObligationStack<'o, 'tcx>,
                                                    candidate_i: &SelectionCandidate<'tcx>,
                                                    candidate_j: &SelectionCandidate<'tcx>)
                                                    -> bool
@@ -1270,37 +1247,16 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
 
         match (candidate_i, candidate_j) {
-            (&ImplCandidate(impl_def_id), &ParamCandidate(ref bound)) => {
-                debug!("Considering whether to drop param {} in favor of impl {}",
-                       candidate_i.repr(self.tcx()),
-                       candidate_j.repr(self.tcx()));
-
-                self.infcx.probe(|snapshot| {
-                    let (skol_obligation_trait_ref, skol_map) =
-                        self.infcx().skolemize_late_bound_regions(
-                            &stack.obligation.predicate, snapshot);
-                    let impl_substs =
-                        self.rematch_impl(impl_def_id, stack.obligation, snapshot,
-                                          &skol_map, skol_obligation_trait_ref.trait_ref.clone());
-                    let impl_trait_ref =
-                        ty::impl_trait_ref(self.tcx(), impl_def_id).unwrap();
-                    let impl_trait_ref =
-                        impl_trait_ref.subst(self.tcx(), &impl_substs.value);
-                    let poly_impl_trait_ref =
-                        ty::Binder(impl_trait_ref);
-                    let origin =
-                        infer::RelateOutputImplTypes(stack.obligation.cause.span);
-                    self.infcx
-                        .sub_poly_trait_refs(false, origin, poly_impl_trait_ref, bound.clone())
-                        .is_ok()
-                })
-            }
-            (&BuiltinCandidate(_), &ParamCandidate(_)) => {
-                // If we have a where-clause like `Option<K> : Send`,
-                // then we wind up in a situation where there is a
-                // default rule (`Option<K>:Send if K:Send) and the
-                // where-clause that both seem applicable. Just take
-                // the where-clause in that case.
+            (&ImplCandidate(..), &ParamCandidate(..)) |
+            (&ClosureCandidate(..), &ParamCandidate(..)) |
+            (&FnPointerCandidate(..), &ParamCandidate(..)) |
+            (&BuiltinCandidate(..), &ParamCandidate(..)) => {
+                // We basically prefer always prefer to use a
+                // where-clause over another option. Where clauses
+                // impose the burden of finding the exact match onto
+                // the caller. Using an impl in preference of a where
+                // clause can also lead us to "overspecialize", as in
+                // #18453.
                 true
             }
             (&ProjectionCandidate, &ParamCandidate(_)) => {
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 8618bde95fe..e3eda02b0a8 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -2337,6 +2337,10 @@ impl ClosureKind {
 }
 
 pub trait ClosureTyper<'tcx> {
+    fn tcx(&self) -> &ty::ctxt<'tcx> {
+        self.param_env().tcx
+    }
+
     fn param_env<'a>(&'a self) -> &'a ty::ParameterEnvironment<'a, 'tcx>;
 
     /// Is this a `Fn`, `FnMut` or `FnOnce` closure? During typeck,
@@ -4384,8 +4388,8 @@ pub fn adjust_ty<'tcx, F>(cx: &ctxt<'tcx>,
                                     // overloaded deref operators have all late-bound
                                     // regions fully instantiated and coverge
                                     let fn_ret =
-                                        ty::assert_no_late_bound_regions(cx,
-                                                                         &ty_fn_ret(method_ty));
+                                        ty::no_late_bound_regions(cx,
+                                                                  &ty_fn_ret(method_ty)).unwrap();
                                     adjusted_ty = fn_ret.unwrap();
                                 }
                                 None => {}
@@ -5186,7 +5190,7 @@ impl<'tcx> VariantInfo<'tcx> {
                 let arg_tys = if args.len() > 0 {
                     // the regions in the argument types come from the
                     // enum def'n, and hence will all be early bound
-                    ty::assert_no_late_bound_regions(cx, &ty_fn_args(ctor_ty))
+                    ty::no_late_bound_regions(cx, &ty_fn_args(ctor_ty)).unwrap()
                 } else {
                     Vec::new()
                 };
@@ -6463,10 +6467,6 @@ impl<'tcx> ctxt<'tcx> {
 }
 
 impl<'a,'tcx> mc::Typer<'tcx> for ParameterEnvironment<'a,'tcx> {
-    fn tcx(&self) -> &ty::ctxt<'tcx> {
-        self.tcx
-    }
-
     fn node_ty(&self, id: ast::NodeId) -> mc::McResult<Ty<'tcx>> {
         Ok(ty::node_id_to_type(self.tcx, id))
     }
@@ -6677,14 +6677,17 @@ pub fn binds_late_bound_regions<'tcx, T>(
     count_late_bound_regions(tcx, value) > 0
 }
 
-pub fn assert_no_late_bound_regions<'tcx, T>(
+pub fn no_late_bound_regions<'tcx, T>(
     tcx: &ty::ctxt<'tcx>,
     value: &Binder<T>)
-    -> T
+    -> Option<T>
     where T : TypeFoldable<'tcx> + Repr<'tcx> + Clone
 {
-    assert!(!binds_late_bound_regions(tcx, value));
-    value.0.clone()
+    if binds_late_bound_regions(tcx, value) {
+        None
+    } else {
+        Some(value.0.clone())
+    }
 }
 
 /// Replace any late-bound regions bound in `value` with `'static`. Useful in trans but also
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_trans/trans/common.rs b/src/librustc_trans/trans/common.rs
index d658003702d..3709490d8da 100644
--- a/src/librustc_trans/trans/common.rs
+++ b/src/librustc_trans/trans/common.rs
@@ -637,10 +637,6 @@ impl<'blk, 'tcx> BlockS<'blk, 'tcx> {
 }
 
 impl<'blk, 'tcx> mc::Typer<'tcx> for BlockS<'blk, 'tcx> {
-    fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
-        self.tcx()
-    }
-
     fn node_ty(&self, id: ast::NodeId) -> mc::McResult<Ty<'tcx>> {
         Ok(node_id_type(self, id))
     }
diff --git a/src/librustc_trans/trans/expr.rs b/src/librustc_trans/trans/expr.rs
index 480679f43cb..7a05cc55276 100644
--- a/src/librustc_trans/trans/expr.rs
+++ b/src/librustc_trans/trans/expr.rs
@@ -781,8 +781,8 @@ fn trans_index<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
             let ix_datum = unpack_datum!(bcx, trans(bcx, idx));
 
             let ref_ty = // invoked methods have LB regions instantiated:
-                ty::assert_no_late_bound_regions(
-                    bcx.tcx(), &ty::ty_fn_ret(method_ty)).unwrap();
+                ty::no_late_bound_regions(
+                    bcx.tcx(), &ty::ty_fn_ret(method_ty)).unwrap().unwrap();
             let elt_ty = match ty::deref(ref_ty, true) {
                 None => {
                     bcx.tcx().sess.span_bug(index_expr.span,
@@ -2214,8 +2214,8 @@ fn deref_once<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
             };
 
             let ref_ty = // invoked methods have their LB regions instantiated
-                ty::assert_no_late_bound_regions(
-                    ccx.tcx(), &ty::ty_fn_ret(method_ty)).unwrap();
+                ty::no_late_bound_regions(
+                    ccx.tcx(), &ty::ty_fn_ret(method_ty)).unwrap().unwrap();
             let scratch = rvalue_scratch_datum(bcx, ref_ty, "overloaded_deref");
 
             unpack_result!(bcx, trans_overloaded_op(bcx, expr, method_call,
diff --git a/src/librustc_typeck/check/_match.rs b/src/librustc_typeck/check/_match.rs
index 81868f3695c..0d30741978a 100644
--- a/src/librustc_typeck/check/_match.rs
+++ b/src/librustc_typeck/check/_match.rs
@@ -509,7 +509,7 @@ pub fn check_pat_enum<'a, 'tcx>(pcx: &pat_ctxt<'a, 'tcx>,
     let ctor_scheme = ty::lookup_item_type(tcx, enum_def);
     let ctor_predicates = ty::lookup_predicates(tcx, enum_def);
     let path_scheme = if ty::is_fn_ty(ctor_scheme.ty) {
-        let fn_ret = ty::assert_no_late_bound_regions(tcx, &ty::ty_fn_ret(ctor_scheme.ty));
+        let fn_ret = ty::no_late_bound_regions(tcx, &ty::ty_fn_ret(ctor_scheme.ty)).unwrap();
         ty::TypeScheme {
             ty: fn_ret.unwrap(),
             generics: ctor_scheme.generics,
diff --git a/src/librustc_typeck/check/callee.rs b/src/librustc_typeck/check/callee.rs
index 6a9d34d7637..7354ea7377c 100644
--- a/src/librustc_typeck/check/callee.rs
+++ b/src/librustc_typeck/check/callee.rs
@@ -367,8 +367,8 @@ impl<'tcx> DeferredCallResolution<'tcx> for CallResolution<'tcx> {
                 // (This always bites me, should find a way to
                 // refactor it.)
                 let method_sig =
-                    ty::assert_no_late_bound_regions(fcx.tcx(),
-                                                     ty::ty_fn_sig(method_callee.ty));
+                    ty::no_late_bound_regions(fcx.tcx(),
+                                              ty::ty_fn_sig(method_callee.ty)).unwrap();
 
                 debug!("attempt_resolution: method_callee={}",
                        method_callee.repr(fcx.tcx()));
diff --git a/src/librustc_typeck/check/regionmanip.rs b/src/librustc_typeck/check/implicator.rs
index 209570585d2..da25719baaa 100644
--- a/src/librustc_typeck/check/regionmanip.rs
+++ b/src/librustc_typeck/check/implicator.rs
@@ -10,52 +10,74 @@
 
 // #![warn(deprecated_mode)]
 
-pub use self::WfConstraint::*;
-
 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.
 
-pub enum WfConstraint<'tcx> {
-    RegionSubRegionConstraint(Option<Ty<'tcx>>, ty::Region, ty::Region),
-    RegionSubGenericConstraint(Option<Ty<'tcx>>, ty::Region, GenericKind<'tcx>),
+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 Wf<'a, 'tcx: 'a> {
-    tcx: &'a ty::ctxt<'tcx>,
+struct Implicator<'a, 'tcx: 'a> {
+    infcx: &'a InferCtxt<'a,'tcx>,
+    closure_typer: &'a (ty::ClosureTyper<'tcx>+'a),
+    body_id: ast::NodeId,
     stack: Vec<(ty::Region, Option<Ty<'tcx>>)>,
-    out: Vec<WfConstraint<'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 region_wf_constraints<'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)
-    -> Vec<WfConstraint<'tcx>>
+    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 = Wf { 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> Wf<'a, 'tcx> {
+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!("Wf::accumulate_from_ty(ty={})",
-               ty.repr(self.tcx));
+        debug!("accumulate_from_ty(ty={})",
+               ty.repr(self.tcx()));
 
         match ty.sty {
             ty::ty_bool |
@@ -96,13 +118,13 @@ impl<'a, 'tcx> Wf<'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)
             }
 
@@ -141,9 +163,9 @@ impl<'a, 'tcx> Wf<'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()))[]);
             }
         }
     }
@@ -197,7 +219,7 @@ impl<'a, 'tcx> Wf<'a, 'tcx> {
                                   opt_ty: Option<Ty<'tcx>>,
                                   r_a: ty::Region,
                                   r_b: ty::Region) {
-        self.out.push(RegionSubRegionConstraint(opt_ty, r_a, r_b));
+        self.out.push(Implication::RegionSubRegion(opt_ty, r_a, r_b));
     }
 
     /// Pushes a constraint that `param_ty` must outlive the top region on the stack.
@@ -211,7 +233,7 @@ impl<'a, 'tcx> Wf<'a, 'tcx> {
     fn push_projection_constraint_from_top(&mut self,
                                            projection_ty: &ty::ProjectionTy<'tcx>) {
         let &(region, opt_ty) = self.stack.last().unwrap();
-        self.out.push(RegionSubGenericConstraint(
+        self.out.push(Implication::RegionSubGeneric(
             opt_ty, region, GenericKind::Projection(projection_ty.clone())));
     }
 
@@ -220,110 +242,120 @@ impl<'a, 'tcx> Wf<'a, 'tcx> {
                              region: ty::Region,
                              opt_ty: Option<Ty<'tcx>>,
                              param_ty: ty::ParamTy) {
-        self.out.push(RegionSubGenericConstraint(
+        self.out.push(Implication::RegionSubGeneric(
             opt_ty, region, GenericKind::Param(param_ty)));
     }
 
     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,
@@ -372,25 +404,53 @@ impl<'a, 'tcx> Wf<'a, 'tcx> {
         for &r_d in &required_region_bounds {
             // Each of these is an instance of the `'c <= 'b`
             // constraint above
-            self.out.push(RegionSubRegionConstraint(Some(ty), r_d, r_c));
+            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 WfConstraint<'tcx> {
+impl<'tcx> Repr<'tcx> for Implication<'tcx> {
     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
         match *self {
-            RegionSubRegionConstraint(_, ref r_a, ref r_b) => {
-                format!("RegionSubRegionConstraint({}, {})",
+            Implication::RegionSubRegion(_, ref r_a, ref r_b) => {
+                format!("RegionSubRegion({}, {})",
                         r_a.repr(tcx),
                         r_b.repr(tcx))
             }
 
-            RegionSubGenericConstraint(_, ref r, ref p) => {
-                format!("RegionSubGenericConstraint({}, {})",
+            Implication::RegionSubGeneric(_, ref r, ref p) => {
+                format!("RegionSubGeneric({}, {})",
                         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 30896c1607a..3c2888e2278 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -131,7 +131,7 @@ pub mod dropck;
 pub mod _match;
 pub mod vtable;
 pub mod writeback;
-pub mod regionmanip;
+pub mod implicator;
 pub mod regionck;
 pub mod coercion;
 pub mod demand;
@@ -309,9 +309,6 @@ pub struct FnCtxt<'a, 'tcx: 'a> {
 }
 
 impl<'a, 'tcx> mc::Typer<'tcx> for FnCtxt<'a, 'tcx> {
-    fn tcx(&self) -> &ty::ctxt<'tcx> {
-        self.ccx.tcx
-    }
     fn node_ty(&self, id: ast::NodeId) -> McResult<Ty<'tcx>> {
         let ty = self.node_ty(id);
         self.resolve_type_vars_or_error(&ty)
@@ -484,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>)
 {
@@ -502,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,
@@ -721,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);
@@ -868,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);
 }
@@ -2050,8 +2049,8 @@ fn make_overloaded_lvalue_return_type<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
     match method {
         Some(method) => {
             let ref_ty = // invoked methods have all LB regions instantiated
-                ty::assert_no_late_bound_regions(
-                    fcx.tcx(), &ty::ty_fn_ret(method.ty));
+                ty::no_late_bound_regions(
+                    fcx.tcx(), &ty::ty_fn_ret(method.ty)).unwrap();
             match method_call {
                 Some(method_call) => {
                     fcx.inh.method_map.borrow_mut().insert(method_call,
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index 17c259e674e..4e5550a2106 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -85,7 +85,7 @@
 use astconv::AstConv;
 use check::dropck;
 use check::FnCtxt;
-use check::regionmanip;
+use check::implicator;
 use check::vtable;
 use middle::def;
 use middle::mem_categorization as mc;
@@ -97,12 +97,12 @@ 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;
 use syntax::visit::Visitor;
 
-use self::RepeatingScope::Repeating;
 use self::SubjectNode::Subject;
 
 // a variation on try that just returns unit
@@ -114,7 +114,7 @@ macro_rules! ignore_err {
 // PUBLIC ENTRY POINTS
 
 pub fn regionck_expr(fcx: &FnCtxt, e: &ast::Expr) {
-    let mut rcx = Rcx::new(fcx, Repeating(e.id), Subject(e.id));
+    let mut rcx = Rcx::new(fcx, RepeatingScope(e.id), e.id, Subject(e.id));
     if fcx.err_count_since_creation() == 0 {
         // regionck assumes typeck succeeded
         rcx.visit_expr(e);
@@ -124,22 +124,23 @@ pub fn regionck_expr(fcx: &FnCtxt, e: &ast::Expr) {
 }
 
 pub fn regionck_item(fcx: &FnCtxt, item: &ast::Item) {
-    let mut rcx = Rcx::new(fcx, Repeating(item.id), Subject(item.id));
+    let mut rcx = Rcx::new(fcx, RepeatingScope(item.id), item.id, Subject(item.id));
     rcx.visit_region_obligations(item.id);
     rcx.resolve_regions_and_report_errors();
 }
 
-pub fn regionck_fn(fcx: &FnCtxt, id: ast::NodeId, decl: &ast::FnDecl, blk: &ast::Block) {
-    let mut rcx = Rcx::new(fcx, Repeating(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);
+        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();
 }
 
@@ -148,7 +149,7 @@ pub fn regionck_fn(fcx: &FnCtxt, id: ast::NodeId, decl: &ast::FnDecl, blk: &ast:
 pub fn regionck_ensure_component_tys_wf<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
                                                   span: Span,
                                                   component_tys: &[Ty<'tcx>]) {
-    let mut rcx = Rcx::new(fcx, Repeating(0), SubjectNode::None);
+    let mut rcx = Rcx::new(fcx, RepeatingScope(0), 0, SubjectNode::None);
     for &component_ty in component_tys {
         // Check that each type outlives the empty region. Since the
         // empty region is a subregion of all others, this can't fail
@@ -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,
 
@@ -189,16 +193,18 @@ fn region_of_def(fcx: &FnCtxt, def: def::Def) -> ty::Region {
     }
 }
 
-pub enum RepeatingScope { Repeating(ast::NodeId) }
+struct RepeatingScope(ast::NodeId);
 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 Repeating(initial_repeating_scope) = initial_repeating_scope;
+        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,10 +214,12 @@ impl<'a, 'tcx> Rcx<'a, 'tcx> {
         self.fcx.ccx.tcx
     }
 
-    pub fn set_repeating_scope(&mut self, scope: ast::NodeId) -> ast::NodeId {
-        let old_scope = self.repeating_scope;
-        self.repeating_scope = scope;
-        old_scope
+    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)
     }
 
     /// Try to resolve the type for the given node, returning t_err if an error results.  Note that
@@ -269,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) {
@@ -283,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 =
@@ -326,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();
 
@@ -335,25 +353,22 @@ 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 constraints =
-                regionmanip::region_wf_constraints(
-                    tcx,
-                    ty,
-                    body_scope);
-            for constraint in &constraints {
-                debug!("constraint: {}", constraint.repr(tcx));
-                match *constraint {
-                    regionmanip::RegionSubRegionConstraint(_,
-                                              ty::ReFree(free_a),
-                                              ty::ReFree(free_b)) => {
+            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)) => {
                         tcx.region_maps.relate_free_regions(free_a, free_b);
                     }
-                    regionmanip::RegionSubRegionConstraint(_,
-                                              ty::ReFree(free_a),
-                                              ty::ReInfer(ty::ReVar(vid_b))) => {
+                    implicator::Implication::RegionSubRegion(_,
+                                                             ty::ReFree(free_a),
+                                                             ty::ReInfer(ty::ReVar(vid_b))) => {
                         self.fcx.inh.infcx.add_given(free_a, vid_b);
                     }
-                    regionmanip::RegionSubRegionConstraint(..) => {
+                    implicator::Implication::RegionSubRegion(..) => {
                         // In principle, we could record (and take
                         // advantage of) every relationship here, but
                         // we are also free not to -- it simply means
@@ -364,12 +379,13 @@ impl<'a, 'tcx> Rcx<'a, 'tcx> {
                         // relationship that arises here, but
                         // presently we do not.)
                     }
-                    regionmanip::RegionSubGenericConstraint(_, r_a, ref generic_b) => {
-                        debug!("RegionSubGenericConstraint: {} <= {}",
+                    implicator::Implication::RegionSubGeneric(_, r_a, ref generic_b) => {
+                        debug!("RegionSubGeneric: {} <= {}",
                                r_a.repr(tcx), generic_b.repr(tcx));
 
                         self.region_bound_pairs.push((r_a, generic_b.clone()));
                     }
+                    implicator::Implication::Predicate(..) => { }
                 }
             }
         }
@@ -400,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); }
@@ -628,7 +644,7 @@ fn visit_expr(rcx: &mut Rcx, expr: &ast::Expr) {
                     constrain_call(rcx, expr, Some(&**base),
                                    None::<ast::Expr>.iter(), true);
                     let fn_ret = // late-bound regions in overloaded method calls are instantiated
-                        ty::assert_no_late_bound_regions(rcx.tcx(), &ty::ty_fn_ret(method.ty));
+                        ty::no_late_bound_regions(rcx.tcx(), &ty::ty_fn_ret(method.ty)).unwrap();
                     fn_ret.unwrap()
                 }
                 None => rcx.resolve_node_type(base.id)
@@ -975,7 +991,7 @@ fn constrain_autoderefs<'a, 'tcx>(rcx: &mut Rcx<'a, 'tcx>,
                 // was applied on the base type, as that is always the case.
                 let fn_sig = ty::ty_fn_sig(method.ty);
                 let fn_sig = // late-bound regions should have been instantiated
-                    ty::assert_no_late_bound_regions(rcx.tcx(), fn_sig);
+                    ty::no_late_bound_regions(rcx.tcx(), fn_sig).unwrap();
                 let self_ty = fn_sig.inputs[0];
                 let (m, r) = match self_ty.sty {
                     ty::ty_rptr(r, ref m) => (m.mutbl, r),
@@ -1481,28 +1497,32 @@ pub fn type_must_outlive<'a, 'tcx>(rcx: &mut Rcx<'a, 'tcx>,
            ty.repr(rcx.tcx()),
            region.repr(rcx.tcx()));
 
-    let constraints =
-        regionmanip::region_wf_constraints(
-            rcx.tcx(),
-            ty,
-            region);
-    for constraint in &constraints {
-        debug!("constraint: {}", constraint.repr(rcx.tcx()));
-        match *constraint {
-            regionmanip::RegionSubRegionConstraint(None, r_a, r_b) => {
+    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 {
+            implicator::Implication::RegionSubRegion(None, r_a, r_b) => {
                 rcx.fcx.mk_subr(origin.clone(), r_a, r_b);
             }
-            regionmanip::RegionSubRegionConstraint(Some(ty), r_a, r_b) => {
+            implicator::Implication::RegionSubRegion(Some(ty), r_a, r_b) => {
                 let o1 = infer::ReferenceOutlivesReferent(ty, origin.span());
                 rcx.fcx.mk_subr(o1, r_a, r_b);
             }
-            regionmanip::RegionSubGenericConstraint(None, r_a, ref generic_b) => {
+            implicator::Implication::RegionSubGeneric(None, r_a, ref generic_b) => {
                 generic_must_outlive(rcx, origin.clone(), r_a, generic_b);
             }
-            regionmanip::RegionSubGenericConstraint(Some(ty), r_a, ref generic_b) => {
+            implicator::Implication::RegionSubGeneric(Some(ty), r_a, ref generic_b) => {
                 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 94670305be7..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 =
@@ -578,8 +574,8 @@ fn enum_variants<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>,
                     // the regions in the argument types come from the
                     // enum def'n, and hence will all be early bound
                     let arg_tys =
-                        ty::assert_no_late_bound_regions(
-                            fcx.tcx(), &ty::ty_fn_args(ctor_ty));
+                        ty::no_late_bound_regions(
+                            fcx.tcx(), &ty::ty_fn_args(ctor_ty)).unwrap();
                     AdtVariant {
                         fields: args.iter().enumerate().map(|(index, arg)| {
                             let arg_ty = arg_tys[index];
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..7d955065ff4
--- /dev/null
+++ b/src/test/compile-fail/regions-assoc-type-outlives-container-hrtb.rs
@@ -0,0 +1,70 @@
+// 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)]
+#![feature(rustc_attrs)]
+
+///////////////////////////////////////////////////////////////////////////
+
+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() { }
diff --git a/src/test/run-pass/traits-issue-22110.rs b/src/test/run-pass/traits-issue-22110.rs
new file mode 100644
index 00000000000..9cdcf4945d8
--- /dev/null
+++ b/src/test/run-pass/traits-issue-22110.rs
@@ -0,0 +1,34 @@
+// 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 an issue where we reported ambiguity between the where-clause
+// and the blanket impl. The only important thing is that compilation
+// succeeds here. Issue #22110.
+
+#![allow(dead_code)]
+
+trait Foo<A> {
+    fn foo(&self, a: A);
+}
+
+impl<A,F:Fn(A)> Foo<A> for F {
+    fn foo(&self, _: A) { }
+}
+
+fn baz<A,F:for<'a> Foo<(&'a A,)>>(_: F) { }
+
+fn components<T,A>(t: fn(&A))
+    where fn(&A) : for<'a> Foo<(&'a A,)>,
+{
+    baz(t)
+}
+
+fn main() {
+}