sheet_core/graph.rs
1//! The dependency DAG — formulas, precedents, dependents, evaluation order.
2//!
3//! The graph is two index maps over one source of truth:
4//!
5//! - **forward**: formula cell → the cells its formula reads (precedents),
6//! - **reverse**: cell → the formula cells that read it (dependents).
7//!
8//! Both directions are maintained on every [`add`](DependencyGraph::add_formula)
9//! and [`remove`](DependencyGraph::remove_formula), so the two queries are
10//! always consistent by construction — a property the test suite checks on
11//! random graphs.
12//!
13//! # Determinism
14//!
15//! Every derived quantity — [`topological_order`](DependencyGraph::topological_order),
16//! [`dirty_subgraph`](DependencyGraph::dirty_subgraph),
17//! [`has_circular`](DependencyGraph::has_circular) — is a pure function of
18//! the edge set: Kahn's algorithm with a sorted ready set and Tarjan SCC
19//! with ascending neighbor order. Same edges in, same order out, on every
20//! machine, every run.
21//!
22//! # Cycle policy
23//!
24//! Cycles are *represented*, not rejected at insert: real workbooks contain
25//! them, and an engine needs [`has_circular`] to report them while the rest
26//! of the graph still evaluates. Cycle members are excluded from
27//! [`topological_order`] (no valid position exists for them) and from
28//! [`dirty_subgraph`] roots' propagation only insofar as they cannot be
29//! ordered — they still appear when the edit reaches them.
30
31use crate::error::GraphError;
32use crate::refs::extract_refs;
33use alloc::collections::{BTreeMap, BTreeSet};
34use alloc::vec::Vec;
35
36/// The dependency graph of one worksheet's formulas.
37///
38/// A cell is a *formula cell* iff it appears in the forward map; constant
39/// cells appear only on the reverse side (as things formulas read). The
40/// graph is single-sheet: coordinates are `(row, col)` within the modeled
41/// worksheet (see [`crate::refs`] for the sheet-qualifier policy).
42#[derive(Debug, Clone, Default, PartialEq, Eq)]
43pub struct DependencyGraph {
44 /// formula cell → precedents (cells its formula reads).
45 forward: BTreeMap<(u32, u32), BTreeSet<(u32, u32)>>,
46 /// cell → dependents (formula cells whose formulas read it).
47 reverse: BTreeMap<(u32, u32), BTreeSet<(u32, u32)>>,
48}
49
50impl DependencyGraph {
51 /// An empty graph.
52 #[must_use]
53 pub const fn new() -> Self {
54 DependencyGraph {
55 forward: BTreeMap::new(),
56 reverse: BTreeMap::new(),
57 }
58 }
59
60 /// Extracts the references of `formula` into a standalone graph anchored
61 /// at the origin cell `(0, 0)` — i.e. exactly
62 /// `Self::new()` + [`add_formula`](Self::add_formula)`((0, 0), formula)`.
63 ///
64 /// Useful for one-shot parsing (`precedents((0, 0))` returns the sorted,
65 /// de-duplicated references) and as the typed entry point when the
66 /// anchor cell is irrelevant. Note the modeling consequence: a formula
67 /// at the origin that reads `A1` produces a self-edge and will be
68 /// reported by [`has_circular`](Self::has_circular) — correct for the
69 /// anchor, so prefer [`add_formula`](Self::add_formula) with the real
70 /// address when one exists.
71 ///
72 /// # Errors
73 ///
74 /// [`GraphError`] — see [`extract_refs`](crate::refs::extract_refs).
75 pub fn extract(formula: &str) -> Result<Self, GraphError> {
76 let mut graph = Self::new();
77 graph.add_formula((0, 0), formula)?;
78 Ok(graph)
79 }
80
81 /// Registers `cell` as holding `formula`, replacing any formula
82 /// previously registered there. The graph is mutated only when the
83 /// formula parses — a rejected formula leaves it untouched.
84 ///
85 /// # Errors
86 ///
87 /// [`GraphError`] — see [`extract_refs`](crate::refs::extract_refs).
88 pub fn add_formula(&mut self, cell: (u32, u32), formula: &str) -> Result<(), GraphError> {
89 let refs = extract_refs(formula)?;
90 self.remove_formula(cell); // replace semantics: detach old edges first
91 let set: BTreeSet<(u32, u32)> = refs.into_iter().collect();
92 for precedent in &set {
93 self.reverse.entry(*precedent).or_default().insert(cell);
94 }
95 self.forward.insert(cell, set);
96 Ok(())
97 }
98
99 /// Unregisters the formula at `cell` (no-op when there is none). The
100 /// cell's *own* outgoing edges go; incoming edges of other formulas
101 /// that read it stay — removing a formula does not blank its value for
102 /// readers, it just stops the cell from being recomputed.
103 pub fn remove_formula(&mut self, cell: (u32, u32)) {
104 if let Some(precedents) = self.forward.remove(&cell) {
105 for precedent in precedents {
106 if let Some(dependents) = self.reverse.get_mut(&precedent) {
107 dependents.remove(&cell);
108 if dependents.is_empty() {
109 self.reverse.remove(&precedent);
110 }
111 }
112 }
113 }
114 }
115
116 /// Cells read by the formula at `cell`, sorted ascending. Empty when
117 /// `cell` holds no formula.
118 #[must_use]
119 pub fn precedents(&self, cell: (u32, u32)) -> Vec<(u32, u32)> {
120 self.forward
121 .get(&cell)
122 .map_or_else(Vec::new, |p| p.iter().copied().collect())
123 }
124
125 /// Formula cells whose formulas read `cell`, sorted ascending.
126 #[must_use]
127 pub fn dependents(&self, cell: (u32, u32)) -> Vec<(u32, u32)> {
128 self.reverse
129 .get(&cell)
130 .map_or_else(Vec::new, |d| d.iter().copied().collect())
131 }
132
133 /// `true` when `cell` holds a registered formula.
134 #[must_use]
135 pub fn contains_formula(&self, cell: (u32, u32)) -> bool {
136 self.forward.contains_key(&cell)
137 }
138
139 /// Number of registered formulas.
140 #[must_use]
141 pub fn formula_count(&self) -> usize {
142 self.forward.len()
143 }
144
145 /// All registered formula cells, sorted ascending.
146 #[must_use]
147 pub fn formula_cells(&self) -> Vec<(u32, u32)> {
148 self.forward.keys().copied().collect()
149 }
150
151 /// The evaluation order: every formula cell, ordered so that each
152 /// formula comes after every formula it (transitively) reads. Ties
153 /// break by ascending `(row, col)`, so the result is a total, stable
154 /// order. Formula cells inside a circular reference have no valid
155 /// position — and neither does anything that reads them — so both are
156 /// omitted; pair with [`has_circular`](Self::has_circular) to detect
157 /// that case.
158 #[must_use]
159 pub fn topological_order(&self) -> Vec<(u32, u32)> {
160 // in-degree over formula cells only: an edge p → f exists for every
161 // precedent p of f that is itself a formula cell.
162 let mut in_degree: BTreeMap<(u32, u32), usize> = BTreeMap::new();
163 let mut edges: BTreeMap<(u32, u32), Vec<(u32, u32)>> = BTreeMap::new();
164 for (&formula, precedents) in &self.forward {
165 in_degree.entry(formula).or_insert(0);
166 for &p in precedents {
167 if self.forward.contains_key(&p) {
168 *in_degree.entry(formula).or_insert(0) += 1;
169 edges.entry(p).or_default().push(formula);
170 }
171 }
172 }
173
174 // Kahn's algorithm; the ready set is sorted, so pops are deterministic.
175 let mut ready: BTreeSet<(u32, u32)> = in_degree
176 .iter()
177 .filter(|(_, &d)| d == 0)
178 .map(|(&f, _)| f)
179 .collect();
180 let mut order = Vec::with_capacity(self.forward.len());
181 while let Some(cell) = ready.pop_first() {
182 order.push(cell);
183 if let Some(targets) = edges.get(&cell) {
184 for &t in targets {
185 if let Some(d) = in_degree.get_mut(&t) {
186 *d -= 1;
187 if *d == 0 {
188 ready.insert(t);
189 }
190 }
191 }
192 }
193 }
194 order
195 }
196
197 /// The minimal recompute set for an edit of `edited`, in evaluation
198 /// order — ready to drive an incremental recalc directly.
199 ///
200 /// Formulas among the edited cells are included (an edited formula must
201 /// re-evaluate); constants only propagate. Cycle members that the
202 /// propagation reaches are included but cannot be ordered, so they are
203 /// appended after the orderable prefix (see [`has_circular`](Self::has_circular)).
204 #[must_use]
205 pub fn dirty_subgraph(&self, edited: &[(u32, u32)]) -> Vec<(u32, u32)> {
206 // Transitive dependents of the edited cells (reverse BFS), keeping
207 // only formula cells; edited formula cells are dirty themselves.
208 let mut dirty: BTreeSet<(u32, u32)> = BTreeSet::new();
209 let mut frontier: Vec<(u32, u32)> = Vec::new();
210 for &cell in edited {
211 if self.forward.contains_key(&cell) {
212 if dirty.insert(cell) {
213 frontier.push(cell);
214 }
215 } else {
216 frontier.push(cell); // constant: propagates without being dirty
217 }
218 }
219 while let Some(cell) = frontier.pop() {
220 if let Some(dependents) = self.reverse.get(&cell) {
221 for &d in dependents {
222 if dirty.insert(d) {
223 frontier.push(d);
224 }
225 }
226 }
227 }
228
229 // Order the dirty set internally, appending anything circular.
230 let orderable = self.topological_order();
231 let mut result: Vec<(u32, u32)> = orderable
232 .into_iter()
233 .filter(|c| dirty.contains(c))
234 .collect();
235 for &c in &dirty {
236 if !result.contains(&c) {
237 result.push(c);
238 }
239 }
240 result
241 }
242
243 /// The circular references, as explicit cycles. Each cycle is sorted
244 /// ascending and the cycles themselves are sorted by first member, so
245 /// the output is deterministic. Self-references (`A1 = A1+1`) report as
246 /// single-member cycles. Empty when the graph is acyclic.
247 #[must_use]
248 pub fn has_circular(&self) -> Vec<Vec<(u32, u32)>> {
249 let sccs = tarjan_sccs(self);
250 let mut cycles = Vec::new();
251 for scc in sccs {
252 let self_loop = scc
253 .first()
254 .is_some_and(|&m| self.forward.get(&m).is_some_and(|p| p.contains(&m)));
255 if scc.len() > 1 || self_loop {
256 cycles.push(scc);
257 }
258 }
259 cycles.sort();
260 cycles
261 }
262}
263
264/// Tarjan strongly-connected components over the formula-cell subgraph
265/// (edges: formula → formula precedents). Iterative (no recursion, so no
266/// stack overflow on deep chains); neighbor iteration is ascending, and
267/// components are emitted sorted, making the result deterministic.
268fn tarjan_sccs(graph: &DependencyGraph) -> Vec<Vec<(u32, u32)>> {
269 #[derive(Clone, Copy, PartialEq)]
270 enum Frame {
271 Enter,
272 Visit { child: usize },
273 }
274
275 let mut index: BTreeMap<(u32, u32), usize> = BTreeMap::new();
276 let mut low: BTreeMap<(u32, u32), usize> = BTreeMap::new();
277 let mut on_stack: BTreeSet<(u32, u32)> = BTreeSet::new();
278 let mut stack: Vec<(u32, u32)> = Vec::new();
279 let mut next_index = 0usize;
280 let mut components: Vec<Vec<(u32, u32)>> = Vec::new();
281
282 for &root in graph.forward.keys() {
283 if index.contains_key(&root) {
284 continue;
285 }
286 let mut call = alloc::vec![(root, Frame::Enter)];
287 while let Some((cell, frame)) = call.pop() {
288 match frame {
289 Frame::Enter => {
290 index.insert(cell, next_index);
291 low.insert(cell, next_index);
292 next_index += 1;
293 stack.push(cell);
294 on_stack.insert(cell);
295 call.push((cell, Frame::Visit { child: 0 }));
296 }
297 Frame::Visit { child } => {
298 let precedents = graph
299 .forward
300 .get(&cell)
301 .map_or_else(Vec::new, |p| p.iter().copied().collect::<Vec<_>>());
302 if let Some(&next) = precedents.get(child) {
303 call.push((cell, Frame::Visit { child: child + 1 }));
304 if !graph.forward.contains_key(&next) {
305 continue;
306 }
307 if index.contains_key(&next) {
308 if on_stack.contains(&next) {
309 if let (Some(&n), Some(&l)) = (index.get(&next), low.get(&cell)) {
310 let m = n.min(l);
311 low.insert(cell, m);
312 }
313 }
314 } else {
315 call.push((next, Frame::Enter));
316 }
317 } else {
318 // All children processed: maybe close a component.
319 if let (Some(&l), Some(&i)) = (low.get(&cell), index.get(&cell)) {
320 if l == i {
321 let mut component = Vec::new();
322 while let Some(top) = stack.pop() {
323 on_stack.remove(&top);
324 component.push(top);
325 if top == cell {
326 break;
327 }
328 }
329 component.sort_unstable();
330 components.push(component);
331 }
332 }
333 // Propagate low-link to the parent.
334 if let Some(&l) = low.get(&cell) {
335 if let Some(&(p, Frame::Visit { .. })) = call.last() {
336 if let Some(&pl) = low.get(&p) {
337 low.insert(p, pl.min(l));
338 }
339 }
340 }
341 }
342 }
343 }
344 }
345 }
346 components
347}
348
349#[cfg(test)]
350mod tests {
351 #![allow(
352 clippy::unwrap_used,
353 clippy::expect_used,
354 clippy::panic,
355 clippy::indexing_slicing
356 )]
357
358 use super::DependencyGraph;
359 use crate::error::GraphError;
360 use alloc::{string::String, vec, vec::Vec};
361
362 #[test]
363 fn add_query_remove_round_trip() {
364 let mut g = DependencyGraph::new();
365 assert_eq!(g.formula_count(), 0);
366 assert!(g.formula_cells().is_empty());
367 g.add_formula((0, 1), "=A1+B2").unwrap();
368 assert!(g.contains_formula((0, 1)));
369 assert_eq!(g.formula_count(), 1);
370 assert_eq!(g.precedents((0, 1)), vec![(0, 0), (1, 1)]);
371 assert_eq!(g.dependents((0, 0)), vec![(0, 1)]);
372 assert_eq!(g.dependents((1, 1)), vec![(0, 1)]);
373 assert_eq!(g.precedents((0, 0)), Vec::<(u32, u32)>::new()); // constant
374 assert_eq!(g.formula_cells(), vec![(0, 1)]);
375
376 g.remove_formula((0, 1));
377 assert!(!g.contains_formula((0, 1)));
378 assert_eq!(g.formula_count(), 0);
379 assert_eq!(g.dependents((0, 0)), Vec::<(u32, u32)>::new());
380 g.remove_formula((9, 9)); // absent: no-op
381 }
382
383 #[test]
384 fn replace_semantics_swap_edges() {
385 let mut g = DependencyGraph::new();
386 g.add_formula((0, 0), "=B1").unwrap();
387 let _ = g.add_formula((0, 0), "=C1"); // replaces B1 edge with C1
388 assert_eq!(g.precedents((0, 0)), vec![(0, 2)]);
389 assert_eq!(g.dependents((0, 1)), Vec::<(u32, u32)>::new());
390 assert_eq!(g.dependents((0, 2)), vec![(0, 0)]);
391
392 // Failed parse leaves the graph untouched.
393 assert_eq!(
394 g.add_formula((0, 0), "=Nope!"),
395 Err(GraphError::InvalidReference {
396 position: 5,
397 text: String::new()
398 })
399 );
400 assert_eq!(g.precedents((0, 0)), vec![(0, 2)]);
401 }
402
403 #[test]
404 fn topological_order_places_formulas_after_their_inputs() {
405 let mut g = DependencyGraph::new();
406 // B2 = A1+1, C3 = B2+1, D4 = C3+1 (a pure chain), E5 = const ref.
407 g.add_formula((1, 1), "=A1+1").unwrap();
408 g.add_formula((2, 2), "=B2+1").unwrap();
409 g.add_formula((3, 3), "=C4+1").unwrap();
410 let order = g.topological_order();
411 assert_eq!(order, vec![(1, 1), (2, 2), (3, 3)]);
412
413 // Diamond: A1 → B2, A1 → C3, B2 + C3 → D4.
414 let mut d = DependencyGraph::new();
415 d.add_formula((1, 1), "=A1").unwrap();
416 d.add_formula((2, 2), "=A1").unwrap();
417 d.add_formula((3, 3), "=B2+C3").unwrap();
418 let order = d.topological_order();
419 assert_eq!(order.len(), 3);
420 let pos = |c| order.iter().position(|&x| x == c).unwrap();
421 assert!(pos((1, 1)) < pos((3, 3)));
422 assert!(pos((2, 2)) < pos((3, 3)));
423 }
424
425 #[test]
426 fn dirty_subgraph_is_minimal_transitive_and_ordered() {
427 let mut g = DependencyGraph::new();
428 g.add_formula((1, 1), "=A1").unwrap(); // B2
429 g.add_formula((2, 2), "=B2").unwrap(); // C3
430 g.add_formula((3, 3), "=Z9").unwrap(); // D4 (unrelated)
431
432 // Editing the constant A1 dirties B2 then C3, in order.
433 assert_eq!(g.dirty_subgraph(&[(0, 0)]), vec![(1, 1), (2, 2)]);
434 // Editing B2 (a formula) dirties itself and downstream.
435 assert_eq!(g.dirty_subgraph(&[(1, 1)]), vec![(1, 1), (2, 2)]);
436 // Unrelated edits dirty nothing.
437 assert_eq!(g.dirty_subgraph(&[(8, 8)]), Vec::<(u32, u32)>::new());
438 // Empty edit list.
439 assert_eq!(g.dirty_subgraph(&[]), Vec::<(u32, u32)>::new());
440 }
441
442 #[test]
443 fn circular_references_are_reported_as_cycles() {
444 let mut g = DependencyGraph::new();
445 g.add_formula((0, 0), "=B1").unwrap();
446 g.add_formula((0, 1), "=A1").unwrap(); // A1 ↔ B1
447 g.add_formula((5, 5), "=A1").unwrap(); // feeds into the cycle but not in it
448 let cycles = g.has_circular();
449 assert_eq!(cycles, vec![vec![(0, 0), (0, 1)]]);
450
451 // Self-reference is a single-member cycle.
452 let mut s = DependencyGraph::new();
453 s.add_formula((2, 2), "=C3+1").unwrap();
454 assert_eq!(s.has_circular(), vec![vec![(2, 2)]]);
455
456 // Cycle members are omitted from the evaluation order — and so is
457 // everything downstream of a cycle (it could never evaluate first).
458 let order = g.topological_order();
459 assert_eq!(order, Vec::<(u32, u32)>::new());
460 }
461
462 #[test]
463 fn extract_anchors_at_the_origin() {
464 let g = DependencyGraph::extract("=SUM(B1:C2)").unwrap();
465 assert_eq!(g.precedents((0, 0)), vec![(0, 1), (0, 2), (1, 1), (1, 2)]);
466 assert!(DependencyGraph::extract("=Nope!1").is_err());
467 }
468}