Canonicalize before doing method resolution

7 files changed, 165 insertions, 133 deletions

diff --git a/crates/ra_hir/src/source_binder.rs b/crates/ra_hir/src/source_binder.rs
index 2959e3eca..24350bda7 100644
--- a/crates/ra_hir/src/source_binder.rs
+++ b/crates/ra_hir/src/source_binder.rs
@@ -350,7 +350,16 @@ impl SourceAnalyzer {
         name: Option<&Name>,
         callback: impl FnMut(&Ty, Function) -> Option<T>,
     ) -> Option<T> {
-        ty.iterate_method_candidates(db, &self.resolver, name, callback)
+        // There should be no inference vars in types passed here
+        // TODO check that?
+        let canonical = crate::ty::Canonical { value: ty, num_vars: 0 };
+        crate::ty::method_resolution::iterate_method_candidates(
+            &canonical,
+            db,
+            &self.resolver,
+            name,
+            callback,
+        )
     }
 
     #[cfg(test)]
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index e7c39487d..6a79af35b 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -234,6 +234,17 @@ impl TraitRef {
     }
 }
 
+/// Basically a claim (currently not validated / checked) that the contained
+/// type / trait ref contains no inference variables; any inference variables it
+/// contained have been replaced by bound variables, and `num_vars` tells us how
+/// many there are. This is used to erase irrelevant differences between types
+/// before using them in queries.
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub(crate) struct Canonical<T> {
+    pub value: T,
+    pub num_vars: usize,
+}
+
 /// A function signature as seen by type inference: Several parameter types and
 /// one return type.
 #[derive(Clone, PartialEq, Eq, Debug)]
