Skip to main content

sheet_engine/
engine.rs

1//! The engine itself: cell storage, dependency tracking, calculation.
2
3use crate::error::EngineError;
4use crate::qualified::Prepared;
5use crate::resolver::EngineResolver;
6use crate::workbook;
7use crate::CellId;
8use formula_lang::ExcelError;
9use sheet_core::{Cell, DependencyGraph, Sheet};
10use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
11use std::string::String;
12use std::vec::Vec;
13
14/// A spreadsheet calculation engine.
15///
16/// Named sheets of cells ([`sheet_core::Sheet`]), a workbook-level
17/// dependency graph (per-sheet [`sheet_core::DependencyGraph`] plus the
18/// engine's cross-sheet edges), a cache of computed values, and the dirty
19/// set incremental recalculation drains. See the [crate docs](crate) for
20/// the calculation model.
21pub struct Engine {
22    /// Named sheets, sorted by name — the engine's cell storage.
23    sheets: BTreeMap<String, Sheet>,
24    /// Per-sheet local dependency graphs: a formula's edges to cells of its
25    /// own sheet, exactly as `sheet-core` models them.
26    graphs: BTreeMap<String, DependencyGraph>,
27    /// Cross-sheet edges: a qualified formula → the cells it reads on other
28    /// sheets. Local edges never appear here.
29    cross_precedents: HashMap<CellId, BTreeSet<CellId>>,
30    /// Reverse of `cross_precedents`: a cell → the qualified formulas that
31    /// read it.
32    cross_dependents: HashMap<CellId, BTreeSet<CellId>>,
33    /// Formulas in evaluation-ready form, keyed by their cell.
34    formulas: BTreeMap<CellId, Prepared>,
35    /// Cells whose formula contains at least one sheet-qualified reference.
36    qualified: BTreeSet<CellId>,
37    /// Cells whose formula contains a volatile function (`TODAY`, `NOW`,
38    /// `OFFSET`) and therefore re-evaluates on every calculation.
39    volatile: BTreeSet<CellId>,
40    /// Cached values: literals at set time, computed results at
41    /// recalculation time. A formula cell with no entry has never been
42    /// calculated.
43    values: HashMap<CellId, formula_lang::Value>,
44    /// Cells edited since the last calculation.
45    dirty: HashSet<CellId>,
46    /// Cached workbook topological order — the cold path runs only when
47    /// edges change (formulas registered or retired), never per
48    /// recalculation.
49    order_cache: Option<Vec<CellId>>,
50}
51
52impl Engine {
53    /// An empty workbook with no sheets. Sheets are created on demand by
54    /// [`set_cell`](Self::set_cell) and by
55    /// [`from_xlsx`](Self::from_xlsx).
56    #[must_use]
57    pub fn new() -> Self {
58        Self {
59            sheets: BTreeMap::new(),
60            graphs: BTreeMap::new(),
61            cross_precedents: HashMap::new(),
62            cross_dependents: HashMap::new(),
63            formulas: BTreeMap::new(),
64            qualified: BTreeSet::new(),
65            volatile: BTreeSet::new(),
66            values: HashMap::new(),
67            dirty: HashSet::new(),
68            order_cache: None,
69        }
70    }
71}
72
73impl Default for Engine {
74    fn default() -> Self {
75        Engine::new()
76    }
77}
78
79impl Engine {
80    /// The names of the sheets currently in the workbook, sorted.
81    #[must_use]
82    pub fn sheet_names(&self) -> Vec<String> {
83        self.sheets.keys().cloned().collect()
84    }
85
86    /// `true` when the named sheet exists.
87    #[must_use]
88    pub fn has_sheet(&self, sheet: &str) -> bool {
89        self.sheets.contains_key(sheet)
90    }
91
92    /// The cached value of one cell — the computed result for a formula,
93    /// the literal for anything else. `None` for a blank cell, an unknown
94    /// sheet, or a formula that has never been calculated.
95    #[must_use]
96    pub fn get_value(&self, sheet: &str, row: u32, col: u32) -> Option<formula_lang::Value> {
97        self.values.get(&(sheet.to_string(), row, col)).cloned()
98    }
99
100    /// Every volatile cell (`TODAY`, `NOW`, `OFFSET` formulas), in
101    /// `(sheet, row, col)` order. These re-evaluate on every calculation,
102    /// full or incremental, Excel-style.
103    #[must_use]
104    pub fn volatile_cells(&self) -> Vec<CellId> {
105        self.volatile.iter().cloned().collect()
106    }
107
108    /// Sets one cell from user input.
109    ///
110    /// Input grammar, Excel-flavored:
111    ///
112    /// - `=…` — a formula, parsed with `formula-lang` (sheet-qualified
113    ///   references supported; see [`crate::qualified`]);
114    /// - a number — stored numeric (`"42"`, `"-3.5"`, `"1e3"`);
115    /// - `TRUE` / `FALSE`, any case — stored logical;
116    /// - an error literal (`"#DIV/0!"` and the other canonical spellings) —
117    ///   stored as an error *value*;
118    /// - anything else — stored text, verbatim.
119    ///
120    /// The cell is marked dirty; nothing computes until
121    /// [`recalculate`](Self::recalculate) or
122    /// [`recalculate_incremental`](Self::recalculate_incremental). A
123    /// formula replacing a formula swaps the dependency edges; a literal
124    /// replacing a formula removes them. Referencing a sheet that does not
125    /// exist is legal at set time (spreadsheets let you type ahead) — such
126    /// reads evaluate to `#REF!` until the sheet appears.
127    ///
128    /// # Errors
129    ///
130    /// [`EngineError::Formula`] when formula text does not parse;
131    /// [`EngineError::Graph`] when its references cannot be modeled (for
132    /// example a range wider than `sheet_core::refs::RANGE_CELL_CAP`). A
133    /// rejected formula changes nothing *except* dropping the cell's
134    /// previous cached value.
135    pub fn set_cell(
136        &mut self,
137        sheet: &str,
138        row: u32,
139        col: u32,
140        input: &str,
141    ) -> Result<(), EngineError> {
142        let input = input.trim();
143        if input.starts_with('=') {
144            return self.set_formula(sheet, row, col, input);
145        }
146        let (cell, value) = literal(input);
147        let node = (sheet.to_string(), row, col);
148        self.unregister_formula(&node);
149        self.sheets
150            .entry(node.0.clone())
151            .or_default()
152            .set(row, col, cell);
153        self.values.insert(node.clone(), value);
154        self.dirty.insert(node);
155        Ok(())
156    }
157
158    /// Evaluates every formula in the workbook, in topological order —
159    /// each formula after every formula it reads, across sheets. The dirty
160    /// set is drained.
161    ///
162    /// # Errors
163    ///
164    /// [`EngineError::CircularReference`] when the workbook contains
165    /// circular references. Everything *not* on a cycle has still been
166    /// evaluated when the error is raised (Excel computes the rest of the
167    /// workbook); cells on a cycle keep no value.
168    pub fn recalculate(&mut self) -> Result<(), EngineError> {
169        let order = self.topo();
170        let mut circular = None;
171        if order.len() < self.formulas.len() {
172            let placed: BTreeSet<&CellId> = order.iter().collect();
173            let leftover: Vec<CellId> = self
174                .formulas
175                .keys()
176                .filter(|n| !placed.contains(*n))
177                .cloned()
178                .collect();
179            circular = Some(workbook::circular_members(self, &leftover));
180        }
181        for node in order {
182            self.evaluate_node(&node);
183        }
184        self.dirty.clear();
185        match circular {
186            Some(cells) => Err(EngineError::CircularReference(cells)),
187            None => Ok(()),
188        }
189    }
190
191    /// Evaluates only what an edit made stale: the edited cells and their
192    /// transitive dependents, plus every volatile cell — in topological
193    /// order, so a chain settles in one pass.
194    ///
195    /// `edited` lists cells that changed outside the engine's bookkeeping
196    /// (typically the cells of a [`set_cell`](Self::set_cell) batch);
197    /// cells dirtied by earlier `set_cell` calls are included
198    /// automatically, so `recalculate_incremental(&[])` is the
199    /// "recalculate what is pending" form.
200    ///
201    /// On a large sheet whose edit touches a small subgraph this is
202    /// proportionally cheaper than a full [`recalculate`](Self::recalculate).
203    ///
204    /// # Errors
205    ///
206    /// [`EngineError::CircularReference`] when the pending set meets a
207    /// cycle — same contract as `recalculate`.
208    pub fn recalculate_incremental(
209        &mut self,
210        edited: &[(String, u32, u32)],
211    ) -> Result<(), EngineError> {
212        let seeds = self.dirty.iter().cloned().chain(edited.iter().cloned());
213        let mut work = workbook::dirty_closure(self, seeds);
214        for v in self.volatile.clone() {
215            work.insert(v);
216        }
217
218        // Incremental evaluation only orders the work set: cells outside
219        // it are clean, and their current values read as constants.
220        let order = workbook::topological_order_restricted(self, &work);
221        let mut circular = None;
222        let placed: BTreeSet<&CellId> = order.iter().collect();
223        let leftover: Vec<CellId> = work
224            .iter()
225            // Literal seeds are never "ordered" — only formula cells can
226            // be stuck on a cycle.
227            .filter(|n| self.formulas.contains_key(*n) && !placed.contains(*n))
228            .cloned()
229            .collect();
230        if !leftover.is_empty() {
231            let members = workbook::circular_members(self, &leftover);
232            if !members.is_empty() {
233                circular = Some(members);
234            }
235        }
236
237        for node in order {
238            self.evaluate_node(&node);
239        }
240        self.dirty.clear();
241        match circular {
242            Some(cells) => Err(EngineError::CircularReference(cells)),
243            None => Ok(()),
244        }
245    }
246
247    /// Serializes the workbook to XLSX bytes. Formula cells carry their
248    /// cached results, so a `to_xlsx` → `from_xlsx` round-trip preserves
249    /// values without a recalculation.
250    ///
251    /// # Errors
252    ///
253    /// [`EngineError::Xlsx`] when the codec rejects the workbook.
254    pub fn to_xlsx(&self) -> Result<Vec<u8>, EngineError> {
255        crate::xlsx_codec::to_xlsx(self)
256    }
257
258    /// Loads a workbook from XLSX bytes. Formula cells come back with
259    /// their cached results (the file's stored values); a
260    /// [`recalculate`](Self::recalculate) refreshes them.
261    ///
262    /// # Errors
263    ///
264    /// [`EngineError::Xlsx`] when the bytes are not a readable workbook;
265    /// [`EngineError::Formula`] / [`EngineError::Graph`] when a stored
266    /// formula cannot be parsed or modeled;
267    /// [`EngineError::DuplicateSheet`] for duplicated sheet names.
268    pub fn from_xlsx(data: &[u8]) -> Result<Self, EngineError> {
269        crate::xlsx_codec::from_xlsx(data)
270    }
271
272    // ------------------------------------------------------------------
273    // Internals
274    // ------------------------------------------------------------------
275
276    /// The sheets map, for the XLSX codec.
277    pub(crate) fn sheets_ref(&self) -> &BTreeMap<String, Sheet> {
278        &self.sheets
279    }
280
281    /// Creates a sheet and its graph when absent (codec load path).
282    pub(crate) fn open_sheet(&mut self, sheet: &str) {
283        self.sheets.entry(sheet.to_string()).or_default();
284        self.graphs.entry(sheet.to_string()).or_default();
285    }
286
287    /// Stores a literal cell and its cached value (codec load path).
288    pub(crate) fn insert_literal(
289        &mut self,
290        sheet: &str,
291        row: u32,
292        col: u32,
293        cell: Cell,
294        value: formula_lang::Value,
295    ) {
296        let node = (sheet.to_string(), row, col);
297        self.unregister_formula(&node);
298        self.sheets
299            .entry(node.0.clone())
300            .or_default()
301            .set(row, col, cell);
302        self.values.insert(node, value);
303    }
304
305    /// Inserts a cached value directly (codec load path — a formula's
306    /// stored result).
307    pub(crate) fn insert_cached(&mut self, node: CellId, value: formula_lang::Value) {
308        self.values.insert(node, value);
309    }
310
311    /// Registers a formula loaded from a file: full bookkeeping, but not
312    /// dirty — the file's cached results are authoritative until an edit.
313    pub(crate) fn register_loaded_formula(
314        &mut self,
315        sheet: &str,
316        row: u32,
317        col: u32,
318        text: &str,
319    ) -> Result<(), EngineError> {
320        self.register_formula(sheet, row, col, text, false)
321    }
322
323    /// The workbook's topological order, cached across recalculations.
324    /// Invalidated whenever edges change.
325    fn topo(&mut self) -> Vec<CellId> {
326        if let Some(order) = &self.order_cache {
327            return order.clone();
328        }
329        let order = workbook::topological_order(self);
330        self.order_cache = Some(order.clone());
331        order
332    }
333
334    /// The sheet's local graph, for the workbook algorithms.
335    pub(crate) fn graph_for(&self, sheet: &str) -> Option<&DependencyGraph> {
336        self.graphs.get(sheet)
337    }
338
339    /// Cross-sheet precedents of a formula cell.
340    pub(crate) fn cross_precedents(&self, node: &CellId) -> Option<&BTreeSet<CellId>> {
341        self.cross_precedents.get(node)
342    }
343
344    /// Cross-sheet dependents of any cell.
345    pub(crate) fn cross_dependents(&self, node: &CellId) -> Option<&BTreeSet<CellId>> {
346        self.cross_dependents.get(node)
347    }
348
349    /// Every formula cell, for the workbook algorithms.
350    pub(crate) fn formula_nodes(&self) -> BTreeSet<CellId> {
351        self.formulas.keys().cloned().collect()
352    }
353
354    /// The cached value of one cell (resolver-facing read).
355    pub(crate) fn cached(&self, node: &CellId) -> Option<formula_lang::Value> {
356        self.values.get(node).cloned()
357    }
358
359    /// Registers formula text at a cell: parse, stub-rewrite, edge
360    /// bookkeeping. The cell's previous formula (if any) is replaced.
361    fn set_formula(
362        &mut self,
363        sheet: &str,
364        row: u32,
365        col: u32,
366        text: &str,
367    ) -> Result<(), EngineError> {
368        self.register_formula(sheet, row, col, text, true)
369    }
370
371    /// Registration core. `mark_dirty` is `true` for user edits (the cell
372    /// needs recomputation) and `false` for file loads (the file's cached
373    /// results are authoritative until something changes).
374    fn register_formula(
375        &mut self,
376        sheet: &str,
377        row: u32,
378        col: u32,
379        text: &str,
380        mark_dirty: bool,
381    ) -> Result<(), EngineError> {
382        // Parse and plan first — nothing mutates until this cannot fail.
383        let prepared = crate::qualified::prepare(text)?;
384        let registration = if prepared.stubs.is_empty() {
385            Some(String::from(text))
386        } else {
387            prepared.local_registration_text()
388        };
389        let has_stubs = !prepared.stubs.is_empty();
390        let volatile = prepared.volatile;
391        // Cross-sheet precedents: every cell of every qualified rectangle
392        // — a range edit anywhere inside must reach the reader (local
393        // ranges get the same expansion inside `sheet-core`).
394        let targets: BTreeSet<CellId> = prepared
395            .stubs
396            .iter()
397            .flat_map(|s| {
398                let sheet = s.target.0.clone();
399                let base = (s.target.1, s.target.2);
400                (0..s.rows).flat_map(move |r| {
401                    let sheet = sheet.clone();
402                    (0..s.cols).map(move |c| (sheet.clone(), base.0 + r, base.1 + c))
403                })
404            })
405            .collect();
406
407        let node = (sheet.to_string(), row, col);
408        // Retire the previous formula's bookkeeping (no-op when the cell
409        // was not a formula).
410        self.unregister_formula(&node);
411
412        // Local edges: pure-local formulas register their own text;
413        // qualified formulas register the reconstructed local-only text so
414        // the sheet's graph never sees stub coordinates.
415        let graph = self.graphs.entry(node.0.clone()).or_default();
416        if let Some(reg) = registration.as_deref() {
417            graph.add_formula((row, col), reg)?;
418        }
419
420        self.sheets
421            .entry(node.0.clone())
422            .or_default()
423            .set(row, col, Cell::formula(text));
424        self.formulas.insert(node.clone(), prepared);
425        if has_stubs {
426            self.qualified.insert(node.clone());
427            for t in &targets {
428                self.cross_dependents
429                    .entry(t.clone())
430                    .or_default()
431                    .insert(node.clone());
432            }
433            self.cross_precedents.insert(node.clone(), targets);
434        }
435        if volatile {
436            self.volatile.insert(node.clone());
437        }
438        if mark_dirty {
439            self.dirty.insert(node);
440        }
441        self.order_cache = None;
442        Ok(())
443    }
444    /// Removes a cell's formula bookkeeping: parsed form, edge flags,
445    /// cached value, and the local graph's edges for the cell. No-op for a
446    /// cell that was not a formula.
447    fn unregister_formula(&mut self, node: &CellId) {
448        if self.formulas.remove(node).is_none() {
449            return;
450        }
451        self.order_cache = None;
452        let (sheet, row, col) = (node.0.clone(), node.1, node.2);
453        if let Some(graph) = self.graphs.get_mut(&sheet) {
454            graph.remove_formula((row, col));
455        }
456        if let Some(targets) = self.cross_precedents.remove(node) {
457            for t in targets {
458                if let Some(readers) = self.cross_dependents.get_mut(&t) {
459                    readers.remove(node);
460                    if readers.is_empty() {
461                        self.cross_dependents.remove(&t);
462                    }
463                }
464            }
465        }
466        self.qualified.remove(node);
467        self.volatile.remove(node);
468        self.values.remove(node);
469    }
470
471    /// Evaluates one formula cell and caches the result. Errors are
472    /// values: `#DIV/0!` from arithmetic lands in the cache as
473    /// `Value::Error` exactly like a referenced error cell does.
474    fn evaluate_node(&mut self, node: &CellId) {
475        let Some(prepared) = self.formulas.get(node) else {
476            return;
477        };
478        let resolver = EngineResolver::new(self, &node.0, prepared);
479        let evaluated = formula_lang::evaluate(&prepared.expr, &resolver);
480        let value = match evaluated {
481            Ok(v) => v,
482            // Evaluation-produced worksheet errors carry the literal.
483            Err(formula_lang::FormulaError::Eval(e)) => formula_lang::Value::Error(e),
484            // Parse-validated failures (unknown function, recursion limit,
485            // invalid range) cannot reach evaluation; `#VALUE!` is the
486            // spreadsheet-honest answer if one ever does.
487            Err(_) => formula_lang::Value::Error(ExcelError::Value),
488        };
489        self.values.insert(node.clone(), value);
490    }
491}
492
493impl core::fmt::Debug for Engine {
494    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
495        f.debug_struct("Engine")
496            .field("sheets", &self.sheets)
497            .field("graphs", &self.graphs)
498            .field("formulas", &self.formulas.keys().collect::<Vec<_>>())
499            .field("qualified", &self.qualified)
500            .field("volatile", &self.volatile)
501            .field("values", &self.values)
502            .field("dirty", &self.dirty)
503            .finish_non_exhaustive()
504    }
505}
506
507/// Parses a non-formula literal into its stored cell and cached value.
508/// Total: anything not a number, boolean, or error literal is text.
509fn literal(input: &str) -> (Cell, formula_lang::Value) {
510    if let Some(v) = ExcelError::from_literal(input) {
511        return (Cell::error(sheet_error(v)), formula_lang::Value::Error(v));
512    }
513    match input.to_ascii_uppercase().as_str() {
514        "TRUE" => return (Cell::boolean(true), formula_lang::Value::Boolean(true)),
515        "FALSE" => return (Cell::boolean(false), formula_lang::Value::Boolean(false)),
516        _ => {}
517    }
518    if let Some(n) = numeric(input) {
519        return (Cell::number(n), formula_lang::Value::Number(n));
520    }
521    (
522        Cell::text(String::from(input)),
523        formula_lang::Value::Text(String::from(input)),
524    )
525}
526
527/// Excel-flavored numeric literal: a finite float whose first character
528/// could begin a number. `f64::from_str` also accepts `"inf"`/`"NaN"` —
529/// spreadsheets store those as text.
530fn numeric(input: &str) -> Option<f64> {
531    let first = input.chars().next()?;
532    if !(first.is_ascii_digit() || first == '+' || first == '-' || first == '.') {
533        return None;
534    }
535    input.parse::<f64>().ok().filter(|v| v.is_finite())
536}
537
538/// Maps `formula-lang`'s error values onto `sheet-core`'s (which has two
539/// more for array semantics; the engine's literal cells use the nearest
540/// canonical spelling).
541fn sheet_error(e: ExcelError) -> sheet_core::ExcelError {
542    match e {
543        ExcelError::DivZero => sheet_core::ExcelError::Div0,
544        ExcelError::NA => sheet_core::ExcelError::Na,
545        ExcelError::Name => sheet_core::ExcelError::Name,
546        ExcelError::Null => sheet_core::ExcelError::Null,
547        ExcelError::Num => sheet_core::ExcelError::Num,
548        ExcelError::Ref => sheet_core::ExcelError::Ref,
549        ExcelError::Value => sheet_core::ExcelError::Value,
550    }
551}