Merge #1757

1757: Assoc type bindings r=flodiebold a=flodiebold

This adds support for type bindings (bounds like `where T: Iterator<Item = u32>`).

It doesn't yet work in as many situations as I'd like because of some [Chalk problems](https://github.com/rust-lang/chalk/issues/234). But it works in some situations, and will at least not bitrot this way ;)

(part of the problem is that we use `Normalize` to normalize associated types, but produce `ProjectionEq` goals from where clauses, so Chalk can't normalize using the environment; this would be fixed by using `ProjectionEq` for normalization, which I think is the 'proper' way, but then we'd run into those ambiguity problems everywhere...)

Co-authored-by: Florian Diebold <[email protected]>

12 files changed, 427 insertions, 158 deletions

diff --git a/crates/ra_cli/src/analysis_stats.rs b/crates/ra_cli/src/analysis_stats.rs
index 5c0a9dd98..1fad5b233 100644
--- a/crates/ra_cli/src/analysis_stats.rs
+++ b/crates/ra_cli/src/analysis_stats.rs
@@ -1,7 +1,7 @@
 use std::{collections::HashSet, fmt::Write, path::Path, time::Instant};
 
 use ra_db::SourceDatabase;
-use ra_hir::{Crate, HasBodySource, HasSource, HirDisplay, ImplItem, ModuleDef, Ty};
+use ra_hir::{Crate, HasBodySource, HasSource, HirDisplay, ImplItem, ModuleDef, Ty, TypeWalk};
 use ra_syntax::AstNode;
 
 use crate::Result;
diff --git a/crates/ra_hir/src/lib.rs b/crates/ra_hir/src/lib.rs
index 752653ad7..c3e589921 100644
--- a/crates/ra_hir/src/lib.rs
+++ b/crates/ra_hir/src/lib.rs
@@ -69,7 +69,9 @@ pub use self::{
     resolve::Resolution,
     source_binder::{PathResolution, ScopeEntryWithSyntax, SourceAnalyzer},
     source_id::{AstIdMap, ErasedFileAstId},
-    ty::{display::HirDisplay, ApplicationTy, CallableDef, Substs, TraitRef, Ty, TypeCtor},
+    ty::{
+        display::HirDisplay, ApplicationTy, CallableDef, Substs, TraitRef, Ty, TypeCtor, TypeWalk,
+    },
     type_ref::Mutability,
 };
 
diff --git a/crates/ra_hir/src/path.rs b/crates/ra_hir/src/path.rs
index 5ee71e421..24316fc91 100644
--- a/crates/ra_hir/src/path.rs
+++ b/crates/ra_hir/src/path.rs
@@ -31,7 +31,8 @@ pub struct GenericArgs {
     /// Self type. Otherwise, when we have a path `Trait<X, Y>`, the Self type
     /// is left out.
     pub has_self_type: bool,
-    // someday also bindings
+    /// Associated type bindings like in `Iterator<Item = T>`.
+    pub bindings: Vec<(Name, TypeRef)>,
 }
 
 /// A single generic argument.
@@ -170,16 +171,24 @@ impl GenericArgs {
             let type_ref = TypeRef::from_ast_opt(type_arg.type_ref());
             args.push(GenericArg::Type(type_ref));
         }
-        // lifetimes and assoc type args ignored for now
-        if !args.is_empty() {
-            Some(GenericArgs { args, has_self_type: false })
-        } else {
+        // lifetimes ignored for now
+        let mut bindings = Vec::new();
+        for assoc_type_arg in node.assoc_type_args() {
+            if let Some(name_ref) = assoc_type_arg.name_ref() {
+                let name = name_ref.as_name();
+                let type_ref = TypeRef::from_ast_opt(assoc_type_arg.type_ref());
+                bindings.push((name, type_ref));
+            }
+        }
+        if args.is_empty() && bindings.is_empty() {
             None
+        } else {
+            Some(GenericArgs { args, has_self_type: false, bindings })
         }
     }
 
     pub(crate) fn empty() -> GenericArgs {
-        GenericArgs { args: Vec::new(), has_self_type: false }
+        GenericArgs { args: Vec::new(), has_self_type: false, bindings: Vec::new() }
     }
 }
 
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index b54c80318..a3df08827 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -120,12 +120,44 @@ pub struct ProjectionTy {
     pub parameters: Substs,
 }
 
