cellar
Un motore per fogli di calcolo con un proprio linguaggio di formule, in puro Dart. Parser, grafo delle dipendenze e ricalcolo delle celle - il fondamento del funzionamento di un foglio.
Un motore di foglio di calcolo in Dart puro. Sotto, un foglio di calcolo è un grafo di dipendenze tra celle: ne cambi una e devi ricalcolare esattamente quelle che dipendono da essa, e nell'ordine giusto. A questo si aggiunge un linguaggio di formule fatto in casa con un parser.
Introduzione
Visivamente un foglio di calcolo è una griglia di celle, ma è un'illusione su ciò che accade sotto. Logicamente è un grafo orientato: una cella con una formula dipende da altre celle, queste da altre ancora. Tutta l'ingegneria di cellar si riduce a ricalcolare quel grafo correttamente e solo nella parte che ne ha davvero bisogno.
Il resto, il parser delle formule e le funzioni, avvolge questo unico meccanismo. Se il grafo delle dipendenze è costruito male, nessun ricco linguaggio di formule lo salverà, perché il foglio comincerà a mostrare numeri calcolati su dati obsoleti.
Un foglio di calcolo è un grafo, non una tabella
Quando cambi un valore, non puoi ricalcolare tutto, perché è uno spreco, né ricalcolare in ordine casuale, perché ottieni spazzatura. Devi toccare esattamente le celle che dipendono da quella cambiata, e farlo in un ordine in cui ciascuna calcola già sui dati aggiornati dei suoi predecessori.
Questo è il cuore di cellar e anche il punto in cui i fogli più grandi si fanno difficili. Una soluzione ingenua che ricalcola l'intera griglia dopo ogni modifica funziona su dieci celle e muore su mille.
L'ordine topologico governa tutto
Il ricalcolo percorre il grafo delle dipendenze ordinato topologicamente. L'ordinamento topologico dispone le celle in un ordine in cui, prima di calcolarne una qualsiasi, tutto ciò da cui dipende è già pronto. Così ogni formula vede i valori freschi delle sue sorgenti, non la loro versione precedente.
È lo stesso schema che decide la correttezza dei sistemi di build e dei bundler. L'ordine non è un dettaglio ma la condizione perché il risultato abbia un qualche senso.
L'ordinamento topologico offre il rilevamento dei cicli in regalo. Se una cella dipende indirettamente da se stessa, il grafo non ha un ordine valido, quindi invece di ciclare all'infinito il foglio segnala un errore di riferimento circolare. La stessa struttura che fissa l'ordine intercetta le dipendenze impossibili.
Senza di essa un ciclo del tipo A dipende da B e B da A bloccherebbe il ricalcolo. Poiché tutto poggia su un unico grafo, questo caso più pericoloso non richiede codice separato, deriva semplicemente dal fatto che l'ordinamento non ha soluzione.
Uno schema che torna ovunque
La cosa più interessante di cellar è che il problema del foglio di calcolo si rivela lo stesso problema che incontri in posti del tutto diversi. Ovunque un cambiamento di un valore debba trascinarne altri nell'ordine giusto, c'è un grafo di dipendenze più un ordinamento topologico.
Lo stesso meccanismo in altri sistemi
| Sistema | Dove torna il grafo delle dipendenze |
|---|---|
| Foglio di calcolo | ricalcolo delle celle dipendenti |
| Bundler | ordine di collegamento dei moduli |
| Sistemi di build | ordine di compilazione dei target |
| Framework reattivi | aggiornamento dei valori derivati |
Altri progetti
Altri lavori della stessa categoria - scopri come affrontiamo sfide simili.
Hai un progetto simile?
Contattaci - il preventivo è gratuito e arriva entro un'ora.