1 files changed, 193 insertions, 45 deletions

diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index ee1936b0e..888dc3116 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -6,20 +6,21 @@ use std::sync::Arc;
 
 use arrayvec::ArrayVec;
 use hir_def::{
-    lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutability, AssocItemId, AstItemDef,
-    FunctionId, HasModule, ImplId, TraitId,
+    lang_item::LangItemTarget, resolver::Resolver, type_ref::Mutability, AssocContainerId,
+    AssocItemId, FunctionId, HasModule, ImplId, Lookup, TraitId,
 };
 use hir_expand::name::Name;
 use ra_db::CrateId;
 use ra_prof::profile;
 use rustc_hash::FxHashMap;
 
+use super::Substs;
 use crate::{
     autoderef,
     db::HirDatabase,
     primitive::{FloatBitness, Uncertain},
     utils::all_super_traits,
-    Canonical, ImplTy, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor,
+    Canonical, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor, TypeWalk,
 };
 
 /// This is used as a key for indexing impls.
@@ -57,12 +58,13 @@ impl CrateImplBlocks {
 
         let crate_def_map = db.crate_def_map(krate);
         for (_module_id, module_data) in crate_def_map.modules.iter() {
-            for &impl_id in module_data.impls.iter() {
-                match db.impl_ty(impl_id) {
-                    ImplTy::TraitRef(tr) => {
+            for impl_id in module_data.scope.impls() {
+                match db.impl_trait(impl_id) {
+                    Some(tr) => {
                         res.impls_by_trait.entry(tr.trait_).or_default().push(impl_id);
                     }
-                    ImplTy::Inherent(self_ty) => {
+                    None => {
+                        let self_ty = db.impl_self_ty(impl_id);
                         if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty) {
                             res.impls.entry(self_ty_fp).or_default().push(impl_id);
                         }
@@ -132,7 +134,7 @@ impl Ty {
                 LangItemTarget::ImplBlockId(it) => Some(it),
                 _ => None,
             })
-            .map(|it| it.module(db).krate)
+            .map(|it| it.lookup(db).container.module(db).krate)
             .collect();
         Some(res)
     }
@@ -175,7 +177,6 @@ pub fn iterate_method_candidates<T>(
     mode: LookupMode,
     mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
 ) -> Option<T> {
-    let krate = resolver.krate()?;
     match mode {
         LookupMode::MethodCall => {
             // For method calls, rust first does any number of autoderef, and then one
@@ -188,57 +189,159 @@ pub fn iterate_method_candidates<T>(
             // rustc does an autoderef and then autoref again).
             let environment = TraitEnvironment::lower(db, resolver);
             let ty = InEnvironment { value: ty.clone(), environment };
-            for derefed_ty in autoderef::autoderef(db, resolver.krate(), ty) {
-                if let Some(result) =
-                    iterate_inherent_methods(&derefed_ty, db, name, mode, krate, &mut callback)
-                {
-                    return Some(result);
-                }
-                if let Some(result) = iterate_trait_method_candidates(
-                    &derefed_ty,
+            let krate = resolver.krate()?;
+
+            // We have to be careful about the order we're looking at candidates
+            // in here. Consider the case where we're resolving `x.clone()`
+            // where `x: &Vec<_>`. This resolves to the clone method with self
+            // type `Vec<_>`, *not* `&_`. I.e. we need to consider methods where
+            // the receiver type exactly matches before cases where we have to
+            // do autoref. But in the autoderef steps, the `&_` self type comes
+            // up *before* the `Vec<_>` self type.
+            //
+            // On the other hand, we don't want to just pick any by-value method
+            // before any by-autoref method; it's just that we need to consider
+            // the methods by autoderef order of *receiver types*, not *self
+            // types*.
+
+            let deref_chain: Vec<_> = autoderef::autoderef(db, Some(krate), ty.clone()).collect();
+            for i in 0..deref_chain.len() {
+                if let Some(result) = iterate_method_candidates_with_autoref(
+                    &deref_chain[i..],
                     db,
                     resolver,
                     name,
-                    mode,
                     &mut callback,
                 ) {
                     return Some(result);
                 }
             }
+            None
         }
         LookupMode::Path => {
             // No autoderef for path lookups
-            if let Some(result) =
-                iterate_inherent_methods(&ty, db, name, mode, krate.into(), &mut callback)
-            {
-                return Some(result);
-            }
-            if let Some(result) =
-                iterate_trait_method_candidates(&ty, db, resolver, name, mode, &mut callback)
-            {
-                return Some(result);
-            }
+            iterate_method_candidates_for_self_ty(&ty, db, resolver, name, &mut callback)
+        }
+    }
+}
+
+fn iterate_method_candidates_with_autoref<T>(
+    deref_chain: &[Canonical<Ty>],
+    db: &impl HirDatabase,
+    resolver: &Resolver,
+    name: Option<&Name>,
+    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
+) -> Option<T> {
+    if let Some(result) = iterate_method_candidates_by_receiver(
+        &deref_chain[0],
+        &deref_chain[1..],
+        db,
+        resolver,
+        name,
+        &mut callback,
+    ) {
+        return Some(result);
+    }
+    let refed = Canonical {
+        num_vars: deref_chain[0].num_vars,
+        value: Ty::apply_one(TypeCtor::Ref(Mutability::Shared), deref_chain[0].value.clone()),
+    };
+    if let Some(result) = iterate_method_candidates_by_receiver(
+        &refed,
+        deref_chain,
+        db,
+        resolver,
+        name,
+        &mut callback,
+    ) {
+        return Some(result);
+    }
+    let ref_muted = Canonical {
+        num_vars: deref_chain[0].num_vars,
+        value: Ty::apply_one(TypeCtor::Ref(Mutability::Mut), deref_chain[0].value.clone()),
+    };
+    if let Some(result) = iterate_method_candidates_by_receiver(
+        &ref_muted,
+        deref_chain,
+        db,
+        resolver,
+        name,
+        &mut callback,
+    ) {
+        return Some(result);
+    }
+    None
+}
+
+fn iterate_method_candidates_by_receiver<T>(
+    receiver_ty: &Canonical<Ty>,
+    rest_of_deref_chain: &[Canonical<Ty>],
+    db: &impl HirDatabase,
+    resolver: &Resolver,
+    name: Option<&Name>,
+    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
+) -> Option<T> {
+    // We're looking for methods with *receiver* type receiver_ty. These could
+    // be found in any of the derefs of receiver_ty, so we have to go through
+    // that.
+    let krate = resolver.krate()?;
+    for self_ty in std::iter::once(receiver_ty).chain(rest_of_deref_chain) {
+        if let Some(result) =
+            iterate_inherent_methods(self_ty, db, name, Some(receiver_ty), krate, &mut callback)
+        {
+            return Some(result);
+        }
+    }
+    for self_ty in std::iter::once(receiver_ty).chain(rest_of_deref_chain) {
+        if let Some(result) = iterate_trait_method_candidates(
+            self_ty,
+            db,
+            resolver,
+            name,
+            Some(receiver_ty),
+            &mut callback,
+        ) {
+            return Some(result);
         }
     }
     None
 }
 
+fn iterate_method_candidates_for_self_ty<T>(
+    self_ty: &Canonical<Ty>,
+    db: &impl HirDatabase,
+    resolver: &Resolver,
+    name: Option<&Name>,
+    mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
+) -> Option<T> {
+    let krate = resolver.krate()?;
+    if let Some(result) = iterate_inherent_methods(self_ty, db, name, None, krate, &mut callback) {
+        return Some(result);
+    }
+    if let Some(result) =
+        iterate_trait_method_candidates(self_ty, db, resolver, name, None, &mut callback)
+    {
+        return Some(result);
+    }
+    None
+}
+
 fn iterate_trait_method_candidates<T>(
-    ty: &Canonical<Ty>,
+    self_ty: &Canonical<Ty>,
     db: &impl HirDatabase,
     resolver: &Resolver,
     name: Option<&Name>,
-    mode: LookupMode,
+    receiver_ty: Option<&Canonical<Ty>>,
     mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
 ) -> Option<T> {
     let krate = resolver.krate()?;
     // FIXME: maybe put the trait_env behind a query (need to figure out good input parameters for that)
     let env = TraitEnvironment::lower(db, resolver);
     // if ty is `impl Trait` or `dyn Trait`, the trait doesn't need to be in scope
-    let inherent_trait = ty.value.inherent_trait().into_iter();
+    let inherent_trait = self_ty.value.inherent_trait().into_iter();
     // if we have `T: Trait` in the param env, the trait doesn't need to be in scope
     let traits_from_env = env
-        .trait_predicates_for_self_ty(&ty.value)
+        .trait_predicates_for_self_ty(&self_ty.value)
         .map(|tr| tr.trait_)
         .flat_map(|t| all_super_traits(db, t));
     let traits =
@@ -251,17 +354,17 @@ fn iterate_trait_method_candidates<T>(
         // iteration
         let mut known_implemented = false;
         for (_name, item) in data.items.iter() {
-            if !is_valid_candidate(db, name, mode, (*item).into()) {
+            if !is_valid_candidate(db, name, receiver_ty, (*item).into(), self_ty) {
                 continue;
             }
             if !known_implemented {
-                let goal = generic_implements_goal(db, env.clone(), t, ty.clone());
+                let goal = generic_implements_goal(db, env.clone(), t, self_ty.clone());
                 if db.trait_solve(krate.into(), goal).is_none() {
                     continue 'traits;
                 }
             }
             known_implemented = true;
-            if let Some(result) = callback(&ty.value, (*item).into()) {
+            if let Some(result) = callback(&self_ty.value, (*item).into()) {
                 return Some(result);
             }
         }
@@ -270,22 +373,22 @@ fn iterate_trait_method_candidates<T>(
 }
 
 fn iterate_inherent_methods<T>(
-    ty: &Canonical<Ty>,
+    self_ty: &Canonical<Ty>,
     db: &impl HirDatabase,
     name: Option<&Name>,
-    mode: LookupMode,
+    receiver_ty: Option<&Canonical<Ty>>,
     krate: CrateId,
     mut callback: impl FnMut(&Ty, AssocItemId) -> Option<T>,
 ) -> Option<T> {
-    for krate in ty.value.def_crates(db, krate)? {
+    for krate in self_ty.value.def_crates(db, krate)? {
         let impls = db.impls_in_crate(krate);
 
-        for impl_block in impls.lookup_impl_blocks(&ty.value) {
+        for impl_block in impls.lookup_impl_blocks(&self_ty.value) {
             for &item in db.impl_data(impl_block).items.iter() {
-                if !is_valid_candidate(db, name, mode, item) {
+                if !is_valid_candidate(db, name, receiver_ty, item, self_ty) {
                     continue;
                 }
-                if let Some(result) = callback(&ty.value, item.into()) {
+                if let Some(result) = callback(&self_ty.value, item) {
                     return Some(result);
                 }
             }
@@ -297,23 +400,68 @@ fn iterate_inherent_methods<T>(
 fn is_valid_candidate(
     db: &impl HirDatabase,
     name: Option<&Name>,
-    mode: LookupMode,
+    receiver_ty: Option<&Canonical<Ty>>,
     item: AssocItemId,
+    self_ty: &Canonical<Ty>,
 ) -> bool {
     match item {
         AssocItemId::FunctionId(m) => {
             let data = db.function_data(m);
-            name.map_or(true, |name| &data.name == name)
-                && (data.has_self_param || mode == LookupMode::Path)
+            if let Some(name) = name {
+                if &data.name != name {
+                    return false;
+                }
+            }
+            if let Some(receiver_ty) = receiver_ty {
+                if !data.has_self_param {
+                    return false;
+                }
+                let transformed_receiver_ty = match transform_receiver_ty(db, m, self_ty) {
+                    Some(ty) => ty,
+                    None => return false,
+                };
+                if transformed_receiver_ty != receiver_ty.value {
+                    return false;
+                }
+            }
+            true
         }
         AssocItemId::ConstId(c) => {
             let data = db.const_data(c);
-            name.map_or(true, |name| data.name.as_ref() == Some(name)) && (mode == LookupMode::Path)
+            name.map_or(true, |name| data.name.as_ref() == Some(name)) && receiver_ty.is_none()
         }
         _ => false,
     }
 }
 
+pub(crate) fn inherent_impl_substs(
+    db: &impl HirDatabase,
+    impl_id: ImplId,
+    self_ty: &Canonical<Ty>,
+) -> Option<Substs> {
+    let vars = Substs::build_for_def(db, impl_id).fill_with_bound_vars(0).build();
+    let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars);
+    let self_ty_with_vars = Canonical { num_vars: vars.len(), value: self_ty_with_vars };
+    super::infer::unify(&self_ty_with_vars, self_ty)
+}
+
+fn transform_receiver_ty(
+    db: &impl HirDatabase,
+    function_id: FunctionId,
+    self_ty: &Canonical<Ty>,
+) -> Option<Ty> {
+    let substs = match function_id.lookup(db).container {
+        AssocContainerId::TraitId(_) => Substs::build_for_def(db, function_id)
+            .push(self_ty.value.clone())
+            .fill_with_unknown()
+            .build(),
+        AssocContainerId::ImplId(impl_id) => inherent_impl_substs(db, impl_id, &self_ty)?,
+        AssocContainerId::ContainerId(_) => unreachable!(),
+    };
+    let sig = db.callable_item_signature(function_id.into());
+    Some(sig.params()[0].clone().subst(&substs))
+}
+
 pub fn implements_trait(
     ty: &Canonical<Ty>,
     db: &impl HirDatabase,