code_ranker_graph/
cycles.rs

1//! Cycle detection over information-flow edges (Kosaraju SCC). Edges count iff
2//! their kind is in `flow_kinds` (derived from `EdgeKindSpec.flow`); structural
3//! kinds like `contains` are excluded, so a `mod foo;` parent/child pair is not
4//! flagged as a false cycle.
5
6use crate::level_graph::CycleGroup;
7use code_ranker_plugin_api::{attrs::AttrValue, graph::Graph};
8use std::collections::HashMap;
9use std::collections::HashSet;
10
11/// Detect SCCs (≥ 2 members) over flow edges, write a `cycle` attribute on each
12/// participating node (`"mutual"` for a 2-node SCC, `"chain"` for 3+), and
13/// return the cycle groups.
14pub fn annotate_cycles(graph: &mut Graph, flow_kinds: &HashSet<String>) -> Vec<CycleGroup> {
15    let n = graph.nodes.len();
16    if n == 0 {
17        return Vec::new();
18    }
19
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    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
28    for edge in &graph.edges {
29        if !flow_kinds.contains(&edge.kind) {
30            continue;
31        }
32        if let (Some(&fi), Some(&ti)) = (
33            id_to_idx.get(edge.source.as_str()),
34            id_to_idx.get(edge.target.as_str()),
35        ) && fi != ti
36        {
37            adj[fi].push(ti);
38        }
39    }
40
41    let sccs = kosaraju_sccs(n, &adj);
42
43    let mut node_kind: Vec<Option<&'static str>> = vec![None; n];
44    let mut groups: Vec<CycleGroup> = Vec::new();
45    for scc in &sccs {
46        if scc.len() < 2 {
47            continue;
48        }
49        // Rust forbids circular dependencies between crates, so an SCC whose
50        // members span more than one crate cannot be a real cycle — it is an
51        // artifact of imprecise path resolution. Drop it.
52        if spans_multiple_crates(scc, graph) {
53            continue;
54        }
55        let kind = classify_scc(scc);
56        for &idx in scc {
57            node_kind[idx] = Some(kind);
58        }
59        groups.push(CycleGroup {
60            kind: kind.to_string(),
61            nodes: scc.iter().map(|&i| graph.nodes[i].id.clone()).collect(),
62        });
63    }
64
65    for (i, node) in graph.nodes.iter_mut().enumerate() {
66        match node_kind[i] {
67            Some(k) => {
68                node.attrs
69                    .insert("cycle".to_string(), AttrValue::Str(k.to_string()));
70            }
71            None => {
72                node.attrs.remove("cycle");
73            }
74        }
75    }
76    groups
77}
78
79/// The crate a node belongs to. Prefers the plugin-provided `crate` attribute
80/// (the precise per-target compilation unit from `cargo metadata`); falls back
81/// to deriving it from the id as everything before the last `/src/` segment for
82/// nodes/plugins that don't set it. Returns `None` when neither is available, so
83/// callers can stay conservative.
84fn crate_of(node: &code_ranker_plugin_api::node::Node) -> Option<&str> {
85    if let Some(AttrValue::Str(c)) = node.attrs.get("crate") {
86        return Some(c.as_str());
87    }
88    node.id.rfind("/src/").map(|i| &node.id[..i])
89}
90
91/// True only when every member has a determinable crate and at least two crates
92/// are present. Unknown-crate nodes make this `false` (conservative: keep the
93/// cycle) so non-crate id schemes (tests, other plugins) are never mis-dropped.
94fn spans_multiple_crates(scc: &[usize], graph: &Graph) -> bool {
95    let mut crates = Vec::with_capacity(scc.len());
96    for &i in scc {
97        match crate_of(&graph.nodes[i]) {
98            Some(c) => crates.push(c),
99            None => return false,
100        }
101    }
102    crates.iter().any(|c| *c != crates[0])
103}
104
105fn classify_scc(scc: &[usize]) -> &'static str {
106    if scc.len() == 2 { "mutual" } else { "chain" }
107}
108
109// ── Kosaraju's SCC (iterative, O(V+E)) ─────────────────────────────────────
110
111fn kosaraju_sccs(n: usize, adj: &[Vec<usize>]) -> Vec<Vec<usize>> {
112    let mut visited = vec![false; n];
113    let mut finish_order = Vec::with_capacity(n);
114    for i in 0..n {
115        if !visited[i] {
116            dfs_finish(i, adj, &mut visited, &mut finish_order);
117        }
118    }
119    let mut radj: Vec<Vec<usize>> = vec![Vec::new(); n];
120    for (u, neighbors) in adj.iter().enumerate() {
121        for &v in neighbors {
122            radj[v].push(u);
123        }
124    }
125    let mut visited2 = vec![false; n];
126    let mut sccs: Vec<Vec<usize>> = Vec::new();
127    for &start in finish_order.iter().rev() {
128        if !visited2[start] {
129            let mut scc = Vec::new();
130            dfs_collect(start, &radj, &mut visited2, &mut scc);
131            sccs.push(scc);
132        }
133    }
134    sccs
135}
136
137fn dfs_finish(start: usize, adj: &[Vec<usize>], visited: &mut [bool], order: &mut Vec<usize>) {
138    let mut stack: Vec<(usize, usize)> = vec![(start, 0)];
139    visited[start] = true;
140    while let Some((u, ni)) = stack.last_mut() {
141        let u = *u;
142        if *ni < adj[u].len() {
143            let v = adj[u][*ni];
144            *ni += 1;
145            if !visited[v] {
146                visited[v] = true;
147                stack.push((v, 0));
148            }
149        } else {
150            stack.pop();
151            order.push(u);
152        }
153    }
154}
155
156fn dfs_collect(start: usize, adj: &[Vec<usize>], visited: &mut [bool], scc: &mut Vec<usize>) {
157    let mut stack = vec![start];
158    visited[start] = true;
159    while let Some(u) = stack.pop() {
160        scc.push(u);
161        for &v in &adj[u] {
162            if !visited[v] {
163                visited[v] = true;
164                stack.push(v);
165            }
166        }
167    }
168}
169
170#[cfg(test)]
171#[path = "cycles_test.rs"]
172mod tests;
code_ranker_graph/cycles.rs

code_ranker_graph/
cycles.rs
