11 files changed, 156 insertions, 25 deletions

diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs
index 5437133b8..88c13566c 100644
--- a/crates/ra_hir/src/code_model_api.rs
+++ b/crates/ra_hir/src/code_model_api.rs
@@ -17,6 +17,7 @@ use crate::{
     impl_block::ImplBlock,
     resolve::Resolver,
     diagnostics::DiagnosticSink,
+    traits::{TraitItem, TraitData},
 };
 
 /// hir::Crate describes a single crate. It's the main interface with which
@@ -649,6 +650,18 @@ impl Trait {
     pub fn generic_params(&self, db: &impl DefDatabase) -> Arc<GenericParams> {
         db.generic_params((*self).into())
     }
+
+    pub fn name(self, db: &impl DefDatabase) -> Option<Name> {
+        self.trait_data(db).name().clone()
+    }
+
+    pub fn items(self, db: &impl DefDatabase) -> Vec<TraitItem> {
+        self.trait_data(db).items().to_vec()
+    }
+
+    pub(crate) fn trait_data(self, db: &impl DefDatabase) -> Arc<TraitData> {
+        db.trait_data(self)
+    }
 }
 
 impl Docs for Trait {
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index d3908f8ac..dd0bf6e34 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -14,6 +14,7 @@ use crate::{
     impl_block::{ModuleImplBlocks, ImplSourceMap},
     generics::{GenericParams, GenericDef},
     type_ref::TypeRef,
+    traits::TraitData, Trait
 };
 
 #[salsa::query_group(DefDatabaseStorage)]
@@ -27,6 +28,9 @@ pub trait DefDatabase: SourceDatabase + AsRef<HirInterner> {
     #[salsa::invoke(crate::adt::EnumData::enum_data_query)]
     fn enum_data(&self, e: Enum) -> Arc<EnumData>;
 
+    #[salsa::invoke(crate::traits::TraitData::trait_data_query)]
+    fn trait_data(&self, t: Trait) -> Arc<TraitData>;
+
     #[salsa::invoke(crate::ids::SourceFileItems::file_items_query)]
     fn file_items(&self, file_id: HirFileId) -> Arc<SourceFileItems>;
 
diff --git a/crates/ra_hir/src/lib.rs b/crates/ra_hir/src/lib.rs
index ce54d7608..974ebd831 100644
--- a/crates/ra_hir/src/lib.rs
+++ b/crates/ra_hir/src/lib.rs
@@ -27,6 +27,7 @@ mod ids;
 mod name;
 mod nameres;
 mod adt;
+mod traits;
 mod type_alias;
 mod type_ref;
 mod ty;
diff --git a/crates/ra_hir/src/nameres.rs b/crates/ra_hir/src/nameres.rs
index 56ed872d5..c34aa4b50 100644
--- a/crates/ra_hir/src/nameres.rs
+++ b/crates/ra_hir/src/nameres.rs
@@ -62,7 +62,7 @@ use test_utils::tested_by;
 
 use crate::{
     ModuleDef, Name, Crate, Module,
-    DefDatabase, Path, PathKind, HirFileId,
+    DefDatabase, Path, PathKind, HirFileId, Trait,
     ids::{SourceItemId, SourceFileItemId, MacroCallId},
     diagnostics::DiagnosticSink,
     nameres::diagnostics::DefDiagnostic,
@@ -139,6 +139,12 @@ impl ModuleScope {
     pub fn get(&self, name: &Name) -> Option<&Resolution> {
         self.items.get(name)
     }
+    pub fn traits<'a>(&'a self) -> impl Iterator<Item = Trait> + 'a {
+        self.items.values().filter_map(|r| match r.def.take_types() {
+            Some(ModuleDef::Trait(t)) => Some(t),
+            _ => None,
+        })
+    }
 }
 
 #[derive(Debug, Clone, PartialEq, Eq, Default)]
diff --git a/crates/ra_hir/src/resolve.rs b/crates/ra_hir/src/resolve.rs
index f28154517..0f5031e76 100644
--- a/crates/ra_hir/src/resolve.rs
+++ b/crates/ra_hir/src/resolve.rs
@@ -11,7 +11,7 @@ use crate::{
     generics::GenericParams,
     expr::{scope::{ExprScopes, ScopeId}, PatId, Body},
     impl_block::ImplBlock,
-    path::Path,
+    path::Path, Trait
 };
 
 #[derive(Debug, Clone, Default)]
@@ -175,6 +175,21 @@ 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,
+                }
+                .into_iter()
+            })
+            .flat_map(|i| i)
+    }
+
     fn module(&self) -> Option<(&CrateDefMap, CrateModuleId)> {
         self.scopes.iter().rev().find_map(|scope| match scope {
             Scope::ModuleScope(m) => Some((&*m.crate_def_map, m.module_id)),
diff --git a/crates/ra_hir/src/traits.rs b/crates/ra_hir/src/traits.rs
new file mode 100644
index 000000000..725bdd5cb
--- /dev/null
+++ b/crates/ra_hir/src/traits.rs
@@ -0,0 +1,52 @@
+//! HIR for trait definitions.
+
+use std::sync::Arc;
+
+use ra_syntax::ast::{self, NameOwner};
+
+use crate::{Function, Const, TypeAlias, Name, DefDatabase, Trait, ids::LocationCtx, name::AsName};
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct TraitData {
+    name: Option<Name>,
+    items: Vec<TraitItem>,
+}
+
+impl TraitData {
+    pub(crate) fn trait_data_query(db: &impl DefDatabase, tr: Trait) -> Arc<TraitData> {
+        let (file_id, node) = tr.source(db);
+        let name = node.name().map(|n| n.as_name());
+        let module = tr.module(db);
+        let ctx = LocationCtx::new(db, module, file_id);
+        let items = if let Some(item_list) = node.item_list() {
+            item_list
+                .impl_items()
+                .map(|item_node| match item_node.kind() {
+                    ast::ImplItemKind::FnDef(it) => Function { id: ctx.to_def(it) }.into(),
+                    ast::ImplItemKind::ConstDef(it) => Const { id: ctx.to_def(it) }.into(),
+                    ast::ImplItemKind::TypeAliasDef(it) => TypeAlias { id: ctx.to_def(it) }.into(),
+                })
+                .collect()
+        } else {
+            Vec::new()
+        };
+        Arc::new(TraitData { name, items })
+    }
+
+    pub(crate) fn name(&self) -> &Option<Name> {
+        &self.name
+    }
+
+    pub(crate) fn items(&self) -> &[TraitItem] {
+        &self.items
+    }
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub enum TraitItem {
+    Function(Function),
+    Const(Const),
+    TypeAlias(TypeAlias),
+    // Existential
+}
+impl_froms!(TraitItem: Function, Const, TypeAlias);
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index 5fd602a9e..573115321 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -821,7 +821,8 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
             }
             Expr::MethodCall { receiver, args, method_name, generic_args } => {
                 let receiver_ty = self.infer_expr(*receiver, &Expectation::none());
-                let resolved = receiver_ty.clone().lookup_method(self.db, method_name);
+                let resolved =
+                    receiver_ty.clone().lookup_method(self.db, method_name, &self.resolver);
                 let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
                     Some((ty, func)) => {
                         self.write_method_resolution(tgt_expr, func);
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index b1684acf9..708a435b4 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -11,7 +11,7 @@ use crate::{
     ids::TraitId,
     impl_block::{ImplId, ImplBlock, ImplItem},
     ty::{Ty, TypeCtor},
-    nameres::CrateModuleId,
+    nameres::CrateModuleId, resolve::Resolver, traits::TraitItem
 
 };
 
@@ -73,18 +73,18 @@ impl CrateImplBlocks {
 
             let target_ty = impl_block.target_ty(db);
 
-            if let Some(target_ty_fp) = TyFingerprint::for_impl(&target_ty) {
-                self.impls
-                    .entry(target_ty_fp)
-                    .or_insert_with(Vec::new)
-                    .push((module.module_id, impl_id));
-            }
-
             if let Some(tr) = impl_block.target_trait(db) {
                 self.impls_by_trait
                     .entry(tr.id)
                     .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
+                        .entry(target_ty_fp)
+                        .or_insert_with(Vec::new)
+                        .push((module.module_id, impl_id));
+                }
             }
         }
 
@@ -120,20 +120,52 @@ fn def_crate(db: &impl HirDatabase, ty: &Ty) -> Option<Crate> {
 }
 
 impl Ty {
-    // FIXME: cache this as a query?
-    // - if so, what signature? (TyFingerprint, Name)?
-    // - or maybe cache all names and def_ids of methods per fingerprint?
     /// Look up the method with the given name, returning the actual autoderefed
     /// receiver type (but without autoref applied yet).
-    pub fn lookup_method(self, db: &impl HirDatabase, name: &Name) -> Option<(Ty, Function)> {
-        self.iterate_methods(db, |ty, f| {
+    pub fn lookup_method(
+        self,
+        db: &impl HirDatabase,
+        name: &Name,
+        resolver: &Resolver,
+    ) -> Option<(Ty, Function)> {
+        // FIXME: what has priority, an inherent method that needs autoderefs or a trait method?
+        let inherent_method = self.clone().iterate_methods(db, |ty, f| {
             let sig = f.signature(db);
             if sig.name() == name && sig.has_self_param() {
                 Some((ty.clone(), f))
             } else {
                 None
             }
-        })
+        });
+        inherent_method.or_else(|| self.lookup_trait_method(db, name, resolver))
+    }
+
+    fn lookup_trait_method(
+        self,
+        db: &impl HirDatabase,
+        name: &Name,
+        resolver: &Resolver,
+    ) -> Option<(Ty, Function)> {
+        let mut candidates = Vec::new();
+        for t in resolver.traits_in_scope() {
+            let data = t.trait_data(db);
+            for item in data.items() {
+                match item {
+                    &TraitItem::Function(m) => {
+                        let sig = m.signature(db);
+                        if sig.name() == name && sig.has_self_param() {
+                            candidates.push((t, m));
+                        }
+                    }
+                    _ => {}
+                }
+            }
+        }
+        // FIXME the implements check may result in other obligations or unifying variables?
+        candidates.retain(|(_t, _m)| /* self implements t */ true);
+        // FIXME what happens if there are still multiple potential candidates?
+        let (_chosen_trait, chosen_method) = candidates.first()?;
+        Some((self.clone(), *chosen_method))
     }
 
     // This would be nicer if it just returned an iterator, but that runs into
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 3aedba243..971043266 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -1272,8 +1272,8 @@ fn test() {
 [241; 252) 'Struct::FOO': u32
 [262; 263) 'y': u32
 [266; 275) 'Enum::BAR': u32
-[285; 286) 'z': u32
-[289; 302) 'TraitTest::ID': u32"###
+[285; 286) 'z': {unknown}
+[289; 302) 'TraitTest::ID': {unknown}"###
     );
 }
 
@@ -1918,9 +1918,9 @@ fn test() {
 [110; 114) 'self': &{unknown}
 [170; 228) '{     ...i128 }': ()
 [176; 178) 'S1': S1
-[176; 187) 'S1.method()': {unknown}
+[176; 187) 'S1.method()': u32
 [203; 205) 'S2': S2
-[203; 214) 'S2.method()': {unknown}"###
+[203; 214) 'S2.method()': u32"###
     );
 }
 
@@ -1964,10 +1964,10 @@ mod bar_test {
 [169; 173) 'self': &{unknown}
 [300; 337) '{     ...     }': ()
 [310; 311) 'S': S
-[310; 320) 'S.method()': {unknown}
+[310; 320) 'S.method()': u32
 [416; 454) '{     ...     }': ()
 [426; 427) 'S': S
-[426; 436) 'S.method()': {unknown}"###
+[426; 436) 'S.method()': i128"###
     );
 }
 
diff --git a/crates/ra_syntax/src/ast/generated.rs b/crates/ra_syntax/src/ast/generated.rs
index 54b72f8c5..47a37e4d1 100644
--- a/crates/ra_syntax/src/ast/generated.rs
+++ b/crates/ra_syntax/src/ast/generated.rs
@@ -4061,7 +4061,11 @@ impl ast::NameOwner for TraitDef {}
 impl ast::AttrsOwner for TraitDef {}
 impl ast::DocCommentsOwner for TraitDef {}
 impl ast::TypeParamsOwner for TraitDef {}
-impl TraitDef {}
+impl TraitDef {
+    pub fn item_list(&self) -> Option<&ItemList> {
+        super::child_opt(self)
+    }
+}
 
 // TrueKw
 #[derive(Debug, PartialEq, Eq, Hash)]
diff --git a/crates/ra_syntax/src/grammar.ron b/crates/ra_syntax/src/grammar.ron
index 4f8e19bd0..ad6d74162 100644
--- a/crates/ra_syntax/src/grammar.ron
+++ b/crates/ra_syntax/src/grammar.ron
@@ -292,7 +292,10 @@ Grammar(
         ], options: [["variant_list", "EnumVariantList"]] ),
         "EnumVariantList": ( collections: [["variants", "EnumVariant"]] ),
         "EnumVariant": ( traits: ["NameOwner", "DocCommentsOwner", "AttrsOwner"], options: ["Expr"] ),
-        "TraitDef": ( traits: ["VisibilityOwner", "NameOwner", "AttrsOwner", "DocCommentsOwner", "TypeParamsOwner"] ),
+        "TraitDef": (
+            traits: ["VisibilityOwner", "NameOwner", "AttrsOwner", "DocCommentsOwner", "TypeParamsOwner"],
+            options: ["ItemList"]
+        ),
         "Module": (
             traits: ["VisibilityOwner", "NameOwner", "AttrsOwner", "DocCommentsOwner" ],
             options: [ "ItemList" ]