aboutsummaryrefslogtreecommitdiff
path: root/crates/base_db/src/input.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/base_db/src/input.rs')
-rw-r--r--crates/base_db/src/input.rs28
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 {
221 deps.into_iter() 221 deps.into_iter()
222 } 222 }
223 223
224 /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate
225 /// come before the crate itself).
226 pub fn crates_in_topological_order(&self) -> Vec<CrateId> {
227 let mut res = Vec::new();
228 let mut visited = FxHashSet::default();
229
230 for krate in self.arena.keys().copied() {
231 go(self, &mut visited, &mut res, krate);
232 }
233
234 return res;
235
236 fn go(
237 graph: &CrateGraph,
238 visited: &mut FxHashSet<CrateId>,
239 res: &mut Vec<CrateId>,
240 source: CrateId,
241 ) {
242 if !visited.insert(source) {
243 return;
244 }
245 for dep in graph[source].dependencies.iter() {
246 go(graph, visited, res, dep.crate_id)
247 }
248 res.push(source)
249 }
250 }
251
224 // FIXME: this only finds one crate with the given root; we could have multiple 252 // FIXME: this only finds one crate with the given root; we could have multiple
225 pub fn crate_id_for_crate_root(&self, file_id: FileId) -> Option<CrateId> { 253 pub fn crate_id_for_crate_root(&self, file_id: FileId) -> Option<CrateId> {
226 let (&crate_id, _) = 254 let (&crate_id, _) =