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,