rapx/analysis/graphs/
scc.rs

1use rustc_data_structures::fx::FxHashSet;
2use std::cmp;
3
4#[derive(Debug, Clone, Eq, Hash, PartialEq)]
5pub struct SccExit {
6    pub exit: usize,
7    pub to: usize,
8}
9
10impl SccExit {
11    pub fn new(exit: usize, to: usize) -> Self {
12        SccExit { exit, to }
13    }
14}
15
16#[derive(Debug, Clone)]
17pub struct SccInfo {
18    pub enter: usize,                // In Rust CFG, each scc has exactly one enter.
19    pub nodes: FxHashSet<usize>,     // Other nodes of the scc except the enter.
20    pub exits: FxHashSet<SccExit>,   // Exit information of the scc.
21    pub backnodes: FxHashSet<usize>, // The nodes with a backedge.
22}
23
24impl SccInfo {
25    pub fn new(enter: usize) -> Self {
26        SccInfo {
27            enter,
28            nodes: FxHashSet::default(),
29            exits: FxHashSet::default(),
30            backnodes: FxHashSet::default(),
31        }
32    }
33}
34
35pub trait Scc {
36    fn find_scc(&mut self) {
37        let mut stack = Vec::new();
38        let mut instack = FxHashSet::<usize>::default(); // for fast query only
39        let mut dfn = vec![0; self.get_size()];
40        let mut low = vec![0; self.get_size()];
41        let mut time = 0;
42        self.tarjan(0, &mut stack, &mut instack, &mut dfn, &mut low, &mut time);
43    }
44
45    fn on_scc_found(&mut self, root: usize, scc_components: &[usize]); // callback 
46    fn get_next(&mut self, root: usize) -> FxHashSet<usize>; //
47    fn get_size(&mut self) -> usize; //
48    //
49    fn tarjan(
50        &mut self,
51        index: usize,
52        stack: &mut Vec<usize>,
53        instack: &mut FxHashSet<usize>,
54        dfn: &mut Vec<usize>,
55        low: &mut Vec<usize>,
56        time: &mut usize,
57    ) {
58        dfn[index] = *time;
59        low[index] = *time;
60        *time += 1;
61        stack.push(index);
62        instack.insert(index);
63        let nexts = self.get_next(index);
64        for next in nexts {
65            if dfn[next] == 0 {
66                self.tarjan(next, stack, instack, dfn, low, time);
67                low[index] = cmp::min(low[index], low[next]);
68            } else if instack.contains(&next) {
69                low[index] = cmp::min(low[index], dfn[next]);
70            }
71        }
72        if dfn[index] == low[index] {
73            let mut component = vec![index];
74            while let Some(top) = stack.pop() {
75                instack.remove(&top);
76                if top == index {
77                    break;
78                }
79                component.push(top);
80            }
81            self.on_scc_found(index, &component);
82        }
83    }
84}
85
86#[derive(Debug)]
87pub struct SccTree {
88    pub scc: SccInfo,
89    pub children: Vec<SccTree>,
90}
rapx/analysis/graphs/scc.rs

rapx/analysis/graphs/
scc.rs
