16 files changed, 303 insertions, 100 deletions

diff --git a/src/librustc/metadata/tydecode.rs b/src/librustc/metadata/tydecode.rs
index cce31b1f4c2..955905ee263 100644
--- a/src/librustc/metadata/tydecode.rs
+++ b/src/librustc/metadata/tydecode.rs
@@ -341,7 +341,12 @@ fn parse_region_<F>(st: &mut PState, conv: &mut F) -> ty::Region where
         let index = parse_u32(st);
         assert_eq!(next(st), '|');
         let nm = token::str_to_ident(&parse_str(st, ']'));
-        ty::ReEarlyBound(node_id, space, index, nm.name)
+        ty::ReEarlyBound(ty::EarlyBoundRegion {
+            param_id: node_id,
+            space: space,
+            index: index,
+            name: nm.name
+        })
       }
       'f' => {
         assert_eq!(next(st), '[');
diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs
index 90a905f1840..8a278811282 100644
--- a/src/librustc/metadata/tyencode.rs
+++ b/src/librustc/metadata/tyencode.rs
@@ -241,12 +241,12 @@ pub fn enc_region(w: &mut Encoder, cx: &ctxt, r: ty::Region) {
             enc_bound_region(w, cx, br);
             mywrite!(w, "]");
         }
-        ty::ReEarlyBound(node_id, space, index, name) => {
+        ty::ReEarlyBound(ref data) => {
             mywrite!(w, "B[{}|{}|{}|{}]",
-                     node_id,
-                     space.to_uint(),
-                     index,
-                     token::get_name(name));
+                     data.param_id,
+                     data.space.to_uint(),
+                     data.index,
+                     token::get_name(data.name));
         }
         ty::ReFree(ref fr) => {
             mywrite!(w, "f[");
diff --git a/src/librustc/middle/astencode.rs b/src/librustc/middle/astencode.rs
index 2b8540a34b1..7ee0ea4fd66 100644
--- a/src/librustc/middle/astencode.rs
+++ b/src/librustc/middle/astencode.rs
@@ -496,8 +496,13 @@ impl tr for ty::Region {
             ty::ReLateBound(debruijn, br) => {
                 ty::ReLateBound(debruijn, br.tr(dcx))
             }
-            ty::ReEarlyBound(id, space, index, ident) => {
-                ty::ReEarlyBound(dcx.tr_id(id), space, index, ident)
+            ty::ReEarlyBound(data) => {
+                ty::ReEarlyBound(ty::EarlyBoundRegion {
+                    param_id: dcx.tr_id(data.param_id),
+                    space: data.space,
+                    index: data.index,
+                    name: data.name,
+                })
             }
             ty::ReScope(scope) => {
                 ty::ReScope(scope.tr(dcx))
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index 5131322dc41..2f7296051c5 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -603,14 +603,11 @@ impl RegionMaps {
                     self.sub_free_region(sub_fr, super_fr)
                 }
 
-                (ty::ReEarlyBound(param_id_a, param_space_a, index_a, _),
-                 ty::ReEarlyBound(param_id_b, param_space_b, index_b, _)) => {
+                (ty::ReEarlyBound(data_a), ty::ReEarlyBound(data_b)) => {
                     // This case is used only to make sure that explicitly-
                     // specified `Self` types match the real self type in
-                    // implementations.
-                    param_id_a == param_id_b &&
-                        param_space_a == param_space_b &&
-                        index_a == index_b
+                    // implementations. Yuck.
+                    data_a == data_b
                 }
 
                 _ => {
diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index d9cdf0fa1cb..29f718fd097 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -622,11 +622,11 @@ impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> {
         // regions that appear in a function signature is done using
         // the specialized routine `ty::replace_late_regions()`.
         match r {
-            ty::ReEarlyBound(_, space, i, region_name) => {
+            ty::ReEarlyBound(data) => {
                 match self.substs.regions {
                     ErasedRegions => ty::ReStatic,
                     NonerasedRegions(ref regions) =>
-                        match regions.opt_get(space, i as usize) {
+                        match regions.opt_get(data.space, data.index as usize) {
                             Some(&r) => {
                                 self.shift_region_through_binders(r)
                             }
@@ -635,11 +635,12 @@ impl<'a, 'tcx> TypeFolder<'tcx> for SubstFolder<'a, 'tcx> {
                                 self.tcx().sess.span_bug(
                                     span,
                                     &format!("Type parameter out of range \
-                                     when substituting in region {} (root type={}) \
-                                     (space={:?}, index={})",
-                                    region_name.as_str(),
-                                    self.root_ty.repr(self.tcx()),
-                                    space, i));
+                                              when substituting in region {} (root type={}) \
+                                              (space={:?}, index={})",
+                                             data.name.as_str(),
+                                             self.root_ty.repr(self.tcx()),
+                                             data.space,
+                                             data.index));
                             }
                         }
                 }
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index eab87dc846d..53c3cdd02af 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -1134,10 +1134,7 @@ pub enum Region {
     // Region bound in a type or fn declaration which will be
     // substituted 'early' -- that is, at the same time when type
     // parameters are substituted.
-    ReEarlyBound(/* param id */ ast::NodeId,
-                 subst::ParamSpace,
-                 /*index*/ u32,
-                 ast::Name),
+    ReEarlyBound(EarlyBoundRegion),
 
     // Region bound in a function scope, which will be substituted when the
     // function is called.
@@ -1169,6 +1166,14 @@ pub enum Region {
     ReEmpty,
 }
 
+#[derive(Copy, Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
+pub struct EarlyBoundRegion {
+    pub param_id: ast::NodeId,
+    pub space: subst::ParamSpace,
+    pub index: u32,
+    pub name: ast::Name,
+}
+
 /// Upvars do not get their own node-id. Instead, we use the pair of
 /// the original var id (that is, the root variable that is referenced
 /// by the upvar) and the id of the closure expression.
@@ -1761,7 +1766,12 @@ pub struct RegionParameterDef {
 
 impl RegionParameterDef {
     pub fn to_early_bound_region(&self) -> ty::Region {
-        ty::ReEarlyBound(self.def_id.node, self.space, self.index, self.name)
+        ty::ReEarlyBound(ty::EarlyBoundRegion {
+            param_id: self.def_id.node,
+            space: self.space,
+            index: self.index,
+            name: self.name,
+        })
     }
     pub fn to_bound_region(&self) -> ty::BoundRegion {
         ty::BoundRegion::BrNamed(self.def_id, self.name)
@@ -7071,8 +7081,7 @@ pub fn make_substs_for_receiver_types<'tcx>(tcx: &ty::ctxt<'tcx>,
     let meth_regions: Vec<ty::Region> =
         method.generics.regions.get_slice(subst::FnSpace)
               .iter()
-              .map(|def| ty::ReEarlyBound(def.def_id.node, def.space,
-                                          def.index, def.name))
+              .map(|def| def.to_early_bound_region())
               .collect();
     trait_ref.substs.clone().with_method(meth_tps, meth_regions)
 }
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 650f40a8291..12a6d584857 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -163,8 +163,8 @@ pub fn explain_region_and_span(cx: &ctxt, region: ty::Region)
 
       ReEmpty => { ("the empty lifetime".to_string(), None) }
 
-      ReEarlyBound(_, _, _, name) => {
-        (format!("{}", token::get_name(name)), None)
+      ReEarlyBound(ref data) => {
+        (format!("{}", token::get_name(data.name)), None)
       }
 
       // I believe these cases should not occur (except when debugging,
@@ -223,8 +223,8 @@ pub fn region_to_string(cx: &ctxt, prefix: &str, space: bool, region: Region) ->
     // `explain_region()` or `note_and_explain_region()`.
     match region {
         ty::ReScope(_) => prefix.to_string(),
-        ty::ReEarlyBound(_, _, _, name) => {
-            token::get_name(name).to_string()
+        ty::ReEarlyBound(ref data) => {
+            token::get_name(data.name).to_string()
         }
         ty::ReLateBound(_, br) => bound_region_to_string(cx, prefix, space, br),
         ty::ReFree(ref fr) => bound_region_to_string(cx, prefix, space, fr.bound_region),
@@ -903,12 +903,12 @@ impl<'tcx> Repr<'tcx> for ty::BoundRegion {
 impl<'tcx> Repr<'tcx> for ty::Region {
     fn repr(&self, tcx: &ctxt) -> String {
         match *self {
-            ty::ReEarlyBound(id, space, index, name) => {
+            ty::ReEarlyBound(ref data) => {
                 format!("ReEarlyBound({}, {:?}, {}, {})",
-                               id,
-                               space,
-                               index,
-                               token::get_name(name))
+                        data.param_id,
+                        data.space,
+                        data.index,
+                        token::get_name(data.name))
             }
 
             ty::ReLateBound(binder_id, ref bound_region) => {
diff --git a/src/librustc_driver/test.rs b/src/librustc_driver/test.rs
index f9be71561e3..12b16e95a71 100644
--- a/src/librustc_driver/test.rs
+++ b/src/librustc_driver/test.rs
@@ -290,7 +290,12 @@ impl<'a, 'tcx> Env<'a, 'tcx> {
                           -> ty::Region
     {
         let name = token::intern(name);
-        ty::ReEarlyBound(ast::DUMMY_NODE_ID, space, index, name)
+        ty::ReEarlyBound(ty::EarlyBoundRegion {
+            param_id: ast::DUMMY_NODE_ID,
+            space: space,
+            index: index,
+            name: name
+        })
     }
 
     pub fn re_late_bound_with_debruijn(&self, id: u32, debruijn: ty::DebruijnIndex) -> ty::Region {
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index e37e9c97018..171c83d00e4 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -161,7 +161,12 @@ pub fn ast_region_to_region(tcx: &ty::ctxt, lifetime: &ast::Lifetime)
         }
 
         Some(&rl::DefEarlyBoundRegion(space, index, id)) => {
-            ty::ReEarlyBound(id, space, index, lifetime.name)
+            ty::ReEarlyBound(ty::EarlyBoundRegion {
+                param_id: id,
+                space: space,
+                index: index,
+                name: lifetime.name
+            })
         }
 
         Some(&rl::DefFreeRegion(scope, id)) => {
diff --git a/src/librustc_typeck/check/wf.rs b/src/librustc_typeck/check/wf.rs
index 7f2af1d1b62..83e0c398590 100644
--- a/src/librustc_typeck/check/wf.rs
+++ b/src/librustc_typeck/check/wf.rs
@@ -10,7 +10,7 @@
 
 use astconv::AstConv;
 use check::{FnCtxt, Inherited, blank_fn_ctxt, vtable, regionck};
-use constrained_type_params::identify_constrained_type_params;
+use constrained_type_params::{identify_constrained_type_params, Parameter};
 use CrateCtxt;
 use middle::region;
 use middle::subst::{self, TypeSpace, FnSpace, ParamSpace, SelfSpace};
@@ -287,10 +287,11 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
 
         let mut constrained_parameters: HashSet<_> =
             variances.types
-            .iter_enumerated()
-            .filter(|&(_, _, &variance)| variance != ty::Bivariant)
-            .map(|(space, index, _)| self.param_ty(ast_generics, space, index))
-            .collect();
+                     .iter_enumerated()
+                     .filter(|&(_, _, &variance)| variance != ty::Bivariant)
+                     .map(|(space, index, _)| self.param_ty(ast_generics, space, index))
+                     .map(|p| Parameter::Type(p))
+                     .collect();
 
         identify_constrained_type_params(self.tcx(),
                                          ty_predicates.predicates.as_slice(),
@@ -299,7 +300,7 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> {
 
         for (space, index, _) in variances.types.iter_enumerated() {
             let param_ty = self.param_ty(ast_generics, space, index);
-            if constrained_parameters.contains(&param_ty) {
+            if constrained_parameters.contains(&Parameter::Type(param_ty)) {
                 continue;
             }
             let span = self.ty_param_span(ast_generics, item, space, index);
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index e5022b98918..5ed93703d97 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -66,7 +66,7 @@ There are some shortcomings in this design:
 
 use astconv::{self, AstConv, ty_of_arg, ast_ty_to_ty, ast_region_to_region};
 use middle::def;
-use constrained_type_params::identify_constrained_type_params;
+use constrained_type_params as ctp;
 use middle::lang_items::SizedTraitLangItem;
 use middle::region;
 use middle::resolve_lifetime;
@@ -902,9 +902,10 @@ fn convert_item(ccx: &CrateCtxt, it: &ast::Item) {
                 tcx.impl_trait_refs.borrow_mut().insert(it.id, trait_ref);
             }
 
-            enforce_impl_ty_params_are_constrained(tcx,
-                                                   generics,
-                                                   local_def(it.id));
+            enforce_impl_params_are_constrained(tcx,
+                                                generics,
+                                                local_def(it.id),
+                                                impl_items);
         },
         ast::ItemTrait(_, _, _, ref trait_items) => {
             let trait_def = trait_def_of_item(ccx, it);
@@ -1217,10 +1218,12 @@ fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
             generics.lifetimes
                     .iter()
                     .enumerate()
-                    .map(|(i, def)| ty::ReEarlyBound(def.lifetime.id,
-                                                     TypeSpace,
-                                                     i as u32,
-                                                     def.lifetime.name))
+                    .map(|(i, def)| ty::ReEarlyBound(ty::EarlyBoundRegion {
+                        param_id: def.lifetime.id,
+                        space: TypeSpace,
+                        index: i as u32,
+                        name: def.lifetime.name
+                    }))
                     .collect();
 
         // Start with the generics in the type parameters...
@@ -1691,7 +1694,13 @@ fn ty_generic_predicates<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>,
     let early_lifetimes = early_bound_lifetimes_from_generics(space, ast_generics);
     for (index, param) in early_lifetimes.iter().enumerate() {
         let index = index as u32;
-        let region = ty::ReEarlyBound(param.lifetime.id, space, index, param.lifetime.name);
+        let region =
+            ty::ReEarlyBound(ty::EarlyBoundRegion {
+                param_id: param.lifetime.id,
+                space: space,
+                index: index,
+                name: param.lifetime.name
+            });
         for bound in &param.bounds {
             let bound_region = ast_region_to_region(ccx.tcx, bound);
             let outlives = ty::Binder(ty::OutlivesPredicate(region, bound_region));
@@ -2168,10 +2177,10 @@ fn check_method_self_type<'a, 'tcx, RS:RegionScope>(
 
         ty_fold::fold_regions(tcx, value, |region, _| {
             match region {
-                ty::ReEarlyBound(id, _, _, name) => {
-                    let def_id = local_def(id);
+                ty::ReEarlyBound(data) => {
+                    let def_id = local_def(data.param_id);
                     ty::ReFree(ty::FreeRegion { scope: scope,
-                                                bound_region: ty::BrNamed(def_id, name) })
+                                                bound_region: ty::BrNamed(def_id, data.name) })
                 }
                 _ => region
             }
@@ -2180,9 +2189,10 @@ fn check_method_self_type<'a, 'tcx, RS:RegionScope>(
 }
 
 /// Checks that all the type parameters on an impl
-fn enforce_impl_ty_params_are_constrained<'tcx>(tcx: &ty::ctxt<'tcx>,
-                                                ast_generics: &ast::Generics,
-                                                impl_def_id: ast::DefId)
+fn enforce_impl_params_are_constrained<'tcx>(tcx: &ty::ctxt<'tcx>,
+                                             ast_generics: &ast::Generics,
+                                             impl_def_id: ast::DefId,
+                                             impl_items: &[P<ast::ImplItem>])
 {
     let impl_scheme = ty::lookup_item_type(tcx, impl_def_id);
     let impl_predicates = ty::lookup_predicates(tcx, impl_def_id);
@@ -2192,27 +2202,81 @@ fn enforce_impl_ty_params_are_constrained<'tcx>(tcx: &ty::ctxt<'tcx>,
     // reachable from there, to start (if this is an inherent impl,
     // then just examine the self type).
     let mut input_parameters: HashSet<_> =
-        impl_trait_ref.iter()
-                      .flat_map(|t| t.input_types().iter()) // Types in trait ref, if any
-                      .chain(Some(impl_scheme.ty).iter())   // Self type, always
-                      .flat_map(|t| t.walk())
-                      .filter_map(|t| t.as_opt_param_ty())
-                      .collect();
-
-    identify_constrained_type_params(tcx,
-                                     impl_predicates.predicates.as_slice(),
-                                     impl_trait_ref,
-                                     &mut input_parameters);
+        ctp::parameters_for_type(impl_scheme.ty).into_iter().collect();
+    if let Some(ref trait_ref) = impl_trait_ref {
+        input_parameters.extend(ctp::parameters_for_trait_ref(trait_ref));
+    }
+
+    ctp::identify_constrained_type_params(tcx,
+                                          impl_predicates.predicates.as_slice(),
+                                          impl_trait_ref,
+                                          &mut input_parameters);
 
     for (index, ty_param) in ast_generics.ty_params.iter().enumerate() {
         let param_ty = ty::ParamTy { space: TypeSpace,
                                      idx: index as u32,
                                      name: ty_param.ident.name };
-        if !input_parameters.contains(&param_ty) {
-            span_err!(tcx.sess, ty_param.span, E0207,
-                "the type parameter `{}` is not constrained by the \
-                         impl trait, self type, or predicates",
-                        param_ty.user_string(tcx));
+        if !input_parameters.contains(&ctp::Parameter::Type(param_ty)) {
+            report_unused_parameter(tcx, ty_param.span, "type", &param_ty.user_string(tcx));
         }
     }
+
+    // Every lifetime used in an associated type must be constrained.
+
+    let lifetimes_in_associated_types: HashSet<_> =
+        impl_items.iter()
+                  .filter_map(|item| match item.node {
+                      ast::TypeImplItem(..) => Some(ty::node_id_to_type(tcx, item.id)),
+                      ast::MethodImplItem(..) | ast::MacImplItem(..) => None,
+                  })
+                  .flat_map(|ty| ctp::parameters_for_type(ty).into_iter())
+                  .filter_map(|p| match p {
+                      ctp::Parameter::Type(_) => None,
+                      ctp::Parameter::Region(r) => Some(r),
+                  })
+                  .collect();
+
+    for (index, lifetime_def) in ast_generics.lifetimes.iter().enumerate() {
+        let region = ty::EarlyBoundRegion { param_id: lifetime_def.lifetime.id,
+                                            space: TypeSpace,
+                                            index: index as u32,
+                                            name: lifetime_def.lifetime.name };
+        if
+            lifetimes_in_associated_types.contains(&region) && // (*)
+            !input_parameters.contains(&ctp::Parameter::Region(region))
+        {
+            report_unused_parameter(tcx, lifetime_def.lifetime.span,
+                                    "lifetime", &region.name.user_string(tcx));
+        }
+    }
+
+    // (*) This is a horrible concession to reality. I think it'd be
+    // better to just ban unconstrianed lifetimes outright, but in
+    // practice people do non-hygenic macros like:
+    //
+    // ```
+    // macro_rules! __impl_slice_eq1 {
+    //     ($Lhs: ty, $Rhs: ty, $Bound: ident) => {
+    //         impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs where A: PartialEq<B> {
+    //            ....
+    //         }
+    //     }
+    // }
+    // ```
+    //
+    // In a concession to backwards compatbility, we continue to
+    // permit those, so long as the lifetimes aren't used in
+    // associated types. I believe this is sound, because lifetimes
+    // used elsewhere are not projected back out.
+}
+
+fn report_unused_parameter(tcx: &ty::ctxt,
+                           span: Span,
+                           kind: &str,
+                           name: &str)
+{
+    span_err!(tcx.sess, span, E0207,
+              "the {} parameter `{}` is not constrained by the \
+               impl trait, self type, or predicates",
+              kind, name);
 }
diff --git a/src/librustc_typeck/constrained_type_params.rs b/src/librustc_typeck/constrained_type_params.rs
index 83d7e985000..fad8fbef2a4 100644
--- a/src/librustc_typeck/constrained_type_params.rs
+++ b/src/librustc_typeck/constrained_type_params.rs
@@ -8,49 +8,101 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use middle::ty::{self};
+use middle::subst;
+use middle::ty::{self, Ty};
 
 use std::collections::HashSet;
 use std::rc::Rc;
 
+#[derive(Clone, PartialEq, Eq, Hash, Debug)]
+pub enum Parameter {
+    Type(ty::ParamTy),
+    Region(ty::EarlyBoundRegion),
+}
+
+pub fn parameters_for_type<'tcx>(ty: Ty<'tcx>) -> Vec<Parameter> {
+    ty.walk()
+      .flat_map(|ty| parameters_for_type_shallow(ty).into_iter())
+      .collect()
+}
+
+pub fn parameters_for_trait_ref<'tcx>(trait_ref: &Rc<ty::TraitRef<'tcx>>) -> Vec<Parameter> {
+    let mut region_parameters =
+        parameters_for_regions_in_substs(&trait_ref.substs);
+
+    let type_parameters =
+        trait_ref.substs.types.iter()
+                              .flat_map(|ty| parameters_for_type(ty).into_iter());
+
+    region_parameters.extend(type_parameters);
+
+    region_parameters
+}
+
+fn parameters_for_type_shallow<'tcx>(ty: Ty<'tcx>) -> Vec<Parameter> {
+    match ty.sty {
+        ty::ty_param(ref d) =>
+            vec![Parameter::Type(d.clone())],
+        ty::ty_rptr(region, _) =>
+            parameters_for_region(region).into_iter().collect(),
+        ty::ty_struct(_, substs) |
+        ty::ty_enum(_, substs) =>
+            parameters_for_regions_in_substs(substs),
+        ty::ty_trait(ref data) =>
+            parameters_for_regions_in_substs(&data.principal.skip_binder().substs),
+        _ =>
+            vec![],
+    }
+}
+
+fn parameters_for_regions_in_substs(substs: &subst::Substs) -> Vec<Parameter> {
+    substs.regions()
+          .iter()
+          .filter_map(|r| parameters_for_region(r))
+          .collect()
+}
+
+fn parameters_for_region(region: &ty::Region) -> Option<Parameter> {
+    match *region {
+        ty::ReEarlyBound(data) => Some(Parameter::Region(data)),
+        _ => None,
+    }
+}
+
 pub fn identify_constrained_type_params<'tcx>(_tcx: &ty::ctxt<'tcx>,
                                               predicates: &[ty::Predicate<'tcx>],
                                               impl_trait_ref: Option<Rc<ty::TraitRef<'tcx>>>,
-                                              input_parameters: &mut HashSet<ty::ParamTy>)
+                                              input_parameters: &mut HashSet<Parameter>)
 {
     loop {
         let num_inputs = input_parameters.len();
 
-        let projection_predicates =
+        let poly_projection_predicates = // : iterator over PolyProjectionPredicate
             predicates.iter()
                       .filter_map(|predicate| {
                           match *predicate {
-                              // Ignore higher-ranked binders. For the purposes
-                              // of this check, they don't matter because they
-                              // only affect named regions, and we're just
-                              // concerned about type parameters here.
-                              ty::Predicate::Projection(ref data) => Some(data.0.clone()),
+                              ty::Predicate::Projection(ref data) => Some(data.clone()),
                               _ => None,
                           }
                       });
 
-        for projection in projection_predicates {
+        for poly_projection in poly_projection_predicates {
+            // Note that we can skip binder here because the impl
+            // trait ref never contains any late-bound regions.
+            let projection = poly_projection.skip_binder();
+
             // Special case: watch out for some kind of sneaky attempt
-            // to project out an associated type defined by this very trait.
-            if Some(projection.projection_ty.trait_ref.clone()) == impl_trait_ref {
+            // to project out an associated type defined by this very
+            // trait.
+            let unbound_trait_ref = &projection.projection_ty.trait_ref;
+            if Some(unbound_trait_ref.clone()) == impl_trait_ref {
                 continue;
             }
 
-            let relies_only_on_inputs =
-                projection.projection_ty.trait_ref.input_types()
-                                                  .iter()
-                                                  .flat_map(|t| t.walk())
-                                                  .filter_map(|t| t.as_opt_param_ty())
-                                                  .all(|t| input_parameters.contains(&t));
-
+            let inputs = parameters_for_trait_ref(&projection.projection_ty.trait_ref);
+            let relies_only_on_inputs = inputs.iter().all(|p| input_parameters.contains(&p));
             if relies_only_on_inputs {
-                input_parameters.extend(
-                    projection.ty.walk().filter_map(|t| t.as_opt_param_ty()));
+                input_parameters.extend(parameters_for_type(projection.ty));
             }
         }
 
diff --git a/src/librustc_typeck/variance.rs b/src/librustc_typeck/variance.rs
index da2de731d64..7575f12878a 100644
--- a/src/librustc_typeck/variance.rs
+++ b/src/librustc_typeck/variance.rs
@@ -1046,9 +1046,9 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
                                    region: ty::Region,
                                    variance: VarianceTermPtr<'a>) {
         match region {
-            ty::ReEarlyBound(param_id, _, _, _) => {
-                if self.is_to_be_inferred(param_id) {
-                    let index = self.inferred_index(param_id);
+            ty::ReEarlyBound(ref data) => {
+                if self.is_to_be_inferred(data.param_id) {
+                    let index = self.inferred_index(data.param_id);
                     self.add_constraint(index, variance);
                 }
             }
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index f7fbb67e08a..23c9edde77c 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -775,7 +775,7 @@ impl Clean<Option<Lifetime>> for ty::Region {
             ty::ReStatic => Some(Lifetime::statik()),
             ty::ReLateBound(_, ty::BrNamed(_, name)) =>
                 Some(Lifetime(token::get_name(name).to_string())),
-            ty::ReEarlyBound(_, _, _, name) => Some(Lifetime(name.clean(cx))),
+            ty::ReEarlyBound(ref data) => Some(Lifetime(data.name.clean(cx))),
 
             ty::ReLateBound(..) |
             ty::ReFree(..) |
diff --git a/src/test/compile-fail/impl-unused-rps-in-assoc-type.rs b/src/test/compile-fail/impl-unused-rps-in-assoc-type.rs
new file mode 100644
index 00000000000..23401db21d8
--- /dev/null
+++ b/src/test/compile-fail/impl-unused-rps-in-assoc-type.rs
@@ -0,0 +1,28 @@
+// 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 lifetime parameters must be constrained if they appear in
+// an associated type def'n. Issue #22077.
+
+trait Fun {
+    type Output;
+    fn call<'x>(&'x self) -> Self::Output;
+}
+
+struct Holder { x: String }
+
+impl<'a> Fun for Holder { //~ ERROR E0207
+    type Output = &'a str;
+    fn call<'b>(&'b self) -> &'b str {
+        &self.x[..]
+    }
+}
+
+fn main() { }
diff --git a/src/test/compile-fail/issue-22886.rs b/src/test/compile-fail/issue-22886.rs
new file mode 100644
index 00000000000..4aa2571cad0
--- /dev/null
+++ b/src/test/compile-fail/issue-22886.rs
@@ -0,0 +1,31 @@
+// 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 #22886.
+
+fn crash_please() {
+    let mut iter = Newtype(Some(Box::new(0)));
+    let saved = iter.next().unwrap();
+    println!("{}", saved);
+    iter.0 = None;
+    println!("{}", saved);
+}
+
+struct Newtype(Option<Box<usize>>);
+
+impl<'a> Iterator for Newtype { //~ ERROR E0207
+    type Item = &'a Box<usize>;
+
+    fn next(&mut self) -> Option<&Box<usize>> {
+        self.0.as_ref()
+    }
+}
+
+fn main() { }