Implemented for traits (associated type definitions).

12 files changed, 313 insertions, 250 deletions

diff --git a/src/librustc/hir/intravisit.rs b/src/librustc/hir/intravisit.rs
index f838ec84d8b..da4d41c9d87 100644
--- a/src/librustc/hir/intravisit.rs
+++ b/src/librustc/hir/intravisit.rs
@@ -626,6 +626,9 @@ pub fn walk_ty<'v, V: Visitor<'v>>(visitor: &mut V, typ: &'v Ty) {
         TyKind::CVarArgs(ref lt) => {
             visitor.visit_lifetime(lt)
         }
+        TyKind::AssocTyExistential(ref bounds) => {
+            walk_list!(visitor, visit_param_bound, bounds);
+        }
         TyKind::Infer | TyKind::Err => {}
     }
 }
diff --git a/src/librustc/hir/lowering.rs b/src/librustc/hir/lowering.rs
index 5a0e9d53b08..2c2cd6a2f6f 100644
--- a/src/librustc/hir/lowering.rs
+++ b/src/librustc/hir/lowering.rs
@@ -195,6 +195,12 @@ enum ImplTraitContext<'a> {
     /// (e.g., for consts and statics).
     Existential(Option<DefId> /* fn def-ID */),
 
+    /// Treat `impl Trait` as a bound on the associated type applied to the trait.
+    /// Example: `trait Foo { type Bar: Iterator<Item = impl Debug>; }` is conceptually
+    /// equivalent to `trait Foo where <Self::Bar as Iterator>::Item: Debug
+    /// { type Bar: Iterator; }`.
+    AssociatedTy,
+
     /// `impl Trait` is not accepted in this position.
     Disallowed(ImplTraitPosition),
 }
@@ -217,6 +223,7 @@ impl<'a> ImplTraitContext<'a> {
         match self {
             Universal(params) => Universal(params),
             Existential(fn_def_id) => Existential(*fn_def_id),
+            AssociatedTy => AssociatedTy,
             Disallowed(pos) => Disallowed(*pos),
         }
     }
@@ -1537,6 +1544,16 @@ impl<'a> LoweringContext<'a> {
                             }),
                         ))
                     }
+                    ImplTraitContext::AssociatedTy => {
+                        let hir_bounds = self.lower_param_bounds(
+                            bounds,
+                            ImplTraitContext::AssociatedTy,
+                        );
+
+                        hir::TyKind::AssocTyExistential(
+                            hir_bounds,
+                        )
+                    }
                     ImplTraitContext::Disallowed(pos) => {
                         let allowed_in = if self.sess.features_untracked()
                                                 .impl_trait_in_bindings {
@@ -1640,8 +1657,8 @@ impl<'a> LoweringContext<'a> {
         })
     }
 
