Building a Spreadsheet from Scratch: A Real Formula Engine, Dependency Graph and Topological Recalc

A spreadsheet looks like the hardest component you could pick. Formulas, ranges, absolute references, drag-to-fill, errors that spread, circular reference warnings — it feels like a product, not a widget. It is actually four small machines bolted together, and none of them is more than about forty lines. Here is a working Google-Sheets-style grid in vanilla HTML, CSS and JS — no libraries, no images, and no eval() anywhere.

The sheet is a sparse map, not a grid of DOM nodes

The tempting model is a 2-D array the size of the visible grid, or worse, treating the table cells themselves as the data. Both fall apart immediately. A real sheet is mostly empty, and the DOM is a rendering detail that gets rebuilt constantly.

Store a Map keyed by the A1 address, holding only the cells somebody touched, and treat a missing key as blank.

const BLANK = null;
const SHEET = {
  cells:      new Map(),   // "B2" -> { raw, ast, refs, val }
  dependents: new Map()    // "B2" -> Set("E2","B10")   (who reads me)
};
const cellAt  = a => SHEET.cells.get(a) || null;
const rawAt   = a => { const c = cellAt(a); return c ? c.raw : ""; };
const valueAt = a => { const c = cellAt(a); return c ? c.val : BLANK; };

The demo grid is 10 × 24 = 240 slots but fills about 100 of them. The same structure would survive a million-row sheet without allocating anything extra.

Two fields per cell, and that is the whole illusion

This is the single decision that makes a spreadsheet feel like a spreadsheet. Keep what the user typed (raw) and what the engine produced (val) side by side, forever.

The grid paints val. The formula bar paints raw. That is why clicking E10 shows 182,760 in the cell and =SUM(E2:E8) in the bar. Collapse them into one field and you must choose between a sheet that shows formulas everywhere, or a sheet that has forgotten how its numbers were made and can never recalculate.

function setCell(addr, raw) {
  const cell = { raw, ast: null, refs: [], val: BLANK };
  if (raw.charAt(0) === "=") {
    cell.ast  = parseFormula(raw.slice(1));   // structure
    cell.refs = refsOf(cell.ast);             // dependencies
  } else {
    cell.val = literalOf(raw);                // 42000 / true / "Salaries"
  }
  SHEET.cells.set(addr, cell);
  return recalcFrom(addr);                    // val gets filled in here
}

Address math: why Z is followed by AA

Column letters look like base 26, but there is no digit for zero, so the conversion is off by one in both directions. Check the boundaries rather than the middle: 25 is Z, 26 is AA, 701 is ZZ, 702 is AAA.

function colName(c) {                 // 0 -> A, 25 -> Z, 26 -> AA
  let s = "", n = c + 1;
  while (n > 0) {
    const r = (n - 1) % 26;
    s = String.fromCharCode(65 + r) + s;
    n = Math.floor((n - 1) / 26);
  }
  return s;
}
function colIndex(s) {                // "A" -> 0, "AA" -> 26
  let n = 0;
  const up = s.toUpperCase();
  for (let i = 0; i < up.length; i++) n = n * 26 + (up.charCodeAt(i) - 64);
  return n - 1;
}

This pair is used by the parser, the renderer, the range expander and the fill handle. A bug here shows up as five unrelated-looking bugs later, so it is worth a sweep test over a few thousand columns.

Tokenizing, and the LOG10 problem

Before anything can understand =ROUND(E10/$B$12,2) it has to stop being a string. The scanner walks the characters once and emits typed tokens.

Identifiers are the interesting case, because SUM, A1 and LOG10 all look the same to a regex — LOG10 is three letters followed by digits, which is exactly the shape of a cell address. Real spreadsheets resolve this by looking ahead: peek past any spaces at the next character, and if it is an opening bracket the identifier is a function name.

const ADDR_RE = /^(\$?)([A-Za-z]{1,3})(\$?)([1-9][0-9]{0,6})$/;

if (/[A-Za-z_$]/.test(ch)) {
  while (i < s.length && /[A-Za-z0-9_$.]/.test(s[i])) i++;
  const text = s.slice(start, i), up = text.toUpperCase();
  let j = i; while (s[j] === " ") j++;              // peek past spaces
  if (up === "TRUE" || up === "FALSE") push("bool");
  else if (s[j] === "(")               push("func");   // SUM(  LOG10(
  else if (ADDR_RE.test(text))         push("ref");    // A1  $B$12
  else                                 push("name");   // -> #NAME?
}

Record each token's position too. The fill handle needs it later.

A Pratt parser gives you precedence for free

A flat token list still does not know that 1+2*3 is seven. Give every binary operator a binding power, then write one loop: parse a left operand, and while the next operator binds at least as tightly as the caller demanded, consume it and recurse.

