Borrar y recorrer: la lápida y el texto visible

Quedan dos operaciones para tener un editor completo: quitar caracteres y mostrar el resultado. Ninguna de las dos es lo que parece. Borrar no puede consistir en eliminar el nodo, porque el nodo es el ancla de cualquier inserción concurrente que lo citara como predecesor, y quitarlo deja esas inserciones colgando en el vacío para siempre. Y mostrar no puede consistir en leer el array tal cual, porque el array contiene tanto lo que se ve como lo que estuvo y ya no está. La solución a ambas cosas es la misma marca booleana, y esta lección la implementa, la ejecuta y muestra con salida real qué ocurre exactamente cuando alguien decide ahorrársela. Al final tendremos la pieza que faltaba para la prueba de convergencia: la función que traduce posiciones de la interfaz a sellos, que es por donde el editor habla con la estructura.

Borrar de verdad rompe a quien te citaba

El argumento teórico ya apareció en el nivel 32: si desaparece un nodo, la inserción concurrente que lo declaraba como padre se queda huérfana. Vale la pena verlo ocurrir. El escenario es mínimo: dos réplicas con HOLA sincronizado, Ana borra la L, y Beto —que no ha visto ese borrado— escribe ITO justo detrás de esa misma L.

// Variante destructiva: el borrado elimina el nodo de verdad
function borrarFisico(rep, id) {
  const i = rep.lista.findIndex((n) => clave(n.id) === clave(id));
  if (i >= 0) { rep.lista.splice(i, 1); rep.indice.delete(clave(id)); }
  return { tipo: "borrarFisico", id };
}

function escenario(borrado) {
  const ana = crearReplica("ana"), beto = crearReplica("beto");
  const base = escribir(ana, 0, "HOLA");
  for (const op of base) recibir(beto, op);
  const idL = idVisible(ana, 2);                 // la letra L
  const opBorrar = borrado(ana, idL);            // ana la quita
  const opsBeto = escribir(beto, 3, "ITO");      // beto escribe justo detras de ella
  for (const op of opsBeto) recibir(ana, op);
  if (opBorrar.tipo === "borrar") recibir(beto, opBorrar);
  return { ana, beto };
}

borrado fisico  -> ana="HOA"  operaciones atascadas en ana: 3
borrado logico  -> ana="HOITOA"  beto="HOITOA"  atascadas: 0

La primera línea es el diagnóstico completo. No es que Ana pierda el texto de Beto por un rato: es que sus tres operaciones quedan en la cola de pendientes de forma permanente, porque esperan un ancla que ya no existe y que nunca volverá a existir. Ninguna retransmisión las salva. Reenviar el mensaje mil veces produce mil veces el mismo false. Y como Beto sí las tiene aplicadas, las dos réplicas han divergido sin ningún mecanismo interno capaz de detectarlo o corregirlo.

La lápida: una marca, no un valor

El borrado lógico es tan pequeño que decepciona: se busca el nodo por su sello y se pone su marca a verdadero. La operación que viaja por la red no lleva valor, no lleva posición y no lleva padre; solo el sello del nodo afectado. Esa parquedad es la que la hace conmutativa e idempotente sin ningún esfuerzo adicional: aplicar dos veces el mismo borrado deja la marca en verdadero, y aplicarlo antes o después de otras inserciones no altera el resultado, porque la marca no participa en el orden.

function borrar(rep, id) {
  const op = { tipo: "borrar", id };
  aplicar(rep, op);
  return op;
}

// dentro de aplicar, para el caso de borrado:
const objetivo = rep.indice.get(clave(op.id));
if (!objetivo) return false;     // el nodo aun no ha llegado: se encola
objetivo.borrado = true;
return true;

Fíjate en el return false cuando el nodo no está. Un borrado también puede llegar antes que la inserción que lo creó, y en ese caso se aparca exactamente igual que una inserción huérfana. Es el mismo mecanismo, y esa uniformidad es la que permite que recibir no distinguya entre tipos de operación: todo lo que no se puede aplicar todavía espera en la misma cola y se reintenta con el mismo bucle.

Conviene decir en voz alta que el borrado lógico no es una decisión de ingeniería revisable, al menos no localmente. Un nodo solo puede desaparecer del todo cuando se tiene la certeza de que ninguna réplica del sistema —incluidas las que llevan meses apagadas— podría emitir una operación que lo cite. Eso exige un acuerdo global sobre lo que todo el mundo ha visto, que es precisamente lo que un sistema local-first no quiere necesitar. De ahí que la compactación sea un problema aparte y difícil, y no un if que se pueda añadir a esta función.

El recorrido: de la estructura al texto que se ve

Con el array ya linealizado por la integración, producir el texto visible es un barrido de izquierda a derecha concatenando los valores de los nodos sin marca. No hay recursión, no hay ordenación y no hay que consultar la relación de paternidad: todo ese trabajo lo hizo integrar en el momento de insertar.

function texto(rep) {
  let s = "";
  for (const n of rep.lista) if (!n.borrado) s += n.valor;
  return s;
}

flowchart LR
A[array linealizado] --> B[recorrer de izquierda a derecha]
B --> C{tiene lapida}
C -->|si| D[saltar el nodo]
C -->|no| E[concatenar el valor]
D --> B
E --> B
B --> F[texto visible]
style D fill:#f38ba8,color:#11111b
style E fill:#a6e3a1,color:#11111b
style F fill:#89b4fa,color:#11111b

El coste de esta función es proporcional al número total de nodos, no al número de caracteres visibles, y esa distinción es exactamente el problema que abordará la última lección. Un documento del que se ha borrado el noventa y nueve por ciento de lo que alguna vez se escribió tarda en renderizarse lo que tardaría el documento completo, aunque en pantalla se vean cuatro líneas. La raíz centinela pasa por aquí sin hacer ruido: nació con la marca puesta y con el valor vacío, así que el recorrido la ignora sin ningún caso especial.

Traducir posiciones de la interfaz a sellos

Queda la pieza que conecta la estructura con el mundo exterior. El editor no habla de sellos: cuando alguien teclea, lo que llega es inserta en la posición cuarenta y dos. Hace falta una función que convierta esa posición visible en el sello del nodo tras el cual hay que colgar, y otra que haga el camino inverso para los borrados.

function anclaEn(rep, pos) {          // sello del predecesor para insertar en pos
  let vistos = 0, ancla = RAIZ;
  for (const n of rep.lista) {
    if (n.borrado) continue;
    if (vistos === pos) break;
    ancla = n.id; vistos += 1;
  }
  return ancla;                        // pos cero devuelve la raiz: sin caso especial
}

function idVisible(rep, pos) {         // sello del nodo que ocupa la posicion pos
  let vistos = 0;
  for (const n of rep.lista) {
    if (n.borrado) continue;
    if (vistos === pos) return n.id;
    vistos += 1;
  }
  return null;
}

function escribir(rep, pos, cadena) {  // una rafaga: cada nodo cuelga del anterior
  const ops = [];
  let padre = anclaEn(rep, pos);
  for (const ch of cadena) { const op = insertar(rep, padre, ch); ops.push(op); padre = op.id; }
  return ops;
}

Estas tres funciones parecen utilitarias y son, en realidad, el punto donde se concentra todo el coste real de una implementación ingenua. anclaEn recorre el array entero hasta la posición pedida, y hay que llamarla en cada pulsación de teclado. En un documento con muchas lápidas, ese recorrido es largo aunque el cursor esté cerca del principio del texto visible. La quinta lección medirá exactamente cuánto y explicará qué estructura auxiliar usan las bibliotecas reales para convertir ese barrido lineal en una búsqueda logarítmica.