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}