SPB Git

Repository Public

calculation-graph.md 23.4 KB

# Calculation graph and recalculation

CalcEngine (Packages/SheetCore/Sources/SheetCore/Engine/CalcEngine.swift, 477 lines) owns the dependency graph of one workbook and performs incremental recalculation. This document explains how precedents are registered, how a change propagates, in which order formulas are evaluated, how cycles, spills, volatile and visibility-dependent functions are handled, how a recalculation is cancelled, and what the engine deliberately does not do. The parser and evaluator are described in formula-engine.md; the threading model of the whole application is in overview.md.

Behaviours marked "observed" were obtained on 2026-11-21 with a throw-away executable linked against Packages/SheetEngine (debug build). Timings come from docs/benchmarks/engine.txt and are quoted with their source.

# Data structures

Structure Declared in Role
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)
CellKey Engine/DepGraph.swift (sheet, row, column) packed in a UInt64: sheet << 34 | row << 14 | col (20 bits of row, 14 bits of column)
DepGraph.singles Engine/DepGraph.swift [CellKey: [CellKey]] — for a precedent that is one cell, the formulas that read it
DepGraph.ranges Engine/DepGraph.swift per sheet: deps: [RangeRef: [CellKey]] plus a lazily built index (below) for precedents that are rectangles
dirty: [UInt64] CalcEngine list of formulas scheduled for the next pass
dirtyCols: [[Int: Int]] CalcEngine per sheet, column → number of dirty formulas in it
pendingDirty CalcEngine number of dirty formulas
volatiles, visibilityCells CalcEngine sets of formula keys with a volatile call / a SUBTOTAL or AGGREGATE call
spills, blocked CalcEngine spill anchor → occupied area; anchor showing #SPILL! → area it needs

Source: Packages/SheetCore/Sources/SheetCore/Engine/CalcEngine.swift, DepGraph.swift, Model/Workbook.swift.

The graph is a reverse index (precedent → dependents). The forward direction is the precedents array kept on each Formula, which is what unregister uses to remove a formula from the graph and what the audit tools read (CalcEngine.precedents(sheet:row:col:), dependents(sheet:row:col:)).

# Dependency registration

register is called when a formula is written into a cell and for every formula when the graph is rebuilt. collectPrecedents walks the AST once and collects distinct areas:

  • .cell → a 1×1 area; .range → its rectangle (whole columns span all 1 048 576 rows, whole rows all 16 384 columns);
  • .structured → the rectangle the structured reference resolves to at that moment;
  • .name → the precedents of the defined name's formula (expanded recursively, up to 16 levels), or the data range of a table of that name;
  • .call → sets the volatile flag when the registered function is volatile; when the name is not a registered function but a defined name (a named LAMBDA), its formula is expanded like a name.

What this static walk cannot see are references computed at run time (INDIRECT, OFFSET) — which is why those two functions are volatile — and the areas returned by INDEX, XLOOKUP or CHOOSE beyond the ranges written in their arguments (these are covered because the written arguments contain them).

A single-cell precedent goes into the singles hash map. A rectangular precedent goes into the per-sheet deps dictionary, keyed by the rectangle itself, so that 10 000 formulas reading the same $A$1:$A$1000 share one entry.

# The interval index for ranges

Finding "which registered rectangles contain cell (r, c)?" must not scan every rectangle. DepGraph answers it with an index built lazily on the first query after the set of distinct rectangles changed (buildIndex):

  • rectangles at most 64 columns wide (wideLimit) are bucketed by 16-column blocks (blockShift = 4); a rectangle is listed in every block it touches;
  • each block holds an IntervalIndex: the rectangles sorted by first row, with an implicit balanced tree (maxEnd array) giving the largest last row of each subtree — a static interval tree queried in O(log n + hits);
  • rectangles wider than 64 columns (whole rows, very wide ranges) are kept in a plain list and tested one by one.

Adding a dependent to an already known rectangle does not invalidate the index; adding or removing a distinct rectangle sets blocks = nil and the index of that sheet is rebuilt at the next query.

