Skip to main content

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}