+impl ProjectionTy {
+    pub fn trait_ref(&self, db: &impl HirDatabase) -> TraitRef {
+        TraitRef {
+            trait_: self
+                .associated_ty
+                .parent_trait(db)
+                .expect("projection ty without parent trait"),
+            substs: self.parameters.clone(),
+        }
+    }
+}
+
+impl TypeWalk for ProjectionTy {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        self.parameters.walk(f);
+    }
+
+    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+        self.parameters.walk_mut(f);
+    }
+}
+
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct UnselectedProjectionTy {
     pub type_name: Name,
     pub parameters: Substs,
 }
 
+impl TypeWalk for UnselectedProjectionTy {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        self.parameters.walk(f);
+    }
+
+    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+        self.parameters.walk_mut(f);
+    }
+}
+
 /// A type.
 ///
 /// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents
@@ -282,20 +314,14 @@ impl TraitRef {
     pub fn self_ty(&self) -> &Ty {
         &self.substs[0]
     }
+}
 
-    pub fn subst(mut self, substs: &Substs) -> TraitRef {
-        self.substs.walk_mut(&mut |ty_mut| {
-            let ty = mem::replace(ty_mut, Ty::Unknown);
-            *ty_mut = ty.subst(substs);
-        });
-        self
-    }
-
-    pub fn walk(&self, f: &mut impl FnMut(&Ty)) {
+impl TypeWalk for TraitRef {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
         self.substs.walk(f);
     }
 
-    pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
         self.substs.walk_mut(f);
     }
 }
