From e97cd709cd91ccfafbd45bab8b2bf01f3ddf6a04 Mon Sep 17 00:00:00 2001
From: Lukas Wirth <lukastw97@gmail.com>
Date: Mon, 15 Mar 2021 17:43:46 +0100
Subject: Implement Crate::transitive_reverse_dependencies

---
 crates/base_db/src/input.rs | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)

(limited to 'crates/base_db')

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> {
-- 
cgit v1.2.3