Los tres estados de un nodo

Un motor con dos estados —limpio y sucio— es correcto y hace demasiado trabajo. La diferencia entre dos y tres estados es la diferencia entre recalcular todo lo alcanzable desde un cambio y recalcular solo lo que de verdad cambió. Ese tercer estado, el intermedio, es una de las ideas más rentables de todo el diseño de motores reactivos, y cuesta un entero por nodo.

Qué significa cada estado

Limpio. El valor cacheado es válido. Una lectura lo devuelve sin comprobar nada. Es el estado de reposo y donde están casi todos los nodos casi todo el tiempo.

Sucio. Se sabe con certeza que hay que reejecutar el cuerpo. Un nodo llega aquí cuando una de sus fuentes directas cambió de valor de verdad.

Quizá sucio. Algo en el camino de arriba cambió, pero no se sabe si el cambio llegó hasta aquí. Un nodo en este estado tiene que preguntar hacia arriba antes de decidir si se reejecuta o se declara limpio.

La asimetría de información entre los dos últimos es la clave. SUCIO es una certeza local: mi entrada cambió, lo he visto. QUIZA es una sospecha: mi abuelo cambió, y si mi padre acaba produciendo otro valor entonces yo también tengo que cambiar, pero eso todavía no se sabe.

Por qué dos estados no bastan

Supón que solo tienes limpio y sucio. Al escribir una fuente, hay que marcar hacia adelante. ¿Hasta dónde?

Si marcas solo a los observadores directos, los indirectos se quedan limpios y devolverán una caché obsoleta. Incorrecto.

Si marcas a todos los descendientes transitivos como sucios, todo lo alcanzable se reejecuta. Correcto y caro: has vuelto al coste de push puro, porque no hay manera de que un nodo intermedio corte la cadena. Una derivación que devuelve el mismo valor no puede comunicar no ha pasado nada a sus descendientes, porque ya están marcados como sucios y sucio significa reejecuta.

// Con dos estados: todo lo alcanzable acaba ejecutandose
const a = senal(1);
const par = memo(() => a() % 2 === 0);
const etiqueta = memo(() => par() ? 'par' : 'impar');
const clase = memo(() => `fila fila-${etiqueta()}`);
efecto(() => aplicar(clase()));

a.set(3);   // dos estados: se ejecutan los tres memos y el efecto
            // tres estados: se ejecuta solo el primer memo

El tercer estado es precisamente el canal para comunicar todavía no se sabe. Sin él, el sistema no puede aplazar la decisión, y aplazar la decisión es lo que permite tomarla con información.

Las transiciones

Solo hay cinco transiciones legales, y cada una tiene un único responsable.

LIMPIO a SUCIO: la provoca una fuente directa al cambiar de valor, o una derivación de arriba al recalcularse y producir un valor distinto.

LIMPIO a QUIZA: la provoca la propagación transitiva del marcado, cuando un ancestro se ensucia.

QUIZA a SUCIO: la provoca la resolución hacia arriba, cuando una fuente en QUIZA se recalcula y cambia. Es un ascenso.

QUIZA a LIMPIO: la provoca la resolución hacia arriba cuando ninguna fuente cambió. Es la transición que ahorra trabajo, y es la razón de existir del estado intermedio.

SUCIO a LIMPIO: la provoca la ejecución del cuerpo.

flowchart LR
L[LIMPIO] -->|una fuente directa cambia| S[SUCIO]
L -->|un ancestro se ensucia| Q[QUIZA]
Q -->|al preguntar arriba algo cambio| S
Q -->|al preguntar arriba nada cambio| L
S -->|se ejecuta el cuerpo| L
style L fill:#a6e3a1,color:#11111b
style Q fill:#f9e2af,color:#11111b
style S fill:#f38ba8,color:#11111b

Y una transición ilegal que conviene nombrar: de SUCIO a QUIZA. El estado solo puede escalar en certeza, nunca degradarse. De ahí la guarda que aparece en todo el código de marcado.

if (obs.estado >= estado) continue;   // nunca degradar, y nunca repetir trabajo

Esa guarda hace dos cosas a la vez, y las dos son necesarias. Impide la degradación, y corta la propagación cuando el nodo ya estaba marcado al menos con esa certeza, lo que evita recorrer el mismo subgrafo varias veces en un rombo. Sin ella, un grafo con muchos caminos paralelos se recorrería una vez por camino, con coste exponencial en el número de rombos anidados.

Detalles de la propagación

El detalle de la propagación en dos velocidades

Hay una sutileza en el código de marcado que merece atención porque es fácil equivocarse.

function marcar(nodo, estado) {
  for (const obs of nodo.observadores) {
    if (obs.estado >= estado) continue;
    const antes = obs.estado;
    obs.estado = estado;
    if (obs.efecto) planificar(obs);
    if (antes === LIMPIO) marcar(obs, QUIZA);   // <-- solo si venia de limpio
  }
}

La última línea propaga hacia abajo solo si el nodo venía de limpio. La razón: si ya estaba en QUIZA, entonces sus descendientes también lo están desde una propagación anterior, y volver a recorrerlos no añadiría información. Es la optimización que mantiene el marcado en coste lineal en el número de aristas del subgrafo, en vez de cuadrático.

Y fíjate en que la llamada recursiva pasa QUIZA y no estado. La certeza no se hereda: que mi padre esté seguro no significa que yo lo esté, porque entre él y yo hay un cálculo que puede devolver lo mismo.

Un cuarto estado que a veces aparece

Algunas implementaciones añaden un estado adicional para nodos que se están evaluando ahora mismo, con el único fin de detectar dependencias circulares: si al resolver un nodo te lo encuentras en ese estado, hay un ciclo y hay que lanzar un error.

No es parte del modelo de propagación —no participa en las decisiones de recálculo— sino una salvaguarda. En un motor didáctico se puede omitir; en uno de producción conviene tenerlo, porque el error alternativo es un desbordamiento de pila con una traza inútil.