formualizer_eval/engine/
live_graph.rs

1//! Local SCC analysis over a recorded live-edge list (Stage 2 of the
2//! runtime-cycle-verdicts work, RFC #112).
3//!
4//! `evaluate_scc_unit` records live edges as `(from_idx, to_idx)` pairs over
5//! the member index space of one statically-cyclic SCC (`from` *reads* `to`,
6//! i.e. `from` depends on `to`). This module classifies that small index
7//! graph:
8//!
9//! * which members sit on a **live cycle** (SCC of size > 1, or a self-loop),
10//! * a deterministic **live-topological order** (dependencies before
11//!   dependents) used for stale-reader settling and the post-stamp
12//!   consistency pass.
13//!
14//! The scheduler's Tarjan reads dependency-graph adjacency, not edge lists,
15//! so this is a separate ~80-line iterative implementation. It is
16//! deterministic given a deterministic edge list: callers must pass sorted
17//! edges (the collector hands out a hash set; sort before calling).
18
19/// Classification of the live index graph of one SCC task.
20#[derive(Debug, Clone, PartialEq, Eq)]
21pub(crate) struct LiveGraphAnalysis {
22    /// `in_cycle[i]` — member `i` lies on a live cycle (its live SCC has
23    /// size > 1, or it has a live self-edge).
24    pub in_cycle: Vec<bool>,
25    /// Number of distinct live cycles (cyclic live SCCs).
26    pub cycle_count: usize,
27    /// All member indices in live-topological order: every member appears
28    /// after all members it has a live edge *to* (its live dependencies).
29    /// Members of one cyclic SCC appear contiguously (their internal order is
30    /// deterministic but otherwise meaningless).
31    pub topo: Vec<u32>,
32}
33
34impl LiveGraphAnalysis {
35    /// `pos[i]` = position of member `i` in `topo` (for ordering subsets).
36    pub fn topo_positions(&self) -> Vec<u32> {
37        let mut pos = vec![0u32; self.topo.len()];
38        for (p, &i) in self.topo.iter().enumerate() {
39            pos[i as usize] = p as u32;
40        }
41        pos
42    }
43}
44
45/// Iterative Tarjan over `n` nodes and directed `edges` (`from` depends on
46/// `to`). `edges` must be sorted and deduplicated for deterministic output.
47pub(crate) fn analyze_live_graph(n: usize, edges: &[(u32, u32)]) -> LiveGraphAnalysis {
48    debug_assert!(
49        edges.is_sorted(),
50        "live edges must be sorted for determinism"
51    );
52
53    // CSR adjacency.
54    let mut adj_start = vec![0usize; n + 1];
55    for &(from, _) in edges {
56        adj_start[from as usize + 1] += 1;
57    }
58    for i in 0..n {
59        adj_start[i + 1] += adj_start[i];
60    }
61    // `edges` is sorted by `from`, so the slice for node i is contiguous.
62    let adj = |i: usize| -> &[(u32, u32)] { &edges[adj_start[i]..adj_start[i + 1]] };
63
64    const UNVISITED: u32 = u32::MAX;
65    let mut index = vec![UNVISITED; n];
66    let mut lowlink = vec![0u32; n];
67    let mut on_stack = vec![false; n];
68    let mut stack: Vec<u32> = Vec::new();
69    let mut next_index = 0u32;
70
71    let mut in_cycle = vec![false; n];
72    let mut cycle_count = 0usize;
73    // Tarjan emits an SCC only after all SCCs it depends on were emitted, so
74    // emission order == live-topological order (dependencies first).
75    let mut topo: Vec<u32> = Vec::with_capacity(n);
76
77    // Explicit DFS frames: (node, next-edge-offset within its adjacency).
78    let mut frames: Vec<(u32, usize)> = Vec::new();
79    for root in 0..n as u32 {
80        if index[root as usize] != UNVISITED {
81            continue;
82        }
83        frames.push((root, 0));
84        index[root as usize] = next_index;
85        lowlink[root as usize] = next_index;
86        next_index += 1;
87        stack.push(root);
88        on_stack[root as usize] = true;
89
90        while let Some(&(v, next_edge)) = frames.last() {
91            let vu = v as usize;
92            if let Some(&(_, w)) = adj(vu).get(next_edge) {
93                frames.last_mut().expect("frame exists").1 += 1;
94                let wu = w as usize;
95                if index[wu] == UNVISITED {
96                    index[wu] = next_index;
97                    lowlink[wu] = next_index;
98                    next_index += 1;
99                    stack.push(w);
100                    on_stack[wu] = true;
101                    frames.push((w, 0));
102                } else if on_stack[wu] {
103                    lowlink[vu] = lowlink[vu].min(index[wu]);
104                }
105            } else {
106                // v is exhausted: maybe emit an SCC, then propagate lowlink.
107                if lowlink[vu] == index[vu] {
108                    let scc_start = topo.len();
109                    loop {
110                        let w = stack.pop().expect("tarjan stack underflow");
111                        on_stack[w as usize] = false;
112                        topo.push(w);
113                        if w == v {
114                            break;
115                        }
116                    }
117                    let members = &mut topo[scc_start..];
118                    // Deterministic intra-SCC order (pop order depends on DFS).
119                    members.sort_unstable();
120                    let cyclic = members.len() > 1 || adj(vu).iter().any(|&(_, w)| w == v); // self-loop
121                    if cyclic {
122                        cycle_count += 1;
123                        for &m in topo[scc_start..].iter() {
124                            in_cycle[m as usize] = true;
125                        }
126                    }
127                }
128                frames.pop();
129                if let Some(&(parent, _)) = frames.last() {
130                    let pu = parent as usize;
131                    lowlink[pu] = lowlink[pu].min(lowlink[vu]);
132                }
133            }
134        }
135    }
136
137    LiveGraphAnalysis {
138        in_cycle,
139        cycle_count,
140        topo,
141    }
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147
148    fn analyze(n: usize, mut edges: Vec<(u32, u32)>) -> LiveGraphAnalysis {
149        edges.sort_unstable();
150        edges.dedup();
151        analyze_live_graph(n, &edges)
152    }
153
154    fn assert_topo_consistent(a: &LiveGraphAnalysis, n: usize, edges: &[(u32, u32)]) {
155        assert_eq!(a.topo.len(), n);
156        let pos = a.topo_positions();
157        for &(from, to) in edges {
158            if from == to {
159                continue;
160            }
161            // Within a cyclic SCC ordering constraints don't apply.
162            if a.in_cycle[from as usize] && a.in_cycle[to as usize] {
163                continue;
164            }
165            assert!(
166                pos[to as usize] < pos[from as usize],
167                "dependency {to} must precede reader {from} in topo {:?}",
168                a.topo
169            );
170        }
171    }
172
173    #[test]
174    fn empty_graph_is_acyclic() {
175        let a = analyze(3, vec![]);
176        assert_eq!(a.cycle_count, 0);
177        assert_eq!(a.in_cycle, vec![false; 3]);
178        assert_eq!(a.topo.len(), 3);
179    }
180
181    #[test]
182    fn self_loop_is_a_cycle() {
183        let a = analyze(2, vec![(0, 0)]);
184        assert_eq!(a.cycle_count, 1);
185        assert_eq!(a.in_cycle, vec![true, false]);
186    }
187
188    #[test]
189    fn two_cycle_detected() {
190        let edges = vec![(0, 1), (1, 0)];
191        let a = analyze(2, edges.clone());
192        assert_eq!(a.cycle_count, 1);
193        assert_eq!(a.in_cycle, vec![true, true]);
194        assert_topo_consistent(&a, 2, &edges);
195    }
196
197    #[test]
198    fn chain_is_acyclic_with_deps_first_topo() {
199        // 0 reads 1, 1 reads 2: topo must be [2, 1, 0].
200        let edges = vec![(0, 1), (1, 2)];
201        let a = analyze(3, edges.clone());
202        assert_eq!(a.cycle_count, 0);
203        assert_eq!(a.in_cycle, vec![false; 3]);
204        assert_eq!(a.topo, vec![2, 1, 0]);
205        assert_topo_consistent(&a, 3, &edges);
206    }
207
208    #[test]
209    fn disjoint_components_cycle_and_chain() {
210        // Component A: 0 <-> 1 (cycle). Component B: 2 reads 3 (chain).
211        // Node 4 isolated.
212        let edges = vec![(0, 1), (1, 0), (2, 3)];
213        let a = analyze(5, edges.clone());
214        assert_eq!(a.cycle_count, 1);
215        assert_eq!(a.in_cycle, vec![true, true, false, false, false]);
216        assert_topo_consistent(&a, 5, &edges);
217    }
218
219    #[test]
220    fn cycle_with_downstream_reader() {
221        // 2 reads the cycle {0,1}; 3 reads 2.
222        let edges = vec![(0, 1), (1, 0), (2, 0), (3, 2)];
223        let a = analyze(4, edges.clone());
224        assert_eq!(a.cycle_count, 1);
225        assert_eq!(a.in_cycle, vec![true, true, false, false]);
226        let pos = a.topo_positions();
227        assert!(pos[0] < pos[2] && pos[1] < pos[2] && pos[2] < pos[3]);
228    }
229
230    #[test]
231    fn two_distinct_cycles_counted() {
232        let edges = vec![(0, 1), (1, 0), (2, 2)];
233        let a = analyze(3, edges);
234        assert_eq!(a.cycle_count, 2);
235        assert_eq!(a.in_cycle, vec![true, true, true]);
236    }
237
238    #[test]
239    fn deterministic_for_same_input() {
240        let edges = vec![(0, 2), (1, 2), (2, 3), (4, 0), (4, 1)];
241        let a1 = analyze(5, edges.clone());
242        let a2 = analyze(5, edges);
243        assert_eq!(a1, a2);
244    }
245}
formualizer_eval/engine/live_graph.rs

formualizer_eval/engine/
live_graph.rs
