17 files changed, 530 insertions, 123 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 8aaf0375a..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,
@@ -161,6 +164,13 @@ pub trait HirDatabase: DefDatabase {
     #[salsa::invoke(crate::ty::traits::solver)]
     #[salsa::volatile]
     fn solver(&self, krate: Crate) -> Arc<Mutex<crate::ty::traits::Solver>>;
+
+    #[salsa::invoke(crate::ty::traits::implements)]
+    fn implements(
+        &self,
+        krate: Crate,
+        goal: crate::ty::Canonical<crate::ty::TraitRef>,
+    ) -> Option<crate::ty::traits::Solution>;
 }
 
 #[test]
diff --git a/crates/ra_hir/src/expr.rs b/crates/ra_hir/src/expr.rs
index 480eaf171..a2b5db1a1 100644
--- a/crates/ra_hir/src/expr.rs
+++ b/crates/ra_hir/src/expr.rs
@@ -10,7 +10,7 @@ use ra_syntax::{
 };
 
 use crate::{
-    Path, Name, HirDatabase, Resolver,DefWithBody, Either, HirFileId,
+    Path, Name, HirDatabase, Resolver,DefWithBody, Either, HirFileId, MacroCallLoc,
     name::AsName,
     type_ref::{Mutability, TypeRef},
 };
@@ -828,7 +828,8 @@ where
                     .ast_id(e)
                     .with_file_id(self.current_file_id);
 