flowchart TD
    E["Edit of cell (s, r, c)"] --> Q["DepGraph.dependents(s, r, c)"]
    Q --> S["singles[CellKey]<br/>hash lookup"]
    Q --> B["blocks[c >> 4]<br/>IntervalIndex query on r"]
    Q --> W["wide list<br/>ranges wider than 64 columns"]
    B --> D["deps[RangeRef]"]
    W --> D
    S --> M["markDirty(dependent)"]
    D --> M
    M --> R["propagate: the same lookup is repeated<br/>for each newly dirty formula"]

SVG fallback: Reverse dependency lookup and dirty propagation

# Dirty propagation

writeCell is the single path for a content change. It unregisters the old formula (if any), records the change for undo, stores the new cell under the engine lock, notifies spills (touchSpills), registers the new formula (which marks it dirty) and calls propagate(sheet, row, col).

propagate is an iterative depth-first walk over the reverse graph with an explicit stack: for each popped key it asks DepGraph.dependents, and every dependent whose state is 0 is marked dirty and pushed. A formula already dirty is not visited again, so the walk is linear in the number of formulas reached. markDirty sets state = 1, appends the key to dirty, increments dirtyCols[sheet][col] and pendingDirty.

Nothing is evaluated during propagation. Evaluation happens when the host calls recalculate(); in the application that is WorkbookSession.runCalc, called at the end of every mutation (finishMutation).

# Evaluation order

recalculate first marks every volatile formula and its dependents dirty, then runs one pass:

  1. dirty is sorted by key, that is by sheet, then row, then column. Row-major order means that the common spreadsheet layout — a formula depending on cells above it or to its left — finds its precedents already clean, without any recursion (comment in recalcBody).
  2. Each dirty formula is evaluated with evalCell: state = 2 (evaluating), the expression is evaluated, the result is stored (store), state = 0.
  3. On-demand recursion. Whenever the evaluator reads cells, EvalContext calls the engine hook ensureClean(area). For a single cell this checks that cell's formula; for a rectangle it scans only the columns that dirtyCols reports as containing dirty formulas. Every dirty formula found is evaluated immediately, recursively (need → evalCell), before the reader continues. Order is therefore correct for any layout, not just the row-major one.
  4. Depth interrupt. Recursion depth is tracked in EvalContext.depth. When a needed cell would exceed maxDepth (1 500 nested cell evaluations) need throws EvalInterrupt(sheet,row,col) instead of recursing. The exception unwinds to the top-level loop, which resets every formula on the evaluation stack to dirty, pushes the interrupting cell on an explicit work stack, evaluates it first (starting again at depth 0) and then retries what is underneath. A dependency chain of any length is thus evaluated with bounded native recursion.
  5. Large stack. Formula evaluation itself is recursive (expression nesting × cell nesting), so the whole pass runs on a dedicated thread created by CalcEngine.runDeep with a stack of 1 << 29 bytes (512 MiB of reserved address space) and user-initiated QoS; the caller waits on a semaphore. A nested call on that thread runs inline.
sequenceDiagram
    participant H as Host (session)
    participant E as CalcEngine pass
    participant X as EvalContext
    participant G as Dirty formula G
    H->>E: recalculate(progress, isCancelled)
    E->>E: mark volatiles dirty, sort dirty row-major
    E->>X: evalCell(F), F.state = 2
    X->>E: ensureClean(area read by F)
    E->>G: G dirty: evalCell(G) first
    G-->>E: value stored, G.state = 0
    E-->>X: area is clean
    X-->>E: value of F
    E->>E: store(F), propagate changed spill cells
    Note over E,X: depth >= 1500: EvalInterrupt, unwind, evaluate the deep cell first, retry
    E-->>H: RecalcStats(evaluated, seconds, cancelled, remaining)

SVG fallback: One recalculation pass with on-demand evaluation

Observed: 200 000 formulas each depending on the cell below it (the worst case for row-major order) are evaluated in one pass, evaluated = 200000, remaining = 0. The engine benchmark measures the same mechanism at a larger size:

