prune method

Fugue<T> prune(Set<Dot> stable)

Drop blocks that are fully tombstoned, causally stable (every element dot observed everywhere), and have no surviving descendant block.

Returns a new pruned instance. A block with any live element, or any kept child block, is retained — its element positions still anchor live descendants. Because a run compresses to one block with a deleted range, a wholly-deleted paragraph is a single droppable unit, not thousands of tombstone nodes.

Caller invariant. Every replica must have observed every dot in stable AND no future write may reference a dot in stable from an ancestral state. For a Fugue, stable must additionally guarantee that every delta referencing these dots — including inserts parented on their tombstones (a tombstone still anchors positions; _rightOrigin walks the tombstone-inclusive traversal) — has been delivered to every replica, and prune must be applied with the same stable set on all replicas. Violating this leaves permanently unreachable ("orphan") blocks and breaks convergence of visible values: the pruning replica drops a block another replica just anchored a child on, so that child is visible on the peer and invisible here, forever. See orphanBlockCount to detect the condition.

Implementation

Fugue<T> prune(Set<Dot> stable) {
  // Block-level child index: parent block's start dot -> child blocks.
  final blockChildren = <Dot, List<_Block<T>>>{};
  final roots = <_Block<T>>[];
  for (final c in _blocks.values) {
    if (c.parent.isOrigin) {
      roots.add(c);
      continue;
    }
    final pb = _locate(c.parent);
    if (pb == null) {
      roots.add(c); // orphan (parent not yet delivered) — treat as root
      continue;
    }
    (blockChildren[pb.$1.start] ??= <_Block<T>>[]).add(c);
  }

  // A block is droppable iff it has no live element, all its element dots are
  // stable, and every child block is droppable. Iterative post-order so a
  // long chain of small blocks can't overflow the stack.
  final droppable = <Dot, bool>{};
  final stack = <Object>[for (final r in roots) _ExpandBlock<T>(r)];
  while (stack.isNotEmpty) {
    final item = stack.removeLast();
    if (item is _ExpandBlock<T>) {
      stack.add(item.b); // compute after children
      for (final c in blockChildren[item.b.start] ?? <_Block<T>>[]) {
        stack.add(_ExpandBlock<T>(c));
      }
    } else {
      final b = item as _Block<T>;
      var drop = b.deleted.length == b.length; // no live offset
      for (var k = 0; drop && k < b.length; k++) {
        if (!stable.contains(b.dotAt(k))) drop = false;
      }
      if (drop) {
        for (final c in blockChildren[b.start] ?? <_Block<T>>[]) {
          if (droppable[c.start] != true) {
            drop = false;
            break;
          }
        }
      }
      droppable[b.start] = drop;
    }
  }

  final kept = Fugue<T>();
  for (final b in _blocks.values) {
    if (droppable[b.start] == true) continue;
    final nb = _Block<T>(b.start, b.parent, b.side, List<T>.of(b.values));
    nb.deleted.addAll(b.deleted);
    kept._index(nb);
  }
  return kept;
}