cellar
Un motor de hoja de cálculo con su propio lenguaje de fórmulas, en Dart puro. Parser, grafo de dependencias y recálculo de celdas - la base de cómo funciona una hoja.
Un motor de hoja de cálculo en Dart puro. Por debajo, una hoja de cálculo es un grafo de dependencias entre celdas: cambias una y debes recalcular exactamente las que dependen de ella, y en el orden correcto. A eso se suma un lenguaje de fórmulas propio con un parser.
Introducción
Visualmente una hoja de cálculo es una cuadrícula de celdas, pero eso es una ilusión sobre lo que ocurre por debajo. Lógicamente es un grafo dirigido: una celda con una fórmula depende de otras celdas, estas de otras más. Toda la ingeniería de cellar se reduce a recalcular ese grafo correctamente y solo en la parte que de verdad lo necesita.
El resto, el parser de fórmulas y las funciones, envuelve este único mecanismo. Si el grafo de dependencias está mal construido, ningún lenguaje de fórmulas rico lo salvará, porque la hoja empezará a mostrar números calculados sobre datos obsoletos.
Una hoja de cálculo es un grafo, no una tabla
Cuando cambias un valor, no puedes recalcular todo, porque es un derroche, ni recalcular en orden aleatorio, porque obtienes basura. Debes tocar exactamente las celdas que dependen de la que cambió, y hacerlo en un orden en el que cada una calcule ya sobre los datos actualizados de sus predecesoras.
Ese es el corazón de cellar y también el punto donde las hojas más grandes se vuelven difíciles. Una solución ingenua que recalcula toda la cuadrícula tras cada cambio funciona con diez celdas y muere con mil.
El orden topológico gobierna todo
El recálculo recorre el grafo de dependencias ordenado topológicamente. El orden topológico dispone las celdas en un orden en el que, antes de calcular cualquiera de ellas, todo aquello de lo que depende ya está listo. Así cada fórmula ve los valores frescos de sus fuentes, no su versión anterior.
Es el mismo patrón que decide la corrección de los sistemas de build y los bundlers. El orden no es un detalle sino la condición para que el resultado tenga algún sentido.
El orden topológico regala la detección de ciclos. Si una celda depende indirectamente de sí misma, el grafo no tiene un orden válido, así que en lugar de dar vueltas infinitas la hoja señala un error de referencia circular. La misma estructura que fija el orden atrapa las dependencias imposibles.
Sin él, un ciclo del tipo A depende de B y B de A colgaría el recálculo. Al apoyarlo todo en un único grafo, ese caso más peligroso no necesita código aparte, simplemente se deriva de que el orden no tiene solución.
Un patrón que reaparece en todas partes
Lo más interesante de cellar es que el problema de la hoja de cálculo resulta ser el mismo problema que encuentras en lugares completamente distintos. Dondequiera que un cambio en un valor deba arrastrar a otros en el orden correcto, hay un grafo de dependencias más un orden topológico.
El mismo mecanismo en otros sistemas
| Sistema | Dónde reaparece el grafo de dependencias |
|---|---|
| Hoja de cálculo | recálculo de celdas dependientes |
| Bundlers | orden de enlazado de módulos |
| Sistemas de build | orden de compilación de objetivos |
| Frameworks reactivos | refresco de valores derivados |
Más proyectos
Más trabajos de la misma categoría - mira cómo abordamos retos parecidos.
¿Tiene un proyecto similar?
Escríbenos - el presupuesto es gratuito y llega en una hora.