const BINP = { "=":1,"<>":1,"<":1,">":1,"<=":1,">=":1, "&":2, "+":3,"-":3, "*":4,"/":4, "^":5 };

function parseExpr(minp) {
  let left = parseUnary();
  for (;;) {
    const t = peek();
    if (!t || t.type !== "op") break;
    const bp = BINP[t.text];
    if (bp === undefined || bp < minp) break;
    next();
    const right = parseExpr(bp + 1);      // +1 => left-associative
    left = { t: "bin", op: t.text, l: left, r: right };
  }
  return left;
}

Recursing with bp + 1 makes everything left-associative, which is what you want here — including the exponent. Spreadsheets evaluate 2^3^2 as 64, not the mathematician's 512. Parentheses need no rule at all; they simply restart the expression parser. Unary minus is parsed above ^, so -2^2 is 4, matching Excel.

Fifteen lines replaces a stack of hand-written precedence functions, and adding an operator is one table entry.

A range is a rectangle, expanded only when asked

A1:C3 is two corners, not nine cells. Keep it that way in the tree and let only the argument-flattening step turn it into addresses.

function rangeAddrs(a, b) {
  const r1 = Math.min(a.r, b.r), r2 = Math.max(a.r, b.r);
  const c1 = Math.min(a.c, b.c), c2 = Math.max(a.c, b.c);
  const out = [];
  for (let r = r1; r <= r2; r++)
    for (let c = c1; c <= c2; c++) out.push(addrOf(r, c));
  return out;
}

Three things fall out. Reversed ranges normalise, so C3:A1 and A1:C3 are the same nine cells in the same order. A range used where a single value was expected stays honestly wrong — =A1:C3+1 is #VALUE! rather than a silent guess. And the dependency walk gets the exact list of cells a formula reads without evaluating anything.

The dependency graph is a by-product of parsing

You never need to analyse formulas a second time. The parser already found every reference; walk the tree once and collect them.

function refsOf(ast) {
  const out = [];
  (function walk(n) {
    if (!n || typeof n !== "object") return;
    if (n.t === "ref")   return void out.push(addrOf(n.a.r, n.a.c));
    if (n.t === "range") return void rangeAddrs(n.a, n.b).forEach(a => out.push(a));
    if (n.t === "bin")   { walk(n.l); walk(n.r); return; }
    if (n.t === "un" || n.t === "pct") return walk(n.x);
    if (n.t === "call")  n.args.forEach(walk);
  })(ast);
  return Array.from(new Set(out));
}

Store the reverse direction as well, because recalculation asks the reverse question: I changed B3, who cares? Rebuild both on every edit and — this is the one people forget — unhook the old edges first. Skip that and a reference you deleted keeps triggering work forever, which is the classic slow-spreadsheet bug.

Recalculate in topological order, not everywhere

The naive fix after an edit is to recompute every formula on the sheet. It is wrong twice over: it is O(all cells) for a one-cell change, and it can still produce stale numbers, because a formula evaluated before its input reads the previous value.

Collect the edited cell plus its transitive dependents, count in-degrees within that set only, and drain the queue.

function recalcSet(set) {
  const order = [], indeg = new Map();
  set.forEach(a => indeg.set(a, 0));
  set.forEach(a => (cellAt(a) ? cellAt(a).refs : []).forEach(d => {
    if (set.has(d)) indeg.set(a, indeg.get(a) + 1);
  }));

  const q = [...set].filter(a => indeg.get(a) === 0).sort();
  while (q.length) {
    const a = q.shift(); order.push(a);
    (SHEET.dependents.get(a) || []).forEach(d => {
      if (!set.has(d)) return;
      indeg.set(d, indeg.get(d) - 1);
      if (indeg.get(d) === 0) q.push(d);
    });
  }

  order.forEach(a => { const c = cellAt(a); if (c && c.ast) c.val = evalNode(c.ast, CTX); });
  return order;
}

Every affected cell is evaluated exactly once, always after everything it reads, and untouched cells are never visited. On the demo budget sheet, editing one figure recalculates 17 cells out of about 100 — and on a real financial model the ratio is thousands to one.

Cycle detection is just what the sort left behind

You do not need a separate checker. A topological sort can only order a directed acyclic graph, so if the queue empties while cells remain in the set, those cells are precisely the ones that could never be ordered. That is the definition of a cycle.

const done = new Set(order), circular = [];
set.forEach(a => {
  if (done.has(a)) return;
  const c = cellAt(a);
  if (c) c.val = err("#CIRC!");
  circular.push(a);
});

