code_split_core/
cycles.rs

1use crate::graph::{CycleGroup, CycleKind, Graph};
2use crate::snapshot::PluginGraphs;
3use std::collections::HashMap;
4
5/// Detect SCCs in every projected graph and annotate nodes + the graph's
6/// `cycles` field in-place.
7pub fn annotate_all_cycles(graphs: &mut PluginGraphs) {
8    annotate_graph_cycles(&mut graphs.modules);
9    annotate_graph_cycles(&mut graphs.files);
10    annotate_graph_cycles(&mut graphs.functions);
11}
12
13fn annotate_graph_cycles(graph: &mut Graph) {
14    let n = graph.nodes.len();
15    if n == 0 {
16        return;
17    }
18
19    // Build index map NodeId → usize.
20    let id_to_idx: HashMap<&str, usize> = graph
21        .nodes
22        .iter()
23        .enumerate()
24        .map(|(i, node)| (node.id.as_str(), i))
25        .collect();
26
27    // Adjacency list over ALL edge kinds (contains, uses, reexports, calls).
28    // We deliberately include `contains` edges so that the Rust-specific
29    // test-embed pattern (parent --contains--> tests --uses--> parent) is
30    // visible as a cycle and can be classified correctly.
31    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
32    for edge in &graph.edges {
33        if let (Some(&fi), Some(&ti)) = (
34            id_to_idx.get(edge.from.as_str()),
35            id_to_idx.get(edge.to.as_str()),
36        ) && fi != ti
37        {
38            adj[fi].push(ti);
39        }
40    }
41
42    let sccs = kosaraju_sccs(n, &adj);
43
44    let mut node_kind: Vec<Option<CycleKind>> = vec![None; n];
45    let mut cycle_groups: Vec<CycleGroup> = Vec::new();
46
47    for scc in &sccs {
48        if scc.len() < 2 {
49            continue;
50        }
51        let kind = classify_scc(scc, graph);
52        for &idx in scc {
53            node_kind[idx] = Some(kind.clone());
54        }
55        cycle_groups.push(CycleGroup {
56            kind,
57            nodes: scc.iter().map(|&i| graph.nodes[i].id.clone()).collect(),
58        });
59    }
60
61    for (i, node) in graph.nodes.iter_mut().enumerate() {
62        node.cycle_kind = node_kind[i].clone();
63    }
64    graph.cycles = cycle_groups;
65}
66
67fn classify_scc(scc: &[usize], graph: &Graph) -> CycleKind {
68    if scc.iter().any(|&i| is_test_node(graph, i)) {
69        return CycleKind::TestEmbed;
70    }
71    if scc.len() == 2 {
72        CycleKind::Mutual
73    } else {
74        CycleKind::Chain
75    }
76}
77
78fn is_test_node(graph: &Graph, idx: usize) -> bool {
79    let node = &graph.nodes[idx];
80    let name = node.name.to_ascii_lowercase();
81    // Common Rust test module names
82    if matches!(name.as_str(), "tests" | "test" | "benches" | "bench") {
83        return true;
84    }
85    if name.ends_with("_tests") || name.ends_with("_test") || name.ends_with("_bench") {
86        return true;
87    }
88    // ID path segments — catches `::tests`, `::test::`, etc.
89    let id = &node.id;
90    id.contains("::tests") || id.contains("::test::") || id.ends_with("::test")
91}
92
93// ---------------------------------------------------------------------------
94// Kosaraju's SCC (iterative, O(V+E))
95// ---------------------------------------------------------------------------
96
97fn kosaraju_sccs(n: usize, adj: &[Vec<usize>]) -> Vec<Vec<usize>> {
98    // Pass 1: DFS on the original graph, collect finish order.
99    let mut visited = vec![false; n];
100    let mut finish_order = Vec::with_capacity(n);
101    for i in 0..n {
102        if !visited[i] {
103            dfs_finish(i, adj, &mut visited, &mut finish_order);
104        }
105    }
106
107    // Build transposed adjacency list.
108    let mut radj: Vec<Vec<usize>> = vec![Vec::new(); n];
109    for (u, neighbors) in adj.iter().enumerate() {
110        for &v in neighbors {
111            radj[v].push(u);
112        }
113    }
114
115    // Pass 2: DFS on the transposed graph in reverse finish order.
116    let mut visited2 = vec![false; n];
117    let mut sccs: Vec<Vec<usize>> = Vec::new();
118    for &start in finish_order.iter().rev() {
119        if !visited2[start] {
120            let mut scc = Vec::new();
121            dfs_collect(start, &radj, &mut visited2, &mut scc);
122            sccs.push(scc);
123        }
124    }
125    sccs
126}
127
128fn dfs_finish(start: usize, adj: &[Vec<usize>], visited: &mut [bool], order: &mut Vec<usize>) {
129    // Iterative DFS; (node, next_neighbor_index) on the call stack.
130    let mut stack: Vec<(usize, usize)> = vec![(start, 0)];
131    visited[start] = true;
132    while let Some((u, ni)) = stack.last_mut() {
133        let u = *u;
134        if *ni < adj[u].len() {
135            let v = adj[u][*ni];
136            *ni += 1;
137            if !visited[v] {
138                visited[v] = true;
139                stack.push((v, 0));
140            }
141        } else {
142            stack.pop();
143            order.push(u);
144        }
145    }
146}
147
148fn dfs_collect(start: usize, adj: &[Vec<usize>], visited: &mut [bool], scc: &mut Vec<usize>) {
149    let mut stack = vec![start];
150    visited[start] = true;
151    while let Some(u) = stack.pop() {
152        scc.push(u);
153        for &v in &adj[u] {
154            if !visited[v] {
155                visited[v] = true;
156                stack.push(v);
157            }
158        }
159    }
160}
code_split_core/cycles.rs

code_split_core/
cycles.rs
