Repository Public
1# Calculation graph and recalculation23`CalcEngine` (`Packages/SheetCore/Sources/SheetCore/Engine/CalcEngine.swift`, 477 lines) owns the dependency4graph of one workbook and performs incremental recalculation. This document explains how precedents are5registered, how a change propagates, in which order formulas are evaluated, how cycles, spills, volatile and6visibility-dependent functions are handled, how a recalculation is cancelled, and what the engine7deliberately does not do. The parser and evaluator are described in [formula-engine.md](formula-engine.md);8the threading model of the whole application is in [overview.md](overview.md).910Behaviours marked "observed" were obtained on 2026-11-21 with a throw-away executable linked against11`Packages/SheetEngine` (debug build). Timings come from `docs/benchmarks/engine.txt` and are quoted with12their source.1314## Data structures1516| Structure | Declared in | Role |17|---|---|---|18| `Formula` (class) | `Model/Workbook.swift` | per formula cell: immutable `expr`, last `value`, `spill` area, `precedents: [AreaRef]`, `isVolatile`, `usesVisibility`, `state` (0 clean, 1 dirty, 2 evaluating) |19| `CellKey` | `Engine/DepGraph.swift` | (sheet, row, column) packed in a `UInt64`: `sheet << 34 \| row << 14 \| col` (20 bits of row, 14 bits of column) |20| `DepGraph.singles` | `Engine/DepGraph.swift` | `[CellKey: [CellKey]]` — for a precedent that is **one cell**, the formulas that read it |21| `DepGraph.ranges` | `Engine/DepGraph.swift` | per sheet: `deps: [RangeRef: [CellKey]]` plus a lazily built index (below) for precedents that are **rectangles** |22| `dirty: [UInt64]` | `CalcEngine` | list of formulas scheduled for the next pass |23| `dirtyCols: [[Int: Int]]` | `CalcEngine` | per sheet, column → number of dirty formulas in it |24| `pendingDirty` | `CalcEngine` | number of dirty formulas |25| `volatiles`, `visibilityCells` | `CalcEngine` | sets of formula keys with a volatile call / a `SUBTOTAL` or `AGGREGATE` call |26| `spills`, `blocked` | `CalcEngine` | spill anchor → occupied area; anchor showing `#SPILL!` → area it needs |2728Source: `Packages/SheetCore/Sources/SheetCore/Engine/CalcEngine.swift`, `DepGraph.swift`, `Model/Workbook.swift`.2930The graph is a **reverse** index (precedent → dependents). The forward direction is the `precedents` array31kept on each `Formula`, which is what `unregister` uses to remove a formula from the graph and what the32audit tools read (`CalcEngine.precedents(sheet:row:col:)`, `dependents(sheet:row:col:)`).3334### Dependency registration3536`register` is called when a formula is written into a cell and for every formula when the graph is rebuilt.37`collectPrecedents` walks the AST once and collects distinct areas:3839- `.cell` → a 1×1 area; `.range` → its rectangle (whole columns span all 1 048 576 rows, whole rows all40 16 384 columns);41- `.structured` → the rectangle the structured reference resolves to at that moment;42- `.name` → the precedents of the defined name's formula (expanded recursively, up to 16 levels), or the data43 range of a table of that name;44- `.call` → sets the volatile flag when the registered function is volatile; when the name is not a45 registered function but a defined name (a named `LAMBDA`), its formula is expanded like a name.4647What this static walk **cannot** see are references computed at run time (`INDIRECT`, `OFFSET`) — which is48why those two functions are volatile — and the areas returned by `INDEX`, `XLOOKUP` or `CHOOSE` beyond the49ranges written in their arguments (these are covered because the written arguments contain them).5051A single-cell precedent goes into the `singles` hash map. A rectangular precedent goes into the per-sheet52`deps` dictionary, keyed by the rectangle itself, so that 10 000 formulas reading the same `$A$1:$A$1000`53share one entry.5455### The interval index for ranges5657Finding "which registered rectangles contain cell (r, c)?" must not scan every rectangle. `DepGraph` answers58it with an index built lazily on the first query after the set of distinct rectangles changed59(`buildIndex`):6061- rectangles at most 64 columns wide (`wideLimit`) are bucketed by **16-column blocks**62 (`blockShift = 4`); a rectangle is listed in every block it touches;63- each block holds an `IntervalIndex`: the rectangles sorted by first row, with an implicit balanced tree64 (`maxEnd` array) giving the largest last row of each subtree — a static interval tree queried in65 O(log n + hits);66- rectangles wider than 64 columns (whole rows, very wide ranges) are kept in a plain list and tested one by67 one.6869Adding a dependent to an already known rectangle does not invalidate the index; adding or removing a70**distinct** rectangle sets `blocks = nil` and the index of that sheet is rebuilt at the next query.7172<!-- diagram: calculation-graph-structures -->73```mermaid74flowchart TD75 E["Edit of cell (s, r, c)"] --> Q["DepGraph.dependents(s, r, c)"]76 Q --> S["singles[CellKey]<br/>hash lookup"]77 Q --> B["blocks[c >> 4]<br/>IntervalIndex query on r"]78 Q --> W["wide list<br/>ranges wider than 64 columns"]79 B --> D["deps[RangeRef]"]80 W --> D81 S --> M["markDirty(dependent)"]82 D --> M83 M --> R["propagate: the same lookup is repeated<br/>for each newly dirty formula"]84```85SVG fallback: 8687## Dirty propagation8889`writeCell` is the single path for a content change. It unregisters the old formula (if any), records the90change for undo, stores the new cell under the engine lock, notifies spills (`touchSpills`), registers the91new formula (which marks it dirty) and calls `propagate(sheet, row, col)`.9293`propagate` is an iterative depth-first walk over the reverse graph with an explicit stack: for each popped94key it asks `DepGraph.dependents`, and every dependent whose `state` is 0 is marked dirty and pushed. A95formula already dirty is not visited again, so the walk is linear in the number of formulas reached.96`markDirty` sets `state = 1`, appends the key to `dirty`, increments `dirtyCols[sheet][col]` and97`pendingDirty`.9899Nothing is evaluated during propagation. Evaluation happens when the host calls `recalculate()`; in the100application that is `WorkbookSession.runCalc`, called at the end of every mutation (`finishMutation`).101102## Evaluation order103104`recalculate` first marks every volatile formula and its dependents dirty, then runs one pass:1051061. `dirty` is **sorted** by key, that is by sheet, then row, then column. Row-major order means that the107 common spreadsheet layout — a formula depending on cells above it or to its left — finds its precedents108 already clean, without any recursion (comment in `recalcBody`).1092. Each dirty formula is evaluated with `evalCell`: `state = 2` (evaluating), the expression is evaluated,110 the result is stored (`store`), `state = 0`.1113. **On-demand recursion.** Whenever the evaluator reads cells, `EvalContext` calls the engine hook112 `ensureClean(area)`. For a single cell this checks that cell's formula; for a rectangle it scans only the113 columns that `dirtyCols` reports as containing dirty formulas. Every dirty formula found is evaluated114 immediately, recursively (`need` → `evalCell`), before the reader continues. Order is therefore correct115 for any layout, not just the row-major one.1164. **Depth interrupt.** Recursion depth is tracked in `EvalContext.depth`. When a needed cell would exceed117 `maxDepth` (1 500 nested cell evaluations) `need` throws `EvalInterrupt(sheet,row,col)` instead of118 recursing. The exception unwinds to the top-level loop, which resets every formula on the evaluation119 stack to dirty, pushes the interrupting cell on an explicit work stack, evaluates **it** first (starting120 again at depth 0) and then retries what is underneath. A dependency chain of any length is thus evaluated121 with bounded native recursion.1225. **Large stack.** Formula evaluation itself is recursive (expression nesting × cell nesting), so the whole123 pass runs on a dedicated thread created by `CalcEngine.runDeep` with a stack of `1 << 29` bytes (512 MiB of124 reserved address space) and user-initiated QoS; the caller waits on a semaphore. A nested call on that125 thread runs inline.126127<!-- diagram: calculation-graph-recalc -->128```mermaid129sequenceDiagram130 participant H as Host (session)131 participant E as CalcEngine pass132 participant X as EvalContext133 participant G as Dirty formula G134 H->>E: recalculate(progress, isCancelled)135 E->>E: mark volatiles dirty, sort dirty row-major136 E->>X: evalCell(F), F.state = 2137 X->>E: ensureClean(area read by F)138 E->>G: G dirty: evalCell(G) first139 G-->>E: value stored, G.state = 0140 E-->>X: area is clean141 X-->>E: value of F142 E->>E: store(F), propagate changed spill cells143 Note over E,X: depth >= 1500: EvalInterrupt, unwind, evaluate the deep cell first, retry144 E-->>H: RecalcStats(evaluated, seconds, cancelled, remaining)145```146SVG fallback: 147148Observed: 200 000 formulas each depending on the cell **below** it (the worst case for row-major order) are149evaluated in one pass, `evaluated = 200000`, `remaining = 0`. The engine benchmark measures the same150mechanism at a larger size:151152| Scenario (release build) | Time |153|---|---:|154| chain of 1 000 000 dependent formulas, first calculation | 0.3920 s |155| chain: change the first cell (1 000 000 dependents) | 0.3250 s |156| full recalculation, 800 000 formulas (1 200 000 cells) | 1.2120 s |157| incremental recalculation after 1 edit (1 200 000 cells), 8 formulas evaluated | 0.0002 s |158| recalculation after editing a whole column (100 000 edits), 800 000 formulas evaluated | 0.9732 s |159| dependency graph, 800 000 formulas | 1.2041 s |160| dependency graph, 4 000 000 formulas | 6.3115 s |161| full recalculation, 4 000 000 formulas (6 000 000 cells) | 5.0114 s |162| 7 whole-column aggregates over 1 000 000 rows | 0.5351 s |163164Source: `docs/benchmarks/engine.txt` / `engine.json` — `orix-bench`, macOS "Version 27.0 (Build 26A5425a)", 18 cores, 48 GB, run dated 2026-11-21T07:08:59Z. The complete tables are in [../development/performance.md](../development/performance.md).165166### Results of an evaluation167168`store` applies these rules to the value of a formula before writing it:169170- an array of one element becomes that element; a larger array **spills** (next section);171- a lambda becomes `#CALC!`;172- **a blank result becomes the number 0** ("a formula that yields an empty cell displays 0, as in Excel").173 Observed: `=Z50` on an empty `Z50` stores 0, and `ISBLANK` of that formula cell is FALSE. An empty string174 result (`=""`) stays an empty text;175- a `CellError` thrown anywhere in the expression becomes the error value of the cell.176177The value is written while `CalcEngine.lock` is held; that lock is what lets the grid read values for178painting while a background pass is running (`GridView` and the document save path take the same lock).179180## Circular references: `#CIRC!`181182A formula being evaluated has `state == 2`. If evaluation needs a formula that is in that state, `need`183throws `CellError.circular`. There is no iteration and no warning dialog: the cell where the cycle is184detected gets the error value `#CIRC!`, and the other members of the cycle receive it through normal error185propagation.186187Observed:188189| Cells | Result |190|---|---|191| `A1: =B1`, `B1: =A1+1`, `C1: =A1*2` | `A1`, `B1`, `C1` all `#CIRC!` |192| `D1: =D1+1` | `#CIRC!` |193| `C1: =SUM(C1:C3)` (the formula is inside its own range) | `#CIRC!` |194| `A1: =IFERROR(B1,0)`, `B1: =A1+1` | `A1` = 0, `B1` = `#CIRC!` |195196Source: probe run on 2026-11-21 against `CalcEngine`; `CellError.circular` is documented in `Model/Value.swift` as "an ORIX Sheet extension (Excel shows a warning and 0)".197198The last row shows a consequence to be aware of: because `#CIRC!` is an ordinary error value, an199error-trapping function inside the cycle can absorb it, and which cell shows the error then depends on the200evaluation order. Chains of defined names deeper than 64 levels also yield `#CIRC!` (`resolveName`).201`ERROR.TYPE(#CIRC!)` is 15.202203## Spills and conflicts204205When a formula returns an array with more than one element, `store` computes the target rectangle anchored206at the formula cell and decides:207208| Situation | Result |209|---|---|210| target extends beyond row 1 048 576 or column 16 384 | `#SPILL!` |211| target intersects a merged range or a table | `#SPILL!`, anchor recorded in `blocked` |212| a target cell (other than the anchor) holds a formula or a non-blank literal | `#SPILL!`, recorded in `blocked` |213| a target cell is a spill child of **another** anchor | `#SPILL!`, recorded in `blocked` |214| otherwise | the anchor's `Formula.value` is the top-left element; the other elements are written as cells with `isSpill = true` (keeping each cell's style); the area is recorded in `Formula.spill` and `spills` |215216Source: `Packages/SheetCore/Sources/SheetCore/Engine/CalcEngine.swift` (`store`, `clearSpill`, `touchSpills`).217218Further rules implemented:219220- Blank elements of a spilled array are written as 0, like a blank formula result.221- Spill children are real cells in the cell store, which is why ordinary references to them, and222 dependencies on them, work without special cases: every child whose value changed is propagated like an223 edit. A child whose value did not change is not rewritten and does not dirty its dependents.224- When the array shrinks, moves or disappears, `clearSpill` removes the old children (a styled cell keeps its225 style) and propagates from each of them.226- `touchSpills` runs on every content change: writing into the area of an existing spill dirties its anchor227 (which will then show `#SPILL!`), and writing into an area that a blocked anchor needs dirties that anchor228 so that it can spill once the obstacle is gone. Observed: `A5: =SEQUENCE(3)` with text in `A6` shows229 `#SPILL!`; after clearing `A6` and recalculating, `A5:A7` hold 1, 2, 3.230- `A1#` evaluates the anchor first and returns its current spill area (the cell itself when it does not231 spill; `#REF!` when the cell holds no formula). Observed: `F5: =F1#` with `F1: =SEQUENCE(2,2)` spills the232 same 2×2 block.233- Structural edits and undo/redo of snapshots strip all spill children (`stripSpills`); the next234 recalculation regenerates them.235- `CalcEngine.spillArea(sheet:containing:)` gives the UI the area to outline.236237There is no legacy array-formula mode and no implicit intersection for array results: every array result238spills.239240## Volatile functions241242A formula is volatile when its expression (or a defined name it uses) calls a function registered with243`volatile: true`. Nine functions are:244245`CELL`, `INDIRECT`, `INFO`, `NOW`, `OFFSET`, `RAND`, `RANDARRAY`, `RANDBETWEEN`, `TODAY`.246247Source: `docs/compatibility/function-registry.json` (`volatile` flag of each `FunctionSpec`), 2026-11-21.248249At the start of **every** `recalculate` call each volatile formula and all its dependents are marked dirty,250whatever was edited. `hasPendingWork` is true as long as one volatile formula exists, so the session runs a251pass after every mutation even when nothing else is dirty. Observed: with `J1: =RAND()`, `J2: =J1*2` and252`J3: =1+1`, a pass with no edit evaluates exactly 2 formulas. All `NOW()`/`TODAY()` of one pass share the253timestamp taken when the pass creates its `EvalContext`. There is no timer that recalculates `NOW()` on its254own: a volatile value changes when something triggers a pass (an edit, undo/redo, "Recalculate Everything").255256## Visibility-dependent functions257258`SUBTOTAL` and `AGGREGATE` read `SheetMeta.hiddenRows` / `filteredRows` at evaluation time. They are **not**259volatile. Instead `register` flags every formula whose expression contains a call named `SUBTOTAL` or260`AGGREGATE` (`usesVisibility`, `visibilityCells`), and `markVisibilityDependents()` dirties those formulas261and their dependents. It is called automatically:262263- by `CalcEngine.editMeta` when the closure changed `hiddenRows` or `filteredRows`;264- by undo/redo when a metadata change restores different `hiddenRows` / `filteredRows`.265266Observed: `L1: =SUBTOTAL(109,M1:M3)` with 1, 2, 4 gives 7; after `editMeta { $0.hiddenRows.insert(1) }` and267a recalculation it gives 5.268269Two limits follow from the implementation:270271- the flag is found by a syntactic walk of the cell's own expression: a `SUBTOTAL` reached only through a272 defined name is not flagged;273- code that mutates `sheet.meta.hiddenRows` directly, without going through `editMeta`, must call274 `markAllDirty()` or trigger the dependents itself.275276`Packages/FunctionsNumeric/COMPATIBILITY.md` ("Integration note") describes the same mechanism from the277functions' side: the application has nothing to dirty by hand, provided row visibility is changed through278`editMeta`.279280## Cancellation, progress and budget281282```swift283public func recalculate(progress: ((_ done: Int, _ total: Int) -> Void)? = nil,284 isCancelled: (() -> Bool)? = nil) -> RecalcStats285```286287- Every 4 096 formulas evaluated, at the top-level loop, the engine reports progress288 (`done = evaluated`, `total = evaluated + pending`), then polls `isCancelled`.289- The cancel closure is **also polled inside on-demand chains**: `evalCell` calls it each time the count of290 evaluations in the pass reaches a multiple of 4 096 and throws the private `EvalCancelled` error when it291 returns true. The top level catches it, puts the formulas of the evaluation stack back to dirty and stops.292 A long chain pulled from a single dirty entry is therefore interruptible. Test293 `cancellationInsideALongChain` (`Packages/SheetCore/Tests`): on a 200 000-formula chain in which each cell294 depends on the one below, a pass whose closure returns true from its fourth poll stops with295 `cancelled` true, fewer than 199 999 evaluations and a non-zero `pendingCount`; a second, uncancelled pass296 finishes the chain and `A1` holds 200 000.297- On cancellation `RecalcStats.cancelled` is true, the formulas not yet evaluated stay dirty298 (`remaining`) and the next `recalculate` call resumes with them. No formula is left half-written: a cell is299 either evaluated and stored or still dirty.300- A pass also stops when the number of evaluations exceeds `pendingDirty × 64 + 100 000` (computed when the301 pass starts). This is a safety bound against formulas that keep re-dirtying each other (for example through302 spills). The stop is reported: `RecalcStats.budgetExceeded` is true (`cancelled` stays false) and the303 remaining formulas stay dirty. The budget is tested at the top-level loop, at the same 4 096-evaluation304 checkpoint as progress, not inside an on-demand chain. No code in `Packages/SheetUI` or `App/Sources`305 reads `budgetExceeded`: the host sees it only through `remaining`.306307How the application uses this (`WorkbookSession.runCalc`):308309- at most `syncCalcThreshold` pending formulas (default 20 000; the app sets it from the setting310 "Calculate in the background above N pending formulas", adjustable from 1 000 to 1 000 000 in311 `App/Sources/AppSettings.swift`): the pass runs synchronously — the main actor waits312 for the deep-stack thread;313- above that: `isCalculating` is set and the pass runs on the serial queue `ai.spboucher.orix.sheet.calc`314 with a progress reporter throttled to one main-queue update per 0.08 s (the sheet-tab bar shows a linear315 progress view) and an atomic cancel flag;316- every mutation, undo, redo or new `runCalc` first calls `haltCalculation()`: set the flag, wait for the317 queue to drain (`calcQueue.sync {}`), clear the flag. Edits therefore never run concurrently with a pass;318 a cancelled pass's result is discarded and a new pass starts after the edit.319320The engine itself is **not re-entrant**: "all mutations and `recalculate` calls must be serialized by the321caller" (class comment). Only the reads guarded by `lock` are safe from another thread.322323## Structural edits rebuild the graph324325Inserting or deleting rows or columns, sheet operations (add, remove, rename, move, duplicate), block moves326("Move Cells"), defining or deleting a name and undoing any of these go through `CalcEngine.structural`,327which:3283291. takes a whole-workbook snapshot for undo (sheets share `Formula` objects with the snapshot, which is why330 rewritten formulas are always new objects);3312. strips spill children;3323. performs the change and rewrites every formula, conditional-format formula, validation formula and333 defined name with a `RefTransform`;3344. calls `rebuildGraph()`: the graph is emptied and **every formula of the workbook is registered again and335 marked dirty**, so the following pass is a full recalculation.336337This is the main known slow path of the engine:338339| Operation (1 200 000 cells, 800 000 formulas, release build) | Time |340|---|---:|341| insert 5 rows + recalculation | 3.0839 s |342| undo that insertion + recalculation | 1.9569 s |343344Source: `docs/benchmarks/engine.txt`, same run as above.345346Sorting is not a structural edit: `CalcEngine.sort` rewrites the sorted cells one by one through `writeCell`347(formulas are shifted with `RefTransform.shift`), so it pays the per-cell unregister/register/propagate cost348instead of a rebuild. The same benchmark run measures "sort 100 000 rows × 4 columns + recalc" at 2.5159 s.349350Opening a document is the one case where building the graph does not imply a recalculation:351`CalcEngine(workbook:trustCachedValues: true)` registers every formula without marking it dirty and keeps352the cached results stored in the file; `WorkbookSession` then skips its initial `runCalc()`. Whether a given353document is opened that way is decided by `WorkbookDocument` (`trustValues`) (see [persistence.md](persistence.md) and [../compatibility/formats.md](../compatibility/formats.md)).354355## Ad-hoc evaluation356357`CalcEngine.evaluate(_:sheet:at:)` evaluates a formula text or an `Expr` in the context of a cell without358storing anything; conditional formatting, data validation and the formula-bar preview use it. It first runs359`recalculate()` if anything is dirty, then evaluates on a deep-stack thread with a fresh context that has no360engine hook. Text that does not parse returns `#NAME?`. An array result is returned as an array value (its361description is its top-left element).362363## What is not done364365- **No multi-threaded evaluation.** One pass evaluates formulas one after another on a single thread. The366 benchmark machine has 18 cores; the engine uses one of them per workbook pass. Independent workbooks have367 independent engines.368- **No iterative calculation.** There is no "enable iterative calculation" option, no maximum-iterations or369 maximum-change setting; a cycle is always `#CIRC!`.370- **No manual calculation mode in the engine.** `CalcEngine` has no automatic/manual switch; the session371 calls `runCalc` after every mutation. "Recalculate Everything" in the Tools menu (key equivalent `⌘=` in372 `App/Sources/MainMenu.swift`) calls373 `markAllDirty()` and runs a full pass.374- **No partial rebuild on structural edits** (see above), and no incremental maintenance of the interval375 index: it is rebuilt per sheet when the set of distinct range precedents changes.376- **No dependency on anything outside the cell grid**: row visibility is handled by the mechanism above;377 defined names are expanded at registration, so changing a name rebuilds the graph; data-engine tables,378 Python results and chart data are not graph nodes (see [data-engine.md](data-engine.md),379 [python-runtime.md](python-runtime.md), [chart-engine.md](chart-engine.md)).380- **No cross-cell memoization** of lookups or sub-expressions; each formula evaluates its own tree.381- **Sheet index width.** `CellKey` leaves the bits above 34 for the sheet index and its comment documents382 16 bits; there is no explicit check on the number of sheets in the key packing.383