7 files changed, 755 insertions, 237 deletions

diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index c7772a7f6..edce1afe7 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -44,9 +44,12 @@ use crate::{
 };
 use super::{
     Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef,
-    traits::{ Solution, Obligation, Guidance},
+    traits::{Solution, Obligation, Guidance},
+    method_resolution,
 };
 
+mod unify;
+
 /// The entry point of type inference.
 pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> {
     db.check_canceled();
@@ -321,30 +324,29 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
     fn resolve_obligations_as_possible(&mut self) {
         let obligations = mem::replace(&mut self.obligations, Vec::new());
         for obligation in obligations {
-            // FIXME resolve types in the obligation first
-            let (solution, var_mapping) = match &obligation {
+            let (solution, canonicalized) = match &obligation {
                 Obligation::Trait(tr) => {
-                    let (tr, var_mapping) = super::traits::canonicalize(tr.clone());
-                    (self.db.implements(tr), var_mapping)
+                    let canonicalized = self.canonicalizer().canonicalize_trait_ref(tr.clone());
+                    (
+                        super::traits::implements(
+                            self.db,
+                            self.resolver.krate().unwrap(),
+                            canonicalized.value.clone(),
+                        ),
+                        canonicalized,
+                    )
                 }
             };
             match solution {
                 Some(Solution::Unique(substs)) => {
-                    for (i, subst) in substs.0.iter().enumerate() {
-                        let uncanonical = var_mapping[i];
-                        // FIXME the subst may contain type variables, which would need to be mapped back as well
-                        self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
-                    }
+                    canonicalized.apply_solution(self, substs.0);
                 }
                 Some(Solution::Ambig(Guidance::Definite(substs))) => {
-                    for (i, subst) in substs.0.iter().enumerate() {
-                        let uncanonical = var_mapping[i];
-                        // FIXME the subst may contain type variables, which would need to be mapped back as well
-                        self.unify(&Ty::Infer(InferTy::TypeVar(uncanonical)), subst);
-                    }
+                    canonicalized.apply_solution(self, substs.0);
                     self.obligations.push(obligation);
                 }
                 Some(_) => {
+                    // FIXME use this when trying to resolve everything at the end
                     self.obligations.push(obligation);
                 }
                 None => {
@@ -737,14 +739,14 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 };
                 let expectations_iter = expectations.iter().chain(repeat(&Ty::Unknown));
 
-                let inner_tys = args
+                let inner_tys: Substs = args
                     .iter()
                     .zip(expectations_iter)
                     .map(|(&pat, ty)| self.infer_pat(pat, ty, default_bm))
                     .collect::<Vec<_>>()
                     .into();
 
-                Ty::apply(TypeCtor::Tuple, Substs(inner_tys))
+                Ty::apply(TypeCtor::Tuple { cardinality: inner_tys.len() as u16 }, inner_tys)
             }
             Pat::Ref { pat, mutability } => {
                 let expectation = match expected.as_reference() {
@@ -877,9 +879,16 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         generic_args: Option<&GenericArgs>,
     ) -> Ty {
         let receiver_ty = self.infer_expr(receiver, &Expectation::none());
-        let resolved = receiver_ty.clone().lookup_method(self.db, method_name, &self.resolver);
+        let canonicalized_receiver = self.canonicalizer().canonicalize_ty(receiver_ty.clone());
+        let resolved = method_resolution::lookup_method(
+            &canonicalized_receiver.value,
+            self.db,
+            method_name,
+            &self.resolver,
+        );
         let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
             Some((ty, func)) => {
+                let ty = canonicalized_receiver.decanonicalize_ty(ty);
                 self.write_method_resolution(tgt_expr, func);
                 (
                     ty,
@@ -1064,7 +1073,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                     .autoderef(self.db)
                     .find_map(|derefed_ty| match derefed_ty {
                         Ty::Apply(a_ty) => match a_ty.ctor {
-                            TypeCtor::Tuple => {
+                            TypeCtor::Tuple { .. } => {
                                 let i = name.to_string().parse::<usize>().ok();
                                 i.and_then(|i| a_ty.parameters.0.get(i).cloned())
                             }
@@ -1175,7 +1184,10 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                     ty_vec.push(self.infer_expr(*arg, &Expectation::none()));
                 }
 
-                Ty::apply(TypeCtor::Tuple, Substs(ty_vec.into()))
+                Ty::apply(
+                    TypeCtor::Tuple { cardinality: ty_vec.len() as u16 },
+                    Substs(ty_vec.into()),
+                )
             }
             Expr::Array(array) => {
                 let elem_ty = match &expected.ty {
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs
new file mode 100644
index 000000000..8ca7e957d
--- /dev/null
+++ b/crates/ra_hir/src/ty/infer/unify.rs
@@ -0,0 +1,122 @@
+//! Unification and canonicalization logic.
+
+use crate::db::HirDatabase;
+use crate::ty::{Ty, Canonical, TraitRef, InferTy};
+use super::InferenceContext;
+
+impl<'a, D: HirDatabase> InferenceContext<'a, D> {
+    pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D>
+    where
+        'a: 'b,
+    {
+        Canonicalizer { ctx: self, free_vars: Vec::new(), var_stack: Vec::new() }
+    }
+}
+
+pub(super) struct Canonicalizer<'a, 'b, D: HirDatabase>
+where
+    'a: 'b,
+{
+    ctx: &'b mut InferenceContext<'a, D>,
+    free_vars: Vec<InferTy>,
+    /// A stack of type variables that is used to detect recursive types (which
+    /// are an error, but we need to protect against them to avoid stack
+    /// overflows).
+    var_stack: Vec<super::TypeVarId>,
+}
+
+pub(super) struct Canonicalized<T> {
+    pub value: Canonical<T>,
+    free_vars: Vec<InferTy>,
+}
+
+impl<'a, 'b, D: HirDatabase> Canonicalizer<'a, 'b, D>
+where
+    'a: 'b,
+{
+    fn add(&mut self, free_var: InferTy) -> usize {
+        self.free_vars.iter().position(|&v| v == free_var).unwrap_or_else(|| {
+            let next_index = self.free_vars.len();
+            self.free_vars.push(free_var);
+            next_index
+        })
+    }
+
+    fn do_canonicalize_ty(&mut self, ty: Ty) -> Ty {
+        ty.fold(&mut |ty| match ty {
+            Ty::Infer(tv) => {
+                let inner = tv.to_inner();
+                if self.var_stack.contains(&inner) {
+                    // recursive type
+                    return tv.fallback_value();
+                }
+                if let Some(known_ty) = self.ctx.var_unification_table.probe_value(inner).known() {
+                    self.var_stack.push(inner);
+                    let result = self.do_canonicalize_ty(known_ty.clone());
+                    self.var_stack.pop();
+                    result
+                } else {
+                    let free_var = InferTy::TypeVar(self.ctx.var_unification_table.find(inner));
+                    let position = self.add(free_var);
+                    Ty::Bound(position as u32)
+                }
+            }
+            _ => ty,
+        })
+    }
+
+    fn do_canonicalize_trait_ref(&mut self, trait_ref: TraitRef) -> TraitRef {
+        let substs = trait_ref
+            .substs
+            .iter()
+            .map(|ty| self.do_canonicalize_ty(ty.clone()))
+            .collect::<Vec<_>>();
+        TraitRef { trait_: trait_ref.trait_, substs: substs.into() }
+    }
+
+    fn into_canonicalized<T>(self, result: T) -> Canonicalized<T> {
+        Canonicalized {
+            value: Canonical { value: result, num_vars: self.free_vars.len() },
+            free_vars: self.free_vars,
+        }
+    }
+
+    pub fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized<Ty> {
+        let result = self.do_canonicalize_ty(ty);
+        self.into_canonicalized(result)
+    }
+
+    pub fn canonicalize_trait_ref(mut self, trait_ref: TraitRef) -> Canonicalized<TraitRef> {
+        let result = self.do_canonicalize_trait_ref(trait_ref);
+        self.into_canonicalized(result)
+    }
+}
+
+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].clone())
+                } else {
+                    Ty::Bound(idx)
+                }
+            }
+            ty => ty,
+        })
+    }
+
+    pub fn apply_solution(
+        &self,
+        ctx: &mut InferenceContext<'_, impl HirDatabase>,
+        solution: Canonical<Vec<Ty>>,
+    ) {
+        // the solution may contain new variables, which we need to convert to new inference vars
+        let new_vars =
+            (0..solution.num_vars).map(|_| ctx.new_type_var()).collect::<Vec<_>>().into();
+        for (i, ty) in solution.value.into_iter().enumerate() {
+            let var = self.free_vars[i].clone();
+            ctx.unify(&Ty::Infer(var), &ty.subst_bound_vars(&new_vars));
+        }
+    }
+}
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 7fac084ce..8bab7e54b 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -29,7 +29,10 @@ impl Ty {
             TypeRef::Tuple(inner) => {
                 let inner_tys =
                     inner.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>();
-                Ty::apply(TypeCtor::Tuple, Substs(inner_tys.into()))
+                Ty::apply(
+                    TypeCtor::Tuple { cardinality: inner_tys.len() as u16 },
+                    Substs(inner_tys.into()),
+                )
             }
             TypeRef::Path(path) => Ty::from_hir_path(db, resolver, path),
             TypeRef::RawPtr(inner, mutability) => {
@@ -53,7 +56,7 @@ impl Ty {
                 let inner_tys =
                     params.iter().map(|tr| Ty::from_hir(db, resolver, tr)).collect::<Vec<_>>();
                 let sig = Substs(inner_tys.into());
-                Ty::apply(TypeCtor::FnPtr, sig)
+                Ty::apply(TypeCtor::FnPtr { num_args: sig.len() as u16 - 1 }, sig)
             }
             TypeRef::Error => Ty::Unknown,
         }
@@ -238,6 +241,11 @@ impl TraitRef {
         let segment = path.segments.last().expect("path should have at least one segment");
         substs_from_path_segment(db, resolver, segment, &resolved.generic_params(db), true)
     }
+
+    pub(crate) fn for_trait(db: &impl HirDatabase, trait_: Trait) -> TraitRef {
+        let substs = Substs::identity(&trait_.generic_params(db));
+        TraitRef { trait_, substs }
+    }
 }
 
 /// Build the declared type of an item. This depends on the namespace; e.g. for
@@ -299,7 +307,7 @@ fn fn_sig_for_fn(db: &impl HirDatabase, def: Function) -> FnSig {
 /// function body.
 fn type_for_fn(db: &impl HirDatabase, def: Function) -> Ty {
     let generics = def.generic_params(db);
-    let substs = make_substs(&generics);
+    let substs = Substs::identity(&generics);
     Ty::apply(TypeCtor::FnDef(def.into()), substs)
 }
 
@@ -341,7 +349,7 @@ fn type_for_struct_constructor(db: &impl HirDatabase, def: Struct) -> Ty {
         return type_for_struct(db, def); // Unit struct
     }
     let generics = def.generic_params(db);
-    let substs = make_substs(&generics);
+    let substs = Substs::identity(&generics);
     Ty::apply(TypeCtor::FnDef(def.into()), substs)
 }
 
@@ -357,7 +365,7 @@ fn fn_sig_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant)
         .map(|(_, field)| Ty::from_hir(db, &resolver, &field.type_ref))
         .collect::<Vec<_>>();
     let generics = def.parent_enum(db).generic_params(db);
-    let substs = make_substs(&generics);
+    let substs = Substs::identity(&generics);
     let ret = type_for_enum(db, def.parent_enum(db)).subst(&substs);
     FnSig::from_params_and_return(params, ret)
 }
@@ -369,36 +377,25 @@ fn type_for_enum_variant_constructor(db: &impl HirDatabase, def: EnumVariant) ->
         return type_for_enum(db, def.parent_enum(db)); // Unit variant
     }
     let generics = def.parent_enum(db).generic_params(db);
-    let substs = make_substs(&generics);
+    let substs = Substs::identity(&generics);
     Ty::apply(TypeCtor::FnDef(def.into()), substs)
 }
 
