Implement basic inherent method resolution

11 files changed, 309 insertions, 17 deletions

diff --git a/crates/ra_hir/src/code_model_api.rs b/crates/ra_hir/src/code_model_api.rs
index d4244f70c..9c28b62af 100644
--- a/crates/ra_hir/src/code_model_api.rs
+++ b/crates/ra_hir/src/code_model_api.rs
@@ -113,6 +113,11 @@ impl Module {
         self.child_impl(db, name)
     }
 
+    /// Iterates over all child modules.
+    pub fn children(&self, db: &impl HirDatabase) -> Cancelable<impl Iterator<Item = Module>> {
+        self.children_impl(db)
+    }
+
     /// Finds a parent module.
     pub fn parent(&self, db: &impl HirDatabase) -> Cancelable<Option<Module>> {
         self.parent_impl(db)
@@ -270,6 +275,9 @@ pub struct FnSignature {
     pub(crate) name: Name,
     pub(crate) args: Vec<TypeRef>,
     pub(crate) ret_type: TypeRef,
+    /// True if the first arg is `self`. This is relevant to decide whether this
+    /// can be called as a method.
+    pub(crate) has_self_arg: bool,
 }
 
 impl FnSignature {
@@ -284,6 +292,12 @@ impl FnSignature {
     pub fn ret_type(&self) -> &TypeRef {
         &self.ret_type
     }
+
+    /// True if the first arg is `self`. This is relevant to decide whether this
+    /// can be called as a method.
+    pub fn has_self_arg(&self) -> bool {
+        self.has_self_arg
+    }
 }
 
 impl Function {
diff --git a/crates/ra_hir/src/code_model_impl/function.rs b/crates/ra_hir/src/code_model_impl/function.rs
index 1ce939e05..77dddff79 100644
--- a/crates/ra_hir/src/code_model_impl/function.rs
+++ b/crates/ra_hir/src/code_model_impl/function.rs
@@ -43,6 +43,7 @@ impl FnSignature {
             .map(|n| n.as_name())
             .unwrap_or_else(Name::missing);
         let mut args = Vec::new();
+        let mut has_self_arg = false;
         if let Some(param_list) = node.param_list() {
             if let Some(self_param) = param_list.self_param() {
                 let self_type = if let Some(type_ref) = self_param.type_ref() {
@@ -60,6 +61,7 @@ impl FnSignature {
                     }
                 };
                 args.push(self_type);
+                has_self_arg = true;
             }
             for param in param_list.params() {
                 let type_ref = TypeRef::from_ast_opt(param.type_ref());
@@ -75,6 +77,7 @@ impl FnSignature {
             name,
             args,
             ret_type,
+            has_self_arg,
         };
         Arc::new(sig)
     }
diff --git a/crates/ra_hir/src/code_model_impl/module.rs b/crates/ra_hir/src/code_model_impl/module.rs
index e9ff06dc8..775dd6709 100644
--- a/crates/ra_hir/src/code_model_impl/module.rs
+++ b/crates/ra_hir/src/code_model_impl/module.rs
@@ -95,6 +95,21 @@ impl Module {
         Module::from_module_id(db, loc.source_root_id, child_id).map(Some)
     }
 
+    /// Iterates over all child modules.
+    pub fn children_impl(&self, db: &impl HirDatabase) -> Cancelable<impl Iterator<Item = Module>> {
+        // FIXME this should be implementable without collecting into a vec, but
+        // it's kind of hard since the iterator needs to keep a reference to the
+        // module tree.
+        let loc = self.def_id.loc(db);
+        let module_tree = db.module_tree(loc.source_root_id)?;
+        let children = loc
+            .module_id
+            .children(&module_tree)
+            .map(|(_, module_id)| Module::from_module_id(db, loc.source_root_id, module_id))
+            .collect::<Cancelable<Vec<_>>>()?;
+        Ok(children.into_iter())
+    }
+
     pub fn parent_impl(&self, db: &impl HirDatabase) -> Cancelable<Option<Module>> {
         let loc = self.def_id.loc(db);
         let module_tree = db.module_tree(loc.source_root_id)?;
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index a11c73db0..842f54f11 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -5,13 +5,13 @@ use ra_db::{SourceRootId, LocationIntener, SyntaxDatabase, Cancelable};
 
 use crate::{
     DefLoc, DefId, MacroCallLoc, MacroCallId, Name, HirFileId,
-    SourceFileItems, SourceItemId,
+    SourceFileItems, SourceItemId, Crate,
     query_definitions,
     FnSignature, FnScopes,
     macros::MacroExpansion,
     module_tree::{ModuleId, ModuleTree},
     nameres::{ItemMap, InputModuleItems},
-    ty::{InferenceResult, Ty},
+    ty::{InferenceResult, Ty, method_resolution::CrateImplBlocks},
     adt::{StructData, EnumData, EnumVariantData},
     impl_block::ModuleImplBlocks,
 };
@@ -102,6 +102,11 @@ pub trait HirDatabase: SyntaxDatabase
         use fn crate::impl_block::impls_in_module;
     }
 
+    fn impls_in_crate(krate: Crate) -> Cancelable<Arc<CrateImplBlocks>> {
+        type ImplsInCrateQuery;
+        use fn crate::ty::method_resolution::impls_in_crate;
+    }
+
     fn body_hir(def_id: DefId) -> Cancelable<Arc<crate::expr::Body>> {
         type BodyHirQuery;
         use fn crate::expr::body_hir;
diff --git a/crates/ra_hir/src/impl_block.rs b/crates/ra_hir/src/impl_block.rs
index 4acda9af3..23c1d98d5 100644
--- a/crates/ra_hir/src/impl_block.rs
+++ b/crates/ra_hir/src/impl_block.rs
@@ -33,20 +33,27 @@ impl ImplBlock {
         })
     }
 
+    pub(crate) fn from_id(module_impl_blocks: Arc<ModuleImplBlocks>, impl_id: ImplId) -> ImplBlock {
+        ImplBlock {
+            module_impl_blocks,
+            impl_id,
+        }
+    }
+
     fn impl_data(&self) -> &ImplData {
         &self.module_impl_blocks.impls[self.impl_id]
     }
 
     pub fn target_trait(&self) -> Option<&TypeRef> {
-        self.impl_data().target_trait.as_ref()
+        self.impl_data().target_trait()
     }
 
     pub fn target_type(&self) -> &TypeRef {
-        &self.impl_data().target_type
+        self.impl_data().target_type()
     }
 
     pub fn items(&self) -> &[ImplItem] {
-        &self.impl_data().items
+        self.impl_data().items()
     }
 }
 
@@ -64,7 +71,7 @@ impl ImplData {
         module: &Module,
         node: &ast::ImplBlock,
     ) -> Self {
-        let target_trait = node.target_type().map(TypeRef::from_ast);
+        let target_trait = node.target_trait().map(TypeRef::from_ast);
         let target_type = TypeRef::from_ast_opt(node.target_type());
         let module_loc = module.def_id.loc(db);
         let items = if let Some(item_list) = node.item_list() {
@@ -103,6 +110,18 @@ impl ImplData {
             items,
         }
     }
+
+    pub fn target_trait(&self) -> Option<&TypeRef> {
+        self.target_trait.as_ref()
+    }
+
+    pub fn target_type(&self) -> &TypeRef {
+        &self.target_type
+    }
+
+    pub fn items(&self) -> &[ImplItem] {
+        &self.items
+    }
 }
 
 #[derive(Debug, Clone, PartialEq, Eq)]
@@ -133,11 +152,9 @@ impl_arena_id!(ImplId);
 /// This way, we avoid having to do this process for the whole crate whenever
 /// a file is changed; as long as the impl blocks in the file don't change,
 /// we don't need to do the second step again.
-///
-/// (The second step does not yet exist.)
 #[derive(Debug, PartialEq, Eq)]
 pub struct ModuleImplBlocks {
-    impls: Arena<ImplId, ImplData>,
+    pub(crate) impls: Arena<ImplId, ImplData>,
     impls_by_def: FxHashMap<DefId, ImplId>,
 }
 
@@ -153,7 +170,10 @@ impl ModuleImplBlocks {
         let (file_id, module_source) = module.definition_source(db)?;
         let node = match &module_source {
             ModuleSource::SourceFile(node) => node.syntax(),
-            ModuleSource::Module(node) => node.syntax(),
+            ModuleSource::Module(node) => match node.item_list() {
+                Some(item_list) => item_list.syntax(),
+                None => return Ok(()),
+            },
         };
 
         let source_file_items = db.file_items(file_id.into());
diff --git a/crates/ra_hir/src/mock.rs b/crates/ra_hir/src/mock.rs
index 6f93bb59d..9371c5a0d 100644
--- a/crates/ra_hir/src/mock.rs
+++ b/crates/ra_hir/src/mock.rs
@@ -235,6 +235,7 @@ salsa::database_storage! {
             fn enum_data() for db::EnumDataQuery;
             fn enum_variant_data() for db::EnumVariantDataQuery;
             fn impls_in_module() for db::ImplsInModuleQuery;
+            fn impls_in_crate() for db::ImplsInCrateQuery;
             fn body_hir() for db::BodyHirQuery;
             fn body_syntax_mapping() for db::BodySyntaxMappingQuery;
             fn fn_signature() for db::FnSignatureQuery;
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 2d533eb6a..2dcba5283 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -17,6 +17,7 @@ mod autoderef;
 mod primitive;
 #[cfg(test)]
 mod tests;
+pub(crate) mod method_resolution;
 
 use std::borrow::Cow;
 use std::ops::Index;
@@ -891,14 +892,38 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
                 }
                 ret_ty
             }
-            Expr::MethodCall { receiver, args, .. } => {
-                let _receiver_ty = self.infer_expr(*receiver, &Expectation::none())?;
-                // TODO resolve method...
-                for (_i, arg) in args.iter().enumerate() {
-                    // TODO unify / expect argument type
-                    self.infer_expr(*arg, &Expectation::none())?;
+            Expr::MethodCall {
+                receiver,
+                args,
+                method_name,
+            } => {
+                let receiver_ty = self.infer_expr(*receiver, &Expectation::none())?;
+                let resolved = receiver_ty.clone().lookup_method(self.db, method_name)?;
+                let method_ty = match resolved {
+                    Some(def_id) => self.db.type_for_def(def_id)?,
+                    None => Ty::Unknown,
+                };
+                let method_ty = self.insert_type_vars(method_ty);
+                let (expected_receiver_ty, arg_tys, ret_ty) = match &method_ty {
+                    Ty::FnPtr(sig) => {
+                        if sig.input.len() > 0 {
+                            (&sig.input[0], &sig.input[1..], sig.output.clone())
+                        } else {
+                            (&Ty::Unknown, &[][..], sig.output.clone())
+                        }
+                    }
+                    _ => (&Ty::Unknown, &[][..], Ty::Unknown),
+                };
+                // TODO we would have to apply the autoderef/autoref steps here
+                // to get the correct receiver type to unify...
+                self.unify(expected_receiver_ty, &receiver_ty);
+                for (i, arg) in args.iter().enumerate() {
+                    self.infer_expr(
+                        *arg,
+                        &Expectation::has_type(arg_tys.get(i).cloned().unwrap_or(Ty::Unknown)),
+                    )?;
                 }
-                Ty::Unknown
+                ret_ty
             }
             Expr::Match { expr, arms } => {
                 let _ty = self.infer_expr(*expr, &Expectation::none())?;
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
new file mode 100644
index 000000000..ad80aa8b6
--- /dev/null
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -0,0 +1,164 @@
+//! This module is concerned with finding methods that a given type provides.
+//! For details about how this works in rustc, see the method lookup page in the
+//! [rustc guide](https://rust-lang.github.io/rustc-guide/method-lookup.html)
+//! and the corresponding code mostly in librustc_typeck/check/method/probe.rs.
+use std::sync::Arc;
+
+use rustc_hash::FxHashMap;
+
+use ra_db::{Cancelable, SourceRootId};
+
+use crate::{HirDatabase, DefId, module_tree::ModuleId, Module, Crate, Name, Function, impl_block::{ImplId, ImplBlock, ImplItem}};
+use super::Ty;
+
+/// This is used as a key for indexing impls.
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
+pub enum TyFingerprint {
+    Adt(DefId),
+    // we'll also want to index impls for primitive types etc.
+}
+
+impl TyFingerprint {
+    /// Creates a TyFingerprint for looking up an impl. Only certain types can
+    /// have impls: if we have some `struct S`, we can have an `impl S`, but not
+    /// `impl &S`. Hence, this will return `None` for reference types and such.
+    fn for_impl(ty: &Ty) -> Option<TyFingerprint> {
+        match ty {
+            Ty::Adt { def_id, .. } => Some(TyFingerprint::Adt(*def_id)),
+            _ => None,
+        }
+    }
+}
+
+#[derive(Debug, PartialEq, Eq)]
+pub struct CrateImplBlocks {
+    /// To make sense of the ModuleIds, we need the source root.
+    source_root_id: SourceRootId,
+    impls: FxHashMap<TyFingerprint, Vec<(ModuleId, ImplId)>>,
+}
+
+impl CrateImplBlocks {
+    pub fn lookup_impl_blocks<'a>(
+        &'a self,
+        db: &'a impl HirDatabase,
+        ty: &Ty,
+    ) -> impl Iterator<Item = Cancelable<ImplBlock>> + 'a {
+        let fingerprint = TyFingerprint::for_impl(ty);
+        fingerprint
+            .and_then(|f| self.impls.get(&f))
+            .into_iter()
+            .flat_map(|i| i.iter())
+            .map(move |(module_id, impl_id)| {
+                let module_impl_blocks = db.impls_in_module(self.source_root_id, *module_id)?;
+                Ok(ImplBlock::from_id(module_impl_blocks, *impl_id))
+            })
+    }
+
+    fn collect_recursive(&mut self, db: &impl HirDatabase, module: Module) -> Cancelable<()> {
+        let module_id = module.def_id.loc(db).module_id;
+        let module_impl_blocks = db.impls_in_module(self.source_root_id, module_id)?;
+
+        for (impl_id, impl_data) in module_impl_blocks.impls.iter() {
+            let impl_block = ImplBlock::from_id(Arc::clone(&module_impl_blocks), impl_id);
+
+            if let Some(_target_trait) = impl_data.target_trait() {
+                // ignore for now
+            } else {
+                let target_ty =
+                    Ty::from_hir(db, &module, Some(&impl_block), impl_data.target_type())?;
+                if let Some(target_ty_fp) = TyFingerprint::for_impl(&target_ty) {
+                    self.impls
+                        .entry(target_ty_fp)
+                        .or_insert_with(Vec::new)
+                        .push((module_id, impl_id));
+                }
+            }
+        }
+
+        for child in module.children(db)? {
+            self.collect_recursive(db, child)?;
+        }
+
+        Ok(())
+    }
+}
+
+pub(crate) fn impls_in_crate(
+    db: &impl HirDatabase,
+    krate: Crate,
+) -> Cancelable<Arc<CrateImplBlocks>> {
+    let crate_graph = db.crate_graph();
+    let file_id = crate_graph.crate_root(krate.crate_id);
+    let source_root_id = db.file_source_root(file_id);
+    let mut crate_impl_blocks = CrateImplBlocks {
+        source_root_id,
+        impls: FxHashMap::default(),
+    };
+    if let Some(module) = krate.root_module(db)? {
+        crate_impl_blocks.collect_recursive(db, module)?;
+    }
+    Ok(Arc::new(crate_impl_blocks))
+}
+
+fn def_crate(db: &impl HirDatabase, ty: &Ty) -> Cancelable<Option<Crate>> {
+    match ty {
+        Ty::Adt { def_id, .. } => def_id.krate(db),
+        _ => Ok(None),
+    }
+}
+
+impl Ty {
+    // TODO: cache this as a query?
+    // - if so, what signature? (TyFingerprint, Name)?
+    // - or maybe cache all names and def_ids of methods per fingerprint?
+    pub fn lookup_method(self, db: &impl HirDatabase, name: &Name) -> Cancelable<Option<DefId>> {
+        self.iterate_methods(db, |f| {
+            let sig = f.signature(db);
+            if sig.name() == name && sig.has_self_arg() {
+                Ok(Some(f.def_id()))
+            } else {
+                Ok(None)
+            }
+        })
+    }
+
+    // This would be nicer if it just returned an iterator, but that's really
+    // complicated with all the cancelable operations
+    pub fn iterate_methods<T>(
+        self,
+        db: &impl HirDatabase,
+        mut callback: impl FnMut(Function) -> Cancelable<Option<T>>,
+    ) -> Cancelable<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) {
+            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(db, &derefed_ty) {
+                let impl_block = impl_block?;
+                for item in impl_block.items() {
+                    match item {
+                        ImplItem::Method(f) => {
+                            if let Some(result) = callback(f.clone())? {
+                                return Ok(Some(result));
+                            }
+                        }
+                        _ => {}
+                    }
+                }
+            }
+        }
+        Ok(None)
+    }
+}
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 815aecda7..1c3129441 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -242,6 +242,32 @@ fn test() {
     );
 }
 
+#[test]
+fn infer_inherent_method() {
+    check_inference(
+        r#"
+struct A;
+
+impl A {
+    fn foo(self, x: u32) -> i32 {}
+}
+
+mod b {
+    impl super::A {
+        fn bar(&self, x: u64) -> i64 {}
+    }
+}
+
+fn test(a: A) {
+    a.foo(1);
+    (&a).bar(1);
+    a.bar(1);
+}
+"#,
+        "inherent_method.txt",
+    );
+}
+
 fn infer(content: &str) -> String {
     let (db, _, file_id) = MockDatabase::with_single_file(content);
     let source_file = db.source_file(file_id);
diff --git a/crates/ra_hir/src/ty/tests/data/inherent_method.txt b/crates/ra_hir/src/ty/tests/data/inherent_method.txt
new file mode 100644
index 000000000..6e6f70357
--- /dev/null
+++ b/crates/ra_hir/src/ty/tests/data/inherent_method.txt
@@ -0,0 +1,18 @@
+[32; 36) 'self': A
+[38; 39) 'x': u32
+[53; 55) '{}': ()
+[103; 107) 'self': &A
+[109; 110) 'x': u64
+[124; 126) '{}': ()
+[144; 145) 'a': A
+[150; 198) '{     ...(1); }': ()
+[156; 157) 'a': A
+[156; 164) 'a.foo(1)': i32
+[162; 163) '1': u32
+[170; 181) '(&a).bar(1)': i64
+[171; 173) '&a': &A
+[172; 173) 'a': A
+[179; 180) '1': u64
+[187; 188) 'a': A
+[187; 195) 'a.bar(1)': i64
+[193; 194) '1': u64
diff --git a/crates/ra_ide_api/src/db.rs b/crates/ra_ide_api/src/db.rs
index efdf261be..60f84675d 100644
--- a/crates/ra_ide_api/src/db.rs
+++ b/crates/ra_ide_api/src/db.rs
@@ -124,6 +124,7 @@ salsa::database_storage! {
             fn enum_data() for hir::db::EnumDataQuery;
             fn enum_variant_data() for hir::db::EnumVariantDataQuery;
             fn impls_in_module() for hir::db::ImplsInModuleQuery;
+            fn impls_in_crate() for hir::db::ImplsInCrateQuery;
             fn body_hir() for hir::db::BodyHirQuery;
             fn body_syntax_mapping() for hir::db::BodySyntaxMappingQuery;
             fn fn_signature() for hir::db::FnSignatureQuery;