cellar
Un moteur de tableur avec son propre langage de formules, en Dart pur. Parseur, graphe de dépendances et recalcul des cellules - le fondement du fonctionnement d'un tableur.
Un moteur de tableur en Dart pur. En dessous, un tableur est un graphe de dépendances entre cellules : vous en changez une et vous devez recalculer exactement celles qui en dépendent, dans le bon ordre. À cela s'ajoute un langage de formules maison avec un parseur.
Introduction
Visuellement un tableur est une grille de cellules, mais c'est une illusion sur ce qui se passe en dessous. Logiquement c'est un graphe orienté : une cellule avec une formule dépend d'autres cellules, celles-ci d'autres encore. Toute l'ingénierie de cellar se ramène à recalculer ce graphe correctement et seulement dans la partie qui en a vraiment besoin.
Le reste, le parseur de formules et les fonctions, enveloppe cet unique mécanisme. Si le graphe de dépendances est mal construit, aucun langage de formules riche ne le sauvera, car la feuille se mettra à afficher des nombres calculés sur des données périmées.
Une feuille de calcul est un graphe, pas un tableau
Quand vous changez une valeur, vous ne pouvez pas tout recalculer, car c'est du gaspillage, ni recalculer dans un ordre aléatoire, car vous obtenez du n'importe quoi. Vous devez toucher exactement les cellules qui dépendent de celle qui a changé, et le faire dans un ordre où chacune calcule déjà sur les données à jour de ses prédécesseurs.
C'est le cœur de cellar et aussi le point où les feuilles plus grandes deviennent difficiles. Une solution naïve qui recalcule toute la grille après chaque changement fonctionne sur dix cellules et meurt sur mille.
L'ordre topologique gouverne tout
Le recalcul parcourt le graphe de dépendances trié topologiquement. Le tri topologique dispose les cellules dans un ordre où, avant de calculer l'une d'elles, tout ce dont elle dépend est déjà prêt. Ainsi chaque formule voit les valeurs fraîches de ses sources, pas leur version précédente.
C'est le même motif qui décide de la correction des systèmes de build et des bundlers. L'ordre n'est pas un détail mais la condition pour que le résultat ait le moindre sens.
Le tri topologique offre la détection de cycles en cadeau. Si une cellule dépend indirectement d'elle-même, le graphe n'a pas d'ordre valide, donc au lieu de boucler à l'infini la feuille signale une erreur de référence circulaire. La même structure qui fixe l'ordre attrape les dépendances impossibles.
Sans cela un cycle du type A dépend de B et B de A ferait tourner le recalcul sans fin. Parce que tout repose sur un seul graphe, ce cas le plus dangereux ne demande pas de code séparé, il découle simplement du fait que le tri n'a pas de solution.
Un motif qui revient partout
Le plus intéressant dans cellar est que le problème du tableur se révèle être le même problème que vous rencontrez à des endroits totalement différents. Partout où un changement d'une valeur doit en entraîner d'autres dans le bon ordre, il y a un graphe de dépendances plus un tri topologique.
Le même mécanisme dans d'autres systèmes
| Système | Où revient le graphe de dépendances |
|---|---|
| Tableur | recalcul des cellules dépendantes |
| Bundlers | ordre de liaison des modules |
| Systèmes de build | ordre de compilation des cibles |
| Frameworks réactifs | rafraîchissement des valeurs dérivées |
Plus de projets
D'autres réalisations de la même catégorie - découvrez comment nous abordons des défis similaires.
Vous avez un projet similaire ?
Contactez-nous - le devis est gratuit et arrive sous une heure.