Notes
Requirements
Fix the scope. Set a cell to a number, some text, or a formula that starts with an equals sign. Formulas support plus, minus, times, divide, brackets, unary minus and a SUM function over ranges or a list of arguments. When a cell changes, everything that depends on it updates. A cycle is rejected with a clear message. Division by zero and maths on text show error values. And every edit can be undone and redone.
Ask the questions that shape the code. An empty cell in a formula counts as zero. When an edit would create a cycle, do we store an error in the cell or reject the edit? We reject it and leave the sheet unchanged, which is simpler to reason about. Bad syntax is also rejected, with the position. If a cell I read has an error, I show that error too. More functions, copy and paste, formatting and live collaboration are out of scope for now.
- set(cell, input)
- number, text, or a formula
- formula starts with =
- operators: + - * / and ( )
- SUM(A1:A3) and SUM(a, b, c)
- change a cell: dependents update
- cycles rejected with a message
- errors: #DIV/0!, #VALUE!
- undo and redo every edit
- display(cell) shows the value
- empty cell in a formula?
- counts as zero
- cycle: store an error or reject?
- reject, sheet unchanged
- bad syntax like =B1+*2?
- reject with the position
- error in a cell I read?
- it flows to me too
- out of scope: more functions,
- copy paste, formatting,
- multi-user editing
Entities
The entities. The spreadsheet holds cells by address. A cell keeps what the user typed, an expression tree built from it, the computed value and an error if there is one. The parser turns formula text into that tree. A dependency graph knows which cells read which. And every edit is a command object, so it can be undone. Notice the split: parsing, the graph and history are separate classes, and the sheet just wires them together.
Class diagram
A cell stores the raw input exactly as typed, because that is what we show when editing and what undo puts back. A plain number becomes a tiny number expression, so numbers and formulas are evaluated the same way. Text has no expression. The value and the error are results, recomputed whenever needed. Storing the input as the source of truth means everything else can always be rebuilt from it.
final class Cell {
final String input; // "=SUM(B1:B3)"
final Expr expr; // null for text
double value;
String error; // "#DIV/0!" or null
}
"1200" -> Num(1200)
"Rent" -> text, expr null
"=B4*12" -> Binary(*, Ref B4, Num 12) Interpreter pattern
This is the Interpreter pattern. Each kind of piece in the formula language is a small class with one method to evaluate itself: a number, a cell reference, a unary minus, a binary operator, and SUM. A formula is a tree of these. The tree has a second job too: collect refs walks it and returns every cell the formula reads, and that list becomes the edges in the dependency graph. One tree gives both the value and the dependencies.
interface Expr {
double eval(Values values);
void collectRefs(Set<String> out);
}
record Num(double value)
record Ref(String cell)
record Neg(Expr inner)
record Binary(char op, Expr l, Expr r)
record Sum(List<Expr> args)
=B4*12 is Binary(*, Ref(B4), Num(12)) The parser
The parser is recursive descent, one method per grammar rule. An expression is terms joined by plus or minus. A term is factors joined by times or divide. A factor is a number, a cell, a minus sign before a factor, something in brackets, or a SUM call. Because times lives one level deeper than plus, A1 plus B2 times two groups the multiplication first, with no precedence table at all. Inside SUM, a range like B1 to B3 expands into three cell references.
expr = term ((+ | -) term)*
term = factor ((* | /) factor)*
factor = number | cell | -factor
| ( expr )
| SUM ( arg (, arg)* )
arg = cell : cell | expr
=A1+B2*2:
Binary(+, A1, Binary(*, B2, 2)) Dependency graph
The dependency graph keeps edges in both directions. Reads maps a cell to the cells its formula uses. Read by is the reverse, mapping a cell to the formulas that use it. We need reads to detect cycles and to count inputs, and read by to find what must update after a change. When a cell gets a new formula, set reads removes its old edges from both maps and adds the new ones, so the two maps never disagree.
Map<String, Set<String>> reads;
Map<String, Set<String>> readBy;
B4 = SUM(B1:B3)
reads: B4 -> {B1, B2, B3}
readBy: B1 -> {B4}, B2 -> {B4} ...
B5 = B4*12: readBy B4 -> {B5, C4}
setReads(cell, refs): drop old
edges, add the new ones Cycle detection
Cycle detection happens before anything changes. Before giving a cell new inputs, search from each new input along the reads edges. If the search reaches the cell itself, the edit would close a loop. Setting B1 to B5 divided by twelve fails, because B5 reads B4 and B4 reads B1. The error spells out the whole path, so the user can see where the loop is. A cell that reads itself is the shortest cycle of all.
for (String r : newReads) depth-first search along reads if we reach cell: cycle found B1 = B5/12 B5 reads B4, B4 reads B1 -> cycle: B1 -> B5 -> B4 -> B1 J1 = J1+1 -> cycle: J1 -> J1 checked BEFORE any change
Topological recalc
Recalculation has two steps. First, walk the read by edges from the changed cell to find every affected cell; the rest of the sheet is untouched. Second, sort those cells topologically: count how many of each cell's inputs are also affected, start with the changed cell, and when a cell is done, lower the count of its readers. A reader is ready when its count hits zero. Every cell is evaluated once, and always after its inputs.
Why not simply recompute every reader as you find it? Look at the diamond in the demo. G1 reads both E1 and F1, and F1 reads E1. A naive walk might update G1 straight after E1, using the old value of F1, then update it again later. In a big sheet that repeated work explodes, and a careless version can even leave a stale value. Topological order fixes both problems: G1 simply waits until F1 is done.
1. affected = changed + everything reachable through readBy 2. count inputs inside affected 3. start with changed; when a cell is done, lower its readers count; at zero they are ready F1=E1*10 G1=E1+F1 H1=F1+G1*2 E1 changes -> E1, F1, G1, H1 each cell evaluated exactly once
- G1 reads E1 and F1
- F1 reads E1
- naive depth-first from E1:
- E1, G1 (uses OLD F1!), F1,
- G1 again, ...
- repeated or wrong work
- topological: G1 waits for F1
- correct, and each cell once
Error values
Some problems are not edit errors but value errors. Dividing by zero shows hash div zero in that cell. Doing maths on a text cell shows hash value. And a formula that reads a cell holding an error shows the same error, so the problem is visible everywhere it matters. These are stored on the cell, not thrown at the user, and they clear by themselves on the next recalculation once the input is fixed.
divide by zero -> #DIV/0! formula reads text -> #VALUE! reads a cell with an error -> same error passes through D1 = B1/(E1-3) E1 = 3 -> #DIV/0! D2 = D1+1 -> #DIV/0! E1 = 4 -> D1 = 1200, D2 = 1201 errors clear on the next recalc
Command: undo
Undo uses the Command pattern. Each edit becomes a set cell command that remembers the cell, the input before and the input after. Execute applies the new input; undo applies the old one through exactly the same path, so the graph and every dependent update automatically. Two stacks hold the history, and a fresh edit clears the redo stack. Undo can never form a cycle, because the sheet it returns to was valid before.
final String cell, before, after;
void execute() { apply(cell, after); }
void undo() { apply(cell, before); }
set(): execute, push undo,
clear redo
undo(): pop undo, cmd.undo(),
push redo
redo(): pop redo, execute,
push undo Flow: set a cell
Put it together for one edit, food from three hundred to four hundred and fifty. Parse the input; a syntax error throws here, before any change. Collect the references and check for a cycle; that can also throw, still before any change. Only then rewire the graph and store the cell. Finally get the recalculation order, B2, then the total in B4, then the yearly total and the per person share, and evaluate each one. All validation comes first, so a failed edit leaves nothing half done.
expr = input starts with "=" ? new Parser(rest).parse() : number ? new Num(..) : null reads = refs of expr cycle = graph.findCycle(cell, reads) if (cycle != null) throw graph.setReads(cell, reads) store or remove the Cell for (c : graph.recalcOrder(cell)) evaluate(c)
Concurrency
Concurrency. One edit can ripple through thousands of cells, and the order matters across all of them, so fine-grained locks per cell would be complex and easy to get wrong. Instead, every public method on the sheet is synchronized: edits are applied one at a time, and readers never see a half finished recalculation. The demo runs four threads making five hundred edits each, and the SUM always ends at exactly two thousand. Live collaboration is a different design: a server puts edits in one order.
- one sheet, one lock:
- set, undo, redo, display are
- synchronized
- why not finer locks? a recalc
- touches many cells, and order
- matters across all of them
- demo: 4 threads x 500 edits
- L5 = SUM(L1:L4) ends at 2000
- collaboration: a server orders
- edits, clients replay them
Extensibility
New features land in one layer each. More functions like minimum, maximum, average or if are new expression classes and one branch in the parser. Number formats are a strategy used only when displaying. The sheet is already sparse, since only filled cells are stored. Saving only needs the inputs, because values can always be recomputed. Copy and paste needs relative references that shift, with a marker for references that must stay fixed.
- MIN, MAX, AVG, IF: new Expr
- classes, one parser branch
- cell formats: a Format strategy
- used only by display()
- big sheets: sparse map, already
- lazy recalc: mark dirty, compute
- on read
- save and load: store inputs only
- copy paste: shift relative refs
- ($A$1 stays fixed)
Testing
The full code is below the player. The demo builds a small monthly budget with labels, a SUM total, a yearly total and a share per person, then changes food and prints the recalculation order. It runs the diamond, checks operator precedence, rejects two cycles and a syntax error, shows both error values clearing, undoes and redoes, restores a formula that was typed over, ripples a change through a chain of a thousand cells, and runs the concurrent edits.
Food to 450, recalculated [B2, B4, B5, C4]: B5=21600 E1 to 3, order [E1, F1, G1, H1] Rejected B1 =B5/12 -> cycle: B1 -> B5 -> B4 -> B1 Errors: D1=#DIV/0!, D3=#VALUE! B4 typed over: B4=0, B5=0 Undo restores the formula: B5=21600 Chain: 1000 cells, K1000=1004 Concurrent edits: L5=2000
Follow-ups
Expect follow-ups. With a million cells, only the affected part is recalculated, which is the whole point of the graph. Very long chains can overflow the call stack in a recursive search, so switch to an explicit stack. Functions like now or random are volatile and must recompute every time. Some spreadsheets allow intended cycles with a capped number of rounds. And cells at the same depth of the order can be evaluated in parallel.
- a million cells, one changes?
- only the affected part recalcs
- deep chains: recursion depth
- use an explicit stack
- volatile functions like NOW()?
- always dirty on recalc
- cycle by design (iteration)?
- opt in, cap the rounds
- parallel recalc: cells at the
- same depth run together
Say it like this
The short version to say out loud. A cell keeps its raw input and an expression tree built by a recursive descent parser, the Interpreter pattern. A dependency graph stores edges both ways. Every edit checks for a cycle before changing anything, then rewires the graph and recalculates only the affected cells, in topological order. Each edit is a command that remembers the old input, so undo just applies it again.
- "A cell keeps its input and an
- Expr tree from a recursive
- descent parser. A graph stores
- reads and read-by edges. Edits
- check for a cycle first, then
- rewire and recalculate only the
- affected cells in topological
- order. Each edit is a Command
- that remembers the old input."