Merge #1262

1262: Where clauses and other Chalk improvements r=matklad a=flodiebold

This adds support for where clauses to the Chalk integration; it also adds FnDef lowering and partly handles auto traits.

One thing I'm not sure about is the error handling -- what do we do if we can't
resolve a trait reference in a where clause? For impls, I think it's clear we
need to disregard the impl for trait solving. I've solved this for now by
introducing an 'unknown trait' that has no impls, so if we encounter an unknown
trait we can use that and basically get a where clause that's always false. (The
alternative would be somehow not returning the impl to Chalk at all, but we
would need to know that we need to do that in `impls_for_trait` already, and we
don't resolve anything there.)

A bit surprisingly, this has almost no impact on the type inference stats for RA, probably because of missing edge cases. Probably impl Trait support and closure support will do more.

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

11 files changed, 406 insertions, 56 deletions

diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs
index 55e1793c5..0c4a80bfa 100644
--- a/crates/ra_hir/src/code_model_api.rs
+++ b/crates/ra_hir/src/code_model_api.rs
@@ -703,6 +703,10 @@ impl Trait {
         TraitRef::for_trait(db, self)
     }
 
+    pub fn is_auto(self, db: &impl DefDatabase) -> bool {
+        self.trait_data(db).is_auto()
+    }
+
     pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
         let r = self.module(db).resolver(db);
         // add generic params, if present
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index 689dd6225..8f98ca3a5 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -11,7 +11,7 @@ use crate::{
     DefWithBody, Trait,
     ids,
     nameres::{Namespace, ImportSourceMap, RawItems, CrateDefMap},
-    ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig, TypeCtor},
+    ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks, TypableDef, CallableDef, FnSig, TypeCtor, GenericPredicate},
     adt::{StructData, EnumData},
     impl_block::{ModuleImplBlocks, ImplSourceMap, ImplBlock},
     generics::{GenericParams, GenericDef},
