diff options
Diffstat (limited to 'crates/base_db/src/input.rs')
-rw-r--r-- | crates/base_db/src/input.rs | 27 |
1 files changed, 27 insertions, 0 deletions
diff --git a/crates/base_db/src/input.rs b/crates/base_db/src/input.rs index b5f7e4200..d0def2181 100644 --- a/crates/base_db/src/input.rs +++ b/crates/base_db/src/input.rs | |||
@@ -274,6 +274,33 @@ impl CrateGraph { | |||
274 | deps.into_iter() | 274 | deps.into_iter() |
275 | } | 275 | } |
276 | 276 | ||
277 | /// Returns an iterator over all transitive reverse dependencies of the given crate. | ||
278 | pub fn transitive_reverse_dependencies( | ||
279 | &self, | ||
280 | of: CrateId, | ||
281 | ) -> impl Iterator<Item = CrateId> + '_ { | ||
282 | let mut worklist = vec![of]; | ||
283 | let mut rev_deps = FxHashSet::default(); | ||
284 | let mut inverted_graph = FxHashMap::<_, Vec<_>>::default(); | ||
285 | self.arena.iter().for_each(|(&krate, data)| { | ||
286 | data.dependencies | ||
287 | .iter() | ||
288 | .for_each(|dep| inverted_graph.entry(dep.crate_id).or_default().push(krate)) | ||
289 | }); | ||
290 | |||
291 | while let Some(krate) = worklist.pop() { | ||
292 | if let Some(krate_rev_deps) = inverted_graph.get(&krate) { | ||
293 | krate_rev_deps | ||
294 | .iter() | ||
295 | .copied() | ||
296 | .filter(|&rev_dep| rev_deps.insert(rev_dep)) | ||
297 | .for_each(|rev_dep| worklist.push(rev_dep)); | ||
298 | } | ||
299 | } | ||
300 | |||
301 | rev_deps.into_iter() | ||
302 | } | ||
303 | |||
277 | /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate | 304 | /// Returns all crates in the graph, sorted in topological order (ie. dependencies of a crate |
278 | /// come before the crate itself). | 305 | /// come before the crate itself). |
279 | pub fn crates_in_topological_order(&self) -> Vec<CrateId> { | 306 | pub fn crates_in_topological_order(&self) -> Vec<CrateId> { |