Auto merge of #24461 - nikomatsakis:issue-22077-unused-lifetimes, r=aturon

This makes it illegal to have unconstrained lifetimes that appear in an associated type definition. Arguably, we should prohibit all unconstrained lifetimes -- but it would break various macros. It'd be good to evaluate how large a break change it would be. But this seems like the minimal change we need to do to establish soundness, so we should land it regardless. Another variant would be to prohibit all lifetimes that appear in any impl item, not just associated types. I don't think that's necessary for soundness -- associated types are different because they can be projected -- but it would feel a bit more consistent and "obviously" safe. I'll experiment with that in the meantime.

r? @aturon 

Fixes #22077.

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() { }