cellar
Eine Tabellenkalkulations-Engine mit eigener Formelsprache, in reinem Dart. Parser, Abhängigkeitsgraph und Zellenberechnung - das Fundament, wie eine Tabelle funktioniert.
Eine Tabellenkalkulations-Engine in reinem Dart. Darunter ist eine Tabelle ein Abhängigkeitsgraph zwischen Zellen: Ändern Sie eine, müssen Sie genau die neu berechnen, die von ihr abhängen, und in der richtigen Reihenfolge. Dazu kommt eine eigene Formelsprache mit Parser.
Einführung
Optisch ist ein Arbeitsblatt ein Raster aus Zellen, doch das ist eine Illusion über dem, was darunter geschieht. Logisch ist es ein gerichteter Graph: Eine Zelle mit einer Formel hängt von anderen Zellen ab, diese von weiteren. Die ganze Ingenieurarbeit von cellar läuft darauf hinaus, diesen Graphen korrekt und nur in dem Teil neu zu berechnen, der es wirklich braucht.
Der Rest, der Formelparser und die Funktionen, umschließt diesen einen Mechanismus. Ist der Abhängigkeitsgraph falsch gebaut, rettet ihn keine reiche Formelsprache, denn das Arbeitsblatt beginnt, Zahlen anzuzeigen, die auf veralteten Daten berechnet wurden.
Das Arbeitsblatt ist ein Graph, keine Tabelle
Wenn Sie einen Wert ändern, können Sie nicht alles neu berechnen, denn das ist Verschwendung, und auch nicht in zufälliger Reihenfolge, denn dann bekommen Sie Müll. Sie müssen genau die Zellen anfassen, die von der geänderten abhängen, und zwar in einer Reihenfolge, in der jede bereits auf aktuellen Daten ihrer Vorgänger rechnet.
Das ist der Kern von cellar und zugleich der Punkt, an dem größere Arbeitsblätter schwierig werden. Eine naive Lösung, die nach jeder Änderung das ganze Raster neu berechnet, funktioniert bei zehn Zellen und stirbt bei tausend.
Die topologische Reihenfolge regiert alles
Die Neuberechnung läuft über den topologisch sortierten Abhängigkeitsgraphen. Die topologische Sortierung ordnet die Zellen so an, dass, bevor Sie eine von ihnen berechnen, alles, wovon sie abhängt, bereits fertig ist. Dadurch sieht jede Formel frische Werte ihrer Quellen und nicht deren vorherige Version.
Es ist dasselbe Muster, das über die Korrektheit von Build-Systemen und Bundlern entscheidet. Die Reihenfolge ist kein Detail, sondern die Bedingung dafür, dass das Ergebnis überhaupt einen Sinn ergibt.
Die topologische Sortierung liefert die Zyklenerkennung als Geschenk. Hängt eine Zelle indirekt von sich selbst ab, hat der Graph keine gültige Reihenfolge, also gibt das Arbeitsblatt, statt sich endlos zu drehen, einen Fehler wegen Zirkelbezugs aus. Dieselbe Struktur, die die Reihenfolge festlegt, fängt unmögliche Abhängigkeiten ab.
Ohne sie würde ein Zyklus wie A hängt von B ab und B von A die Neuberechnung aufhängen. Weil alles auf einem einzigen Graphen ruht, braucht dieser gefährlichste Fall keinen eigenen Code, er folgt einfach daraus, dass die Sortierung keine Lösung hat.
Ein Muster, das überall auftaucht
Das Interessanteste an cellar ist, dass sich das Tabellenproblem als dasselbe Problem entpuppt, dem Sie an völlig anderen Stellen begegnen. Überall dort, wo eine Änderung eines Wertes andere in der richtigen Reihenfolge nachziehen soll, steckt ein Abhängigkeitsgraph plus eine topologische Sortierung.
Derselbe Mechanismus in anderen Systemen
| System | Wo der Abhängigkeitsgraph wiederkehrt |
|---|---|
| Tabellenkalkulation | Neuberechnung abhängiger Zellen |
| Bundler | Reihenfolge des Verknüpfens von Modulen |
| Build-Systeme | Reihenfolge des Kompilierens von Zielen |
| Reaktive Frameworks | Aktualisieren abgeleiteter Werte |
Weitere Projekte
Weitere Projekte aus derselben Kategorie - sehen Sie, wie wir ähnliche Herausforderungen angehen.
Haben Sie ein ähnliches Projekt?
Melden Sie sich - ein Angebot ist kostenlos und kommt innerhalb einer Stunde.