6 files changed, 383 insertions, 49 deletions

diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index edce1afe7..1e7d97f51 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -328,8 +328,7 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 Obligation::Trait(tr) => {
                     let canonicalized = self.canonicalizer().canonicalize_trait_ref(tr.clone());
                     (
-                        super::traits::implements(
-                            self.db,
+                        self.db.implements(
                             self.resolver.krate().unwrap(),
                             canonicalized.value.clone(),
                         ),
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index 8bab7e54b..09d26ce5a 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -5,6 +5,7 @@
 //!  - Building the type for an item: This happens through the `type_for_def` query.
 //!
 //! This usually involves resolving names, collecting generic arguments etc.
+use std::sync::Arc;
 use std::iter;
 
 use crate::{
@@ -18,9 +19,9 @@ use crate::{
     resolve::{Resolver, Resolution},
     path::{PathSegment, GenericArg},
     generics::{GenericParams, HasGenericParams},
-    adt::VariantDef, Trait
+    adt::VariantDef, Trait, generics::{ WherePredicate, GenericDef}
 };
-use super::{Ty, primitive, FnSig, Substs, TypeCtor, TraitRef};
+use super::{Ty, primitive, FnSig, Substs, TypeCtor, TraitRef, GenericPredicate};
 
 impl Ty {
     pub(crate) fn from_hir(db: &impl HirDatabase, resolver: &Resolver, type_ref: &TypeRef) -> Self {
@@ -208,16 +209,12 @@ pub(super) fn substs_from_path_segment(
 }
 
 impl TraitRef {
-    pub(crate) fn from_hir(
+    pub(crate) fn from_path(
         db: &impl HirDatabase,
         resolver: &Resolver,
-        type_ref: &TypeRef,
+        path: &Path,
         explicit_self_ty: Option<Ty>,
     ) -> Option<Self> {
-        let path = match type_ref {
-            TypeRef::Path(path) => path,
-            _ => return None,
-        };
         let resolved = match resolver.resolve_path(db, &path).take_types()? {
             Resolution::Def(ModuleDef::Trait(tr)) => tr,
             _ => return None,
@@ -232,6 +229,19 @@ impl TraitRef {
         Some(TraitRef { trait_: resolved, substs })
     }
 
+    pub(crate) fn from_hir(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        type_ref: &TypeRef,
+        explicit_self_ty: Option<Ty>,
+    ) -> Option<Self> {
+        let path = match type_ref {
+            TypeRef::Path(path) => path,
+            _ => return None,
+        };
+        TraitRef::from_path(db, resolver, path, explicit_self_ty)
+    }
+
     fn substs_from_path(
         db: &impl HirDatabase,
         resolver: &Resolver,
@@ -246,6 +256,15 @@ impl TraitRef {
         let substs = Substs::identity(&trait_.generic_params(db));
         TraitRef { trait_, substs }
     }
+
+    pub(crate) fn for_where_predicate(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        pred: &WherePredicate,
+    ) -> Option<TraitRef> {
+        let self_ty = Ty::from_hir(db, resolver, &pred.type_ref);
+        TraitRef::from_path(db, resolver, &pred.trait_ref, Some(self_ty))
+    }
 }
 
 /// Build the declared type of an item. This depends on the namespace; e.g. for
@@ -294,6 +313,24 @@ pub(crate) fn type_for_field(db: &impl HirDatabase, field: StructField) -> Ty {
     Ty::from_hir(db, &resolver, type_ref)
 }
 
+/// Resolve the where clause(s) of an item with generics.
+pub(crate) fn generic_predicates(
+    db: &impl HirDatabase,
+    def: GenericDef,
+) -> Arc<[GenericPredicate]> {
+    let resolver = def.resolver(db);
+    let generic_params = def.generic_params(db);
+    let predicates = generic_params
+        .where_predicates
+        .iter()
+        .map(|pred| {
+            TraitRef::for_where_predicate(db, &resolver, pred)
+                .map_or(GenericPredicate::Error, GenericPredicate::Implemented)
+        })
+        .collect::<Vec<_>>();
+    predicates.into()
+}
+
 fn fn_sig_for_fn(db: &impl HirDatabase, def: Function) -> FnSig {
     let signature = def.signature(db);
     let resolver = def.resolver(db);
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index 607e9ba79..34817a5ec 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -75,11 +75,13 @@ impl CrateImplBlocks {
 
             let target_ty = impl_block.target_ty(db);
 
-            if let Some(tr) = impl_block.target_trait_ref(db) {
-                self.impls_by_trait
-                    .entry(tr.trait_)
-                    .or_insert_with(Vec::new)
-                    .push((module.module_id, impl_id));
+            if impl_block.target_trait(db).is_some() {
+                if let Some(tr) = impl_block.target_trait_ref(db) {
+                    self.impls_by_trait
+                        .entry(tr.trait_)
+                        .or_insert_with(Vec::new)
+                        .push((module.module_id, impl_id));
+                }
             } else {
                 if let Some(target_ty_fp) = TyFingerprint::for_impl(&target_ty) {
                     self.impls
@@ -183,7 +185,7 @@ fn iterate_trait_method_candidates<T>(
     mut callback: impl FnMut(&Ty, Function) -> Option<T>,
 ) -> Option<T> {
     let krate = resolver.krate()?;
-    'traits: for t in resolver.traits_in_scope() {
+    'traits: for t in resolver.traits_in_scope(db) {
         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
@@ -196,8 +198,7 @@ fn iterate_trait_method_candidates<T>(
                     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() {
+                            if db.implements(krate, trait_ref).is_none() {
                                 continue 'traits;
                             }
                         }
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index a38fe35c7..978cc2587 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2502,6 +2502,50 @@ fn test() { (&S).foo()<|>; }
 }
 
 #[test]
+fn method_resolution_trait_from_prelude() {
+    let (mut db, pos) = MockDatabase::with_position(
+        r#"
+//- /main.rs
+struct S;
+impl Clone for S {}
+
+fn test() {
+    S.clone()<|>;
+}
+
+//- /lib.rs
+#[prelude_import] use foo::*;
+
+mod foo {
+    trait Clone {
+        fn clone(&self) -> Self;
+    }
+}
+"#,
+    );
+    db.set_crate_graph_from_fixture(crate_graph! {
+        "main": ("/main.rs", ["other_crate"]),
+        "other_crate": ("/lib.rs", []),
+    });
+    assert_eq!("S", type_at_pos(&db, pos));
+}
+
+#[test]
+fn method_resolution_where_clause_for_unknown_trait() {
+    // The blanket impl shouldn't apply because we can't even resolve UnknownTrait
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Trait { fn foo(self) -> u128; }
+struct S;
+impl<T> Trait for T where T: UnknownTrait {}
+fn test() { (&S).foo()<|>; }
+"#,
+    );
+    assert_eq!(t, "{unknown}");
+}
+
+#[test]
 fn method_resolution_where_clause_not_met() {
     // The blanket impl shouldn't apply because we can't prove S: Clone
     let t = type_at(
@@ -2510,12 +2554,122 @@ fn method_resolution_where_clause_not_met() {
 trait Clone {}
 trait Trait { fn foo(self) -> u128; }
 struct S;
-impl S { fn foo(self) -> i8 { 0 } }
-impl<T> Trait for T where T: Clone { fn foo(self) -> u128 { 0 } }
+impl<T> Trait for T where T: Clone {}
 fn test() { (&S).foo()<|>; }
 "#,
     );
-    assert_eq!(t, "i8");
+    // This is also to make sure that we don't resolve to the foo method just
+    // because that's the only method named foo we can find, which would make
+    // the below tests not work
+    assert_eq!(t, "{unknown}");
+}
+
+#[test]
+fn method_resolution_where_clause_inline_not_met() {
+    // The blanket impl shouldn't apply because we can't prove S: Clone
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Clone {}
+trait Trait { fn foo(self) -> u128; }
+struct S;
+impl<T: Clone> Trait for T {}
+fn test() { (&S).foo()<|>; }
+"#,
+    );
+    assert_eq!(t, "{unknown}");
+}
+
+#[test]
+fn method_resolution_where_clause_1() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Clone {}
+trait Trait { fn foo(self) -> u128; }
+struct S;
+impl Clone for S {};
+impl<T> Trait for T where T: Clone {}
+fn test() { S.foo()<|>; }
+"#,
+    );
+    assert_eq!(t, "u128");
+}
+
+#[test]
+fn method_resolution_where_clause_2() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Into<T> { fn into(self) -> T; }
+trait From<T> { fn from(other: T) -> Self; }
+struct S1;
+struct S2;
+impl From<S2> for S1 {};
+impl<T, U> Into<U> for T where U: From<T> {}
+fn test() { S2.into()<|>; }
+"#,
+    );
+    assert_eq!(t, "S1");
+}
+
+#[test]
+fn method_resolution_where_clause_inline() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Into<T> { fn into(self) -> T; }
+trait From<T> { fn from(other: T) -> Self; }
+struct S1;
+struct S2;
+impl From<S2> for S1 {};
+impl<T, U: From<T>> Into<U> for T {}
+fn test() { S2.into()<|>; }
+"#,
+    );
+    assert_eq!(t, "S1");
+}
+
+#[test]
+fn method_resolution_encountering_fn_type() {
+    covers!(trait_resolution_on_fn_type);
+    type_at(
+        r#"
+//- /main.rs
+fn foo() {}
+trait FnOnce { fn call(self); }
+fn test() { foo.call()<|>; }
+"#,
+    );
+}
+
+#[test]
+fn method_resolution_slow() {
+    // this can get quite slow if we set the solver size limit too high
+    let t = type_at(
+        r#"
+//- /main.rs
+trait SendX {}
+
+struct S1; impl SendX for S1;
+struct S2; impl SendX for S2;
+struct U1;
+
+trait Trait { fn method(self); }
+
+struct X1<A, B> {}
+impl<A, B> SendX for X1<A, B> where A: SendX, B: SendX {}
+
+struct S<B, C> {}
+
+trait FnX {}
+
+impl<B, C> Trait for S<B, C> where C: FnX, B: SendX {}
+
+fn test() { (S {}).method()<|>; }
+"#,
+    );
+    assert_eq!(t, "{unknown}");
 }
 
 fn type_at_pos(db: &MockDatabase, pos: FilePosition) -> String {
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index a1ed0c028..4260f7ef7 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -1,6 +1,7 @@
 //! Trait solving using Chalk.
 use std::sync::{Arc, Mutex};
 
+use rustc_hash::FxHashSet;
 use log::debug;
 use chalk_ir::cast::Cast;
 
@@ -13,6 +14,11 @@ mod chalk;
 
 pub(crate) type Solver = chalk_solve::Solver;
 
+/// 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
+/// find some solutions.
+const CHALK_SOLVER_MAX_SIZE: usize = 2;
+
 #[derive(Debug, Copy, Clone)]
 struct ChalkContext<'a, DB> {
     db: &'a DB,
@@ -21,7 +27,8 @@ struct ChalkContext<'a, DB> {
 
 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 };
+    let solver_choice = chalk_solve::SolverChoice::SLG { max_size: CHALK_SOLVER_MAX_SIZE };
+    debug!("Creating new solver for crate {:?}", _krate);
     Arc::new(Mutex::new(solver_choice.into_solver()))
 }
 
@@ -31,7 +38,7 @@ pub(crate) fn impls_for_trait(
     krate: Crate,
     trait_: Trait,
 ) -> Arc<[ImplBlock]> {
-    let mut impls = Vec::new();
+    let mut impls = FxHashSet::default();
     // 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
@@ -42,7 +49,7 @@ pub(crate) fn impls_for_trait(
     }
     let crate_impl_blocks = db.impls_in_crate(krate);
     impls.extend(crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_));
-    impls.into()
+    impls.into_iter().collect::<Vec<_>>().into()
 }
 
 fn solve(
@@ -52,6 +59,7 @@ fn solve(
 ) -> Option<chalk_solve::Solution> {
     let context = ChalkContext { db, krate };
     let solver = db.solver(krate);
+    debug!("solve goal: {:?}", goal);
     let solution = solver.lock().unwrap().solve(&context, goal);
     debug!("solve({:?}) => {:?}", goal, solution);
     solution
@@ -125,11 +133,11 @@ fn solution_from_chalk(db: &impl HirDatabase, solution: chalk_solve::Solution) -
 }
 
 #[derive(Clone, Debug, PartialEq, Eq)]
-pub(crate) struct SolutionVariables(pub Canonical<Vec<Ty>>);
+pub struct SolutionVariables(pub Canonical<Vec<Ty>>);
 
 #[derive(Clone, Debug, PartialEq, Eq)]
 /// A (possible) solution for a proposed goal.
-pub(crate) enum Solution {
+pub enum Solution {
     /// The goal indeed holds, and there is a unique value for all existential
     /// variables.
     Unique(SolutionVariables),
@@ -144,7 +152,7 @@ pub(crate) enum Solution {
 #[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 {
+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.
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
index 8b77d21b4..78440b258 100644
--- a/crates/ra_hir/src/ty/traits/chalk.rs
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -6,15 +6,22 @@ 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 test_utils::tested_by;
 use ra_db::salsa::{InternId, InternKey};
 
 use crate::{
     Trait, HasGenericParams, ImplBlock,
     db::HirDatabase,
-    ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs},
+    ty::{TraitRef, Ty, ApplicationTy, TypeCtor, Substs, GenericPredicate, CallableDef},
+    ty::display::HirDisplay,
+    generics::GenericDef,
 };
 use super::ChalkContext;
 
+/// This represents a trait whose name we could not resolve.
+const UNKNOWN_TRAIT: chalk_ir::TraitId =
+    chalk_ir::TraitId(chalk_ir::RawId { index: u32::max_value() });
+
 pub(super) trait ToChalk {
     type Chalk;
     fn to_chalk(self, db: &impl HirDatabase) -> Self::Chalk;
@@ -45,7 +52,10 @@ impl ToChalk for Ty {
             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(),
+            // maybe an alternative would be `for<T> T`? (meaningless in rust, but expressible in chalk's Ty)
+            Ty::Unknown => {
+                PlaceholderIndex { ui: UniverseIndex::ROOT, idx: usize::max_value() }.to_ty()
+            }
         }
     }
     fn from_chalk(db: &impl HirDatabase, chalk: chalk_ir::Ty) -> Self {
@@ -146,6 +156,33 @@ impl ToChalk for ImplBlock {
     }
 }
 
+impl ToChalk for GenericPredicate {
+    type Chalk = chalk_ir::QuantifiedWhereClause;
+
+    fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::QuantifiedWhereClause {
+        match self {
+            GenericPredicate::Implemented(trait_ref) => {
+                make_binders(chalk_ir::WhereClause::Implemented(trait_ref.to_chalk(db)), 0)
+            }
+            GenericPredicate::Error => {
+                let impossible_trait_ref = chalk_ir::TraitRef {
+                    trait_id: UNKNOWN_TRAIT,
+                    parameters: vec![Ty::Unknown.to_chalk(db).cast()],
+                };
+                make_binders(chalk_ir::WhereClause::Implemented(impossible_trait_ref), 0)
+            }
+        }
+    }
+
+    fn from_chalk(
+        _db: &impl HirDatabase,
+        _where_clause: chalk_ir::QuantifiedWhereClause,
+    ) -> GenericPredicate {
+        // This should never need to be called
+        unimplemented!()
+    }
+}
+
 fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> {
     chalk_ir::Binders {
         value,
@@ -153,6 +190,40 @@ fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> {
     }
 }
 
+fn blacklisted_trait(db: &impl HirDatabase, trait_: Trait) -> bool {
+    let name = trait_.name(db).unwrap_or_else(crate::Name::missing).to_string();
+    match &*name {
+        "Send" | "Sync" | "Sized" | "Fn" | "FnMut" | "FnOnce" => true,
+        _ => false,
+    }
+}
+
+fn convert_where_clauses(
+    db: &impl HirDatabase,
+    def: GenericDef,
+    substs: &Substs,
+) -> Vec<chalk_ir::QuantifiedWhereClause> {
+    let generic_predicates = db.generic_predicates(def);
+    let mut result = Vec::with_capacity(generic_predicates.len());
+    for pred in generic_predicates.iter() {
+        if pred.is_error() {
+            // HACK: Return just the single predicate (which is always false
+            // anyway), otherwise Chalk can easily get into slow situations
+            return vec![pred.clone().subst(substs).to_chalk(db)];
+        }
+        match pred {
+            GenericPredicate::Implemented(trait_ref) => {
+                if blacklisted_trait(db, trait_ref.trait_) {
+                    continue;
+                }
+            }
+            _ => {}
+        }
+        result.push(pred.clone().subst(substs).to_chalk(db));
+    }
+    result
+}
+
 impl<'a, DB> chalk_solve::RustIrDatabase for ChalkContext<'a, DB>
 where
     DB: HirDatabase,
@@ -162,18 +233,36 @@ where
     }
     fn trait_datum(&self, trait_id: chalk_ir::TraitId) -> Arc<TraitDatum> {
         debug!("trait_datum {:?}", trait_id);
+        if trait_id == UNKNOWN_TRAIT {
+            let trait_datum_bound = chalk_rust_ir::TraitDatumBound {
+                trait_ref: chalk_ir::TraitRef {
+                    trait_id: UNKNOWN_TRAIT,
+                    parameters: vec![chalk_ir::Ty::BoundVar(0).cast()],
+                },
+                associated_ty_ids: Vec::new(),
+                where_clauses: Vec::new(),
+                flags: chalk_rust_ir::TraitFlags {
+                    auto: false,
+                    marker: false,
+                    upstream: true,
+                    fundamental: false,
+                },
+            };
+            return Arc::new(TraitDatum { binders: make_binders(trait_datum_bound, 1) });
+        }
         let trait_: Trait = from_chalk(self.db, trait_id);
+        debug!("trait {:?} = {:?}", trait_id, trait_.name(self.db));
         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 {
+            auto: trait_.is_auto(self.db),
+            upstream: trait_.module(self.db).krate(self.db) != Some(self.krate),
             // 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 where_clauses = convert_where_clauses(self.db, trait_.into(), &bound_vars);
         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 };
@@ -183,23 +272,51 @@ where
     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);
+        debug!("struct {:?} = {:?}", struct_id, type_ctor);
         // 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 {
+        let (num_params, where_clauses, 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::Str => (0, vec![], true),
+            TypeCtor::Slice | TypeCtor::Array | TypeCtor::RawPtr(_) | TypeCtor::Ref(_) => {
+                (1, vec![], true)
+            }
+            TypeCtor::FnPtr { num_args } => (num_args as usize + 1, vec![], true),
+            TypeCtor::Tuple { cardinality } => (cardinality as usize, vec![], true),
+            TypeCtor::FnDef(callable) => {
+                tested_by!(trait_resolution_on_fn_type);
+                let krate = match callable {
+                    CallableDef::Function(f) => f.module(self.db).krate(self.db),
+                    CallableDef::Struct(s) => s.module(self.db).krate(self.db),
+                    CallableDef::EnumVariant(v) => {
+                        v.parent_enum(self.db).module(self.db).krate(self.db)
+                    }
+                };
+                let generic_def: GenericDef = match callable {
+                    CallableDef::Function(f) => f.into(),
+                    CallableDef::Struct(s) => s.into(),
+                    CallableDef::EnumVariant(v) => v.parent_enum(self.db).into(),
+                };
+                let generic_params = generic_def.generic_params(self.db);
+                let bound_vars = Substs::bound_vars(&generic_params);
+                let where_clauses = convert_where_clauses(self.db, generic_def, &bound_vars);
+                (
+                    generic_params.count_params_including_parent(),
+                    where_clauses,
+                    krate != Some(self.krate),
+                )
+            }
             TypeCtor::Adt(adt) => {
                 let generic_params = adt.generic_params(self.db);
+                let bound_vars = Substs::bound_vars(&generic_params);
+                let where_clauses = convert_where_clauses(self.db, adt.into(), &bound_vars);
                 (
                     generic_params.count_params_including_parent(),
+                    where_clauses,
                     adt.krate(self.db) != Some(self.krate),
                 )
             }
@@ -209,7 +326,6 @@ where
             // 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(),
@@ -237,10 +353,23 @@ where
         } else {
             chalk_rust_ir::ImplType::External
         };
+        let where_clauses = convert_where_clauses(self.db, impl_block.into(), &bound_vars);
+        let negative = impl_block.is_negative(self.db);
+        debug!(
+            "impl {:?}: {}{} where {:?}",
+            impl_id,
+            if negative { "!" } else { "" },
+            trait_ref.display(self.db),
+            where_clauses
+        );
+        let trait_ref = trait_ref.to_chalk(self.db);
         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
+            trait_ref: if negative {
+                chalk_rust_ir::PolarizedTraitRef::Negative(trait_ref)
+            } else {
+                chalk_rust_ir::PolarizedTraitRef::Positive(trait_ref)
+            },
+            where_clauses,
             associated_ty_values: Vec::new(), // FIXME add associated type values
             impl_type,
         };
@@ -249,16 +378,22 @@ where
     }
     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
+        if trait_id == UNKNOWN_TRAIT {
+            return Vec::new();
+        }
+        let trait_: Trait = from_chalk(self.db, trait_id);
+        let blacklisted = blacklisted_trait(self.db, trait_);
+        if blacklisted {
+            return Vec::new();
+        }
+        let result: Vec<_> = 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()
+            .collect();
+        debug!("impls_for_trait returned {} impls", result.len());
+        result
     }
     fn impl_provided_for(
         &self,