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/src')

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


From 75fafd6fcc010c71d770d19bea4b744b92c5267b Mon Sep 17 00:00:00 2001
From: Lukas Wirth <lukastw97@gmail.com>
Date: Tue, 16 Mar 2021 15:28:02 +0100
Subject: Add new_source_root meta to test fixtures

---
 crates/base_db/src/fixture.rs | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

(limited to 'crates/base_db/src')

diff --git a/crates/base_db/src/fixture.rs b/crates/base_db/src/fixture.rs
index 5c9824814..cad6866aa 100644
--- a/crates/base_db/src/fixture.rs
+++ b/crates/base_db/src/fixture.rs
@@ -57,7 +57,7 @@
 //! fn insert_source_code_here() {}
 //! "
 //! ```
-use std::{str::FromStr, sync::Arc};
+use std::{mem, str::FromStr, sync::Arc};
 
 use cfg::CfgOptions;
 use rustc_hash::FxHashMap;
@@ -148,6 +148,7 @@ impl ChangeFixture {
         let mut file_set = FileSet::default();
         let source_root_prefix = "/".to_string();
         let mut file_id = FileId(0);
+        let mut roots = Vec::new();
 
         let mut file_position = None;
 
@@ -168,6 +169,10 @@ impl ChangeFixture {
             let meta = FileMeta::from(entry);
             assert!(meta.path.starts_with(&source_root_prefix));
 
+            if meta.introduce_new_source_root {
+                roots.push(SourceRoot::new_local(mem::take(&mut file_set)));
+            }
+
             if let Some(krate) = meta.krate {
                 let crate_name = CrateName::normalize_dashes(&krate);
                 let crate_id = crate_graph.add_crate_root(
@@ -215,7 +220,8 @@ impl ChangeFixture {
             }
         }
 
-        change.set_roots(vec![SourceRoot::new_local(file_set)]);
+        roots.push(SourceRoot::new_local(mem::take(&mut file_set)));
+        change.set_roots(roots);
         change.set_crate_graph(crate_graph);
 
         ChangeFixture { file_position, files, change }
@@ -229,6 +235,7 @@ struct FileMeta {
     cfg: CfgOptions,
     edition: Edition,
     env: Env,
+    introduce_new_source_root: bool,
 }
 
 impl From<Fixture> for FileMeta {
@@ -247,6 +254,7 @@ impl From<Fixture> for FileMeta {
                 .as_ref()
                 .map_or(Edition::Edition2018, |v| Edition::from_str(&v).unwrap()),
             env: f.env.into_iter().collect(),
+            introduce_new_source_root: f.introduce_new_source_root,
         }
     }
 }
-- 
cgit v1.2.3


From bebee2106de7bbd20f54d7f55d5c56dba0d636b6 Mon Sep 17 00:00:00 2001
From: Lukas Wirth <lukastw97@gmail.com>
Date: Tue, 16 Mar 2021 15:53:34 +0100
Subject: Don't repeat work in transitive_reverse_dependencies

---
 crates/base_db/src/input.rs | 21 ++++++++++-----------
 1 file changed, 10 insertions(+), 11 deletions(-)

(limited to 'crates/base_db/src')

diff --git a/crates/base_db/src/input.rs b/crates/base_db/src/input.rs
index 06f1c14f5..d0def2181 100644
--- a/crates/base_db/src/input.rs
+++ b/crates/base_db/src/input.rs
@@ -281,24 +281,23 @@ impl CrateGraph {
     ) -> impl Iterator<Item = CrateId> + '_ {
         let mut worklist = vec![of];
         let mut rev_deps = FxHashSet::default();
-        let mut inverted_graph = FxHashMap::default();
+        let mut inverted_graph = FxHashMap::<_, Vec<_>>::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)
-            })
+            data.dependencies
+                .iter()
+                .for_each(|dep| inverted_graph.entry(dep.crate_id).or_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);
+            if let Some(krate_rev_deps) = inverted_graph.get(&krate) {
+                krate_rev_deps
+                    .iter()
+                    .copied()
+                    .filter(|&rev_dep| rev_deps.insert(rev_dep))
+                    .for_each(|rev_dep| worklist.push(rev_dep));
             }
         }
 
-        rev_deps.remove(&of);
         rev_deps.into_iter()
     }
 
-- 
cgit v1.2.3