-fn make_substs(generics: &GenericParams) -> Substs {
-    Substs(
-        generics
-            .params_including_parent()
-            .into_iter()
-            .map(|p| Ty::Param { idx: p.idx, name: p.name.clone() })
-            .collect::<Vec<_>>()
-            .into(),
-    )
-}
-
 fn type_for_struct(db: &impl HirDatabase, s: Struct) -> Ty {
     let generics = s.generic_params(db);
-    Ty::apply(TypeCtor::Adt(s.into()), make_substs(&generics))
+    Ty::apply(TypeCtor::Adt(s.into()), Substs::identity(&generics))
 }
 
 fn type_for_enum(db: &impl HirDatabase, s: Enum) -> Ty {
     let generics = s.generic_params(db);
-    Ty::apply(TypeCtor::Adt(s.into()), make_substs(&generics))
+    Ty::apply(TypeCtor::Adt(s.into()), Substs::identity(&generics))
 }
 
 fn type_for_type_alias(db: &impl HirDatabase, t: TypeAlias) -> Ty {
     let generics = t.generic_params(db);
     let resolver = t.resolver(db);
     let type_ref = t.type_ref(db);
-    let substs = make_substs(&generics);
+    let substs = Substs::identity(&generics);
     let inner = Ty::from_hir(db, &resolver, &type_ref);
     inner.subst(&substs)
 }
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index ea6e0dc0f..607e9ba79 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -16,7 +16,7 @@ use crate::{
     generics::HasGenericParams,
     ty::primitive::{UncertainIntTy, UncertainFloatTy}
 };