@@ -306,6 +332,8 @@ impl TraitRef {
 pub enum GenericPredicate {
     /// The given trait needs to be implemented for its type parameters.
     Implemented(TraitRef),
+    /// An associated type bindings like in `Iterator<Item = T>`.
+    Projection(ProjectionPredicate),
     /// We couldn't resolve the trait reference. (If some type parameters can't
     /// be resolved, they will just be Unknown).
     Error,
@@ -319,25 +347,35 @@ impl GenericPredicate {
         }
     }
 
-    pub fn subst(self, substs: &Substs) -> GenericPredicate {
+    pub fn is_implemented(&self) -> bool {
         match self {
-            GenericPredicate::Implemented(trait_ref) => {
-                GenericPredicate::Implemented(trait_ref.subst(substs))
-            }
-            GenericPredicate::Error => self,
+            GenericPredicate::Implemented(_) => true,
+            _ => false,
         }
     }
 
-    pub fn walk(&self, f: &mut impl FnMut(&Ty)) {
+    pub fn trait_ref(&self, db: &impl HirDatabase) -> Option<TraitRef> {
+        match self {
+            GenericPredicate::Implemented(tr) => Some(tr.clone()),
+            GenericPredicate::Projection(proj) => Some(proj.projection_ty.trait_ref(db)),
+            GenericPredicate::Error => None,
+        }
+    }
+}
+
+impl TypeWalk for GenericPredicate {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
         match self {
             GenericPredicate::Implemented(trait_ref) => trait_ref.walk(f),
+            GenericPredicate::Projection(projection_pred) => projection_pred.walk(f),
             GenericPredicate::Error => {}
         }
     }
 
-    pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
         match self {
             GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut(f),
+            GenericPredicate::Projection(projection_pred) => projection_pred.walk_mut(f),
             GenericPredicate::Error => {}
         }
     }
@@ -378,16 +416,16 @@ impl FnSig {
     pub fn ret(&self) -> &Ty {
         &self.params_and_return[self.params_and_return.len() - 1]
     }
+}
 
-    /// Applies the given substitutions to all types in this signature and
-    /// returns the result.
-    pub fn subst(&self, substs: &Substs) -> FnSig {
-        let result: Vec<_> =
-            self.params_and_return.iter().map(|ty| ty.clone().subst(substs)).collect();
-        FnSig { params_and_return: result.into() }
+impl TypeWalk for FnSig {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        for t in self.params_and_return.iter() {
+            t.walk(f);
+        }
     }
 
-    pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
         // Without an Arc::make_mut_slice, we can't avoid the clone here:
         let mut v: Vec<_> = self.params_and_return.iter().cloned().collect();
         for t in &mut v {
@@ -411,64 +449,6 @@ impl Ty {
         Ty::apply(TypeCtor::Tuple { cardinality: 0 }, Substs::empty())
     }
 
-    pub fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        match self {
-            Ty::Apply(a_ty) => {
-                for t in a_ty.parameters.iter() {
-                    t.walk(f);
-                }
-            }
-            Ty::Projection(p_ty) => {
-                for t in p_ty.parameters.iter() {
-                    t.walk(f);
-                }
-            }
-            Ty::UnselectedProjection(p_ty) => {
-                for t in p_ty.parameters.iter() {
-                    t.walk(f);
-                }
-            }
-            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
-                for p in predicates.iter() {
-                    p.walk(f);
-                }
-            }
-            Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
-        }
-        f(self);
-    }
-
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
-        match self {
-            Ty::Apply(a_ty) => {
-                a_ty.parameters.walk_mut(f);
-            }
-            Ty::Projection(p_ty) => {
-                p_ty.parameters.walk_mut(f);
-            }
-            Ty::UnselectedProjection(p_ty) => {
-                p_ty.parameters.walk_mut(f);
-            }
-            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
-                let mut v: Vec<_> = predicates.iter().cloned().collect();
-                for p in &mut v {
-                    p.walk_mut(f);
-                }
-                *predicates = v.into();
-            }
-            Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
-        }
-        f(self);
-    }
-
-    fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Ty {
-        self.walk_mut(&mut |ty_mut| {
-            let ty = mem::replace(ty_mut, Ty::Unknown);
-            *ty_mut = f(ty);
-        });
-        self
-    }
-
     pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
         match self {
             Ty::Apply(ApplicationTy { ctor: TypeCtor::Ref(mutability), parameters }) => {
@@ -544,10 +524,53 @@ impl Ty {
         }
     }
 
+    /// Returns the type parameters of this type if it has some (i.e. is an ADT
+    /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
+    pub fn substs(&self) -> Option<Substs> {
+        match self {
+            Ty::Apply(ApplicationTy { parameters, .. }) => Some(parameters.clone()),
+            _ => None,
+        }
+    }
+
+    /// If this is an `impl Trait` or `dyn Trait`, returns that trait.
+    pub fn inherent_trait(&self) -> Option<Trait> {
+        match self {
+            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
+                predicates.iter().find_map(|pred| match pred {
+                    GenericPredicate::Implemented(tr) => Some(tr.trait_),
+                    _ => None,
+                })
+            }
+            _ => None,
+        }
+    }
+}
+
+/// This allows walking structures that contain types to do something with those
+/// types, similar to Chalk's `Fold` trait.
+pub trait TypeWalk {
+    fn walk(&self, f: &mut impl FnMut(&Ty));
+    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty));
+
+    fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self
+    where
+        Self: Sized,
+    {
+        self.walk_mut(&mut |ty_mut| {
+            let ty = mem::replace(ty_mut, Ty::Unknown);
+            *ty_mut = f(ty);
+        });
+        self
+    }
+
     /// Replaces type parameters in this type using the given `Substs`. (So e.g.
     /// if `self` is `&[T]`, where type parameter T has index 0, and the
     /// `Substs` contain `u32` at index 0, we'll have `&[u32]` afterwards.)
