From cde7392ec809599e6337d91561971e08c8e06831 Mon Sep 17 00:00:00 2001
From: Jonas Schievink <jonas.schievink@ferrous-systems.com>
Date: Tue, 6 Oct 2020 17:58:03 +0200
Subject: Improve prime_caches and display its progress

---
 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 c330314d4..215ac4b41 100644
--- a/crates/base_db/src/input.rs
+++ b/crates/base_db/src/input.rs
@@ -221,6 +221,34 @@ impl CrateGraph {
         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> {
+        let mut res = Vec::new();
+        let mut visited = FxHashSet::default();
+
+        for krate in self.arena.keys().copied() {
+            go(self, &mut visited, &mut res, krate);
+        }
+
+        return res;
+
+        fn go(
+            graph: &CrateGraph,
+            visited: &mut FxHashSet<CrateId>,
+            res: &mut Vec<CrateId>,
+            source: CrateId,
+        ) {
+            if !visited.insert(source) {
+                return;
+            }
+            for dep in graph[source].dependencies.iter() {
+                go(graph, visited, res, dep.crate_id)
+            }
+            res.push(source)
+        }
+    }
+
     // 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, _) =
-- 
cgit v1.2.3