From 63ea8f2af097316523f54f09e1c54d515a1bb9fd Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Wed, 1 Jul 2020 15:18:51 +0200 Subject: Add a transitive deps iterator to `CrateGraph` --- crates/ra_db/src/input.rs | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) (limited to 'crates') diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs index 445a1ee48..aaa492759 100644 --- a/crates/ra_db/src/input.rs +++ b/crates/ra_db/src/input.rs @@ -197,6 +197,23 @@ impl CrateGraph { self.arena.keys().copied() } + /// Returns an iterator over all transitive dependencies of the given crate. + pub fn transitive_deps(&self, of: CrateId) -> impl Iterator + '_ { + let mut worklist = vec![of]; + let mut deps = FxHashSet::default(); + + while let Some(krate) = worklist.pop() { + if !deps.insert(krate) { + continue; + } + + worklist.extend(self[krate].dependencies.iter().map(|dep| dep.crate_id)); + } + + deps.remove(&of); + deps.into_iter() + } + // FIXME: this only finds one crate with the given root; we could have multiple pub fn crate_id_for_crate_root(&self, file_id: FileId) -> Option { let (&crate_id, _) = -- cgit v1.2.3 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') 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/src/code_model.rs | 16 +-- crates/ra_hir/src/db.rs | 8 +- crates/ra_hir_ty/src/db.rs | 13 +- crates/ra_hir_ty/src/method_resolution.rs | 192 +++++++++++++++--------------- crates/ra_hir_ty/src/traits/chalk.rs | 10 +- crates/ra_ide/src/goto_implementation.rs | 4 + crates/ra_ide_db/src/change.rs | 5 +- 7 files changed, 130 insertions(+), 118 deletions(-) (limited to 'crates') diff --git a/crates/ra_hir/src/code_model.rs b/crates/ra_hir/src/code_model.rs index e09eb77c2..cc72964ff 100644 --- a/crates/ra_hir/src/code_model.rs +++ b/crates/ra_hir/src/code_model.rs @@ -1053,12 +1053,14 @@ pub struct ImplDef { impl ImplDef { pub fn all_in_crate(db: &dyn HirDatabase, krate: Crate) -> Vec { - let impls = db.impls_in_crate(krate.id); - impls.all_impls().map(Self::from).collect() + let inherent = db.inherent_impls_in_crate(krate.id); + let trait_ = db.trait_impls_in_crate(krate.id); + + inherent.all_impls().chain(trait_.all_impls()).map(Self::from).collect() } pub fn for_trait(db: &dyn HirDatabase, krate: Crate, trait_: Trait) -> Vec { - let impls = db.impls_in_crate(krate.id); - impls.lookup_impl_defs_for_trait(trait_.id).map(Self::from).collect() + let impls = db.trait_impls_in_crate(krate.id); + impls.for_trait(trait_.id).map(Self::from).collect() } pub fn target_trait(self, db: &dyn HirDatabase) -> Option { @@ -1303,10 +1305,10 @@ impl Type { mut callback: impl FnMut(AssocItem) -> Option, ) -> Option { for krate in self.ty.value.def_crates(db, krate.id)? { - 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 &item in db.impl_data(impl_def).items.iter() { + for impl_def in impls.for_self_ty(&self.ty.value) { + for &item in db.impl_data(*impl_def).items.iter() { if let Some(result) = callback(item.into()) { return Some(result); } diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs index bb67952de..cb48ca065 100644 --- a/crates/ra_hir/src/db.rs +++ b/crates/ra_hir/src/db.rs @@ -16,10 +16,10 @@ pub use hir_expand::db::{ pub use hir_ty::db::{ AssociatedTyDataQuery, AssociatedTyValueQuery, CallableItemSignatureQuery, FieldTypesQuery, GenericDefaultsQuery, GenericPredicatesForParamQuery, GenericPredicatesQuery, HirDatabase, - HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, ImplsFromDepsQuery, - ImplsInCrateQuery, InferQueryQuery, InternAssocTyValueQuery, InternChalkImplQuery, - InternTypeCtorQuery, InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery, - TraitDatumQuery, TraitSolveQuery, TyQuery, ValueTyQuery, + HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, InferQueryQuery, + InherentImplsInCrateQuery, InternAssocTyValueQuery, InternChalkImplQuery, InternTypeCtorQuery, + InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery, TraitDatumQuery, + TraitImplsInCrateQuery, TraitImplsInDepsQuery, TraitSolveQuery, TyQuery, ValueTyQuery, }; #[test] diff --git a/crates/ra_hir_ty/src/db.rs b/crates/ra_hir_ty/src/db.rs index cad553273..dc06c0ee7 100644 --- a/crates/ra_hir_ty/src/db.rs +++ b/crates/ra_hir_ty/src/db.rs @@ -11,7 +11,7 @@ use ra_db::{impl_intern_key, salsa, CrateId, Upcast}; use ra_prof::profile; use crate::{ - method_resolution::CrateImplDefs, + method_resolution::{InherentImpls, TraitImpls}, traits::{chalk, AssocTyValue, Impl}, Binders, CallableDef, GenericPredicate, InferenceResult, OpaqueTyId, PolyFnSig, ReturnTypeImplTraits, TraitRef, Ty, TyDefId, TypeCtor, ValueTyDefId, @@ -67,11 +67,14 @@ pub trait HirDatabase: DefDatabase + Upcast { #[salsa::invoke(crate::lower::generic_defaults_query)] fn generic_defaults(&self, def: GenericDefId) -> Arc<[Binders]>; - #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_in_crate_query)] - fn impls_in_crate(&self, krate: CrateId) -> Arc; + #[salsa::invoke(InherentImpls::inherent_impls_in_crate_query)] + fn inherent_impls_in_crate(&self, krate: CrateId) -> Arc; - #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_from_deps_query)] - fn impls_from_deps(&self, krate: CrateId) -> Arc; + #[salsa::invoke(TraitImpls::trait_impls_in_crate_query)] + fn trait_impls_in_crate(&self, krate: CrateId) -> Arc; + + #[salsa::invoke(TraitImpls::trait_impls_in_deps_query)] + fn trait_impls_in_deps(&self, krate: CrateId) -> Arc; // Interned IDs for Chalk integration #[salsa::interned] 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; diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs index 8ef4941c0..c97b81d57 100644 --- a/crates/ra_hir_ty/src/traits/chalk.rs +++ b/crates/ra_hir_ty/src/traits/chalk.rs @@ -77,8 +77,8 @@ impl<'a> chalk_solve::RustIrDatabase for ChalkContext<'a> { // Note: Since we're using impls_for_trait, only impls where the trait // can be resolved should ever reach Chalk. `impl_datum` relies on that // and will panic if the trait can't be resolved. - let in_deps = self.db.impls_from_deps(self.krate); - let in_self = self.db.impls_in_crate(self.krate); + let in_deps = self.db.trait_impls_in_deps(self.krate); + let in_self = self.db.trait_impls_in_crate(self.krate); let impl_maps = [in_deps, in_self]; let id_to_chalk = |id: hir_def::ImplId| Impl::ImplDef(id).to_chalk(self.db); @@ -87,14 +87,12 @@ impl<'a> chalk_solve::RustIrDatabase for ChalkContext<'a> { Some(fp) => impl_maps .iter() .flat_map(|crate_impl_defs| { - crate_impl_defs.lookup_impl_defs_for_trait_and_ty(trait_, fp).map(id_to_chalk) + crate_impl_defs.for_trait_and_self_ty(trait_, fp).map(id_to_chalk) }) .collect(), None => impl_maps .iter() - .flat_map(|crate_impl_defs| { - crate_impl_defs.lookup_impl_defs_for_trait(trait_).map(id_to_chalk) - }) + .flat_map(|crate_impl_defs| crate_impl_defs.for_trait(trait_).map(id_to_chalk)) .collect(), }; diff --git a/crates/ra_ide/src/goto_implementation.rs b/crates/ra_ide/src/goto_implementation.rs index 99a7022a4..9acc960fc 100644 --- a/crates/ra_ide/src/goto_implementation.rs +++ b/crates/ra_ide/src/goto_implementation.rs @@ -219,6 +219,10 @@ impl T for &Foo {} #[derive(Copy)] //^^^^^^^^^^^^^^^ struct Foo<|>; + +mod marker { + trait Copy {} +} "#, ); } diff --git a/crates/ra_ide_db/src/change.rs b/crates/ra_ide_db/src/change.rs index b507000f2..dbe6eacc5 100644 --- a/crates/ra_ide_db/src/change.rs +++ b/crates/ra_ide_db/src/change.rs @@ -243,8 +243,9 @@ impl RootDatabase { hir::db::GenericPredicatesForParamQuery hir::db::GenericPredicatesQuery hir::db::GenericDefaultsQuery - hir::db::ImplsInCrateQuery - hir::db::ImplsFromDepsQuery + hir::db::InherentImplsInCrateQuery + hir::db::TraitImplsInCrateQuery + hir::db::TraitImplsInDepsQuery hir::db::InternTypeCtorQuery hir::db::InternTypeParamIdQuery hir::db::InternChalkImplQuery -- cgit v1.2.3