8 files changed, 370 insertions, 186 deletions

diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index 276b0774f..d75d71d66 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -13,8 +13,10 @@ use crate::{
     lang_item::{LangItemTarget, LangItems},
     traits::TraitData,
     ty::{
-        method_resolution::CrateImplBlocks, traits::Impl, CallableDef, FnSig, GenericPredicate,
-        InferenceResult, Namespace, Substs, Ty, TypableDef, TypeCtor,
+        method_resolution::CrateImplBlocks,
+        traits::{AssocTyValue, Impl},
+        CallableDef, FnSig, GenericPredicate, InferenceResult, Namespace, Substs, Ty, TypableDef,
+        TypeCtor,
     },
     type_alias::TypeAliasData,
     Const, ConstData, Crate, DefWithBody, FnData, Function, ImplBlock, Module, Static, StructField,
@@ -119,26 +121,42 @@ pub trait HirDatabase: DefDatabase + AstDatabase {
     fn intern_type_ctor(&self, type_ctor: TypeCtor) -> ids::TypeCtorId;
     #[salsa::interned]
     fn intern_chalk_impl(&self, impl_: Impl) -> ids::GlobalImplId;
+    #[salsa::interned]
+    fn intern_assoc_ty_value(&self, assoc_ty_value: AssocTyValue) -> ids::AssocTyValueId;
 
     #[salsa::invoke(crate::ty::traits::chalk::associated_ty_data_query)]
-    fn associated_ty_data(&self, id: chalk_ir::TypeId) -> Arc<chalk_rust_ir::AssociatedTyDatum>;
+    fn associated_ty_data(
+        &self,
+        id: chalk_ir::TypeId,
+    ) -> Arc<chalk_rust_ir::AssociatedTyDatum<chalk_ir::family::ChalkIr>>;
 
     #[salsa::invoke(crate::ty::traits::chalk::trait_datum_query)]
     fn trait_datum(
         &self,
         krate: Crate,
         trait_id: chalk_ir::TraitId,
-    ) -> Arc<chalk_rust_ir::TraitDatum>;
+    ) -> Arc<chalk_rust_ir::TraitDatum<chalk_ir::family::ChalkIr>>;
 
     #[salsa::invoke(crate::ty::traits::chalk::struct_datum_query)]
     fn struct_datum(
         &self,
         krate: Crate,
         struct_id: chalk_ir::StructId,
-    ) -> Arc<chalk_rust_ir::StructDatum>;
+    ) -> Arc<chalk_rust_ir::StructDatum<chalk_ir::family::ChalkIr>>;
 
     #[salsa::invoke(crate::ty::traits::chalk::impl_datum_query)]
-    fn impl_datum(&self, krate: Crate, impl_id: chalk_ir::ImplId) -> Arc<chalk_rust_ir::ImplDatum>;
+    fn impl_datum(
+        &self,
+        krate: Crate,
+        impl_id: chalk_ir::ImplId,
+    ) -> Arc<chalk_rust_ir::ImplDatum<chalk_ir::family::ChalkIr>>;
+
+    #[salsa::invoke(crate::ty::traits::chalk::associated_ty_value_query)]
+    fn associated_ty_value(
+        &self,
+        krate: Crate,
+        id: chalk_rust_ir::AssociatedTyValueId,
+    ) -> Arc<chalk_rust_ir::AssociatedTyValue<chalk_ir::family::ChalkIr>>;
 
     #[salsa::invoke(crate::ty::traits::trait_solve_query)]
     fn trait_solve(
diff --git a/crates/ra_hir/src/ids.rs b/crates/ra_hir/src/ids.rs
index fe083c0c6..2b59365fb 100644
--- a/crates/ra_hir/src/ids.rs
+++ b/crates/ra_hir/src/ids.rs
@@ -37,3 +37,9 @@ impl_intern_key!(TypeCtorId);
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct GlobalImplId(salsa::InternId);
 impl_intern_key!(GlobalImplId);
+
+/// This exists just for Chalk, because it needs a unique ID for each associated
+/// type value in an impl (even synthetic ones).
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub struct AssocTyValueId(salsa::InternId);
+impl_intern_key!(AssocTyValueId);
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index ff6030ac4..a54135188 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -224,8 +224,8 @@ impl TypeWalk for ProjectionTy {
         self.parameters.walk(f);
     }
 
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
-        self.parameters.walk_mut(f);
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+        self.parameters.walk_mut_binders(f, binders);
     }
 }
 
@@ -291,6 +291,20 @@ pub enum Ty {
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct Substs(Arc<[Ty]>);
 
+impl TypeWalk for Substs {
+    fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        for t in self.0.iter() {
+            t.walk(f);
+        }
+    }
+
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+        for t in make_mut_slice(&mut self.0) {
+            t.walk_mut_binders(f, binders);
+        }
+    }
+}
+
 impl Substs {
     pub fn empty() -> Substs {
         Substs(Arc::new([]))
@@ -304,18 +318,6 @@ impl Substs {
         Substs(self.0[..std::cmp::min(self.0.len(), n)].into())
     }
 
-    pub fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        for t in self.0.iter() {
-            t.walk(f);
-        }
-    }
-
-    pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
-        for t in make_mut_slice(&mut self.0) {
-            t.walk_mut(f);
-        }
-    }
-
     pub fn as_single(&self) -> &Ty {
         if self.0.len() != 1 {
             panic!("expected substs of len 1, got {:?}", self);
@@ -440,8 +442,8 @@ impl TypeWalk for TraitRef {
         self.substs.walk(f);
     }
 
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
-        self.substs.walk_mut(f);
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+        self.substs.walk_mut_binders(f, binders);
     }
 }
 