-                if let Some(call_id) = self.resolver.resolve_macro_call(self.db, path, ast_id) {
+                if let Some(def) = self.resolver.resolve_macro_call(path) {
+                    let call_id = MacroCallLoc { def, ast_id }.id(self.db);
                     if let Some(tt) = self.db.macro_expand(call_id).ok() {
                         if let Some(expr) = mbe::token_tree_to_expr(&tt).ok() {
                             log::debug!("macro expansion {}", expr.syntax().debug_dump());
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/nameres.rs b/crates/ra_hir/src/nameres.rs
index a450d7b84..0290b3474 100644
--- a/crates/ra_hir/src/nameres.rs
+++ b/crates/ra_hir/src/nameres.rs
@@ -272,8 +272,8 @@ impl CrateDefMap {
         (res.resolved_def, res.segment_index)
     }
 
-    pub(crate) fn find_macro(&self, name: &Name) -> Option<&MacroDefId> {
-        self.public_macros.get(name).or(self.local_macros.get(name))
+    pub(crate) fn find_macro(&self, name: &Name) -> Option<MacroDefId> {
+        self.public_macros.get(name).or(self.local_macros.get(name)).map(|it| *it)
     }
 
     // Returns Yes if we are sure that additions to `ItemMap` wouldn't change
diff --git a/crates/ra_hir/src/resolve.rs b/crates/ra_hir/src/resolve.rs
index 707556ef8..3874e28bf 100644
--- a/crates/ra_hir/src/resolve.rs
+++ b/crates/ra_hir/src/resolve.rs
@@ -1,16 +1,12 @@
 //! Name resolution.
 use std::sync::Arc;
 
-use ra_syntax::ast;
-
-use rustc_hash::FxHashMap;
+use rustc_hash::{FxHashMap, FxHashSet};
 
 use crate::{
     ModuleDef, Trait,
     code_model_api::Crate,
-    MacroCallId,
-    MacroCallLoc,
-    AstId,
+    MacroDefId,
     db::HirDatabase,
     name::{Name, KnownName},
     nameres::{PerNs, CrateDefMap, CrateModuleId},
@@ -134,16 +130,9 @@ impl Resolver {
         resolution
     }
 
-    pub fn resolve_macro_call(
-        &self,
-        db: &impl HirDatabase,
-        path: Option<Path>,
-        ast_id: AstId<ast::MacroCall>,
-    ) -> Option<MacroCallId> {
+    pub(crate) fn resolve_macro_call(&self, path: Option<Path>) -> Option<MacroDefId> {
         let name = path.and_then(|path| path.expand_macro_expr()).unwrap_or_else(Name::missing);
-        let def_id = self.module().and_then(|(module, _)| module.find_macro(&name))?;
-        let call_loc = MacroCallLoc { def: *def_id, ast_id }.id(db);
-        Some(call_loc)
+        self.module()?.0.find_macro(&name)
     }
 
     /// Returns the resolved path segments
@@ -193,19 +182,18 @@ impl Resolver {
         names
     }
 
-    pub(crate) fn traits_in_scope<'a>(&'a self) -> impl Iterator<Item = Trait> + 'a {
-        // FIXME prelude
-        self.scopes
-            .iter()
-            .rev()
-            .flat_map(|scope| {
-                match scope {
-                    Scope::ModuleScope(m) => Some(m.crate_def_map[m.module_id].scope.traits()),
-                    _ => None,
+    pub(crate) fn traits_in_scope(&self, db: &impl HirDatabase) -> FxHashSet<Trait> {
+        let mut traits = FxHashSet::default();
+        for scope in &self.scopes {
+            if let Scope::ModuleScope(m) = scope {
+                if let Some(prelude) = m.crate_def_map.prelude() {
+                    let prelude_def_map = db.crate_def_map(prelude.krate);
+                    traits.extend(prelude_def_map[prelude.module_id].scope.traits());
                 }
-                .into_iter()
-            })
-            .flatten()
+                traits.extend(m.crate_def_map[m.module_id].scope.traits());
+            }
+        }
+        traits
     }
 
     fn module(&self) -> Option<(&CrateDefMap, CrateModuleId)> {
diff --git a/crates/ra_hir/src/source_binder.rs b/crates/ra_hir/src/source_binder.rs
index 31bf13425..179faebfb 100644
--- a/crates/ra_hir/src/source_binder.rs
+++ b/crates/ra_hir/src/source_binder.rs
@@ -20,7 +20,7 @@ use crate::{
     HirDatabase, Function, Struct, Enum, Const, Static, Either, DefWithBody, PerNs, Name,
     AsName, Module, HirFileId, Crate, Trait, Resolver, Ty,Path,
     expr::{BodySourceMap, scope::{ScopeId, ExprScopes}},
-    ids::{LocationCtx,MacroCallId},
+    ids::{LocationCtx, MacroDefId},
     docs::{docs_from_ast,Documentation},
     expr, AstId,
 };
@@ -191,13 +191,12 @@ pub enum PathResolution {
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct MacroByExampleDef {
-    pub(crate) id: MacroCallId,
+    pub(crate) id: MacroDefId,
 }
 
 impl MacroByExampleDef {
     pub fn source(&self, db: &impl HirDatabase) -> (HirFileId, TreeArc<ast::MacroCall>) {
-        let loc = self.id.loc(db);
-        (self.id.into(), loc.def.0.to_node(db))
+        (self.id.0.file_id(), self.id.0.to_node(db))
     }
 }
 
@@ -284,21 +283,9 @@ impl SourceAnalyzer {
         self.infer.as_ref()?.field_resolution(expr_id)
     }
 
-    pub fn resolve_macro_call(
-        &self,
-        db: &impl HirDatabase,
-        file_id: FileId,
-        macro_call: &ast::MacroCall,
-    ) -> Option<MacroByExampleDef> {
-        let hir_id = file_id.into();
-        let ast_id = db.ast_id_map(hir_id).ast_id(macro_call).with_file_id(hir_id);
-        let call_id = self.resolver.resolve_macro_call(
-            db,
-            macro_call.path().and_then(Path::from_ast),
-            ast_id,
-        );
-
-        call_id.map(|id| MacroByExampleDef { id })
+    pub fn resolve_macro_call(&self, macro_call: &ast::MacroCall) -> Option<MacroByExampleDef> {
+        let id = self.resolver.resolve_macro_call(macro_call.path().and_then(Path::from_ast))?;
+        Some(MacroByExampleDef { id })
     }
 
     pub fn resolve_hir_path(
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 f4eee835f..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,13 +234,42 @@ 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
 /// many there are. This is used to erase irrelevant differences between types
 /// before using them in queries.
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub(crate) struct Canonical<T> {
+pub struct Canonical<T> {
     pub value: T,
     pub num_vars: usize,
 }
@@ -534,3 +563,20 @@ impl HirDisplay for Ty {
         Ok(())
     }
 }
+
+impl HirDisplay for TraitRef {
+    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
+        write!(
+            f,
+            "{}: {}",
+            self.substs[0].display(f.db),
+            self.trait_.name(f.db).unwrap_or_else(Name::missing)
+        )?;
+        if self.substs.len() > 1 {
+            write!(f, "<")?;
+            f.write_joined(&self.substs[1..], ", ")?;
+            write!(f, ">")?;
+        }
+        Ok(())
+    }
+}
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,