From ebd8233b3e6737234a39c0cc9361664fbe21ed20 Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Fri, 19 Jun 2020 01:29:34 +0200 Subject: Replace `impls_in_trait` with `CrateImplDefs` --- crates/ra_hir/src/db.rs | 8 ++--- crates/ra_hir_def/src/lib.rs | 2 +- crates/ra_hir_ty/src/db.rs | 15 +++----- crates/ra_hir_ty/src/method_resolution.rs | 57 ++++++++++++++++++++++++++----- crates/ra_hir_ty/src/traits.rs | 31 +---------------- crates/ra_hir_ty/src/traits/chalk.rs | 28 ++++++++++----- crates/ra_ide_db/src/change.rs | 1 - 7 files changed, 79 insertions(+), 63 deletions(-) diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs index b6b665de1..b4f818088 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, ImplsForTraitQuery, - ImplsInCrateQuery, InferQueryQuery, InternAssocTyValueQuery, InternChalkImplQuery, - InternTypeCtorQuery, InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery, - TraitDatumQuery, TraitSolveQuery, TyQuery, ValueTyQuery, + HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, ImplsInCrateQuery, + InferQueryQuery, InternAssocTyValueQuery, InternChalkImplQuery, InternTypeCtorQuery, + InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery, TraitDatumQuery, + TraitSolveQuery, TyQuery, ValueTyQuery, }; #[test] diff --git a/crates/ra_hir_def/src/lib.rs b/crates/ra_hir_def/src/lib.rs index edc59e5a8..af2a717c9 100644 --- a/crates/ra_hir_def/src/lib.rs +++ b/crates/ra_hir_def/src/lib.rs @@ -159,7 +159,7 @@ pub struct TypeAliasId(salsa::InternId); type TypeAliasLoc = AssocItemLoc; impl_intern!(TypeAliasId, TypeAliasLoc, intern_type_alias, lookup_intern_type_alias); -#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Ord, PartialOrd)] pub struct ImplId(salsa::InternId); type ImplLoc = ItemLoc; impl_intern!(ImplId, ImplLoc, intern_impl, lookup_intern_impl); diff --git a/crates/ra_hir_ty/src/db.rs b/crates/ra_hir_ty/src/db.rs index bf71d38d6..7889b8d2c 100644 --- a/crates/ra_hir_ty/src/db.rs +++ b/crates/ra_hir_ty/src/db.rs @@ -3,15 +3,15 @@ use std::sync::Arc; use hir_def::{ - db::DefDatabase, DefWithBodyId, FunctionId, GenericDefId, ImplId, LocalFieldId, TraitId, - TypeParamId, VariantId, + db::DefDatabase, DefWithBodyId, FunctionId, GenericDefId, ImplId, LocalFieldId, TypeParamId, + VariantId, }; use ra_arena::map::ArenaMap; use ra_db::{impl_intern_key, salsa, CrateId, Upcast}; use ra_prof::profile; use crate::{ - method_resolution::{CrateImplDefs, TyFingerprint}, + method_resolution::CrateImplDefs, traits::{chalk, AssocTyValue, Impl}, Binders, CallableDef, GenericPredicate, InferenceResult, OpaqueTyId, PolyFnSig, ReturnTypeImplTraits, Substs, TraitRef, Ty, TyDefId, TypeCtor, ValueTyDefId, @@ -70,13 +70,8 @@ pub trait HirDatabase: DefDatabase + Upcast { #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_in_crate_query)] fn impls_in_crate(&self, krate: CrateId) -> Arc; - #[salsa::invoke(crate::traits::impls_for_trait_query)] - fn impls_for_trait( - &self, - krate: CrateId, - trait_: TraitId, - self_ty_fp: Option, - ) -> Arc<[ImplId]>; + #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_from_deps_query)] + fn impls_from_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 e83b39456..01b3362d7 100644 --- a/crates/ra_hir_ty/src/method_resolution.rs +++ b/crates/ra_hir_ty/src/method_resolution.rs @@ -38,18 +38,58 @@ impl TyFingerprint { } } +/// A queryable and mergeable collection of impls. #[derive(Debug, PartialEq, Eq)] pub struct CrateImplDefs { - impls: FxHashMap>, + inherent_impls: FxHashMap>, impls_by_trait: 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 { impls: FxHashMap::default(), impls_by_trait: FxHashMap::default() }; + let mut res = CrateImplDefs { + inherent_impls: FxHashMap::default(), + impls_by_trait: FxHashMap::default(), + }; + res.fill(db, krate); + + Arc::new(res) + } + + /// 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 { + // FIXME: This should take visibility and orphan rules into account to keep the result + // smaller. + let _p = profile("impls_from_deps_query"); + let crate_graph = db.crate_graph(); + let mut res = CrateImplDefs { + inherent_impls: FxHashMap::default(), + impls_by_trait: FxHashMap::default(), + }; + let mut seen = FxHashSet::default(); + let mut worklist = vec![krate]; + while let Some(krate) = worklist.pop() { + if !seen.insert(krate) { + continue; + } + // No deduplication, since a) impls can't be reexported, b) we visit a crate only once + res.fill(db, krate); + + worklist.extend(crate_graph[krate].dependencies.iter().map(|dep| dep.crate_id)); + } + + 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() { @@ -57,7 +97,7 @@ impl CrateImplDefs { Some(tr) => { let self_ty = db.impl_self_ty(impl_id); let self_ty_fp = TyFingerprint::for_impl(&self_ty.value); - res.impls_by_trait + self.impls_by_trait .entry(tr.value.trait_) .or_default() .entry(self_ty_fp) @@ -67,18 +107,17 @@ impl CrateImplDefs { None => { let self_ty = db.impl_self_ty(impl_id); if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty.value) { - res.impls.entry(self_ty_fp).or_default().push(impl_id); + self.inherent_impls.entry(self_ty_fp).or_default().push(impl_id); } } } } } - - Arc::new(res) } + pub fn lookup_impl_defs(&self, ty: &Ty) -> impl Iterator + '_ { let fingerprint = TyFingerprint::for_impl(ty); - fingerprint.and_then(|f| self.impls.get(&f)).into_iter().flatten().copied() + 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 + '_ { @@ -110,7 +149,7 @@ impl CrateImplDefs { } pub fn all_impls<'a>(&'a self) -> impl Iterator + 'a { - self.impls + self.inherent_impls .values() .chain(self.impls_by_trait.values().flat_map(|m| m.values())) .flatten() diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs index 6bc6d474c..99d7a9616 100644 --- a/crates/ra_hir_ty/src/traits.rs +++ b/crates/ra_hir_ty/src/traits.rs @@ -5,9 +5,8 @@ use chalk_ir::cast::Cast; use hir_def::{expr::ExprId, DefWithBodyId, ImplId, TraitId, TypeAliasId}; use ra_db::{impl_intern_key, salsa, CrateId}; use ra_prof::profile; -use rustc_hash::FxHashSet; -use crate::{db::HirDatabase, method_resolution::TyFingerprint, DebruijnIndex}; +use crate::{db::HirDatabase, DebruijnIndex}; use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk}; @@ -36,34 +35,6 @@ fn create_chalk_solver() -> chalk_solve::Solver { solver_choice.into_solver() } -/// Collects impls for the given trait in the whole dependency tree of `krate`. -pub(crate) fn impls_for_trait_query( - db: &dyn HirDatabase, - krate: CrateId, - trait_: TraitId, - self_ty_fp: Option, -) -> Arc<[ImplId]> { - // FIXME: We could be a lot smarter here - because of the orphan rules and - // the fact that the trait and the self type need to be in the dependency - // tree of a crate somewhere for an impl to exist, we could skip looking in - // a lot of crates completely - let mut impls = FxHashSet::default(); - // We call the query recursively here. On the one hand, this means we can - // reuse results from queries for different crates; on the other hand, this - // will only ever get called for a few crates near the root of the tree (the - // ones the user is editing), so this may actually be a waste of memory. I'm - // doing it like this mainly for simplicity for now. - for dep in &db.crate_graph()[krate].dependencies { - impls.extend(db.impls_for_trait(dep.crate_id, trait_, self_ty_fp).iter()); - } - let crate_impl_defs = db.impls_in_crate(krate); - match self_ty_fp { - Some(fp) => impls.extend(crate_impl_defs.lookup_impl_defs_for_trait_and_ty(trait_, fp)), - None => impls.extend(crate_impl_defs.lookup_impl_defs_for_trait(trait_)), - } - impls.into_iter().collect() -} - /// A set of clauses that we assume to be true. E.g. if we are inside this function: /// ```rust /// fn foo(t: T) {} diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs index a72a82f5a..2f35d6d49 100644 --- a/crates/ra_hir_ty/src/traits/chalk.rs +++ b/crates/ra_hir_ty/src/traits/chalk.rs @@ -74,14 +74,26 @@ 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 mut result: Vec<_> = self - .db - .impls_for_trait(self.krate, trait_, self_ty_fp) - .iter() - .copied() - .map(Impl::ImplDef) - .map(|impl_| impl_.to_chalk(self.db)) - .collect(); + let in_deps = self.db.impls_from_deps(self.krate); + let in_self = self.db.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); + + let mut result: Vec<_> = match self_ty_fp { + 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) + }) + .collect(), + None => impl_maps + .iter() + .flat_map(|crate_impl_defs| { + crate_impl_defs.lookup_impl_defs_for_trait(trait_).map(id_to_chalk) + }) + .collect(), + }; let arg: Option = parameters.get(1).map(|p| from_chalk(self.db, p.assert_ty_ref(&Interner).clone())); diff --git a/crates/ra_ide_db/src/change.rs b/crates/ra_ide_db/src/change.rs index 78ee6a515..21622a1b0 100644 --- a/crates/ra_ide_db/src/change.rs +++ b/crates/ra_ide_db/src/change.rs @@ -283,7 +283,6 @@ impl RootDatabase { hir::db::GenericPredicatesQuery hir::db::GenericDefaultsQuery hir::db::ImplsInCrateQuery - hir::db::ImplsForTraitQuery hir::db::InternTypeCtorQuery hir::db::InternTypeParamIdQuery hir::db::InternChalkImplQuery -- cgit v1.2.3 From aa8442af70c00b8e5ccef070447c6bca5d1a055a Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Fri, 19 Jun 2020 22:33:13 +0200 Subject: Don't include downstream crate in query --- crates/ra_hir_ty/src/method_resolution.rs | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs index 01b3362d7..be685e12f 100644 --- a/crates/ra_hir_ty/src/method_resolution.rs +++ b/crates/ra_hir_ty/src/method_resolution.rs @@ -74,7 +74,8 @@ impl CrateImplDefs { impls_by_trait: FxHashMap::default(), }; let mut seen = FxHashSet::default(); - let mut worklist = vec![krate]; + let mut worklist = + crate_graph[krate].dependencies.iter().map(|dep| dep.crate_id).collect::>(); while let Some(krate) = worklist.pop() { if !seen.insert(krate) { continue; -- cgit v1.2.3 From a91c2e94b7947d8dcf3437f809cbdab0b4493a77 Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Fri, 19 Jun 2020 23:17:53 +0200 Subject: Add new query to stats --- crates/ra_hir/src/db.rs | 8 ++++---- crates/ra_ide_db/src/change.rs | 1 + 2 files changed, 5 insertions(+), 4 deletions(-) diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs index b4f818088..b25dac28e 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, ImplsInCrateQuery, - InferQueryQuery, InternAssocTyValueQuery, InternChalkImplQuery, InternTypeCtorQuery, - InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery, TraitDatumQuery, - TraitSolveQuery, TyQuery, ValueTyQuery, + HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, ImplsFromDepsQuery, + ImplsInCrateQuery, InferQueryQuery, InternAssocTyValueQuery, InternChalkImplQuery, + InternTypeCtorQuery, InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery, + TraitDatumQuery, TraitSolveQuery, TyQuery, ValueTyQuery, }; #[test] diff --git a/crates/ra_ide_db/src/change.rs b/crates/ra_ide_db/src/change.rs index 21622a1b0..98993d571 100644 --- a/crates/ra_ide_db/src/change.rs +++ b/crates/ra_ide_db/src/change.rs @@ -283,6 +283,7 @@ impl RootDatabase { hir::db::GenericPredicatesQuery hir::db::GenericDefaultsQuery hir::db::ImplsInCrateQuery + hir::db::ImplsFromDepsQuery hir::db::InternTypeCtorQuery hir::db::InternTypeParamIdQuery hir::db::InternChalkImplQuery -- cgit v1.2.3 From a3c2f5126fb9f2575584d12335b6e7e82deec45a Mon Sep 17 00:00:00 2001 From: Jonas Schievink Date: Sat, 20 Jun 2020 00:36:02 +0200 Subject: Recursively compute impl sets --- crates/ra_hir_ty/src/method_resolution.rs | 39 ++++++++++++++++++++----------- 1 file changed, 26 insertions(+), 13 deletions(-) diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs index be685e12f..ed638c195 100644 --- a/crates/ra_hir_ty/src/method_resolution.rs +++ b/crates/ra_hir_ty/src/method_resolution.rs @@ -65,26 +65,20 @@ impl CrateImplDefs { db: &dyn HirDatabase, krate: CrateId, ) -> Arc { - // FIXME: This should take visibility and orphan rules into account to keep the result - // smaller. let _p = profile("impls_from_deps_query"); let crate_graph = db.crate_graph(); let mut res = CrateImplDefs { inherent_impls: FxHashMap::default(), impls_by_trait: FxHashMap::default(), }; - let mut seen = FxHashSet::default(); - let mut worklist = - crate_graph[krate].dependencies.iter().map(|dep| dep.crate_id).collect::>(); - while let Some(krate) = worklist.pop() { - if !seen.insert(krate) { - continue; - } - - // No deduplication, since a) impls can't be reexported, b) we visit a crate only once - res.fill(db, krate); - worklist.extend(crate_graph[krate].dependencies.iter().map(|dep| dep.crate_id)); + // 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)); } Arc::new(res) @@ -116,6 +110,25 @@ impl CrateImplDefs { } } + 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); + vec.sort(); + vec.dedup(); + } + + for (trait_, other_map) in &other.impls_by_trait { + let map = self.impls_by_trait.entry(*trait_).or_default(); + for (fp, impls) in other_map { + let vec = map.entry(*fp).or_default(); + vec.extend(impls); + vec.sort(); + vec.dedup(); + } + } + } + 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() -- cgit v1.2.3