Incremental Dependency-Graph Recalculation for 184 Excel Formulas in a Browser Web Worker

Spreadsheet UIs fail a simple latency test when built naively in JavaScript: the moment a user edits cell B4 in a 25,000-cell .xlsx model, evaluating every formula on the main thread drops frames and freezes keyboard navigation. When building Arte Sheets—a local-first browser spreadsheet supporting 184 Excel-compatible functions, dynamic arrays, Pivot Tables, and .xlsx / .ods / .csv / .tsv import/export without requiring an account—we moved formula evaluation and file conversion into dedicated Web Workers. Moving work off the main thread is only half the fix. If the worker still recalculates all 10,000 formulas on every keystroke, rapid edits queue up behind stale worker messages. Here is how we designed a hybrid incremental precedent-closure + dynamic-spill fallback engine in under 60 lines of worker coordination code. Problem 1: Why Pure Topological DAGs Break on Real Spreadsheets In textbook spreadsheet tutorials, cell dependencies form a static Directed Acyclic Graph (DAG): C2 = A2 * B2 depends statically on A2 and B2. Edit A2, walk outgoing edges from A2, recalculate C2, done. Real-world .xlsx workbooks immediately break static DAG assumptions in three ways: Volatile & Dynamic-Reference Functions: INDIRECT(), OFFSET(), NOW(), TODAY(), RAND(), and RANDBETWEEN() either change their target coordinates at runtime or mutate without any cell edit. Dynamic Array Spills: Modern Excel functions like FILTER(), UNIQUE(), SORT(), SORTBY(), SEQUENCE(), and TRANSPOSE() write output into neighboring empty cells (spill regions) whose dimensions depend on runtime data values. Structural Mutations: Renaming a sheet, changing merged regions, or updating named ranges invalidates range resolution globally. If you try to handle OFFSET and FILTER spills inside an incremental single-cell walker, subtle stale-cache bugs creep in. Conversely, if you fall back to full recalculation for every workbook, simple financial sheets feel sluggish. Problem 2: Splitting Safe Incremental Edits from Spill/Volatile Passes Inside our calculation worker, we classify every formula cell on upsert using a fast regex check for volatile and dynamic-spill functions, tracking them in an unsafe set alongside sheet spillOwners: const DYNAMIC_OR_VOLATILE = /\b(INDIRECT|OFFSET|NOW|TODAY|RAND|RANDBETWEEN|SEQUENCE|FILTER|UNIQUE|SORT|SORTBY|TRANSPOSE|RANDARRAY)\s*\(/i; // During cell upsert in the worker: const isFormula = typeof cell.raw === 'string' && cell.raw.startsWith('='); const identity = `${sheet.id}!${key}`; if (isFormula && DYNAMIC_OR_VOLATILE.test(cell.raw)) { unsafe.add(identity); } else { unsafe.delete(identity); } When an edit message arrives from the UI coordinator, the worker decides in O(1) whether it must run a full topological pass or can execute a targeted incremental closure: const nextLayout = JSON.stringify([ data.sheets.map(s => [s.id, s.name, s.mergedRegions]), data.namedRanges, data.locale, data.currency, ]); const needsFullPass = !store || data.reset || store.workbookId !== data.workbookId || layout !== nextLayout || unsafe.size > 0 || store.sheets.some(s => s.spillOwners.size > 0); Problem 3: Closing the Precedent Graph Before Evaluation For the common case—workbooks filled with SUM, XLOOKUP, INDEX/MATCH, SUMIFS, IFERROR, PMT, and standard arithmetic—needsFullPass is false. Instead of evaluating dependents immediately as we discover them (which risks reading half-updated intermediate cells in diamond dependencies like A1 -> B1, C1 -> D1), we first close the transitive dirty set across recorded range precedents [r1..r2, c1..c2], and then evaluate dirty formulas cleanly: // Close the dependency graph before evaluation so chains see fresh values. for (let i = 0; i < points.length; i++) { const [sheetName, key] = points[i]; const [r, c] = key.split(',').map(Number); for (const [dependent, ranges] of store.precedents) { if (dirty.has(dependent)) continue; const hitsRange = ranges.some( x => x.sheetName === sheetName && r >= x.r1 && r = x.c1 && c