-    /// Registers a new existential type with the proper `NodeId`ss and
-    /// returns the lowered node ID for the existential type.
+    /// Registers a new existential type with the proper `NodeId`s and
+    /// returns the lowered node-ID for the existential type.
     fn generate_existential_type(
         &mut self,
         exist_ty_node_id: NodeId,
@@ -2226,8 +2243,9 @@ impl<'a> LoweringContext<'a> {
         (
             hir::GenericArgs {
                 args: args.iter().map(|a| self.lower_generic_arg(a, itctx.reborrow())).collect(),
-                bindings: constraints.iter().map(
-                    |b| self.lower_assoc_ty_constraint(b, itctx.reborrow())).collect(),
+                bindings: constraints.iter()
+                    .map(|b| self.lower_assoc_ty_constraint(b, itctx.reborrow()))
+                    .collect(),
                 parenthesized: false,
             },
             !has_types && param_mode == ParamMode::Optional
@@ -3257,13 +3275,13 @@ impl<'a> LoweringContext<'a> {
             ItemKind::ForeignMod(ref nm) => hir::ItemKind::ForeignMod(self.lower_foreign_mod(nm)),
             ItemKind::GlobalAsm(ref ga) => hir::ItemKind::GlobalAsm(self.lower_global_asm(ga)),
             ItemKind::Ty(ref t, ref generics) => hir::ItemKind::Ty(
-                self.lower_ty(t, ImplTraitContext::disallowed()),
-                self.lower_generics(generics, ImplTraitContext::disallowed()),
+                self.lower_ty(t, ImplTraitContext::AssociatedTy),
+                self.lower_generics(generics, ImplTraitContext::AssociatedTy),
             ),
             ItemKind::Existential(ref b, ref generics) => hir::ItemKind::Existential(
                 hir::ExistTy {
-                    generics: self.lower_generics(generics, ImplTraitContext::disallowed()),
-                    bounds: self.lower_param_bounds(b, ImplTraitContext::Existential(None)),
+                    generics: self.lower_generics(generics, ImplTraitContext::AssociatedTy),
+                    bounds: self.lower_param_bounds(b, ImplTraitContext::AssociatedTy),
                     impl_trait_fn: None,
                     origin: hir::ExistTyOrigin::ExistentialType,
                 },
@@ -3276,20 +3294,20 @@ impl<'a> LoweringContext<'a> {
                         .map(|x| self.lower_variant(x))
                         .collect(),
                 },
-                self.lower_generics(generics, ImplTraitContext::disallowed()),
+                self.lower_generics(generics, ImplTraitContext::AssociatedTy),
             ),
             ItemKind::Struct(ref struct_def, ref generics) => {
                 let struct_def = self.lower_variant_data(struct_def);
                 hir::ItemKind::Struct(
                     struct_def,
-                    self.lower_generics(generics, ImplTraitContext::disallowed()),
+                    self.lower_generics(generics, ImplTraitContext::AssociatedTy),
                 )
             }
             ItemKind::Union(ref vdata, ref generics) => {
                 let vdata = self.lower_variant_data(vdata);
                 hir::ItemKind::Union(
                     vdata,
-                    self.lower_generics(generics, ImplTraitContext::disallowed()),
+                    self.lower_generics(generics, ImplTraitContext::AssociatedTy),
                 )
             }
             ItemKind::Impl(
@@ -3656,15 +3674,17 @@ impl<'a> LoweringContext<'a> {
                 );
                 (generics, hir::TraitItemKind::Method(sig, hir::TraitMethod::Provided(body_id)))
             }
-            TraitItemKind::Type(ref bounds, ref default) => (
-                self.lower_generics(&i.generics, ImplTraitContext::disallowed()),
-                hir::TraitItemKind::Type(
-                    self.lower_param_bounds(bounds, ImplTraitContext::disallowed()),
+            TraitItemKind::Type(ref bounds, ref default) => {
+                let generics = self.lower_generics(&i.generics, ImplTraitContext::AssociatedTy);
+                let node = hir::TraitItemKind::Type(
+                    self.lower_param_bounds(bounds, ImplTraitContext::AssociatedTy),
                     default
                         .as_ref()
                         .map(|x| self.lower_ty(x, ImplTraitContext::disallowed())),
-                ),
-            ),
+                );
+
+                (generics, node)
+            },
             TraitItemKind::Macro(..) => bug!("macro item shouldn't exist at this point"),
         };
 
diff --git a/src/librustc/hir/mod.rs b/src/librustc/hir/mod.rs
index e29998db777..20968ec6a63 100644
--- a/src/librustc/hir/mod.rs
+++ b/src/librustc/hir/mod.rs
@@ -1898,6 +1898,8 @@ pub enum TyKind {
     /// Placeholder for C-variadic arguments. We "spoof" the `VaList` created
     /// from the variadic arguments. This type is only valid up to typeck.
     CVarArgs(Lifetime),
+    /// The existential type (i.e., `impl Trait`) that constrains an associated type.
+    AssocTyExistential(HirVec<GenericBound>),
 }
 
 #[derive(Clone, RustcEncodable, RustcDecodable, Debug, HashStable)]
diff --git a/src/librustc/hir/print.rs b/src/librustc/hir/print.rs
index 709a43c4734..c8f9e4c7043 100644
--- a/src/librustc/hir/print.rs
+++ b/src/librustc/hir/print.rs
@@ -409,6 +409,9 @@ impl<'a> State<'a> {
             hir::TyKind::CVarArgs(_) => {
                 self.s.word("...")?;
             }
+            hir::TyKind::AssocTyExistential(ref bounds) => {
+                self.print_bounds(":", bounds)?;
+            }
         }
         self.end()
     }
diff --git a/src/librustc/infer/opaque_types/mod.rs b/src/librustc/infer/opaque_types/mod.rs
index ef216110c9e..2127fbbd56e 100644
--- a/src/librustc/infer/opaque_types/mod.rs
+++ b/src/librustc/infer/opaque_types/mod.rs
@@ -948,15 +948,17 @@ pub fn may_define_existential_type(
     let mut hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
     trace!(
         "may_define_existential_type(def={:?}, opaque_node={:?})",
-        tcx.hir().get(hir_id),
-        tcx.hir().get(opaque_hir_id)
+        tcx.hir().get_by_hir_id(hir_id),
+        tcx.hir().get_by_hir_id(opaque_hir_id)
     );
 
     // Named existential types can be defined by any siblings or children of siblings.
-    let scope_id = tcx.hir().get_defining_scope(opaque_hir_id)
-                            .expect("could not get defining scope");
+    let scope_node_id = tcx.hir()
+        .get_defining_scope(tcx.hir().hir_to_node_id(opaque_hir_id))
+        .expect("could not get defining scope");
+    let scope_id = tcx.hir().node_to_hir_id(scope_node_id);
     // We walk up the node tree until we hit the root or the scope of the opaque type.
-    while hir_id != scope_id && hir_id != ast::CRATE_hir_ID {
+    while hir_id != scope_id && hir_id != hir::CRATE_HIR_ID {
         hir_id = tcx.hir().get_parent_item(hir_id);
     }
     // Syntactically, we are allowed to define the concrete type if:
diff --git a/src/librustc_interface/util.rs b/src/librustc_interface/util.rs
index f49f2110f23..fe24eab9f44 100644
--- a/src/librustc_interface/util.rs
+++ b/src/librustc_interface/util.rs
@@ -726,7 +726,8 @@ impl<'a> ReplaceBodyWithLoop<'a> {
                                 any_assoc_ty_bounds ||
                                 any_involves_impl_trait(types.into_iter()) ||
                                 any_involves_impl_trait(data.constraints.iter().filter_map(|c| {
-                                    if let ast::AssocTyConstraintKind::Equality { ref ty } = c.kind {
+                                    if let ast::AssocTyConstraintKind::Equality { ref ty }
+                                            = c.kind {
                                         Some(ty)
                                     } else {
                                         None
diff --git a/src/librustc_privacy/lib.rs b/src/librustc_privacy/lib.rs
index f084d3b9f28..6d01328cd16 100644
--- a/src/librustc_privacy/lib.rs
+++ b/src/librustc_privacy/lib.rs
@@ -1040,12 +1040,11 @@ impl<'a, 'tcx> Visitor<'tcx> for TypePrivacyVisitor<'a, 'tcx> {
         if !self.in_body {
             // Avoid calling `hir_trait_to_predicates` in bodies, it will ICE.
             // The traits' privacy in bodies is already checked as a part of trait object types.
-            let (principal, projections) =
-                rustc_typeck::hir_trait_to_predicates(self.tcx, trait_ref);
+            let (principal, bounds) = rustc_typeck::hir_trait_to_predicates(self.tcx, trait_ref);
             if self.visit_trait(*principal.skip_binder()) {
                 return;
             }
-            for (poly_predicate, _) in projections {
+            for (poly_predicate, _) in bounds.projection_bounds {
                 let tcx = self.tcx;
                 if self.visit(poly_predicate.skip_binder().ty) ||
                    self.visit_trait(poly_predicate.skip_binder().projection_ty.trait_ref(tcx)) {
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index f6e3f1a99e8..6123ee2af6e 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -8,6 +8,7 @@ use crate::hir::def::{CtorOf, Res, DefKind};
 use crate::hir::def_id::DefId;
 use crate::hir::HirVec;
 use crate::lint;
+use crate::middle::lang_items::SizedTraitLangItem;
 use crate::middle::resolve_lifetime as rl;
 use crate::namespace::Namespace;
 use rustc::lint::builtin::AMBIGUOUS_ASSOCIATED_ITEMS;
@@ -86,12 +87,22 @@ pub trait AstConv<'gcx, 'tcx> {
     fn record_ty(&self, hir_id: hir::HirId, ty: Ty<'tcx>, span: Span);
 }
 
+pub enum SizedByDefault {
+    Yes,
+    No,
+}
+
 struct ConvertedBinding<'tcx> {
     item_name: ast::Ident,
-    ty: Ty<'tcx>,
+    kind: ConvertedBindingKind<'tcx>,
     span: Span,
 }
 
+enum ConvertedBindingKind<'tcx> {
+    Equality(Ty<'tcx>),
+    Constraint(P<[hir::GenericBound]>),
+}
+
 #[derive(PartialEq)]
 enum GenericArgPosition {
     Type,
@@ -562,10 +573,10 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
     /// set of substitutions. This may involve applying defaulted type parameters.
     ///
     /// Note that the type listing given here is *exactly* what the user provided.
-    fn create_substs_for_ast_path(&self,
+    fn create_substs_for_ast_path<'a>(&self,
         span: Span,
         def_id: DefId,
-        generic_args: &hir::GenericArgs,
+        generic_args: &'a hir::GenericArgs,
         infer_types: bool,
         self_ty: Option<Ty<'tcx>>)
         -> (SubstsRef<'tcx>, Vec<ConvertedBinding<'tcx>>, Option<Vec<Span>>)
@@ -688,13 +699,20 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
             },
         );
 
-        let assoc_bindings = generic_args.bindings.iter().map(|binding| {
-            ConvertedBinding {
-                item_name: binding.ident,
-                ty: self.ast_ty_to_ty(&binding.ty),
-                span: binding.span,
-            }
-        }).collect();
+        let assoc_bindings = generic_args.bindings.iter()
+            .map(|binding| {
+                let kind = if let hir::TyKind::AssocTyExistential(ref bounds) = binding.ty.node {
+                    ConvertedBindingKind::Constraint(bounds.clone())
+                } else {
+                    ConvertedBindingKind::Equality(self.ast_ty_to_ty(&binding.ty))
+                };
+                ConvertedBinding {
+                    item_name: binding.ident,
+                    kind,
+                    span: binding.span,
+                }
+            })
+            .collect();
 
         debug!("create_substs_for_ast_path(generic_params={:?}, self_ty={:?}) -> {:?}",
                generic_params, self_ty, substs);
@@ -725,7 +743,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
     pub(super) fn instantiate_poly_trait_ref_inner(&self,
         trait_ref: &hir::TraitRef,
         self_ty: Ty<'tcx>,
-        poly_projections: &mut Vec<(ty::PolyProjectionPredicate<'tcx>, Span)>,
+        bounds: &mut Bounds<'tcx>,
         speculative: bool,
     ) -> (ty::PolyTraitRef<'tcx>, Option<Vec<Span>>)
     {
@@ -744,36 +762,40 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
         let poly_trait_ref = ty::Binder::bind(ty::TraitRef::new(trait_def_id, substs));
 
         let mut dup_bindings = FxHashMap::default();
-        poly_projections.extend(assoc_bindings.iter().filter_map(|binding| {
-            // specify type to assert that error was already reported in Err case:
-            let predicate: Result<_, ErrorReported> =
-                self.ast_type_binding_to_poly_projection_predicate(
-                    trait_ref.hir_ref_id, poly_trait_ref, binding, speculative, &mut dup_bindings);
-            // okay to ignore Err because of ErrorReported (see above)
-            Some((predicate.ok()?, binding.span))
-        }));
-
-        debug!("instantiate_poly_trait_ref({:?}, projections={:?}) -> {:?}",
-               trait_ref, poly_projections, poly_trait_ref);
+        for binding in &assoc_bindings {
+            // Specify type to assert that error was already reported in `Err` case.
+            let _ =
+                self.add_predicates_for_ast_type_binding(
+                    trait_ref.hir_ref_id,
+                    poly_trait_ref,
+                    binding,
+                    bounds,
+                    speculative,
+                    &mut dup_bindings
+                );
+            // Okay to ignore `Err` because of `ErrorReported` (see above).
+        }
+
+        debug!("instantiate_poly_trait_ref({:?}, bounds={:?}) -> {:?}",
+               trait_ref, bounds, poly_trait_ref);
         (poly_trait_ref, potential_assoc_types)
     }
 
     pub fn instantiate_poly_trait_ref(&self,
         poly_trait_ref: &hir::PolyTraitRef,
         self_ty: Ty<'tcx>,
-        poly_projections: &mut Vec<(ty::PolyProjectionPredicate<'tcx>, Span)>)
-        -> (ty::PolyTraitRef<'tcx>, Option<Vec<Span>>)
+        bounds: &mut Bounds<'tcx>
+    ) -> (ty::PolyTraitRef<'tcx>, Option<Vec<Span>>)
     {
-        self.instantiate_poly_trait_ref_inner(&poly_trait_ref.trait_ref, self_ty,
-                                              poly_projections, false)
+        self.instantiate_poly_trait_ref_inner(&poly_trait_ref.trait_ref, self_ty, bounds, false)
     }
 
     fn ast_path_to_mono_trait_ref(&self,
-                                  span: Span,
-                                  trait_def_id: DefId,
-                                  self_ty: Ty<'tcx>,
-                                  trait_segment: &hir::PathSegment)
-                                  -> ty::TraitRef<'tcx>
+        span: Span,
+        trait_def_id: DefId,
+        self_ty: Ty<'tcx>,
+        trait_segment: &hir::PathSegment
+    ) -> ty::TraitRef<'tcx>
     {
         let (substs, assoc_bindings, _) =
             self.create_substs_for_ast_trait_ref(span,
@@ -830,15 +852,120 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
         })
     }
 
-    fn ast_type_binding_to_poly_projection_predicate(
+    // Returns `true` if a bounds list includes `?Sized`.
+    pub fn is_unsized(&self, ast_bounds: &[hir::GenericBound], span: Span) -> bool {
+        let tcx = self.tcx();
+
+        // Try to find an unbound in bounds.
+        let mut unbound = None;
+        for ab in ast_bounds {
+            if let &hir::GenericBound::Trait(ref ptr, hir::TraitBoundModifier::Maybe) = ab {
+                if unbound.is_none() {
+                    unbound = Some(ptr.trait_ref.clone());
+                } else {
+                    span_err!(
+                        tcx.sess,
+                        span,
+                        E0203,
+                        "type parameter has more than one relaxed default \
+                        bound, only one is supported"
+                    );
+                }
+            }
+        }
+
+        let kind_id = tcx.lang_items().require(SizedTraitLangItem);
+        match unbound {
+            Some(ref tpb) => {
+                // FIXME(#8559) currently requires the unbound to be built-in.
+                if let Ok(kind_id) = kind_id {
+                    if tpb.path.res != Res::Def(DefKind::Trait, kind_id) {
+                        tcx.sess.span_warn(
+                            span,
+                            "default bound relaxed for a type parameter, but \
+                            this does nothing because the given bound is not \
+                            a default. Only `?Sized` is supported",
+                        );
+                    }
+                }
+            }
+            _ if kind_id.is_ok() => {
+                return false;
+            }
+            // No lang item for `Sized`, so we can't add it as a bound.
+            None => {}
+        }
+
+        true
+    }
+
+    pub fn add_bounds(&self,
+        param_ty: Ty<'tcx>,
+        ast_bounds: &[hir::GenericBound],
+        bounds: &mut Bounds<'tcx>,
+    ) {
+        let mut trait_bounds = Vec::new();
+        let mut region_bounds = Vec::new();
+
+        for ast_bound in ast_bounds {
+            match *ast_bound {
+                hir::GenericBound::Trait(ref b, hir::TraitBoundModifier::None) =>
+                    trait_bounds.push(b),
+                hir::GenericBound::Trait(_, hir::TraitBoundModifier::Maybe) => {}
+                hir::GenericBound::Outlives(ref l) =>
+                    region_bounds.push(l),
+            }
+        }
+
+        for bound in trait_bounds {
+            let (poly_trait_ref, _) = self.instantiate_poly_trait_ref(
+                bound,
+                param_ty,
+                bounds,
+            );
+            bounds.trait_bounds.push((poly_trait_ref, bound.span))
+        }
+
+        bounds.region_bounds.extend(region_bounds
+            .into_iter()
+            .map(|r| (self.ast_region_to_region(r, None), r.span))
+        );
+
+        bounds.trait_bounds.sort_by_key(|(t, _)| t.def_id());
+    }
+
+    /// Translates the AST's notion of ty param bounds (which are an enum consisting of a newtyped `Ty`
+    /// or a region) to ty's notion of ty param bounds, which can either be user-defined traits or the
+    /// built-in trait `Send`.
+    pub fn compute_bounds(&self,
+        param_ty: Ty<'tcx>,
+        ast_bounds: &[hir::GenericBound],
+        sized_by_default: SizedByDefault,
+        span: Span,
+    ) -> Bounds<'tcx> {
+        let mut bounds = Bounds::default();
+        self.add_bounds(param_ty, ast_bounds, &mut bounds);
+        bounds.implicitly_sized = if let SizedByDefault::Yes = sized_by_default {
+            if !self.is_unsized(ast_bounds, span) {
+                Some(span)
+            } else {
+                None
+            }
+        } else {
+            None
+        };
+        bounds
+    }
+
+    fn add_predicates_for_ast_type_binding(
         &self,
         hir_ref_id: hir::HirId,
         trait_ref: ty::PolyTraitRef<'tcx>,
         binding: &ConvertedBinding<'tcx>,
+        bounds: &mut Bounds<'tcx>,
         speculative: bool,
-        dup_bindings: &mut FxHashMap<DefId, Span>)
-        -> Result<ty::PolyProjectionPredicate<'tcx>, ErrorReported>
-    {
+        dup_bindings: &mut FxHashMap<DefId, Span>,
+    ) -> Result<(), ErrorReported> {
         let tcx = self.tcx();
 
         if !speculative {
@@ -865,28 +992,30 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
             //
             //     for<'a> <T as Iterator>::Item = &'a str // <-- 'a is bad
             //     for<'a> <T as FnMut<(&'a u32,)>>::Output = &'a str // <-- 'a is ok
-            let late_bound_in_trait_ref = tcx.collect_constrained_late_bound_regions(&trait_ref);
-            let late_bound_in_ty =
-                tcx.collect_referenced_late_bound_regions(&ty::Binder::bind(binding.ty));
-            debug!("late_bound_in_trait_ref = {:?}", late_bound_in_trait_ref);
-            debug!("late_bound_in_ty = {:?}", late_bound_in_ty);
-            for br in late_bound_in_ty.difference(&late_bound_in_trait_ref) {
-                let br_name = match *br {
-                    ty::BrNamed(_, name) => name,
-                    _ => {
-                        span_bug!(
-                            binding.span,
-                            "anonymous bound region {:?} in binding but not trait ref",
-                            br);
-                    }
-                };
-                struct_span_err!(tcx.sess,
+            if let ConvertedBindingKind::Equality(ty) = binding.kind {
+                let late_bound_in_trait_ref = tcx.collect_constrained_late_bound_regions(&trait_ref);
+                let late_bound_in_ty =
+                    tcx.collect_referenced_late_bound_regions(&ty::Binder::bind(ty));
+                debug!("late_bound_in_trait_ref = {:?}", late_bound_in_trait_ref);
+                debug!("late_bound_in_ty = {:?}", late_bound_in_ty);
+                for br in late_bound_in_ty.difference(&late_bound_in_trait_ref) {
+                    let br_name = match *br {
+                        ty::BrNamed(_, name) => name,
+                        _ => {
+                            span_bug!(
                                 binding.span,
-                                E0582,
-                                "binding for associated type `{}` references lifetime `{}`, \
-                                 which does not appear in the trait input types",
-                                binding.item_name, br_name)
-                    .emit();
+                                "anonymous bound region {:?} in binding but not trait ref",
+                                br);
+                        }
+                    };
+                    struct_span_err!(tcx.sess,
+                                    binding.span,
+                                    E0582,
+                                    "binding for associated type `{}` references lifetime `{}`, \
+                                     which does not appear in the trait input types",
+                                    binding.item_name, br_name)
+                        .emit();
+                }
             }
         }
 
@@ -931,16 +1060,28 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
                 .or_insert(binding.span);
         }
 
-        Ok(candidate.map_bound(|trait_ref| {
-            ty::ProjectionPredicate {
-                projection_ty: ty::ProjectionTy::from_ref_and_name(
-                    tcx,
-                    trait_ref,
-                    binding.item_name,
-                ),
-                ty: binding.ty,
+        match binding.kind {
+            ConvertedBindingKind::Equality(ref ty) => {
+                bounds.projection_bounds.push((candidate.map_bound(|trait_ref| {
+                    ty::ProjectionPredicate {
+                        projection_ty: ty::ProjectionTy::from_ref_and_name(
+                            tcx,
+                            trait_ref,
+                            binding.item_name,
+                        ),
+                        ty,
+                    }
+                }), binding.span));
             }
-        }))
+            ConvertedBindingKind::Constraint(ref ast_bounds) => {
+                self.add_bounds(
+                    trait_ref.self_ty(),
+                    ast_bounds,
+                    bounds,
+                );
+            }
+        }
+        Ok(())
     }
 
     fn ast_path_to_ty(&self,
@@ -974,7 +1115,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
     {
         let tcx = self.tcx();
 
-        let mut projection_bounds = Vec::new();
+        let mut bounds = Bounds::default();
         let mut potential_assoc_types = Vec::new();
         let dummy_self = self.tcx().types.trait_object_dummy_self;
         // FIXME: we want to avoid collecting into a `Vec` here, but simply cloning the iterator is
@@ -986,7 +1127,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
                 let (trait_ref, cur_potential_assoc_types) = self.instantiate_poly_trait_ref(
                     trait_bound,
                     dummy_self,
-                    &mut projection_bounds
+                    &mut bounds,
                 );
                 potential_assoc_types.extend(cur_potential_assoc_types.into_iter().flatten());
                 (trait_ref, trait_bound.span)
@@ -1074,14 +1215,14 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
                     // which is uglier but works. See the discussion in #56288 for alternatives.
                     if !references_self {
                         // Include projections defined on supertraits.
-                        projection_bounds.push((pred, DUMMY_SP))
+                        bounds.projection_bounds.push((pred, DUMMY_SP))
                     }
                 }
                 _ => ()
             }
         }
 
-        for (projection_bound, _) in &projection_bounds {
+        for (projection_bound, _) in &bounds.projection_bounds {
             associated_types.remove(&projection_bound.projection_def_id());
         }
 
@@ -1161,7 +1302,7 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
         let existential_trait_refs = regular_traits.iter().map(|i| {
             i.trait_ref().map_bound(|trait_ref| self.trait_ref_to_existential(trait_ref))
         });
-        let existential_projections = projection_bounds.iter().map(|(bound, _)| {
+        let existential_projections = bounds.projection_bounds.iter().map(|(bound, _)| {
             bound.map_bound(|b| {
                 let trait_ref = self.trait_ref_to_existential(b.projection_ty.trait_ref(tcx));
                 ty::ExistentialProjection {
@@ -1900,6 +2041,10 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
                 let region = self.ast_region_to_region(&lt, None);
                 tcx.type_of(va_list_did).subst(tcx, &[region.into()])
             }
+            hir::TyKind::AssocTyExistential(..) => {
+                // Type is never actually used.
+                tcx.types.err
+            }
             hir::TyKind::Err => {
                 tcx.types.err
             }
@@ -2121,12 +2266,12 @@ impl<'o, 'gcx: 'tcx, 'tcx> dyn AstConv<'gcx, 'tcx> + 'o {
 
 // A helper struct for conveniently grouping a set of bounds which we pass to
 // and return from functions in multiple places.
-#[derive(PartialEq, Eq, Clone, Debug)]
+#[derive(Default, PartialEq, Eq, Clone, Debug)]
 pub struct Bounds<'tcx> {
     pub region_bounds: Vec<(ty::Region<'tcx>, Span)>,
-    pub implicitly_sized: Option<Span>,
     pub trait_bounds: Vec<(ty::PolyTraitRef<'tcx>, Span)>,
     pub projection_bounds: Vec<(ty::PolyProjectionPredicate<'tcx>, Span)>,
+    pub implicitly_sized: Option<Span>,
 }
 
 impl<'a, 'gcx, 'tcx> Bounds<'tcx> {
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index 21d7e483e9d..c3b6fb21e38 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -991,8 +991,8 @@ impl<'a, 'gcx, 'tcx> RegionCtxt<'a, 'gcx, 'tcx> {
         }
     }
 
-    /// Guarantees that any lifetimes which appear in the type of the node `id` (after applying
-    /// adjustments) are valid for at least `minimum_lifetime`
+    /// Guarantees that any lifetimes that appear in the type of the node `id` (after applying
+    /// adjustments) are valid for at least `minimum_lifetime`.
     fn type_of_node_must_outlive(
         &mut self,
         origin: infer::SubregionOrigin<'tcx>,
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index ee7961197d3..92d0e37cb9b 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -14,11 +14,10 @@
 //! At present, however, we do run collection across all items in the
 //! crate as a kind of pass. This should eventually be factored away.
 
-use crate::astconv::{AstConv, Bounds};
+use crate::astconv::{AstConv, Bounds, SizedByDefault};
 use crate::constrained_generic_params as cgp;
 use crate::check::intrinsic::intrisic_operation_unsafety;
 use crate::lint;
-use crate::middle::lang_items::SizedTraitLangItem;
 use crate::middle::resolve_lifetime as rl;
 use crate::middle::weak_lang_items;
 use rustc::mir::mono::Linkage;
@@ -704,7 +703,7 @@ fn super_predicates_of<'a, 'tcx>(
 
     // Convert the bounds that follow the colon, e.g., `Bar + Zed` in `trait Foo: Bar + Zed`.
     let self_param_ty = tcx.mk_self_type();
-    let superbounds1 = compute_bounds(&icx, self_param_ty, bounds, SizedByDefault::No, item.span);
+    let superbounds1 = AstConv::compute_bounds(&icx, self_param_ty, bounds, SizedByDefault::No, item.span);
 
     let superbounds1 = superbounds1.predicates(tcx, self_param_ty);
 
@@ -1650,9 +1649,11 @@ fn find_existential_constraints<'a, 'tcx>(
         }
     }
 
-    let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
-    let scope_id = tcx.hir().get_defining_scope(hir_id)
-                            .expect("could not get defining scope");
+    let node_id = tcx.hir().as_local_node_id(def_id).unwrap();
+    let scope_node_id = tcx.hir()
+        .get_defining_scope(node_id)
+        .expect("could not get defining scope");
+    let scope_id = tcx.hir().node_to_hir_id(scope_node_id);
     let mut locator = ConstraintLocator {
         def_id,
         tcx,
@@ -1661,7 +1662,7 @@ fn find_existential_constraints<'a, 'tcx>(
 
     debug!("find_existential_constraints: scope_id={:?}", scope_id);
 
-    if scope_id == ast::CRATE_HIR_ID {
+    if scope_id == hir::CRATE_HIR_ID {
         intravisit::walk_crate(&mut locator, tcx.hir().krate());
     } else {
         debug!("find_existential_constraints: scope={:?}", tcx.hir().get_by_hir_id(scope_id));
@@ -1788,57 +1789,6 @@ fn impl_polarity<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> hir::I
     }
 }
 
-// Is it marked with ?Sized
-fn is_unsized<'gcx: 'tcx, 'tcx>(
-    astconv: &dyn AstConv<'gcx, 'tcx>,
-    ast_bounds: &[hir::GenericBound],
-    span: Span,
-) -> bool {
-    let tcx = astconv.tcx();
-
-    // Try to find an unbound in bounds.
-    let mut unbound = None;
-    for ab in ast_bounds {
-        if let &hir::GenericBound::Trait(ref ptr, hir::TraitBoundModifier::Maybe) = ab {
-            if unbound.is_none() {
-                unbound = Some(ptr.trait_ref.clone());
-            } else {
-                span_err!(
-                    tcx.sess,
-                    span,
-                    E0203,
-                    "type parameter has more than one relaxed default \
-                     bound, only one is supported"
-                );
-            }
-        }
-    }
-
-    let kind_id = tcx.lang_items().require(SizedTraitLangItem);
-    match unbound {
-        Some(ref tpb) => {
-            // FIXME(#8559) currently requires the unbound to be built-in.
-            if let Ok(kind_id) = kind_id {
-                if tpb.path.res != Res::Def(DefKind::Trait, kind_id) {
-                    tcx.sess.span_warn(
-                        span,
-                        "default bound relaxed for a type parameter, but \
-                         this does nothing because the given bound is not \
-                         a default. Only `?Sized` is supported",
-                    );
-                }
-            }
-        }
-        _ if kind_id.is_ok() => {
-            return false;
-        }
-        // No lang item for Sized, so we can't add it as a bound.
-        None => {}
-    }
-
-    true
-}
-
 /// Returns the early-bound lifetimes declared in this generics
 /// listing. For anything other than fns/methods, this is just all
 /// the lifetimes that are declared. For fns or methods, we have to
@@ -1984,7 +1934,7 @@ fn explicit_predicates_of<'a, 'tcx>(
                 let opaque_ty = tcx.mk_opaque(def_id, substs);
 
                 // Collect the bounds, i.e., the `A + B + 'c` in `impl A + B + 'c`.
-                let bounds = compute_bounds(
+                let bounds = AstConv::compute_bounds(
                     &icx,
                     opaque_ty,
                     bounds,
@@ -2030,7 +1980,7 @@ fn explicit_predicates_of<'a, 'tcx>(
                     let opaque_ty = tcx.mk_opaque(def_id, substs);
 
                     // Collect the bounds, i.e., the `A + B + 'c` in `impl A + B + 'c`.
-                    let bounds = compute_bounds(
+                    let bounds = AstConv::compute_bounds(
                         &icx,
                         opaque_ty,
                         bounds,
@@ -2124,7 +2074,7 @@ fn explicit_predicates_of<'a, 'tcx>(
             index += 1;
 
             let sized = SizedByDefault::Yes;
-            let bounds = compute_bounds(&icx, param_ty, &param.bounds, sized, param.span);
+            let bounds = AstConv::compute_bounds(&icx, param_ty, &param.bounds, sized, param.span);
             predicates.extend(bounds.predicates(tcx, param_ty));
         }
     }
@@ -2159,19 +2109,17 @@ fn explicit_predicates_of<'a, 'tcx>(
                 for bound in bound_pred.bounds.iter() {
                     match bound {
                         &hir::GenericBound::Trait(ref poly_trait_ref, _) => {
-                            let mut projections = Vec::new();
+                            let mut bounds = Bounds::default();
 
                             let (trait_ref, _) = AstConv::instantiate_poly_trait_ref(
                                 &icx,
                                 poly_trait_ref,
                                 ty,
-                                &mut projections,
+                                &mut bounds,
                             );
 
-                            predicates.extend(
-                                iter::once((trait_ref.to_predicate(), poly_trait_ref.span)).chain(
-                                    projections.iter().map(|&(p, span)| (p.to_predicate(), span)
-                            )));
+                            predicates.push((trait_ref.to_predicate(), poly_trait_ref.span));
+                            predicates.extend(bounds.predicates(tcx, ty));
                         }
 
                         &hir::GenericBound::Outlives(ref lifetime) => {
@@ -2210,14 +2158,14 @@ fn explicit_predicates_of<'a, 'tcx>(
             let trait_item = tcx.hir().trait_item(trait_item_ref.id);
             let bounds = match trait_item.node {
                 hir::TraitItemKind::Type(ref bounds, _) => bounds,
-                _ => return vec![].into_iter()
+                _ => return Vec::new().into_iter()
             };
 
             let assoc_ty =
                 tcx.mk_projection(tcx.hir().local_def_id_from_hir_id(trait_item.hir_id),
                     self_trait_ref.substs);
 
-            let bounds = compute_bounds(
+            let bounds = AstConv::compute_bounds(
                 &ItemCtxt::new(tcx, def_id),
                 assoc_ty,
                 bounds,
@@ -2259,68 +2207,6 @@ fn explicit_predicates_of<'a, 'tcx>(
     result
 }
 
-pub enum SizedByDefault {
-    Yes,
-    No,
-}
-
-/// Translate the AST's notion of ty param bounds (which are an enum consisting of a newtyped `Ty`
-/// or a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
-/// built-in trait `Send`.
-pub fn compute_bounds<'gcx: 'tcx, 'tcx>(
-    astconv: &dyn AstConv<'gcx, 'tcx>,
-    param_ty: Ty<'tcx>,
-    ast_bounds: &[hir::GenericBound],
-    sized_by_default: SizedByDefault,
-    span: Span,
-) -> Bounds<'tcx> {
-    let mut region_bounds = Vec::new();
-    let mut trait_bounds = Vec::new();
-
-    for ast_bound in ast_bounds {
-        match *ast_bound {
-            hir::GenericBound::Trait(ref b, hir::TraitBoundModifier::None) => trait_bounds.push(b),
-            hir::GenericBound::Trait(_, hir::TraitBoundModifier::Maybe) => {}
-            hir::GenericBound::Outlives(ref l) => region_bounds.push(l),
-        }
-    }
-
-    let mut projection_bounds = Vec::new();
-
-    let mut trait_bounds: Vec<_> = trait_bounds.iter().map(|&bound| {
-        let (poly_trait_ref, _) = astconv.instantiate_poly_trait_ref(
-            bound,
-            param_ty,
-            &mut projection_bounds,
-        );
-        (poly_trait_ref, bound.span)
-    }).collect();
-
-    let region_bounds = region_bounds
-        .into_iter()
-        .map(|r| (astconv.ast_region_to_region(r, None), r.span))
-        .collect();
-
-    trait_bounds.sort_by_key(|(t, _)| t.def_id());
-
-    let implicitly_sized = if let SizedByDefault::Yes = sized_by_default {
-        if !is_unsized(astconv, ast_bounds, span) {
-            Some(span)
-        } else {
-            None
-        }
-    } else {
-        None
-    };
-
-    Bounds {
-        region_bounds,
-        implicitly_sized,
-        trait_bounds,
-        projection_bounds,
-    }
-}
-
 /// Converts a specific `GenericBound` from the AST into a set of
 /// predicates that apply to the self type. A vector is returned
 /// because this can be anywhere from zero predicates (`T: ?Sized` adds no
@@ -2333,13 +2219,11 @@ fn predicates_from_bound<'tcx>(
 ) -> Vec<(ty::Predicate<'tcx>, Span)> {
     match *bound {
         hir::GenericBound::Trait(ref tr, hir::TraitBoundModifier::None) => {
-            let mut projections = Vec::new();
-            let (pred, _) = astconv.instantiate_poly_trait_ref(tr, param_ty, &mut projections);
-            iter::once((pred.to_predicate(), tr.span)).chain(
-                projections
-                    .into_iter()
-                    .map(|(p, span)| (p.to_predicate(), span))
-            ).collect()
+            let mut bounds = Bounds::default();
+            let (pred, _) = astconv.instantiate_poly_trait_ref(tr, param_ty, &mut bounds);
+            iter::once((pred.to_predicate(), tr.span))
+                .chain(bounds.predicates(astconv.tcx(), param_ty))
+                .collect()
         }
         hir::GenericBound::Outlives(ref lifetime) => {
             let region = astconv.ast_region_to_region(lifetime, None);
@@ -2363,8 +2247,8 @@ fn compute_sig_of_foreign_fn_decl<'a, 'tcx>(
     };
     let fty = AstConv::ty_of_fn(&ItemCtxt::new(tcx, def_id), unsafety, abi, decl);
 
-    // feature gate SIMD types in FFI, since I (huonw) am not sure the
-    // ABIs are handled at all correctly.
+    // Feature gate SIMD types in FFI, since I am not sure that the
+    // ABIs are handled at all correctly. -huonw
     if abi != abi::Abi::RustIntrinsic
         && abi != abi::Abi::PlatformIntrinsic
         && !tcx.features().simd_ffi
@@ -2439,7 +2323,7 @@ fn from_target_feature(
     };
     let rust_features = tcx.features();
     for item in list {
-        // Only `enable = ...` is accepted in the meta item list
+        // Only `enable = ...` is accepted in the meta-item list.
         if !item.check_name(sym::enable) {
             bad_item(item.span());
             continue;
@@ -2454,9 +2338,9 @@ fn from_target_feature(
             }
         };
 
-        // We allow comma separation to enable multiple features
+        // We allow comma separation to enable multiple features.
         target_features.extend(value.as_str().split(',').filter_map(|feature| {
-            // Only allow whitelisted features per platform
+            // Only allow whitelisted features per platform.
             let feature_gate = match whitelist.get(feature) {
                 Some(g) => g,
                 None => {
@@ -2480,7 +2364,7 @@ fn from_target_feature(
                 }
             };
 
-            // Only allow features whose feature gates have been enabled
+            // Only allow features whose feature gates have been enabled.
             let allowed = match feature_gate.as_ref().map(|s| *s) {
                 Some(sym::arm_target_feature) => rust_features.arm_target_feature,
                 Some(sym::aarch64_target_feature) => rust_features.aarch64_target_feature,
diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs
index 024d73ff65b..30993b86a38 100644
--- a/src/librustc_typeck/lib.rs
+++ b/src/librustc_typeck/lib.rs
@@ -114,6 +114,7 @@ use util::common::time;
 
 use std::iter;
 
+use astconv::{AstConv, Bounds};
 pub use collect::checked_type_of;
 
 pub struct TypeAndSubsts<'tcx> {
@@ -390,19 +391,19 @@ pub fn hir_ty_to_ty<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, hir_ty: &hir::Ty) ->
 }
 
 pub fn hir_trait_to_predicates<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, hir_trait: &hir::TraitRef)
-        -> (ty::PolyTraitRef<'tcx>, Vec<(ty::PolyProjectionPredicate<'tcx>, Span)>) {
+        -> (ty::PolyTraitRef<'tcx>, Bounds<'tcx>) {
     // In case there are any projections, etc., find the "environment"
     // def-ID that will be used to determine the traits/predicates in
     // scope.  This is derived from the enclosing item-like thing.
     let env_hir_id = tcx.hir().get_parent_item(hir_trait.hir_ref_id);
     let env_def_id = tcx.hir().local_def_id_from_hir_id(env_hir_id);
     let item_cx = self::collect::ItemCtxt::new(tcx, env_def_id);
-    let mut projections = Vec::new();
-    let (principal, _) = astconv::AstConv::instantiate_poly_trait_ref_inner(
-        &item_cx, hir_trait, tcx.types.err, &mut projections, true
+    let mut bounds = Bounds::default();
+    let (principal, _) = AstConv::instantiate_poly_trait_ref_inner(
+        &item_cx, hir_trait, tcx.types.err, &mut bounds, true
     );
 
-    (principal, projections)
+    (principal, bounds)
 }
 
 __build_diagnostic_array! { librustc_typeck, DIAGNOSTICS }
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index f19e5180939..161e426604e 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -2445,7 +2445,7 @@ pub struct PolyTrait {
 
 /// A representation of a type suitable for hyperlinking purposes. Ideally, one can get the original
 /// type out of the AST/`TyCtxt` given one of these, if more information is needed. Most
-/// importantly, it does not preserve mutability or boxes.
+/// importanntly, it does not preserve mutability or boxes.
 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Debug, Hash)]
 pub enum Type {
     /// Structs/enums/traits (most that would be an `hir::TyKind::Path`).
@@ -2939,6 +2939,9 @@ impl Clean<Type> for hir::Ty {
             TyKind::Infer | TyKind::Err => Infer,
             TyKind::Typeof(..) => panic!("Unimplemented type {:?}", self.node),
             TyKind::CVarArgs(_) => CVarArgs,
+            TyKind::AssocTyExistential(ref bounds) => {
+                ImplTrait(bounds.into_iter().map(|b| b.clean(cx)).collect())
+            }
         }
     }
 }