La implementación: añadir, retirar, consultar y mezclar

Con el contrato escrito, la implementación es corta y casi aburrida, y esa brevedad es el mejor indicio de que el diseño era correcto: cuando una estructura convergente necesita casos especiales, ramas condicionales o comprobaciones de orden, casi siempre es que alguna de las tres decisiones previas se tomó mal. Lo que sigue es la clase entera, sin dependencias, sin librerías y sin abreviar, con los cuatro campos del estado justificados uno a uno y los cinco métodos comentados. Hay exactamente un punto donde se concentra la dificultad de todo el archivo, y es la mezcla: dos líneas que casi todo el mundo escribe de la forma cómoda en vez de la correcta, con una consecuencia que no aparece en ninguna prueba secuencial y que destruye datos en producción. Terminaremos ejecutando la clase para ver una sesión completa y comprobar que volver a añadir algo retirado funciona por construcción y no por un caso especial.

Los cuatro campos del estado

El constructor fija cuatro campos y conviene tener claro qué hace cada uno porque dos de ellos viajan y los otros dos no. El identificador de réplica y el contador son contabilidad local: existen para poder emitir etiquetas únicas sin preguntar a nadie, no se comparan al verificar convergencia y no se mezclan. El mapa de altas y el conjunto de bajas son el estado compartido: son lo que se transmite, lo que se une y lo único que decide qué elementos están presentes.

class ORSet {
  constructor(replica) {
    this.replica = replica;      // identificador unico y estable de esta replica
    this.reloj = 0;              // contador local monotono, solo lo toca esta replica
    this.altas = new Map();      // elemento -> Set de etiquetas que lo anadieron
    this.bajas = new Set();      // etiquetas retiradas, sean de quien sean
  }
  // Una etiqueta es replica mas contador: unica sin coordinar y comparable.
  nuevaEtiqueta() {
    this.reloj += 1;
    return this.replica + ":" + this.reloj;
  }
  // Etiquetas de un elemento que nadie ha retirado todavia.
  vivas(elemento) {
    const todas = this.altas.get(elemento);
    if (!todas) return [];
    return [...todas].filter((t) => !this.bajas.has(t));
  }

La elección del mapa de elemento a conjunto de etiquetas, en lugar de una lista plana de pares, no es indiferente. La consulta de presencia es la operación más frecuente con diferencia y con esta forma cuesta lo que cuesta mirar las etiquetas de un solo elemento, mientras que con una lista plana habría que recorrerla entera. El precio es que la mezcla se complica, porque hay que fusionar los conjuntos internos y no solo las claves, y ahí es exactamente donde aparece el error de la tercera sección. El conjunto de bajas, en cambio, es deliberadamente plano: mantenerlo así hace que su unión sea trivialmente correcta y que comprobar si una etiqueta está muerta no dependa de encontrar antes el elemento adecuado, que es justo lo que hará falta cuando ese conjunto se sustituya por un vector resumido.

Alta, baja y consulta

Los tres métodos de operación son la traducción literal de las cláusulas del contrato, y merece la pena leerlos con el contrato al lado para comprobar que no hay nada más: el alta emite una etiqueta que nunca ha existido y la añade al conjunto del elemento, la baja lee las etiquetas vivas y marca exactamente esas, y la consulta pregunta si queda alguna viva.

  add(elemento) {
    if (!this.altas.has(elemento)) this.altas.set(elemento, new Set());
    const etiqueta = this.nuevaEtiqueta();
    this.altas.get(elemento).add(etiqueta);
    return etiqueta;
  }
  // La baja se lleva consigo exactamente las etiquetas observadas ahora.
  remove(elemento) {
    const observadas = this.vivas(elemento);
    for (const t of observadas) this.bajas.add(t);
    return observadas;
  }
  has(elemento) {
    return this.vivas(elemento).length > 0;
  }
  values() {
    return [...this.altas.keys()].filter((e) => this.has(e)).sort();
  }

Fíjate en que la eliminación observada de la lección anterior no aparece por ninguna parte como concepto: es simplemente la consecuencia de que remove empiece llamando a vivas. No hay captura explícita de contexto causal, ni estructura auxiliar, ni reloj, porque el contexto que hacía falta era el estado local y estaba delante. Los métodos devuelven además la etiqueta emitida y la lista de retiradas, y esa decisión, que parece un detalle de comodidad, será lo que permita construir los deltas en la última lección sin tocar nada más. Merece un comentario aparte que values filtre por presencia en lugar de mantener una lista de elementos vivos actualizada: es más lento y es lo correcto para una implementación de referencia, porque cualquier estructura derivada que se mantenga en paralelo al estado es una oportunidad de que las dos se desincronicen bajo mezcla, que es precisamente el escenario que esta clase existe para sobrevivir.

La mezcla, y el error que la arruina

La mezcla es la única función interesante del archivo. Une los dos componentes por separado y devuelve un estado nuevo, sin modificar los operandos, lo cual importa más de lo que parece: una mezcla que muta a uno de sus argumentos hace imposible comprobar la conmutatividad, porque el segundo experimento ya no parte del mismo sitio que el primero.

