4 files changed, 50 insertions, 12 deletions

diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index dd0bf6e34..143919cdc 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -14,7 +14,7 @@ use crate::{
     impl_block::{ModuleImplBlocks, ImplSourceMap},
     generics::{GenericParams, GenericDef},
     type_ref::TypeRef,
-    traits::TraitData, Trait
+    traits::TraitData, Trait, ty::TraitRef
 };
 
 #[salsa::query_group(DefDatabaseStorage)]
@@ -102,6 +102,9 @@ pub trait HirDatabase: DefDatabase {
 
     #[salsa::invoke(crate::ty::method_resolution::CrateImplBlocks::impls_in_crate_query)]
     fn impls_in_crate(&self, krate: Crate) -> Arc<CrateImplBlocks>;
+
+    #[salsa::invoke(crate::ty::method_resolution::implements)]
+    fn implements(&self, trait_ref: TraitRef) -> bool;
 }
 
 #[test]
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 7d25ade47..d42c61e9d 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -14,7 +14,7 @@ pub(crate) mod display;
 use std::sync::Arc;
 use std::{fmt, mem};
 
-use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase};
+use crate::{Name, AdtDef, type_ref::Mutability, db::HirDatabase, Trait};
 
 pub(crate) use lower::{TypableDef, CallableDef, type_for_def, type_for_field, callable_item_sig};
 pub(crate) use infer::{infer, InferenceResult, InferTy};
@@ -91,7 +91,7 @@ pub enum TypeCtor {
 /// A nominal type with (maybe 0) type parameters. This might be a primitive
 /// type like `bool`, a struct, tuple, function pointer, reference or
 /// several other things.
-#[derive(Clone, PartialEq, Eq, Debug)]
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct ApplicationTy {
     pub ctor: TypeCtor,
     pub parameters: Substs,
@@ -103,7 +103,7 @@ pub struct ApplicationTy {
 /// the same thing (but in a different way).
 ///
 /// This should be cheap to clone.
-#[derive(Clone, PartialEq, Eq, Debug)]
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub enum Ty {
     /// A nominal type with (maybe 0) type parameters. This might be a primitive
     /// type like `bool`, a struct, tuple, function pointer, reference or
@@ -132,7 +132,7 @@ pub enum Ty {
 }
 
 /// A list of substitutions for generic parameters.
-#[derive(Clone, PartialEq, Eq, Debug)]
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct Substs(Arc<[Ty]>);
 
 impl Substs {
@@ -169,6 +169,21 @@ impl Substs {
     }
 }
 
+/// A trait with type parameters. This includes the `Self`, so this represents a concrete type implementing the trait.
+/// Name to be bikeshedded: TraitBound? TraitImplements?
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct TraitRef {
+    /// FIXME name?
+    trait_: Trait,
+    substs: Substs,
+}
+
+impl TraitRef {
+    pub fn self_ty(&self) -> &Ty {
+        &self.substs.0[0]
+    }
+}
+
 /// A function signature as seen by type inference: Several parameter types and
 /// one return type.
 #[derive(Clone, PartialEq, Eq, Debug)]
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index 708a435b4..146e8a02e 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -8,12 +8,12 @@ use rustc_hash::FxHashMap;
 
 use crate::{
     HirDatabase, Module, Crate, Name, Function, Trait,
-    ids::TraitId,
     impl_block::{ImplId, ImplBlock, ImplItem},
     ty::{Ty, TypeCtor},
     nameres::CrateModuleId, resolve::Resolver, traits::TraitItem
 
 };
+use super::{ TraitRef, Substs};
 
 /// This is used as a key for indexing impls.
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
@@ -38,7 +38,7 @@ pub struct CrateImplBlocks {
     /// To make sense of the CrateModuleIds, we need the source root.
     krate: Crate,
     impls: FxHashMap<TyFingerprint, Vec<(CrateModuleId, ImplId)>>,
-    impls_by_trait: FxHashMap<TraitId, Vec<(CrateModuleId, ImplId)>>,
+    impls_by_trait: FxHashMap<Trait, Vec<(CrateModuleId, ImplId)>>,
 }
 
 impl CrateImplBlocks {
@@ -56,8 +56,7 @@ impl CrateImplBlocks {
         &'a self,
         tr: &Trait,
     ) -> impl Iterator<Item = ImplBlock> + 'a {
-        let id = tr.id;
-        self.impls_by_trait.get(&id).into_iter().flat_map(|i| i.iter()).map(
+        self.impls_by_trait.get(&tr).into_iter().flat_map(|i| i.iter()).map(
             move |(module_id, impl_id)| {
                 let module = Module { krate: self.krate, module_id: *module_id };
                 ImplBlock::from_id(module, *impl_id)
@@ -75,7 +74,7 @@ impl CrateImplBlocks {
 
             if let Some(tr) = impl_block.target_trait(db) {
                 self.impls_by_trait
-                    .entry(tr.id)
+                    .entry(tr)
                     .or_insert_with(Vec::new)
                     .push((module.module_id, impl_id));
             } else {
@@ -109,6 +108,24 @@ impl CrateImplBlocks {
     }
 }
 
+/// Rudimentary check whether an impl exists for a given type and trait; this
+/// will actually be done by chalk.
+pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> bool {
+    // FIXME use all trait impls in the whole crate graph
+    let krate = trait_ref.trait_.module(db).krate(db);
+    let krate = match krate {
+        Some(krate) => krate,
+        None => return false,
+    };
+    let crate_impl_blocks = db.impls_in_crate(krate);
+    for impl_block in crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_ref.trait_) {
+        if &impl_block.target_ty(db) == trait_ref.self_ty() {
+            return true;
+        }
+    }
+    false
+}
+
 fn def_crate(db: &impl HirDatabase, ty: &Ty) -> Option<Crate> {
     match ty {
         Ty::Apply(a_ty) => match a_ty.ctor {
@@ -162,7 +179,10 @@ impl Ty {
             }
         }
         // FIXME the implements check may result in other obligations or unifying variables?
-        candidates.retain(|(_t, _m)| /* self implements t */ true);
+        candidates.retain(|(t, _m)| {
+            let trait_ref = TraitRef { trait_: *t, substs: Substs::single(self.clone()) };
+            db.implements(trait_ref)
+        });
         // FIXME what happens if there are still multiple potential candidates?
         let (_chosen_trait, chosen_method) = candidates.first()?;
         Some((self.clone(), *chosen_method))
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 971043266..655f3c522 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -1920,7 +1920,7 @@ fn test() {
 [176; 178) 'S1': S1
 [176; 187) 'S1.method()': u32
 [203; 205) 'S2': S2
-[203; 214) 'S2.method()': u32"###
+[203; 214) 'S2.method()': i128"###
     );
 }