-use super::{TraitRef, Substs};
+use super::{TraitRef, Canonical};
 
 /// This is used as a key for indexing impls.
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
@@ -130,124 +130,122 @@ fn def_crate(db: &impl HirDatabase, cur_crate: Crate, ty: &Ty) -> Option<Crate>
     }
 }
 
-impl Ty {
-    /// Look up the method with the given name, returning the actual autoderefed
-    /// receiver type (but without autoref applied yet).
-    pub(crate) fn lookup_method(
-        self,
-        db: &impl HirDatabase,
-        name: &Name,
-        resolver: &Resolver,
-    ) -> Option<(Ty, Function)> {
-        self.iterate_method_candidates(db, resolver, Some(name), |ty, f| Some((ty.clone(), f)))
-    }
+/// Look up the method with the given name, returning the actual autoderefed
+/// receiver type (but without autoref applied yet).
+pub(crate) fn lookup_method(
+    ty: &Canonical<Ty>,
+    db: &impl HirDatabase,
+    name: &Name,
+    resolver: &Resolver,
+) -> Option<(Ty, Function)> {
+    iterate_method_candidates(ty, db, resolver, Some(name), |ty, f| Some((ty.clone(), f)))
+}
 
-    // This would be nicer if it just returned an iterator, but that runs into
-    // lifetime problems, because we need to borrow temp `CrateImplBlocks`.
-    pub(crate) fn iterate_method_candidates<T>(
-        self,
-        db: &impl HirDatabase,
-        resolver: &Resolver,
-        name: Option<&Name>,
-        mut callback: impl FnMut(&Ty, Function) -> Option<T>,
-    ) -> Option<T> {
-        // For method calls, rust first does any number of autoderef, and then one
-        // autoref (i.e. when the method takes &self or &mut self). We just ignore
-        // the autoref currently -- when we find a method matching the given name,
-        // we assume it fits.
+// This would be nicer if it just returned an iterator, but that runs into
+// lifetime problems, because we need to borrow temp `CrateImplBlocks`.
+pub(crate) fn iterate_method_candidates<T>(
+    ty: &Canonical<Ty>,
+    db: &impl HirDatabase,
+    resolver: &Resolver,
+    name: Option<&Name>,
+    mut callback: impl FnMut(&Ty, Function) -> Option<T>,
+) -> Option<T> {
+    // For method calls, rust first does any number of autoderef, and then one
+    // autoref (i.e. when the method takes &self or &mut self). We just ignore
+    // the autoref currently -- when we find a method matching the given name,
+    // we assume it fits.
 
-        // Also note that when we've got a receiver like &S, even if the method we
-        // find in the end takes &self, we still do the autoderef step (just as
-        // rustc does an autoderef and then autoref again).
+    // Also note that when we've got a receiver like &S, even if the method we
+    // find in the end takes &self, we still do the autoderef step (just as
+    // rustc does an autoderef and then autoref again).
 
-        let krate = resolver.krate()?;
-        for derefed_ty in self.autoderef(db) {
-            if let Some(result) =
-                derefed_ty.iterate_inherent_methods(db, name, krate, &mut callback)
-            {
-                return Some(result);
-            }
-            if let Some(result) =
-                derefed_ty.iterate_trait_method_candidates(db, resolver, name, &mut callback)
-            {
-                return Some(result);
-            }
+    let krate = resolver.krate()?;
+    for derefed_ty in ty.value.clone().autoderef(db) {
+        let derefed_ty = Canonical { value: derefed_ty, num_vars: ty.num_vars };
+        if let Some(result) = iterate_inherent_methods(&derefed_ty, db, name, krate, &mut callback)
+        {
+            return Some(result);
+        }
+        if let Some(result) =
+            iterate_trait_method_candidates(&derefed_ty, db, resolver, name, &mut callback)
+        {
+            return Some(result);
         }
-        None
     }
+    None
+}
 
-    fn iterate_trait_method_candidates<T>(
-        &self,
-        db: &impl HirDatabase,
-        resolver: &Resolver,
-        name: Option<&Name>,
-        mut callback: impl FnMut(&Ty, Function) -> Option<T>,
-    ) -> Option<T> {
-        'traits: for t in resolver.traits_in_scope() {
-            let data = t.trait_data(db);
-            // 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 = false;
-            for item in data.items() {
-                match item {
-                    &TraitItem::Function(m) => {
-                        let sig = m.signature(db);
-                        if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() {
-                            if !known_implemented {
-                                let trait_ref = TraitRef {
-                                    trait_: t,
-                                    substs: fresh_substs_for_trait(db, t, self.clone()),
-                                };
-                                let (trait_ref, _) = super::traits::canonicalize(trait_ref);
-                                if db.implements(trait_ref).is_none() {
-                                    continue 'traits;
-                                }
-                            }
-                            known_implemented = true;
-                            if let Some(result) = callback(self, m) {
-                                return Some(result);
+fn iterate_trait_method_candidates<T>(
+    ty: &Canonical<Ty>,
+    db: &impl HirDatabase,
+    resolver: &Resolver,
+    name: Option<&Name>,
+    mut callback: impl FnMut(&Ty, Function) -> Option<T>,
+) -> Option<T> {
+    let krate = resolver.krate()?;
+    'traits: for t in resolver.traits_in_scope() {
+        let data = t.trait_data(db);
+        // 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 = false;
+        for item in data.items() {
+            match item {
+                &TraitItem::Function(m) => {
+                    let sig = m.signature(db);
+                    if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() {
+                        if !known_implemented {
+                            let trait_ref = canonical_trait_ref(db, t, ty.clone());
+                            // FIXME cache this implements check (without solution) in a query?
+                            if super::traits::implements(db, krate, trait_ref).is_none() {
+                                continue 'traits;
                             }
                         }
+                        known_implemented = true;
+                        if let Some(result) = callback(&ty.value, m) {
+                            return Some(result);
+                        }
                     }
-                    _ => {}
                 }
+                _ => {}
             }
         }
-        None
     }
+    None
+}
 
-    fn iterate_inherent_methods<T>(
-        &self,
-        db: &impl HirDatabase,
-        name: Option<&Name>,
-        krate: Crate,
-        mut callback: impl FnMut(&Ty, Function) -> Option<T>,
-    ) -> Option<T> {
-        let krate = match def_crate(db, krate, self) {
-            Some(krate) => krate,
-            None => return None,
-        };
-        let impls = db.impls_in_crate(krate);
+fn iterate_inherent_methods<T>(
+    ty: &Canonical<Ty>,
+    db: &impl HirDatabase,
+    name: Option<&Name>,
+    krate: Crate,
+    mut callback: impl FnMut(&Ty, Function) -> Option<T>,
+) -> Option<T> {
+    let krate = match def_crate(db, krate, &ty.value) {
+        Some(krate) => krate,
+        None => return None,
+    };
+    let impls = db.impls_in_crate(krate);
 
-        for impl_block in impls.lookup_impl_blocks(self) {
-            for item in impl_block.items(db) {
-                match item {
-                    ImplItem::Method(f) => {
-                        let sig = f.signature(db);
-                        if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() {
-                            if let Some(result) = callback(self, f) {
-                                return Some(result);
-                            }
+    for impl_block in impls.lookup_impl_blocks(&ty.value) {
+        for item in impl_block.items(db) {
+            match item {
+                ImplItem::Method(f) => {
+                    let sig = f.signature(db);
+                    if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() {
+                        if let Some(result) = callback(&ty.value, f) {
+                            return Some(result);
                         }
                     }
-                    _ => {}
                 }
+                _ => {}
             }
         }
-        None
     }
+    None
+}
 
+impl Ty {
     // This would be nicer if it just returned an iterator, but that runs into
     // lifetime problems, because we need to borrow temp `CrateImplBlocks`.
     pub fn iterate_impl_items<T>(
@@ -271,15 +269,26 @@ impl Ty {
 }
 
 /// This creates Substs for a trait with the given Self type and type variables
-/// for all other parameters. This is kind of a hack since these aren't 'real'
-/// type variables; the resulting trait reference is just used for the
-/// preliminary method candidate check.
-fn fresh_substs_for_trait(db: &impl HirDatabase, tr: Trait, self_ty: Ty) -> Substs {
+/// for all other parameters, to query Chalk with it.
+fn canonical_trait_ref(
+    db: &impl HirDatabase,
+    trait_: Trait,
+    self_ty: Canonical<Ty>,
+) -> Canonical<TraitRef> {
     let mut substs = Vec::new();
-    let generics = tr.generic_params(db);
-    substs.push(self_ty);
-    substs.extend(generics.params_including_parent().into_iter().skip(1).enumerate().map(
-        |(i, _p)| Ty::Infer(super::infer::InferTy::TypeVar(super::infer::TypeVarId(i as u32))),
-    ));
-    substs.into()
+    let generics = trait_.generic_params(db);
+    let num_vars = self_ty.num_vars;
+    substs.push(self_ty.value);
+    substs.extend(
+        generics
+            .params_including_parent()
+            .into_iter()
+            .skip(1)
+            .enumerate()
+            .map(|(i, _p)| Ty::Bound((i + num_vars) as u32)),
+    );
+    Canonical {
+        num_vars: substs.len() - 1 + self_ty.num_vars,
+        value: TraitRef { trait_, substs: substs.into() },
+    }
 }
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index c76a5012f..0aecde37c 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2140,7 +2140,7 @@ fn test() {
 [102; 127) '{     ...d(); }': ()
 [108; 109) 'S': S<u32>(T) -> S<T>
 [108; 115) 'S(1u32)': S<u32>
-[108; 124) 'S(1u32...thod()': {unknown}
+[108; 124) 'S(1u32...thod()': u32
 [110; 114) '1u32': u32"###
     );
 }
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index 06f483899..a1ed0c028 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -1,47 +1,65 @@
-//! Stuff that will probably mostly replaced by Chalk.
-use std::collections::HashMap;
+//! Trait solving using Chalk.
+use std::sync::{Arc, Mutex};
 
-use crate::{db::HirDatabase, generics::HasGenericParams};
-use super::{TraitRef, Substs, infer::{TypeVarId, InferTy}, Ty};
+use log::debug;
+use chalk_ir::cast::Cast;
 
-// Copied (and simplified) from Chalk
+use crate::{Crate, Trait, db::HirDatabase, ImplBlock};
+use super::{TraitRef, Ty, Canonical};
 
-#[derive(Clone, Debug, PartialEq, Eq)]
-/// A (possible) solution for a proposed goal. Usually packaged in a `Result`,
-/// where `Err` represents definite *failure* to prove a goal.
-pub enum Solution {
-    /// The goal indeed holds, and there is a unique value for all existential
-    /// variables.
-    Unique(Substs),
+use self::chalk::{ToChalk, from_chalk};
 
-    /// The goal may be provable in multiple ways, but regardless we may have some guidance
-    /// for type inference.
-    Ambig(Guidance),
+mod chalk;
+
+pub(crate) type Solver = chalk_solve::Solver;
+
+#[derive(Debug, Copy, Clone)]
+struct ChalkContext<'a, DB> {
+    db: &'a DB,
+    krate: Crate,
 }
 
-#[derive(Clone, Debug, PartialEq, Eq)]
-/// When a goal holds ambiguously (e.g., because there are multiple possible
-/// solutions), we issue a set of *guidance* back to type inference.
-pub enum Guidance {
-    /// The existential variables *must* have the given values if the goal is
-    /// ever to hold, but that alone isn't enough to guarantee the goal will
-    /// actually hold.
-    Definite(Substs),
+pub(crate) fn solver(_db: &impl HirDatabase, _krate: Crate) -> Arc<Mutex<Solver>> {
+    // krate parameter is just so we cache a unique solver per crate
+    let solver_choice = chalk_solve::SolverChoice::SLG { max_size: 10 };
+    Arc::new(Mutex::new(solver_choice.into_solver()))
+}
 
-    /// There are multiple plausible values for the existentials, but the ones
-    /// here are suggested as the preferred choice heuristically. These should
-    /// be used for inference fallback only.
-    Suggested(Substs),
+/// Collects impls for the given trait in the whole dependency tree of `krate`.
+pub(crate) fn impls_for_trait(
+    db: &impl HirDatabase,
+    krate: Crate,
+    trait_: Trait,
+) -> Arc<[ImplBlock]> {
+    let mut impls = Vec::new();
+    // We call the query recursively here. On the one hand, this means we can
+    // reuse results from queries for different crates; on the other hand, this
+    // will only ever get called for a few crates near the root of the tree (the
+    // ones the user is editing), so this may actually be a waste of memory. I'm
+    // doing it like this mainly for simplicity for now.
+    for dep in krate.dependencies(db) {
+        impls.extend(db.impls_for_trait(dep.krate, trait_).iter());
+    }
+    let crate_impl_blocks = db.impls_in_crate(krate);
+    impls.extend(crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_));
+    impls.into()
+}
 
-    /// There's no useful information to feed back to type inference
-    Unknown,
+fn solve(
+    db: &impl HirDatabase,
+    krate: Crate,
+    goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal>>,
+) -> Option<chalk_solve::Solution> {
+    let context = ChalkContext { db, krate };
+    let solver = db.solver(krate);
+    let solution = solver.lock().unwrap().solve(&context, goal);
+    debug!("solve({:?}) => {:?}", goal, solution);
+    solution
 }
 
 /// Something that needs to be proven (by Chalk) during type checking, e.g. that
 /// a certain type implements a certain trait. Proving the Obligation might
 /// result in additional information about inference variables.
-///
-/// This might be handled by Chalk when we integrate it?
 #[derive(Clone, Debug, PartialEq, Eq)]
 pub enum Obligation {
     /// Prove that a certain type implements a trait (the type is the `Self` type
@@ -49,67 +67,94 @@ pub enum Obligation {
     Trait(TraitRef),
 }
 
-/// Rudimentary check whether an impl exists for a given type and trait; this
-/// will actually be done by chalk.
-pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> Option<Solution> {
-    // FIXME use all trait impls in the whole crate graph
-    let krate = trait_ref.trait_.module(db).krate(db);
-    let krate = match krate {
-        Some(krate) => krate,
-        None => return None,
-    };
-    let crate_impl_blocks = db.impls_in_crate(krate);
-    let mut impl_blocks = crate_impl_blocks
-        .lookup_impl_blocks_for_trait(&trait_ref.trait_)
-        // we don't handle where clauses at all, waiting for Chalk for that
-        .filter(|impl_block| impl_block.generic_params(db).where_predicates.is_empty());
-    impl_blocks
-        .find_map(|impl_block| unify_trait_refs(&trait_ref, &impl_block.target_trait_ref(db)?))
+/// Check using Chalk whether trait is implemented for given parameters including `Self` type.
+pub(crate) fn implements(
+    db: &impl HirDatabase,
+    krate: Crate,
+    trait_ref: Canonical<TraitRef>,
+) -> Option<Solution> {
+    let goal: chalk_ir::Goal = trait_ref.value.to_chalk(db).cast();
+    debug!("goal: {:?}", goal);
+    let env = chalk_ir::Environment::new();
+    let in_env = chalk_ir::InEnvironment::new(&env, goal);
+    let parameter = chalk_ir::ParameterKind::Ty(chalk_ir::UniverseIndex::ROOT);
+    let canonical =
+        chalk_ir::Canonical { value: in_env, binders: vec![parameter; trait_ref.num_vars] };
+    // 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 };
+    let solution = solve(db, krate, &u_canonical);
+    solution.map(|solution| solution_from_chalk(db, solution))
 }
 
-pub(super) fn canonicalize(trait_ref: TraitRef) -> (TraitRef, Vec<TypeVarId>) {
-    let mut canonical = HashMap::new(); // mapping uncanonical -> canonical
-    let mut uncanonical = Vec::new(); // mapping canonical -> uncanonical (which is dense)
-    let mut substs = trait_ref.substs.0.to_vec();
-    for ty in &mut substs {
-        ty.walk_mut(&mut |ty| match ty {
-            Ty::Infer(InferTy::TypeVar(tv)) => {
-                let tv: &mut TypeVarId = tv;
-                *tv = *canonical.entry(*tv).or_insert_with(|| {
-                    let i = uncanonical.len();
-                    uncanonical.push(*tv);
-                    TypeVarId(i as u32)
-                });
-            }
-            _ => {}
-        });
+fn solution_from_chalk(db: &impl HirDatabase, solution: chalk_solve::Solution) -> Solution {
+    let convert_subst = |subst: chalk_ir::Canonical<chalk_ir::Substitution>| {
+        let value = subst
+            .value
+            .parameters
+            .into_iter()
+            .map(|p| {
+                let ty = match p {
+                    chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty),
+                    chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(),
+                };
+                ty
+            })
+            .collect();
+        let result = Canonical { value, num_vars: subst.binders.len() };
+        SolutionVariables(result)
+    };
+    match solution {
+        chalk_solve::Solution::Unique(constr_subst) => {
+            let subst = chalk_ir::Canonical {
+                value: constr_subst.value.subst,
+                binders: constr_subst.binders,
+            };
+            Solution::Unique(convert_subst(subst))
+        }
+        chalk_solve::Solution::Ambig(chalk_solve::Guidance::Definite(subst)) => {
+            Solution::Ambig(Guidance::Definite(convert_subst(subst)))
+        }
+        chalk_solve::Solution::Ambig(chalk_solve::Guidance::Suggested(subst)) => {
+            Solution::Ambig(Guidance::Suggested(convert_subst(subst)))
+        }
+        chalk_solve::Solution::Ambig(chalk_solve::Guidance::Unknown) => {
+            Solution::Ambig(Guidance::Unknown)
+        }
     }
-    (TraitRef { substs: substs.into(), ..trait_ref }, uncanonical)
 }
 
-fn unify_trait_refs(tr1: &TraitRef, tr2: &TraitRef) -> Option<Solution> {
-    if tr1.trait_ != tr2.trait_ {
-        return None;
-    }
-    let mut solution_substs = Vec::new();
-    for (t1, t2) in tr1.substs.0.iter().zip(tr2.substs.0.iter()) {
-        // this is very bad / hacky 'unification' logic, just enough to make the simple tests pass
-        match (t1, t2) {
-            (_, Ty::Infer(InferTy::TypeVar(_))) | (_, Ty::Unknown) | (_, Ty::Param { .. }) => {
-                // type variable (or similar) in the impl, we just assume it works
-            }
-            (Ty::Infer(InferTy::TypeVar(v1)), _) => {
-                // type variable in the query and fixed type in the impl, record its value
-                solution_substs.resize_with(v1.0 as usize + 1, || Ty::Unknown);
-                solution_substs[v1.0 as usize] = t2.clone();
-            }
-            _ => {
-                // check that they're equal (actually we'd have to recurse etc.)
-                if t1 != t2 {
-                    return None;
-                }
-            }
-        }
-    }
-    Some(Solution::Unique(solution_substs.into()))
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub(crate) struct SolutionVariables(pub Canonical<Vec<Ty>>);
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+/// A (possible) solution for a proposed goal.
+pub(crate) enum Solution {
+    /// The goal indeed holds, and there is a unique value for all existential
+    /// variables.
+    Unique(SolutionVariables),
+
+    /// The goal may be provable in multiple ways, but regardless we may have some guidance
+    /// for type inference. In this case, we don't return any lifetime
+    /// constraints, since we have not "committed" to any particular solution
+    /// yet.
+    Ambig(Guidance),
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+/// When a goal holds ambiguously (e.g., because there are multiple possible
+/// solutions), we issue a set of *guidance* back to type inference.
+pub(crate) enum Guidance {
+    /// The existential variables *must* have the given values if the goal is
+    /// ever to hold, but that alone isn't enough to guarantee the goal will
+    /// actually hold.
+    Definite(SolutionVariables),
+
+    /// There are multiple plausible values for the existentials, but the ones
+    /// here are suggested as the preferred choice heuristically. These should
+    /// be used for inference fallback only.
+    Suggested(SolutionVariables),
+
+    /// There's no useful information to feed back to type inference
+    Unknown,
 }
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
new file mode 100644
index 000000000..8b77d21b4
--- /dev/null
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -0,0 +1,333 @@
+//! Conversion code from/to Chalk.
+use std::sync::Arc;
+
+use log::debug;
+
+use chalk_ir::{TypeId, ImplId, TypeKindId, ProjectionTy, Parameter, Identifier, cast::Cast, PlaceholderIndex, UniverseIndex, TypeName};
+use chalk_rust_ir::{AssociatedTyDatum, TraitDatum, StructDatum, ImplDatum};
+
+use ra_db::salsa::{InternId, InternKey};
+
+use crate::{
+    Trait, HasGenericParams, ImplBlock,
+    db::HirDatabase,
+    ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs},
+};
+use super::ChalkContext;
+
+pub(super) trait ToChalk {
+    type Chalk;
+    fn to_chalk(self, db: &impl HirDatabase) -> Self::Chalk;
+    fn from_chalk(db: &impl HirDatabase, chalk: Self::Chalk) -> Self;
+}
+
+pub(super) fn from_chalk<T, ChalkT>(db: &impl HirDatabase, chalk: ChalkT) -> T
+where
+    T: ToChalk<Chalk = ChalkT>,
+{
+    T::from_chalk(db, chalk)
+}
+
+impl ToChalk for Ty {
+    type Chalk = chalk_ir::Ty;
+    fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::Ty {
+        match self {
+            Ty::Apply(apply_ty) => {
+                let struct_id = apply_ty.ctor.to_chalk(db);
+                let name = TypeName::TypeKindId(struct_id.into());
+                let parameters = apply_ty.parameters.to_chalk(db);
+                chalk_ir::ApplicationTy { name, parameters }.cast()
+            }
+            Ty::Param { idx, .. } => {
+                PlaceholderIndex { ui: UniverseIndex::ROOT, idx: idx as usize }.to_ty()
+            }
+            Ty::Bound(idx) => chalk_ir::Ty::BoundVar(idx as usize),
+            Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"),
+            // FIXME this is clearly incorrect, but probably not too incorrect
+            // and I'm not sure what to actually do with Ty::Unknown
+            Ty::Unknown => PlaceholderIndex { ui: UniverseIndex::ROOT, idx: 0 }.to_ty(),
+        }
+    }
+    fn from_chalk(db: &impl HirDatabase, chalk: chalk_ir::Ty) -> Self {
+        match chalk {
+            chalk_ir::Ty::Apply(apply_ty) => {
+                match apply_ty.name {
+                    TypeName::TypeKindId(TypeKindId::StructId(struct_id)) => {
+                        let ctor = from_chalk(db, struct_id);
+                        let parameters = from_chalk(db, apply_ty.parameters);
+                        Ty::Apply(ApplicationTy { ctor, parameters })
+                    }
+                    // FIXME handle TypeKindId::Trait/Type here
+                    TypeName::TypeKindId(_) => unimplemented!(),
+                    TypeName::AssociatedType(_) => unimplemented!(),
+                    TypeName::Placeholder(idx) => {
+                        assert_eq!(idx.ui, UniverseIndex::ROOT);
+                        Ty::Param { idx: idx.idx as u32, name: crate::Name::missing() }
+                    }
+                }
+            }
+            chalk_ir::Ty::Projection(_) => unimplemented!(),
+            chalk_ir::Ty::UnselectedProjection(_) => unimplemented!(),
+            chalk_ir::Ty::ForAll(_) => unimplemented!(),
+            chalk_ir::Ty::BoundVar(idx) => Ty::Bound(idx as u32),
+            chalk_ir::Ty::InferenceVar(_iv) => panic!("unexpected chalk infer ty"),
+        }
+    }
+}
+
+impl ToChalk for Substs {
+    type Chalk = Vec<chalk_ir::Parameter>;
+
+    fn to_chalk(self, db: &impl HirDatabase) -> Vec<Parameter> {
+        self.iter().map(|ty| ty.clone().to_chalk(db).cast()).collect()
+    }
+
+    fn from_chalk(db: &impl HirDatabase, parameters: Vec<chalk_ir::Parameter>) -> Substs {
+        parameters
+            .into_iter()
+            .map(|p| match p {
+                chalk_ir::Parameter(chalk_ir::ParameterKind::Ty(ty)) => from_chalk(db, ty),
+                chalk_ir::Parameter(chalk_ir::ParameterKind::Lifetime(_)) => unimplemented!(),
+            })
+            .collect::<Vec<_>>()
+            .into()
+    }
+}
+
+impl ToChalk for TraitRef {
+    type Chalk = chalk_ir::TraitRef;
+
+    fn to_chalk(self: TraitRef, db: &impl HirDatabase) -> chalk_ir::TraitRef {
+        let trait_id = self.trait_.to_chalk(db);
+        let parameters = self.substs.to_chalk(db);
+        chalk_ir::TraitRef { trait_id, parameters }
+    }
+
+    fn from_chalk(db: &impl HirDatabase, trait_ref: chalk_ir::TraitRef) -> Self {
+        let trait_ = from_chalk(db, trait_ref.trait_id);
+        let substs = from_chalk(db, trait_ref.parameters);
+        TraitRef { trait_, substs }
+    }
+}
+
+impl ToChalk for Trait {
+    type Chalk = chalk_ir::TraitId;
+
+    fn to_chalk(self, _db: &impl HirDatabase) -> chalk_ir::TraitId {
+        self.id.into()
+    }
+
+    fn from_chalk(_db: &impl HirDatabase, trait_id: chalk_ir::TraitId) -> Trait {
+        Trait { id: trait_id.into() }
+    }
+}
+
+impl ToChalk for TypeCtor {
+    type Chalk = chalk_ir::StructId;
+
+    fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::StructId {
+        db.intern_type_ctor(self).into()
+    }
+
+    fn from_chalk(db: &impl HirDatabase, struct_id: chalk_ir::StructId) -> TypeCtor {
+        db.lookup_intern_type_ctor(struct_id.into())
+    }
+}
+
+impl ToChalk for ImplBlock {
+    type Chalk = chalk_ir::ImplId;
+
+    fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::ImplId {
+        db.intern_impl_block(self).into()
+    }
+
+    fn from_chalk(db: &impl HirDatabase, impl_id: chalk_ir::ImplId) -> ImplBlock {
+        db.lookup_intern_impl_block(impl_id.into())
+    }
+}
+
+fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> {
+    chalk_ir::Binders {
+        value,
+        binders: std::iter::repeat(chalk_ir::ParameterKind::Ty(())).take(num_vars).collect(),
+    }
+}
+
+impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB>
+where
+    DB: HirDatabase,
+{
+    fn associated_ty_data(&self, _ty: TypeId) -> Arc<AssociatedTyDatum> {
+        unimplemented!()
+    }
+    fn trait_datum(&self, trait_id: chalk_ir::TraitId) -> Arc<TraitDatum> {
+        debug!("trait_datum {:?}", trait_id);
+        let trait_: Trait = from_chalk(self.db, trait_id);
+        let generic_params = trait_.generic_params(self.db);
+        let bound_vars = Substs::bound_vars(&generic_params);
+        let trait_ref = trait_.trait_ref(self.db).subst(&bound_vars).to_chalk(self.db);
+        let flags = chalk_rust_ir::TraitFlags {
+            // FIXME set these flags correctly
+            auto: false,
+            marker: false,
+            upstream: trait_.module(self.db).krate(self.db) != Some(self.krate),
+            fundamental: false,
+        };
+        let where_clauses = Vec::new(); // FIXME add where clauses
+        let associated_ty_ids = Vec::new(); // FIXME add associated tys
+        let trait_datum_bound =
+            chalk_rust_ir::TraitDatumBound { trait_ref, where_clauses, flags, associated_ty_ids };
+        let trait_datum = TraitDatum { binders: make_binders(trait_datum_bound, bound_vars.len()) };
+        Arc::new(trait_datum)
+    }
+    fn struct_datum(&self, struct_id: chalk_ir::StructId) -> Arc<StructDatum> {
+        debug!("struct_datum {:?}", struct_id);
+        let type_ctor = from_chalk(self.db, struct_id);
+        // FIXME might be nicer if we can create a fake GenericParams for the TypeCtor
+        // FIXME extract this to a method on Ty
+        let (num_params, upstream) = match type_ctor {
+            TypeCtor::Bool
+            | TypeCtor::Char
+            | TypeCtor::Int(_)
+            | TypeCtor::Float(_)
+            | TypeCtor::Never
+            | TypeCtor::Str => (0, true),
+            TypeCtor::Slice | TypeCtor::Array | TypeCtor::RawPtr(_) | TypeCtor::Ref(_) => (1, true),
+            TypeCtor::FnPtr { num_args } => (num_args as usize + 1, true),
+            TypeCtor::Tuple { cardinality } => (cardinality as usize, true),
+            TypeCtor::FnDef(_) => unimplemented!(),
+            TypeCtor::Adt(adt) => {
+                let generic_params = adt.generic_params(self.db);
+                (
+                    generic_params.count_params_including_parent(),
+                    adt.krate(self.db) != Some(self.krate),
+                )
+            }
+        };
+        let flags = chalk_rust_ir::StructFlags {
+            upstream,
+            // FIXME set fundamental flag correctly
+            fundamental: false,
+        };
+        let where_clauses = Vec::new(); // FIXME add where clauses
+        let self_ty = chalk_ir::ApplicationTy {
+            name: TypeName::TypeKindId(type_ctor.to_chalk(self.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) };
+        Arc::new(struct_datum)
+    }
+    fn impl_datum(&self, impl_id: ImplId) -> Arc<ImplDatum> {
+        debug!("impl_datum {:?}", impl_id);
+        let impl_block: ImplBlock = from_chalk(self.db, impl_id);
+        let generic_params = impl_block.generic_params(self.db);
+        let bound_vars = Substs::bound_vars(&generic_params);
+        let trait_ref = impl_block
+            .target_trait_ref(self.db)
+            .expect("FIXME handle unresolved impl block trait ref")
+            .subst(&bound_vars);
+        let impl_type = if impl_block.module().krate(self.db) == Some(self.krate) {
+            chalk_rust_ir::ImplType::Local
+        } else {
+            chalk_rust_ir::ImplType::External
+        };
+        let impl_datum_bound = chalk_rust_ir::ImplDatumBound {
+            // FIXME handle negative impls (impl !Sync for Foo)
+            trait_ref: chalk_rust_ir::PolarizedTraitRef::Positive(trait_ref.to_chalk(self.db)),
+            where_clauses: Vec::new(),        // FIXME add where clauses
+            associated_ty_values: Vec::new(), // FIXME add associated type values
+            impl_type,
+        };
+        let impl_datum = ImplDatum { binders: make_binders(impl_datum_bound, bound_vars.len()) };
+        Arc::new(impl_datum)
+    }
+    fn impls_for_trait(&self, trait_id: chalk_ir::TraitId) -> Vec<ImplId> {
+        debug!("impls_for_trait {:?}", trait_id);
+        let trait_ = from_chalk(self.db, trait_id);
+        self.db
+            .impls_for_trait(self.krate, trait_)
+            .iter()
+            // FIXME temporary hack -- as long as we're not lowering where clauses
+            // correctly, ignore impls with them completely so as to not treat
+            // impl<T> Trait for T where T: ... as a blanket impl on all types
+            .filter(|impl_block| impl_block.generic_params(self.db).where_predicates.is_empty())
+            .map(|impl_block| impl_block.to_chalk(self.db))
+            .collect()
+    }
+    fn impl_provided_for(
+        &self,
+        auto_trait_id: chalk_ir::TraitId,
+        struct_id: chalk_ir::StructId,
+    ) -> bool {
+        debug!("impl_provided_for {:?}, {:?}", auto_trait_id, struct_id);
+        false // FIXME
+    }
+    fn type_name(&self, _id: TypeKindId) -> Identifier {
+        unimplemented!()
+    }
+    fn split_projection<'p>(
+        &self,
+        projection: &'p ProjectionTy,
+    ) -> (Arc<AssociatedTyDatum>, &'p [Parameter], &'p [Parameter]) {
+        debug!("split_projection {:?}", projection);
+        unimplemented!()
+    }
+    fn custom_clauses(&self) -> Vec<chalk_ir::ProgramClause> {
+        debug!("custom_clauses");
+        vec![]
+    }
+    fn all_structs(&self) -> Vec<chalk_ir::StructId> {
+        debug!("all_structs");
+        // FIXME
+        vec![]
+    }
+}
+
+fn id_from_chalk<T: InternKey>(chalk_id: chalk_ir::RawId) -> T {
+    T::from_intern_id(InternId::from(chalk_id.index))
+}
+fn id_to_chalk<T: InternKey>(salsa_id: T) -> chalk_ir::RawId {
+    chalk_ir::RawId { index: salsa_id.as_intern_id().as_u32() }
+}
+
+impl From<chalk_ir::TraitId> for crate::ids::TraitId {
+    fn from(trait_id: chalk_ir::TraitId) -> Self {
+        id_from_chalk(trait_id.0)
+    }
+}
+
+impl From<crate::ids::TraitId> for chalk_ir::TraitId {
+    fn from(trait_id: crate::ids::TraitId) -> Self {
+        chalk_ir::TraitId(id_to_chalk(trait_id))
+    }
+}
+
+impl From<chalk_ir::StructId> for crate::ids::TypeCtorId {
+    fn from(struct_id: chalk_ir::StructId) -> Self {
+        id_from_chalk(struct_id.0)
+    }
+}
+
+impl From<crate::ids::TypeCtorId> for chalk_ir::StructId {
+    fn from(type_ctor_id: crate::ids::TypeCtorId) -> Self {
+        chalk_ir::StructId(id_to_chalk(type_ctor_id))
+    }
+}
+
+impl From<chalk_ir::ImplId> for crate::ids::GlobalImplId {
+    fn from(impl_id: chalk_ir::ImplId) -> Self {
+        id_from_chalk(impl_id.0)
+    }
+}
+
+impl From<crate::ids::GlobalImplId> for chalk_ir::ImplId {
+    fn from(impl_id: crate::ids::GlobalImplId) -> Self {
+        chalk_ir::ImplId(id_to_chalk(impl_id))
+    }
+}