  // Mezcla: union de altas elemento a elemento y union de bajas.
  static merge(a, b) {
    const salida = new ORSet(a.replica);
    salida.reloj = a.reloj;
    for (const fuente of [a.altas, b.altas]) {
      for (const [elemento, etiquetas] of fuente) {
        if (!salida.altas.has(elemento)) salida.altas.set(elemento, new Set());
        for (const t of etiquetas) salida.altas.get(elemento).add(t);
      }
    }
    salida.bajas = new Set([...a.bajas, ...b.bajas]);
    return salida;
  }
}

El error que hay que evitar es tan cómodo de escribir que aparece en buena parte de las implementaciones caseras, y consiste en construir el mapa resultante con la sintaxis de expansión sobre los dos mapas. Parece que une y en realidad reemplaza: cuando una clave existe en ambos, el segundo mapa pisa el conjunto del primero en lugar de fusionarlo. El experimento siguiente lo mide.

function mergeMalo(a, b) {
  const s = new ORSet(a.replica);
  s.altas = new Map([...a.altas, ...b.altas]);       // el segundo pisa al primero
  s.bajas = new Set([...a.bajas, ...b.bajas]);
  return s;
}
const P = new ORSet("P"); P.add("cafe");
const Q = new ORSet("Q"); Q.add("cafe");
console.log("bien :", serializar(ORSet.merge(P, Q)));
console.log("mal  :", serializar(mergeMalo(P, Q)));
console.log("conmutativa con el merge malo:",
  serializar(mergeMalo(P, Q)) === serializar(mergeMalo(Q, P)));

bien : {"altas":{"cafe":["P:1","Q:1"]},"bajas":[]}
mal  : {"altas":{"cafe":["Q:1"]},"bajas":[]}
conmutativa con el merge malo: false

La etiqueta P:1 desapareció. El daño no es que el elemento deje de estar presente —sigue estándolo, porque queda Q:1— sino algo mucho peor de diagnosticar: una retirada posterior creerá haber observado todas las altas del elemento cuando en realidad solo vio una, y el alta perdida podrá resucitar más tarde si llega desde otra réplica que sí la conservaba. El síntoma que reportará el usuario será un elemento que reaparece semanas después, y ningún volcado del estado en el momento del fallo contendrá la pista, porque la información se destruyó en una mezcla anterior.

La clase entera en funcionamiento

Queda añadir una función de serialización estable, que no forma parte de la estructura pero es imprescindible para todo lo que viene: comparar estados en las pruebas, medir tamaños y depurar. Es estable porque ordena claves y etiquetas, de modo que dos estados equivalentes producen exactamente la misma cadena, y omite replica y reloj porque son contabilidad local y no deben participar en ninguna comparación de convergencia.

function serializar(s) {
  const altas = {};
  for (const [e, etiquetas] of [...s.altas].sort()) altas[e] = [...etiquetas].sort();
  return JSON.stringify({ altas, bajas: [...s.bajas].sort() });
}
const s = new ORSet("A");
console.log("add cafe ->", s.add("cafe"));
console.log("add te    ->", s.add("te"));
console.log("values    :", s.values());
console.log("remove cafe mata:", s.remove("cafe"));
console.log("has cafe  :", s.has("cafe"));
console.log("add cafe ->", s.add("cafe"));
console.log("has cafe  :", s.has("cafe"), "vivas:", s.vivas("cafe"));
console.log("estado    :", serializar(s));

add cafe -> A:1
add te    -> A:2
values    : [ 'cafe', 'te' ]
remove cafe mata: [ 'A:1' ]
has cafe  : false
add cafe -> A:3
has cafe  : true vivas: [ 'A:3' ]
estado    : {"altas":{"cafe":["A:1","A:3"],"te":["A:2"]},"bajas":["A:1"]}

Lo que hay que mirar en esa salida no es que funcione, sino por qué funciona. Volver a añadir cafe no se resolvió con ninguna comprobación de si el elemento estaba retirado ni con ninguna limpieza de la marca anterior: la etiqueta A:3 es nueva, no figura entre las bajas y no puede figurar, porque las bajas solo contienen etiquetas que alguien vio y nadie pudo ver una etiqueta que no existía. El caso que rompía las dos estructuras ingenuas de la lección anterior aquí ni siquiera es un caso.

El último detalle que conviene señalar del estado impreso es que A:1 sigue ahí. La etiqueta muerta no se borra del mapa de altas, y no se borra a propósito: eliminarla sería perder la información de que existió, y esa información hace falta para que una mezcla posterior con una réplica que aún no la conocía no la resucite. Ese residuo es la lápida de toda la vida, y su acumulación es el problema que ocupará las últimas lecciones del bloque.