From 07ba986db7b9f7c275bc2b6a32487e0aa8b70864 Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Wed, 1 Jul 2020 15:19:36 +0200 Subject: Don't recursively call `impls_from_deps` It creates a big map and duplicates lots of impls that are then left lying around --- crates/ra_hir_ty/src/method_resolution.rs | 13 ++----------- 1 file changed, 2 insertions(+), 11 deletions(-) (limited to 'crates/ra_hir_ty/src/method_resolution.rs') diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs index c19519cf1..201604e1d 100644 --- a/crates/ra_hir_ty/src/method_resolution.rs +++ b/crates/ra_hir_ty/src/method_resolution.rs @@ -72,13 +72,8 @@ impl CrateImplDefs { impls_by_trait: FxHashMap::default(), }; - // For each dependency, calculate `impls_from_deps` recursively, then add its own - // `impls_in_crate`. - // As we might visit crates multiple times, `merge` has to deduplicate impls to avoid - // wasting memory. - for dep in &crate_graph[krate].dependencies { - res.merge(&db.impls_from_deps(dep.crate_id)); - res.merge(&db.impls_in_crate(dep.crate_id)); + for krate in crate_graph.transitive_deps(krate) { + res.merge(&db.impls_in_crate(krate)); } Arc::new(res) @@ -114,8 +109,6 @@ impl CrateImplDefs { for (fp, impls) in &other.inherent_impls { let vec = self.inherent_impls.entry(*fp).or_default(); vec.extend(impls); - vec.sort(); - vec.dedup(); } for (trait_, other_map) in &other.impls_by_trait { @@ -123,8 +116,6 @@ impl CrateImplDefs { for (fp, impls) in other_map { let vec = map.entry(*fp).or_default(); vec.extend(impls); - vec.sort(); - vec.dedup(); } } } -- cgit v1.2.3 From 6bde542a39fe63298a31b838e59705797ed8a2cf Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Wed, 1 Jul 2020 17:15:20 +0200 Subject: Split `CrateImplDefs` in inherent and trait impls This makes the intention of inherent vs. trait impls somewhat more clear and also fixes (?) an issue where trait impls with an unresolved trait were added as inherent impls instead (hence the test changes). --- crates/ra_hir_ty/src/method_resolution.rs | 192 +++++++++++++++--------------- 1 file changed, 98 insertions(+), 94 deletions(-) (limited to 'crates/ra_hir_ty/src/method_resolution.rs') diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs index 201604e1d..5dbabd12b 100644 --- a/crates/ra_hir_ty/src/method_resolution.rs +++ b/crates/ra_hir_ty/src/method_resolution.rs @@ -38,81 +38,55 @@ impl TyFingerprint { } } -/// A queryable and mergeable collection of impls. -#[derive(Debug, PartialEq, Eq)] -pub struct CrateImplDefs { - inherent_impls: FxHashMap>, - impls_by_trait: FxHashMap, Vec>>, +/// Trait impls defined or available in some crate. +#[derive(Debug, Eq, PartialEq)] +pub struct TraitImpls { + // If the `Option` is `None`, the impl may apply to any self type. + map: FxHashMap, Vec>>, } -impl CrateImplDefs { - pub(crate) fn impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc { - let _p = profile("impls_in_crate_query"); - let mut res = CrateImplDefs { - inherent_impls: FxHashMap::default(), - impls_by_trait: FxHashMap::default(), - }; - res.fill(db, krate); +impl TraitImpls { + pub(crate) fn trait_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc { + let _p = profile("trait_impls_in_crate_query"); + let mut impls = Self { map: FxHashMap::default() }; - Arc::new(res) + 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.scope.impls() { + let target_trait = match db.impl_trait(impl_id) { + Some(tr) => tr.value.trait_, + None => continue, + }; + let self_ty = db.impl_self_ty(impl_id); + let self_ty_fp = TyFingerprint::for_impl(&self_ty.value); + impls + .map + .entry(target_trait) + .or_default() + .entry(self_ty_fp) + .or_default() + .push(impl_id); + } + } + + Arc::new(impls) } - /// Collects all impls from transitive dependencies of `krate` that may be used by `krate`. - /// - /// The full set of impls that can be used by `krate` is the returned map plus all the impls - /// from `krate` itself. - pub(crate) fn impls_from_deps_query( - db: &dyn HirDatabase, - krate: CrateId, - ) -> Arc { - let _p = profile("impls_from_deps_query"); + pub(crate) fn trait_impls_in_deps_query(db: &dyn HirDatabase, krate: CrateId) -> Arc { + let _p = profile("trait_impls_in_deps_query"); let crate_graph = db.crate_graph(); - let mut res = CrateImplDefs { - inherent_impls: FxHashMap::default(), - impls_by_trait: FxHashMap::default(), - }; + let mut res = Self { map: FxHashMap::default() }; for krate in crate_graph.transitive_deps(krate) { - res.merge(&db.impls_in_crate(krate)); + res.merge(&db.trait_impls_in_crate(krate)); } Arc::new(res) } - fn fill(&mut self, db: &dyn HirDatabase, krate: CrateId) { - 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.scope.impls() { - match db.impl_trait(impl_id) { - Some(tr) => { - let self_ty = db.impl_self_ty(impl_id); - let self_ty_fp = TyFingerprint::for_impl(&self_ty.value); - self.impls_by_trait - .entry(tr.value.trait_) - .or_default() - .entry(self_ty_fp) - .or_default() - .push(impl_id); - } - None => { - let self_ty = db.impl_self_ty(impl_id); - if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty.value) { - self.inherent_impls.entry(self_ty_fp).or_default().push(impl_id); - } - } - } - } - } - } - fn merge(&mut self, other: &Self) { - for (fp, impls) in &other.inherent_impls { - let vec = self.inherent_impls.entry(*fp).or_default(); - vec.extend(impls); - } - - for (trait_, other_map) in &other.impls_by_trait { - let map = self.impls_by_trait.entry(*trait_).or_default(); + for (trait_, other_map) in &other.map { + let map = self.map.entry(*trait_).or_default(); for (fp, impls) in other_map { let vec = map.entry(*fp).or_default(); vec.extend(impls); @@ -120,45 +94,75 @@ impl CrateImplDefs { } } - pub fn lookup_impl_defs(&self, ty: &Ty) -> impl Iterator + '_ { - let fingerprint = TyFingerprint::for_impl(ty); - fingerprint.and_then(|f| self.inherent_impls.get(&f)).into_iter().flatten().copied() - } - - pub fn lookup_impl_defs_for_trait(&self, tr: TraitId) -> impl Iterator + '_ { - self.impls_by_trait - .get(&tr) + /// Queries all impls of the given trait. + pub fn for_trait(&self, trait_: TraitId) -> impl Iterator + '_ { + self.map + .get(&trait_) .into_iter() - .flat_map(|m| m.values().flat_map(|v| v.iter().copied())) + .flat_map(|map| map.values().flat_map(|v| v.iter().copied())) } - pub fn lookup_impl_defs_for_trait_and_ty( + /// Queries all impls of `trait_` that may apply to `self_ty`. + pub fn for_trait_and_self_ty( &self, - tr: TraitId, - fp: TyFingerprint, + trait_: TraitId, + self_ty: TyFingerprint, ) -> impl Iterator + '_ { - self.impls_by_trait - .get(&tr) - .and_then(|m| m.get(&Some(fp))) + self.map + .get(&trait_) .into_iter() - .flatten() - .copied() - .chain( - self.impls_by_trait - .get(&tr) - .and_then(|m| m.get(&None)) - .into_iter() - .flatten() - .copied(), - ) + .flat_map(move |map| map.get(&None).into_iter().chain(map.get(&Some(self_ty)))) + .flat_map(|v| v.iter().copied()) + } + + pub fn all_impls(&self) -> impl Iterator + '_ { + self.map.values().flat_map(|map| map.values().flat_map(|v| v.iter().copied())) + } +} + +/// Inherent impls defined in some crate. +/// +/// Inherent impls can only be defined in the crate that also defines the self type of the impl +/// (note that some primitives are considered to be defined by both libcore and liballoc). +/// +/// This makes inherent impl lookup easier than trait impl lookup since we only have to consider a +/// single crate. +#[derive(Debug, Eq, PartialEq)] +pub struct InherentImpls { + map: FxHashMap>, +} + +impl InherentImpls { + pub(crate) fn inherent_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc { + let mut map: FxHashMap<_, Vec<_>> = FxHashMap::default(); + + 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.scope.impls() { + let data = db.impl_data(impl_id); + if data.target_trait.is_some() { + continue; + } + + let self_ty = db.impl_self_ty(impl_id); + if let Some(fp) = TyFingerprint::for_impl(&self_ty.value) { + map.entry(fp).or_default().push(impl_id); + } + } + } + + Arc::new(Self { map }) + } + + pub fn for_self_ty(&self, self_ty: &Ty) -> &[ImplId] { + match TyFingerprint::for_impl(self_ty) { + Some(fp) => self.map.get(&fp).map(|vec| vec.as_ref()).unwrap_or(&[]), + None => &[], + } } - pub fn all_impls<'a>(&'a self) -> impl Iterator + 'a { - self.inherent_impls - .values() - .chain(self.impls_by_trait.values().flat_map(|m| m.values())) - .flatten() - .copied() + pub fn all_impls(&self) -> impl Iterator + '_ { + self.map.values().flat_map(|v| v.iter().copied()) } } @@ -515,9 +519,9 @@ fn iterate_inherent_methods( None => return false, }; for krate in def_crates { - let impls = db.impls_in_crate(krate); + let impls = db.inherent_impls_in_crate(krate); - for impl_def in impls.lookup_impl_defs(&self_ty.value) { + for &impl_def in impls.for_self_ty(&self_ty.value) { for &item in db.impl_data(impl_def).items.iter() { if !is_valid_candidate(db, name, receiver_ty, item, self_ty) { continue; -- cgit v1.2.3 From d5d485ef9289589332893f2c0ad96cb366afe9d6 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 28 Jun 2020 21:17:27 +0200 Subject: Implement Chalk variable kinds This means we need to keep track of the kinds (general/int/float) of variables in `Canonical`, which requires some more ceremony. (It also exposes some places where we're not really dealing with canonicalization correctly -- another thing to be cleaned up when we switch to using Chalk's types directly.) Should fix the last remaining issue of #2534. --- crates/ra_hir_ty/src/method_resolution.rs | 32 ++++++++++++++++--------------- 1 file changed, 17 insertions(+), 15 deletions(-) (limited to 'crates/ra_hir_ty/src/method_resolution.rs') diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs index c19519cf1..c3edd6885 100644 --- a/crates/ra_hir_ty/src/method_resolution.rs +++ b/crates/ra_hir_ty/src/method_resolution.rs @@ -2,7 +2,7 @@ //! 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 std::{iter, sync::Arc}; use arrayvec::ArrayVec; use hir_def::{ @@ -17,7 +17,8 @@ use rustc_hash::{FxHashMap, FxHashSet}; use super::Substs; use crate::{ autoderef, db::HirDatabase, primitive::FloatBitness, utils::all_super_traits, ApplicationTy, - Canonical, DebruijnIndex, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor, TypeWalk, + Canonical, DebruijnIndex, InEnvironment, TraitEnvironment, TraitRef, Ty, TyKind, TypeCtor, + TypeWalk, }; /// This is used as a key for indexing impls. @@ -377,7 +378,7 @@ fn iterate_method_candidates_with_autoref( return true; } let refed = Canonical { - num_vars: deref_chain[0].num_vars, + kinds: deref_chain[0].kinds.clone(), value: Ty::apply_one(TypeCtor::Ref(Mutability::Shared), deref_chain[0].value.clone()), }; if iterate_method_candidates_by_receiver( @@ -393,7 +394,7 @@ fn iterate_method_candidates_with_autoref( return true; } let ref_muted = Canonical { - num_vars: deref_chain[0].num_vars, + kinds: deref_chain[0].kinds.clone(), value: Ty::apply_one(TypeCtor::Ref(Mutability::Mut), deref_chain[0].value.clone()), }; if iterate_method_candidates_by_receiver( @@ -612,18 +613,19 @@ pub(crate) fn inherent_impl_substs( // we create a var for each type parameter of the impl; we need to keep in // mind here that `self_ty` might have vars of its own let vars = Substs::build_for_def(db, impl_id) - .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty.num_vars) + .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty.kinds.len()) .build(); let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars); - let self_ty_with_vars = - Canonical { num_vars: vars.len() + self_ty.num_vars, value: self_ty_with_vars }; - let substs = super::infer::unify(&self_ty_with_vars, self_ty); + let mut kinds = self_ty.kinds.to_vec(); + kinds.extend(iter::repeat(TyKind::General).take(vars.len())); + let tys = Canonical { kinds: kinds.into(), value: (self_ty_with_vars, self_ty.value.clone()) }; + let substs = super::infer::unify(&tys); // We only want the substs for the vars we added, not the ones from self_ty. // Also, if any of the vars we added are still in there, we replace them by // Unknown. I think this can only really happen if self_ty contained // Unknown, and in that case we want the result to contain Unknown in those // places again. - substs.map(|s| fallback_bound_vars(s.suffix(vars.len()), self_ty.num_vars)) + substs.map(|s| fallback_bound_vars(s.suffix(vars.len()), self_ty.kinds.len())) } /// This replaces any 'free' Bound vars in `s` (i.e. those with indices past @@ -683,15 +685,15 @@ fn generic_implements_goal( trait_: TraitId, self_ty: Canonical, ) -> Canonical> { - let num_vars = self_ty.num_vars; + let mut kinds = self_ty.kinds.to_vec(); let substs = super::Substs::build_for_def(db, trait_) .push(self_ty.value) - .fill_with_bound_vars(DebruijnIndex::INNERMOST, num_vars) + .fill_with_bound_vars(DebruijnIndex::INNERMOST, kinds.len()) .build(); - let num_vars = substs.len() - 1 + self_ty.num_vars; + kinds.extend(iter::repeat(TyKind::General).take(substs.len() - 1)); let trait_ref = TraitRef { trait_, substs }; let obligation = super::Obligation::Trait(trait_ref); - Canonical { num_vars, value: InEnvironment::new(env, obligation) } + Canonical { kinds: kinds.into(), value: InEnvironment::new(env, obligation) } } fn autoderef_method_receiver( @@ -704,9 +706,9 @@ fn autoderef_method_receiver( if let Some(Ty::Apply(ApplicationTy { ctor: TypeCtor::Array, parameters })) = deref_chain.last().map(|ty| &ty.value) { - let num_vars = deref_chain.last().unwrap().num_vars; + let kinds = deref_chain.last().unwrap().kinds.clone(); let unsized_ty = Ty::apply(TypeCtor::Slice, parameters.clone()); - deref_chain.push(Canonical { value: unsized_ty, num_vars }) + deref_chain.push(Canonical { value: unsized_ty, kinds }) } deref_chain } -- cgit v1.2.3 From 7e9c4d58f189d4ac3c390a6ea345f2578dd5f661 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sat, 11 Jul 2020 19:12:10 +0200 Subject: Search more efficiently for int/float impls --- crates/ra_hir_ty/src/method_resolution.rs | 71 ++++++++++++++++++++++++++++--- 1 file changed, 66 insertions(+), 5 deletions(-) (limited to 'crates/ra_hir_ty/src/method_resolution.rs') diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs index a45febbf7..fb4b30a13 100644 --- a/crates/ra_hir_ty/src/method_resolution.rs +++ b/crates/ra_hir_ty/src/method_resolution.rs @@ -6,8 +6,10 @@ use std::{iter, sync::Arc}; use arrayvec::ArrayVec; use hir_def::{ - lang_item::LangItemTarget, type_ref::Mutability, AssocContainerId, AssocItemId, FunctionId, - HasModule, ImplId, Lookup, TraitId, + builtin_type::{IntBitness, Signedness}, + lang_item::LangItemTarget, + type_ref::Mutability, + AssocContainerId, AssocItemId, FunctionId, HasModule, ImplId, Lookup, TraitId, }; use hir_expand::name::Name; use ra_db::CrateId; @@ -16,9 +18,12 @@ use rustc_hash::{FxHashMap, FxHashSet}; use super::Substs; use crate::{ - autoderef, db::HirDatabase, primitive::FloatBitness, utils::all_super_traits, ApplicationTy, - Canonical, DebruijnIndex, InEnvironment, TraitEnvironment, TraitRef, Ty, TyKind, TypeCtor, - TypeWalk, + autoderef, + db::HirDatabase, + primitive::{FloatBitness, FloatTy, IntTy}, + utils::all_super_traits, + ApplicationTy, Canonical, DebruijnIndex, InEnvironment, TraitEnvironment, TraitRef, Ty, TyKind, + TypeCtor, TypeWalk, }; /// This is used as a key for indexing impls. @@ -39,6 +44,62 @@ impl TyFingerprint { } } +pub(crate) const ALL_INT_FPS: [TyFingerprint; 12] = [ + TyFingerprint::Apply(TypeCtor::Int(IntTy { + signedness: Signedness::Unsigned, + bitness: IntBitness::X8, + })), + TyFingerprint::Apply(TypeCtor::Int(IntTy { + signedness: Signedness::Unsigned, + bitness: IntBitness::X16, + })), + TyFingerprint::Apply(TypeCtor::Int(IntTy { + signedness: Signedness::Unsigned, + bitness: IntBitness::X32, + })), + TyFingerprint::Apply(TypeCtor::Int(IntTy { + signedness: Signedness::Unsigned, + bitness: IntBitness::X64, + })), + TyFingerprint::Apply(TypeCtor::Int(IntTy { + signedness: Signedness::Unsigned, + bitness: IntBitness::X128, + })), + TyFingerprint::Apply(TypeCtor::Int(IntTy { + signedness: Signedness::Unsigned, + bitness: IntBitness::Xsize, + })), + TyFingerprint::Apply(TypeCtor::Int(IntTy { + signedness: Signedness::Signed, + bitness: IntBitness::X8, + })), + TyFingerprint::Apply(TypeCtor::Int(IntTy { + signedness: Signedness::Signed, + bitness: IntBitness::X16, + })), + TyFingerprint::Apply(TypeCtor::Int(IntTy { + signedness: Signedness::Signed, + bitness: IntBitness::X32, + })), + TyFingerprint::Apply(TypeCtor::Int(IntTy { + signedness: Signedness::Signed, + bitness: IntBitness::X64, + })), + TyFingerprint::Apply(TypeCtor::Int(IntTy { + signedness: Signedness::Signed, + bitness: IntBitness::X128, + })), + TyFingerprint::Apply(TypeCtor::Int(IntTy { + signedness: Signedness::Signed, + bitness: IntBitness::Xsize, + })), +]; + +pub(crate) const ALL_FLOAT_FPS: [TyFingerprint; 2] = [ + TyFingerprint::Apply(TypeCtor::Float(FloatTy { bitness: FloatBitness::X32 })), + TyFingerprint::Apply(TypeCtor::Float(FloatTy { bitness: FloatBitness::X64 })), +]; + /// Trait impls defined or available in some crate. #[derive(Debug, Eq, PartialEq)] pub struct TraitImpls { -- cgit v1.2.3