Merge #866

866: Implement basic support for Associated Methods r=flodiebold a=vipentti

This is my attempt at learning to understand how the type inference works by adding basic support for associated methods. Currently it does not resolve associated types or constants. 

The basic idea is that `Resolver::resolve_path` returns a new `PathResult` type, which has two variants, `FullyResolved` and `PartiallyResolved`, fully resolved matches the previous behavior, where as `PartiallyResolved` contains the `PerNs<Resolution` in addition to a `segment_index` which contains the index of the segment which we failed to resolve. This index can then be used to continue inference in `infer_path_expr` using the `Type` we managed to resolve.

This changes some of the previous apis, so looking for feedback and suggestions.

This should enable fixing #832

Co-authored-by: Ville Penttinen <[email protected]>

9 files changed, 410 insertions, 31 deletions

diff --git a/crates/ra_hir/src/nameres.rs b/crates/ra_hir/src/nameres.rs
index bd920bfea..8067b8415 100644
--- a/crates/ra_hir/src/nameres.rs
+++ b/crates/ra_hir/src/nameres.rs
@@ -297,7 +297,14 @@ where
             );
             (res, if res.is_none() { ReachedFixedPoint::No } else { ReachedFixedPoint::Yes })
         } else {
-            self.result.resolve_path_fp(self.db, ResolveMode::Import, original_module, &import.path)
+            let res = self.result.resolve_path_fp(
+                self.db,
+                ResolveMode::Import,
+                original_module,
+                &import.path,
+            );
+
+            (res.resolved_def, res.reached_fixedpoint)
         };
 
         if reached_fixedpoint != ReachedFixedPoint::Yes {
@@ -435,6 +442,27 @@ where
     }
 }
 
