Implement Crate::transitive_reverse_dependencies

4 files changed, 71 insertions, 5 deletions

diff --git a/crates/base_db/src/input.rs b/crates/base_db/src/input.rs
index b5f7e4200..06f1c14f5 100644
--- a/crates/base_db/src/input.rs
+++ b/crates/base_db/src/input.rs
@@ -274,6 +274,34 @@ impl CrateGraph {
         deps.into_iter()
     }
 
+    /// Returns an iterator over all transitive reverse dependencies of the given crate.
+    pub fn transitive_reverse_dependencies(
+        &self,
+        of: CrateId,
+    ) -> impl Iterator<Item = CrateId> + '_ {
+        let mut worklist = vec![of];
+        let mut rev_deps = FxHashSet::default();
+        let mut inverted_graph = FxHashMap::default();
+        self.arena.iter().for_each(|(&krate, data)| {
+            data.dependencies.iter().for_each(|dep| {
+                inverted_graph.entry(dep.crate_id).or_insert_with(Vec::default).push(krate)
+            })
+        });
+
+        while let Some(krate) = worklist.pop() {
+            if !rev_deps.insert(krate) {
+                continue;
+            }
+
+            if let Some(rev_deps) = inverted_graph.get(&krate) {
+                worklist.extend(rev_deps);
+            }
+        }
+
+        rev_deps.remove(&of);
+        rev_deps.into_iter()
+    }
+
     /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate
     /// come before the crate itself).
     pub fn crates_in_topological_order(&self) -> Vec<CrateId> {
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index c5161dadd..079a5f7b8 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -58,6 +58,7 @@ use hir_ty::{
     InEnvironment, Interner, Obligation, ProjectionPredicate, ProjectionTy, Scalar, Substs, Ty,
     TyDefId, TyKind, TyVariableKind,
 };
+use itertools::Itertools;
 use rustc_hash::FxHashSet;
 use stdx::{format_to, impl_from};
 use syntax::{
@@ -139,7 +140,6 @@ impl Crate {
             .collect()
     }
 
-    // FIXME: add `transitive_reverse_dependencies`.
     pub fn reverse_dependencies(self, db: &dyn HirDatabase) -> Vec<Crate> {
         let crate_graph = db.crate_graph();
         crate_graph
@@ -151,6 +151,14 @@ impl Crate {
             .collect()
     }
 
+    pub fn transitive_reverse_dependencies(self, db: &dyn HirDatabase) -> Vec<Crate> {
+        db.crate_graph()
+            .transitive_reverse_dependencies(self.id)
+            .into_iter()
+            .map(|id| Crate { id })
+            .collect()
+    }
+
     pub fn root_module(self, db: &dyn HirDatabase) -> Module {
         let def_map = db.crate_def_map(self.id);
         Module { id: def_map.module_id(def_map.root()) }
@@ -1497,11 +1505,17 @@ impl Impl {
         };
 
         let mut all = Vec::new();
-        def_crates.into_iter().for_each(|id| {
+        def_crates.iter().for_each(|&id| {
             all.extend(db.inherent_impls_in_crate(id).all_impls().map(Self::from).filter(filter))
         });
         let fp = TyFingerprint::for_impl(&ty.value);
-        for id in db.crate_graph().iter() {
+        for id in def_crates
+            .iter()
+            .flat_map(|&id| Crate { id }.transitive_reverse_dependencies(db))
+            .map(|Crate { id }| id)
+            .chain(def_crates.iter().copied())
+            .unique()
+        {
             match fp {
                 Some(fp) => all.extend(
                     db.trait_impls_in_crate(id).for_self_ty(fp).map(Self::from).filter(filter),
@@ -1516,7 +1530,8 @@ impl Impl {
     pub fn all_for_trait(db: &dyn HirDatabase, trait_: Trait) -> Vec<Impl> {
         let krate = trait_.module(db).krate();
         let mut all = Vec::new();
-        for Crate { id } in krate.reverse_dependencies(db).into_iter().chain(Some(krate)) {
+        for Crate { id } in krate.transitive_reverse_dependencies(db).into_iter().chain(Some(krate))
+        {
             let impls = db.trait_impls_in_crate(id);
             all.extend(impls.for_trait(trait_.id).map(Self::from))
         }
diff --git a/crates/ide/src/references.rs b/crates/ide/src/references.rs
index ec7c7686d..fc85cd0ce 100644
--- a/crates/ide/src/references.rs
+++ b/crates/ide/src/references.rs
@@ -1270,4 +1270,27 @@ fn foo(_: bool) -> bo$0ol { true }
             "#]],
         );
     }
+
+    #[test]
+    fn test_transitive() {
+        check(
+            r#"
+//- /level3/level3.rs crate:level3
+pub struct Fo$0o;
+//- /level2/level2.rs crate:level2 deps:level3
+pub use level3::Foo;
+//- /level1/level1.rs crate:level1 deps:level2
+pub use level2::Foo;
+//- /level0/level0.rs crate:level0 deps:level1
+pub use level1::Foo;
+"#,
+            expect![[r#"
+                Foo Struct FileId(0) 0..15 11..14
+
+                FileId(1) 16..19
+                FileId(2) 16..19
+                FileId(3) 16..19
+            "#]],
+        );
+    }
 }
diff --git a/crates/ide_db/src/search.rs b/crates/ide_db/src/search.rs
index d00a8b6e7..f56221a6c 100644
--- a/crates/ide_db/src/search.rs
+++ b/crates/ide_db/src/search.rs
@@ -260,7 +260,7 @@ impl Definition {
             let mut res = source_root.iter().map(|id| (id, None)).collect::<FxHashMap<_, _>>();
 
             let krate = module.krate();
-            for rev_dep in krate.reverse_dependencies(db) {
+            for rev_dep in krate.transitive_reverse_dependencies(db) {
                 let root_file = rev_dep.root_file(db);
                 let source_root_id = db.file_source_root(root_file);
                 let source_root = db.source_root(source_root_id);