Implemented for function bounds, type bounds, and named existential types.

17 files changed, 367 insertions, 196 deletions

diff --git a/src/librustc/hir/lowering.rs b/src/librustc/hir/lowering.rs
index af8c9c38de5..5a0e9d53b08 100644
--- a/src/librustc/hir/lowering.rs
+++ b/src/librustc/hir/lowering.rs
@@ -69,7 +69,7 @@ use syntax::symbol::{kw, sym, Symbol};
 use syntax::tokenstream::{TokenStream, TokenTree};
 use syntax::parse::token::Token;
 use syntax::visit::{self, Visitor};
-use syntax_pos::{edition, Span};
+use syntax_pos::{DUMMY_SP, edition, Span};
 
 const HIR_ID_COUNTER_LOCKED: u32 = 0xFFFFFFFF;
 
@@ -191,9 +191,9 @@ enum ImplTraitContext<'a> {
     /// equivalent to a fresh existential parameter like `existential type T; fn foo() -> T`.
     ///
     /// We optionally store a `DefId` for the parent item here so we can look up necessary
-    /// information later. It is `None` when no information about the context should be stored,
-    /// e.g., for consts and statics.
-    Existential(Option<DefId>),
+    /// information later. It is `None` when no information about the context should be stored
+    /// (e.g., for consts and statics).
+    Existential(Option<DefId> /* fn def-ID */),
 
     /// `impl Trait` is not accepted in this position.
     Disallowed(ImplTraitPosition),
@@ -216,7 +216,7 @@ impl<'a> ImplTraitContext<'a> {
         use self::ImplTraitContext::*;
         match self {
             Universal(params) => Universal(params),
-            Existential(did) => Existential(*did),
+            Existential(fn_def_id) => Existential(*fn_def_id),
             Disallowed(pos) => Disallowed(*pos),
         }
     }
@@ -1342,13 +1342,36 @@ impl<'a> LoweringContext<'a> {
         }
     }
 
