Merge #5319

5319: Chalk upgrade r=flodiebold a=flodiebold

 - upgrade Chalk
 - make use of Chalk's `Unsize` impls, remove ours
 - use Chalk's built-in array type
 - search efficiently for impls for an int/float variable
 - output Chalk tracing logs in hir_ty tests

Fixes #2534.
Fixes #5057.
Fixes #4374.
Fixes #4281.

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

11 files changed, 338 insertions, 335 deletions

diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index a45febbf7..fb4b30a13 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -6,8 +6,10 @@ use std::{iter, sync::Arc};
 
 use arrayvec::ArrayVec;
 use hir_def::{
-    lang_item::LangItemTarget, type_ref::Mutability, AssocContainerId, AssocItemId, FunctionId,
-    HasModule, ImplId, Lookup, TraitId,
+    builtin_type::{IntBitness, Signedness},
+    lang_item::LangItemTarget,
+    type_ref::Mutability,
+    AssocContainerId, AssocItemId, FunctionId, HasModule, ImplId, Lookup, TraitId,
 };
 use hir_expand::name::Name;
 use ra_db::CrateId;
@@ -16,9 +18,12 @@ use rustc_hash::{FxHashMap, FxHashSet};
 
 use super::Substs;
 use crate::{
-    autoderef, db::HirDatabase, primitive::FloatBitness, utils::all_super_traits, ApplicationTy,
-    Canonical, DebruijnIndex, InEnvironment, TraitEnvironment, TraitRef, Ty, TyKind, TypeCtor,
-    TypeWalk,
+    autoderef,
+    db::HirDatabase,
+    primitive::{FloatBitness, FloatTy, IntTy},
+    utils::all_super_traits,
+    ApplicationTy, Canonical, DebruijnIndex, InEnvironment, TraitEnvironment, TraitRef, Ty, TyKind,
+    TypeCtor, TypeWalk,
 };
 
 /// This is used as a key for indexing impls.
@@ -39,6 +44,62 @@ impl TyFingerprint {
     }
 }
 