@@ -491,10 +493,12 @@ impl TypeWalk for GenericPredicate {
         }
     }
 
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
         match self {
-            GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut(f),
-            GenericPredicate::Projection(projection_pred) => projection_pred.walk_mut(f),
+            GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders),
+            GenericPredicate::Projection(projection_pred) => {
+                projection_pred.walk_mut_binders(f, binders)
+            }
             GenericPredicate::Error => {}
         }
     }
@@ -544,9 +548,9 @@ impl TypeWalk for FnSig {
         }
     }
 
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
         for t in make_mut_slice(&mut self.params_and_return) {
-            t.walk_mut(f);
+            t.walk_mut_binders(f, binders);
         }
     }
 }
@@ -671,7 +675,20 @@ impl Ty {
 /// 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 walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+        self.walk_mut_binders(&mut |ty, _binders| f(ty), 0);
+    }
+    /// Walk the type, counting entered binders.
+    ///
+    /// `Ty::Bound` variables use DeBruijn indexing, which means that 0 refers
+    /// to the innermost binder, 1 to the next, etc.. So when we want to
+    /// substitute a certain bound variable, we can't just walk the whole type
+    /// and blindly replace each instance of a certain index; when we 'enter'
+    /// things that introduce new bound variables, we have to keep track of
+    /// that. Currently, the only thing that introduces bound variables on our
+    /// side are `Ty::Dyn` and `Ty::Opaque`, which each introduce a bound
+    /// variable for the self type.
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize);
 
     fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self
     where
@@ -700,14 +717,22 @@ pub trait TypeWalk {
     }
 
     /// Substitutes `Ty::Bound` vars (as opposed to type parameters).
-    fn subst_bound_vars(self, substs: &Substs) -> Self
+    fn subst_bound_vars(mut 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,
-        })
+        self.walk_mut_binders(
+            &mut |ty, binders| match ty {
+                &mut Ty::Bound(idx) => {
+                    if idx as usize >= binders && (idx as usize - binders) < substs.len() {
+                        *ty = substs.0[idx as usize - binders].clone();
+                    }
+                }
+                _ => {}
+            },
+            0,
+        );
+        self
     }
 
     /// Shifts up `Ty::Bound` vars by `n`.
@@ -748,22 +773,22 @@ impl TypeWalk for Ty {
         f(self);
     }
 
-    fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
         match self {
             Ty::Apply(a_ty) => {
-                a_ty.parameters.walk_mut(f);
+                a_ty.parameters.walk_mut_binders(f, binders);
             }
             Ty::Projection(p_ty) => {
-                p_ty.parameters.walk_mut(f);
+                p_ty.parameters.walk_mut_binders(f, binders);
             }
             Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
                 for p in make_mut_slice(predicates) {
-                    p.walk_mut(f);
+                    p.walk_mut_binders(f, binders + 1);
                 }
             }
             Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
         }
