Ordenación topológica explícita

La otra manera de garantizar el orden es la obvia: calcularlo. Asigna a cada nodo un número que respete la topología, mete los nodos afectados en una cola de prioridad, y procésalos de menor a mayor. Es la solución clásica de los sistemas de flujo de datos, funciona perfectamente, y tiene un problema concreto con los grafos dinámicos que explica por qué los motores de interfaz eligieron la otra.

La altura de un nodo

La idea es asignar a cada nodo un entero tal que todo nodo sea estrictamente mayor que todas sus fuentes. Se calcula al tejer las aristas.

function alturaDe(nodo) {
  let h = 0;
  for (const f of nodo.fuentes) h = Math.max(h, (f.altura ?? 0) + 1);
  return h;
}

function seguirConAltura(fuente) {
  if (!Observador) return;
  Observador.fuentes.add(fuente);
  fuente.observadores.add(Observador);
  if ((fuente.altura ?? 0) >= Observador.altura) {
    Observador.altura = fuente.altura + 1;
    propagarAltura(Observador);       // los descendientes suben tambien
  }
}

function propagarAltura(nodo) {
  for (const o of nodo.observadores) {
    if (o.altura > nodo.altura) continue;
    o.altura = nodo.altura + 1;
    propagarAltura(o);
  }
}

En el rombo de siempre, a tiene altura cero, b y c altura uno, y el efecto altura dos. Procesar en orden de altura garantiza que el efecto se evalúa después de b y de c.

La propagación por cola de prioridad

Con las alturas asignadas, la propagación es un bucle sobre una cola ordenada.

function escribir(fuente, valor) {
  if (fuente.iguales(fuente.valor, valor)) return;
  fuente.valor = valor;

  const cola = new ColaDePrioridad((x, y) => x.altura - y.altura);
  for (const o of fuente.observadores) cola.meter(o);

  const enCola = new Set(cola.elementos());
  while (!cola.vacia()) {
    const nodo = cola.sacar();           // siempre el de menor altura
    enCola.delete(nodo);
    const anterior = nodo.valor;
    ejecutar(nodo);
    if (!nodo.iguales(anterior, nodo.valor)) {
      for (const o of nodo.observadores) {
        if (enCola.has(o)) continue;      // ya esta pendiente
        cola.meter(o); enCola.add(o);
      }
    }
  }
}

En el rombo: la cola arranca con b y c, ambos de altura uno. Se saca uno cualquiera, se ejecuta, cambia, y se mete el efecto de altura dos. Se saca el otro nodo de altura uno —porque dos es mayor que uno, el efecto espera—, se ejecuta, cambia, e intenta meter el efecto, que ya está. Finalmente se saca el efecto y se ejecuta una vez, con las dos fuentes actualizadas.

Correcto, y con una propiedad que la solución de dos fases no tiene: el orden está garantizado de forma global y explícita, no como consecuencia de una recursión.

flowchart TB
A[fuente altura 0] --> B[b altura 1]
A --> C[c altura 1]
B --> E[efecto altura 2]
C --> E
E --> N[se procesa cuando la cola llega a la altura 2]
style A fill:#89b4fa,color:#11111b
style B fill:#cba6f7,color:#11111b
style C fill:#cba6f7,color:#11111b
style E fill:#f9e2af,color:#11111b
style N fill:#a6e3a1,color:#11111b

Las ventajas reales

Es ansiosa y por tanto tiene latencia mínima. Cuando la escritura vuelve, todo está calculado. No hay estados marcados pendientes de resolver, y por tanto tampoco hay coste en la lectura: leer siempre es devolver un campo.

Permite prioridades adicionales. Como ya hay una cola de prioridad, es trivial añadir criterios: procesar antes los nodos visibles, agrupar los que escriben en el DOM, aplazar los caros. Los sistemas de renderizado con presupuesto de tiempo se apoyan en esto.

El orden es inspeccionable. Se puede volcar la cola, se puede ver la altura de cada nodo, se puede razonar sobre el orden sin ejecutar. Para depurar un sistema grande eso vale mucho.

El problema del grafo dinámico

El problema: el grafo cambia

Y aquí está la razón por la que los motores de interfaz no la usan. Con tracking automático, las aristas cambian en cada ejecución, y cada cambio de arista puede invalidar las alturas.

Considera una condicional que cambia de rama y hace que un nodo pase a depender de una cadena más larga. Su altura sube, y con ella la de todos sus descendientes, recursivamente. Esa propagación de alturas puede tocar una parte enorme del grafo, y ocurre durante la propagación, es decir, mientras la cola ya está poblada con las alturas viejas.

El problema es peor de lo que parece: si un nodo ya está en la cola con altura tres y su altura sube a siete, la cola contiene una prioridad obsoleta. Hay que sacarlo y volver a meterlo, lo que exige una cola de prioridad con actualización de clave. Y si la subida de altura ocurre mientras se procesa un nodo de altura cinco, se ha violado el orden: ya se procesó algo que debería ir después.

Las soluciones existen y todas son caras. Recalcular alturas al vuelo con reordenación de la cola. Detectar la violación y reiniciar la propagación. Usar alturas reales en vez de enteras, para poder insertar entre dos niveles sin renumerar. Ninguna es barata, y todas añaden complejidad considerable al camino caliente.

Una variante intermedia

Existe un punto medio que aparece en algunos motores: usar la altura no para ordenar la evaluación, sino solo para ordenar la cola de efectos. Las computaciones puras se resuelven con el marcado en dos fases, que no necesita alturas, y los efectos —que son hojas y cuyo orden relativo a veces importa— se ejecutan en orden de creación o de profundidad en el árbol de componentes.

Es una solución pragmática: la parte del grafo que cambia mucho usa el mecanismo barato, y la parte donde el orden es observable por el programador usa un criterio explícito y predecible. El nivel 8 vuelve sobre esto al hablar del orden entre computaciones puras y efectos.