Refactor method candidate generation a bit

This fixes the order in which candidates are chosen a bit (not completely
though, as the ignored test demonstrates), and makes autoderef work with trait
methods. As a side effect, this also makes completion of trait methods work :)

4 files changed, 176 insertions, 55 deletions

diff --git a/crates/ra_hir/src/source_binder.rs b/crates/ra_hir/src/source_binder.rs
index bd035ced9..f1bb13bc6 100644
--- a/crates/ra_hir/src/source_binder.rs
+++ b/crates/ra_hir/src/source_binder.rs
@@ -18,7 +18,7 @@ use ra_syntax::{
 
 use crate::{
     HirDatabase, Function, Struct, Enum, Const, Static, Either, DefWithBody, PerNs, Name,
-    AsName, Module, HirFileId, Crate, Trait, Resolver,
+    AsName, Module, HirFileId, Crate, Trait, Resolver, Ty,
     expr::{BodySourceMap, scope::{ScopeId, ExprScopes}},
     ids::LocationCtx,
     expr, AstId
@@ -343,6 +343,16 @@ impl SourceAnalyzer {
             .collect()
     }
 
+    pub fn iterate_method_candidates<T>(
+        &self,
+        db: &impl HirDatabase,
+        ty: Ty,
+        name: Option<&Name>,
+        callback: impl FnMut(&Ty, Function) -> Option<T>,
+    ) -> Option<T> {
+        ty.iterate_method_candidates(db, &self.resolver, name, callback)
+    }
+
     #[cfg(test)]
     pub(crate) fn body_source_map(&self) -> Arc<BodySourceMap> {
         self.body_source_map.clone().unwrap()
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index 6b7918187..667b66095 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -129,85 +129,105 @@ impl Ty {
         name: &Name,
         resolver: &Resolver,
     ) -> Option<(Ty, Function)> {
-        // FIXME: trait methods should be used before autoderefs
-        // (and we need to do autoderefs for trait method calls as well)
-        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))
+        self.iterate_method_candidates(db, resolver, Some(name), |ty, f| Some((ty.clone(), f)))
     }
 
-    fn lookup_trait_method(
+    // This would be nicer if it just returned an iterator, but that runs into
+    // lifetime problems, because we need to borrow temp `CrateImplBlocks`.
+    pub(crate) fn iterate_method_candidates<T>(
         self,
         db: &impl HirDatabase,
-        name: &Name,
         resolver: &Resolver,
-    ) -> Option<(Ty, Function)> {
-        let mut candidates = Vec::new();
-        for t in resolver.traits_in_scope() {
+        name: Option<&Name>,
+        mut callback: impl FnMut(&Ty, Function) -> Option<T>,
+    ) -> Option<T> {
+        // For method calls, rust first does any number of autoderef, and then one
+        // autoref (i.e. when the method takes &self or &mut self). We just ignore
+        // the autoref currently -- when we find a method matching the given name,
+        // we assume it fits.
+
+        // Also note that when we've got a receiver like &S, even if the method we
+        // find in the end takes &self, we still do the autoderef step (just as
+        // rustc does an autoderef and then autoref again).
+
+        for derefed_ty in self.autoderef(db) {
+            if let Some(result) = derefed_ty.iterate_inherent_methods(db, name, &mut callback) {
+                return Some(result);
+            }
+            if let Some(result) =
+                derefed_ty.iterate_trait_method_candidates(db, resolver, name, &mut callback)
+            {
+                return Some(result);
+            }
+        }
+        None
+    }
+
+    fn iterate_trait_method_candidates<T>(
+        &self,
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        name: Option<&Name>,
+        mut callback: impl FnMut(&Ty, Function) -> Option<T>,
+    ) -> Option<T> {
+        'traits: for t in resolver.traits_in_scope() {
             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
+            // iteration
+            let mut known_implemented = false;
             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));
+                        if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() {
+                            if !known_implemented {
+                                let trait_ref = TraitRef {
+                                    trait_: t,
+                                    substs: fresh_substs_for_trait(db, t, self.clone()),
+                                };
+                                let (trait_ref, _) = super::traits::canonicalize(trait_ref);
+                                if db.implements(trait_ref).is_none() {
+                                    continue 'traits;
+                                }
+                            }
+                            known_implemented = true;
+                            if let Some(result) = callback(self, m) {
+                                return Some(result);
+                            }
                         }
                     }
                     _ => {}
                 }
             }
         }
-        candidates.retain(|(t, _m)| {
-            let trait_ref =
-                TraitRef { trait_: *t, substs: fresh_substs_for_trait(db, *t, self.clone()) };
-            let (trait_ref, _) = super::traits::canonicalize(trait_ref);
-            db.implements(trait_ref).is_some()
-        });
-        // FIXME if there's multiple candidates here, that's an ambiguity error
-        let (_chosen_trait, chosen_method) = candidates.first()?;
-        // FIXME return correct receiver type
-        Some((self.clone(), *chosen_method))
+        None
     }
 