-        f(self);
+        f(self, binders);
     }
 }
 
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs
index ca33cc7f8..64d9394cf 100644
--- a/crates/ra_hir/src/ty/infer/unify.rs
+++ b/crates/ra_hir/src/ty/infer/unify.rs
@@ -134,17 +134,19 @@ where
 }
 
 impl<T> Canonicalized<T> {
-    pub fn decanonicalize_ty(&self, ty: Ty) -> Ty {
-        ty.fold(&mut |ty| match ty {
-            Ty::Bound(idx) => {
-                if (idx as usize) < self.free_vars.len() {
-                    Ty::Infer(self.free_vars[idx as usize])
-                } else {
-                    Ty::Bound(idx)
+    pub fn decanonicalize_ty(&self, mut ty: Ty) -> Ty {
+        ty.walk_mut_binders(
+            &mut |ty, binders| match ty {
+                &mut Ty::Bound(idx) => {
+                    if idx as usize >= binders && (idx as usize - binders) < self.free_vars.len() {
+                        *ty = Ty::Infer(self.free_vars[idx as usize - binders]);
+                    }
                 }
-            }
-            ty => ty,
-        })
+                _ => {}
+            },
+            0,
+        );
+        ty
     }
 
     pub fn apply_solution(
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index 9aad2d3fe..d20aeaacf 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -228,14 +228,10 @@ fn iterate_trait_method_candidates<T>(
     'traits: for t in traits {
         let data = t.trait_data(db);
 
-        // FIXME this is a bit of a hack, since Chalk should say the same thing
-        // anyway, but currently Chalk doesn't implement `dyn/impl Trait` yet
-        let inherently_implemented = ty.value.inherent_trait() == Some(t);
-
         // we'll be lazy about checking whether the type implements the
         // trait, but if we find out it doesn't, we'll skip the rest of the
         // iteration
-        let mut known_implemented = inherently_implemented;
+        let mut known_implemented = false;
         for &item in data.items() {
             if !is_valid_candidate(db, name, mode, item) {
                 continue;
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 9a26e02fa..ca1693679 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -3983,11 +3983,11 @@ fn test(x: impl Trait<u64>, y: &impl Trait<u64>) {
     [180; 183) 'bar': fn bar() -> impl Trait<u64>
     [180; 185) 'bar()': impl Trait<u64>
     [191; 192) 'x': impl Trait<u64>
-    [191; 198) 'x.foo()': {unknown}
+    [191; 198) 'x.foo()': u64
     [204; 205) 'y': &impl Trait<u64>
-    [204; 211) 'y.foo()': {unknown}
+    [204; 211) 'y.foo()': u64
     [217; 218) 'z': impl Trait<u64>
-    [217; 224) 'z.foo()': {unknown}
+    [217; 224) 'z.foo()': u64
     [230; 231) 'x': impl Trait<u64>
     [230; 238) 'x.foo2()': i64
     [244; 245) 'y': &impl Trait<u64>
@@ -4033,11 +4033,11 @@ fn test(x: dyn Trait<u64>, y: &dyn Trait<u64>) {
     [177; 180) 'bar': fn bar() -> dyn Trait<u64>
     [177; 182) 'bar()': dyn Trait<u64>
     [188; 189) 'x': dyn Trait<u64>
-    [188; 195) 'x.foo()': {unknown}
+    [188; 195) 'x.foo()': u64
     [201; 202) 'y': &dyn Trait<u64>
-    [201; 208) 'y.foo()': {unknown}
+    [201; 208) 'y.foo()': u64
     [214; 215) 'z': dyn Trait<u64>
-    [214; 221) 'z.foo()': {unknown}
+    [214; 221) 'z.foo()': u64
     [227; 228) 'x': dyn Trait<u64>
     [227; 235) 'x.foo2()': i64
     [241; 242) 'y': &dyn Trait<u64>
@@ -4185,6 +4185,49 @@ fn test<T: Trait<Type = u32>>(x: T, y: impl Trait<Type = i64>) {
 }
 
 #[test]
+fn impl_trait_assoc_binding_projection_bug() {
+    let (db, pos) = TestDB::with_position(
+        r#"
+//- /main.rs crate:main deps:std
+pub trait Language {
+    type Kind;
+}
+pub enum RustLanguage {}
+impl Language for RustLanguage {
+    type Kind = SyntaxKind;
+}
+struct SyntaxNode<L> {}
+fn foo() -> impl Iterator<Item = SyntaxNode<RustLanguage>> {}
+
+trait Clone {
+    fn clone(&self) -> Self;
+}
+
+fn api_walkthrough() {
+    for node in foo() {
+        node.clone()<|>;
+    }
+}
+
+//- /std.rs crate:std
+#[prelude_import] use iter::*;
+mod iter {
+    trait IntoIterator {
+        type Item;
+    }
+    trait Iterator {
+        type Item;
+    }
+    impl<T: Iterator> IntoIterator for T {
+        type Item = <T as Iterator>::Item;
+    }
+}
+"#,
+    );
+    assert_eq!("{unknown}", type_at_pos(&db, pos));
+}
+
+#[test]
 fn projection_eq_within_chalk() {
     // std::env::set_var("CHALK_DEBUG", "1");
     assert_snapshot!(
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index 4f1eab150..45f725438 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -8,7 +8,7 @@ use ra_prof::profile;
 use rustc_hash::FxHashSet;
 
 use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk};
-use crate::{db::HirDatabase, expr::ExprId, Crate, DefWithBody, ImplBlock, Trait};
+use crate::{db::HirDatabase, expr::ExprId, Crate, DefWithBody, ImplBlock, Trait, TypeAlias};
 
 use self::chalk::{from_chalk, ToChalk};
 
@@ -17,7 +17,7 @@ pub(crate) mod chalk;
 #[derive(Debug, Clone)]
 pub struct TraitSolver {
     krate: Crate,
-    inner: Arc<Mutex<chalk_solve::Solver>>,
+    inner: Arc<Mutex<chalk_solve::Solver<ChalkIr>>>,
 }
 
 /// We need eq for salsa
@@ -34,7 +34,7 @@ impl TraitSolver {
         &self,
         db: &impl HirDatabase,
         goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal<ChalkIr>>>,
-    ) -> Option<chalk_solve::Solution> {
+    ) -> Option<chalk_solve::Solution<ChalkIr>> {
         let context = ChalkContext { db, krate: self.krate };
         debug!("solve goal: {:?}", goal);
         let mut solver = match self.inner.lock() {
@@ -165,9 +165,9 @@ impl TypeWalk for ProjectionPredicate {
         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);
+    fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) {
+        self.projection_ty.walk_mut_binders(f, binders);
+        self.ty.walk_mut_binders(f, binders);
     }
 }
 
@@ -188,6 +188,7 @@ pub(crate) fn trait_solve_query(
     }
 
     let canonical = goal.to_chalk(db).cast();
+
     // We currently don't deal with universes (I think / hope they're not yet
     // relevant for our use cases?)
     let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 };
@@ -195,7 +196,10 @@ pub(crate) fn trait_solve_query(
     solution.map(|solution| solution_from_chalk(db, solution))
 }
 
-fn solution_from_chalk(db: &impl HirDatabase, solution: chalk_solve::Solution) -> Solution {
+fn solution_from_chalk(
+    db: &impl HirDatabase,
+    solution: chalk_solve::Solution<ChalkIr>,
+) -> Solution {
     let convert_subst = |subst: chalk_ir::Canonical<chalk_ir::Substitution<ChalkIr>>| {
         let value = subst
             .value
@@ -300,3 +304,14 @@ pub enum Impl {
     /// Closure types implement the Fn traits synthetically.
     ClosureFnTraitImpl(ClosureFnTraitImplData),
 }
+
+/// An associated type value. Usually this comes from a `type` declaration
+/// inside an impl block, but for built-in impls we have to synthesize it.
+/// (We only need this because Chalk wants a unique ID for each of these.)
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub enum AssocTyValue {
+    /// A normal assoc type value from an impl block.
+    TypeAlias(TypeAlias),
+    /// The output type of the Fn trait implementation.
+    ClosureFnTraitImplOutput(ClosureFnTraitImplData),
+}
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
index 68304b950..9bf93981a 100644
--- a/crates/ra_hir/src/ty/traits/chalk.rs
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -7,22 +7,19 @@ use chalk_ir::{
     cast::Cast, family::ChalkIr, Identifier, ImplId, Parameter, PlaceholderIndex, TypeId,
     TypeKindId, TypeName, UniverseIndex,
 };
-use chalk_rust_ir::{AssociatedTyDatum, ImplDatum, StructDatum, TraitDatum};
+use chalk_rust_ir::{AssociatedTyDatum, AssociatedTyValue, ImplDatum, StructDatum, TraitDatum};
 
 use hir_expand::name;
 
 use ra_db::salsa::{InternId, InternKey};
 
-use super::{Canonical, ChalkContext, Impl, Obligation};
+use super::{AssocTyValue, Canonical, ChalkContext, Impl, Obligation};
 use crate::{
     db::HirDatabase,
     generics::{GenericDef, HasGenericParams},
     ty::display::HirDisplay,
-    ty::{
-        ApplicationTy, GenericPredicate, Namespace, ProjectionTy, Substs, TraitRef, Ty, TypeCtor,
-        TypeWalk,
-    },
-    AssocItem, Crate, HasBody, ImplBlock, Trait, TypeAlias,
+    ty::{ApplicationTy, GenericPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor, TypeWalk},
+    Crate, HasBody, ImplBlock, Trait, TypeAlias,
 };
 
 /// This represents a trait whose name we could not resolve.
@@ -59,29 +56,36 @@ impl ToChalk for Ty {
                     }
                 };
                 let parameters = apply_ty.parameters.to_chalk(db);
-                chalk_ir::ApplicationTy { name, parameters }.cast()
+                chalk_ir::ApplicationTy { name, parameters }.cast().intern()
             }
             Ty::Projection(proj_ty) => {
                 let associated_ty_id = proj_ty.associated_ty.to_chalk(db);
                 let parameters = proj_ty.parameters.to_chalk(db);
-                chalk_ir::ProjectionTy { associated_ty_id, parameters }.cast()
+                chalk_ir::ProjectionTy { associated_ty_id, parameters }.cast().intern()
             }
             Ty::Param { idx, .. } => {
                 PlaceholderIndex { ui: UniverseIndex::ROOT, idx: idx as usize }.to_ty::<ChalkIr>()
             }
-            Ty::Bound(idx) => chalk_ir::Ty::BoundVar(idx as usize),
+            Ty::Bound(idx) => chalk_ir::TyData::BoundVar(idx as usize).intern(),
             Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"),
-            // FIXME use Chalk's Dyn/Opaque once the bugs with that are fixed
-            Ty::Unknown | Ty::Dyn(_) | Ty::Opaque(_) => {
+            Ty::Dyn(predicates) => {
+                let where_clauses = predicates.iter().cloned().map(|p| p.to_chalk(db)).collect();
+                chalk_ir::TyData::Dyn(make_binders(where_clauses, 1)).intern()
+            }
+            Ty::Opaque(predicates) => {
+                let where_clauses = predicates.iter().cloned().map(|p| p.to_chalk(db)).collect();
+                chalk_ir::TyData::Opaque(make_binders(where_clauses, 1)).intern()
+            }
+            Ty::Unknown => {
                 let parameters = Vec::new();
                 let name = TypeName::Error;
-                chalk_ir::ApplicationTy { name, parameters }.cast()
+                chalk_ir::ApplicationTy { name, parameters }.cast().intern()
             }
         }
     }
     fn from_chalk(db: &impl HirDatabase, chalk: chalk_ir::Ty<ChalkIr>) -> Self {
-        match chalk {
-            chalk_ir::Ty::Apply(apply_ty) => {
+        match chalk.data().clone() {
+            chalk_ir::TyData::Apply(apply_ty) => {
                 // FIXME this is kind of hacky due to the fact that
                 // TypeName::Placeholder is a Ty::Param on our side
                 match apply_ty.name {
@@ -104,21 +108,21 @@ impl ToChalk for Ty {
                     }
                 }
             }
-            chalk_ir::Ty::Projection(proj) => {
+            chalk_ir::TyData::Projection(proj) => {
                 let associated_ty = from_chalk(db, proj.associated_ty_id);
                 let parameters = from_chalk(db, proj.parameters);
                 Ty::Projection(ProjectionTy { associated_ty, parameters })
             }
-            chalk_ir::Ty::ForAll(_) => unimplemented!(),
-            chalk_ir::Ty::BoundVar(idx) => Ty::Bound(idx as u32),
-            chalk_ir::Ty::InferenceVar(_iv) => Ty::Unknown,
-            chalk_ir::Ty::Dyn(where_clauses) => {
+            chalk_ir::TyData::ForAll(_) => unimplemented!(),
+            chalk_ir::TyData::BoundVar(idx) => Ty::Bound(idx as u32),
+            chalk_ir::TyData::InferenceVar(_iv) => Ty::Unknown,
+            chalk_ir::TyData::Dyn(where_clauses) => {
                 assert_eq!(where_clauses.binders.len(), 1);
                 let predicates =
                     where_clauses.value.into_iter().map(|c| from_chalk(db, c)).collect();
                 Ty::Dyn(predicates)
             }
-            chalk_ir::Ty::Opaque(where_clauses) => {
+            chalk_ir::TyData::Opaque(where_clauses) => {
                 assert_eq!(where_clauses.binders.len(), 1);
                 let predicates =
                     where_clauses.value.into_iter().map(|c| from_chalk(db, c)).collect();
@@ -211,6 +215,21 @@ impl ToChalk for TypeAlias {
     }
 }
 
+impl ToChalk for AssocTyValue {
+    type Chalk = chalk_rust_ir::AssociatedTyValueId;
+
+    fn to_chalk(self, db: &impl HirDatabase) -> chalk_rust_ir::AssociatedTyValueId {
+        db.intern_assoc_ty_value(self).into()
+    }
+
+    fn from_chalk(
+        db: &impl HirDatabase,
+        assoc_ty_value_id: chalk_rust_ir::AssociatedTyValueId,
+    ) -> AssocTyValue {
+        db.lookup_intern_assoc_ty_value(assoc_ty_value_id.into())
+    }
+}
+
 impl ToChalk for GenericPredicate {
     type Chalk = chalk_ir::QuantifiedWhereClause<ChalkIr>;
 
@@ -399,20 +418,20 @@ fn convert_where_clauses(
     result
 }
 
-impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB>
+impl<'a, DB> chalk_solve::RustIrDatabase<ChalkIr> for ChalkContext<'a, DB>
 where
     DB: HirDatabase,
 {
-    fn associated_ty_data(&self, id: TypeId) -> Arc<AssociatedTyDatum> {
+    fn associated_ty_data(&self, id: TypeId) -> Arc<AssociatedTyDatum<ChalkIr>> {
         self.db.associated_ty_data(id)
     }
-    fn trait_datum(&self, trait_id: chalk_ir::TraitId) -> Arc<TraitDatum> {
+    fn trait_datum(&self, trait_id: chalk_ir::TraitId) -> Arc<TraitDatum<ChalkIr>> {
         self.db.trait_datum(self.krate, trait_id)
     }
-    fn struct_datum(&self, struct_id: chalk_ir::StructId) -> Arc<StructDatum> {
+    fn struct_datum(&self, struct_id: chalk_ir::StructId) -> Arc<StructDatum<ChalkIr>> {
         self.db.struct_datum(self.krate, struct_id)
     }
-    fn impl_datum(&self, impl_id: ImplId) -> Arc<ImplDatum> {
+    fn impl_datum(&self, impl_id: ImplId) -> Arc<ImplDatum<ChalkIr>> {
         self.db.impl_datum(self.krate, impl_id)
     }
     fn impls_for_trait(
@@ -462,13 +481,11 @@ where
     fn type_name(&self, _id: TypeKindId) -> Identifier {
         unimplemented!()
     }
-    fn split_projection<'p>(
+    fn associated_ty_value(
         &self,
-        projection: &'p chalk_ir::ProjectionTy<ChalkIr>,
-    ) -> (Arc<AssociatedTyDatum>, &'p [Parameter<ChalkIr>], &'p [Parameter<ChalkIr>]) {
-        debug!("split_projection {:?}", projection);
-        // we don't support GATs, so I think this should always be correct currently
-        (self.db.associated_ty_data(projection.associated_ty_id), &projection.parameters, &[])
+        id: chalk_rust_ir::AssociatedTyValueId,
+    ) -> Arc<AssociatedTyValue<ChalkIr>> {
+        self.db.associated_ty_value(self.krate, id)
     }
     fn custom_clauses(&self) -> Vec<chalk_ir::ProgramClause<ChalkIr>> {
         vec![]
@@ -485,7 +502,7 @@ where
 pub(crate) fn associated_ty_data_query(
     db: &impl HirDatabase,
     id: TypeId,
-) -> Arc<AssociatedTyDatum> {
+) -> Arc<AssociatedTyDatum<ChalkIr>> {
     debug!("associated_ty_data {:?}", id);
     let type_alias: TypeAlias = from_chalk(db, id);
     let trait_ = match type_alias.container(db) {
@@ -493,19 +510,16 @@ pub(crate) fn associated_ty_data_query(
         _ => panic!("associated type not in trait"),
     };
     let generic_params = type_alias.generic_params(db);
-    let parameter_kinds = generic_params
-        .params_including_parent()
-        .into_iter()
-        .map(|p| chalk_ir::ParameterKind::Ty(lalrpop_intern::intern(&p.name.to_string())))
-        .collect();
+    let bound_data = chalk_rust_ir::AssociatedTyDatumBound {
+        // FIXME add bounds and where clauses
+        bounds: vec![],
+        where_clauses: vec![],
+    };
     let datum = AssociatedTyDatum {
         trait_id: trait_.to_chalk(db),
         id,
         name: lalrpop_intern::intern(&type_alias.name(db).to_string()),
-        parameter_kinds,
-        // FIXME add bounds and where clauses
-        bounds: vec![],
-        where_clauses: vec![],
+        binders: make_binders(bound_data, generic_params.count_params_including_parent()),
     };
     Arc::new(datum)
 }
@@ -514,17 +528,10 @@ pub(crate) fn trait_datum_query(
     db: &impl HirDatabase,
     krate: Crate,
     trait_id: chalk_ir::TraitId,
-) -> Arc<TraitDatum> {
+) -> Arc<TraitDatum<ChalkIr>> {
     debug!("trait_datum {:?}", trait_id);
     if trait_id == UNKNOWN_TRAIT {
-        let trait_datum_bound = chalk_rust_ir::TraitDatumBound {
-            trait_ref: chalk_ir::TraitRef {
-                trait_id: UNKNOWN_TRAIT,
-                parameters: vec![chalk_ir::Ty::BoundVar(0).cast()],
-            },
-            associated_ty_ids: Vec::new(),
-            where_clauses: Vec::new(),
-        };
+        let trait_datum_bound = chalk_rust_ir::TraitDatumBound { where_clauses: Vec::new() };
 
         let flags = chalk_rust_ir::TraitFlags {
             auto: false,
@@ -532,18 +539,24 @@ pub(crate) fn trait_datum_query(
             upstream: true,
             fundamental: false,
             non_enumerable: true,
+            coinductive: false,
         };
-        return Arc::new(TraitDatum { binders: make_binders(trait_datum_bound, 1), flags });
+        return Arc::new(TraitDatum {
+            id: trait_id,
+            binders: make_binders(trait_datum_bound, 1),
+            flags,
+            associated_ty_ids: vec![],
+        });
     }
     let trait_: Trait = from_chalk(db, trait_id);
     debug!("trait {:?} = {:?}", trait_id, trait_.name(db));
     let generic_params = trait_.generic_params(db);
     let bound_vars = Substs::bound_vars(&generic_params);
-    let trait_ref = trait_.trait_ref(db).subst(&bound_vars).to_chalk(db);
     let flags = chalk_rust_ir::TraitFlags {
         auto: trait_.is_auto(db),
         upstream: trait_.module(db).krate() != krate,
         non_enumerable: true,
+        coinductive: false, // only relevant for Chalk testing
         // FIXME set these flags correctly
         marker: false,
         fundamental: false,
@@ -558,10 +571,13 @@ pub(crate) fn trait_datum_query(
         })
         .map(|type_alias| type_alias.to_chalk(db))
         .collect();
-    let trait_datum_bound =
-        chalk_rust_ir::TraitDatumBound { trait_ref, where_clauses, associated_ty_ids };
-    let trait_datum =
-        TraitDatum { binders: make_binders(trait_datum_bound, bound_vars.len()), flags };
+    let trait_datum_bound = chalk_rust_ir::TraitDatumBound { where_clauses };
+    let trait_datum = TraitDatum {
+        id: trait_id,
+        binders: make_binders(trait_datum_bound, bound_vars.len()),
+        flags,
+        associated_ty_ids,
+    };
     Arc::new(trait_datum)
 }
 
@@ -569,7 +585,7 @@ pub(crate) fn struct_datum_query(
     db: &impl HirDatabase,
     krate: Crate,
     struct_id: chalk_ir::StructId,
-) -> Arc<StructDatum> {
+) -> Arc<StructDatum<ChalkIr>> {
     debug!("struct_datum {:?}", struct_id);
     let type_ctor: TypeCtor = from_chalk(db, struct_id);
     debug!("struct {:?} = {:?}", struct_id, type_ctor);
@@ -588,17 +604,12 @@ pub(crate) fn struct_datum_query(
         // FIXME set fundamental flag correctly
         fundamental: false,
     };
-    let self_ty = chalk_ir::ApplicationTy {
-        name: TypeName::TypeKindId(type_ctor.to_chalk(db).into()),
-        parameters: (0..num_params).map(|i| chalk_ir::Ty::BoundVar(i).cast()).collect(),
-    };
     let struct_datum_bound = chalk_rust_ir::StructDatumBound {
-        self_ty,
         fields: Vec::new(), // FIXME add fields (only relevant for auto traits)
         where_clauses,
-        flags,
     };
-    let struct_datum = StructDatum { binders: make_binders(struct_datum_bound, num_params) };
+    let struct_datum =
+        StructDatum { id: struct_id, binders: make_binders(struct_datum_bound, num_params), flags };
     Arc::new(struct_datum)
 }
 
@@ -606,16 +617,15 @@ pub(crate) fn impl_datum_query(
     db: &impl HirDatabase,
     krate: Crate,
     impl_id: ImplId,
-) -> Arc<ImplDatum> {
+) -> Arc<ImplDatum<ChalkIr>> {
     let _p = ra_prof::profile("impl_datum");
     debug!("impl_datum {:?}", impl_id);
     let impl_: Impl = from_chalk(db, impl_id);
     match impl_ {
         Impl::ImplBlock(impl_block) => impl_block_datum(db, krate, impl_id, impl_block),
-        Impl::ClosureFnTraitImpl(data) => {
-            closure_fn_trait_impl_datum(db, krate, impl_id, data).unwrap_or_else(invalid_impl_datum)
-        }
+        Impl::ClosureFnTraitImpl(data) => closure_fn_trait_impl_datum(db, krate, data),
     }
+    .unwrap_or_else(invalid_impl_datum)
 }
 
 fn impl_block_datum(
@@ -623,13 +633,11 @@ fn impl_block_datum(
     krate: Crate,
     impl_id: ImplId,
     impl_block: ImplBlock,
-) -> Arc<ImplDatum> {
+) -> Option<Arc<ImplDatum<ChalkIr>>> {
     let generic_params = impl_block.generic_params(db);
     let bound_vars = Substs::bound_vars(&generic_params);
-    let trait_ref = impl_block
-        .target_trait_ref(db)
-        .expect("FIXME handle unresolved impl block trait ref")
-        .subst(&bound_vars);
+    let trait_ref = impl_block.target_trait_ref(db)?.subst(&bound_vars);
+    let trait_ = trait_ref.trait_;
     let impl_type = if impl_block.krate(db) == krate {
         chalk_rust_ir::ImplType::Local
     } else {
@@ -644,28 +652,7 @@ fn impl_block_datum(
         trait_ref.display(db),
         where_clauses
     );
-    let trait_ = trait_ref.trait_;
     let trait_ref = trait_ref.to_chalk(db);
-    let associated_ty_values = impl_block
-        .items(db)
-        .into_iter()
-        .filter_map(|item| match item {
-            AssocItem::TypeAlias(t) => Some(t),
-            _ => None,
-        })
-        .filter_map(|t| {
-            let assoc_ty = trait_.associated_type_by_name(db, &t.name(db))?;
-            let ty = db.type_for_def(t.into(), Namespace::Types).subst(&bound_vars);
-            Some(chalk_rust_ir::AssociatedTyValue {
-                impl_id,
-                associated_ty_id: assoc_ty.to_chalk(db),
-                value: chalk_ir::Binders {
-                    value: chalk_rust_ir::AssociatedTyValueBound { ty: ty.to_chalk(db) },
-                    binders: vec![], // we don't support GATs yet
-                },
-            })
-        })
-        .collect();
 
     let polarity = if negative {
         chalk_rust_ir::Polarity::Negative
@@ -673,31 +660,41 @@ fn impl_block_datum(
         chalk_rust_ir::Polarity::Positive
     };
 
-    let impl_datum_bound =
-        chalk_rust_ir::ImplDatumBound { trait_ref, where_clauses, associated_ty_values };
+    let impl_datum_bound = chalk_rust_ir::ImplDatumBound { trait_ref, where_clauses };
+    let associated_ty_value_ids = impl_block
+        .items(db)
+        .into_iter()
+        .filter_map(|item| match item {
+            crate::AssocItem::TypeAlias(type_alias) => Some(type_alias),
+            _ => None,
+        })
+        .filter(|type_alias| {
+            // don't include associated types that don't exist in the trait
+            trait_.associated_type_by_name(db, &type_alias.name(db)).is_some()
+        })
+        .map(|type_alias| AssocTyValue::TypeAlias(type_alias).to_chalk(db))
+        .collect();
     debug!("impl_datum: {:?}", impl_datum_bound);
     let impl_datum = ImplDatum {
         binders: make_binders(impl_datum_bound, bound_vars.len()),
         impl_type,
         polarity,
+        associated_ty_value_ids,
     };
-    Arc::new(impl_datum)
+    Some(Arc::new(impl_datum))
 }
 
-fn invalid_impl_datum() -> Arc<ImplDatum> {
+fn invalid_impl_datum() -> Arc<ImplDatum<ChalkIr>> {
     let trait_ref = chalk_ir::TraitRef {
         trait_id: UNKNOWN_TRAIT,
-        parameters: vec![chalk_ir::Ty::BoundVar(0).cast()],
-    };
-    let impl_datum_bound = chalk_rust_ir::ImplDatumBound {
-        trait_ref,
-        where_clauses: Vec::new(),
-        associated_ty_values: Vec::new(),
+        parameters: vec![chalk_ir::TyData::BoundVar(0).cast().intern().cast()],
     };
+    let impl_datum_bound = chalk_rust_ir::ImplDatumBound { trait_ref, where_clauses: Vec::new() };
     let impl_datum = ImplDatum {
         binders: make_binders(impl_datum_bound, 1),
         impl_type: chalk_rust_ir::ImplType::External,
         polarity: chalk_rust_ir::Polarity::Positive,
+        associated_ty_value_ids: Vec::new(),
     };
     Arc::new(impl_datum)
 }
@@ -705,15 +702,19 @@ fn invalid_impl_datum() -> Arc<ImplDatum> {
 fn closure_fn_trait_impl_datum(
     db: &impl HirDatabase,
     krate: Crate,
-    impl_id: ImplId,
     data: super::ClosureFnTraitImplData,
-) -> Option<Arc<ImplDatum>> {
+) -> Option<Arc<ImplDatum<ChalkIr>>> {
     // for some closure |X, Y| -> Z:
     // impl<T, U, V> Fn<(T, U)> for closure<fn(T, U) -> V> { Output = V }
 
-    let fn_once_trait = get_fn_trait(db, krate, super::FnTrait::FnOnce)?;
     let trait_ = get_fn_trait(db, krate, data.fn_trait)?; // get corresponding fn trait
 
+    // validate FnOnce trait, since we need it in the assoc ty value definition
+    // and don't want to return a valid value only to find out later that FnOnce
+    // is broken
+    let fn_once_trait = get_fn_trait(db, krate, super::FnTrait::FnOnce)?;
+    fn_once_trait.associated_type_by_name(db, &name::OUTPUT_TYPE)?;
+
     let num_args: u16 = match &data.def.body(db)[data.expr] {
         crate::expr::Expr::Lambda { args, .. } => args.len() as u16,
         _ => {
@@ -726,7 +727,6 @@ fn closure_fn_trait_impl_datum(
         TypeCtor::Tuple { cardinality: num_args },
         Substs::builder(num_args as usize).fill_with_bound_vars(0).build(),
     );
-    let output_ty = Ty::Bound(num_args.into());
     let sig_ty = Ty::apply(
         TypeCtor::FnPtr { num_args },
         Substs::builder(num_args as usize + 1).fill_with_bound_vars(0).build(),
@@ -739,32 +739,99 @@ fn closure_fn_trait_impl_datum(
         substs: Substs::build_for_def(db, trait_).push(self_ty).push(arg_ty).build(),
     };
 
-    let output_ty_id = fn_once_trait.associated_type_by_name(db, &name::OUTPUT_TYPE)?;
-
-    let output_ty_value = chalk_rust_ir::AssociatedTyValue {
-        associated_ty_id: output_ty_id.to_chalk(db),
-        impl_id,
-        value: make_binders(
-            chalk_rust_ir::AssociatedTyValueBound { ty: output_ty.to_chalk(db) },
-            0,
-        ),
-    };
+    let output_ty_id = AssocTyValue::ClosureFnTraitImplOutput(data.clone()).to_chalk(db);
 
     let impl_type = chalk_rust_ir::ImplType::External;
 
     let impl_datum_bound = chalk_rust_ir::ImplDatumBound {
         trait_ref: trait_ref.to_chalk(db),
         where_clauses: Vec::new(),
-        associated_ty_values: vec![output_ty_value],
     };
     let impl_datum = ImplDatum {
         binders: make_binders(impl_datum_bound, num_args as usize + 1),
         impl_type,
         polarity: chalk_rust_ir::Polarity::Positive,
+        associated_ty_value_ids: vec![output_ty_id],
     };
     Some(Arc::new(impl_datum))
 }
 
+pub(crate) fn associated_ty_value_query(
+    db: &impl HirDatabase,
+    krate: Crate,
+    id: chalk_rust_ir::AssociatedTyValueId,
+) -> Arc<chalk_rust_ir::AssociatedTyValue<ChalkIr>> {
+    let data: AssocTyValue = from_chalk(db, id);
+    match data {
+        AssocTyValue::TypeAlias(type_alias) => {
+            type_alias_associated_ty_value(db, krate, type_alias)
+        }
+        AssocTyValue::ClosureFnTraitImplOutput(data) => {
+            closure_fn_trait_output_assoc_ty_value(db, krate, data)
+        }
+    }
+}
+
+fn type_alias_associated_ty_value(
+    db: &impl HirDatabase,
+    _krate: Crate,
+    type_alias: TypeAlias,
+) -> Arc<AssociatedTyValue<ChalkIr>> {
+    let impl_block = type_alias.impl_block(db).expect("assoc ty value should be in impl");
+    let impl_id = Impl::ImplBlock(impl_block).to_chalk(db);
+    let trait_ = impl_block
+        .target_trait_ref(db)
+        .expect("assoc ty value should not exist") // we don't return any assoc ty values if the impl'd trait can't be resolved
+        .trait_;
+    let assoc_ty = trait_
+        .associated_type_by_name(db, &type_alias.name(db))
+        .expect("assoc ty value should not exist"); // validated when building the impl data as well
+    let generic_params = impl_block.generic_params(db);
+    let bound_vars = Substs::bound_vars(&generic_params);
+    let ty = db.type_for_def(type_alias.into(), crate::ty::Namespace::Types).subst(&bound_vars);
+    let value_bound = chalk_rust_ir::AssociatedTyValueBound { ty: ty.to_chalk(db) };
+    let value = chalk_rust_ir::AssociatedTyValue {
+        impl_id,
+        associated_ty_id: assoc_ty.to_chalk(db),
+        value: make_binders(value_bound, bound_vars.len()),
+    };
+    Arc::new(value)
+}
+
+fn closure_fn_trait_output_assoc_ty_value(
+    db: &impl HirDatabase,
+    krate: Crate,
+    data: super::ClosureFnTraitImplData,
+) -> Arc<AssociatedTyValue<ChalkIr>> {
+    let impl_id = Impl::ClosureFnTraitImpl(data.clone()).to_chalk(db);
+
+    let num_args: u16 = match &data.def.body(db)[data.expr] {
+        crate::expr::Expr::Lambda { args, .. } => args.len() as u16,
+        _ => {
+            log::warn!("closure for closure type {:?} not found", data);
+            0
+        }
+    };
+
+    let output_ty = Ty::Bound(num_args.into());
+
+    let fn_once_trait =
+        get_fn_trait(db, krate, super::FnTrait::FnOnce).expect("assoc ty value should not exist");
+
+    let output_ty_id = fn_once_trait
+        .associated_type_by_name(db, &name::OUTPUT_TYPE)
+        .expect("assoc ty value should not exist");
+
+    let value_bound = chalk_rust_ir::AssociatedTyValueBound { ty: output_ty.to_chalk(db) };
+
+    let value = chalk_rust_ir::AssociatedTyValue {
+        associated_ty_id: output_ty_id.to_chalk(db),
+        impl_id,
+        value: make_binders(value_bound, num_args as usize + 1),
+    };
+    Arc::new(value)
+}
+
 fn get_fn_trait(db: &impl HirDatabase, krate: Crate, fn_trait: super::FnTrait) -> Option<Trait> {
     let target = db.lang_item(krate, fn_trait.lang_item_name().into())?;
     match target {
@@ -803,3 +870,15 @@ impl From<crate::ids::GlobalImplId> for chalk_ir::ImplId {
         chalk_ir::ImplId(id_to_chalk(impl_id))
     }
 }
+
+impl From<chalk_rust_ir::AssociatedTyValueId> for crate::ids::AssocTyValueId {
+    fn from(id: chalk_rust_ir::AssociatedTyValueId) -> Self {
+        id_from_chalk(id.0)
+    }
+}
+
+impl From<crate::ids::AssocTyValueId> for chalk_rust_ir::AssociatedTyValueId {
+    fn from(assoc_ty_value_id: crate::ids::AssocTyValueId) -> Self {
+        chalk_rust_ir::AssociatedTyValueId(id_to_chalk(assoc_ty_value_id))
+    }
+}