swc_bundler/modules/sort/
graph.rs

1use std::{collections::VecDeque, iter::repeat};
2
3use petgraph::{
4    prelude::GraphMap,
5    Directed,
6    EdgeDirection::{self, Incoming, Outgoing},
7};
8use rustc_hash::{FxBuildHasher, FxHashSet};
9
10/// Is dependency between nodes hard?
11#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
12pub(super) enum Required {
13    /// Required to evaluate
14    Always,
15
16    /// Maybe required to evaluate
17    Maybe,
18}
19
20/// Used to debug petgraph.
21#[derive(Debug, Default)]
22pub(super) struct StmtDepGraph {
23    inner: GraphMap<usize, Required, Directed, FxBuildHasher>,
24    /// Read-optimized hashset which contains all direct dependencies and
25    /// transitive dependencies.
26    paths: Vec<FxHashSet<usize>>,
27}
28
29impl StmtDepGraph {
30    pub fn node_count(&self) -> usize {
31        self.inner.node_count()
32    }
33
34    pub fn add_node(&mut self, node: usize) {
35        self.inner.add_node(node);
36    }
37
38    pub fn remove_node(&mut self, node: usize) {
39        self.inner.add_node(node);
40    }
41
42    pub fn add_edge(&mut self, a: usize, b: usize, required: Required) {
43        self.inner.add_edge(a, b, required);
44
45        self.insert_transitives(a, b);
46    }
47
48    fn calc_transitives(&self, id: usize, dir: EdgeDirection) -> FxHashSet<usize> {
49        let mut set = FxHashSet::default();
50
51        let mut queue = VecDeque::default();
52        queue.push_front(id);
53
54        while let Some(id) = queue.pop_front() {
55            // Already processed
56            if !set.insert(id) {
57                continue;
58            }
59
60            for transitive in self.inner.neighbors_directed(id, dir) {
61                queue.push_back(transitive);
62            }
63        }
64
65        set
66    }
67
68    fn insert_transitives(&mut self, from: usize, to: usize) {
69        if self.paths.len() <= from {
70            self.paths
71                .extend(repeat(Default::default()).take(from + 1 - self.paths.len()))
72        }
73        if !self.paths[from].insert(to) {
74            return;
75        }
76
77        for transitive in self.calc_transitives(to, Outgoing) {
78            if from == transitive {
79                continue;
80            }
81            self.paths[from].insert(transitive);
82        }
83
84        for transitive in self.calc_transitives(from, Incoming) {
85            if to == transitive {
86                continue;
87            }
88
89            self.paths[transitive].insert(to);
90        }
91    }
92
93    pub fn edge_weight(&self, a: usize, b: usize) -> Option<Required> {
94        self.inner.edge_weight(a, b).cloned()
95    }
96
97    pub fn neighbors_directed(
98        &self,
99        start: usize,
100        dir: EdgeDirection,
101    ) -> impl '_ + Iterator<Item = usize> {
102        self.inner.neighbors_directed(start, dir)
103    }
104
105    pub fn has_a_path(&self, from: usize, to: usize) -> bool {
106        match self.paths.get(from) {
107            Some(ps) => ps.contains(&to),
108            None => false,
109        }
110    }
111}
swc_bundler/modules/sort/graph.rs

swc_bundler/modules/sort/
graph.rs
