Merge #6153

6153: Improve prime_caches and display its progress r=matklad a=jonas-schievink

It now computes the `CrateDefMap` of all crates, which is generally a reasonable approximation for "IDE features ready". There is still some delay after this finishes, I suspect mostly due to impl collection, which takes a while, but this should be an improvement already.

For more accurate progress reports, this topologically sorts all crates before starting this operation. ~~Because that is also the ordering in which parallelization makes sense (which was previously attempted in https://github.com/rust-analyzer/rust-analyzer/pull/3529), I decided to throw that into the mix as well. It still doesn't provide *that* much of a performance boost, but it does scale beyond the current single-core architecture, and adding it was very easy.~~

~~Unfortunately, as written, this will not tell the user which crate is actually causing slowdowns, since the displayed crate is the last one that was *started*, not the one we are currently *blocked* on, but that seems fairly difficult to implement unless I'm missing something.~~

(I have removed rayon for now since it does not work correctly with cancellation.)

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

1 files changed, 28 insertions, 0 deletions

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, _) =