diff --git a/crates/ra_hir/src/ty/infer.rs b/crates/ra_hir/src/ty/infer.rs
index a6d08dbcb..41ae569f7 100644
--- a/crates/ra_hir/src/ty/infer.rs
+++ b/crates/ra_hir/src/ty/infer.rs
@@ -45,12 +45,11 @@ use crate::{
 use super::{
     Ty, TypableDef, Substs, primitive, op, ApplicationTy, TypeCtor, CallableDef, TraitRef,
     traits::{Solution, Obligation, Guidance},
+    method_resolution,
 };
 
 mod unify;
 
-pub(super) use unify::Canonical;
-
 /// The entry point of type inference.
 pub fn infer(db: &impl HirDatabase, def: DefWithBody) -> Arc<InferenceResult> {
     db.check_canceled();
@@ -878,9 +877,17 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
         generic_args: Option<&GenericArgs>,
     ) -> Ty {
         let receiver_ty = self.infer_expr(receiver, &Expectation::none());
-        let resolved = receiver_ty.clone().lookup_method(self.db, method_name, &self.resolver);
+        let mut canonicalizer = self.canonicalizer();
+        let canonical_receiver = canonicalizer.canonicalize_ty(receiver_ty.clone());
+        let resolved = method_resolution::lookup_method(
+            &canonical_receiver,
+            canonicalizer.ctx.db,
+            method_name,
+            &canonicalizer.ctx.resolver,
+        );
         let (derefed_receiver_ty, method_ty, def_generics) = match resolved {
             Some((ty, func)) => {
+                let ty = canonicalizer.decanonicalize_ty(ty);
                 self.write_method_resolution(tgt_expr, func);
                 (
                     ty,
diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs
index 5edb95c31..820a64789 100644
--- a/crates/ra_hir/src/ty/infer/unify.rs
+++ b/crates/ra_hir/src/ty/infer/unify.rs
@@ -1,6 +1,8 @@
 //! Unification and canonicalization logic.
 
-use super::{InferenceContext, Ty, TraitRef, InferTy, HirDatabase};
+use crate::db::HirDatabase;
+use crate::ty::{Ty, Canonical, TraitRef, InferTy};
+use super::InferenceContext;
 
 impl<'a, D: HirDatabase> InferenceContext<'a, D> {
     pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b, D>
@@ -13,13 +15,6 @@ impl<'a, D: HirDatabase> InferenceContext<'a, D> {
 
 // TODO improve the interface of this
 
-// TODO move further up?
-#[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub(crate) struct Canonical<T> {
-    pub value: T,
-    pub num_vars: usize,
-}
-
 pub(super) struct Canonicalizer<'a, 'b, D: HirDatabase>
 where
     'a: 'b,
@@ -68,6 +63,19 @@ where
         Canonical { value, num_vars: self.free_vars.len() }
     }
 
+    pub fn decanonicalize_ty(&self, ty: Ty) -> Ty {
+        ty.fold(&mut |ty| match ty {
+            Ty::Bound(idx) => {
+                if (idx as usize) < self.free_vars.len() {
+                    Ty::Infer(self.free_vars[idx as usize].clone())
+                } else {
+                    Ty::Bound(idx)
+                }
+            }
+            ty => ty,
+        })
+    }
+
     pub fn apply_solution(&mut self, solution: Canonical<Vec<Ty>>) {
         // the solution may contain new variables, which we need to convert to new inference vars
         let new_vars =
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index ea7da0b62..bc5033be6 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -16,7 +16,7 @@ use crate::{
     generics::HasGenericParams,
     ty::primitive::{UncertainIntTy, UncertainFloatTy}
 };
-use super::{TraitRef, infer::Canonical, Substs};
+use super::{TraitRef, Canonical};
 
 /// This is used as a key for indexing impls.
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
@@ -130,132 +130,123 @@ fn def_crate(db: &impl HirDatabase, cur_crate: Crate, ty: &Ty) -> Option<Crate>
     }
 }
 
-impl Ty {
-    /// Look up the method with the given name, returning the actual autoderefed
-    /// receiver type (but without autoref applied yet).
-    pub(crate) fn lookup_method(
-        self,
-        db: &impl HirDatabase,
-        name: &Name,
-        resolver: &Resolver,
-    ) -> Option<(Ty, Function)> {
-        self.iterate_method_candidates(db, resolver, Some(name), |ty, f| Some((ty.clone(), f)))
-    }
+/// Look up the method with the given name, returning the actual autoderefed
+/// receiver type (but without autoref applied yet).
+pub(crate) fn lookup_method(
+    ty: &Canonical<Ty>,
+    db: &impl HirDatabase,
+    name: &Name,
+    resolver: &Resolver,
+) -> Option<(Ty, Function)> {
+    iterate_method_candidates(ty, db, resolver, Some(name), |ty, f| Some((ty.clone(), f)))
+}
 
-    // 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,
-        resolver: &Resolver,
-        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.
+// 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>(
+    ty: &Canonical<Ty>,
+    db: &impl HirDatabase,
+    resolver: &Resolver,
+    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).
+    // 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 = resolver.krate()?;
-        for derefed_ty in self.autoderef(db) {
-            if let Some(result) =
-                derefed_ty.iterate_inherent_methods(db, name, krate, &mut callback)
-            {
-                return Some(result);
-            }
-            if let Some(result) =
-                derefed_ty.iterate_trait_method_candidates(db, resolver, name, &mut callback)
-            {
-                return Some(result);
-            }
+    let krate = resolver.krate()?;
+    for derefed_ty in ty.value.clone().autoderef(db) {
+        let derefed_ty = Canonical { value: derefed_ty, num_vars: ty.num_vars };
+        if let Some(result) = iterate_inherent_methods(&derefed_ty, db, name, krate, &mut callback)
+        {
+            return Some(result);
+        }
+        if let Some(result) =
+            iterate_trait_method_candidates(&derefed_ty, db, resolver, name, &mut callback)
+        {
+            return Some(result);
         }
-        None
     }
+    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> {
-        let krate = resolver.krate()?;
-        '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 name.map_or(true, |name| sig.name() == name) && sig.has_self_param() {
-                            if !known_implemented {
-                                // TODO the self type may contain type
-                                // variables, so we need to do proper
-                                // canonicalization here
-                                let trait_ref = TraitRef {
-                                    trait_: t,
-                                    substs: fresh_substs_for_trait(db, t, self.clone()),
-                                };
-                                let canonical = Canonical {
-                                    num_vars: trait_ref.substs.len(),
-                                    value: trait_ref,
-                                };
-                                // FIXME cache this implements check (without solution) in a query?
-                                if super::traits::implements(db, krate, canonical).is_none() {
-                                    continue 'traits;
-                                }
-                            }
-                            known_implemented = true;
-                            if let Some(result) = callback(self, m) {
-                                return Some(result);
+fn iterate_trait_method_candidates<T>(
+    ty: &Canonical<Ty>,
+    db: &impl HirDatabase,
+    resolver: &Resolver,
+    name: Option<&Name>,
+    mut callback: impl FnMut(&Ty, Function) -> Option<T>,
+) -> Option<T> {
+    let krate = resolver.krate()?;
+    '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 name.map_or(true, |name| sig.name() == name) && sig.has_self_param() {
+                        if !known_implemented {
+                            let trait_ref = canonical_trait_ref(db, t, ty.clone());
+                            // FIXME cache this implements check (without solution) in a query?
+                            if super::traits::implements(db, krate, trait_ref).is_none() {
+                                continue 'traits;
                             }
                         }
+                        known_implemented = true;
+                        // TODO the self type is now canonicalized...
+                        if let Some(result) = callback(&ty.value, m) {
+                            return Some(result);
+                        }
                     }
-                    _ => {}
                 }
+                _ => {}
             }
         }
-        None
     }
+    None
+}
 
-    fn iterate_inherent_methods<T>(
-        &self,
-        db: &impl HirDatabase,
-        name: Option<&Name>,
-        krate: Crate,
-        mut callback: impl FnMut(&Ty, Function) -> Option<T>,
-    ) -> Option<T> {
-        let krate = match def_crate(db, krate, self) {
-            Some(krate) => krate,
-            None => return None,
-        };
-        let impls = db.impls_in_crate(krate);
+fn iterate_inherent_methods<T>(
+    ty: &Canonical<Ty>,
+    db: &impl HirDatabase,
+    name: Option<&Name>,
+    krate: Crate,
+    mut callback: impl FnMut(&Ty, Function) -> Option<T>,
+) -> Option<T> {
+    let krate = match def_crate(db, krate, &ty.value) {
+        Some(krate) => krate,
+        None => return None,
+    };
+    let impls = db.impls_in_crate(krate);
 
-        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);
-                            }
+    for impl_block in impls.lookup_impl_blocks(&ty.value) {
+        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(&ty.value, f) {
+                            return Some(result);
                         }
                     }
-                    _ => {}
                 }
+                _ => {}
             }
         }