-    fn lower_ty_binding(&mut self, b: &TypeBinding,
-                        itctx: ImplTraitContext<'_>) -> hir::TypeBinding {
+    fn lower_assoc_ty_constraint(&mut self,
+                                 c: &AssocTyConstraint,
+                                 itctx: ImplTraitContext<'_>)
+                                 -> hir::TypeBinding {
+        let ty = match c.kind {
+            AssocTyConstraintKind::Equality { ref ty } => self.lower_ty(ty, itctx),
+            AssocTyConstraintKind::Bound { ref bounds } => {
+                // Desugar `AssocTy: Bounds` into `AssocTy = impl Bounds`.
+                let impl_ty_node_id = self.sess.next_node_id();
+                let parent_def_index = self.current_hir_id_owner.last().unwrap().0;
+                self.resolver.definitions().create_def_with_parent(
+                    parent_def_index,
+                    impl_ty_node_id,
+                    DefPathData::Misc,
+                    DefIndexAddressSpace::High,
+                    Mark::root(),
+                    DUMMY_SP);
+                self.lower_ty(&Ty {
+                    id: self.sess.next_node_id(),
+                    node: TyKind::ImplTrait(impl_ty_node_id, bounds.clone()),
+                    span: DUMMY_SP,
+                }, itctx)
+            }
+        };
+
         hir::TypeBinding {
-            hir_id: self.lower_node_id(b.id),
-            ident: b.ident,
-            ty: self.lower_ty(&b.ty, itctx),
-            span: b.span,
+            hir_id: self.lower_node_id(c.id),
+            ident: c.ident,
+            ty
+            span: c.span,
         }
     }
 
@@ -1604,7 +1627,7 @@ impl<'a> LoweringContext<'a> {
                 origin: hir::ExistTyOrigin::ReturnImplTrait,
             };
 
-            trace!("exist ty from impl trait def index: {:#?}", exist_ty_def_index);
+            trace!("exist ty from impl trait def-index: {:#?}", exist_ty_def_index);
             let exist_ty_id = lctx.generate_existential_type(
                 exist_ty_node_id,
                 exist_ty_item,
@@ -1617,7 +1640,7 @@ impl<'a> LoweringContext<'a> {
         })
     }
 
-    /// Registers a new existential type with the proper NodeIds and
+    /// Registers a new existential type with the proper `NodeId`ss and
     /// returns the lowered node ID for the existential type.
     fn generate_existential_type(
         &mut self,
@@ -2195,7 +2218,7 @@ impl<'a> LoweringContext<'a> {
         param_mode: ParamMode,
         mut itctx: ImplTraitContext<'_>,
     ) -> (hir::GenericArgs, bool) {
-        let &AngleBracketedArgs { ref args, ref bindings, .. } = data;
+        let &AngleBracketedArgs { ref args, ref constraints, .. } = data;
         let has_types = args.iter().any(|arg| match arg {
             ast::GenericArg::Type(_) => true,
             _ => false,
@@ -2203,7 +2226,8 @@ impl<'a> LoweringContext<'a> {
         (
             hir::GenericArgs {
                 args: args.iter().map(|a| self.lower_generic_arg(a, itctx.reborrow())).collect(),
-                bindings: bindings.iter().map(|b| self.lower_ty_binding(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
@@ -3236,12 +3260,14 @@ impl<'a> LoweringContext<'a> {
                 self.lower_ty(t, ImplTraitContext::disallowed()),
                 self.lower_generics(generics, ImplTraitContext::disallowed()),
             ),
-            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::disallowed()),
-                impl_trait_fn: None,
-                origin: hir::ExistTyOrigin::ExistentialType,
-            }),
+            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)),
+                    impl_trait_fn: None,
+                    origin: hir::ExistTyOrigin::ExistentialType,
+                },
+            ),
             ItemKind::Enum(ref enum_definition, ref generics) => hir::ItemKind::Enum(
                 hir::EnumDef {
                     variants: enum_definition
diff --git a/src/librustc/hir/map/definitions.rs b/src/librustc/hir/map/definitions.rs
index b85f6f6ce84..b01eed8f660 100644
--- a/src/librustc/hir/map/definitions.rs
+++ b/src/librustc/hir/map/definitions.rs
@@ -397,6 +397,11 @@ impl Definitions {
         self.node_to_hir_id[node_id]
     }
 
+    #[inline]
+    pub fn def_index_to_node_id(&self, def_index: DefIndex) -> ast::NodeId {
+        self.as_local_node_id(DefId::local(def_index)).unwrap()
+    }
+
     /// Retrieves the span of the given `DefId` if `DefId` is in the local crate, the span exists
     /// and it's not `DUMMY_SP`.
     #[inline]
diff --git a/src/librustc/hir/map/mod.rs b/src/librustc/hir/map/mod.rs
index 18c596f164d..cdbeb8a4a54 100644
--- a/src/librustc/hir/map/mod.rs
+++ b/src/librustc/hir/map/mod.rs
@@ -288,7 +288,7 @@ impl<'hir> Map<'hir> {
 
     #[inline]
     pub fn def_index_to_node_id(&self, def_index: DefIndex) -> NodeId {
-        self.definitions.as_local_node_id(DefId::local(def_index)).unwrap()
+        self.definitions.def_index_to_node_id(def_index)
     }
 
     #[inline]
@@ -649,16 +649,16 @@ impl<'hir> Map<'hir> {
         result
     }
 
-    /// Similar to `get_parent`; returns the parent node-id, or own `id` if there is
-    /// no parent. Note that the parent may be `CRATE_NODE_ID`, which is not itself
-    /// present in the map -- so passing the return value of get_parent_node to
-    /// get may actually panic.
-    /// This function returns the immediate parent in the AST, whereas get_parent
+    /// Similar to `get_parent`; returns the parent node-ID, or just `hir_id` if there
+    /// is no parent. Note that the parent may be `CRATE_NODE_ID`, which is not itself
+    /// present in the map, so passing the return value of `get_parent_node` to
+    /// `get` may in fact panic.
+    /// This function returns the immediate parent in the AST, whereas `get_parent`
     /// returns the enclosing item. Note that this might not be the actual parent
-    /// node in the AST - some kinds of nodes are not in the map and these will
-    /// never appear as the parent_node. So you can always walk the `parent_nodes`
-    /// from a node to the root of the ast (unless you get the same ID back here
-    /// that can happen if the ID is not in the map itself or is just weird).
+    /// node in the AST -- some kinds of nodes are not in the map and these will
+    /// never appear as the parent node. Thus, you can always walk the parent nodes
+    /// from a node to the root of the AST (unless you get back the same ID here,
+    /// which can happen if the ID is not in the map itself or is just weird).
     pub fn get_parent_node(&self, id: NodeId) -> NodeId {
         let hir_id = self.node_to_hir_id(id);
         let parent_hir_id = self.get_parent_node_by_hir_id(hir_id);
@@ -841,21 +841,66 @@ impl<'hir> Map<'hir> {
         }
     }
 
-    /// Returns the nearest enclosing scope. A scope is an item or block.
-    /// FIXME: it is not clear to me that all items qualify as scopes -- statics
-    /// and associated types probably shouldn't, for example. Behavior in this
-    /// regard should be expected to be highly unstable.
-    pub fn get_enclosing_scope(&self, hir_id: HirId) -> Option<HirId> {
+    /// Returns the nearest enclosing scope. A scope is roughly an item or block.
+    pub fn get_enclosing_scope(&self, id: HirId) -> Option<HirId> {
         self.walk_parent_nodes(hir_id, |node| match *node {
-            Node::Item(_) |
-            Node::ForeignItem(_) |
-            Node::TraitItem(_) |
-            Node::ImplItem(_) |
+            Node::Item(i) => {
+                match i.node {
+                    ItemKind::Fn(..)
+                    | ItemKind::Mod(..)
+                    | ItemKind::Enum(..)
+                    | ItemKind::Struct(..)
+                    | ItemKind::Union(..)
+                    | ItemKind::Trait(..)
+                    | ItemKind::Impl(..) => true,
+                    _ => false,
+                }
+            },
+            Node::ForeignItem(fi) => {
+                match fi.node {
+                    ForeignItemKind::Fn(..) => true,
+                    _ => false,
+                }
+            },
+            Node::TraitItem(ti) => {
+                match ti.node {
+                    TraitItemKind::Method(..) => true,
+                    _ => false,
+                }
+            },
+            Node::ImplItem(ii) => {
+                match ii.node {
+                    ImplItemKind::Method(..) => true,
+                    _ => false,
+                }
+            },
             Node::Block(_) => true,
             _ => false,
         }, |_| false).ok()
     }
 
+    /// Returns the defining scope for an existential type definition.
+    pub fn get_defining_scope(&self, id: NodeId) -> Option<NodeId> {
+        let mut scope = id;
+        loop {
+            scope = self.get_enclosing_scope(scope)?;
+            if scope == CRATE_NODE_ID {
+                return Some(CRATE_NODE_ID);
+            }
+            match self.get(scope) {
+                Node::Item(i) => {
+                    match i.node {
+                        ItemKind::Existential(ExistTy { impl_trait_fn: None, .. }) => {}
+                        _ => break,
+                    }
+                }
+                Node::Block(_) => {}
+                _ => break,
+            }
+        }
+        Some(scope)
+    }
+
     pub fn get_parent_did(&self, id: NodeId) -> DefId {
         let hir_id = self.node_to_hir_id(id);
         self.get_parent_did_by_hir_id(hir_id)
diff --git a/src/librustc/infer/opaque_types/mod.rs b/src/librustc/infer/opaque_types/mod.rs
index 1423b855745..ef216110c9e 100644
--- a/src/librustc/infer/opaque_types/mod.rs
+++ b/src/librustc/infer/opaque_types/mod.rs
@@ -786,13 +786,13 @@ impl<'a, 'gcx, 'tcx> Instantiator<'a, 'gcx, 'tcx> {
                             match tcx.hir().find_by_hir_id(opaque_hir_id)
                         {
                             Some(Node::Item(item)) => match item.node {
-                                // impl trait
+                                // Anonymous `impl Trait`
                                 hir::ItemKind::Existential(hir::ExistTy {
                                     impl_trait_fn: Some(parent),
                                     origin,
                                     ..
                                 }) => (parent == self.parent_def_id, origin),
-                                // named existential types
+                                // Named `existential type`
                                 hir::ItemKind::Existential(hir::ExistTy {
                                     impl_trait_fn: None,
                                     origin,
@@ -868,7 +868,7 @@ impl<'a, 'gcx, 'tcx> Instantiator<'a, 'gcx, 'tcx> {
 
         let predicates_of = tcx.predicates_of(def_id);
         debug!(
-            "instantiate_opaque_types: predicates: {:#?}",
+            "instantiate_opaque_types: predicates={:#?}",
             predicates_of,
         );
         let bounds = predicates_of.instantiate(tcx, substs);
@@ -884,11 +884,11 @@ impl<'a, 'gcx, 'tcx> Instantiator<'a, 'gcx, 'tcx> {
         // (e.g., `existential type Foo<T: Bound>: Bar;` needs to be
         // defined by a function like `fn foo<T: Bound>() -> Foo<T>`).
         debug!(
-            "instantiate_opaque_types: param_env: {:#?}",
+            "instantiate_opaque_types: param_env={:#?}",
             self.param_env,
         );
         debug!(
-            "instantiate_opaque_types: generics: {:#?}",
+            "instantiate_opaque_types: generics={:#?}",
             tcx.generics_of(def_id),
         );
 
@@ -922,8 +922,9 @@ impl<'a, 'gcx, 'tcx> Instantiator<'a, 'gcx, 'tcx> {
     }
 }
 
-/// Returns `true` if `opaque_node_id` is a sibling or a child of a sibling of `def_id`.
+/// Returns `true` if `opaque_hir_id` is a sibling or a child of a sibling of `def_id`.
 ///
+/// Example:
 /// ```rust
 /// pub mod foo {
 ///     pub mod bar {
@@ -936,24 +937,28 @@ impl<'a, 'gcx, 'tcx> Instantiator<'a, 'gcx, 'tcx> {
 /// }
 /// ```
 ///
-/// Here, `def_id` is the `DefId` of the existential type `Baz` and `opaque_node_id` is the
-/// `NodeId` of the reference to `Baz` (i.e., the return type of both `f1` and `f2`).
-/// We return `true` if the reference is within the same module as the existential type
-/// (i.e., `true` for `f1`, `false` for `f2`).
+/// Here, `def_id` is the `DefId` of the defining use of the existential type (e.g., `f1` or `f2`),
+/// and `opaque_hir_id` is the `HirId` of the definition of the existential type `Baz`.
+/// For the above example, this function returns `true` for `f1` and `false` for `f2`.
 pub fn may_define_existential_type(
     tcx: TyCtxt<'_, '_, '_>,
     def_id: DefId,
     opaque_hir_id: hir::HirId,
 ) -> bool {
     let mut hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
-    // Named existential types can be defined by any siblings or
-    // children of siblings.
-    let mod_id = tcx.hir().get_parent_item(opaque_hir_id);
-    // We walk up the node tree until we hit the root or the parent
-    // of the opaque type.
-    while hir_id != mod_id && node_id != ast::CRATE_HIR_ID {
+    trace!(
+        "may_define_existential_type(def={:?}, opaque_node={:?})",
+        tcx.hir().get(hir_id),
+        tcx.hir().get(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");
+    // 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 {
         hir_id = tcx.hir().get_parent_item(hir_id);
     }
-    // Syntactically we are allowed to define the concrete type.
-    hir_id == mod_id
+    // Syntactically, we are allowed to define the concrete type if:
+    hir_id == scope_id
 }
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index fc9756d52f5..7810d65e88c 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -1848,8 +1848,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             .iter()
             .filter_map(|o| o.to_opt_poly_trait_ref());
 
-        // micro-optimization: filter out predicates relating to different
-        // traits.
+        // Micro-optimization: filter out predicates relating to different traits.
         let matching_bounds =
             all_bounds.filter(|p| p.def_id() == stack.obligation.predicate.def_id());
 
diff --git a/src/librustc_interface/util.rs b/src/librustc_interface/util.rs
index 4ff996d1f57..f49f2110f23 100644
--- a/src/librustc_interface/util.rs
+++ b/src/librustc_interface/util.rs
@@ -716,8 +716,22 @@ impl<'a> ReplaceBodyWithLoop<'a> {
                                     ast::GenericArg::Type(ty) => Some(ty),
                                     _ => None,
                                 });
+                                let any_assoc_ty_bounds = data.constraints.iter().any(|c| {
+                                    if let ast::AssocTyConstraintKind::Bound { .. } = c.kind {
+                                        true
+                                    } else {
+                                        false
+                                    }
+                                });
+                                any_assoc_ty_bounds ||
                                 any_involves_impl_trait(types.into_iter()) ||
-                                any_involves_impl_trait(data.bindings.iter().map(|b| &b.ty))
+                                any_involves_impl_trait(data.constraints.iter().filter_map(|c| {
+                                    if let ast::AssocTyConstraintKind::Equality { ref ty } = c.kind {
+                                        Some(ty)
+                                    } else {
+                                        None
+                                    }
+                                }))
                             },
                             Some(&ast::GenericArgs::Parenthesized(ref data)) => {
                                 any_involves_impl_trait(data.inputs.iter()) ||
diff --git a/src/librustc_passes/ast_validation.rs b/src/librustc_passes/ast_validation.rs
index 6a17a84517e..2d602a7f1b4 100644
--- a/src/librustc_passes/ast_validation.rs
+++ b/src/librustc_passes/ast_validation.rs
@@ -93,14 +93,16 @@ impl<'a> AstValidator<'a> {
         self.outer_impl_trait = old;
     }
 
-    fn visit_assoc_type_binding_from_generic_args(&mut self, type_binding: &'a TypeBinding) {
-        // rust-lang/rust#57979: bug in old `visit_generic_args` called
-        // `walk_ty` rather than `visit_ty`, skipping outer `impl Trait`
-        // if it happened to occur at `type_binding.ty`.
-        if let TyKind::ImplTrait(..) = type_binding.ty.node {
-            self.warning_period_57979_didnt_record_next_impl_trait = true;
+    fn visit_assoc_ty_constraint_from_generic_args(&mut self, constraint: &'a AssocTyConstraint) {
+        if let AssocTyConstraintKind::Equality { ref ty } = constraint.kind {
+            // rust-lang/rust#57979: bug in old `visit_generic_args` called
+            // `walk_ty` rather than `visit_ty`, skipping outer `impl Trait`
+            // if it happened to occur at `ty`.
+            if let TyKind::ImplTrait(..) = ty.node {
+                self.warning_period_57979_didnt_record_next_impl_trait = true;
+            }
         }
-        self.visit_assoc_type_binding(type_binding);
+        self.visit_assoc_ty_constraint(constraint);
     }
 
     fn visit_ty_from_generic_args(&mut self, ty: &'a Ty) {
@@ -724,7 +726,7 @@ impl<'a> Visitor<'a> for AstValidator<'a> {
                 // Type bindings such as `Item = impl Debug` in `Iterator<Item = Debug>`
                 // are allowed to contain nested `impl Trait`.
                 self.with_impl_trait(None, |this| {
-                    walk_list!(this, visit_assoc_type_binding_from_generic_args, &data.bindings);
+                    walk_list!(this, visit_assoc_ty_constraint_from_generic_args, &data.constraints);
                 });
             }
             GenericArgs::Parenthesized(ref data) => {
diff --git a/src/librustc_passes/hir_stats.rs b/src/librustc_passes/hir_stats.rs
index 0088c97679c..6936aedb9de 100644
--- a/src/librustc_passes/hir_stats.rs
+++ b/src/librustc_passes/hir_stats.rs
@@ -353,9 +353,9 @@ impl<'v> ast_visit::Visitor<'v> for StatCollector<'v> {
         ast_visit::walk_path_segment(self, path_span, path_segment)
     }
 
-    fn visit_assoc_type_binding(&mut self, type_binding: &'v ast::TypeBinding) {
-        self.record("TypeBinding", Id::None, type_binding);
-        ast_visit::walk_assoc_type_binding(self, type_binding)
+    fn visit_assoc_ty_constraint(&mut self, constraint: &'v ast::AssocTyConstraint) {
+        self.record("AssocTyConstraint", Id::None, constraint);
+        ast_visit::walk_assoc_ty_constraint(self, constraint)
     }
 
     fn visit_attribute(&mut self, attr: &'v ast::Attribute) {
diff --git a/src/librustc_typeck/check/wfcheck.rs b/src/librustc_typeck/check/wfcheck.rs
index e11172ae36d..2b627a69250 100644
--- a/src/librustc_typeck/check/wfcheck.rs
+++ b/src/librustc_typeck/check/wfcheck.rs
@@ -20,8 +20,11 @@ use rustc::hir::itemlikevisit::ParItemLikeVisitor;
 use rustc::hir;
 
 /// Helper type of a temporary returned by `.for_item(...)`.
-/// Necessary because we can't write the following bound:
-/// `F: for<'b, 'tcx> where 'gcx: 'tcx FnOnce(FnCtxt<'b, 'gcx, 'tcx>)`.
+/// This is necessary because we can't write the following bound:
+///
+/// ```rust
+/// F: for<'b, 'tcx> where 'gcx: 'tcx FnOnce(FnCtxt<'b, 'gcx, 'tcx>)
+/// ```
 struct CheckWfFcxBuilder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     inherited: super::InheritedBuilder<'a, 'gcx, 'tcx>,
     id: hir::HirId,
@@ -42,7 +45,7 @@ impl<'a, 'gcx, 'tcx> CheckWfFcxBuilder<'a, 'gcx, 'tcx> {
             if !inh.tcx.features().trivial_bounds {
                 // As predicates are cached rather than obligations, this
                 // needsto be called first so that they are checked with an
-                // empty param_env.
+                // empty `param_env`.
                 check_false_global_bounds(&fcx, span, id);
             }
             let wf_tys = f(&fcx, fcx.tcx.global_tcx());
@@ -56,7 +59,9 @@ impl<'a, 'gcx, 'tcx> CheckWfFcxBuilder<'a, 'gcx, 'tcx> {
 /// well-formed, meaning that they do not require any constraints not declared in the struct
 /// definition itself. For example, this definition would be illegal:
 ///
-///     struct Ref<'a, T> { x: &'a T }
+/// ```rust
+/// struct Ref<'a, T> { x: &'a T }
+/// ```
 ///
 /// because the type did not declare that `T:'a`.
 ///
@@ -75,7 +80,7 @@ pub fn check_item_well_formed<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: Def
         // Right now we check that every default trait implementation
         // has an implementation of itself. Basically, a case like:
         //
-        // `impl Trait for T {}`
+        //     impl Trait for T {}
         //
         // has a requirement of `T: Trait` which was required for default
         // method implementations. Although this could be improved now that
@@ -85,7 +90,7 @@ pub fn check_item_well_formed<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: Def
         // Since there's such a requirement, we need to check *just* positive
         // implementations, otherwise things like:
         //
-        // impl !Send for T {}
+        //     impl !Send for T {}
         //
         // won't be allowed unless there's an *explicit* implementation of `Send`
         // for `T`
@@ -98,7 +103,7 @@ pub fn check_item_well_formed<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: Def
             if polarity == hir::ImplPolarity::Positive {
                 check_impl(tcx, item, self_ty, trait_ref);
             } else {
-                // FIXME(#27579) what amount of WF checking do we need for neg impls?
+                // FIXME(#27579): what amount of WF checking do we need for neg impls?
                 if trait_ref.is_some() && !is_auto {
                     span_err!(tcx.sess, item.span, E0192,
                               "negative impls are only allowed for \
@@ -302,7 +307,8 @@ fn check_type_defn<'a, 'tcx, F>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
         check_where_clauses(tcx, fcx, item.span, def_id, None);
 
-        vec![] // no implied bounds in a struct def'n
+        // No implied bounds in a struct definition.
+        vec![]
     });
 }
 
@@ -369,7 +375,8 @@ fn check_item_type<'a, 'tcx>(
             );
         }
 
-        vec![] // no implied bounds in a const etc
+        // No implied bounds in a const, etc.
+        vec![]
     });
 }
 
@@ -421,6 +428,8 @@ fn check_where_clauses<'a, 'gcx, 'fcx, 'tcx>(
     def_id: DefId,
     return_ty: Option<Ty<'tcx>>,
 ) {
+    debug!("check_where_clauses(def_id={:?}, return_ty={:?})", def_id, return_ty);
+
     let predicates = fcx.tcx.predicates_of(def_id);
     let generics = tcx.generics_of(def_id);
 
@@ -434,15 +443,17 @@ fn check_where_clauses<'a, 'gcx, 'fcx, 'tcx>(
     };
 
     // Check that concrete defaults are well-formed. See test `type-check-defaults.rs`.
-    // For example this forbids the declaration:
-    // struct Foo<T = Vec<[u32]>> { .. }
-    // Here the default `Vec<[u32]>` is not WF because `[u32]: Sized` does not hold.
+    // For example, this forbids the declaration:
+    //
+    //     struct Foo<T = Vec<[u32]>> { .. }
+    //
+    // Here, the default `Vec<[u32]>` is not WF because `[u32]: Sized` does not hold.
     for param in &generics.params {
         if let GenericParamDefKind::Type { .. } = param.kind {
             if is_our_default(&param) {
                 let ty = fcx.tcx.type_of(param.def_id);
-                // ignore dependent defaults -- that is, where the default of one type
-                // parameter includes another (e.g., <T, U = T>). In those cases, we can't
+                // Ignore dependent defaults -- that is, where the default of one type
+                // parameter includes another (e.g., `<T, U = T>`). In those cases, we can't
                 // be sure if it will error or not as user might always specify the other.
                 if !ty.needs_subst() {
                     fcx.register_wf_obligation(ty, fcx.tcx.def_span(param.def_id),
@@ -468,16 +479,16 @@ fn check_where_clauses<'a, 'gcx, 'fcx, 'tcx>(
             }
 
             GenericParamDefKind::Type { .. } => {
-                // If the param has a default,
+                // If the param has a default, ...
                 if is_our_default(param) {
                     let default_ty = fcx.tcx.type_of(param.def_id);
-                    // and it's not a dependent default
+                    // ... and it's not a dependent default, ...
                     if !default_ty.needs_subst() {
-                        // then substitute with the default.
+                        // ... then substitute it with the default.
                         return default_ty.into();
                     }
                 }
-                // Mark unwanted params as err.
+                // Mark unwanted params as error.
                 fcx.tcx.types.err.into()
             }
 
@@ -525,7 +536,7 @@ fn check_where_clauses<'a, 'gcx, 'fcx, 'tcx>(
             Some(substituted_pred)
         }
     }).map(|pred| {
-        // convert each of those into an obligation. So if you have
+        // Convert each of those into an obligation. So if you have
         // something like `struct Foo<T: Copy = String>`, we would
         // take that predicate `T: Copy`, substitute to `String: Copy`
         // (actually that happens in the previous `flat_map` call),
@@ -595,14 +606,13 @@ fn check_fn_or_method<'a, 'fcx, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'gcx>,
 /// ```rust
 /// existential type Foo<A, B>;
 ///
-/// // ok -- `Foo` is applied to two distinct, generic types.
+/// // Okay -- `Foo` is applied to two distinct, generic types.
 /// fn a<T, U>() -> Foo<T, U> { .. }
 ///
-/// // not ok -- `Foo` is applied to `T` twice.
+/// // Not okay -- `Foo` is applied to `T` twice.
 /// fn b<T>() -> Foo<T, T> { .. }
 ///
-///
-/// // not ok -- `Foo` is applied to a non-generic type.
+/// // Not okay -- `Foo` is applied to a non-generic type.
 /// fn b<T>() -> Foo<T, u32> { .. }
 /// ```
 ///
@@ -613,7 +623,7 @@ fn check_existential_types<'a, 'fcx, 'gcx, 'tcx>(
     span: Span,
     ty: Ty<'tcx>,
 ) -> Vec<ty::Predicate<'tcx>> {
-    trace!("check_existential_types: {:?}", ty);
+    trace!("check_existential_types(ty={:?})", ty);
     let mut substituted_predicates = Vec::new();
     ty.fold_with(&mut ty::fold::BottomUpFolder {
         tcx: fcx.tcx,
@@ -621,17 +631,17 @@ fn check_existential_types<'a, 'fcx, 'gcx, 'tcx>(
             if let ty::Opaque(def_id, substs) = ty.sty {
                 trace!("check_existential_types: opaque_ty, {:?}, {:?}", def_id, substs);
                 let generics = tcx.generics_of(def_id);
-                // only check named existential types defined in this crate
+                // Only check named existential types defined in this crate.
                 if generics.parent.is_none() && def_id.is_local() {
                     let opaque_hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
                     if may_define_existential_type(tcx, fn_def_id, opaque_hir_id) {
-                        trace!("check_existential_types may define. Generics: {:#?}", generics);
+                        trace!("check_existential_types: may define, generics={:#?}", generics);
                         let mut seen: FxHashMap<_, Vec<_>> = FxHashMap::default();
                         for (subst, param) in substs.iter().zip(&generics.params) {
                             match subst.unpack() {
                                 ty::subst::UnpackedKind::Type(ty) => match ty.sty {
                                     ty::Param(..) => {}
-                                    // prevent `fn foo() -> Foo<u32>` from being defining
+                                    // Prevent `fn foo() -> Foo<u32>` from being defining.
                                     _ => {
                                         tcx.sess
                                             .struct_span_err(
@@ -713,20 +723,19 @@ fn check_existential_types<'a, 'fcx, 'gcx, 'tcx>(
                         }
                     } // if may_define_existential_type
 
-                    // now register the bounds on the parameters of the existential type
-                    // so the parameters given by the function need to fulfill them
-                    // ```rust
-                    // existential type Foo<T: Bar>: 'static;
-                    // fn foo<U>() -> Foo<U> { .. *}
-                    // ```
+                    // Now register the bounds on the parameters of the existential type
+                    // so the parameters given by the function need to fulfill them.
+                    //
+                    //     existential type Foo<T: Bar>: 'static;
+                    //     fn foo<U>() -> Foo<U> { .. *}
+                    //
                     // becomes
-                    // ```rust
-                    // existential type Foo<T: Bar>: 'static;
-                    // fn foo<U: Bar>() -> Foo<U> { .. *}
-                    // ```
+                    //
+                    //     existential type Foo<T: Bar>: 'static;
+                    //     fn foo<U: Bar>() -> Foo<U> { .. *}
                     let predicates = tcx.predicates_of(def_id);
                     trace!(
-                        "check_existential_types may define. adding predicates: {:#?}",
+                        "check_existential_types: may define, predicates={:#?}",
                         predicates,
                     );
                     for &(pred, _) in predicates.predicates.iter() {
@@ -751,7 +760,7 @@ fn check_method_receiver<'fcx, 'gcx, 'tcx>(fcx: &FnCtxt<'fcx, 'gcx, 'tcx>,
                                            method: &ty::AssocItem,
                                            self_ty: Ty<'tcx>)
 {
-    // check that the method has a valid receiver type, given the type `Self`
+    // Check that the method has a valid receiver type, given the type `Self`.
     debug!("check_method_receiver({:?}, self_ty={:?})",
            method, self_ty);
 
@@ -783,7 +792,7 @@ fn check_method_receiver<'fcx, 'gcx, 'tcx>(fcx: &FnCtxt<'fcx, 'gcx, 'tcx>,
 
     if fcx.tcx.features().arbitrary_self_types {
         if !receiver_is_valid(fcx, span, receiver_ty, self_ty, true) {
-            // report error, arbitrary_self_types was enabled
+            // Report error; `arbitrary_self_types` was enabled.
             fcx.tcx.sess.diagnostic().mut_span_err(
                 span, &format!("invalid method receiver type: {:?}", receiver_ty)
             ).note("type of `self` must be `Self` or a type that dereferences to it")
@@ -794,7 +803,7 @@ fn check_method_receiver<'fcx, 'gcx, 'tcx>(fcx: &FnCtxt<'fcx, 'gcx, 'tcx>,
     } else {
         if !receiver_is_valid(fcx, span, receiver_ty, self_ty, false) {
             if receiver_is_valid(fcx, span, receiver_ty, self_ty, true) {
-                // report error, would have worked with arbitrary_self_types
+                // Report error; would have worked with `arbitrary_self_types`.
                 feature_gate::feature_err(
                     &fcx.tcx.sess.parse_sess,
                     sym::arbitrary_self_types,
@@ -808,7 +817,7 @@ fn check_method_receiver<'fcx, 'gcx, 'tcx>(fcx: &FnCtxt<'fcx, 'gcx, 'tcx>,
                 ).help("consider changing to `self`, `&self`, `&mut self`, or `self: Box<Self>`")
                 .emit();
             } else {
-                // report error, would not have worked with arbitrary_self_types
+                // Report error; would not have worked with `arbitrary_self_types`.
                 fcx.tcx.sess.diagnostic().mut_span_err(
                     span, &format!("invalid method receiver type: {:?}", receiver_ty)
                 ).note("type must be `Self` or a type that dereferences to it")
@@ -820,10 +829,11 @@ fn check_method_receiver<'fcx, 'gcx, 'tcx>(fcx: &FnCtxt<'fcx, 'gcx, 'tcx>,
     }
 }
 
-/// returns true if `receiver_ty` would be considered a valid receiver type for `self_ty`. If
+/// Returns whether `receiver_ty` would be considered a valid receiver type for `self_ty`. If
 /// `arbitrary_self_types` is enabled, `receiver_ty` must transitively deref to `self_ty`, possibly
 /// through a `*const/mut T` raw pointer. If the feature is not enabled, the requirements are more
-/// strict: `receiver_ty` must implement `Receiver` and directly implement `Deref<Target=self_ty>`.
+/// strict: `receiver_ty` must implement `Receiver` and directly implement
+/// `Deref<Target = self_ty>`.
 ///
 /// N.B., there are cases this function returns `true` but causes an error to be emitted,
 /// particularly when `receiver_ty` derefs to a type that is the same as `self_ty` but has the
@@ -839,7 +849,7 @@ fn receiver_is_valid<'fcx, 'tcx, 'gcx>(
 
     let can_eq_self = |ty| fcx.infcx.can_eq(fcx.param_env, self_ty, ty).is_ok();
 
-    // `self: Self` is always valid
+    // `self: Self` is always valid.
     if can_eq_self(receiver_ty) {
         if let Some(mut err) = fcx.demand_eqtype_with_origin(&cause, self_ty, receiver_ty) {
             err.emit();
@@ -849,15 +859,15 @@ fn receiver_is_valid<'fcx, 'tcx, 'gcx>(
 
     let mut autoderef = fcx.autoderef(span, receiver_ty);
 
-    // the `arbitrary_self_types` feature allows raw pointer receivers like `self: *const Self`
+    // The `arbitrary_self_types` feature allows raw pointer receivers like `self: *const Self`.
     if arbitrary_self_types_enabled {
         autoderef = autoderef.include_raw_pointers();
     }
 
-    // the first type is `receiver_ty`, which we know its not equal to `self_ty`. skip it.
+    // The first type is `receiver_ty`, which we know its not equal to `self_ty`; skip it.
     autoderef.next();
 
-    // keep dereferencing `receiver_ty` until we get to `self_ty`
+    // Keep dereferencing `receiver_ty` until we get to `self_ty`.
     loop {
         if let Some((potential_self_ty, _)) = autoderef.next() {
             debug!("receiver_is_valid: potential self type `{:?}` to match `{:?}`",
@@ -882,14 +892,14 @@ fn receiver_is_valid<'fcx, 'tcx, 'gcx>(
             return receiver_ty.references_error();
         }
 
-        // without the `arbitrary_self_types` feature, `receiver_ty` must directly deref to
-        // `self_ty`. Enforce this by only doing one iteration of the loop
+        // Without the `arbitrary_self_types` feature, `receiver_ty` must directly deref to
+        // `self_ty`. Enforce this by only doing one iteration of the loop.
         if !arbitrary_self_types_enabled {
             return false
         }
     }
 
-    // without `feature(arbitrary_self_types)`, we require that `receiver_ty` implements `Receiver`
+    // Without `feature(arbitrary_self_types)`, we require that `receiver_ty` implements `Receiver`.
     if !arbitrary_self_types_enabled {
         let trait_def_id = match fcx.tcx.lang_items().receiver_trait() {
             Some(did) => did,
@@ -968,7 +978,7 @@ fn report_bivariance<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     let mut err = error_392(tcx, span, param_name);
 
     let suggested_marker_id = tcx.lang_items().phantom_data();
-    // help is available only in presence of lang items
+    // Help is available only in presence of lang items.
     if let Some(def_id) = suggested_marker_id {
         err.help(&format!("consider removing `{}` or using a marker such as `{}`",
                           param_name,
@@ -988,12 +998,12 @@ fn reject_shadowing_parameters(tcx: TyCtxt<'_, '_, '_>, def_id: DefId) {
     }).collect();
 
     for method_param in &generics.params {
-        // Shadowing is checked in resolve_lifetime.
+        // Shadowing is checked in `resolve_lifetime`.
         if let GenericParamDefKind::Lifetime = method_param.kind {
             continue
         }
         if impl_params.contains_key(&method_param.name) {
-            // Tighten up the span to focus on only the shadowing type
+            // Tighten up the span to focus on only the shadowing type.
             let type_span = tcx.def_span(method_param.def_id);
 
             // The expectation here is that the original trait declaration is
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index f362263c16e..ee7961197d3 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -1488,10 +1488,13 @@ fn find_existential_constraints<'a, 'tcx>(
 
     impl<'a, 'tcx> ConstraintLocator<'a, 'tcx> {
         fn check(&mut self, def_id: DefId) {
-            trace!("checking {:?}", def_id);
-            // don't try to check items that cannot possibly constrain the type
+            // Don't try to check items that cannot possibly constrain the type.
             if !self.tcx.has_typeck_tables(def_id) {
-                trace!("no typeck tables for {:?}", def_id);
+                debug!(
+                    "find_existential_constraints: no constraint for `{:?}` at `{:?}`: no tables",
+                    self.def_id,
+                    def_id,
+                );
                 return;
             }
             let ty = self
@@ -1500,7 +1503,14 @@ fn find_existential_constraints<'a, 'tcx>(
                 .concrete_existential_types
                 .get(&self.def_id);
             if let Some(ty::ResolvedOpaqueTy { concrete_type, substs }) = ty {
-                // FIXME(oli-obk): trace the actual span from inference to improve errors
+                debug!(
+                    "find_existential_constraints: found constraint for `{:?}` at `{:?}`: {:?}",
+                    self.def_id,
+                    def_id,
+                    ty,
+                );
+
+                // FIXME(oli-obk): trace the actual span from inference to improve errors.
                 let span = self.tcx.def_span(def_id);
                 // used to quickly look up the position of a generic parameter
                 let mut index_map: FxHashMap<ty::ParamTy, usize> = FxHashMap::default();
@@ -1555,14 +1565,15 @@ fn find_existential_constraints<'a, 'tcx>(
                     let mut ty = concrete_type.walk().fuse();
                     let mut p_ty = prev_ty.walk().fuse();
                     let iter_eq = (&mut ty).zip(&mut p_ty).all(|(t, p)| match (&t.sty, &p.sty) {
-                        // type parameters are equal to any other type parameter for the purpose of
+                        // Type parameters are equal to any other type parameter for the purpose of
                         // concrete type equality, as it is possible to obtain the same type just
                         // by passing matching parameters to a function.
                         (ty::Param(_), ty::Param(_)) => true,
                         _ => t == p,
                     });
                     if !iter_eq || ty.next().is_some() || p_ty.next().is_some() {
-                        // found different concrete types for the existential type
+                        debug!("find_existential_constraints: span={:?}", span);
+                        // Found different concrete types for the existential type.
                         let mut err = self.tcx.sess.struct_span_err(
                             span,
                             "concrete type differs from previous defining existential type use",
@@ -1574,7 +1585,7 @@ fn find_existential_constraints<'a, 'tcx>(
                         err.span_note(prev_span, "previous use here");
                         err.emit();
                     } else if indices != *prev_indices {
-                        // found "same" concrete types, but the generic parameter order differs
+                        // Found "same" concrete types, but the generic parameter order differs.
                         let mut err = self.tcx.sess.struct_span_err(
                             span,
                             "concrete type's generic parameters differ from previous defining use",
@@ -1602,6 +1613,12 @@ fn find_existential_constraints<'a, 'tcx>(
                 } else {
                     self.found = Some((span, concrete_type, indices));
                 }
+            } else {
+                debug!(
+                    "find_existential_constraints: no constraint for `{:?}` at `{:?}`",
+                    self.def_id,
+                    def_id,
+                );
             }
         }
     }
@@ -1633,26 +1650,27 @@ 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 mut locator = ConstraintLocator {
         def_id,
         tcx,
         found: None,
     };
-    let hir_id = tcx.hir().as_local_hir_id(def_id).unwrap();
-    let parent = tcx.hir().get_parent_item(hir_id);
 
-    trace!("parent_id: {:?}", parent);
+    debug!("find_existential_constraints: scope_id={:?}", scope_id);
 
-    if parent == hir::CRATE_HIR_ID {
+    if scope_id == ast::CRATE_HIR_ID {
         intravisit::walk_crate(&mut locator, tcx.hir().krate());
     } else {
-        trace!("parent: {:?}", tcx.hir().get_by_hir_id(parent));
-        match tcx.hir().get_by_hir_id(parent) {
+        debug!("find_existential_constraints: scope={:?}", tcx.hir().get_by_hir_id(scope_id));
+        match tcx.hir().get_by_hir_id(scope_id) {
             Node::Item(ref it) => intravisit::walk_item(&mut locator, it),
             Node::ImplItem(ref it) => intravisit::walk_impl_item(&mut locator, it),
             Node::TraitItem(ref it) => intravisit::walk_trait_item(&mut locator, it),
             other => bug!(
-                "{:?} is not a valid parent of an existential type item",
+                "{:?} is not a valid scope for an existential type item",
                 other
             ),
         }
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 31e89804800..598232f9f8f 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -190,9 +190,9 @@ pub struct AngleBracketedArgs {
     pub span: Span,
     /// The arguments for this path segment.
     pub args: Vec<GenericArg>,
-    /// Bindings (equality constraints) on associated types, if present.
-    /// E.g., `Foo<A = Bar>`.
-    pub bindings: Vec<TypeBinding>,
+    /// Constraints on associated types, if any.
+    /// E.g., `Foo<A = Bar, B: Baz>`.
+    pub constraints: Vec<AssocTyConstraint>,
 }
 
 impl Into<Option<P<GenericArgs>>> for AngleBracketedArgs {
@@ -225,7 +225,7 @@ impl ParenthesizedArgs {
         AngleBracketedArgs {
             span: self.span,
             args: self.inputs.iter().cloned().map(|input| GenericArg::Type(input)).collect(),
-            bindings: vec![],
+            constraints: vec![],
         }
     }
 }
@@ -1611,15 +1611,29 @@ impl fmt::Display for UintTy {
     }
 }
 
-// Bind a type to an associated type: `A = Foo`.
+/// A constraint on an associated type (e.g., `A = Bar` in `Foo<A = Bar>` or
+/// `A: TraitA + TraitB` in `Foo<A: TraitA + TraitB>`).
 #[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
-pub struct TypeBinding {
+pub struct AssocTyConstraint {
     pub id: NodeId,
     pub ident: Ident,
-    pub ty: P<Ty>,
+    pub kind: AssocTyConstraintKind,
     pub span: Span,
 }
 
+/// The kinds of an `AssocTyConstraint`.
+#[derive(Clone, RustcEncodable, RustcDecodable, Debug)]
+pub enum AssocTyConstraintKind {
+    /// E.g., `A = Bar` in `Foo<A = Bar>`.
+    Equality {
+        ty: P<Ty>,
+    },
+    /// E.g. `A: TraitA + TraitB` in `Foo<A: TraitA + TraitB>`.
+    Bound {
+        bounds: GenericBounds,
+    },
+}
+
 #[derive(Clone, RustcEncodable, RustcDecodable)]
 pub struct Ty {
     pub id: NodeId,
diff --git a/src/libsyntax/ext/build.rs b/src/libsyntax/ext/build.rs
index 435a3d7b6a2..2a03e49996b 100644
--- a/src/libsyntax/ext/build.rs
+++ b/src/libsyntax/ext/build.rs
@@ -18,7 +18,7 @@ pub trait AstBuilder {
                 global: bool,
                 idents: Vec<ast::Ident>,
                 args: Vec<ast::GenericArg>,
-                bindings: Vec<ast::TypeBinding>)
+                constraints: Vec<ast::AssocTyConstraint>)
         -> ast::Path;
 
     fn qpath(&self, self_type: P<ast::Ty>,
@@ -29,7 +29,7 @@ pub trait AstBuilder {
                 trait_path: ast::Path,
                 ident: ast::Ident,
                 args: Vec<ast::GenericArg>,
-                bindings: Vec<ast::TypeBinding>)
+                constraints: Vec<ast::AssocTyConstraint>)
                 -> (ast::QSelf, ast::Path);
 
     // types and consts
@@ -302,7 +302,7 @@ impl<'a> AstBuilder for ExtCtxt<'a> {
                 global: bool,
                 mut idents: Vec<ast::Ident> ,
                 args: Vec<ast::GenericArg>,
-                bindings: Vec<ast::TypeBinding> )
+                constraints: Vec<ast::AssocTyConstraint> )
                 -> ast::Path {
         assert!(!idents.is_empty());
         let add_root = global && !idents[0].is_path_segment_keyword();
@@ -314,8 +314,8 @@ impl<'a> AstBuilder for ExtCtxt<'a> {
         segments.extend(idents.into_iter().map(|ident| {
             ast::PathSegment::from_ident(ident.with_span_pos(span))
         }));
-        let args = if !args.is_empty() || !bindings.is_empty() {
-            ast::AngleBracketedArgs { args, bindings, span }.into()
+        let args = if !args.is_empty() || !constraints.is_empty() {
+            ast::AngleBracketedArgs { args, constraints, span }.into()
         } else {
             None
         };
@@ -346,11 +346,11 @@ impl<'a> AstBuilder for ExtCtxt<'a> {
                  trait_path: ast::Path,
                  ident: ast::Ident,
                  args: Vec<ast::GenericArg>,
-                 bindings: Vec<ast::TypeBinding>)
+                 constraints: Vec<ast::AssocTyConstraint>)
                  -> (ast::QSelf, ast::Path) {
         let mut path = trait_path;
-        let args = if !args.is_empty() || !bindings.is_empty() {
-            ast::AngleBracketedArgs { args, bindings, span: ident.span }.into()
+        let args = if !args.is_empty() || !constraints.is_empty() {
+            ast::AngleBracketedArgs { args, constraints, span: ident.span }.into()
         } else {
             None
         };
diff --git a/src/libsyntax/mut_visit.rs b/src/libsyntax/mut_visit.rs
index 75751309899..fb1a7a680ba 100644
--- a/src/libsyntax/mut_visit.rs
+++ b/src/libsyntax/mut_visit.rs
@@ -163,8 +163,8 @@ pub trait MutVisitor: Sized {
         noop_visit_lifetime(l, self);
     }
 
-    fn visit_ty_binding(&mut self, t: &mut TypeBinding) {
-        noop_visit_ty_binding(t, self);
+    fn visit_ty_constraint(&mut self, t: &mut AssocTyConstraint) {
+        noop_visit_ty_constraint(t, self);
     }
 
     fn visit_mod(&mut self, m: &mut Mod) {
@@ -400,11 +400,20 @@ pub fn noop_visit_guard<T: MutVisitor>(g: &mut Guard, vis: &mut T) {
     }
 }
 
-pub fn noop_visit_ty_binding<T: MutVisitor>(TypeBinding { id, ident, ty, span }: &mut TypeBinding,
-                                            vis: &mut T) {
+pub fn noop_visit_ty_constraint<T: MutVisitor>(
+    AssocTyConstraint { id, ident, kind, span }: &mut AssocTyConstraint,
+    vis: &mut T
+) {
     vis.visit_id(id);
     vis.visit_ident(ident);
-    vis.visit_ty(ty);
+    match kind {
+        AssocTyConstraintKind::Equality { ref mut ty } => {
+            vis.visit_ty(ty);
+        }
+        AssocTyConstraintKind::Bound { ref mut bounds } => {
+            visit_bounds(bounds, vis);
+        }
+    }
     vis.visit_span(span);
 }
 
@@ -499,9 +508,9 @@ pub fn noop_visit_generic_arg<T: MutVisitor>(arg: &mut GenericArg, vis: &mut T)
 
 pub fn noop_visit_angle_bracketed_parameter_data<T: MutVisitor>(data: &mut AngleBracketedArgs,
                                                                 vis: &mut T) {
-    let AngleBracketedArgs { args, bindings, span } = data;
+    let AngleBracketedArgs { args, constraints, span } = data;
     visit_vec(args, |arg| vis.visit_generic_arg(arg));
-    visit_vec(bindings, |binding| vis.visit_ty_binding(binding));
+    visit_vec(constraints, |constraint| vis.visit_ty_constraint(constraint));
     vis.visit_span(span);
 }
 
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index abfce660c80..790013f6eb1 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -27,7 +27,7 @@ use crate::ast::{VariantData, StructField};
 use crate::ast::StrStyle;
 use crate::ast::SelfKind;
 use crate::ast::{TraitItem, TraitRef, TraitObjectSyntax};
-use crate::ast::{Ty, TyKind, TypeBinding, GenericBounds};
+use crate::ast::{Ty, TyKind, AssocTyConstraint, AssocTyConstraintKind, GenericBounds};
 use crate::ast::{Visibility, VisibilityKind, WhereClause, CrateSugar};
 use crate::ast::{UseTree, UseTreeKind};
 use crate::ast::{BinOpKind, UnOp};
@@ -1791,11 +1791,11 @@ impl<'a> Parser<'a> {
             let lo = self.span;
             let args = if self.eat_lt() {
                 // `<'a, T, A = U>`
-                let (args, bindings) =
+                let (args, constraints) =
                     self.parse_generic_args_with_leaning_angle_bracket_recovery(style, lo)?;
                 self.expect_gt()?;
                 let span = lo.to(self.prev_span);
-                AngleBracketedArgs { args, bindings, span }.into()
+                AngleBracketedArgs { args, constraints, span }.into()
             } else {
                 // `(T, U) -> R`
                 self.bump(); // `(`
@@ -5076,7 +5076,7 @@ impl<'a> Parser<'a> {
         &mut self,
         style: PathStyle,
         lo: Span,
-    ) -> PResult<'a, (Vec<GenericArg>, Vec<TypeBinding>)> {
+    ) -> PResult<'a, (Vec<GenericArg>, Vec<AssocTyConstraint>)> {
         // We need to detect whether there are extra leading left angle brackets and produce an
         // appropriate error and suggestion. This cannot be implemented by looking ahead at
         // upcoming tokens for a matching `>` character - if there are unmatched `<` tokens
@@ -5211,11 +5211,11 @@ impl<'a> Parser<'a> {
 
     /// Parses (possibly empty) list of lifetime and type arguments and associated type bindings,
     /// possibly including trailing comma.
-    fn parse_generic_args(&mut self) -> PResult<'a, (Vec<GenericArg>, Vec<TypeBinding>)> {
+    fn parse_generic_args(&mut self) -> PResult<'a, (Vec<GenericArg>, Vec<AssocTyConstraint>)> {
         let mut args = Vec::new();
-        let mut bindings = Vec::new();
-        let mut misplaced_assoc_ty_bindings: Vec<Span> = Vec::new();
-        let mut assoc_ty_bindings: Vec<Span> = Vec::new();
+        let mut constraints = Vec::new();
+        let mut misplaced_assoc_ty_constraints: Vec<Span> = Vec::new();
+        let mut assoc_ty_constraints: Vec<Span> = Vec::new();
 
         let args_lo = self.span;
 
@@ -5223,21 +5223,31 @@ impl<'a> Parser<'a> {
             if self.check_lifetime() && self.look_ahead(1, |t| !t.is_like_plus()) {
                 // Parse lifetime argument.
                 args.push(GenericArg::Lifetime(self.expect_lifetime()));
-                misplaced_assoc_ty_bindings.append(&mut assoc_ty_bindings);
-            } else if self.check_ident() && self.look_ahead(1, |t| t == &token::Eq) {
-                // Parse associated type binding.
+                misplaced_assoc_ty_constraints.append(&mut assoc_ty_constraints);
+            } else if self.check_ident() && self.look_ahead(1,
+                    |t| t == &token::Eq || t == &token::Colon) {
+                // Parse associated type constraint.
                 let lo = self.span;
                 let ident = self.parse_ident()?;
-                self.bump();
-                let ty = self.parse_ty()?;
+                let kind = if self.eat(&token::Eq) {
+                    AssocTyConstraintKind::Equality {
+                        ty: self.parse_ty()?,
+                    }
+                } else if self.eat(&token::Colon) {
+                    AssocTyConstraintKind::Bound {
+                        bounds: self.parse_generic_bounds(Some(self.prev_span))?,
+                    }
+                } else {
+                    unreachable!();
+                };
                 let span = lo.to(self.prev_span);
-                bindings.push(TypeBinding {
+                constraints.push(AssocTyConstraint {
                     id: ast::DUMMY_NODE_ID,
                     ident,
-                    ty,
+                    kind,
                     span,
                 });
-                assoc_ty_bindings.push(span);
+                assoc_ty_constraints.push(span);
             } else if self.check_const_arg() {
                 // Parse const argument.
                 let expr = if let token::OpenDelim(token::Brace) = self.token {
@@ -5261,11 +5271,11 @@ impl<'a> Parser<'a> {
                     value: expr,
                 };
                 args.push(GenericArg::Const(value));
-                misplaced_assoc_ty_bindings.append(&mut assoc_ty_bindings);
+                misplaced_assoc_ty_constraints.append(&mut assoc_ty_constraints);
             } else if self.check_type() {
                 // Parse type argument.
                 args.push(GenericArg::Type(self.parse_ty()?));
-                misplaced_assoc_ty_bindings.append(&mut assoc_ty_bindings);
+                misplaced_assoc_ty_constraints.append(&mut assoc_ty_constraints);
             } else {
                 break
             }
@@ -5278,12 +5288,12 @@ impl<'a> Parser<'a> {
         // FIXME: we would like to report this in ast_validation instead, but we currently do not
         // preserve ordering of generic parameters with respect to associated type binding, so we
         // lose that information after parsing.
-        if misplaced_assoc_ty_bindings.len() > 0 {
+        if misplaced_assoc_ty_constraints.len() > 0 {
             let mut err = self.struct_span_err(
                 args_lo.to(self.prev_span),
                 "associated type bindings must be declared after generic parameters",
             );
-            for span in misplaced_assoc_ty_bindings {
+            for span in misplaced_assoc_ty_constraints {
                 err.span_label(
                     span,
                     "this associated type binding should be moved after the generic parameters",
@@ -5292,7 +5302,7 @@ impl<'a> Parser<'a> {
             err.emit();
         }
 
-        Ok((args, bindings))
+        Ok((args, constraints))
     }
 
     /// Parses an optional where-clause and places it in `generics`.
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index 44e1f5398d3..57c01e9e3ef 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -2450,14 +2450,21 @@ impl<'a> State<'a> {
 
                 let mut comma = data.args.len() != 0;
 
-                for binding in data.bindings.iter() {
+                for constraint in data.constraints.iter() {
                     if comma {
                         self.word_space(",")?
                     }
-                    self.print_ident(binding.ident)?;
+                    self.print_ident(constraint.ident)?;
                     self.s.space()?;
-                    self.word_space("=")?;
-                    self.print_type(&binding.ty)?;
+                    match constraint.kind {
+                        ast::AssocTyConstraintKind::Equality { ref ty } => {
+                            self.word_space("=")?;
+                            self.print_type(ty)?;
+                        }
+                        ast::AssocTyConstraintKind::Bound { ref bounds } => {
+                            self.print_type_bounds(":", &*bounds)?;
+                        }
+                    }
                     comma = true;
                 }
 
diff --git a/src/libsyntax/util/node_count.rs b/src/libsyntax/util/node_count.rs
index 521edac8f5f..f17eb3b3943 100644
--- a/src/libsyntax/util/node_count.rs
+++ b/src/libsyntax/util/node_count.rs
@@ -131,9 +131,9 @@ impl<'ast> Visitor<'ast> for NodeCounter {
         self.count += 1;
         walk_generic_args(self, path_span, generic_args)
     }
-    fn visit_assoc_type_binding(&mut self, type_binding: &TypeBinding) {
+    fn visit_assoc_ty_constraint(&mut self, constraint: &AssocTyConstraint) {
         self.count += 1;
-        walk_assoc_type_binding(self, type_binding)
+        walk_assoc_ty_constraint(self, constraint)
     }
     fn visit_attribute(&mut self, _attr: &Attribute) {
         self.count += 1;
diff --git a/src/libsyntax/visit.rs b/src/libsyntax/visit.rs
index ba57055b8e0..334709b1521 100644
--- a/src/libsyntax/visit.rs
+++ b/src/libsyntax/visit.rs
@@ -139,8 +139,8 @@ pub trait Visitor<'ast>: Sized {
             GenericArg::Const(ct) => self.visit_anon_const(ct),
         }
     }
-    fn visit_assoc_type_binding(&mut self, type_binding: &'ast TypeBinding) {
-        walk_assoc_type_binding(self, type_binding)
+    fn visit_assoc_ty_constraint(&mut self, constraint: &'ast AssocTyConstraint) {
+        walk_assoc_ty_constraint(self, constraint)
     }
     fn visit_attribute(&mut self, attr: &'ast Attribute) {
         walk_attribute(self, attr)
@@ -404,7 +404,7 @@ pub fn walk_generic_args<'a, V>(visitor: &mut V,
     match *generic_args {
         GenericArgs::AngleBracketed(ref data) => {
             walk_list!(visitor, visit_generic_arg, &data.args);
-            walk_list!(visitor, visit_assoc_type_binding, &data.bindings);
+            walk_list!(visitor, visit_assoc_ty_constraint, &data.constraints);
         }
         GenericArgs::Parenthesized(ref data) => {
             walk_list!(visitor, visit_ty, &data.inputs);
@@ -413,10 +413,17 @@ pub fn walk_generic_args<'a, V>(visitor: &mut V,
     }
 }
 
-pub fn walk_assoc_type_binding<'a, V: Visitor<'a>>(visitor: &mut V,
-                                                   type_binding: &'a TypeBinding) {
-    visitor.visit_ident(type_binding.ident);
-    visitor.visit_ty(&type_binding.ty);
+pub fn walk_assoc_ty_constraint<'a, V: Visitor<'a>>(visitor: &mut V,
+                                                    constraint: &'a AssocTyConstraint) {
+    visitor.visit_ident(constraint.ident);
+    match constraint.kind {
+        AssocTyConstraintKind::Equality { ref ty } => {
+            visitor.visit_ty(ty);
+        }
+        AssocTyConstraintKind::Bound { ref bounds } => {
+            walk_list!(visitor, visit_param_bound, bounds);
+        }
+    }
 }
 
 pub fn walk_pat<'a, V: Visitor<'a>>(visitor: &mut V, pattern: &'a Pat) {