@@ -138,6 +138,9 @@ pub trait HirDatabase: DefDatabase {
     #[salsa::invoke(crate::ty::callable_item_sig)]
     fn callable_item_signature(&self, def: CallableDef) -> FnSig;
 
+    #[salsa::invoke(crate::ty::generic_predicates)]
+    fn generic_predicates(&self, def: GenericDef) -> Arc<[GenericPredicate]>;
+
     #[salsa::invoke(crate::expr::body_with_source_map_query)]
     fn body_with_source_map(
         &self,
diff --git a/crates/ra_hir/src/generics.rs b/crates/ra_hir/src/generics.rs
index 2e52c5871..c29b96f50 100644
--- a/crates/ra_hir/src/generics.rs
+++ b/crates/ra_hir/src/generics.rs
@@ -8,7 +8,7 @@ use std::sync::Arc;
 use ra_syntax::ast::{self, NameOwner, TypeParamsOwner, TypeBoundsOwner};
 
 use crate::{
-    db::DefDatabase,
+    db::{ HirDatabase, DefDatabase},
     Name, AsName, Function, Struct, Enum, Trait, TypeAlias, ImplBlock, Container, path::Path, type_ref::TypeRef, AdtDef
 };
 
@@ -32,8 +32,8 @@ pub struct GenericParams {
 /// where clauses like `where T: Foo + Bar` are turned into multiple of these.
 #[derive(Clone, PartialEq, Eq, Debug)]
 pub struct WherePredicate {
-    type_ref: TypeRef,
-    trait_ref: Path,
+    pub(crate) type_ref: TypeRef,
+    pub(crate) trait_ref: Path,
 }
 
 // FIXME: consts can have type parameters from their parents (i.e. associated consts of traits)
@@ -90,8 +90,17 @@ impl GenericParams {
     fn fill_params(&mut self, params: &ast::TypeParamList, start: u32) {
         for (idx, type_param) in params.type_params().enumerate() {
             let name = type_param.name().map(AsName::as_name).unwrap_or_else(Name::missing);
-            let param = GenericParam { idx: idx as u32 + start, name };
+            let param = GenericParam { idx: idx as u32 + start, name: name.clone() };
             self.params.push(param);
+
+            let type_ref = TypeRef::Path(name.into());
+            for bound in type_param
+                .type_bound_list()
+                .iter()
+                .flat_map(|type_bound_list| type_bound_list.bounds())
+            {
+                self.add_where_predicate_from_bound(bound, type_ref.clone());
+            }
         }
     }
 
@@ -101,26 +110,28 @@ impl GenericParams {
                 Some(type_ref) => type_ref,
                 None => continue,
             };
+            let type_ref = TypeRef::from_ast(type_ref);
             for bound in pred.type_bound_list().iter().flat_map(|l| l.bounds()) {
-                let path = bound
-                    .type_ref()
-                    .and_then(|tr| match tr.kind() {
-                        ast::TypeRefKind::PathType(path) => path.path(),
-                        _ => None,
-                    })
-                    .and_then(Path::from_ast);
-                let path = match path {
-                    Some(p) => p,
-                    None => continue,
-                };
-                self.where_predicates.push(WherePredicate {
-                    type_ref: TypeRef::from_ast(type_ref),
-                    trait_ref: path,
-                });
+                self.add_where_predicate_from_bound(bound, type_ref.clone());
             }
         }
     }
 
+    fn add_where_predicate_from_bound(&mut self, bound: &ast::TypeBound, type_ref: TypeRef) {
+        let path = bound
+            .type_ref()
+            .and_then(|tr| match tr.kind() {
+                ast::TypeRefKind::PathType(path) => path.path(),
+                _ => None,
+            })
+            .and_then(Path::from_ast);
+        let path = match path {
+            Some(p) => p,
+            None => return,
+        };
+        self.where_predicates.push(WherePredicate { type_ref, trait_ref: path });
+    }
+
     pub(crate) fn find_by_name(&self, name: &Name) -> Option<&GenericParam> {
         self.params.iter().find(|p| &p.name == name)
     }
@@ -148,6 +159,19 @@ impl GenericParams {
     }
 }
 
+impl GenericDef {
+    pub(crate) fn resolver(&self, db: &impl HirDatabase) -> crate::Resolver {
+        match self {
+            GenericDef::Function(inner) => inner.resolver(db),
+            GenericDef::Struct(inner) => inner.resolver(db),
+            GenericDef::Enum(inner) => inner.resolver(db),
+            GenericDef::Trait(inner) => inner.resolver(db),
+            GenericDef::TypeAlias(inner) => inner.resolver(db),
+            GenericDef::ImplBlock(inner) => inner.resolver(db),
+        }
+    }
+}
+
 impl From<Container> for GenericDef {
     fn from(c: Container) -> Self {
         match c {
diff --git a/crates/ra_hir/src/impl_block.rs b/crates/ra_hir/src/impl_block.rs
index a8a466e43..b7dd775f1 100644
--- a/crates/ra_hir/src/impl_block.rs
+++ b/crates/ra_hir/src/impl_block.rs
@@ -93,6 +93,10 @@ impl ImplBlock {
         db.impls_in_module(self.module).impls[self.impl_id].items().to_vec()
     }
 
+    pub fn is_negative(&self, db: &impl DefDatabase) -> bool {
+        db.impls_in_module(self.module).impls[self.impl_id].negative
+    }
+
     pub(crate) fn resolver(&self, db: &impl DefDatabase) -> Resolver {
         let r = self.module().resolver(db);
         // add generic params, if present
@@ -108,6 +112,7 @@ pub struct ImplData {
     target_trait: Option<TypeRef>,
     target_type: TypeRef,
     items: Vec<ImplItem>,
+    negative: bool,
 }
 
 impl ImplData {
@@ -120,6 +125,7 @@ impl ImplData {
         let target_trait = node.target_trait().map(TypeRef::from_ast);
         let target_type = TypeRef::from_ast_opt(node.target_type());
         let ctx = LocationCtx::new(db, module, file_id);
+        let negative = node.is_negative();
         let items = if let Some(item_list) = node.item_list() {
             item_list
                 .impl_items()
@@ -132,7 +138,7 @@ impl ImplData {
         } else {
             Vec::new()
         };
-        ImplData { target_trait, target_type, items }
+        ImplData { target_trait, target_type, items, negative }
     }
 
     pub fn target_trait(&self) -> Option<&TypeRef> {
diff --git a/crates/ra_hir/src/marks.rs b/crates/ra_hir/src/marks.rs
index 5b6400042..2d831f0d8 100644
--- a/crates/ra_hir/src/marks.rs
+++ b/crates/ra_hir/src/marks.rs
@@ -9,4 +9,5 @@ test_utils::marks!(
     glob_across_crates
     std_prelude
     match_ergonomics_ref
+    trait_resolution_on_fn_type
 );
diff --git a/crates/ra_hir/src/traits.rs b/crates/ra_hir/src/traits.rs
index 15f0977b7..dfe883fa4 100644
--- a/crates/ra_hir/src/traits.rs
+++ b/crates/ra_hir/src/traits.rs
@@ -11,6 +11,7 @@ use crate::{Function, Const, TypeAlias, Name, DefDatabase, Trait, ids::LocationC
 pub struct TraitData {
     name: Option<Name>,
     items: Vec<TraitItem>,
+    auto: bool,
 }
 
 impl TraitData {
@@ -19,6 +20,7 @@ impl TraitData {
         let name = node.name().map(|n| n.as_name());
         let module = tr.module(db);
         let ctx = LocationCtx::new(db, module, file_id);
+        let auto = node.is_auto();
         let items = if let Some(item_list) = node.item_list() {
             item_list
                 .impl_items()
@@ -31,7 +33,7 @@ impl TraitData {
         } else {
             Vec::new()
         };
-        Arc::new(TraitData { name, items })
+        Arc::new(TraitData { name, items, auto })
     }
 
     pub(crate) fn name(&self) -> &Option<Name> {
@@ -41,6 +43,10 @@ impl TraitData {
     pub(crate) fn items(&self) -> &[TraitItem] {
         &self.items
     }
+
+    pub(crate) fn is_auto(&self) -> bool {
+        self.auto
+    }
 }
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 12429a668..cfe07156b 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -19,7 +19,7 @@ use std::{fmt, mem};
 use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait, GenericParams};
 use display::{HirDisplay, HirFormatter};
 
-pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig};
+pub(crate) use lower::{TypableDef, type_for_def, type_for_field, callable_item_sig, generic_predicates};
 pub(crate) use infer::{infer, InferenceResult, InferTy};
 pub use lower::CallableDef;
 
@@ -234,6 +234,35 @@ impl TraitRef {
     }
 }
 
+/// Like `generics::WherePredicate`, but with resolved types: A condition on the
+/// parameters of a generic item.
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub enum GenericPredicate {
+    /// The given trait needs to be implemented for its type parameters.
+    Implemented(TraitRef),
+    /// We couldn't resolve the trait reference. (If some type parameters can't
+    /// be resolved, they will just be Unknown).
+    Error,
+}
+
+impl GenericPredicate {
+    pub fn is_error(&self) -> bool {
+        match self {
+            GenericPredicate::Error => true,
+            _ => false,
+        }
+    }
+
+    pub fn subst(self, substs: &Substs) -> GenericPredicate {
+        match self {
+            GenericPredicate::Implemented(trait_ref) => {
+                GenericPredicate::Implemented(trait_ref.subst(substs))
+            }
+            GenericPredicate::Error => self,
+        }
+    }
+}
+
 /// Basically a claim (currently not validated / checked) that the contained
 /// type / trait ref contains no inference variables; any inference variables it
 /// contained have been replaced by bound variables, and `num_vars` tells us how
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/tests.rs b/crates/ra_hir/src/ty/tests.rs
index a38fe35c7..59c85daed 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2502,6 +2502,21 @@ fn test() { (&S).foo()<|>; }
 }
 
 #[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 +2525,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 Send {}
+
+struct S1; impl Send for S1;
+struct S2; impl Send for S2;
+struct U1;
+
+trait Trait { fn method(self); }
+
+struct X1<A, B> {}
+impl<A, B> Send for X1<A, B> where A: Send, B: Send {}
+
+struct S<B, C> {}
+
+trait Fn {}
+
+impl<B, C> Trait for S<B, C> where C: Fn, B: Send {}
+
+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 4bbc99f0e..4260f7ef7 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -14,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,
@@ -22,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()))
 }
 
@@ -53,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
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
index 8b77d21b4..027c5ec4c 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,19 @@ fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T> {
     }
 }
 
+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() {
+        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 +212,35 @@ 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);
         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 };
@@ -185,21 +252,48 @@ where
         let type_ctor = from_chalk(self.db, struct_id);
         // FIXME might be nicer if we can create a fake GenericParams for the TypeCtor
         // FIXME extract this to a method on Ty
-        let (num_params, upstream) = match type_ctor {
+        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 +303,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 +330,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 +355,18 @@ where
     }
     fn impls_for_trait(&self, trait_id: chalk_ir::TraitId) -> Vec<ImplId> {
         debug!("impls_for_trait {:?}", trait_id);
+        if trait_id == UNKNOWN_TRAIT {
+            return Vec::new();
+        }
         let trait_ = from_chalk(self.db, trait_id);
-        self.db
+        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,