swc_graph_analyzer/
lib.rs

1use std::{fmt::Debug, hash::Hash, marker::PhantomData};
2
3use auto_impl::auto_impl;
4use rustc_hash::FxHashSet;
5use swc_fast_graph::digraph::FastDiGraphMap;
6
7#[auto_impl(&, Box, Rc, Arc)]
8pub trait DepGraph {
9    type ModuleId: Debug + Copy + Eq + Hash + Ord;
10
11    fn deps_of(&self, module_id: Self::ModuleId) -> Vec<Self::ModuleId>;
12}
13
14/// Utility to detect cycles in a dependency graph.
15pub struct GraphAnalyzer<G>
16where
17    G: DepGraph,
18{
19    /// `(src, dst)`
20    tracked: FxHashSet<(G::ModuleId, G::ModuleId)>,
21    dep_graph: G,
22    data: GraphResult<G>,
23}
24
25impl<G> GraphAnalyzer<G>
26where
27    G: DepGraph,
28{
29    pub fn new(dep_graph: G) -> Self {
30        Self {
31            dep_graph,
32            data: GraphResult {
33                all: Default::default(),
34                graph: Default::default(),
35                cycles: Default::default(),
36                _marker: Default::default(),
37            },
38            tracked: Default::default(),
39        }
40    }
41
42    pub fn load(&mut self, entry: G::ModuleId) {
43        self.add_to_graph(
44            entry,
45            &mut vec![entry],
46            &mut State {
47                visited: Default::default(),
48            },
49        );
50    }
51
52    fn add_to_graph(
53        &mut self,
54        module_id: G::ModuleId,
55        path: &mut Vec<G::ModuleId>,
56        state: &mut State<G::ModuleId>,
57    ) {
58        let visited = state.visited.contains(&module_id);
59        // dbg!(visited);
60        // dbg!(&path);
61        let cycle_rpos = if visited {
62            path.iter().rposition(|v| *v == module_id)
63        } else {
64            None
65        };
66
67        if let Some(rpos) = cycle_rpos {
68            let cycle = path[rpos..].to_vec();
69            tracing::debug!("Found cycle: {:?}", cycle);
70            self.data.cycles.push(cycle);
71        }
72
73        let prev_last = *path.last().unwrap();
74        // Prevent infinite recursion.
75        if !self.tracked.insert((prev_last, module_id)) {
76            return;
77        }
78
79        path.push(module_id);
80
81        if !visited {
82            state.visited.push(module_id);
83        }
84        if !self.data.all.contains(&module_id) {
85            self.data.all.push(module_id);
86        }
87        self.data.graph.add_node(module_id);
88
89        for dep_module_id in self.dep_graph.deps_of(module_id) {
90            tracing::debug!("Dep: {:?} -> {:?}", module_id, dep_module_id);
91
92            self.data.graph.add_edge(module_id, dep_module_id, ());
93
94            self.add_to_graph(dep_module_id, path, state);
95        }
96
97        let res = path.pop();
98        debug_assert_eq!(res, Some(module_id));
99    }
100
101    pub fn into_result(self) -> GraphResult<G> {
102        self.data
103    }
104}
105
106struct State<I> {
107    visited: Vec<I>,
108}
109
110pub struct GraphResult<G>
111where
112    G: DepGraph,
113{
114    pub all: Vec<G::ModuleId>,
115    pub graph: FastDiGraphMap<G::ModuleId, ()>,
116    pub cycles: Vec<Vec<G::ModuleId>>,
117
118    _marker: PhantomData<G>,
119}
swc_graph_analyzer/lib.rs

swc_graph_analyzer/
lib.rs
