Lesson 24 · A formula's precedents - Build a Spreadsheet Engine

A formula's precedents

To recalculate in the right order, the engine must know which cells each formula reads - its precedents. Today you walk a formula's tree and collect the exact set of cells it depends on.

The goal

Collect the set of cells a formula reads, expanding any ranges to their cells.

Start here - the target

TO DO

Scenario: A formula reports the cells it reads

Givena parsed formula

Whenprecedents walks its tree

Thenprecedents(parse('=A1+B1*2')) is the cells A1, B1 and precedents(parse('=SUM(A1:A3)')) is A1, A2, A3

Andprecedents(parse('=IF(A1>0, B1, C1)')) is A1, B1, C1, listed in reading order

Background

The whole of recalculation rests on one question: which cells does a formula read? Those cells are its precedents. Finding them is a recursive walk of the AST that collects every CellNode’s address and expands every RangeNode to its cells, gathering them into a set so a cell mentioned twice counts once. So A1+B1*2 depends on A1 and B1, and SUM(A1:A3) depends on all three cells the range covers.

Return the precedents in a stable reading order (row by row, left to right) so that every result built on top of them - the graph’s edges, the recalculation order

is deterministic and exactly assertable. Precedents are the raw material for the dependency graph: if C1’s precedents include B1, then there is an edge saying “C1 depends on B1”, and therefore B1 must be computed before C1. The next lesson turns these per-formula precedent sets into that graph.

Make it work

// walk the AST; collect CellNode refs, expand RangeNode to its cells
func precedents(e Expr) []Ref {
  set := map[Ref]bool{}
  var walk func(Expr)
  walk = func(e Expr) {
    switch n := e.(type) {
    case CellNode:  set[n.Ref] = true
    case RangeNode: for _, r := range expand(n.A, n.B) { set[r] = true }
    case BinaryNode: walk(n.L); walk(n.R)
    case CallNode:  for _, a := range n.Args { walk(a) }
    }
  }
  walk(e)
  return sortedReadingOrder(set)
}

CheckpointDONE

A formula can report the exact set of cells it depends on. Commit and stop here.