-        None
     }
+    None
+}
 
+impl Ty {
     // 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_impl_items<T>(
@@ -280,17 +271,25 @@ impl Ty {
 
 /// This creates Substs for a trait with the given Self type and type variables
 /// for all other parameters, to query Chalk with it.
-fn fresh_substs_for_trait(db: &impl HirDatabase, tr: Trait, self_ty: Ty) -> Substs {
+fn canonical_trait_ref(
+    db: &impl HirDatabase,
+    trait_: Trait,
+    self_ty: Canonical<Ty>,
+) -> Canonical<TraitRef> {
     let mut substs = Vec::new();
-    let generics = tr.generic_params(db);
-    substs.push(self_ty);
+    let generics = trait_.generic_params(db);
+    let num_vars = self_ty.num_vars;
+    substs.push(self_ty.value);
     substs.extend(
         generics
             .params_including_parent()
             .into_iter()
             .skip(1)
             .enumerate()
-            .map(|(i, _p)| Ty::Bound(i as u32)),
+            .map(|(i, _p)| Ty::Bound((i + num_vars) as u32)),
     );
-    substs.into()
+    Canonical {
+        num_vars: substs.len() - 1 + self_ty.num_vars,
+        value: TraitRef { trait_, substs: substs.into() },
+    }
 }
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs
index ac31ca2f6..c707110ad 100644
--- a/crates/ra_hir/src/ty/traits.rs
+++ b/crates/ra_hir/src/ty/traits.rs
@@ -4,7 +4,7 @@ use std::sync::{Arc, Mutex};
 use chalk_ir::cast::Cast;
 
 use crate::{Crate, Trait, db::HirDatabase, ImplBlock};
-use super::{TraitRef, Ty, infer::Canonical};
+use super::{TraitRef, Ty, Canonical};
 
 use self::chalk::{ToChalk, from_chalk};
 
@@ -86,10 +86,7 @@ pub(crate) fn implements(
     solution.map(|solution| solution_from_chalk(db, solution))
 }
 
-fn solution_from_chalk(
-    db: &impl HirDatabase,
-    solution: chalk_solve::Solution,
-) -> Solution {
+fn solution_from_chalk(db: &impl HirDatabase, solution: chalk_solve::Solution) -> Solution {
     let convert_subst = |subst: chalk_ir::Canonical<chalk_ir::Substitution>| {
         let value = subst
             .value
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
index 36cc52704..18f301789 100644
--- a/crates/ra_hir/src/ty/traits/chalk.rs
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -32,8 +32,7 @@ impl ToChalk for Ty {
         match self {
             Ty::Apply(apply_ty) => chalk_ir::Ty::Apply(apply_ty.to_chalk(db)),
             Ty::Param { idx, .. } => {
-                PlaceholderIndex { ui: UniverseIndex::ROOT, idx: idx as usize }
-                    .to_ty()
+                PlaceholderIndex { ui: UniverseIndex::ROOT, idx: idx as usize }.to_ty()
             }
             Ty::Bound(idx) => chalk_ir::Ty::BoundVar(idx as usize),
             Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"),
@@ -74,9 +73,7 @@ impl ToChalk for ApplicationTy {
 
     fn from_chalk(db: &impl HirDatabase, apply_ty: chalk_ir::ApplicationTy) -> ApplicationTy {
         let ctor = match apply_ty.name {
-            TypeName::TypeKindId(TypeKindId::StructId(struct_id)) => {
-                from_chalk(db, struct_id)
-            }
+            TypeName::TypeKindId(TypeKindId::StructId(struct_id)) => from_chalk(db, struct_id),
             TypeName::TypeKindId(_) => unimplemented!(),
             TypeName::Placeholder(_) => unimplemented!(),
             TypeName::AssociatedType(_) => unimplemented!(),
@@ -267,7 +264,11 @@ where
             .map(|impl_block| impl_block.to_chalk(self.db))
             .collect()
     }
-    fn impl_provided_for(&self, auto_trait_id: chalk_ir::TraitId, struct_id: chalk_ir::StructId) -> bool {
+    fn impl_provided_for(
+        &self,
+        auto_trait_id: chalk_ir::TraitId,
+        struct_id: chalk_ir::StructId,
+    ) -> bool {
         eprintln!("impl_provided_for {:?}, {:?}", auto_trait_id, struct_id);
         false // FIXME
     }