El marcado en dos fases

La solución al problema del rombo no consiste en ordenar el grafo, sino en algo más barato y más elegante: separar por completo el momento de marcar del momento de evaluar. Durante la primera fase no se calcula absolutamente nada; durante la segunda, cada nodo resuelve sus dependencias antes de resolverse a sí mismo. El orden topológico emerge de la recursión sin que nadie lo calcule, y eso es lo que hace que la técnica sea tan buena.

El invariante que hace falta

La demostración es corta si se enuncia bien el invariante.

Invariante de la fase 1: cuando la fase de marcado termina, todo nodo cuyo valor pueda haber cambiado está marcado como SUCIO o QUIZA. Ninguno queda limpio por error.

Invariante de la fase 2: un nodo solo se evalúa después de que todas sus fuentes hayan sido resueltas —evaluadas o declaradas limpias— en esta misma transacción.

Del segundo invariante se sigue inmediatamente que no puede haber glitches: si todas las fuentes están resueltas antes de la evaluación, ninguna puede pertenecer al estado anterior. El trabajo está en garantizar el segundo invariante, y aquí es donde entra la resolución recursiva.

function actualizar(nodo) {
  if (nodo.estado === QUIZA) {
    for (const f of nodo.fuentes) {
      if (f.fn) actualizar(f);            // <-- garantiza el invariante 2
      if (nodo.estado === SUCIO) break;
    }
    if (nodo.estado === QUIZA) { nodo.estado = LIMPIO; return; }
  }
  if (nodo.estado !== SUCIO) return;
  ejecutar(nodo);
}

La línea marcada es la que hace todo el trabajo. Antes de decidir nada sobre mí, resuelvo a mis fuentes. Y como cada una de ellas hace lo mismo, la recursión llega hasta las raíces y vuelve resolviendo en orden topológico inverso, que es exactamente el orden correcto.

El rombo, paso a paso

Retomemos el caso que rompía push puro.

const a = senal(1);
const b = memo(() => a() + 1);      // 2
const c = memo(() => a() * 10);     // 10
efecto(() => registrar(b() + c())); // 12

a.set(2). Fase 1, marcado, sin ejecutar nada.

Los observadores directos de a son b y c: los dos pasan a SUCIO. Como los dos venían de limpio, se propaga QUIZA hacia abajo. Desde b, el efecto pasa a QUIZA y entra en la cola. Desde c, el efecto ya está en QUIZA, así que la guarda de no degradar corta la propagación ahí mismo. Fin de la fase 1: b y c sucios, el efecto quizá sucio y encolado. Cero cuerpos ejecutados.

Fase 2, al vaciar la cola. Se actualiza el efecto, que está en QUIZA, así que recorre sus fuentes.

Primera fuente, b: está SUCIO, se ejecuta, devuelve 3. Como cambió, asciende a sus observadores directos: el efecto pasa de QUIZA a SUCIO. Vuelve el control al bucle del efecto, que comprueba if (nodo.estado === SUCIO) break y sale del bucle.

Aquí hay un detalle que parece un bug y no lo es: hemos salido del bucle sin haber resuelto c. Pero a continuación se llama a ejecutar(efecto), que ejecuta el cuerpo, y el cuerpo llama a c(). El getter de c comprueba su estado, lo encuentra SUCIO y lo actualiza antes de devolver. Así que c se resuelve igualmente, en el momento exacto en que hace falta.

El efecto se ejecuta una vez y registra 3 + 20 = 23. Correcto, sin valores intermedios, sin ejecuciones sobrantes.

flowchart TB
F1[fase 1 marcar] --> M1[b y c a SUCIO]
M1 --> M2[efecto a QUIZA y a la cola]
M2 --> F2[fase 2 evaluar]
F2 --> R1[efecto resuelve b que cambia]
R1 --> R2[efecto pasa a SUCIO y ejecuta]
R2 --> R3[el cuerpo lee c que se resuelve al leerse]
R3 --> OK[una sola ejecucion con valores coherentes]
style F1 fill:#89b4fa,color:#11111b
style M1 fill:#f38ba8,color:#11111b
style M2 fill:#f9e2af,color:#11111b
style F2 fill:#cba6f7,color:#11111b
style R1 fill:#cba6f7,color:#11111b
style R2 fill:#cba6f7,color:#11111b
style R3 fill:#cba6f7,color:#11111b
style OK fill:#a6e3a1,color:#11111b

El orden emerge de la recursión

Esto es lo bonito del diseño y merece decirlo explícitamente: el motor nunca calcula un orden topológico. No hay ordenación, no hay niveles, no hay cola de prioridad. El orden lo impone la pila de llamadas de JavaScript, porque una llamada no vuelve hasta que sus llamadas anidadas han terminado.

La resolución recursiva es, literalmente, un recorrido en profundidad del grafo en la dirección de las dependencias, y un recorrido en profundidad que procesa el nodo al volver produce un orden topológico inverso. Es un resultado clásico de teoría de grafos, aplicado aquí sin escribir el algoritmo: lo escribe el intérprete por ti.

De ahí salen dos propiedades prácticas. La primera es que no hay coste de ordenación: nada que mantener cuando el grafo cambia de forma, que en un sistema con tracking automático es continuamente. La segunda es que funciona con grafos dinámicos por construcción, porque el orden se descubre en el momento de recorrer y no antes.

El requisito y quién lo cumple

El requisito que hay que cumplir

La garantía se sostiene sobre una condición que conviene enunciar porque es donde fallan las implementaciones caseras: ningún cuerpo se puede ejecutar durante la fase 1.

Si durante el marcado se ejecuta un efecto —por ejemplo, porque planificar lo ejecuta en vez de encolarlo—, ese efecto leerá nodos que todavía no están marcados y verá valores viejos combinados con nuevos. El glitch vuelve.

// MAL: ejecuta durante el marcado
function planificar(efecto) { ejecutar(efecto); }

// BIEN: encola, y la cola se vacia despues del marcado
function planificar(efecto) {
  if (Cola) Cola.add(efecto);
  else lote(() => Cola.add(efecto));
}

Por eso la cola de efectos no es solo una optimización de agrupamiento: es parte de la garantía de corrección. El nivel 8 desarrolla la cola con detalle, pero la razón de su existencia está aquí.

Quién usa esta técnica

Solid la usa con sus estados STALE y PENDING y la resolución hacia arriba. Preact Signals la usa con banderas de bits y comprobación de versiones, con la misma estructura de dos fases. Vue la usa desde su refactorización de la reactividad, con niveles de suciedad y verificación perezosa. La propuesta de TC39 la describe explícitamente en su modelo de Signal.Computed.

La alternativa —ordenar topológicamente y procesar por niveles— existe y se usa en otros dominios. Es la lección siguiente.