cellar
A spreadsheet engine with its own formula language, in pure Dart. A parser, a dependency graph and cell recalculation - the foundation of how a spreadsheet works.
A spreadsheet engine in pure Dart. Underneath, a spreadsheet is a dependency graph between cells: change one and you must recompute exactly those that depend on it, in the right order. On top of that sits a custom formula language with a parser.
Overview
Visually a spreadsheet is a grid of cells, but that is an illusion over what happens underneath. Logically it is a directed graph: a cell with a formula depends on other cells, those on further ones. All of cellar's engineering comes down to recomputing that graph correctly and only in the part that truly needs it.
The rest, the formula parser and the functions, wraps around this one mechanism. If the dependency graph is done wrong, no rich formula language will save it, because the sheet will start showing numbers computed on stale data.
A spreadsheet is a graph, not a table
When you change one value, you cannot recompute everything, because that is wasteful, nor recompute in a random order, because you get garbage. You must touch exactly the cells that depend on the changed one, and do it in an order where each computes on already up-to-date data from its predecessors.
That is the heart of cellar and also the point where larger sheets get hard. A naive solution that recomputes the whole grid after every change works on ten cells and dies on a thousand.
Topological order rules everything
Recalculation walks the topologically sorted dependency graph. The topological sort arranges cells in an order where, before you compute any of them, everything it depends on is already ready. That way each formula sees fresh values of its sources, not their previous version.
It is the same pattern that decides the correctness of build systems and bundlers. Order is not a detail but the condition for the result making any sense at all.
The topological sort gives cycle detection as a gift. If a cell indirectly depends on itself, the graph has no valid order, so instead of looping forever the sheet raises a circular reference error. The same structure that fixes the order catches impossible dependencies.
Without it a cycle like A depends on B and B on A would hang the recalculation. By resting everything on one graph, that most dangerous case needs no separate code, it simply falls out of the sort having no solution.
A pattern that shows up everywhere
The most interesting thing about cellar is that the spreadsheet problem turns out to be the same problem you meet in entirely different places. Anywhere a change to one value should pull others along in the right order, there sits a dependency graph plus a topological sort.
The same mechanism in other systems
| System | Where the dependency graph returns |
|---|---|
| Spreadsheet | recomputing dependent cells |
| Bundlers | order of linking modules |
| Build systems | order of compiling targets |
| Reactive frameworks | refreshing derived values |
More projects
More work from the same category - see how we tackle similar challenges.
Have a similar project?
Get in touch - a quote is free and comes back within an hour.