1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

use std::{fmt::Debug, hash::Hash, marker::PhantomData};

use auto_impl::auto_impl;
use swc_common::collections::AHashSet;
use swc_fast_graph::digraph::FastDiGraphMap;

#[auto_impl(&, Box, Rc, Arc)]
pub trait DepGraph {
    type ModuleId: Debug + Copy + Eq + Hash + Ord;

    fn deps_of(&self, module_id: Self::ModuleId) -> Vec<Self::ModuleId>;
}

/// Utility to detect cycles in a dependency graph.
pub struct GraphAnalyzer<G>
where
    G: DepGraph,
{
    /// `(src, dst)`
    tracked: AHashSet<(G::ModuleId, G::ModuleId)>,
    dep_graph: G,
    data: GraphResult<G>,
}

impl<G> GraphAnalyzer<G>
where
    G: DepGraph,
{
    pub fn new(dep_graph: G) -> Self {
        Self {
            dep_graph,
            data: GraphResult {
                all: Default::default(),
                graph: Default::default(),
                cycles: Default::default(),
                _marker: Default::default(),
            },
            tracked: Default::default(),
        }
    }

    pub fn load(&mut self, entry: G::ModuleId) {
        self.add_to_graph(
            entry,
            &mut vec![entry],
            &mut State {
                visited: Default::default(),
            },
        );
    }

    fn add_to_graph(
        &mut self,
        module_id: G::ModuleId,
        path: &mut Vec<G::ModuleId>,
        state: &mut State<G::ModuleId>,
    ) {
        let visited = state.visited.contains(&module_id);
        // dbg!(visited);
        // dbg!(&path);
        let cycle_rpos = if visited {
            path.iter().rposition(|v| *v == module_id)
        } else {
            None
        };

        if let Some(rpos) = cycle_rpos {
            let cycle = path[rpos..].to_vec();
            tracing::debug!("Found cycle: {:?}", cycle);
            self.data.cycles.push(cycle);
        }

        let prev_last = *path.last().unwrap();
        // Prevent infinite recursion.
        if !self.tracked.insert((prev_last, module_id)) {
            return;
        }

        path.push(module_id);

        if !visited {
            state.visited.push(module_id);
        }
        if !self.data.all.contains(&module_id) {
            self.data.all.push(module_id);
        }
        self.data.graph.add_node(module_id);

        for dep_module_id in self.dep_graph.deps_of(module_id) {
            tracing::debug!("Dep: {:?} -> {:?}", module_id, dep_module_id);

            self.data.graph.add_edge(module_id, dep_module_id, ());

            self.add_to_graph(dep_module_id, path, state);
        }

        let res = path.pop();
        debug_assert_eq!(res, Some(module_id));
    }

    pub fn into_result(self) -> GraphResult<G> {
        self.data
    }
}

struct State<I> {
    visited: Vec<I>,
}

pub struct GraphResult<G>
where
    G: DepGraph,
{
    pub all: Vec<G::ModuleId>,
    pub graph: FastDiGraphMap<G::ModuleId, ()>,
    pub cycles: Vec<Vec<G::ModuleId>>,

    _marker: PhantomData<G>,
}