aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorbors[bot] <26634292+bors[bot]@users.noreply.github.com>2020-06-20 23:14:21 +0100
committerGitHub <[email protected]>2020-06-20 23:14:21 +0100
commit04d64267de2c9ade61ae9fdbc98114599c11a2d7 (patch)
treeeb18414e177eb0e40e902c5ec45cebc49ac8d43b
parent92fef01f6506b33c0489e020df1ad9fdce2fac9b (diff)
parenta3c2f5126fb9f2575584d12335b6e7e82deec45a (diff)
Merge #4947
4947: Replace `impls_in_trait` query with smarter use of `CrateImplDefs` r=matklad a=jonas-schievink `impls_in_trait` was allocating a whopping ~400 MB of RAM when running analysis-stats on r-a itself. Remove it, instead adding a query that computes a summary `CrateImplDefs` map for all transitive dependencies. This can probably still be made more efficient, but this already reduces the peak memory usage by 25% without much performance impact on analysis-stats. **Before**: ``` Total: 34.962107188s, 2083mb allocated 2141mb resident 422mb ImplsForTraitQuery (deps) 250mb CrateDefMapQueryQuery 147mb MacroArgQuery 140mb TraitSolveQuery (deps) 68mb InferQueryQuery (deps) 62mb ImplDatumQuery (deps) ``` **After**: ``` Total: 35.261100358s, 1520mb allocated 1569mb resident 250mb CrateDefMapQueryQuery 147mb MacroArgQuery 144mb TraitSolveQuery (deps) 68mb InferQueryQuery (deps) 61mb ImplDatumQuery (deps) 45mb BodyQuery 45mb ImplDatumQuery ``` Co-authored-by: Jonas Schievink <[email protected]>
-rw-r--r--crates/ra_hir/src/db.rs2
-rw-r--r--crates/ra_hir_def/src/lib.rs2
-rw-r--r--crates/ra_hir_ty/src/db.rs15
-rw-r--r--crates/ra_hir_ty/src/method_resolution.rs69
-rw-r--r--crates/ra_hir_ty/src/traits.rs31
-rw-r--r--crates/ra_hir_ty/src/traits/chalk.rs28
-rw-r--r--crates/ra_ide_db/src/change.rs2
7 files changed, 90 insertions, 59 deletions
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index b6b665de1..b25dac28e 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -16,7 +16,7 @@ pub use hir_expand::db::{
16pub use hir_ty::db::{ 16pub use hir_ty::db::{
17 AssociatedTyDataQuery, AssociatedTyValueQuery, CallableItemSignatureQuery, FieldTypesQuery, 17 AssociatedTyDataQuery, AssociatedTyValueQuery, CallableItemSignatureQuery, FieldTypesQuery,
18 GenericDefaultsQuery, GenericPredicatesForParamQuery, GenericPredicatesQuery, HirDatabase, 18 GenericDefaultsQuery, GenericPredicatesForParamQuery, GenericPredicatesQuery, HirDatabase,
19 HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, ImplsForTraitQuery, 19 HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, ImplsFromDepsQuery,
20 ImplsInCrateQuery, InferQueryQuery, InternAssocTyValueQuery, InternChalkImplQuery, 20 ImplsInCrateQuery, InferQueryQuery, InternAssocTyValueQuery, InternChalkImplQuery,
21 InternTypeCtorQuery, InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery, 21 InternTypeCtorQuery, InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery,
22 TraitDatumQuery, TraitSolveQuery, TyQuery, ValueTyQuery, 22 TraitDatumQuery, TraitSolveQuery, TyQuery, ValueTyQuery,
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);
159type TypeAliasLoc = AssocItemLoc<ast::TypeAliasDef>; 159type TypeAliasLoc = AssocItemLoc<ast::TypeAliasDef>;
160impl_intern!(TypeAliasId, TypeAliasLoc, intern_type_alias, lookup_intern_type_alias); 160impl_intern!(TypeAliasId, TypeAliasLoc, intern_type_alias, lookup_intern_type_alias);
161 161
162#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] 162#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Ord, PartialOrd)]
163pub struct ImplId(salsa::InternId); 163pub struct ImplId(salsa::InternId);
164type ImplLoc = ItemLoc<ast::ImplDef>; 164type ImplLoc = ItemLoc<ast::ImplDef>;
165impl_intern!(ImplId, ImplLoc, intern_impl, lookup_intern_impl); 165impl_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 @@
3use std::sync::Arc; 3use std::sync::Arc;
4 4
5use hir_def::{ 5use hir_def::{
6 db::DefDatabase, DefWithBodyId, FunctionId, GenericDefId, ImplId, LocalFieldId, TraitId, 6 db::DefDatabase, DefWithBodyId, FunctionId, GenericDefId, ImplId, LocalFieldId, TypeParamId,
7 TypeParamId, VariantId, 7 VariantId,
8}; 8};
9use ra_arena::map::ArenaMap; 9use ra_arena::map::ArenaMap;
10use ra_db::{impl_intern_key, salsa, CrateId, Upcast}; 10use ra_db::{impl_intern_key, salsa, CrateId, Upcast};
11use ra_prof::profile; 11use ra_prof::profile;
12 12
13use crate::{ 13use crate::{
14 method_resolution::{CrateImplDefs, TyFingerprint}, 14 method_resolution::CrateImplDefs,
15 traits::{chalk, AssocTyValue, Impl}, 15 traits::{chalk, AssocTyValue, Impl},
16 Binders, CallableDef, GenericPredicate, InferenceResult, OpaqueTyId, PolyFnSig, 16 Binders, CallableDef, GenericPredicate, InferenceResult, OpaqueTyId, PolyFnSig,
17 ReturnTypeImplTraits, Substs, TraitRef, Ty, TyDefId, TypeCtor, ValueTyDefId, 17 ReturnTypeImplTraits, Substs, TraitRef, Ty, TyDefId, TypeCtor, ValueTyDefId,
@@ -70,13 +70,8 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
70 #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_in_crate_query)] 70 #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_in_crate_query)]
71 fn impls_in_crate(&self, krate: CrateId) -> Arc<CrateImplDefs>; 71 fn impls_in_crate(&self, krate: CrateId) -> Arc<CrateImplDefs>;
72 72
73 #[salsa::invoke(crate::traits::impls_for_trait_query)] 73 #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_from_deps_query)]
74 fn impls_for_trait( 74 fn impls_from_deps(&self, krate: CrateId) -> Arc<CrateImplDefs>;
75 &self,
76 krate: CrateId,
77 trait_: TraitId,
78 self_ty_fp: Option<TyFingerprint>,
79 ) -> Arc<[ImplId]>;
80 75
81 // Interned IDs for Chalk integration 76 // Interned IDs for Chalk integration
82 #[salsa::interned] 77 #[salsa::interned]
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index e83b39456..ed638c195 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -38,18 +38,53 @@ impl TyFingerprint {
38 } 38 }
39} 39}
40 40
41/// A queryable and mergeable collection of impls.
41#[derive(Debug, PartialEq, Eq)] 42#[derive(Debug, PartialEq, Eq)]
42pub struct CrateImplDefs { 43pub struct CrateImplDefs {
43 impls: FxHashMap<TyFingerprint, Vec<ImplId>>, 44 inherent_impls: FxHashMap<TyFingerprint, Vec<ImplId>>,
44 impls_by_trait: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>, 45 impls_by_trait: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>,
45} 46}
46 47
47impl CrateImplDefs { 48impl CrateImplDefs {
48 pub(crate) fn impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<CrateImplDefs> { 49 pub(crate) fn impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<CrateImplDefs> {
49 let _p = profile("impls_in_crate_query"); 50 let _p = profile("impls_in_crate_query");
50 let mut res = 51 let mut res = CrateImplDefs {
51 CrateImplDefs { impls: FxHashMap::default(), impls_by_trait: FxHashMap::default() }; 52 inherent_impls: FxHashMap::default(),
53 impls_by_trait: FxHashMap::default(),
54 };
55 res.fill(db, krate);
56
57 Arc::new(res)
58 }
59
60 /// Collects all impls from transitive dependencies of `krate` that may be used by `krate`.
61 ///
62 /// The full set of impls that can be used by `krate` is the returned map plus all the impls
63 /// from `krate` itself.
64 pub(crate) fn impls_from_deps_query(
65 db: &dyn HirDatabase,
66 krate: CrateId,
67 ) -> Arc<CrateImplDefs> {
68 let _p = profile("impls_from_deps_query");
69 let crate_graph = db.crate_graph();
70 let mut res = CrateImplDefs {
71 inherent_impls: FxHashMap::default(),
72 impls_by_trait: FxHashMap::default(),
73 };
52 74
75 // For each dependency, calculate `impls_from_deps` recursively, then add its own
76 // `impls_in_crate`.
77 // As we might visit crates multiple times, `merge` has to deduplicate impls to avoid
78 // wasting memory.
79 for dep in &crate_graph[krate].dependencies {
80 res.merge(&db.impls_from_deps(dep.crate_id));
81 res.merge(&db.impls_in_crate(dep.crate_id));
82 }
83
84 Arc::new(res)
85 }
86
87 fn fill(&mut self, db: &dyn HirDatabase, krate: CrateId) {
53 let crate_def_map = db.crate_def_map(krate); 88 let crate_def_map = db.crate_def_map(krate);
54 for (_module_id, module_data) in crate_def_map.modules.iter() { 89 for (_module_id, module_data) in crate_def_map.modules.iter() {
55 for impl_id in module_data.scope.impls() { 90 for impl_id in module_data.scope.impls() {
@@ -57,7 +92,7 @@ impl CrateImplDefs {
57 Some(tr) => { 92 Some(tr) => {
58 let self_ty = db.impl_self_ty(impl_id); 93 let self_ty = db.impl_self_ty(impl_id);
59 let self_ty_fp = TyFingerprint::for_impl(&self_ty.value); 94 let self_ty_fp = TyFingerprint::for_impl(&self_ty.value);
60 res.impls_by_trait 95 self.impls_by_trait
61 .entry(tr.value.trait_) 96 .entry(tr.value.trait_)
62 .or_default() 97 .or_default()
63 .entry(self_ty_fp) 98 .entry(self_ty_fp)
@@ -67,18 +102,36 @@ impl CrateImplDefs {
67 None => { 102 None => {
68 let self_ty = db.impl_self_ty(impl_id); 103 let self_ty = db.impl_self_ty(impl_id);
69 if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty.value) { 104 if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty.value) {
70 res.impls.entry(self_ty_fp).or_default().push(impl_id); 105 self.inherent_impls.entry(self_ty_fp).or_default().push(impl_id);
71 } 106 }
72 } 107 }
73 } 108 }
74 } 109 }
75 } 110 }
111 }
76 112
77 Arc::new(res) 113 fn merge(&mut self, other: &Self) {
114 for (fp, impls) in &other.inherent_impls {
115 let vec = self.inherent_impls.entry(*fp).or_default();
116 vec.extend(impls);
117 vec.sort();
118 vec.dedup();
119 }
120
121 for (trait_, other_map) in &other.impls_by_trait {
122 let map = self.impls_by_trait.entry(*trait_).or_default();
123 for (fp, impls) in other_map {
124 let vec = map.entry(*fp).or_default();
125 vec.extend(impls);
126 vec.sort();
127 vec.dedup();
128 }
129 }
78 } 130 }
131
79 pub fn lookup_impl_defs(&self, ty: &Ty) -> impl Iterator<Item = ImplId> + '_ { 132 pub fn lookup_impl_defs(&self, ty: &Ty) -> impl Iterator<Item = ImplId> + '_ {
80 let fingerprint = TyFingerprint::for_impl(ty); 133 let fingerprint = TyFingerprint::for_impl(ty);
81 fingerprint.and_then(|f| self.impls.get(&f)).into_iter().flatten().copied() 134 fingerprint.and_then(|f| self.inherent_impls.get(&f)).into_iter().flatten().copied()
82 } 135 }
83 136
84 pub fn lookup_impl_defs_for_trait(&self, tr: TraitId) -> impl Iterator<Item = ImplId> + '_ { 137 pub fn lookup_impl_defs_for_trait(&self, tr: TraitId) -> impl Iterator<Item = ImplId> + '_ {
@@ -110,7 +163,7 @@ impl CrateImplDefs {
110 } 163 }
111 164
112 pub fn all_impls<'a>(&'a self) -> impl Iterator<Item = ImplId> + 'a { 165 pub fn all_impls<'a>(&'a self) -> impl Iterator<Item = ImplId> + 'a {
113 self.impls 166 self.inherent_impls
114 .values() 167 .values()
115 .chain(self.impls_by_trait.values().flat_map(|m| m.values())) 168 .chain(self.impls_by_trait.values().flat_map(|m| m.values()))
116 .flatten() 169 .flatten()
diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs
index 892fbd6d1..6f43c3a22 100644
--- a/crates/ra_hir_ty/src/traits.rs
+++ b/crates/ra_hir_ty/src/traits.rs
@@ -7,9 +7,8 @@ use hir_def::{
7}; 7};
8use ra_db::{impl_intern_key, salsa, CrateId}; 8use ra_db::{impl_intern_key, salsa, CrateId};
9use ra_prof::profile; 9use ra_prof::profile;
10use rustc_hash::FxHashSet;
11 10
12use crate::{db::HirDatabase, method_resolution::TyFingerprint, DebruijnIndex}; 11use crate::{db::HirDatabase, DebruijnIndex};
13 12
14use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk}; 13use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk};
15 14
@@ -38,34 +37,6 @@ fn create_chalk_solver() -> chalk_solve::Solver<Interner> {
38 solver_choice.into_solver() 37 solver_choice.into_solver()
39} 38}
40 39
41/// Collects impls for the given trait in the whole dependency tree of `krate`.
42pub(crate) fn impls_for_trait_query(
43 db: &dyn HirDatabase,
44 krate: CrateId,
45 trait_: TraitId,
46 self_ty_fp: Option<TyFingerprint>,
47) -> Arc<[ImplId]> {
48 // FIXME: We could be a lot smarter here - because of the orphan rules and
49 // the fact that the trait and the self type need to be in the dependency
50 // tree of a crate somewhere for an impl to exist, we could skip looking in
51 // a lot of crates completely
52 let mut impls = FxHashSet::default();
53 // We call the query recursively here. On the one hand, this means we can
54 // reuse results from queries for different crates; on the other hand, this
55 // will only ever get called for a few crates near the root of the tree (the
56 // ones the user is editing), so this may actually be a waste of memory. I'm
57 // doing it like this mainly for simplicity for now.
58 for dep in &db.crate_graph()[krate].dependencies {
59 impls.extend(db.impls_for_trait(dep.crate_id, trait_, self_ty_fp).iter());
60 }
61 let crate_impl_defs = db.impls_in_crate(krate);
62 match self_ty_fp {
63 Some(fp) => impls.extend(crate_impl_defs.lookup_impl_defs_for_trait_and_ty(trait_, fp)),
64 None => impls.extend(crate_impl_defs.lookup_impl_defs_for_trait(trait_)),
65 }
66 impls.into_iter().collect()
67}
68
69/// A set of clauses that we assume to be true. E.g. if we are inside this function: 40/// A set of clauses that we assume to be true. E.g. if we are inside this function:
70/// ```rust 41/// ```rust
71/// fn foo<T: Default>(t: T) {} 42/// fn foo<T: Default>(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<Interner> for ChalkContext<'a> {
74 // Note: Since we're using impls_for_trait, only impls where the trait 74 // Note: Since we're using impls_for_trait, only impls where the trait
75 // can be resolved should ever reach Chalk. `impl_datum` relies on that 75 // can be resolved should ever reach Chalk. `impl_datum` relies on that
76 // and will panic if the trait can't be resolved. 76 // and will panic if the trait can't be resolved.
77 let mut result: Vec<_> = self 77 let in_deps = self.db.impls_from_deps(self.krate);
78 .db 78 let in_self = self.db.impls_in_crate(self.krate);
79 .impls_for_trait(self.krate, trait_, self_ty_fp) 79 let impl_maps = [in_deps, in_self];
80 .iter() 80
81 .copied() 81 let id_to_chalk = |id: hir_def::ImplId| Impl::ImplDef(id).to_chalk(self.db);
82 .map(Impl::ImplDef) 82
83 .map(|impl_| impl_.to_chalk(self.db)) 83 let mut result: Vec<_> = match self_ty_fp {
84 .collect(); 84 Some(fp) => impl_maps
85 .iter()
86 .flat_map(|crate_impl_defs| {
87 crate_impl_defs.lookup_impl_defs_for_trait_and_ty(trait_, fp).map(id_to_chalk)
88 })
89 .collect(),
90 None => impl_maps
91 .iter()
92 .flat_map(|crate_impl_defs| {
93 crate_impl_defs.lookup_impl_defs_for_trait(trait_).map(id_to_chalk)
94 })
95 .collect(),
96 };
85 97
86 let arg: Option<Ty> = 98 let arg: Option<Ty> =
87 parameters.get(1).map(|p| from_chalk(self.db, p.assert_ty_ref(&Interner).clone())); 99 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..98993d571 100644
--- a/crates/ra_ide_db/src/change.rs
+++ b/crates/ra_ide_db/src/change.rs
@@ -283,7 +283,7 @@ impl RootDatabase {
283 hir::db::GenericPredicatesQuery 283 hir::db::GenericPredicatesQuery
284 hir::db::GenericDefaultsQuery 284 hir::db::GenericDefaultsQuery
285 hir::db::ImplsInCrateQuery 285 hir::db::ImplsInCrateQuery
286 hir::db::ImplsForTraitQuery 286 hir::db::ImplsFromDepsQuery
287 hir::db::InternTypeCtorQuery 287 hir::db::InternTypeCtorQuery
288 hir::db::InternTypeParamIdQuery 288 hir::db::InternTypeParamIdQuery
289 hir::db::InternChalkImplQuery 289 hir::db::InternChalkImplQuery