Skip to main content

sheet_engine/
workbook.rs

1//! Workbook-level dependency algorithms — the sheet dimension `sheet-core`'s
2//! single-sheet graph leaves to this crate.
3//!
4//! Three questions, all answered over the *union* of per-sheet local edges
5//! (owned by each sheet's `sheet_core::DependencyGraph`) and the engine's
6//! cross-sheet edges:
7//!
8//! - `topological_order` — a total, deterministic evaluation order over
9//!   every formula cell in the workbook (Kahn's algorithm with a sorted
10//!   frontier; ties break on `(sheet, row, col)`).
11//! - `dirty_closure` — the transitive dependents of an edit set, the
12//!   minimal recompute set for incremental recalculation.
13//! - `circular_members` — the exact cycle membership among the cells
14//!   Kahn's algorithm left unordered (Kosaraju's algorithm; a cell counts
15//!   when it sits on a multi-cell cycle or references itself).
16//!
17//! All functions are pure walks over engine state: no mutation, no
18//! recursion (explicit stacks — formula chains are unbounded), and
19//! deterministic output for deterministic input.
20
21use crate::CellId;
22use std::collections::{BTreeMap, BTreeSet, VecDeque};
23use std::vec::Vec;
24
25/// The workbook-level precedents of `node`: every formula-modeling cell it
26/// reads, local (through the sheet's graph) and cross-sheet (through the
27/// engine's qualified-edge table) together.
28fn precedents(engine: &crate::Engine, node: &CellId) -> Vec<CellId> {
29    let (sheet, row, col) = node;
30    let mut out: Vec<CellId> = engine
31        .graph_for(sheet)
32        .map(|g| {
33            g.precedents((*row, *col))
34                .into_iter()
35                .map(|(r, c)| (sheet.clone(), r, c))
36                .collect::<Vec<_>>()
37        })
38        .unwrap_or_default();
39    if let Some(xs) = engine.cross_precedents(node) {
40        out.extend(xs.iter().cloned());
41    }
42    out
43}
44
45/// The workbook-level dependents of `node`: formula cells that must
46/// recompute when `node` changes.
47pub(crate) fn dependents(engine: &crate::Engine, node: &CellId) -> Vec<CellId> {
48    let (sheet, row, col) = node;
49    let mut out: Vec<CellId> = engine
50        .graph_for(sheet)
51        .map(|g| {
52            g.dependents((*row, *col))
53                .into_iter()
54                .map(|(r, c)| (sheet.clone(), r, c))
55                .collect::<Vec<_>>()
56        })
57        .unwrap_or_default();
58    if let Some(xs) = engine.cross_dependents(node) {
59        out.extend(xs.iter().cloned());
60    }
61    out
62}
63
64/// Every formula cell of the workbook, in `(sheet, row, col)` order.
65pub(crate) fn formula_cells(engine: &crate::Engine) -> BTreeSet<CellId> {
66    engine.formula_nodes()
67}
68
69/// Deterministic topological order over every formula cell: each formula
70/// appears after every formula it reads. Cells on — or downstream of — a
71/// cycle are omitted; see [`circular_members`].
72///
73/// The engine caches this (edges change only when formulas are registered
74/// or retired); the cache lives in [`crate::Engine`] and this function is
75/// the cold path.
76pub(crate) fn topological_order(engine: &crate::Engine) -> Vec<CellId> {
77    let nodes = formula_cells(engine);
78    let mut indegree: BTreeMap<&CellId, usize> = nodes.iter().map(|n| (n, 0)).collect();
79    // precedent → dependents, restricted to formula cells.
80    let mut adj: BTreeMap<&CellId, Vec<&CellId>> = BTreeMap::new();
81    for n in &nodes {
82        for p in precedents(engine, n) {
83            // Only edges into modeled cells count; literals and blanks are
84            // constants, always "already evaluated".
85            if let Some(pn) = nodes.get(&p) {
86                if let Some(deg) = indegree.get_mut(n) {
87                    *deg += 1;
88                }
89                adj.entry(pn).or_default().push(n);
90            }
91        }
92    }
93    kahn(indegree, &adj)
94}
95
96/// Topological order over a *subset* of formula cells — the work set of an
97/// incremental recalculation. Edges to cells outside the set are ignored:
98/// those values are clean and current, so they read as constants. Same
99/// determinism contract as [`topological_order`].
100pub(crate) fn topological_order_restricted(
101    engine: &crate::Engine,
102    work: &BTreeSet<CellId>,
103) -> Vec<CellId> {
104    let mut indegree: BTreeMap<&CellId, usize> = work.iter().map(|n| (n, 0)).collect();
105    let mut adj: BTreeMap<&CellId, Vec<&CellId>> = BTreeMap::new();
106    for n in work {
107        for p in precedents(engine, n) {
108            if let Some(pn) = work.get(&p) {
109                if let Some(deg) = indegree.get_mut(n) {
110                    *deg += 1;
111                }
112                adj.entry(pn).or_default().push(n);
113            }
114        }
115    }
116    kahn(indegree, &adj)
117}
118
119/// Kahn's algorithm over prepared adjacency; the ready set is sorted, so
120/// pops — and therefore the total order — are deterministic in
121/// `(sheet, row, col)`.
122fn kahn(
123    mut indegree: BTreeMap<&CellId, usize>,
124    adj: &BTreeMap<&CellId, Vec<&CellId>>,
125) -> Vec<CellId> {
126    let mut frontier: BTreeSet<&CellId> = indegree
127        .iter()
128        .filter(|(_, &d)| d == 0)
129        .map(|(&n, _)| n)
130        .collect();
131    let mut order: Vec<CellId> = Vec::with_capacity(indegree.len());
132    while let Some(n) = frontier.pop_first() {
133        order.push(n.clone());
134        if let Some(deps) = adj.get(n) {
135            for &d in deps {
136                if let Some(deg) = indegree.get_mut(d) {
137                    *deg -= 1;
138                    if *deg == 0 {
139                        frontier.insert(d);
140                    }
141                }
142            }
143        }
144    }
145    order
146}
147
148/// The transitive dependents of `seeds` (the seeds included). This is the
149/// minimal recompute set: a cell appears because an edit flows to it.
150pub(crate) fn dirty_closure(
151    engine: &crate::Engine,
152    seeds: impl IntoIterator<Item = CellId>,
153) -> BTreeSet<CellId> {
154    let mut seen: BTreeSet<CellId> = seeds.into_iter().collect();
155    let mut queue: VecDeque<CellId> = seen.iter().cloned().collect();
156    while let Some(n) = queue.pop_front() {
157        for d in dependents(engine, &n) {
158            if seen.insert(d.clone()) {
159                queue.push_back(d);
160            }
161        }
162    }
163    seen
164}
165
166/// The exact circular-reference membership among `leftover` — the cells
167/// topological ordering could not place. Kosaraju's algorithm over the
168/// subgraph the leftover induces: a cell is reported when it belongs to a
169/// multi-cell strongly-connected component or references itself. Output is
170/// sorted for determinism.
171pub(crate) fn circular_members(engine: &crate::Engine, leftover: &[CellId]) -> Vec<CellId> {
172    if leftover.is_empty() {
173        return Vec::new();
174    }
175    let set: BTreeSet<&CellId> = leftover.iter().collect();
176    // Forward and reversed adjacency, restricted to the leftover.
177    let mut forward: BTreeMap<&CellId, Vec<&CellId>> = BTreeMap::new();
178    let mut reverse: BTreeMap<&CellId, Vec<&CellId>> = BTreeMap::new();
179    for n in leftover {
180        for p in precedents(engine, n) {
181            if let Some(pn) = set.get(&p) {
182                forward.entry(n).or_default().push(*pn);
183                reverse.entry(*pn).or_default().push(n);
184            }
185        }
186    }
187
188    // Pass 1: finish-time order via an explicit-stack DFS.
189    let mut finished: Vec<&CellId> = Vec::with_capacity(leftover.len());
190    let mut state: BTreeMap<&CellId, u8> = BTreeMap::new(); // 0/absent = unvisited, 1 = on stack, 2 = done
191    for start in leftover {
192        if state.get(start).copied().unwrap_or(0) != 0 {
193            continue;
194        }
195        let mut stack: Vec<(&CellId, usize)> = vec![(start, 0)];
196        state.insert(start, 1);
197        while let Some(top) = stack.last_mut() {
198            let (n, idx) = *top;
199            let next = forward.get(n).and_then(|ns| ns.get(idx)).copied();
200            if let Some(c) = next {
201                top.1 += 1;
202                if state.get(c).copied().unwrap_or(0) == 0 {
203                    state.insert(c, 1);
204                    stack.push((c, 0));
205                }
206            } else {
207                state.insert(n, 2);
208                finished.push(n);
209                stack.pop();
210            }
211        }
212    }
213
214    // Pass 2: reversed-graph DFS in reverse finish order → SCCs.
215    let mut assigned: BTreeMap<&CellId, usize> = BTreeMap::new();
216    let mut components: Vec<Vec<&CellId>> = Vec::new();
217    for &n in finished.iter().rev() {
218        if assigned.contains_key(n) {
219            continue;
220        }
221        let id = components.len();
222        let mut members: Vec<&CellId> = Vec::new();
223        let mut queue: VecDeque<&CellId> = VecDeque::from([n]);
224        assigned.insert(n, id);
225        while let Some(c) = queue.pop_front() {
226            members.push(c);
227            for d in reverse.get(c).into_iter().flatten() {
228                if !assigned.contains_key(d) {
229                    assigned.insert(d, id);
230                    queue.push_back(*d);
231                }
232            }
233        }
234        components.push(members);
235    }
236
237    // A component is a cycle when it has several members or a self-edge.
238    let mut cycle_cells: BTreeSet<CellId> = BTreeSet::new();
239    for members in &components {
240        let single = members.first();
241        let self_edge = members.len() == 1
242            && single.is_some_and(|n| forward.get(n).is_some_and(|ns| ns.contains(n)));
243        if members.len() > 1 || self_edge {
244            cycle_cells.extend(members.iter().map(|n| (*n).clone()));
245        }
246    }
247    cycle_cells.into_iter().collect()
248}
249
250/// Renders a cell as `Sheet!A1` (1-based) for error messages and tests.
251#[cfg(test)]
252pub(crate) fn a1(node: &CellId) -> String {
253    let (sheet, row, col) = node;
254    format!(
255        "{sheet}!{}{}",
256        formula_lang::ast::col_name(col + 1),
257        row + 1
258    )
259}
260
261#[cfg(test)]
262mod tests {
263    #![allow(
264        clippy::unwrap_used,
265        clippy::expect_used,
266        clippy::panic,
267        clippy::indexing_slicing
268    )]
269
270    use super::*;
271    use crate::Engine;
272
273    fn n(sheet: &str, row: u32, col: u32) -> CellId {
274        (sheet.to_string(), row, col)
275    }
276
277    #[test]
278    fn topo_orders_a_cross_sheet_chain() {
279        let mut e = Engine::new();
280        e.set_cell("S1", 0, 0, "1").unwrap();
281        e.set_cell("S2", 0, 0, "=S1!A1+1").unwrap();
282        e.set_cell("S1", 0, 1, "=S2!A1+1").unwrap();
283        let order = topological_order(&e);
284        let a1s: Vec<String> = order.iter().map(a1).collect();
285        assert_eq!(a1s, vec!["S2!A1", "S1!B1"]);
286    }
287
288    #[test]
289    fn closure_flows_across_sheets() {
290        let mut e = Engine::new();
291        e.set_cell("S1", 0, 0, "1").unwrap();
292        e.set_cell("S2", 0, 0, "=S1!A1+1").unwrap();
293        e.set_cell("S2", 0, 1, "=S2!A1+1").unwrap();
294        let dirty = dirty_closure(&e, [n("S1", 0, 0)]);
295        let a1s: Vec<String> = dirty.iter().map(a1).collect();
296        assert_eq!(a1s, vec!["S1!A1", "S2!A1", "S2!B1"]);
297    }
298
299    #[test]
300    fn cycles_are_reported_exactly_not_downstream() {
301        // A1 ↔ B1, C1 = A1 + 1 (downstream of the cycle, not in it).
302        let mut e = Engine::new();
303        e.set_cell("S", 0, 0, "=B1+1").unwrap();
304        e.set_cell("S", 0, 1, "=A1+1").unwrap();
305        e.set_cell("S", 0, 2, "=A1+1").unwrap();
306        let order = topological_order(&e);
307        assert_eq!(order, Vec::<CellId>::new());
308        let left = formula_cells(&e)
309            .into_iter()
310            .filter(|n| !order.contains(n))
311            .collect::<Vec<_>>();
312        let cyc = circular_members(&e, &left);
313        let a1s: Vec<String> = cyc.iter().map(a1).collect();
314        assert_eq!(a1s, vec!["S!A1", "S!B1"]);
315    }
316
317    #[test]
318    fn cross_sheet_cycles_are_found() {
319        let mut e = Engine::new();
320        e.set_cell("S1", 0, 0, "=S2!A1+1").unwrap();
321        e.set_cell("S2", 0, 0, "=S1!A1+1").unwrap();
322        let order = topological_order(&e);
323        assert_eq!(order, Vec::<CellId>::new());
324        let left: Vec<CellId> = formula_cells(&e).into_iter().collect();
325        let cyc = circular_members(&e, &left);
326        assert_eq!(cyc.len(), 2);
327    }
328
329    #[test]
330    fn a1_notation_is_one_based() {
331        assert_eq!(a1(&n("S", 0, 0)), "S!A1");
332        assert_eq!(a1(&n("S", 1, 27)), "S!AB2");
333    }
334}