Scenario (release build) Time
chain of 1 000 000 dependent formulas, first calculation 0.3920 s
chain: change the first cell (1 000 000 dependents) 0.3250 s
full recalculation, 800 000 formulas (1 200 000 cells) 1.2120 s
incremental recalculation after 1 edit (1 200 000 cells), 8 formulas evaluated 0.0002 s
recalculation after editing a whole column (100 000 edits), 800 000 formulas evaluated 0.9732 s
dependency graph, 800 000 formulas 1.2041 s
dependency graph, 4 000 000 formulas 6.3115 s
full recalculation, 4 000 000 formulas (6 000 000 cells) 5.0114 s
7 whole-column aggregates over 1 000 000 rows 0.5351 s

Source: 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.

# Results of an evaluation

store applies these rules to the value of a formula before writing it:

  • an array of one element becomes that element; a larger array spills (next section);
  • a lambda becomes #CALC!;
  • a blank result becomes the number 0 ("a formula that yields an empty cell displays 0, as in Excel"). Observed: =Z50 on an empty Z50 stores 0, and ISBLANK of that formula cell is FALSE. An empty string result (="") stays an empty text;
  • a CellError thrown anywhere in the expression becomes the error value of the cell.

The value is written while CalcEngine.lock is held; that lock is what lets the grid read values for painting while a background pass is running (GridView and the document save path take the same lock).

# Circular references: #CIRC!

A formula being evaluated has state == 2. If evaluation needs a formula that is in that state, need throws CellError.circular. There is no iteration and no warning dialog: the cell where the cycle is detected gets the error value #CIRC!, and the other members of the cycle receive it through normal error propagation.

Observed:

Cells Result
A1: =B1, B1: =A1+1, C1: =A1*2 A1, B1, C1 all #CIRC!
D1: =D1+1 #CIRC!
C1: =SUM(C1:C3) (the formula is inside its own range) #CIRC!
A1: =IFERROR(B1,0), B1: =A1+1 A1 = 0, B1 = #CIRC!

Source: 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)".

The last row shows a consequence to be aware of: because #CIRC! is an ordinary error value, an error-trapping function inside the cycle can absorb it, and which cell shows the error then depends on the evaluation order. Chains of defined names deeper than 64 levels also yield #CIRC! (resolveName). ERROR.TYPE(#CIRC!) is 15.

# Spills and conflicts

When a formula returns an array with more than one element, store computes the target rectangle anchored at the formula cell and decides:

Situation Result
target extends beyond row 1 048 576 or column 16 384 #SPILL!
target intersects a merged range or a table #SPILL!, anchor recorded in blocked
a target cell (other than the anchor) holds a formula or a non-blank literal #SPILL!, recorded in blocked
a target cell is a spill child of another anchor #SPILL!, recorded in blocked
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

Source: Packages/SheetCore/Sources/SheetCore/Engine/CalcEngine.swift (store, clearSpill, touchSpills).