+pub(crate) const ALL_INT_FPS: [TyFingerprint; 12] = [
+    TyFingerprint::Apply(TypeCtor::Int(IntTy {
+        signedness: Signedness::Unsigned,
+        bitness: IntBitness::X8,
+    })),
+    TyFingerprint::Apply(TypeCtor::Int(IntTy {
+        signedness: Signedness::Unsigned,
+        bitness: IntBitness::X16,
+    })),
+    TyFingerprint::Apply(TypeCtor::Int(IntTy {
+        signedness: Signedness::Unsigned,
+        bitness: IntBitness::X32,
+    })),
+    TyFingerprint::Apply(TypeCtor::Int(IntTy {
+        signedness: Signedness::Unsigned,
+        bitness: IntBitness::X64,
+    })),
+    TyFingerprint::Apply(TypeCtor::Int(IntTy {
+        signedness: Signedness::Unsigned,
+        bitness: IntBitness::X128,
+    })),
+    TyFingerprint::Apply(TypeCtor::Int(IntTy {
+        signedness: Signedness::Unsigned,
+        bitness: IntBitness::Xsize,
+    })),
+    TyFingerprint::Apply(TypeCtor::Int(IntTy {
+        signedness: Signedness::Signed,
+        bitness: IntBitness::X8,
+    })),
+    TyFingerprint::Apply(TypeCtor::Int(IntTy {
+        signedness: Signedness::Signed,
+        bitness: IntBitness::X16,
+    })),
+    TyFingerprint::Apply(TypeCtor::Int(IntTy {
+        signedness: Signedness::Signed,
+        bitness: IntBitness::X32,
+    })),
+    TyFingerprint::Apply(TypeCtor::Int(IntTy {
+        signedness: Signedness::Signed,
+        bitness: IntBitness::X64,
+    })),
+    TyFingerprint::Apply(TypeCtor::Int(IntTy {
+        signedness: Signedness::Signed,
+        bitness: IntBitness::X128,
+    })),
+    TyFingerprint::Apply(TypeCtor::Int(IntTy {
+        signedness: Signedness::Signed,
+        bitness: IntBitness::Xsize,
+    })),
+];
+
+pub(crate) const ALL_FLOAT_FPS: [TyFingerprint; 2] = [
+    TyFingerprint::Apply(TypeCtor::Float(FloatTy { bitness: FloatBitness::X32 })),
+    TyFingerprint::Apply(TypeCtor::Float(FloatTy { bitness: FloatBitness::X64 })),
+];
+
 /// Trait impls defined or available in some crate.
 #[derive(Debug, Eq, PartialEq)]
 pub struct TraitImpls {
diff --git a/crates/ra_hir_ty/src/tests.rs b/crates/ra_hir_ty/src/tests.rs
index 69f2d7667..27f5a60bf 100644
--- a/crates/ra_hir_ty/src/tests.rs
+++ b/crates/ra_hir_ty/src/tests.rs
@@ -37,6 +37,15 @@ use crate::{
 // against snapshots of the expected results using insta. Use cargo-insta to
 // update the snapshots.
 
+fn setup_tracing() -> tracing::subscriber::DefaultGuard {
+    use tracing_subscriber::{layer::SubscriberExt, EnvFilter, Registry};
+    use tracing_tree::HierarchicalLayer;
+    let filter = EnvFilter::from_env("CHALK_DEBUG");
+    let layer = HierarchicalLayer::default().with_indent_amount(2).with_writer(std::io::stderr);
+    let subscriber = Registry::default().with(filter).with(layer);
+    tracing::subscriber::set_default(subscriber)
+}
+
 fn check_types(ra_fixture: &str) {
     check_types_impl(ra_fixture, false)
 }
@@ -46,6 +55,7 @@ fn check_types_source_code(ra_fixture: &str) {
 }
 
 fn check_types_impl(ra_fixture: &str, display_source: bool) {
+    let _tracing = setup_tracing();
     let db = TestDB::with_files(ra_fixture);
     let mut checked_one = false;
     for (file_id, annotations) in db.extract_annotations() {
@@ -86,6 +96,7 @@ fn infer(ra_fixture: &str) -> String {
 }
 
 fn infer_with_mismatches(content: &str, include_mismatches: bool) -> String {
+    let _tracing = setup_tracing();
     let (db, file_id) = TestDB::with_single_file(content);
 
     let mut buf = String::new();
diff --git a/crates/ra_hir_ty/src/tests/coercion.rs b/crates/ra_hir_ty/src/tests/coercion.rs
index 136d28a91..d7fb6a962 100644
--- a/crates/ra_hir_ty/src/tests/coercion.rs
+++ b/crates/ra_hir_ty/src/tests/coercion.rs
@@ -662,7 +662,53 @@ fn test() {
 }
 
 #[test]
-fn coerce_unsize_trait_object() {
+fn coerce_unsize_trait_object_simple() {
+    assert_snapshot!(
+        infer_with_mismatches(r#"
+#[lang = "sized"]
+pub trait Sized {}
+#[lang = "unsize"]
+pub trait Unsize<T> {}
+#[lang = "coerce_unsized"]
+pub trait CoerceUnsized<T> {}
+
+impl<T: Unsize<U>, U> CoerceUnsized<&U> for &T {}
+
+trait Foo<T, U> {}
+trait Bar<U, T, X>: Foo<T, U> {}
+trait Baz<T, X>: Bar<usize, T, X> {}
+
+struct S<T, X>;
+impl<T, X> Foo<T, usize> for S<T, X> {}
+impl<T, X> Bar<usize, T, X> for S<T, X> {}
+impl<T, X> Baz<T, X> for S<T, X> {}
+
+fn test() {
+    let obj: &dyn Baz<i8, i16> = &S;
+    let obj: &dyn Bar<_, i8, i16> = &S;
+    let obj: &dyn Foo<i8, _> = &S;
+}
+"#, true),
+        @r###"
+    424..539 '{     ... &S; }': ()
+    434..437 'obj': &dyn Baz<i8, i16>
+    459..461 '&S': &S<i8, i16>
+    460..461 'S': S<i8, i16>
+    471..474 'obj': &dyn Bar<usize, i8, i16>
+    499..501 '&S': &S<i8, i16>
+    500..501 'S': S<i8, i16>
+    511..514 'obj': &dyn Foo<i8, usize>
+    534..536 '&S': &S<i8, {unknown}>
+    535..536 'S': S<i8, {unknown}>
+    "###
+    );
+}
+
+#[test]
+// The rust reference says this should be possible, but rustc doesn't implement
+// it. We used to support it, but Chalk doesn't.
+#[ignore]
+fn coerce_unsize_trait_object_to_trait_object() {
     assert_snapshot!(
         infer_with_mismatches(r#"
 #[lang = "sized"]
@@ -735,16 +781,17 @@ impl D for S {}
 
 fn test() {
     let obj: &dyn D = &S;
-    let obj: &dyn A = obj;
+    let obj: &dyn A = &S;
 }
 "#, true),
         @r###"
-    328..384 '{     ...obj; }': ()
+    328..383 '{     ... &S; }': ()
     338..341 'obj': &dyn D
     352..354 '&S': &S
     353..354 'S': S
     364..367 'obj': &dyn A
-    378..381 'obj': &dyn D
+    378..380 '&S': &S
+    379..380 'S': S
     "###
     );
 }
diff --git a/crates/ra_hir_ty/src/tests/traits.rs b/crates/ra_hir_ty/src/tests/traits.rs
index 529d9e253..27737fa94 100644
--- a/crates/ra_hir_ty/src/tests/traits.rs
+++ b/crates/ra_hir_ty/src/tests/traits.rs
@@ -1992,6 +1992,28 @@ fn test() {
 }
 
 #[test]
+fn fn_item_fn_trait() {
+    check_types(
+        r#"
+#[lang = "fn_once"]
+trait FnOnce<Args> {
+    type Output;
+}
+
+struct S;
+
+fn foo() -> S {}
+
+fn takes_closure<U, F: FnOnce() -> U>(f: F) -> U { f() }
+
+fn test() {
+    takes_closure(foo);
+} //^^^^^^^^^^^^^^^^^^ S
+"#,
+    );
+}
+
+#[test]
 fn unselected_projection_in_trait_env_1() {
     check_types(
         r#"
@@ -3000,74 +3022,47 @@ fn infer_box_fn_arg() {
 
 #[test]
 fn infer_dyn_fn_output() {
-    assert_snapshot!(
-        infer(
-            r#"
-            //- /lib.rs deps:std
-
-            #[lang = "fn_once"]
-            pub trait FnOnce<Args> {
-                type Output;
-
-                extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
-            }
-
-            #[lang = "fn"]
-            pub trait Fn<Args>:FnOnce<Args> {
-                extern "rust-call" fn call(&self, args: Args) -> Self::Output;
-            }
-
-            #[lang = "deref"]
-            pub trait Deref {
-                type Target: ?Sized;
-
-                fn deref(&self) -> &Self::Target;
-            }
+    check_types(
+        r#"
+#[lang = "fn_once"]
+pub trait FnOnce<Args> {
+    type Output;
+    extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
+}
 
-            #[lang = "owned_box"]
-            pub struct Box<T: ?Sized> {
-                inner: *mut T,
-            }
+#[lang = "fn"]
+pub trait Fn<Args>: FnOnce<Args> {
+    extern "rust-call" fn call(&self, args: Args) -> Self::Output;
+}
 
-            impl<T: ?Sized> Deref for Box<T> {
-                type Target = T;
+fn foo() {
+    let f: &dyn Fn() -> i32;
+    f();
+  //^^^ i32
+}"#,
+    );
+}
 
-                fn deref(&self) -> &T {
-                    &self.inner
-                }
-            }
+#[test]
+fn infer_dyn_fn_once_output() {
+    check_types(
+        r#"
+#[lang = "fn_once"]
+pub trait FnOnce<Args> {
+    type Output;
+    extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
+}
 
-            fn foo() {
-                let f: Box<dyn Fn() -> i32> = box(|| 5);
-                let x = f();
-            }
-        "#
-        ),
-        @r###"
-    100..104 'self': Self
-    106..110 'args': Args
-    219..223 'self': &Self
-    225..229 'args': Args
-    333..337 'self': &Self
-    503..507 'self': &Box<T>
-    515..542 '{     ...     }': &T
-    525..536 '&self.inner': &*mut T
-    526..530 'self': &Box<T>
-    526..536 'self.inner': *mut T
-    555..620 '{     ...f(); }': ()
-    565..566 'f': Box<dyn Fn<(), Output = i32>>
-    591..600 'box(|| 5)': Box<|| -> i32>
-    595..599 '|| 5': || -> i32
-    598..599 '5': i32
-    610..611 'x': FnOnce::Output<dyn Fn<(), Output = i32>, ()>
-    614..615 'f': Box<dyn Fn<(), Output = i32>>
-    614..617 'f()': FnOnce::Output<dyn Fn<(), Output = i32>, ()>
-    "###
+fn foo() {
+    let f: dyn FnOnce() -> i32;
+    f();
+  //^^^ i32
+}"#,
     );
 }
 
 #[test]
-fn variable_kinds() {
+fn variable_kinds_1() {
     check_types(
         r#"
 trait Trait<T> { fn get(self, t: T) -> T; }
@@ -3083,3 +3078,20 @@ fn test() {
         "#,
     );
 }
+
+#[test]
+fn variable_kinds_2() {
+    check_types(
+        r#"
+trait Trait { fn get(self) -> Self; }
+impl Trait for u128 {}
+impl Trait for f32 {}
+fn test() {
+    1.get();
+  //^^^^^^^ u128
+    (1.).get();
+  //^^^^^^^^^^ f32
+}
+        "#,
+    );
+}
diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs
index 2a6d7faef..f7edb4c8b 100644
--- a/crates/ra_hir_ty/src/traits.rs
+++ b/crates/ra_hir_ty/src/traits.rs
@@ -2,6 +2,7 @@
 use std::sync::Arc;
 
 use chalk_ir::cast::Cast;
+use chalk_solve::Solver;
 use hir_def::{
     expr::ExprId, lang_item::LangItemTarget, DefWithBodyId, ImplId, TraitId, TypeAliasId,
 };
@@ -32,9 +33,10 @@ struct ChalkContext<'a> {
     krate: CrateId,
 }
 
-fn create_chalk_solver() -> chalk_solve::Solver<Interner> {
-    let solver_choice = chalk_solve::SolverChoice::recursive();
-    solver_choice.into_solver()
+fn create_chalk_solver() -> chalk_recursive::RecursiveSolver<Interner> {
+    let overflow_depth = 100;
+    let caching_enabled = true;
+    chalk_recursive::RecursiveSolver::new(overflow_depth, caching_enabled)
 }
 
 /// A set of clauses that we assume to be true. E.g. if we are inside this function:
@@ -293,13 +295,8 @@ pub enum Impl {
     /// A normal impl from an impl block.
     ImplDef(ImplId),
     /// Closure types implement the Fn traits synthetically.
+    // FIXME: implement closure support from Chalk, remove this
     ClosureFnTraitImpl(ClosureFnTraitImplData),
-    /// [T; n]: Unsize<[T]>
-    UnsizeArray,
-    /// T: Unsize<dyn Trait> where T: Trait
-    UnsizeToTraitObject(TraitId),
-    /// dyn Trait: Unsize<dyn SuperTrait> if Trait: SuperTrait
-    UnsizeToSuperTraitObject(UnsizeToSuperTraitObjectData),
 }
 /// This exists just for Chalk, because our ImplIds are only unique per module.
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
diff --git a/crates/ra_hir_ty/src/traits/builtin.rs b/crates/ra_hir_ty/src/traits/builtin.rs
index 6d5f2d46a..86e22e459 100644
--- a/crates/ra_hir_ty/src/traits/builtin.rs
+++ b/crates/ra_hir_ty/src/traits/builtin.rs
@@ -1,15 +1,12 @@
 //! This module provides the built-in trait implementations, e.g. to make
 //! closures implement `Fn`.
-use hir_def::{expr::Expr, lang_item::LangItemTarget, TraitId, TypeAliasId};
+use hir_def::{expr::Expr, TraitId, TypeAliasId};
 use hir_expand::name::name;
 use ra_db::CrateId;
 
-use super::{AssocTyValue, Impl, UnsizeToSuperTraitObjectData};
+use super::{AssocTyValue, Impl};
 use crate::{
-    db::HirDatabase,
-    utils::{all_super_traits, generics},
-    ApplicationTy, Binders, BoundVar, DebruijnIndex, GenericPredicate, Substs, TraitRef, Ty,
-    TypeCtor, TypeWalk,
+    db::HirDatabase, ApplicationTy, BoundVar, DebruijnIndex, Substs, TraitRef, Ty, TypeCtor,
 };
 
 pub(super) struct BuiltinImplData {
@@ -31,7 +28,7 @@ pub(super) fn get_builtin_impls(
     krate: CrateId,
     ty: &Ty,
     // The first argument for the trait, if present
-    arg: &Option<Ty>,
+    _arg: &Option<Ty>,
     trait_: TraitId,
     mut callback: impl FnMut(Impl),
 ) {
@@ -50,60 +47,12 @@ pub(super) fn get_builtin_impls(
             }
         }
     }
-
-    let unsize_trait = get_unsize_trait(db, krate);
-    if let Some(actual_trait) = unsize_trait {
-        if trait_ == actual_trait {
-            get_builtin_unsize_impls(db, krate, ty, arg, callback);
-        }
-    }
-}
-
-fn get_builtin_unsize_impls(
-    db: &dyn HirDatabase,
-    krate: CrateId,
-    ty: &Ty,
-    // The first argument for the trait, if present
-    arg: &Option<Ty>,
-    mut callback: impl FnMut(Impl),
-) {
-    if !check_unsize_impl_prerequisites(db, krate) {
-        return;
-    }
-
-    if let Ty::Apply(ApplicationTy { ctor: TypeCtor::Array, .. }) = ty {
-        callback(Impl::UnsizeArray);
-        return; // array is unsized, the rest of the impls shouldn't apply
-    }
-
-    if let Some(target_trait) = arg.as_ref().and_then(|t| t.dyn_trait_ref()) {
-        // FIXME what about more complicated dyn tys with marker traits?
-        if let Some(trait_ref) = ty.dyn_trait_ref() {
-            if trait_ref.trait_ != target_trait.trait_ {
-                let super_traits = all_super_traits(db.upcast(), trait_ref.trait_);
-                if super_traits.contains(&target_trait.trait_) {
-                    callback(Impl::UnsizeToSuperTraitObject(UnsizeToSuperTraitObjectData {
-                        trait_: trait_ref.trait_,
-                        super_trait: target_trait.trait_,
-                    }));
-                }
-            }
-        } else {
-            // FIXME only for sized types
-            callback(Impl::UnsizeToTraitObject(target_trait.trait_));
-        }
-    }
 }
 
 pub(super) fn impl_datum(db: &dyn HirDatabase, krate: CrateId, impl_: Impl) -> BuiltinImplData {
     match impl_ {
         Impl::ImplDef(_) => unreachable!(),
         Impl::ClosureFnTraitImpl(data) => closure_fn_trait_impl_datum(db, krate, data),
-        Impl::UnsizeArray => array_unsize_impl_datum(db, krate),
-        Impl::UnsizeToTraitObject(trait_) => trait_object_unsize_impl_datum(db, krate, trait_),
-        Impl::UnsizeToSuperTraitObject(data) => {
-            super_trait_object_unsize_impl_datum(db, krate, data)
-        }
     }
 }
 
@@ -227,145 +176,3 @@ fn closure_fn_trait_output_assoc_ty_value(
         value: output_ty,
     }
 }
-
-// Array unsizing
-
-fn check_unsize_impl_prerequisites(db: &dyn HirDatabase, krate: CrateId) -> bool {
-    // the Unsize trait needs to exist and have two type parameters (Self and T)
-    let unsize_trait = match get_unsize_trait(db, krate) {
-        Some(t) => t,
-        None => return false,
-    };
-    let generic_params = generics(db.upcast(), unsize_trait.into());
-    generic_params.len() == 2
-}
-
-fn array_unsize_impl_datum(db: &dyn HirDatabase, krate: CrateId) -> BuiltinImplData {
-    // impl<T> Unsize<[T]> for [T; _]
-    // (this can be a single impl because we don't distinguish array sizes currently)
-
-    let trait_ = get_unsize_trait(db, krate) // get unsize trait
-        // the existence of the Unsize trait has been checked before
-        .expect("Unsize trait missing");
-
-    let var = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0));
-    let substs = Substs::builder(2)
-        .push(Ty::apply_one(TypeCtor::Array, var.clone()))
-        .push(Ty::apply_one(TypeCtor::Slice, var))
-        .build();
-
-    let trait_ref = TraitRef { trait_, substs };
-
-    BuiltinImplData {
-        num_vars: 1,
-        trait_ref,
-        where_clauses: Vec::new(),
-        assoc_ty_values: Vec::new(),
-    }
-}
-
-// Trait object unsizing
-
-fn trait_object_unsize_impl_datum(
-    db: &dyn HirDatabase,
-    krate: CrateId,
-    trait_: TraitId,
-) -> BuiltinImplData {
-    // impl<T, T1, ...> Unsize<dyn Trait<T1, ...>> for T where T: Trait<T1, ...>
-
-    let unsize_trait = get_unsize_trait(db, krate) // get unsize trait
-        // the existence of the Unsize trait has been checked before
-        .expect("Unsize trait missing");
-
-    let self_ty = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0));
-
-    let target_substs = Substs::build_for_def(db, trait_)
-        .push(Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0)))
-        .fill_with_bound_vars(DebruijnIndex::ONE, 1)
-        .build();
-    let num_vars = target_substs.len();
-    let target_trait_ref = TraitRef { trait_, substs: target_substs };
-    let target_bounds = vec![GenericPredicate::Implemented(target_trait_ref)];
-
-    let self_substs =
-        Substs::build_for_def(db, trait_).fill_with_bound_vars(DebruijnIndex::INNERMOST, 0).build();
-    let self_trait_ref = TraitRef { trait_, substs: self_substs };
-    let where_clauses = vec![GenericPredicate::Implemented(self_trait_ref)];
-
-    let impl_substs = Substs::builder(2).push(self_ty).push(Ty::Dyn(target_bounds.into())).build();
-
-    let trait_ref = TraitRef { trait_: unsize_trait, substs: impl_substs };
-
-    BuiltinImplData { num_vars, trait_ref, where_clauses, assoc_ty_values: Vec::new() }
-}
-
-fn super_trait_object_unsize_impl_datum(
-    db: &dyn HirDatabase,
-    krate: CrateId,
-    data: UnsizeToSuperTraitObjectData,
-) -> BuiltinImplData {
-    // impl<T1, ...> Unsize<dyn SuperTrait> for dyn Trait<T1, ...>
-
-    let unsize_trait = get_unsize_trait(db, krate) // get unsize trait
-        // the existence of the Unsize trait has been checked before
-        .expect("Unsize trait missing");
-
-    let self_substs = Substs::build_for_def(db, data.trait_)
-        .fill_with_bound_vars(DebruijnIndex::INNERMOST, 0)
-        .build();
-    let self_trait_ref = TraitRef { trait_: data.trait_, substs: self_substs.clone() };
-
-    let num_vars = self_substs.len() - 1;
-
-    // we need to go from our trait to the super trait, substituting type parameters
-    let path = crate::utils::find_super_trait_path(db.upcast(), data.trait_, data.super_trait);
-
-    let mut current_trait_ref = self_trait_ref.clone();
-    for t in path.into_iter().skip(1) {
-        let bounds = db.generic_predicates(current_trait_ref.trait_.into());
-        let super_trait_ref = bounds
-            .iter()
-            .find_map(|b| match &b.value {
-                GenericPredicate::Implemented(tr)
-                    if tr.trait_ == t
-                        && tr.substs[0]
-                            == Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0)) =>
-                {
-                    Some(Binders { value: tr, num_binders: b.num_binders })
-                }
-                _ => None,
-            })
-            .expect("trait bound for known super trait not found");
-        current_trait_ref = super_trait_ref.cloned().subst(&current_trait_ref.substs);
-    }
-
-    // We need to renumber the variables a bit now: from ^0.0, ^0.1, ^0.2, ...
-    // to ^0.0, ^1.0, ^1.1. The reason for this is that the first variable comes
-    // from the dyn Trait binder, while the other variables come from the impl.
-    let new_substs = Substs::builder(num_vars + 1)
-        .push(Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0)))
-        .fill_with_bound_vars(DebruijnIndex::ONE, 0)
-        .build();
-
-    let self_bounds =
-        vec![GenericPredicate::Implemented(self_trait_ref.subst_bound_vars(&new_substs))];
-    let super_bounds =
-        vec![GenericPredicate::Implemented(current_trait_ref.subst_bound_vars(&new_substs))];
-
-    let substs = Substs::builder(2)
-        .push(Ty::Dyn(self_bounds.into()))
-        .push(Ty::Dyn(super_bounds.into()))
-        .build();
-
-    let trait_ref = TraitRef { trait_: unsize_trait, substs };
-
-    BuiltinImplData { num_vars, trait_ref, where_clauses: Vec::new(), assoc_ty_values: Vec::new() }
-}
-
-fn get_unsize_trait(db: &dyn HirDatabase, krate: CrateId) -> Option<TraitId> {
-    let target = db.lang_item(krate, "unsize".into())?;
-    match target {
-        LangItemTarget::TraitId(t) => Some(t),
-        _ => None,
-    }
-}
diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs
index c97b81d57..c448aea65 100644
--- a/crates/ra_hir_ty/src/traits/chalk.rs
+++ b/crates/ra_hir_ty/src/traits/chalk.rs
@@ -3,7 +3,7 @@ use std::sync::Arc;
 
 use log::debug;
 
-use chalk_ir::{fold::shift::Shift, GenericArg, TypeName};
+use chalk_ir::{fold::shift::Shift, CanonicalVarKinds, GenericArg, TypeName};
 use chalk_solve::rust_ir::{self, OpaqueTyDatumBound, WellKnownTrait};
 
 use hir_def::{
@@ -14,7 +14,10 @@ use ra_db::{salsa::InternKey, CrateId};
 
 use super::{builtin, AssocTyValue, ChalkContext, Impl};
 use crate::{
-    db::HirDatabase, display::HirDisplay, method_resolution::TyFingerprint, utils::generics,
+    db::HirDatabase,
+    display::HirDisplay,
+    method_resolution::{TyFingerprint, ALL_FLOAT_FPS, ALL_INT_FPS},
+    utils::generics,
     CallableDef, DebruijnIndex, GenericPredicate, Substs, Ty, TypeCtor,
 };
 use mapping::{convert_where_clauses, generic_predicate_to_inline_bound, make_binders};
@@ -66,13 +69,31 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
         &self,
         trait_id: TraitId,
         parameters: &[GenericArg<Interner>],
+        binders: &CanonicalVarKinds<Interner>,
     ) -> Vec<ImplId> {
         debug!("impls_for_trait {:?}", trait_id);
         let trait_: hir_def::TraitId = from_chalk(self.db, trait_id);
 
         let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref(&Interner).clone());
 
+        fn binder_kind(ty: &Ty, binders: &CanonicalVarKinds<Interner>) -> Option<chalk_ir::TyKind> {
+            if let Ty::Bound(bv) = ty {
+                let binders = binders.as_slice(&Interner);
+                if bv.debruijn == DebruijnIndex::INNERMOST {
+                    if let chalk_ir::VariableKind::Ty(tk) = binders[bv.index].kind {
+                        return Some(tk);
+                    }
+                }
+            }
+            None
+        }
+
         let self_ty_fp = TyFingerprint::for_impl(&ty);
+        let fps: &[TyFingerprint] = match binder_kind(&ty, binders) {
+            Some(chalk_ir::TyKind::Integer) => &ALL_INT_FPS,
+            Some(chalk_ir::TyKind::Float) => &ALL_FLOAT_FPS,
+            _ => self_ty_fp.as_ref().map(std::slice::from_ref).unwrap_or(&[]),
+        };
 
         // Note: Since we're using impls_for_trait, only impls where the trait
         // can be resolved should ever reach Chalk. `impl_datum` relies on that
@@ -83,17 +104,21 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
 
         let id_to_chalk = |id: hir_def::ImplId| Impl::ImplDef(id).to_chalk(self.db);
 
-        let mut result: Vec<_> = match self_ty_fp {
-            Some(fp) => impl_maps
+        let mut result: Vec<_> = if fps.is_empty() {
+            debug!("Unrestricted search for {:?} impls...", trait_);
+            impl_maps
+                .iter()
+                .flat_map(|crate_impl_defs| crate_impl_defs.for_trait(trait_).map(id_to_chalk))
+                .collect()
+        } else {
+            impl_maps
                 .iter()
                 .flat_map(|crate_impl_defs| {
-                    crate_impl_defs.for_trait_and_self_ty(trait_, fp).map(id_to_chalk)
+                    fps.iter().flat_map(move |fp| {
+                        crate_impl_defs.for_trait_and_self_ty(trait_, *fp).map(id_to_chalk)
+                    })
                 })
-                .collect(),
-            None => impl_maps
-                .iter()
-                .flat_map(|crate_impl_defs| crate_impl_defs.for_trait(trait_).map(id_to_chalk))
-                .collect(),
+                .collect()
         };
 
         let arg: Option<Ty> =
@@ -219,6 +244,22 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
         // FIXME: implement closure support
         unimplemented!()
     }
+
+    fn trait_name(&self, _trait_id: chalk_ir::TraitId<Interner>) -> String {
+        unimplemented!()
+    }
+    fn adt_name(&self, _struct_id: chalk_ir::AdtId<Interner>) -> String {
+        unimplemented!()
+    }
+    fn assoc_type_name(&self, _assoc_ty_id: chalk_ir::AssocTypeId<Interner>) -> String {
+        unimplemented!()
+    }
+    fn opaque_type_name(&self, _opaque_ty_id: chalk_ir::OpaqueTyId<Interner>) -> String {
+        unimplemented!()
+    }
+    fn fn_def_name(&self, _fn_def_id: chalk_ir::FnDefId<Interner>) -> String {
+        unimplemented!()
+    }
 }
 
 pub(crate) fn program_clauses_for_chalk_env_query(
@@ -354,12 +395,18 @@ pub(crate) fn struct_datum_query(
         fundamental: false,
         phantom_data: false,
     };
-    let struct_datum_bound = rust_ir::AdtDatumBound {
-        fields: Vec::new(), // FIXME add fields (only relevant for auto traits)
-        where_clauses,
+    // FIXME provide enum variants properly (for auto traits)
+    let variant = rust_ir::AdtVariantDatum {
+        fields: Vec::new(), // FIXME add fields (only relevant for auto traits),
+    };
+    let struct_datum_bound = rust_ir::AdtDatumBound { variants: vec![variant], where_clauses };
+    let struct_datum = StructDatum {
+        // FIXME set ADT kind
+        kind: rust_ir::AdtKind::Struct,
+        id: struct_id,
+        binders: make_binders(struct_datum_bound, num_params),
+        flags,
     };
-    let struct_datum =
-        StructDatum { id: struct_id, binders: make_binders(struct_datum_bound, num_params), flags };
     Arc::new(struct_datum)
 }
 
diff --git a/crates/ra_hir_ty/src/traits/chalk/interner.rs b/crates/ra_hir_ty/src/traits/chalk/interner.rs
index 15426b022..156b691b4 100644
--- a/crates/ra_hir_ty/src/traits/chalk/interner.rs
+++ b/crates/ra_hir_ty/src/traits/chalk/interner.rs
@@ -39,6 +39,7 @@ impl chalk_ir::interner::Interner for Interner {
     type InternedQuantifiedWhereClauses = Vec<chalk_ir::QuantifiedWhereClause<Self>>;
     type InternedVariableKinds = Vec<chalk_ir::VariableKind<Self>>;
     type InternedCanonicalVarKinds = Vec<chalk_ir::CanonicalVarKind<Self>>;
+    type InternedConstraints = Vec<chalk_ir::InEnvironment<chalk_ir::Constraint<Self>>>;
     type DefId = InternId;
     type InternedAdtId = crate::TypeCtorId;
     type Identifier = TypeAliasId;
@@ -349,6 +350,20 @@ impl chalk_ir::interner::Interner for Interner {
     ) -> &'a [chalk_ir::CanonicalVarKind<Self>] {
         &canonical_var_kinds
     }
+
+    fn intern_constraints<E>(
+        &self,
+        data: impl IntoIterator<Item = Result<chalk_ir::InEnvironment<chalk_ir::Constraint<Self>>, E>>,
+    ) -> Result<Self::InternedConstraints, E> {
+        data.into_iter().collect()
+    }
+
+    fn constraints_data<'a>(
+        &self,
+        constraints: &'a Self::InternedConstraints,
+    ) -> &'a [chalk_ir::InEnvironment<chalk_ir::Constraint<Self>>] {
+        constraints
+    }
 }
 
 impl chalk_ir::interner::HasInterner for Interner {
diff --git a/crates/ra_hir_ty/src/traits/chalk/mapping.rs b/crates/ra_hir_ty/src/traits/chalk/mapping.rs
index 433d6aa03..7dc9ee759 100644
--- a/crates/ra_hir_ty/src/traits/chalk/mapping.rs
+++ b/crates/ra_hir_ty/src/traits/chalk/mapping.rs
@@ -29,6 +29,7 @@ impl ToChalk for Ty {
         match self {
             Ty::Apply(apply_ty) => match apply_ty.ctor {
                 TypeCtor::Ref(m) => ref_to_chalk(db, m, apply_ty.parameters),
+                TypeCtor::Array => array_to_chalk(db, apply_ty.parameters),
                 TypeCtor::FnPtr { num_args: _ } => {
                     let substitution = apply_ty.parameters.to_chalk(db).shifted_in(&Interner);
                     chalk_ir::TyData::Function(chalk_ir::Fn { num_binders: 0, substitution })
@@ -61,13 +62,13 @@ impl ToChalk for Ty {
             Ty::Bound(idx) => chalk_ir::TyData::BoundVar(idx).intern(&Interner),
             Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"),
             Ty::Dyn(predicates) => {
-                let where_clauses = chalk_ir::QuantifiedWhereClauses::from(
+                let where_clauses = chalk_ir::QuantifiedWhereClauses::from_iter(
                     &Interner,
                     predicates.iter().filter(|p| !p.is_error()).cloned().map(|p| p.to_chalk(db)),
                 );
                 let bounded_ty = chalk_ir::DynTy {
                     bounds: make_binders(where_clauses, 1),
-                    lifetime: LIFETIME_PLACEHOLDER.to_lifetime(&Interner),
+                    lifetime: FAKE_PLACEHOLDER.to_lifetime(&Interner),
                 };
                 chalk_ir::TyData::Dyn(bounded_ty).intern(&Interner)
             }
@@ -92,6 +93,7 @@ impl ToChalk for Ty {
             chalk_ir::TyData::Apply(apply_ty) => match apply_ty.name {
                 TypeName::Error => Ty::Unknown,
                 TypeName::Ref(m) => ref_from_chalk(db, m, apply_ty.substitution),
+                TypeName::Array => array_from_chalk(db, apply_ty.substitution),
                 _ => {
                     let ctor = from_chalk(db, apply_ty.name);
                     let parameters = from_chalk(db, apply_ty.substitution);
@@ -138,7 +140,7 @@ impl ToChalk for Ty {
     }
 }
 
-const LIFETIME_PLACEHOLDER: PlaceholderIndex =
+const FAKE_PLACEHOLDER: PlaceholderIndex =
     PlaceholderIndex { ui: UniverseIndex::ROOT, idx: usize::MAX };
 
 /// We currently don't model lifetimes, but Chalk does. So, we have to insert a
@@ -149,10 +151,10 @@ fn ref_to_chalk(
     subst: Substs,
 ) -> chalk_ir::Ty<Interner> {
     let arg = subst[0].clone().to_chalk(db);
-    let lifetime = LIFETIME_PLACEHOLDER.to_lifetime(&Interner);
+    let lifetime = FAKE_PLACEHOLDER.to_lifetime(&Interner);
     chalk_ir::ApplicationTy {
         name: TypeName::Ref(mutability.to_chalk(db)),
-        substitution: chalk_ir::Substitution::from(
+        substitution: chalk_ir::Substitution::from_iter(
             &Interner,
             vec![lifetime.cast(&Interner), arg.cast(&Interner)],
         ),
@@ -173,11 +175,40 @@ fn ref_from_chalk(
     Ty::apply(TypeCtor::Ref(from_chalk(db, mutability)), Substs(tys))
 }
 
+/// We currently don't model constants, but Chalk does. So, we have to insert a
+/// fake constant here, because Chalks built-in logic may expect it to be there.
+fn array_to_chalk(db: &dyn HirDatabase, subst: Substs) -> chalk_ir::Ty<Interner> {
+    let arg = subst[0].clone().to_chalk(db);
+    let usize_ty = chalk_ir::ApplicationTy {
+        name: TypeName::Scalar(Scalar::Uint(chalk_ir::UintTy::Usize)),
+        substitution: chalk_ir::Substitution::empty(&Interner),
+    }
+    .intern(&Interner);
+    let const_ = FAKE_PLACEHOLDER.to_const(&Interner, usize_ty);
+    chalk_ir::ApplicationTy {
+        name: TypeName::Array,
+        substitution: chalk_ir::Substitution::from_iter(
+            &Interner,
+            vec![arg.cast(&Interner), const_.cast(&Interner)],
+        ),
+    }
+    .intern(&Interner)
+}
+
+/// Here we remove the const from the type we got from Chalk.
+fn array_from_chalk(db: &dyn HirDatabase, subst: chalk_ir::Substitution<Interner>) -> Ty {
+    let tys = subst
+        .iter(&Interner)
+        .filter_map(|p| Some(from_chalk(db, p.ty(&Interner)?.clone())))
+        .collect();
+    Ty::apply(TypeCtor::Array, Substs(tys))
+}
+
 impl ToChalk for Substs {
     type Chalk = chalk_ir::Substitution<Interner>;
 
     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Substitution<Interner> {
-        chalk_ir::Substitution::from(&Interner, self.iter().map(|ty| ty.clone().to_chalk(db)))
+        chalk_ir::Substitution::from_iter(&Interner, self.iter().map(|ty| ty.clone().to_chalk(db)))
     }
 
     fn from_chalk(db: &dyn HirDatabase, parameters: chalk_ir::Substitution<Interner>) -> Substs {
@@ -263,6 +294,7 @@ impl ToChalk for TypeCtor {
             TypeCtor::Tuple { cardinality } => TypeName::Tuple(cardinality.into()),
             TypeCtor::RawPtr(mutability) => TypeName::Raw(mutability.to_chalk(db)),
             TypeCtor::Slice => TypeName::Slice,
+            TypeCtor::Array => TypeName::Array,
             TypeCtor::Ref(mutability) => TypeName::Ref(mutability.to_chalk(db)),
             TypeCtor::Str => TypeName::Str,
             TypeCtor::FnDef(callable_def) => {
@@ -271,10 +303,8 @@ impl ToChalk for TypeCtor {
             }
             TypeCtor::Never => TypeName::Never,
 
-            TypeCtor::Adt(_)
-            | TypeCtor::Array
-            | TypeCtor::FnPtr { .. }
-            | TypeCtor::Closure { .. } => {
+            // FIXME convert these
+            TypeCtor::Adt(_) | TypeCtor::FnPtr { .. } | TypeCtor::Closure { .. } => {
                 // other TypeCtors get interned and turned into a chalk StructId
                 let struct_id = db.intern_type_ctor(self).into();
                 TypeName::Adt(struct_id)
@@ -492,6 +522,11 @@ impl ToChalk for GenericPredicate {
                 // we shouldn't get these from Chalk
                 panic!("encountered LifetimeOutlives from Chalk")
             }
+
+            chalk_ir::WhereClause::TypeOutlives(_) => {
+                // we shouldn't get these from Chalk
+                panic!("encountered TypeOutlives from Chalk")
+            }
         }
     }
 }
@@ -570,7 +605,10 @@ where
                 )
             });
         let value = self.value.to_chalk(db);
-        chalk_ir::Canonical { value, binders: chalk_ir::CanonicalVarKinds::from(&Interner, kinds) }
+        chalk_ir::Canonical {
+            value,
+            binders: chalk_ir::CanonicalVarKinds::from_iter(&Interner, kinds),
+        }
     }
 
     fn from_chalk(db: &dyn HirDatabase, canonical: chalk_ir::Canonical<T::Chalk>) -> Canonical<T> {
@@ -691,7 +729,7 @@ where
     T: HasInterner<Interner = Interner>,
 {
     chalk_ir::Binders::new(
-        chalk_ir::VariableKinds::from(
+        chalk_ir::VariableKinds::from_iter(
             &Interner,
             std::iter::repeat(chalk_ir::VariableKind::Ty(chalk_ir::TyKind::General)).take(num_vars),
         ),
diff --git a/crates/ra_hir_ty/src/traits/chalk/tls.rs b/crates/ra_hir_ty/src/traits/chalk/tls.rs
index e6a9d3211..1e226baea 100644
--- a/crates/ra_hir_ty/src/traits/chalk/tls.rs
+++ b/crates/ra_hir_ty/src/traits/chalk/tls.rs
@@ -157,7 +157,7 @@ impl DebugContext<'_> {
             _ => panic!("associated type not in trait"),
         };
         let trait_data = self.0.trait_data(trait_);
-        let params = projection_ty.substitution.parameters(&Interner);
+        let params = projection_ty.substitution.as_slice(&Interner);
         write!(fmt, "<{:?} as {}", &params[0], trait_data.name,)?;
         if params.len() > 1 {
             write!(
diff --git a/crates/ra_hir_ty/src/utils.rs b/crates/ra_hir_ty/src/utils.rs
index c45820ff0..e3e244268 100644
--- a/crates/ra_hir_ty/src/utils.rs
+++ b/crates/ra_hir_ty/src/utils.rs
@@ -110,38 +110,6 @@ pub(super) fn all_super_trait_refs(db: &dyn HirDatabase, trait_ref: TraitRef) ->
     result
 }
 
-/// Finds a path from a trait to one of its super traits. Returns an empty
-/// vector if there is no path.
-pub(super) fn find_super_trait_path(
-    db: &dyn DefDatabase,
-    trait_: TraitId,
-    super_trait: TraitId,
-) -> Vec<TraitId> {
-    let mut result = Vec::with_capacity(2);
-    result.push(trait_);
-    return if go(db, super_trait, &mut result) { result } else { Vec::new() };
-
-    fn go(db: &dyn DefDatabase, super_trait: TraitId, path: &mut Vec<TraitId>) -> bool {
-        let trait_ = *path.last().unwrap();
-        if trait_ == super_trait {
-            return true;
-        }
-
-        for tt in direct_super_traits(db, trait_) {
-            if path.contains(&tt) {
-                continue;
-            }
-            path.push(tt);
-            if go(db, super_trait, path) {
-                return true;
-            } else {
-                path.pop();
-            }
-        }
-        false
-    }
-}
-
 pub(super) fn associated_type_by_name_including_super_traits(
     db: &dyn HirDatabase,
     trait_ref: TraitRef,