swc_graph_analyzer/
lib.rs

1use std::{fmt::Debug, hash::Hash, marker::PhantomData};
2
3use auto_impl::auto_impl;
4use petgraph::{prelude::GraphMap, Directed};
5use rustc_hash::{FxBuildHasher, FxHashSet};
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            #[cfg(debug_assertions)]
70            tracing::debug!("Found cycle: {:?}", cycle);
71            self.data.cycles.push(cycle);
72        }
73
74        let prev_last = *path.last().unwrap();
75        // Prevent infinite recursion.
76        if !self.tracked.insert((prev_last, module_id)) {
77            return;
78        }
79
80        path.push(module_id);
81
82        if !visited {
83            state.visited.push(module_id);
84        }
85        if !self.data.all.contains(&module_id) {
86            self.data.all.push(module_id);
87        }
88        self.data.graph.add_node(module_id);
89
90        for dep_module_id in self.dep_graph.deps_of(module_id) {
91            #[cfg(debug_assertions)]
92            tracing::debug!("Dep: {:?} -> {:?}", module_id, dep_module_id);
93
94            self.data.graph.add_edge(module_id, dep_module_id, ());
95
96            self.add_to_graph(dep_module_id, path, state);
97        }
98
99        let res = path.pop();
100        debug_assert_eq!(res, Some(module_id));
101    }
102
103    pub fn into_result(self) -> GraphResult<G> {
104        self.data
105    }
106}
107
108struct State<I> {
109    visited: Vec<I>,
110}
111
112pub struct GraphResult<G>
113where
114    G: DepGraph,
115{
116    pub all: Vec<G::ModuleId>,
117    pub graph: GraphMap<G::ModuleId, (), Directed, FxBuildHasher>,
118    pub cycles: Vec<Vec<G::ModuleId>>,
119
120    _marker: PhantomData<G>,
121}
swc_graph_analyzer/lib.rs

swc_graph_analyzer/
lib.rs
