11 files changed, 474 insertions, 81 deletions
diff --git a/crates/ra_hir_ty/src/_match.rs b/crates/ra_hir_ty/src/_match.rs
index a64be9848..688026a04 100644
--- a/crates/ra_hir_ty/src/_match.rs
+++ b/crates/ra_hir_ty/src/_match.rs
@@ -194,9 +194,10 @@ use smallvec::{smallvec, SmallVec};
 use crate::{
    db::HirDatabase,
    expr::{Body, Expr, Literal, Pat, PatId},
-    InferenceResult,
+    ApplicationTy, InferenceResult, Ty, TypeCtor,
 };
-use hir_def::{adt::VariantData, EnumVariantId, VariantId};
+use hir_def::{adt::VariantData, AdtId, EnumVariantId, VariantId};
+use ra_arena::Idx;
 #[derive(Debug, Clone, Copy)]
 /// Either a pattern from the source code being analyzed, represented as
@@ -512,6 +513,7 @@ pub enum Usefulness {
 }
 pub struct MatchCheckCtx<'a> {
+    pub match_expr: Idx<Expr>,
    pub body: Arc<Body>,
    pub infer: Arc<InferenceResult>,
    pub db: &'a dyn HirDatabase,
@@ -530,6 +532,16 @@ pub(crate) fn is_useful(
    matrix: &Matrix,
    v: &PatStack,
 ) -> MatchCheckResult<Usefulness> {
+    // Handle the special case of enums with no variants. In that case, no match
+    // arm is useful.
+    if let Ty::Apply(ApplicationTy { ctor: TypeCtor::Adt(AdtId::EnumId(enum_id)), .. }) =
+        cx.infer[cx.match_expr].strip_references()
+    {
+        if cx.db.enum_data(*enum_id).variants.is_empty() {
+            return Ok(Usefulness::NotUseful);
+        }
+    }
    if v.is_empty() {
        let result = if matrix.is_empty() { Usefulness::Useful } else { Usefulness::NotUseful };
@@ -1618,6 +1630,32 @@ mod tests {
        check_no_diagnostic(content);
    }
+    #[test]
+    fn enum_never() {
+        let content = r"
+            enum Never {}
+            fn test_fn(never: Never) {
+                match never {}
+            }
+        ";
+        check_no_diagnostic(content);
+    }
+    #[test]
+    fn enum_never_ref() {
+        let content = r"
+            enum Never {}
+            fn test_fn(never: &Never) {
+                match never {}
+            }
+        ";
+        check_no_diagnostic(content);
+    }
 }
 #[cfg(test)]
diff --git a/crates/ra_hir_ty/src/autoderef.rs b/crates/ra_hir_ty/src/autoderef.rs
index d91c21e24..1b0f84c5c 100644
--- a/crates/ra_hir_ty/src/autoderef.rs
+++ b/crates/ra_hir_ty/src/autoderef.rs
@@ -14,7 +14,7 @@ use crate::{
    db::HirDatabase,
    traits::{InEnvironment, Solution},
    utils::generics,
-    BoundVar, Canonical, DebruijnIndex, Substs, Ty,
+    BoundVar, Canonical, DebruijnIndex, Obligation, Substs, TraitRef, Ty,
 };
 const AUTODEREF_RECURSION_LIMIT: usize = 10;
@@ -66,6 +66,20 @@ fn deref_by_trait(
    let parameters =
        Substs::build_for_generics(&generic_params).push(ty.value.value.clone()).build();
+    // Check that the type implements Deref at all
+    let trait_ref = TraitRef { trait_: deref_trait, substs: parameters.clone() };
+    let implements_goal = super::Canonical {
+        num_vars: ty.value.num_vars,
+        value: InEnvironment {
+            value: Obligation::Trait(trait_ref),
+            environment: ty.environment.clone(),
+        },
+    };
+    if db.trait_solve(krate, implements_goal).is_none() {
+        return None;
+    }
+    // Now do the assoc type projection
    let projection = super::traits::ProjectionPredicate {
        ty: Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, ty.value.num_vars)),
        projection_ty: super::ProjectionTy { associated_ty: target, parameters },
@@ -91,6 +105,11 @@ fn deref_by_trait(
            // they're just being 'passed through'. In the 'standard' case where
            // we have `impl<T> Deref for Foo<T> { Target = T }`, that should be
            // the case.
+            // FIXME: if the trait solver decides to truncate the type, these
+            // assumptions will be broken. We would need to properly introduce
+            // new variables in that case
            for i in 1..vars.0.num_vars {
                if vars.0.value[i - 1] != Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, i - 1))
                {
diff --git a/crates/ra_hir_ty/src/expr.rs b/crates/ra_hir_ty/src/expr.rs
index 21abbcf1e..fd59f4320 100644
--- a/crates/ra_hir_ty/src/expr.rs
+++ b/crates/ra_hir_ty/src/expr.rs
@@ -156,7 +156,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
            None => return,
        };
-        let cx = MatchCheckCtx { body, infer: infer.clone(), db };
+        let cx = MatchCheckCtx { match_expr, body, infer: infer.clone(), db };
        let pats = arms.iter().map(|arm| arm.pat);
        let mut seen = Matrix::empty();
diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs
index ac25f8a80..5f6cea8d3 100644
--- a/crates/ra_hir_ty/src/infer/unify.rs
+++ b/crates/ra_hir_ty/src/infer/unify.rs
@@ -32,6 +32,7 @@ where
    var_stack: Vec<TypeVarId>,
 }