-    // This would be nicer if it just returned an iterator, but that runs into
-    // lifetime problems, because we need to borrow temp `CrateImplBlocks`.
-    pub fn iterate_methods<T>(
-        self,
+    fn iterate_inherent_methods<T>(
+        &self,
         db: &impl HirDatabase,
+        name: Option<&Name>,
         mut callback: impl FnMut(&Ty, Function) -> Option<T>,
     ) -> Option<T> {
-        // For method calls, rust first does any number of autoderef, and then one
-        // autoref (i.e. when the method takes &self or &mut self). We just ignore
-        // the autoref currently -- when we find a method matching the given name,
-        // we assume it fits.
-
-        // Also note that when we've got a receiver like &S, even if the method we
-        // find in the end takes &self, we still do the autoderef step (just as
-        // rustc does an autoderef and then autoref again).
+        let krate = match def_crate(db, self) {
+            Some(krate) => krate,
+            None => return None,
+        };
+        let impls = db.impls_in_crate(krate);
 
-        for derefed_ty in self.autoderef(db) {
-            let krate = match def_crate(db, &derefed_ty) {
-                Some(krate) => krate,
-                None => continue,
-            };
-            let impls = db.impls_in_crate(krate);
-
-            for impl_block in impls.lookup_impl_blocks(&derefed_ty) {
-                for item in impl_block.items(db) {
-                    match item {
-                        ImplItem::Method(f) => {
-                            if let Some(result) = callback(&derefed_ty, f) {
+        for impl_block in impls.lookup_impl_blocks(self) {
+            for item in impl_block.items(db) {
+                match item {
+                    ImplItem::Method(f) => {
+                        let sig = f.signature(db);
+                        if name.map_or(true, |name| sig.name() == name) && sig.has_self_param() {
+                            if let Some(result) = callback(self, f) {
                                 return Some(result);
                             }
                         }
-                        _ => {}
                     }
+                    _ => {}
                 }
             }
         }
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 291bc9ae5..82c4aeddb 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -2336,6 +2336,66 @@ fn test() -> u64 {
     );
 }
 
+#[ignore]
+#[test]
+fn method_resolution_trait_before_autoref() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Trait { fn foo(self) -> u128; }
+struct S;
+impl S { fn foo(&self) -> i8 { 0 } }
+impl Trait for S { fn foo(self) -> u128 { 0 } }
+fn test() { S.foo()<|>; }
+"#,
+    );
+    assert_eq!(t, "u128");
+}
+
+#[test]
+fn method_resolution_trait_before_autoderef() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Trait { fn foo(self) -> u128; }
+struct S;
+impl S { fn foo(self) -> i8 { 0 } }
+impl Trait for &S { fn foo(self) -> u128 { 0 } }
+fn test() { (&S).foo()<|>; }
+"#,
+    );
+    assert_eq!(t, "u128");
+}
+
+#[test]
+fn method_resolution_impl_before_trait() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Trait { fn foo(self) -> u128; }
+struct S;
+impl S { fn foo(self) -> i8 { 0 } }
+impl Trait for S { fn foo(self) -> u128 { 0 } }
+fn test() { S.foo()<|>; }
+"#,
+    );
+    assert_eq!(t, "i8");
+}
+
+#[test]
+fn method_resolution_trait_autoderef() {
+    let t = type_at(
+        r#"
+//- /main.rs
+trait Trait { fn foo(self) -> u128; }
+struct S;
+impl Trait for S { fn foo(self) -> u128 { 0 } }
+fn test() { (&S).foo()<|>; }
+"#,
+    );
+    assert_eq!(t, "u128");
+}
+
 fn type_at_pos(db: &MockDatabase, pos: FilePosition) -> String {
     let file = db.parse(pos.file_id);
     let expr = algo::find_node_at_offset::<ast::Expr>(file.syntax(), pos.offset).unwrap();
@@ -2344,6 +2404,11 @@ fn type_at_pos(db: &MockDatabase, pos: FilePosition) -> String {
     ty.display(db).to_string()
 }
 
+fn type_at(content: &str) -> String {
+    let (db, file_pos) = MockDatabase::with_position(content);
+    type_at_pos(&db, file_pos)
+}
+
 fn infer(content: &str) -> String {
     let (db, _, file_id) = MockDatabase::with_single_file(content);
     let source_file = db.parse(file_id);
diff --git a/crates/ra_ide_api/src/completion/complete_dot.rs b/crates/ra_ide_api/src/completion/complete_dot.rs
index 4a111aba5..e34ddf24a 100644
--- a/crates/ra_ide_api/src/completion/complete_dot.rs
+++ b/crates/ra_ide_api/src/completion/complete_dot.rs
@@ -37,7 +37,7 @@ fn complete_fields(acc: &mut Completions, ctx: &CompletionContext, receiver: Ty)
 }
 
 fn complete_methods(acc: &mut Completions, ctx: &CompletionContext, receiver: Ty) {
-    receiver.iterate_methods(ctx.db, |_ty, func| {
+    ctx.analyzer.iterate_method_candidates(ctx.db, receiver, None, |_ty, func| {
         let sig = func.signature(ctx.db);
         if sig.has_self_param() {
             acc.add_function(ctx, func);
@@ -196,6 +196,32 @@ mod tests {
     }
 
     #[test]
+    fn test_trait_method_completion() {
+        assert_debug_snapshot_matches!(
+            do_ref_completion(
+                r"
+            struct A {}
+            trait Trait { fn the_method(&self); }
+            impl Trait for A {}
+            fn foo(a: A) {
+               a.<|>
+            }
+            ",
+            ),
+            @r###"[
+    CompletionItem {
+        label: "the_method",
+        source_range: [151; 151),
+        delete: [151; 151),
+        insert: "the_method()$0",
+        kind: Method,
+        detail: "fn the_method(&self)"
+    }
+]"###
+        );
+    }
+
+    #[test]
     fn test_no_non_self_method() {
         assert_debug_snapshot_matches!(
         do_ref_completion(