Merge #5175

5175: More memory-efficient impl collection r=matklad a=jonas-schievink

This saves roughly 90 MB in `ImplsFromDepsQuery`, which used to copy the list of all impls from libcore into *every* crate in the graph. It also stops collecting inherent impls from dependencies entirely, as those can only be located within the crate defining the self type.

Co-authored-by: Jonas Schievink <[email protected]>

8 files changed, 148 insertions, 128 deletions

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<Item = CrateId> + '_ {
+        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<CrateId> {
         let (&crate_id, _) =
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<ImplDef> {
-        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<ImplDef> {
-        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<TypeRef> {
@@ -1303,10 +1305,10 @@ impl Type {
         mut callback: impl FnMut(AssocItem) -> Option<T>,
     ) -> Option<T> {
         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<dyn DefDatabase> {
     #[salsa::invoke(crate::lower::generic_defaults_query)]
     fn generic_defaults(&self, def: GenericDefId) -> Arc<[Binders<Ty>]>;
 
-    #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_in_crate_query)]
-    fn impls_in_crate(&self, krate: CrateId) -> Arc<CrateImplDefs>;
+    #[salsa::invoke(InherentImpls::inherent_impls_in_crate_query)]
+    fn inherent_impls_in_crate(&self, krate: CrateId) -> Arc<InherentImpls>;
 
-    #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_from_deps_query)]
-    fn impls_from_deps(&self, krate: CrateId) -> Arc<CrateImplDefs>;
+    #[salsa::invoke(TraitImpls::trait_impls_in_crate_query)]
+    fn trait_impls_in_crate(&self, krate: CrateId) -> Arc<TraitImpls>;
+
+    #[salsa::invoke(TraitImpls::trait_impls_in_deps_query)]
+    fn trait_impls_in_deps(&self, krate: CrateId) -> Arc<TraitImpls>;
 
     // 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 c19519cf1..5dbabd12b 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -38,136 +38,131 @@ impl TyFingerprint {
     }
 }
 
-/// A queryable and mergeable collection of impls.
-#[derive(Debug, PartialEq, Eq)]
-pub struct CrateImplDefs {
-    inherent_impls: FxHashMap<TyFingerprint, Vec<ImplId>>,
-    impls_by_trait: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>,
+/// Trait impls defined or available in some crate.
+#[derive(Debug, Eq, PartialEq)]
+pub struct TraitImpls {
+    // If the `Option<TyFingerprint>` is `None`, the impl may apply to any self type.
+    map: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>,
 }
 
-impl CrateImplDefs {
-    pub(crate) fn impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<CrateImplDefs> {
-        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<Self> {
+        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<CrateImplDefs> {
-        let _p = profile("impls_from_deps_query");
+    pub(crate) fn trait_impls_in_deps_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
+        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 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.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);
-            vec.sort();
-            vec.dedup();
-        }
-
-        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);
-                vec.sort();
-                vec.dedup();
             }
         }
     }
 
-    pub fn lookup_impl_defs(&self, ty: &Ty) -> impl Iterator<Item = ImplId> + '_ {
-        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<Item = ImplId> + '_ {
-        self.impls_by_trait
-            .get(&tr)
+    /// Queries all impls of the given trait.
+    pub fn for_trait(&self, trait_: TraitId) -> impl Iterator<Item = ImplId> + '_ {
+        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<Item = ImplId> + '_ {
-        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<Item = ImplId> + '_ {
+        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<TyFingerprint, Vec<ImplId>>,
+}
+
+impl InherentImpls {
+    pub(crate) fn inherent_impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<Self> {
+        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<Item = ImplId> + '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<Item = ImplId> + '_ {
+        self.map.values().flat_map(|v| v.iter().copied())
     }
 }
 
@@ -524,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<Interner> 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<Interner> 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