+#[derive(Debug)]
 pub(super) struct Canonicalized<T> {
    pub value: Canonical<T>,
    free_vars: Vec<InferTy>,
diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs
index 18f74d3b1..2677f3af2 100644
--- a/crates/ra_hir_ty/src/lib.rs
+++ b/crates/ra_hir_ty/src/lib.rs
@@ -680,6 +680,16 @@ impl Ty {
        }
    }
+    pub fn strip_references(&self) -> &Ty {
+        let mut t: &Ty = self;
+        while let Ty::Apply(ApplicationTy { ctor: TypeCtor::Ref(_mutability), parameters }) = t {
+            t = parameters.as_single();
+        }
+        t
+    }
    pub fn as_adt(&self) -> Option<(AdtId, &Substs)> {
        match self {
            Ty::Apply(ApplicationTy { ctor: TypeCtor::Adt(adt_def), parameters }) => {
diff --git a/crates/ra_hir_ty/src/lower.rs b/crates/ra_hir_ty/src/lower.rs
index 6c7bbc448..cc1ac8e3e 100644
--- a/crates/ra_hir_ty/src/lower.rs
+++ b/crates/ra_hir_ty/src/lower.rs
@@ -8,6 +8,8 @@
 use std::iter;
 use std::sync::Arc;
+use smallvec::SmallVec;
 use hir_def::{
    adt::StructKind,
    builtin_type::BuiltinType,
@@ -360,13 +362,23 @@ impl Ty {
            },
            Some(TypeNs::GenericParam(param_id)) => {
                let predicates = ctx.db.generic_predicates_for_param(param_id);
-                predicates
+                let mut traits_: Vec<_> = predicates
                    .iter()
                    .filter_map(|pred| match &pred.value {
                        GenericPredicate::Implemented(tr) => Some(tr.trait_),
                        _ => None,
                    })
-                    .collect()
+                    .collect();
+                // Handle `Self::Type` referring to own associated type in trait definitions
+                if let GenericDefId::TraitId(trait_id) = param_id.parent {
+                    let generics = generics(ctx.db.upcast(), trait_id.into());
+                    if generics.params.types[param_id.local_id].provenance
+                        == TypeParamProvenance::TraitSelf
+                    {
+                        traits_.push(trait_id);
+                    }
+                }
+                traits_
            }
            _ => return Ty::Unknown,
        };
@@ -596,21 +608,35 @@ fn assoc_type_bindings_from_type_bound<'a>(
        .into_iter()
        .flat_map(|segment| segment.args_and_bindings.into_iter())
        .flat_map(|args_and_bindings| args_and_bindings.bindings.iter())
-        .map(move |(name, type_ref)| {
+        .flat_map(move |binding| {
            let associated_ty = associated_type_by_name_including_super_traits(
                ctx.db.upcast(),
                trait_ref.trait_,
-                &name,
+                &binding.name,
            );
            let associated_ty = match associated_ty {
-                None => return GenericPredicate::Error,
+                None => return SmallVec::<[GenericPredicate; 1]>::new(),
                Some(t) => t,
            };
            let projection_ty =
                ProjectionTy { associated_ty, parameters: trait_ref.substs.clone() };
-            let ty = Ty::from_hir(ctx, type_ref);
+            let mut preds = SmallVec::with_capacity(
-            let projection_predicate = ProjectionPredicate { projection_ty, ty };
+                binding.type_ref.as_ref().map_or(0, |_| 1) + binding.bounds.len(),
-            GenericPredicate::Projection(projection_predicate)
+            );
+            if let Some(type_ref) = &binding.type_ref {
+                let ty = Ty::from_hir(ctx, type_ref);
+                let projection_predicate =
+                    ProjectionPredicate { projection_ty: projection_ty.clone(), ty };
+                preds.push(GenericPredicate::Projection(projection_predicate));
+            }
+            for bound in &binding.bounds {
+                preds.extend(GenericPredicate::from_type_bound(
+                    ctx,
+                    bound,
+                    Ty::Projection(projection_ty.clone()),
+                ));
+            }
+            preds
        })
 }
diff --git a/crates/ra_hir_ty/src/tests/regression.rs b/crates/ra_hir_ty/src/tests/regression.rs
index 3402e0cb5..d69115a2f 100644
--- a/crates/ra_hir_ty/src/tests/regression.rs
+++ b/crates/ra_hir_ty/src/tests/regression.rs
@@ -451,8 +451,7 @@ pub mod str {
 "#,
    );
-    // should be Option<char>, but currently not because of Chalk ambiguity problem
+    assert_eq!("(Option<char>, Option<char>)", super::type_at_pos(&db, pos));
-    assert_eq!("(Option<{unknown}>, Option<{unknown}>)", super::type_at_pos(&db, pos));
 }
 #[test]
diff --git a/crates/ra_hir_ty/src/tests/traits.rs b/crates/ra_hir_ty/src/tests/traits.rs
index 22ae6ca90..0a889f805 100644
--- a/crates/ra_hir_ty/src/tests/traits.rs
+++ b/crates/ra_hir_ty/src/tests/traits.rs
@@ -349,7 +349,6 @@ trait Trait: SuperTrait {
 #[test]
 fn infer_project_associated_type() {
-    // y, z, a don't yet work because of https://github.com/rust-lang/chalk/issues/234
    assert_snapshot!(
        infer(r#"
 trait Iterable {
@@ -368,12 +367,12 @@ fn test<T: Iterable>() {
    [108; 261) '{     ...ter; }': ()
    [118; 119) 'x': u32
    [145; 146) '1': u32
-    [156; 157) 'y': {unknown}
+    [156; 157) 'y': Iterable::Item<T>
-    [183; 192) 'no_matter': {unknown}
+    [183; 192) 'no_matter': Iterable::Item<T>
-    [202; 203) 'z': {unknown}
+    [202; 203) 'z': Iterable::Item<T>
-    [215; 224) 'no_matter': {unknown}
+    [215; 224) 'no_matter': Iterable::Item<T>
-    [234; 235) 'a': {unknown}
+    [234; 235) 'a': Iterable::Item<T>
-    [249; 258) 'no_matter': {unknown}
+    [249; 258) 'no_matter': Iterable::Item<T>
    "###
    );
 }
@@ -433,8 +432,8 @@ fn test<T: Iterable<Item=u32>>() {
 "#),
        @r###"
    [67; 100) '{     ...own; }': ()
-    [77; 78) 'y': {unknown}
+    [77; 78) 'y': u32
-    [90; 97) 'unknown': {unknown}
+    [90; 97) 'unknown': u32
    "###
    );
 }
@@ -549,7 +548,7 @@ impl std::ops::Index<u32> for Bar {
 fn test() {
    let a = Bar;
-    let b = a[1];
+    let b = a[1u32];
    b<|>;
 }
@@ -574,7 +573,7 @@ fn infer_ops_index_autoderef() {
 //- /main.rs crate:main deps:std
 fn test() {
    let a = &[1u32, 2, 3];
-    let b = a[1];
+    let b = a[1u32];
    b<|>;
 }
@@ -916,11 +915,7 @@ fn test<T: ApplyL>(t: T) {
 }
 "#,
    );
-    // FIXME here Chalk doesn't normalize the type to a placeholder. I think we
+    assert_eq!(t, "ApplyL::Out<T>");
-    // need to add a rule like Normalize(<T as ApplyL>::Out -> ApplyL::Out<T>)
-    // to the trait env ourselves here; probably Chalk can't do this by itself.
-    // assert_eq!(t, "ApplyL::Out<[missing name]>");
-    assert_eq!(t, "{unknown}");
 }
 #[test]
@@ -1329,16 +1324,16 @@ fn test<T: Trait<Type = u32>>(x: T, y: impl Trait<Type = i64>) {
    [263; 264) 'y': impl Trait<Type = i64>
    [290; 398) '{     ...r>); }': ()
    [296; 299) 'get': fn get<T>(T) -> <T as Trait>::Type
-    [296; 302) 'get(x)': {unknown}
+    [296; 302) 'get(x)': u32
    [300; 301) 'x': T
-    [308; 312) 'get2': fn get2<{unknown}, T>(T) -> {unknown}
+    [308; 312) 'get2': fn get2<u32, T>(T) -> u32
-    [308; 315) 'get2(x)': {unknown}
+    [308; 315) 'get2(x)': u32
    [313; 314) 'x': T
    [321; 324) 'get': fn get<impl Trait<Type = i64>>(impl Trait<Type = i64>) -> <impl Trait<Type = i64> as Trait>::Type
-    [321; 327) 'get(y)': {unknown}
+    [321; 327) 'get(y)': i64
    [325; 326) 'y': impl Trait<Type = i64>
-    [333; 337) 'get2': fn get2<{unknown}, impl Trait<Type = i64>>(impl Trait<Type = i64>) -> {unknown}
+    [333; 337) 'get2': fn get2<i64, impl Trait<Type = i64>>(impl Trait<Type = i64>) -> i64
-    [333; 340) 'get2(y)': {unknown}
+    [333; 340) 'get2(y)': i64
    [338; 339) 'y': impl Trait<Type = i64>
    [346; 349) 'get': fn get<S<u64>>(S<u64>) -> <S<u64> as Trait>::Type
    [346; 357) 'get(set(S))': u64
@@ -1402,7 +1397,6 @@ mod iter {
 #[test]
 fn projection_eq_within_chalk() {
-    // std::env::set_var("CHALK_DEBUG", "1");
    assert_snapshot!(
        infer(r#"
 trait Trait1 {
@@ -1422,7 +1416,7 @@ fn test<T: Trait1<Type = u32>>(x: T) {
    [164; 165) 'x': T
    [170; 186) '{     ...o(); }': ()
    [176; 177) 'x': T
-    [176; 183) 'x.foo()': {unknown}
+    [176; 183) 'x.foo()': u32
    "###
    );
 }
@@ -1578,7 +1572,7 @@ fn test<F: FnOnce(u32, u64) -> u128>(f: F) {
    [150; 151) 'f': F
    [156; 184) '{     ...2)); }': ()
    [162; 163) 'f': F
-    [162; 181) 'f.call...1, 2))': {unknown}
+    [162; 181) 'f.call...1, 2))': u128
    [174; 180) '(1, 2)': (u32, u64)
    [175; 176) '1': u32
    [178; 179) '2': u64
@@ -1803,7 +1797,7 @@ fn test<T, U>() where T::Item: Trait2, T: Trait<U::Item>, U: Trait<()> {
 }
 #[test]
-fn unselected_projection_on_trait_self() {
+fn unselected_projection_on_impl_self() {
    assert_snapshot!(infer(
        r#"
 //- /main.rs
@@ -1829,7 +1823,7 @@ impl Trait for S2 {
 "#,
    ), @r###"
    [54; 58) 'self': &Self
-    [60; 61) 'x': {unknown}
+    [60; 61) 'x': Trait::Item<Self>
    [140; 144) 'self': &S
    [146; 147) 'x': u32
    [161; 175) '{ let y = x; }': ()
@@ -1844,6 +1838,30 @@ impl Trait for S2 {
 }
 #[test]
+fn unselected_projection_on_trait_self() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Trait {
+    type Item;
+    fn f(&self) -> Self::Item { loop {} }
+}
+struct S;
+impl Trait for S {
+    type Item = u32;
+}
+fn test() {
+    S.f()<|>;
+}
+"#,
+    );
+    assert_eq!(t, "u32");
+}
+#[test]
 fn trait_impl_self_ty() {
    let t = type_at(
        r#"
@@ -1924,6 +1942,119 @@ fn test<T, U>() where T: Trait<U::Item>, U: Trait<T::Item> {
 }
 #[test]
+fn inline_assoc_type_bounds_1() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Iterator {
+    type Item;
+}
+trait OtherTrait<T> {
+    fn foo(&self) -> T;
+}
+// workaround for Chalk assoc type normalization problems
+pub struct S<T>;
+impl<T: Iterator> Iterator for S<T> {
+    type Item = <T as Iterator>::Item;
+}
+fn test<I: Iterator<Item: OtherTrait<u32>>>() {
+    let x: <S<I> as Iterator>::Item;
+    x.foo()<|>;
+}
+"#,
+    );
+    assert_eq!(t, "u32");
+}
+#[test]
+fn inline_assoc_type_bounds_2() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Iterator {
+    type Item;
+}
+fn test<I: Iterator<Item: Iterator<Item = u32>>>() {
+    let x: <<I as Iterator>::Item as Iterator>::Item;
+    x<|>;
+}
+"#,
+    );
+    assert_eq!(t, "u32");
+}
+#[test]
+fn proc_macro_server_types() {
+    assert_snapshot!(
+        infer_with_mismatches(r#"
+macro_rules! with_api {
+    ($S:ident, $self:ident, $m:ident) => {
+        $m! {
+            TokenStream {
+                fn new() -> $S::TokenStream;
+            },
+            Group {
+            },
+        }
+    };
+}
+macro_rules! associated_item {
+    (type TokenStream) =>
+        (type TokenStream: 'static + Clone;);
+    (type Group) =>
+        (type Group: 'static + Clone;);
+    ($($item:tt)*) => ($($item)*;)
+}
+macro_rules! declare_server_traits {
+    ($($name:ident {
+        $(fn $method:ident($($arg:ident: $arg_ty:ty),* $(,)?) $(-> $ret_ty:ty)?;)*
+    }),* $(,)?) => {
+        pub trait Types {
+            $(associated_item!(type $name);)*
+        }
+        $(pub trait $name: Types {
+            $(associated_item!(fn $method(&mut self, $($arg: $arg_ty),*) $(-> $ret_ty)?);)*
+        })*
+        pub trait Server: Types $(+ $name)* {}
+        impl<S: Types $(+ $name)*> Server for S {}
+    }
+}
+with_api!(Self, self_, declare_server_traits);
+struct Group {}
+struct TokenStream {}
+struct Rustc;
+impl Types for Rustc {
+    type TokenStream = TokenStream;
+    type Group = Group;
+}
+fn make<T>() -> T { loop {} }
+impl TokenStream for Rustc {
+    fn new() -> Self::TokenStream {
+        let group: Self::Group = make();
+        make()
+    }
+}
+"#, true),
+        @r###"
+    [1115; 1126) '{ loop {} }': T
+    [1117; 1124) 'loop {}': !
+    [1122; 1124) '{}': ()
+    [1190; 1253) '{     ...     }': {unknown}
+    [1204; 1209) 'group': {unknown}
+    [1225; 1229) 'make': fn make<{unknown}>() -> {unknown}
+    [1225; 1231) 'make()': {unknown}
+    [1241; 1245) 'make': fn make<{unknown}>() -> {unknown}
+    [1241; 1247) 'make()': {unknown}
+    "###
+    );
+}
+#[test]
 fn unify_impl_trait() {
    assert_snapshot!(
        infer_with_mismatches(r#"
@@ -2023,6 +2154,33 @@ fn main() {
 }
 #[test]
+fn associated_type_bound() {
+    let t = type_at(
+        r#"
+//- /main.rs
+pub trait Trait {
+    type Item: OtherTrait<u32>;
+}
+pub trait OtherTrait<T> {
+    fn foo(&self) -> T;
+}
+// this is just a workaround for chalk#234
+pub struct S<T>;
+impl<T: Trait> Trait for S<T> {
+    type Item = <T as Trait>::Item;
+}
+fn test<T: Trait>() {
+    let y: <S<T> as Trait>::Item = no_matter;
+    y.foo()<|>;
+}
+"#,
+    );
+    assert_eq!(t, "u32");
+}
+#[test]
 fn dyn_trait_through_chalk() {
    let t = type_at(
        r#"
diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs
index 43d8d1e80..05791a848 100644
--- a/crates/ra_hir_ty/src/traits.rs
+++ b/crates/ra_hir_ty/src/traits.rs
@@ -16,10 +16,12 @@ use self::chalk::{from_chalk, Interner, ToChalk};
 pub(crate) mod chalk;
 mod builtin;
-/// This controls the maximum size of types Chalk considers. If we set this too
+// This controls the maximum size of types Chalk considers. If we set this too
-/// high, we can run into slow edge cases; if we set it too low, Chalk won't
+// high, we can run into slow edge cases; if we set it too low, Chalk won't
-/// find some solutions.
+// find some solutions.
-const CHALK_SOLVER_MAX_SIZE: usize = 10;
+// FIXME this is currently hardcoded in the recursive solver
+// const CHALK_SOLVER_MAX_SIZE: usize = 10;
 /// This controls how much 'time' we give the Chalk solver before giving up.
 const CHALK_SOLVER_FUEL: i32 = 100;
@@ -30,8 +32,7 @@ struct ChalkContext<'a> {
 }
 fn create_chalk_solver() -> chalk_solve::Solver<Interner> {
-    let solver_choice =
+    let solver_choice = chalk_solve::SolverChoice::recursive();
-        chalk_solve::SolverChoice::SLG { max_size: CHALK_SOLVER_MAX_SIZE, expected_answers: None };
    solver_choice.into_solver()
 }
@@ -194,13 +195,16 @@ fn solve(
        }
        remaining > 0
    };
-    let mut solve = || solver.solve_limited(&context, goal, should_continue);
+    let mut solve = || {
+        let solution = solver.solve_limited(&context, goal, should_continue);
+        log::debug!("solve({:?}) => {:?}", goal, solution);
+        solution
+    };
    // don't set the TLS for Chalk unless Chalk debugging is active, to make
    // extra sure we only use it for debugging
    let solution =
        if is_chalk_debug() { chalk::tls::set_current_program(db, solve) } else { solve() };
-    log::debug!("solve({:?}) => {:?}", goal, solution);
    solution
 }
diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs
index e05fea843..60d70d18e 100644
--- a/crates/ra_hir_ty/src/traits/chalk.rs
+++ b/crates/ra_hir_ty/src/traits/chalk.rs
@@ -32,6 +32,9 @@ impl chalk_ir::interner::Interner for Interner {
    type InternedGoal = Arc<GoalData<Self>>;
    type InternedGoals = Vec<Goal<Self>>;
    type InternedSubstitution = Vec<Parameter<Self>>;
+    type InternedProgramClause = chalk_ir::ProgramClauseData<Self>;
+    type InternedProgramClauses = Vec<chalk_ir::ProgramClause<Self>>;
+    type InternedQuantifiedWhereClauses = Vec<chalk_ir::QuantifiedWhereClause<Self>>;
    type Identifier = TypeAliasId;
    type DefId = InternId;
@@ -181,6 +184,48 @@ impl chalk_ir::interner::Interner for Interner {
    ) -> &'a [Parameter<Self>] {
        substitution
    }
+    fn intern_program_clause(
+        &self,
+        data: chalk_ir::ProgramClauseData<Self>,
+    ) -> chalk_ir::ProgramClauseData<Self> {
+        data
+    }
+    fn program_clause_data<'a>(
+        &self,
+        clause: &'a chalk_ir::ProgramClauseData<Self>,
+    ) -> &'a chalk_ir::ProgramClauseData<Self> {
+        clause
+    }
+    fn intern_program_clauses(
+        &self,
+        data: impl IntoIterator<Item = chalk_ir::ProgramClause<Self>>,
+    ) -> Vec<chalk_ir::ProgramClause<Self>> {
+        data.into_iter().collect()
+    }
+    fn program_clauses_data<'a>(
+        &self,
+        clauses: &'a Vec<chalk_ir::ProgramClause<Self>>,
+    ) -> &'a [chalk_ir::ProgramClause<Self>] {
+        clauses
+    }
+    fn intern_quantified_where_clauses(
+        &self,
+        data: impl IntoIterator<Item = chalk_ir::QuantifiedWhereClause<Self>>,
+    ) -> Self::InternedQuantifiedWhereClauses {
+        data.into_iter().collect()
+    }
+    fn quantified_where_clauses_data<'a>(
+        &self,
+        clauses: &'a Self::InternedQuantifiedWhereClauses,
+    ) -> &'a [chalk_ir::QuantifiedWhereClause<Self>] {
+        clauses
+    }
 }
 impl chalk_ir::interner::HasInterner for Interner {
@@ -238,12 +283,10 @@ 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 = predicates
+                let where_clauses = chalk_ir::QuantifiedWhereClauses::from(
-                    .iter()
+                    &Interner,
-                    .filter(|p| !p.is_error())
+                    predicates.iter().filter(|p| !p.is_error()).cloned().map(|p| p.to_chalk(db)),
-                    .cloned()
+                );
-                    .map(|p| p.to_chalk(db))
-                    .collect();
                let bounded_ty = chalk_ir::DynTy { bounds: make_binders(where_clauses, 1) };
                chalk_ir::TyData::Dyn(bounded_ty).intern(&Interner)
            }
@@ -281,8 +324,12 @@ impl ToChalk for Ty {
            chalk_ir::TyData::InferenceVar(_iv) => Ty::Unknown,
            chalk_ir::TyData::Dyn(where_clauses) => {
                assert_eq!(where_clauses.bounds.binders.len(), 1);
-                let predicates =
+                let predicates = where_clauses
-                    where_clauses.bounds.value.into_iter().map(|c| from_chalk(db, c)).collect();
+                    .bounds
+                    .skip_binders()
+                    .iter(&Interner)
+                    .map(|c| from_chalk(db, c.clone()))
+                    .collect();
                Ty::Dyn(predicates)
            }
        }
@@ -426,7 +473,7 @@ impl ToChalk for GenericPredicate {
    ) -> GenericPredicate {
        // we don't produce any where clauses with binders and can't currently deal with them
        match where_clause
-            .value
+            .skip_binders()
            .shifted_out(&Interner)
            .expect("unexpected bound vars in where clause")
        {
@@ -464,13 +511,13 @@ impl ToChalk for ProjectionTy {
 }
 impl ToChalk for super::ProjectionPredicate {
-    type Chalk = chalk_ir::Normalize<Interner>;
+    type Chalk = chalk_ir::AliasEq<Interner>;
-    fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Normalize<Interner> {
+    fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::AliasEq<Interner> {
-        chalk_ir::Normalize { alias: self.projection_ty.to_chalk(db), ty: self.ty.to_chalk(db) }
+        chalk_ir::AliasEq { alias: self.projection_ty.to_chalk(db), ty: self.ty.to_chalk(db) }
    }
-    fn from_chalk(_db: &dyn HirDatabase, _normalize: chalk_ir::Normalize<Interner>) -> Self {
+    fn from_chalk(_db: &dyn HirDatabase, _normalize: chalk_ir::AliasEq<Interner>) -> Self {
        unimplemented!()
    }
 }
@@ -521,7 +568,7 @@ impl ToChalk for Arc<super::TraitEnvironment> {
                pred.clone().to_chalk(db).cast(&Interner);
            clauses.push(program_clause.into_from_env_clause(&Interner));
        }
-        chalk_ir::Environment::new().add_clauses(clauses)
+        chalk_ir::Environment::new(&Interner).add_clauses(&Interner, clauses)
    }
    fn from_chalk(
@@ -603,10 +650,10 @@ impl ToChalk for builtin::BuiltinImplAssocTyValueData {
 }
 fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> {
-    chalk_ir::Binders {
+    chalk_ir::Binders::new(
+        std::iter::repeat(chalk_ir::ParameterKind::Ty(())).take(num_vars).collect(),
        value,
-        binders: std::iter::repeat(chalk_ir::ParameterKind::Ty(())).take(num_vars).collect(),
+    )
-    }
 }
 fn convert_where_clauses(
@@ -626,6 +673,55 @@ fn convert_where_clauses(
    result
 }
+fn generic_predicate_to_inline_bound(
+    db: &dyn HirDatabase,
+    pred: &GenericPredicate,
+    self_ty: &Ty,
+) -> Option<chalk_rust_ir::InlineBound<Interner>> {
+    // An InlineBound is like a GenericPredicate, except the self type is left out.
+    // We don't have a special type for this, but Chalk does.
+    match pred {
+        GenericPredicate::Implemented(trait_ref) => {
+            if &trait_ref.substs[0] != self_ty {
+                // we can only convert predicates back to type bounds if they
+                // have the expected self type
+                return None;
+            }
+            let args_no_self = trait_ref.substs[1..]
+                .iter()
+                .map(|ty| ty.clone().to_chalk(db).cast(&Interner))
+                .collect();
+            let trait_bound =
+                chalk_rust_ir::TraitBound { trait_id: trait_ref.trait_.to_chalk(db), args_no_self };
+            Some(chalk_rust_ir::InlineBound::TraitBound(trait_bound))
+        }
+        GenericPredicate::Projection(proj) => {
+            if &proj.projection_ty.parameters[0] != self_ty {
+                return None;
+            }
+            let trait_ = match proj.projection_ty.associated_ty.lookup(db.upcast()).container {
+                AssocContainerId::TraitId(t) => t,
+                _ => panic!("associated type not in trait"),
+            };
+            let args_no_self = proj.projection_ty.parameters[1..]
+                .iter()
+                .map(|ty| ty.clone().to_chalk(db).cast(&Interner))
+                .collect();
+            let alias_eq_bound = chalk_rust_ir::AliasEqBound {
+                value: proj.ty.clone().to_chalk(db),
+                trait_bound: chalk_rust_ir::TraitBound {
+                    trait_id: trait_.to_chalk(db),
+                    args_no_self,
+                },
+                associated_ty_id: proj.projection_ty.associated_ty.to_chalk(db),
+                parameters: Vec::new(), // FIXME we don't support generic associated types yet
+            };
+            Some(chalk_rust_ir::InlineBound::AliasEqBound(alias_eq_bound))
+        }
+        GenericPredicate::Error => None,
+    }
+}
 impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
    fn associated_ty_data(&self, id: AssocTypeId) -> Arc<AssociatedTyDatum> {
        self.db.associated_ty_data(id)
@@ -696,6 +792,13 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
    fn interner(&self) -> &Interner {
        &Interner
    }
+    fn well_known_trait_id(
+        &self,
+        _well_known_trait: chalk_rust_ir::WellKnownTrait,
+    ) -> Option<chalk_ir::TraitId<Interner>> {
+        // FIXME tell Chalk about well-known traits (here and in trait_datum)
+        None
+    }
 }
 pub(crate) fn associated_ty_data_query(
@@ -708,12 +811,25 @@ pub(crate) fn associated_ty_data_query(
        AssocContainerId::TraitId(t) => t,
        _ => panic!("associated type not in trait"),
    };
+    // Lower bounds -- we could/should maybe move this to a separate query in `lower`
+    let type_alias_data = db.type_alias_data(type_alias);
    let generic_params = generics(db.upcast(), type_alias.into());
-    let bound_data = chalk_rust_ir::AssociatedTyDatumBound {
+    let bound_vars = Substs::bound_vars(&generic_params);
-        // FIXME add bounds and where clauses
+    let resolver = hir_def::resolver::HasResolver::resolver(type_alias, db.upcast());
-        bounds: vec![],
+    let ctx = crate::TyLoweringContext::new(db, &resolver)
-        where_clauses: vec![],
+        .with_type_param_mode(crate::lower::TypeParamLoweringMode::Variable);
-    };
+    let self_ty = Ty::Bound(crate::BoundVar::new(crate::DebruijnIndex::INNERMOST, 0));
+    let bounds = type_alias_data
+        .bounds
+        .iter()
+        .flat_map(|bound| GenericPredicate::from_type_bound(&ctx, bound, self_ty.clone()))
+        .filter_map(|pred| generic_predicate_to_inline_bound(db, &pred, &self_ty))
+        .map(|bound| make_binders(bound.shifted_in(&Interner), 0))
+        .collect();
+    let where_clauses = convert_where_clauses(db, type_alias.into(), &bound_vars);
+    let bound_data = chalk_rust_ir::AssociatedTyDatumBound { bounds, where_clauses };
    let datum = AssociatedTyDatum {
        trait_id: trait_.to_chalk(db),
        id,
diff --git a/crates/ra_hir_ty/src/traits/chalk/tls.rs b/crates/ra_hir_ty/src/traits/chalk/tls.rs
index d9bbb54a5..fa8e4d1ad 100644
--- a/crates/ra_hir_ty/src/traits/chalk/tls.rs
+++ b/crates/ra_hir_ty/src/traits/chalk/tls.rs
@@ -2,10 +2,11 @@
 use std::fmt;
 use chalk_ir::{AliasTy, Goal, Goals, Lifetime, Parameter, ProgramClauseImplication, TypeName};
+use itertools::Itertools;
 use super::{from_chalk, Interner};
 use crate::{db::HirDatabase, CallableDef, TypeCtor};
-use hir_def::{AdtId, AssocContainerId, Lookup, TypeAliasId};
+use hir_def::{AdtId, AssocContainerId, DefWithBodyId, Lookup, TypeAliasId};
 pub use unsafe_tls::{set_current_program, with_current_program};
@@ -69,7 +70,27 @@ impl DebugContext<'_> {
                write!(f, "{}::{}", trait_name, name)?;
            }
            TypeCtor::Closure { def, expr } => {
-                write!(f, "{{closure {:?} in {:?}}}", expr.into_raw(), def)?;
+                write!(f, "{{closure {:?} in ", expr.into_raw())?;
+                match def {
+                    DefWithBodyId::FunctionId(func) => {
+                        write!(f, "fn {}", self.0.function_data(func).name)?
+                    }
+                    DefWithBodyId::StaticId(s) => {
+                        if let Some(name) = self.0.static_data(s).name.as_ref() {
+                            write!(f, "body of static {}", name)?;
+                        } else {
+                            write!(f, "body of unnamed static {:?}", s)?;
+                        }
+                    }
+                    DefWithBodyId::ConstId(c) => {
+                        if let Some(name) = self.0.const_data(c).name.as_ref() {
+                            write!(f, "body of const {}", name)?;
+                        } else {
+                            write!(f, "body of unnamed const {:?}", c)?;
+                        }
+                    }
+                };
+                write!(f, "}}")?;
            }
        }
        Ok(())
@@ -113,14 +134,15 @@ impl DebugContext<'_> {
        };
        let trait_data = self.0.trait_data(trait_);
        let params = alias.substitution.parameters(&Interner);
-        write!(
+        write!(fmt, "<{:?} as {}", &params[0], trait_data.name,)?;
-            fmt,
+        if params.len() > 1 {
-            "<{:?} as {}<{:?}>>::{}",
+            write!(
-            &params[0],
+                fmt,
-            trait_data.name,
+                "<{}>",
-            &params[1..],
+                &params[1..].iter().format_with(", ", |x, f| f(&format_args!("{:?}", x))),
-            type_alias_data.name
+            )?;
-        )
+        }
+        write!(fmt, ">::{}", type_alias_data.name)
    }
    pub fn debug_ty(