-    pub fn subst(self, substs: &Substs) -> Ty {
+    fn subst(self, substs: &Substs) -> Self
+    where
+        Self: Sized,
+    {
         self.fold(&mut |ty| match ty {
             Ty::Param { idx, name } => {
                 substs.get(idx as usize).cloned().unwrap_or(Ty::Param { idx, name })
@@ -557,24 +580,21 @@ impl Ty {
     }
 
     /// Substitutes `Ty::Bound` vars (as opposed to type parameters).
-    pub fn subst_bound_vars(self, substs: &Substs) -> Ty {
+    fn subst_bound_vars(self, substs: &Substs) -> Self
+    where
+        Self: Sized,
+    {
         self.fold(&mut |ty| match ty {
             Ty::Bound(idx) => substs.get(idx as usize).cloned().unwrap_or_else(|| Ty::Bound(idx)),
             ty => ty,
         })
     }
 
-    /// Returns the type parameters of this type if it has some (i.e. is an ADT
-    /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
-    pub fn substs(&self) -> Option<Substs> {
-        match self {
-            Ty::Apply(ApplicationTy { parameters, .. }) => Some(parameters.clone()),
-            _ => None,
-        }
-    }
-
     /// Shifts up `Ty::Bound` vars by `n`.
-    pub fn shift_bound_vars(self, n: i32) -> Ty {
+    fn shift_bound_vars(self, n: i32) -> Self
+    where
+        Self: Sized,
+    {
         self.fold(&mut |ty| match ty {
             Ty::Bound(idx) => {
                 assert!(idx as i32 >= -n);
@@ -583,18 +603,57 @@ impl Ty {
             ty => ty,
         })
     }
+}
 
-    /// If this is an `impl Trait` or `dyn Trait`, returns that trait.
-    pub fn inherent_trait(&self) -> Option<Trait> {
+impl TypeWalk for Ty {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        match self {
+            Ty::Apply(a_ty) => {
+                for t in a_ty.parameters.iter() {
+                    t.walk(f);
+                }
+            }
+            Ty::Projection(p_ty) => {
+                for t in p_ty.parameters.iter() {
+                    t.walk(f);
+                }
+            }
+            Ty::UnselectedProjection(p_ty) => {
+                for t in p_ty.parameters.iter() {
+                    t.walk(f);
+                }
+            }
+            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
+                for p in predicates.iter() {
+                    p.walk(f);
+                }
+            }
+            Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
+        }
+        f(self);
+    }
+
+    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
         match self {
+            Ty::Apply(a_ty) => {
+                a_ty.parameters.walk_mut(f);
+            }
+            Ty::Projection(p_ty) => {
+                p_ty.parameters.walk_mut(f);
+            }
+            Ty::UnselectedProjection(p_ty) => {
+                p_ty.parameters.walk_mut(f);
+            }
             Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
-                predicates.iter().find_map(|pred| match pred {
-                    GenericPredicate::Implemented(tr) => Some(tr.trait_),
-                    _ => None,
-                })
+                let mut v: Vec<_> = predicates.iter().cloned().collect();
+                for p in &mut v {
+                    p.walk_mut(f);
+                }
+                *predicates = v.into();
             }
-            _ => None,
+            Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
         }
+        f(self);
     }
 }
 
@@ -742,20 +801,66 @@ impl HirDisplay for Ty {
                     Ty::Opaque(_) => write!(f, "impl ")?,
                     _ => unreachable!(),
                 };
-                // looping by hand here just to format the bounds in a slightly nicer way
+                // Note: This code is written to produce nice results (i.e.
+                // corresponding to surface Rust) for types that can occur in
+                // actual Rust. It will have weird results if the predicates
+                // aren't as expected (i.e. self types = $0, projection
+                // predicates for a certain trait come after the Implemented
+                // predicate for that trait).
                 let mut first = true;
+                let mut angle_open = false;
                 for p in predicates.iter() {
-                    if !first {
-                        write!(f, " + ")?;
-                    }
-                    first = false;
                     match p {
-                        // don't show the $0 self type
                         GenericPredicate::Implemented(trait_ref) => {
-                            trait_ref.hir_fmt_ext(f, false)?
+                            if angle_open {
+                                write!(f, ">")?;
+                            }
+                            if !first {
+                                write!(f, " + ")?;
+                            }
+                            // We assume that the self type is $0 (i.e. the
+                            // existential) here, which is the only thing that's
+                            // possible in actual Rust, and hence don't print it
+                            write!(
+                                f,
+                                "{}",
+                                trait_ref.trait_.name(f.db).unwrap_or_else(Name::missing)
+                            )?;
+                            if trait_ref.substs.len() > 1 {
+                                write!(f, "<")?;
+                                f.write_joined(&trait_ref.substs[1..], ", ")?;
+                                // there might be assoc type bindings, so we leave the angle brackets open
+                                angle_open = true;
+                            }
+                        }
+                        GenericPredicate::Projection(projection_pred) => {
+                            // in types in actual Rust, these will always come
+                            // after the corresponding Implemented predicate
+                            if angle_open {
+                                write!(f, ", ")?;
+                            } else {
+                                write!(f, "<")?;
+                                angle_open = true;
+                            }
+                            let name = projection_pred.projection_ty.associated_ty.name(f.db);
+                            write!(f, "{} = ", name)?;
+                            projection_pred.ty.hir_fmt(f)?;
+                        }
+                        GenericPredicate::Error => {
+                            if angle_open {
+                                // impl Trait<X, {error}>
+                                write!(f, ", ")?;
+                            } else if !first {
+                                // impl Trait + {error}
+                                write!(f, " + ")?;
+                            }
+                            p.hir_fmt(f)?;
                         }
-                        GenericPredicate::Error => p.hir_fmt(f)?,
                     }
+                    first = false;
+                }
+                if angle_open {
+                    write!(f, ">")?;
                 }
             }
             Ty::Unknown => write!(f, "{{unknown}}")?,
@@ -766,13 +871,12 @@ impl HirDisplay for Ty {
 }
 
 impl TraitRef {
-    fn hir_fmt_ext(
-        &self,
-        f: &mut HirFormatter<impl HirDatabase>,
-        with_self_ty: bool,
-    ) -> fmt::Result {
-        if with_self_ty {
-            write!(f, "{}: ", self.substs[0].display(f.db),)?;
+    fn hir_fmt_ext(&self, f: &mut HirFormatter<impl HirDatabase>, use_as: bool) -> fmt::Result {
+        self.substs[0].hir_fmt(f)?;
+        if use_as {
+            write!(f, " as ")?;
+        } else {
+            write!(f, ": ")?;
         }
         write!(f, "{}", self.trait_.name(f.db).unwrap_or_else(Name::missing))?;
         if self.substs.len() > 1 {
@@ -786,7 +890,7 @@ impl TraitRef {
 
 impl HirDisplay for TraitRef {
     fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
-        self.hir_fmt_ext(f, true)
+        self.hir_fmt_ext(f, false)
     }
 }
 
@@ -800,6 +904,16 @@ impl HirDisplay for GenericPredicate {
     fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
         match self {
             GenericPredicate::Implemented(trait_ref) => trait_ref.hir_fmt(f)?,
+            GenericPredicate::Projection(projection_pred) => {
+                write!(f, "<")?;
+                projection_pred.projection_ty.trait_ref(f.db).hir_fmt_ext(f, true)?;
+                write!(
+                    f,
+                    ">::{} = {}",
+                    projection_pred.projection_ty.associated_ty.name(f.db),
+                    projection_pred.ty.display(f.db)
+                )?;
+            }
             GenericPredicate::Error => write!(f, "{{error}}")?,
         }
         Ok(())
diff --git a/crates/ra_hir/src/ty/autoderef.rs b/crates/ra_hir/src/ty/autoderef.rs
index 2535d4ae7..08f52a53b 100644
--- a/crates/ra_hir/src/ty/autoderef.rs
+++ b/crates/ra_hir/src/ty/autoderef.rs
@@ -7,7 +7,7 @@ use std::iter::successors;
 
 use log::{info, warn};
 
-use super::{traits::Solution, Canonical, Ty};
+use super::{traits::Solution, Canonical, Ty, TypeWalk};
 use crate::{HasGenericParams, HirDatabase, Name, Resolver};
 
 const AUTODEREF_RECURSION_LIMIT: usize = 10;
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index b89a40b4b..ec3b7ffef 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -30,7 +30,7 @@ use super::{
     autoderef, lower, method_resolution, op, primitive,
     traits::{Guidance, Obligation, ProjectionPredicate, Solution},
     ApplicationTy, CallableDef, InEnvironment, ProjectionTy, Substs, TraitEnvironment, TraitRef,
-    Ty, TypableDef, TypeCtor,
+    Ty, TypableDef, TypeCtor, TypeWalk,
 };
 use crate::{
     adt::VariantDef,
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs
index e7e8825d1..9a0d2d8f9 100644
--- a/crates/ra_hir/src/ty/infer/unify.rs
+++ b/crates/ra_hir/src/ty/infer/unify.rs
@@ -3,7 +3,7 @@
 use super::{InferenceContext, Obligation};
 use crate::db::HirDatabase;
 use crate::ty::{
-    Canonical, InEnvironment, InferTy, ProjectionPredicate, ProjectionTy, TraitRef, Ty,
+    Canonical, InEnvironment, InferTy, ProjectionPredicate, ProjectionTy, TraitRef, Ty, TypeWalk,
 };
 
 impl<'a, D: HirDatabase> InferenceContext<'a, D> {
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 47d161277..f6f0137cf 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -8,7 +8,10 @@
 use std::iter;
 use std::sync::Arc;
 
-use super::{FnSig, GenericPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor};
+use super::{
+    FnSig, GenericPredicate, ProjectionPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor,
+    TypeWalk,
+};
 use crate::{
     adt::VariantDef,
     generics::HasGenericParams,
@@ -62,7 +65,9 @@ impl Ty {
                 let self_ty = Ty::Bound(0);
                 let predicates = bounds
                     .iter()
-                    .map(|b| GenericPredicate::from_type_bound(db, resolver, b, self_ty.clone()))
+                    .flat_map(|b| {
+                        GenericPredicate::from_type_bound(db, resolver, b, self_ty.clone())
+                    })
                     .collect::<Vec<_>>();
                 Ty::Dyn(predicates.into())
             }
@@ -70,7 +75,9 @@ impl Ty {
                 let self_ty = Ty::Bound(0);
                 let predicates = bounds
                     .iter()
-                    .map(|b| GenericPredicate::from_type_bound(db, resolver, b, self_ty.clone()))
+                    .flat_map(|b| {
+                        GenericPredicate::from_type_bound(db, resolver, b, self_ty.clone())
+                    })
                     .collect::<Vec<_>>();
                 Ty::Opaque(predicates.into())
             }
@@ -326,15 +333,6 @@ impl TraitRef {
         TraitRef { trait_, substs }
     }
 
-    pub(crate) fn from_where_predicate(
-        db: &impl HirDatabase,
-        resolver: &Resolver,
-        pred: &WherePredicate,
-    ) -> Option<TraitRef> {
-        let self_ty = Ty::from_hir(db, resolver, &pred.type_ref);
-        TraitRef::from_type_bound(db, resolver, &pred.bound, self_ty)
-    }
-
     pub(crate) fn from_type_bound(
         db: &impl HirDatabase,
         resolver: &Resolver,
@@ -349,26 +347,58 @@ impl TraitRef {
 }
 
 impl GenericPredicate {
-    pub(crate) fn from_where_predicate(
-        db: &impl HirDatabase,
-        resolver: &Resolver,
-        where_predicate: &WherePredicate,
-    ) -> GenericPredicate {
-        TraitRef::from_where_predicate(db, &resolver, where_predicate)
-            .map_or(GenericPredicate::Error, GenericPredicate::Implemented)
+    pub(crate) fn from_where_predicate<'a>(
+        db: &'a impl HirDatabase,
+        resolver: &'a Resolver,
+        where_predicate: &'a WherePredicate,
+    ) -> impl Iterator<Item = GenericPredicate> + 'a {
+        let self_ty = Ty::from_hir(db, resolver, &where_predicate.type_ref);
+        GenericPredicate::from_type_bound(db, resolver, &where_predicate.bound, self_ty)
     }
 
-    pub(crate) fn from_type_bound(
-        db: &impl HirDatabase,
-        resolver: &Resolver,
-        bound: &TypeBound,
+    pub(crate) fn from_type_bound<'a>(
+        db: &'a impl HirDatabase,
+        resolver: &'a Resolver,
+        bound: &'a TypeBound,
         self_ty: Ty,
-    ) -> GenericPredicate {
-        TraitRef::from_type_bound(db, &resolver, bound, self_ty)
-            .map_or(GenericPredicate::Error, GenericPredicate::Implemented)
+    ) -> impl Iterator<Item = GenericPredicate> + 'a {
+        let trait_ref = TraitRef::from_type_bound(db, &resolver, bound, self_ty);
+        iter::once(trait_ref.clone().map_or(GenericPredicate::Error, GenericPredicate::Implemented))
+            .chain(
+                trait_ref.into_iter().flat_map(move |tr| {
+                    assoc_type_bindings_from_type_bound(db, resolver, bound, tr)
+                }),
+            )
     }
 }
 
+fn assoc_type_bindings_from_type_bound<'a>(
+    db: &'a impl HirDatabase,
+    resolver: &'a Resolver,
+    bound: &'a TypeBound,
+    trait_ref: TraitRef,
+) -> impl Iterator<Item = GenericPredicate> + 'a {
+    let last_segment = match bound {
+        TypeBound::Path(path) => path.segments.last(),
+        TypeBound::Error => None,
+    };
+    last_segment
+        .into_iter()
+        .flat_map(|segment| segment.args_and_bindings.iter())
+        .flat_map(|args_and_bindings| args_and_bindings.bindings.iter())
+        .map(move |(name, type_ref)| {
+            let associated_ty = match trait_ref.trait_.associated_type_by_name(db, name.clone()) {
+                None => return GenericPredicate::Error,
+                Some(t) => t,
+            };
+            let projection_ty =
+                ProjectionTy { associated_ty, parameters: trait_ref.substs.clone() };
+            let ty = Ty::from_hir(db, resolver, type_ref);
+            let projection_predicate = ProjectionPredicate { projection_ty, ty };
+            GenericPredicate::Projection(projection_predicate)
+        })
+}
+
 /// Build the declared type of an item. This depends on the namespace; e.g. for
 /// `struct Foo(usize)`, we have two types: The type of the struct itself, and
 /// the constructor function `(usize) -> Foo` which lives in the values
@@ -425,7 +455,7 @@ pub(crate) fn trait_env(
 ) -> Arc<super::TraitEnvironment> {
     let predicates = resolver
         .where_predicates_in_scope()
-        .map(|pred| GenericPredicate::from_where_predicate(db, &resolver, pred))
+        .flat_map(|pred| GenericPredicate::from_where_predicate(db, &resolver, pred))
         .collect::<Vec<_>>();
 
     Arc::new(super::TraitEnvironment { predicates })
@@ -439,7 +469,7 @@ pub(crate) fn generic_predicates_query(
     let resolver = def.resolver(db);
     let predicates = resolver
         .where_predicates_in_scope()
-        .map(|pred| GenericPredicate::from_where_predicate(db, &resolver, pred))
+        .flat_map(|pred| GenericPredicate::from_where_predicate(db, &resolver, pred))
         .collect::<Vec<_>>();
     predicates.into()
 }
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index cde9801f6..d92d4659b 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -3552,6 +3552,97 @@ fn test() {
     );
 }
 
+#[test]
+fn assoc_type_bindings() {
+    assert_snapshot!(
+        infer(r#"
+trait Trait {
+    type Type;
+}
+
+fn get<T: Trait>(t: T) -> <T as Trait>::Type {}
+fn get2<U, T: Trait<Type = U>>(t: T) -> U {}
+fn set<T: Trait<Type = u64>>(t: T) -> T {t}
+
+struct S<T>;
+impl<T> Trait for S<T> { type Type = T; }
+
+fn test<T: Trait<Type = u32>>(x: T, y: impl Trait<Type = i64>) {
+    get(x);
+    get2(x);
+    get(y);
+    get2(y);
+    get(set(S));
+    get2(set(S));
+    get2(S::<str>);
+}
+"#),
+        @r###"
+    [50; 51) 't': T
+    [78; 80) '{}': ()
+    [112; 113) 't': T
+    [123; 125) '{}': ()
+    [155; 156) 't': T
+    [166; 169) '{t}': T
+    [167; 168) 't': T
+    [257; 258) 'x': T
+    [263; 264) 'y': impl Trait<Type = i64>
+    [290; 398) '{     ...r>); }': ()
+    [296; 299) 'get': fn get<T>(T) -> <T as Trait>::Type
+    [296; 302) 'get(x)': {unknown}
+    [300; 301) 'x': T
+    [308; 312) 'get2': fn get2<{unknown}, S<{unknown}>>(T) -> U
+    [308; 315) 'get2(x)': {unknown}
+    [313; 314) 'x': T
+    [321; 324) 'get': fn get<impl Trait<Type = i64>>(T) -> <T as Trait>::Type
+    [321; 327) 'get(y)': {unknown}
+    [325; 326) 'y': impl Trait<Type = i64>
+    [333; 337) 'get2': fn get2<{unknown}, S<{unknown}>>(T) -> U
+    [333; 340) 'get2(y)': {unknown}
+    [338; 339) 'y': impl Trait<Type = i64>
+    [346; 349) 'get': fn get<S<u64>>(T) -> <T as Trait>::Type
+    [346; 357) 'get(set(S))': u64
+    [350; 353) 'set': fn set<S<u64>>(T) -> T
+    [350; 356) 'set(S)': S<u64>
+    [354; 355) 'S': S<u64>
+    [363; 367) 'get2': fn get2<u64, S<u64>>(T) -> U
+    [363; 375) 'get2(set(S))': u64
+    [368; 371) 'set': fn set<S<u64>>(T) -> T
+    [368; 374) 'set(S)': S<u64>
+    [372; 373) 'S': S<u64>
+    [381; 385) 'get2': fn get2<str, S<str>>(T) -> U
+    [381; 395) 'get2(S::<str>)': str
+    [386; 394) 'S::<str>': S<str>
+    "###
+    );
+}
+
+#[test]
+fn projection_eq_within_chalk() {
+    // std::env::set_var("CHALK_DEBUG", "1");
+    assert_snapshot!(
+        infer(r#"
+trait Trait1 {
+    type Type;
+}
+trait Trait2<T> {
+    fn foo(self) -> T;
+}
+impl<T, U> Trait2<T> for U where U: Trait1<Type = T> {}
+
+fn test<T: Trait1<Type = u32>>(x: T) {
+    x.foo();
+}
+"#),
+        @r###"
+    [62; 66) 'self': Self
+    [164; 165) 'x': T
+    [170; 186) '{     ...o(); }': ()
+    [176; 177) 'x': T
+    [176; 183) 'x.foo()': {unknown}
+    "###
+    );
+}
 fn type_at_pos(db: &MockDatabase, pos: FilePosition) -> String {
     let file = db.parse(pos.file_id).ok().unwrap();
     let expr = algo::find_node_at_offset::<ast::Expr>(file.syntax(), pos.offset).unwrap();
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index b634f0b79..6e0271a96 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -8,7 +8,7 @@ use ra_db::salsa;
 use ra_prof::profile;
 use rustc_hash::FxHashSet;
 
-use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty};
+use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk};
 use crate::{db::HirDatabase, Crate, ImplBlock, Trait};
 
 use self::chalk::{from_chalk, ToChalk};
@@ -124,6 +124,9 @@ impl Obligation {
     pub fn from_predicate(predicate: GenericPredicate) -> Option<Obligation> {
         match predicate {
             GenericPredicate::Implemented(trait_ref) => Some(Obligation::Trait(trait_ref)),
+            GenericPredicate::Projection(projection_pred) => {
+                Some(Obligation::Projection(projection_pred))
+            }
             GenericPredicate::Error => None,
         }
     }
@@ -135,6 +138,18 @@ pub struct ProjectionPredicate {
     pub ty: Ty,
 }
 
+impl TypeWalk for ProjectionPredicate {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        self.projection_ty.walk(f);
+        self.ty.walk(f);
+    }
+
+    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+        self.projection_ty.walk_mut(f);
+        self.ty.walk_mut(f);
+    }
+}
+
 /// Solve a trait goal using Chalk.
 pub(crate) fn trait_solve_query(
     db: &impl HirDatabase,
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
index 2ebc06135..c201c5e50 100644
--- a/crates/ra_hir/src/ty/traits/chalk.rs
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -19,6 +19,7 @@ use crate::{
     ty::display::HirDisplay,
     ty::{
         ApplicationTy, CallableDef, GenericPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor,
+        TypeWalk,
     },
     Crate, HasGenericParams, ImplBlock, ImplItem, Trait, TypeAlias,
 };
@@ -211,6 +212,13 @@ impl ToChalk for GenericPredicate {
             GenericPredicate::Implemented(trait_ref) => {
                 make_binders(chalk_ir::WhereClause::Implemented(trait_ref.to_chalk(db)), 0)
             }
+            GenericPredicate::Projection(projection_pred) => make_binders(
+                chalk_ir::WhereClause::ProjectionEq(chalk_ir::ProjectionEq {
+                    projection: projection_pred.projection_ty.to_chalk(db),
+                    ty: projection_pred.ty.to_chalk(db),
+                }),
+                0,
+            ),
             GenericPredicate::Error => {
                 let impossible_trait_ref = chalk_ir::TraitRef {
                     trait_id: UNKNOWN_TRAIT,
diff --git a/crates/ra_ide_api/src/completion/presentation.rs b/crates/ra_ide_api/src/completion/presentation.rs
index f19eec9b7..db7e8348e 100644
--- a/crates/ra_ide_api/src/completion/presentation.rs
+++ b/crates/ra_ide_api/src/completion/presentation.rs
@@ -1,5 +1,5 @@
 //! This modules takes care of rendering various defenitions as completion items.
-use hir::{Docs, HasSource, HirDisplay, PerNs, Resolution, Ty};
+use hir::{Docs, HasSource, HirDisplay, PerNs, Resolution, Ty, TypeWalk};
 use join_to_string::join;
 use ra_syntax::ast::NameOwner;
 use test_utils::tested_by;