From 0ad7317b24dc90c3787482f9ec563e7830d499fc Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Wed, 1 May 2019 17:57:56 +0200 Subject: Canonicalize before doing method resolution --- crates/ra_hir/src/source_binder.rs | 11 +- crates/ra_hir/src/ty.rs | 11 ++ crates/ra_hir/src/ty/infer.rs | 13 +- crates/ra_hir/src/ty/infer/unify.rs | 24 ++-- crates/ra_hir/src/ty/method_resolution.rs | 219 +++++++++++++++--------------- crates/ra_hir/src/ty/traits.rs | 7 +- crates/ra_hir/src/ty/traits/chalk.rs | 13 +- 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, ) -> Option { - 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 { + 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 { 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 { - 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>) { // 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 } } -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, + 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( - self, - db: &impl HirDatabase, - resolver: &Resolver, - name: Option<&Name>, - mut callback: impl FnMut(&Ty, Function) -> Option, - ) -> Option { - // 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( + ty: &Canonical, + db: &impl HirDatabase, + resolver: &Resolver, + name: Option<&Name>, + mut callback: impl FnMut(&Ty, Function) -> Option, +) -> Option { + // 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( - &self, - db: &impl HirDatabase, - resolver: &Resolver, - name: Option<&Name>, - mut callback: impl FnMut(&Ty, Function) -> Option, - ) -> Option { - 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( + ty: &Canonical, + db: &impl HirDatabase, + resolver: &Resolver, + name: Option<&Name>, + mut callback: impl FnMut(&Ty, Function) -> Option, +) -> Option { + 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( - &self, - db: &impl HirDatabase, - name: Option<&Name>, - krate: Crate, - mut callback: impl FnMut(&Ty, Function) -> Option, - ) -> Option { - 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( + ty: &Canonical, + db: &impl HirDatabase, + name: Option<&Name>, + krate: Crate, + mut callback: impl FnMut(&Ty, Function) -> Option, +) -> Option { + 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( @@ -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, +) -> Canonical { 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| { 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 } -- cgit v1.2.3