fob_graph/memory/
traversal.rs

1//! Traversal methods for ModuleGraph.
2
3use std::collections::VecDeque;
4
5use rustc_hash::FxHashSet as HashSet;
6
7use super::super::ModuleId;
8use super::graph::ModuleGraph;
9use crate::Result;
10
11impl ModuleGraph {
12    /// Returns true if `from` depends on `to` (directly or transitively).
13    pub fn depends_on(&self, from: &ModuleId, to: &ModuleId) -> Result<bool> {
14        if from == to {
15            return Ok(true);
16        }
17
18        let inner = self.inner.read();
19        let mut visited = HashSet::default();
20        let mut queue = VecDeque::new();
21        queue.push_back(from.clone());
22
23        while let Some(current) = queue.pop_front() {
24            if !visited.insert(current.clone()) {
25                continue;
26            }
27
28            if let Some(deps) = inner.dependencies.get(&current) {
29                for dep in deps {
30                    if dep == to {
31                        return Ok(true);
32                    }
33                    queue.push_back(dep.clone());
34                }
35            }
36        }
37
38        Ok(false)
39    }
40
41    /// Collect transitive dependencies of a module.
42    pub fn transitive_dependencies(&self, id: &ModuleId) -> Result<HashSet<ModuleId>> {
43        let mut visited = HashSet::default();
44        let mut queue = VecDeque::new();
45        queue.push_back(id.clone());
46
47        while let Some(current) = queue.pop_front() {
48            if !visited.insert(current.clone()) {
49                continue;
50            }
51
52            let deps = self.dependencies(&current)?;
53            for next in deps {
54                if !visited.contains(&next) {
55                    queue.push_back(next);
56                }
57            }
58        }
59
60        visited.remove(id);
61        Ok(visited)
62    }
63}
fob_graph/memory/traversal.rs

fob_graph/memory/
traversal.rs