+#[derive(Debug, Clone)]
+struct ResolvePathResult {
+    resolved_def: PerNs<ModuleDef>,
+    segment_index: Option<usize>,
+    reached_fixedpoint: ReachedFixedPoint,
+}
+
+impl ResolvePathResult {
+    fn empty(reached_fixedpoint: ReachedFixedPoint) -> ResolvePathResult {
+        ResolvePathResult::with(PerNs::none(), reached_fixedpoint, None)
+    }
+
+    fn with(
+        resolved_def: PerNs<ModuleDef>,
+        reached_fixedpoint: ReachedFixedPoint,
+        segment_index: Option<usize>,
+    ) -> ResolvePathResult {
+        ResolvePathResult { resolved_def, reached_fixedpoint, segment_index }
+    }
+}
+
 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
 enum ResolveMode {
     Import,
@@ -468,8 +496,9 @@ impl ItemMap {
         db: &impl PersistentHirDatabase,
         original_module: Module,
         path: &Path,
-    ) -> PerNs<ModuleDef> {
-        self.resolve_path_fp(db, ResolveMode::Other, original_module, path).0
+    ) -> (PerNs<ModuleDef>, Option<usize>) {
+        let res = self.resolve_path_fp(db, ResolveMode::Other, original_module, path);
+        (res.resolved_def, res.segment_index)
     }
 
     fn resolve_in_prelude(
@@ -534,7 +563,7 @@ impl ItemMap {
         mode: ResolveMode,
         original_module: Module,
         path: &Path,
-    ) -> (PerNs<ModuleDef>, ReachedFixedPoint) {
+    ) -> ResolvePathResult {
         let mut segments = path.segments.iter().enumerate();
         let mut curr_per_ns: PerNs<ModuleDef> = match path.kind {
             PathKind::Crate => PerNs::types(original_module.crate_root(db).into()),
@@ -549,7 +578,7 @@ impl ItemMap {
             {
                 let segment = match segments.next() {
                     Some((_, segment)) => segment,
-                    None => return (PerNs::none(), ReachedFixedPoint::Yes),
+                    None => return ResolvePathResult::empty(ReachedFixedPoint::Yes),
                 };
                 log::debug!("resolving {:?} in crate root (+ extern prelude)", segment);
                 self.resolve_name_in_crate_root_or_extern_prelude(
@@ -561,7 +590,7 @@ impl ItemMap {
             PathKind::Plain => {
                 let segment = match segments.next() {
                     Some((_, segment)) => segment,
-                    None => return (PerNs::none(), ReachedFixedPoint::Yes),
+                    None => return ResolvePathResult::empty(ReachedFixedPoint::Yes),
                 };
                 log::debug!("resolving {:?} in module", segment);
                 self.resolve_name_in_module(db, original_module, &segment.name)
@@ -571,20 +600,20 @@ impl ItemMap {
                     PerNs::types(p.into())
                 } else {
                     log::debug!("super path in root module");
-                    return (PerNs::none(), ReachedFixedPoint::Yes);
+                    return ResolvePathResult::empty(ReachedFixedPoint::Yes);
                 }
             }
             PathKind::Abs => {
                 // 2018-style absolute path -- only extern prelude
                 let segment = match segments.next() {
                     Some((_, segment)) => segment,
-                    None => return (PerNs::none(), ReachedFixedPoint::Yes),
+                    None => return ResolvePathResult::empty(ReachedFixedPoint::Yes),
                 };
                 if let Some(def) = self.extern_prelude.get(&segment.name) {
                     log::debug!("absolute path {:?} resolved to crate {:?}", path, def);
                     PerNs::types(*def)
                 } else {
-                    return (PerNs::none(), ReachedFixedPoint::No); // extern crate declarations can add to the extern prelude
+                    return ResolvePathResult::empty(ReachedFixedPoint::No); // extern crate declarations can add to the extern prelude
                 }
             }
         };
@@ -598,7 +627,7 @@ impl ItemMap {
                     // (don't break here because `curr_per_ns` might contain
                     // something in the value namespace, and it would be wrong
                     // to return that)
-                    return (PerNs::none(), ReachedFixedPoint::No);
+                    return ResolvePathResult::empty(ReachedFixedPoint::No);
                 }
             };
             // resolve segment in curr
@@ -612,15 +641,15 @@ impl ItemMap {
                         };
                         log::debug!("resolving {:?} in other crate", path);
                         let item_map = db.item_map(module.krate);
-                        let def = item_map.resolve_path(db, *module, &path);
-                        return (def, ReachedFixedPoint::Yes);
+                        let (def, s) = item_map.resolve_path(db, *module, &path);
+                        return ResolvePathResult::with(def, ReachedFixedPoint::Yes, s);
                     }
 
                     match self[module.module_id].items.get(&segment.name) {
                         Some(res) if !res.def.is_none() => res.def,
                         _ => {
                             log::debug!("path segment {:?} not found", segment.name);
-                            return (PerNs::none(), ReachedFixedPoint::No);
+                            return ResolvePathResult::empty(ReachedFixedPoint::No);
                         }
                     }
                 }
@@ -629,23 +658,33 @@ impl ItemMap {
                     tested_by!(item_map_enum_importing);
                     match e.variant(db, &segment.name) {
                         Some(variant) => PerNs::both(variant.into(), variant.into()),
-                        None => PerNs::none(),
+                        None => {
+                            return ResolvePathResult::with(
+                                PerNs::types((*e).into()),
+                                ReachedFixedPoint::Yes,
+                                Some(i),
+                            );
+                        }
                     }
                 }
-                _ => {
+                s => {
                     // could be an inherent method call in UFCS form
-                    // (`Struct::method`), or some other kind of associated
-                    // item... Which we currently don't handle (TODO)
+                    // (`Struct::method`), or some other kind of associated item
                     log::debug!(
                         "path segment {:?} resolved to non-module {:?}, but is not last",
                         segment.name,
                         curr,
                     );
-                    return (PerNs::none(), ReachedFixedPoint::Yes);
+
+                    return ResolvePathResult::with(
+                        PerNs::types((*s).into()),
+                        ReachedFixedPoint::Yes,
+                        Some(i),
+                    );
                 }
             };
         }
-        (curr_per_ns, ReachedFixedPoint::Yes)
+        ResolvePathResult::with(curr_per_ns, ReachedFixedPoint::Yes, None)
     }
 }
 
diff --git a/crates/ra_hir/src/resolve.rs b/crates/ra_hir/src/resolve.rs
index 91a531801..57e7d0b9a 100644
--- a/crates/ra_hir/src/resolve.rs
+++ b/crates/ra_hir/src/resolve.rs
@@ -33,6 +33,67 @@ pub(crate) struct ExprScope {
 }
 
 #[derive(Debug, Clone)]
+pub(crate) struct PathResult {
+    /// The actual path resolution
+    resolution: PerNs<Resolution>,
+    /// The first index in the path that we
+    /// were unable to resolve.
+    /// When path is fully resolved, this is 0.
+    remaining_index: usize,
+}
+
+impl PathResult {
+    /// Returns the remaining index in the result
+    /// returns None if the path was fully resolved
+    pub(crate) fn remaining_index(&self) -> Option<usize> {
+        if self.remaining_index > 0 {
+            Some(self.remaining_index)
+        } else {
+            None
+        }
+    }
+
+    /// Consumes `PathResult` and returns the contained `PerNs<Resolution>`
+    /// if the path was fully resolved, meaning we have no remaining items
+    pub(crate) fn into_fully_resolved(self) -> PerNs<Resolution> {
+        if self.is_fully_resolved() {
+            self.resolution
+        } else {
+            PerNs::none()
+        }
+    }
+
+    /// Consumes `PathResult` and returns the resolution and the
+    /// remaining_index as a tuple.
+    pub(crate) fn into_inner(self) -> (PerNs<Resolution>, Option<usize>) {
+        let index = self.remaining_index();
+        (self.resolution, index)
+    }
+
+    /// Path is fully resolved when `remaining_index` is none
+    /// and the resolution contains anything
+    pub(crate) fn is_fully_resolved(&self) -> bool {
+        !self.resolution.is_none() && self.remaining_index().is_none()
+    }
+
+    fn empty() -> PathResult {
+        PathResult { resolution: PerNs::none(), remaining_index: 0 }
+    }
+
+    fn from_resolution(res: PerNs<Resolution>) -> PathResult {
+        PathResult::from_resolution_with_index(res, 0)
+    }
+
+    fn from_resolution_with_index(res: PerNs<Resolution>, remaining_index: usize) -> PathResult {
+        if res.is_none() {
+            PathResult::empty()
+        } else {
+            PathResult { resolution: res, remaining_index }
+        }
+    }
+}
+
+#[derive(Debug, Clone)]
 pub(crate) enum Scope {
     /// All the items and imported names of a module
     ModuleScope(ModuleItemMap),
@@ -67,21 +128,37 @@ impl Resolver {
         resolution
     }
 
-    pub fn resolve_path(&self, db: &impl HirDatabase, path: &Path) -> PerNs<Resolution> {
+    /// Returns the resolved path segments
+    /// Which may be fully resolved, empty or partially resolved.
+    pub(crate) fn resolve_path_segments(&self, db: &impl HirDatabase, path: &Path) -> PathResult {
         if let Some(name) = path.as_ident() {
-            self.resolve_name(db, name)
+            PathResult::from_resolution(self.resolve_name(db, name))
         } else if path.is_self() {
-            self.resolve_name(db, &Name::self_param())
+            PathResult::from_resolution(self.resolve_name(db, &Name::self_param()))
         } else {
             let (item_map, module) = match self.module() {
                 Some(m) => m,
-                _ => return PerNs::none(),
+                _ => return PathResult::empty(),
             };
-            let module_res = item_map.resolve_path(db, module, path);
-            module_res.map(Resolution::Def)
+            let (module_res, segment_index) = item_map.resolve_path(db, module, path);
+
+            let def = module_res.map(Resolution::Def);
+
+            if let Some(index) = segment_index {
+                PathResult::from_resolution_with_index(def, index)
+            } else {
+                PathResult::from_resolution(def)
+            }
         }
     }
 
+    /// Returns the fully resolved path if we were able to resolve it.
+    /// otherwise returns `PerNs::none`
+    pub fn resolve_path(&self, db: &impl HirDatabase, path: &Path) -> PerNs<Resolution> {
+        // into_fully_resolved() returns the fully resolved path or PerNs::none() otherwise
+        self.resolve_path_segments(db, path).into_fully_resolved()
+    }
+
     pub fn all_names(&self, db: &impl HirDatabase) -> FxHashMap<Name, PerNs<Resolution>> {
         let mut names = FxHashMap::default();
         for scope in self.scopes.iter().rev() {
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 1a3e1994f..ae595c16d 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -37,7 +37,7 @@ use crate::{
     FnSignature, ModuleDef, AdtDef,
     HirDatabase,
     type_ref::{TypeRef, Mutability},
-    name::KnownName,
+    name::{KnownName},
     expr::{Body, Expr, BindingAnnotation, Literal, ExprId, Pat, PatId, UnaryOp, BinaryOp, Statement, FieldPat, self},
     generics::GenericParams,
     path::{ GenericArgs, GenericArg},
@@ -1166,15 +1166,55 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
     }
 
     fn infer_path_expr(&mut self, resolver: &Resolver, path: &Path) -> Option<Ty> {
-        let resolved = resolver.resolve_path(self.db, &path).take_values()?;
+        let resolved = resolver.resolve_path_segments(self.db, &path);
+
+        let (def, remaining_index) = resolved.into_inner();
+
+        // if the remaining_index is None, we expect the path
+        // to be fully resolved, in this case we continue with
+        // the default by attempting to `take_values´ from the resolution.
+        // Otherwise the path was partially resolved, which means
+        // we might have resolved into a type for which
+        // we may find some associated item starting at the
+        // path.segment pointed to by `remaining_index´
+        let resolved =
+            if remaining_index.is_none() { def.take_values()? } else { def.take_types()? };
+
         match resolved {
             Resolution::Def(def) => {
                 let typable: Option<TypableDef> = def.into();
                 let typable = typable?;
-                let substs = Ty::substs_from_path(self.db, &self.resolver, path, typable);
-                let ty = self.db.type_for_def(typable, Namespace::Values).apply_substs(substs);
-                let ty = self.insert_type_vars(ty);
-                Some(ty)
+
+                if let Some(remaining_index) = remaining_index {
+                    let ty = self.db.type_for_def(typable, Namespace::Types);
+                    // TODO: Keep resolving the segments
+                    // if we have more segments to process
+                    let segment = &path.segments[remaining_index];
+
+                    // Attempt to find an impl_item for the type which has a name matching
+                    // the current segment
+                    let ty = ty.iterate_impl_items(self.db, |item| match item {
+                        crate::ImplItem::Method(func) => {
+                            let sig = func.signature(self.db);
+                            if segment.name == *sig.name() {
+                                return Some(type_for_fn(self.db, func));
+                            }
+                            None
+                        }
+
+                        // TODO: Resolve associated const
+                        crate::ImplItem::Const(_) => None,
+
+                        // TODO: Resolve associated types
+                        crate::ImplItem::Type(_) => None,
+                    });
+                    ty
+                } else {
+                    let substs = Ty::substs_from_path(self.db, &self.resolver, path, typable);
+                    let ty = self.db.type_for_def(typable, Namespace::Values).apply_substs(substs);
+                    let ty = self.insert_type_vars(ty);
+                    Some(ty)
+                }
             }
             Resolution::LocalBinding(pat) => {
                 let ty = self.type_of_pat.get(pat)?;
diff --git a/crates/ra_hir/src/ty/snapshots/tests__infer_associated_const.snap b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_const.snap
new file mode 100644
index 000000000..131d1fa16
--- /dev/null
+++ b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_const.snap
@@ -0,0 +1,14 @@
+---
+created: "2019-02-21T21:51:46.497925200Z"
+creator: [email protected]
+source: crates/ra_hir/src/ty/tests.rs
+expression: "&result"
+---
+[227; 305) '{     ...:ID; }': ()
+[237; 238) 'x': [unknown]
+[241; 252) 'Struct::FOO': [unknown]
+[262; 263) 'y': [unknown]
+[266; 275) 'Enum::BAR': [unknown]
+[285; 286) 'z': [unknown]
+[289; 302) 'TraitTest::ID': [unknown]
+
diff --git a/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_enum.snap b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_enum.snap
new file mode 100644
index 000000000..8f27af88c
--- /dev/null
+++ b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_enum.snap
@@ -0,0 +1,20 @@
+---
+created: "2019-02-20T11:04:56.553382800Z"
+creator: [email protected]
+source: crates/ra_hir/src/ty/tests.rs
+expression: "&result"
+---
+[48; 68) '{     ...     }': A
+[58; 62) 'A::B': A
+[89; 109) '{     ...     }': A
+[99; 103) 'A::C': A
+[122; 179) '{     ...  c; }': ()
+[132; 133) 'a': A
+[136; 140) 'A::b': fn b() -> A
+[136; 142) 'A::b()': A
+[148; 149) 'a': A
+[159; 160) 'c': A
+[163; 167) 'A::c': fn c() -> A
+[163; 169) 'A::c()': A
+[175; 176) 'c': A
+
diff --git a/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_generics.snap b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_generics.snap
new file mode 100644
index 000000000..fe5d6590e
--- /dev/null
+++ b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_generics.snap
@@ -0,0 +1,16 @@
+---
+created: "2019-02-21T10:25:18.568887300Z"
+creator: [email protected]
+source: crates/ra_hir/src/ty/tests.rs
+expression: "&result"
+---
+[64; 67) 'val': T
+[82; 109) '{     ...     }': Gen<T>
+[92; 103) 'Gen { val }': Gen<T>
+[98; 101) 'val': T
+[123; 155) '{     ...32); }': ()
+[133; 134) 'a': Gen<[unknown]>
+[137; 146) 'Gen::make': fn make<[unknown]>(T) -> Gen<T>
+[137; 152) 'Gen::make(0u32)': Gen<[unknown]>
+[147; 151) '0u32': u32
+
diff --git a/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_struct.snap b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_struct.snap
new file mode 100644
index 000000000..29ca9b0ea
--- /dev/null
+++ b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_struct.snap
@@ -0,0 +1,16 @@
+---
+created: "2019-02-20T11:04:56.553382800Z"
+creator: [email protected]
+source: crates/ra_hir/src/ty/tests.rs
+expression: "&result"
+---
+[50; 76) '{     ...     }': A
+[60; 70) 'A { x: 0 }': A
+[67; 68) '0': u32
+[89; 123) '{     ...a.x; }': ()
+[99; 100) 'a': A
+[103; 109) 'A::new': fn new() -> A
+[103; 111) 'A::new()': A
+[117; 118) 'a': A
+[117; 120) 'a.x': u32
+
diff --git a/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_with_modules.snap b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_with_modules.snap
new file mode 100644
index 000000000..6584bef39
--- /dev/null
+++ b/crates/ra_hir/src/ty/snapshots/tests__infer_associated_method_with_modules.snap
@@ -0,0 +1,23 @@
+---
+created: "2019-02-21T08:55:53.926725400Z"
+creator: [email protected]
+source: crates/ra_hir/src/ty/tests.rs
+expression: "&result"
+---
+[56; 64) '{ A {} }': A
+[58; 62) 'A {}': A
+[126; 132) '{ 99 }': u32
+[128; 130) '99': u32
+[202; 210) '{ C {} }': C
+[204; 208) 'C {}': C
+[241; 325) '{     ...g(); }': ()
+[251; 252) 'x': A
+[255; 266) 'a::A::thing': fn thing() -> A
+[255; 268) 'a::A::thing()': A
+[278; 279) 'y': u32
+[282; 293) 'b::B::thing': fn thing() -> u32
+[282; 295) 'b::B::thing()': u32
+[305; 306) 'z': C
+[309; 320) 'c::C::thing': fn thing() -> C
+[309; 322) 'c::C::thing()': C
+
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 3affcb4fe..f04e9109c 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -608,6 +608,140 @@ fn test() -> i128 {
 }
 
 #[test]
+fn infer_associated_const() {
+    check_inference(
+        "infer_associated_const",
+        r#"
+struct Struct;
+
+impl Struct {
+    const FOO: u32 = 1;
+}
+
+enum Enum;
+
+impl Enum {
+    const BAR: u32 = 2;
+}
+
+trait Trait {
+    const ID: u32;
+}
+
+struct TraitTest;
+
+impl Trait for TraitTest {
+    const ID: u32 = 5;
+}
+
+fn test() {
+    let x = Struct::FOO;
+    let y = Enum::BAR;
+    let z = TraitTest::ID;
+}
+"#,
+    );
+}
+
+#[test]
+fn infer_associated_method_struct() {
+    check_inference(
+        "infer_associated_method_struct",
+        r#"
+struct A { x: u32 };
+
+impl A {
+    fn new() -> A {
+        A { x: 0 }
+    }
+}
+fn test() {
+    let a = A::new();
+    a.x;
+}
+"#,
+    );
+}
+
+#[test]
+fn infer_associated_method_enum() {
+    check_inference(
+        "infer_associated_method_enum",
+        r#"
+enum A { B, C };
+
+impl A {
+    pub fn b() -> A {
+        A::B
+    }
+    pub fn c() -> A {
+        A::C
+    }
+}
+fn test() {
+    let a = A::b();
+    a;
+    let c = A::c();
+    c;
+}
+"#,
+    );
+}
+
+#[test]
+fn infer_associated_method_with_modules() {
+    check_inference(
+        "infer_associated_method_with_modules",
+        r#"
+mod a {
+    struct A;
+    impl A { pub fn thing() -> A { A {} }}
+}
+
+mod b {
+    struct B;
+    impl B { pub fn thing() -> u32 { 99 }}
+
+    mod c {
+        struct C;
+        impl C { pub fn thing() -> C { C {} }}
+    }
+}
+use b::c;
+
+fn test() {
+    let x = a::A::thing();
+    let y = b::B::thing();
+    let z = c::C::thing();
+}
+"#,
+    );
+}
+
+#[test]
+#[ignore] // FIXME: After https://github.com/rust-analyzer/rust-analyzer/pull/866 is merged
+fn infer_associated_method_generics() {
+    check_inference(
+        "infer_associated_method_generics",
+        r#"
+struct Gen<T> {
+    val: T
+}
+
+impl<T> Gen<T> {
+    pub fn make(val: T) -> Gen<T> {
+        Gen { val }
+    }
+}
+
+fn test() {
+    let a = Gen::make(0u32);
+}
+"#,
+    );
+}
+
+#[test]
 fn no_panic_on_field_of_enum() {
     check_inference(
         "no_panic_on_field_of_enum",