This catches A1 containing =A1, and the three-cell loop where A1 reads B1 reads C1 reads A1, with identical code — and it catches them before evaluation rather than by blowing the stack. Cells merely sitting downstream of a cycle are caught too, because their in-degree never reaches zero either.

Errors are values, so propagation is automatic

Do not throw. Model an error as an ordinary value — a small tagged object — and check for it at the top of every operator and every function argument, returning it unchanged.

const err   = code => ({ e: code });
const isErr = v => !!v && typeof v === "object" && typeof v.e === "string";

case "bin": {
  const a = evalNode(n.l, ctx); if (isErr(a)) return a;   // propagate
  const b = evalNode(n.r, ctx); if (isErr(b)) return b;
  if (n.op === "&") return strOf(a) + strOf(b);
  const x = numOf(a); if (isErr(x)) return x;             // "abc" -> #VALUE!
  const y = numOf(b); if (isErr(y)) return y;
  if (n.op === "/") return y === 0 ? err("#DIV/0!") : x / y;
  ...
}

Propagation then needs no machinery at all. One bad cell quietly poisons everything downstream, and the graph you already built decides how far the damage spreads. Each code still carries meaning worth preserving: #DIV/0! a zero denominator, #NAME? an unknown function, #REF! a reference off the sheet, #VALUE! text where a number was needed, #CIRC! a loop.

IF is the one function that must be lazy — evaluate the condition, then only the branch that won. Otherwise =IF(TRUE,1,1/0) fails for no reason.

What the fill handle actually copies

It is not copying a value, and it is not copying a formula either. It is copying a formula shifted by the row and column delta. =A1*2 dragged one row down becomes =A2*2, because A1 means "one row above me", not "the cell A1". A dollar sign pins that half of the address.

function shiftRef(text, dr, dc) {
  const m = ADDR_RE.exec(text);
  const absC = m[1] === "$", absR = m[3] === "$";
  let c = colIndex(m[2]), r = +m[4] - 1;
  if (!absC) c += dc;
  if (!absR) r += dr;
  if (r < 0 || c < 0) return "#REF!";
  return (absC ? "$" : "") + colName(c) + (absR ? "$" : "") + (r + 1);
}

function translateFormula(raw, dr, dc) {
  if (typeof raw !== "string" || raw.charAt(0) !== "=") return raw;
  const body = raw.slice(1), toks = tokenize(body);
  let out = body;
  for (let i = toks.length - 1; i >= 0; i--) {        // splice BACK to front
    const t = toks[i];
    if (t.type !== "ref") continue;
    out = out.slice(0, t.pos) + shiftRef(t.text, dr, dc) + out.slice(t.pos + t.text.length);
  }
  return "=" + out;
}

Splicing from the end is the trick that makes it easy: earlier token positions stay valid no matter how much the replacement changes the length. Because only ref tokens are touched, strings, function names and even the user's spacing survive byte-for-byte — =IF(A1>0,"A1 is up","A1 is down") moves the reference and leaves the message alone. Copy and paste is the same function with a different delta.

Selection is a rectangle; editing is a state machine

Never store a selection as a list of cells. It goes stale the moment anything moves, and it turns shift-arrow into four special cases. Store two points — the anchor where the selection began and the focus the arrows move — and derive the rectangle.

const normRect = (a, f) => ({
  r1: Math.min(a.r, f.r), r2: Math.max(a.r, f.r),
  c1: Math.min(a.c, f.c), c2: Math.max(a.c, f.c)
});

Growing, shrinking and reversing all fall out of that one line, and the status bar's live Sum / Average / Count is a walk over the derived addresses.

Editing is a small explicit machine: idle, then typing (a printable key replaces the cell) or editing in place (F2 or double-click, caret at the end), ending in commit or cancel.

function startEdit(seed) {
  state.editing = true;
  state.preEdit = rawAt(activeAddr());   // Escape restores this
  editor.value  = seed;                  // ONE element, never re-created
  placeOverlays(); editor.focus();
  editor.setSelectionRange(seed.length, seed.length);   // caret at the end
}

Two details matter more than they look. Escape must restore the pre-edit raw text, which is trivial here because nothing is written until commit. And the editor must be one persistent input that gets repositioned and shown — the grid is re-rendered from state on every change, and if the render re-creates the input, the caret dies on every keystroke.

Why this shape keeps showing up

Values that declare their inputs, a graph built from those declarations, and a topological pass that touches each node exactly once — that is a spreadsheet, and it is also every reactive signal library, every build system, and every dataflow scheduler you have used.

Model it that way and incremental recalculation, cycle detection and error propagation stop being optimisations you bolt on later. They are consequences of the design.

Drive the whole thing yourself here: https://dev48v.infy.uk/design/day60-spreadsheet-grid.html