Further rules implemented:

  • Blank elements of a spilled array are written as 0, like a blank formula result.
  • Spill children are real cells in the cell store, which is why ordinary references to them, and dependencies on them, work without special cases: every child whose value changed is propagated like an edit. A child whose value did not change is not rewritten and does not dirty its dependents.
  • When the array shrinks, moves or disappears, clearSpill removes the old children (a styled cell keeps its style) and propagates from each of them.
  • touchSpills runs on every content change: writing into the area of an existing spill dirties its anchor (which will then show #SPILL!), and writing into an area that a blocked anchor needs dirties that anchor so that it can spill once the obstacle is gone. Observed: A5: =SEQUENCE(3) with text in A6 shows #SPILL!; after clearing A6 and recalculating, A5:A7 hold 1, 2, 3.
  • A1# evaluates the anchor first and returns its current spill area (the cell itself when it does not spill; #REF! when the cell holds no formula). Observed: F5: =F1# with F1: =SEQUENCE(2,2) spills the same 2×2 block.
  • Structural edits and undo/redo of snapshots strip all spill children (stripSpills); the next recalculation regenerates them.
  • CalcEngine.spillArea(sheet:containing:) gives the UI the area to outline.

There is no legacy array-formula mode and no implicit intersection for array results: every array result spills.

# Volatile functions

A formula is volatile when its expression (or a defined name it uses) calls a function registered with volatile: true. Nine functions are:

CELL, INDIRECT, INFO, NOW, OFFSET, RAND, RANDARRAY, RANDBETWEEN, TODAY.

Source: docs/compatibility/function-registry.json (volatile flag of each FunctionSpec), 2026-11-21.

At the start of every recalculate call each volatile formula and all its dependents are marked dirty, whatever was edited. hasPendingWork is true as long as one volatile formula exists, so the session runs a pass after every mutation even when nothing else is dirty. Observed: with J1: =RAND(), J2: =J1*2 and J3: =1+1, a pass with no edit evaluates exactly 2 formulas. All NOW()/TODAY() of one pass share the timestamp taken when the pass creates its EvalContext. There is no timer that recalculates NOW() on its own: a volatile value changes when something triggers a pass (an edit, undo/redo, "Recalculate Everything").

# Visibility-dependent functions

SUBTOTAL and AGGREGATE read SheetMeta.hiddenRows / filteredRows at evaluation time. They are not volatile. Instead register flags every formula whose expression contains a call named SUBTOTAL or AGGREGATE (usesVisibility, visibilityCells), and markVisibilityDependents() dirties those formulas and their dependents. It is called automatically:

  • by CalcEngine.editMeta when the closure changed hiddenRows or filteredRows;
  • by undo/redo when a metadata change restores different hiddenRows / filteredRows.

Observed: L1: =SUBTOTAL(109,M1:M3) with 1, 2, 4 gives 7; after editMeta { $0.hiddenRows.insert(1) } and a recalculation it gives 5.

Two limits follow from the implementation:

  • the flag is found by a syntactic walk of the cell's own expression: a SUBTOTAL reached only through a defined name is not flagged;
  • code that mutates sheet.meta.hiddenRows directly, without going through editMeta, must call markAllDirty() or trigger the dependents itself.

Packages/FunctionsNumeric/COMPATIBILITY.md ("Integration note") describes the same mechanism from the functions' side: the application has nothing to dirty by hand, provided row visibility is changed through editMeta.

# Cancellation, progress and budget

swift
public func recalculate(progress: ((_ done: Int, _ total: Int) -> Void)? = nil,
                        isCancelled: (() -> Bool)? = nil) -> RecalcStats
  • Every 4 096 formulas evaluated, at the top-level loop, the engine reports progress (done = evaluated, total = evaluated + pending), then polls isCancelled.
  • The cancel closure is also polled inside on-demand chains: evalCell calls it each time the count of evaluations in the pass reaches a multiple of 4 096 and throws the private EvalCancelled error when it returns true. The top level catches it, puts the formulas of the evaluation stack back to dirty and stops. A long chain pulled from a single dirty entry is therefore interruptible. Test cancellationInsideALongChain (Packages/SheetCore/Tests): on a 200 000-formula chain in which each cell depends on the one below, a pass whose closure returns true from its fourth poll stops with cancelled true, fewer than 199 999 evaluations and a non-zero pendingCount; a second, uncancelled pass finishes the chain and A1 holds 200 000.
  • On cancellation RecalcStats.cancelled is true, the formulas not yet evaluated stay dirty (remaining) and the next recalculate call resumes with them. No formula is left half-written: a cell is either evaluated and stored or still dirty.
  • A pass also stops when the number of evaluations exceeds pendingDirty × 64 + 100 000 (computed when the pass starts). This is a safety bound against formulas that keep re-dirtying each other (for example through spills). The stop is reported: RecalcStats.budgetExceeded is true (cancelled stays false) and the remaining formulas stay dirty. The budget is tested at the top-level loop, at the same 4 096-evaluation checkpoint as progress, not inside an on-demand chain. No code in Packages/SheetUI or App/Sources reads budgetExceeded: the host sees it only through remaining.

How the application uses this (WorkbookSession.runCalc):

  • at most syncCalcThreshold pending formulas (default 20 000; the app sets it from the setting "Calculate in the background above N pending formulas", adjustable from 1 000 to 1 000 000 in App/Sources/AppSettings.swift): the pass runs synchronously — the main actor waits for the deep-stack thread;
  • above that: isCalculating is set and the pass runs on the serial queue ai.spboucher.orix.sheet.calc with a progress reporter throttled to one main-queue update per 0.08 s (the sheet-tab bar shows a linear progress view) and an atomic cancel flag;
  • every mutation, undo, redo or new runCalc first calls haltCalculation(): set the flag, wait for the queue to drain (calcQueue.sync {}), clear the flag. Edits therefore never run concurrently with a pass; a cancelled pass's result is discarded and a new pass starts after the edit.

The engine itself is not re-entrant: "all mutations and recalculate calls must be serialized by the caller" (class comment). Only the reads guarded by lock are safe from another thread.

# Structural edits rebuild the graph

Inserting or deleting rows or columns, sheet operations (add, remove, rename, move, duplicate), block moves ("Move Cells"), defining or deleting a name and undoing any of these go through CalcEngine.structural, which:

  1. takes a whole-workbook snapshot for undo (sheets share Formula objects with the snapshot, which is why rewritten formulas are always new objects);
  2. strips spill children;
  3. performs the change and rewrites every formula, conditional-format formula, validation formula and defined name with a RefTransform;
  4. calls rebuildGraph(): the graph is emptied and every formula of the workbook is registered again and marked dirty, so the following pass is a full recalculation.

This is the main known slow path of the engine:

Operation (1 200 000 cells, 800 000 formulas, release build) Time
insert 5 rows + recalculation 3.0839 s
undo that insertion + recalculation 1.9569 s

Source: docs/benchmarks/engine.txt, same run as above.

Sorting is not a structural edit: CalcEngine.sort rewrites the sorted cells one by one through writeCell (formulas are shifted with RefTransform.shift), so it pays the per-cell unregister/register/propagate cost instead of a rebuild. The same benchmark run measures "sort 100 000 rows × 4 columns + recalc" at 2.5159 s.

Opening a document is the one case where building the graph does not imply a recalculation: CalcEngine(workbook:trustCachedValues: true) registers every formula without marking it dirty and keeps the cached results stored in the file; WorkbookSession then skips its initial runCalc(). Whether a given document is opened that way is decided by WorkbookDocument (trustValues) (see persistence.md and ../compatibility/formats.md).

# Ad-hoc evaluation

CalcEngine.evaluate(_:sheet:at:) evaluates a formula text or an Expr in the context of a cell without storing anything; conditional formatting, data validation and the formula-bar preview use it. It first runs recalculate() if anything is dirty, then evaluates on a deep-stack thread with a fresh context that has no engine hook. Text that does not parse returns #NAME?. An array result is returned as an array value (its description is its top-left element).

# What is not done

  • No multi-threaded evaluation. One pass evaluates formulas one after another on a single thread. The benchmark machine has 18 cores; the engine uses one of them per workbook pass. Independent workbooks have independent engines.
  • No iterative calculation. There is no "enable iterative calculation" option, no maximum-iterations or maximum-change setting; a cycle is always #CIRC!.
  • No manual calculation mode in the engine. CalcEngine has no automatic/manual switch; the session calls runCalc after every mutation. "Recalculate Everything" in the Tools menu (key equivalent ⌘= in App/Sources/MainMenu.swift) calls markAllDirty() and runs a full pass.
  • No partial rebuild on structural edits (see above), and no incremental maintenance of the interval index: it is rebuilt per sheet when the set of distinct range precedents changes.
  • No dependency on anything outside the cell grid: row visibility is handled by the mechanism above; defined names are expanded at registration, so changing a name rebuilds the graph; data-engine tables, Python results and chart data are not graph nodes (see data-engine.md, python-runtime.md, chart-engine.md).
  • No cross-cell memoization of lookups or sub-expressions; each formula evaluates its own tree.
  • Sheet index width. CellKey leaves the bits above 34 for the sheet index and its comment documents 16 bits; there is no explicit check on the number of sheets in the key packing.
Files main
Menu

Theme