Skip to content

armgit / bento

Public Imported from GitHub
0

Bento, the office suite that fits in a file

88.3 KB
Raw Blame
// SPDX-License-Identifier: MIT
// Copyright (c) 2026 The Bento authors
// bento-sync M0 — the CRDT engine. Pure data, no DOM, no imports beyond the
// model types: the same file runs in the browser session layer and in the
// node convergence rig (scripts/test-sync.ts, node --experimental-strip-types).
//
// Design: docs/collab-design.md. Summary of the algebra:
//   - identity: slides key by their id; ELEMENTS key by the composite
//     `slideId U+001F elementId` (elKey) — the same element id on many
//     slides is the format's core morph idiom (data-flip-id pairing), so
//     each per-slide copy must be its own CRDT node. The doc format never
//     sees composite keys (element `id` stays the bare morph id); they
//     live in this layer's registers and on the wire. A cross-slide move
//     changes the key, so the differ emits del(old)+ins(new) — concurrent
//     moves of one element to two slides duplicate it (both users keep
//     their copy) instead of racing. `@doc` is the document's namespace.
//   - per-(node, key) LWW registers ordered by (lamport, actorId).
//   - order + parentage: one `pos` register per node (fractional base-62 key
//     + parent id) — arrays in the doc are always *materialized* pos-order.
//   - liveness: `births[id]` (stamped by ins) vs `tombs[id]` (stamped by del),
//     highest (l,a) wins. Delete beats concurrent edits; undo-of-delete is a
//     fresh ins carrying the full node, which resurrects by out-stamping the
//     tomb. A slide delete cascades to the elements the deleter saw (listed
//     in the op); concurrently inserted/moved-in elements survive in `limbo`
//     until re-parented.
//   - delivery: ops carry a per-actor contiguous sequence `s`; the version
//     vector is per-actor max-contiguous-seq, gaps are buffered in `gap`.
//   - text (M3): element.html upgrades to a token RGA on first concurrent
//     text edit ("seed" travels with the first txt op); plain `set html`
//     with a newer (l,a) resets the RGA (LWW compat with old clients).
//
// Convergence argument: every mutation is a join-semilattice merge (register
// max by (l,a), liveness max, RGA insert) applied under causal-enough
// delivery (per-actor FIFO via `s`, cross-actor buffering via `pending`).
// The rig replays random op interleavings across replicas and asserts
// identical materialized documents.

/**
 * The three shapes the engine touches, structurally.
 *
 * The kernel may not import an app's model (kernel/README.md, PLATFORM §9) —
 * and it does not need to. What the engine actually requires of a document is
 * this and nothing more: a container of parented nodes, each with an `id`,
 * under two keys named by the DocShape below. Every app's model satisfies it.
 */
import type { FieldClass, FieldsOfClass } from '../docfields.ts'

type BentoDoc = object
type Slide = { id: string }
type SlideElement = { id: string }

/**
 * THE unknown-key switch. A doc-level key absent from the local app's class map
 * (a field a NEWER build added) — when one arrives in an op or a snapshot, is it
 * applied (true: a newer build's content survives an older peer, and lands in
 * this replica's own file) or ignored (false: fail closed — an unknown field
 * never enters this replica's doc from the room)? Either way this replica never
 * EMITS an unknown key (diff is content-class only). One line, by design: the
 * ruling between the two goes here and nowhere else.
 */
const APPLY_UNKNOWN_DOC_KEYS = true

// ---------------------------------------------------------------------------
// document shape
// ---------------------------------------------------------------------------

/**
 * WHICH KEYS HOLD THE TWO CONTAINER LEVELS.
 *
 * The engine's algebra — composite node keys, fractional position keys,
 * per-(node,key) registers, the token RGA over `html` — has nothing to do with
 * slides. Only the two property names do: the doc key holding the parent array
 * (`slides`) and the parent key holding the child array (`elements`).
 * bento/spaces has the same two levels under different names (`pages`,
 * `blocks`), so naming them is the whole of what it takes for one engine to
 * serve both apps.
 *
 * BOUND AT MODULE LEVEL, NEVER SERIALIZED, NEVER ON THE WIRE. A room is
 * single-app by construction (the room id is minted per file), so no frame
 * ever has to say which shape it came from — and putting a shape tag in
 * SyncStateJSON would change the bytes of every bento/slides file already on
 * a disk. That constraint is not a style preference: scripts/test-sync-equiv.ts
 * asserts byte-identity against the engine as shipped, and a `state-key-order`
 * mutant exists precisely to prove the comparator notices.
 *
 * The WIRE VOCABULARY is deliberately not parameterized. Ops keep saying
 * `kind:'slide'|'element'` and carrying `sl`/`el` for every app: renaming them
 * per app buys prettier debug output and costs a second binding on the
 * highest-consequence bytes in the system.
 */
export interface DocShape {
  /** doc-level key holding the PARENT array: 'slides' | 'pages' */
  readonly parents: string
  /**
   * Parent-level key holding the CHILD array: 'elements' | 'blocks' — or
   * `null` for a FLAT document, one level deep.
   *
   * bento/type is flat: a block IS the paragraph, so there is nothing beneath
   * it. Rather than make such an app invent an empty child array on every
   * node, the engine treats a childless shape as having no element layer at
   * all — `C()` reads as empty and the differ therefore never mints an element
   * op. See the guard in `applyEffect` for the receiving side.
   */
  readonly children: string | null
  /**
   * The property carrying collaboratively-edited TEXT, which gets the token
   * RGA rather than a last-writer-wins register.
   *
   * Named rather than hard-coded because it is the one property whose merge
   * behaviour decides whether two people can type in the same paragraph at
   * once. It was `'html'` in both existing apps, so the default keeps every
   * shipped file byte-identical; an app whose text lives elsewhere says so.
   */
  readonly text: string
  /**
   * Doc-level keys the differ never syncs.
   *
   * MUST contain `parents`, which is why `shape()` below DERIVES it rather
   * than taking it: the container is synced structurally — per node, with its
   * own position key — so listing it as an ordinary doc property instead would
   * collapse the whole document into ONE last-writer-wins register, and every
   * concurrent edit would destroy every other. Deriving it means no caller can
   * get it wrong; when this becomes a constructor argument, that has to become
   * an assertion instead.
   */
  readonly skipDoc: ReadonlySet<string>
  /**
   * Doc-level keys that are MAPS, merged per key rather than as one value.
   *
   * `assets` and `blobs` were hard-coded for this, with the right reason
   * attached: two people adding different assets concurrently must both keep
   * theirs. Any id-keyed map wants the same treatment, and an app has no way
   * to ask for it while the names are baked in — bento/type's `footnotes` is
   * one (note id → note text), and as a whole-value register it loses a note
   * BODY while both references survive, leaving a marker pointing at nothing.
   */
  readonly maps: ReadonlySet<string>
  /**
   * The app's field-class map (docfields.ts), when the app has adopted one. With
   * it, the engine syncs doc-level keys by ALLOWLIST — the sender rule:
   *   - a peer EMITS only keys its own map classes 'content' (plus `maps`), on
   *     every path it mints: the op diff, its snapshot doc + state, and the
   *     stamped SyncStateJSON. An unknown key — from a newer file opened here,
   *     or applied from the wire — is never emitted by this peer.
   *   - a peer IGNORES any incoming key its map knows as non-content (identity,
   *     mode, capability, history) whatever the sender claims, and applies
   *     unknown keys per APPLY_UNKNOWN_DOC_KEYS.
   * Without it, behaviour is the shipped denylist (skipDoc only). skipDoc keys
   * are never emitted and never applied in either mode.
   */
  readonly classes?: Readonly<Record<string, FieldClass>>
  /**
   * HISTORY-class doc keys that nonetheless SYNC, as whole-value registers. The
   * allowlist decides sync by `classes`, but a field's copy class and its sync
   * decision can diverge: bento/type classes `comments` as history so reader and
   * export copies drop them (the #663 copy ruling), yet comments must still flow
   * between live collaborators. Naming such a key here emits and accepts it
   * though it is non-content — WITHOUT changing its wire shape, so a build that
   * binds a class map stays mixed-version-compatible with one that does not
   * (both see the same whole `#doc <key>` register).
   *
   * RESTRICTED to history-class keys, two ways: `shape()` throws at runtime if a
   * named key is not classed 'history' (or there is no class map), and the typed
   * `historySyncKeys` helper makes naming an identity / mode / capability /
   * unclassified key a compile error. So this can never become a path around the
   * floor: skipDoc is still checked FIRST in both gates, and an identity, mode or
   * capability key can never be listed here at all. For per-key id-maps use
   * `maps` instead (that one changes the wire shape).
   */
  readonly syncHistory: ReadonlySet<string>
}

/** Derived, never authored: the volatile set is the same for every app apart
 *  from the container name, so writing it out twice invites them to drift. */
export const shape = (
  parents: string,
  children: string | null,
  text = 'html',
  maps: readonly string[] = [],
  classes?: Readonly<Record<string, FieldClass>>,
  syncHistory: readonly string[] = [],
): DocShape => {
  // file-local, never synced — each replica keeps its own timeline. (When an app
  // passes `classes`, PR2 ALSO refuses any non-content / unknown doc key inbound
  // and emits only content keys — see DocShape.classes; skipDoc is the floor that
  // holds whether or not an app has adopted a class map.)
  // docId / readonly / template are identity and file modes: never synced, and —
  // because skipDoc is ALSO the receive filter (applySet, mergeSnapshot) — never
  // adopted from a peer either. A remote op can't rewrite a deck's identity,
  // lock or unlock it, or turn it into a template. `policy` is an encoding tag
  // like format/version: a loader that meets an unknown one FREEZES the document
  // read-only on open, so a peer must never be able to set it.
  const skipDoc = new Set([parents, 'modified', 'collab', 'format', 'version', 'policy', 'revisions', 'trail', 'docId', 'readonly', 'template'])
  // `assets` and `blobs` are per-key for every app and always have been —
  // unioned rather than defaulted so an app naming its own map cannot drop them.
  // syncHistory may name ONLY history-class keys — the runtime half of the
  // restriction (the typed helper is the compile half). A key not classed
  // 'history', or named with no class map at all, is refused here so it can
  // never widen what syncs beyond a history field an app chose to share.
  // BELT AND BRACES: also refuse a key that is in skipDoc. The class check
  // trusts the app's own map, and nothing pins collab/revisions to their class —
  // an app that MIS-classes a never-synced key as 'history' and names it here
  // would pass the class check, leaving only the gate ORDER (skipDoc first) to
  // protect it. Refusing skipDoc ∩ syncHistory at bind time makes a never-synced
  // field safe regardless of gate order: it can't be named at all.
  for (const k of syncHistory) {
    if (skipDoc.has(k)) {
      throw new Error(`DocShape.syncHistory names "${k}", which is in the never-synced set (skipDoc); a floor field can never be shared, whatever its class`)
    }
    if (!classes || classes[k] !== 'history') {
      throw new Error(`DocShape.syncHistory names "${k}", which is ${classes ? `classed ${classes[k] ?? 'nothing'}` : 'bound with no class map'}; only history-class keys may sync this way`)
    }
  }
  const out: DocShape = { parents, children, text, skipDoc, maps: new Set(['assets', 'blobs', ...maps]), syncHistory: new Set(syncHistory) }
  return classes ? { ...out, classes } : out
}

/** Build the `syncHistory` list for `shape()` with a COMPILE-TIME guarantee
 *  that every key is history-class in `classes`. `FieldsOfClass<M,'history'>` is
 *  the union of M's history keys, so naming an identity / mode / capability or
 *  unclassified key is a type error here — the compile half of the restriction
 *  that `shape()` also enforces at runtime. Usage:
 *    shape('body', null, 'text', ['footnotes'], TYPE_FIELDS,
 *          historySyncKeys(TYPE_FIELDS, ['comments'])) */
export function historySyncKeys<M extends Record<string, FieldClass>>(
  _classes: M, keys: readonly FieldsOfClass<M, 'history'>[],
): readonly string[] {
  return keys as readonly string[]
}

/** The parent array of a document, and the child array of a parent. Indexed
 *  access through the descriptor: `d['slides']` is the same lookup `d.slides`
 *  was, so these are byte-neutral by construction. */
const P = (S: DocShape, d: BentoDoc): Slide[] => (d as unknown as Record<string, Slide[]>)[S.parents]
/**
 * A parent's children — empty, and FROZEN, when the shape is flat.
 *
 * Frozen on purpose: every mutating call site is supposed to be unreachable
 * without an element layer, and a throw says so at once. Silently swallowing a
 * push is how a replica ends up quietly missing content.
 */
const NO_CHILDREN: SlideElement[] = Object.freeze([]) as unknown as SlideElement[]
const C = (S: DocShape, p: Slide): SlideElement[] =>
  S.children === null ? NO_CHILDREN : (p as unknown as Record<string, SlideElement[]>)[S.children]
/**
 * …and the write-back form for the child array.
 *
 * There is deliberately no `setP`. The engine mutates the PARENT array only in
 * place (push/splice/sort), never by assignment — worth knowing, because a
 * future edit that reassigns it would be replacing the array the caller's
 * document still points at.
 */
const setC = (S: DocShape, p: Slide, v: SlideElement[]): void => {
  if (S.children === null) return // a flat document has no child array to write
  ;(p as unknown as Record<string, SlideElement[]>)[S.children] = v
}

/**
 * Collaboration credentials, as they live in the file.
 *
 * PLATFORM-level, not app-level (§2): every Bento document carries `docId` and
 * may carry `collab`, and the relay, the invite chain and the fork-merge all
 * work purely in these terms. The shape is documented at length in
 * bento/slides' model.ts, which is where it was written, and in
 * docs/collab-design.md.
 */
export interface CollabCreds {
  room: string
  key: string
  on?: boolean
  sync?: SyncStateJSON
  writerPub?: string
  writerPriv?: string
  role?: 'writer' | 'reader' | 'audience'
  v?: number
  owner?: string
  ownerPriv?: string
  invite?: { pub: string; priv: string; role: 'writer' | 'commenter' | 'audience'; exp?: number; sig: string }
}

/** A blob the document references but does not inline. */
export interface BlobRef { key: string; mime: string; size: number }

/**
 * The document, as the SESSION needs to see it.
 *
 * crdt.ts keeps `SyncDoc` deliberately opaque (`object`) because the ENGINE
 * genuinely does not care what is in a document — it is told the shape. The
 * session is a different layer and does care about a few fields, but only the
 * ones PLATFORM §2 guarantees EVERY Bento document has, so each app's own
 * document type already satisfies it structurally — no conversion, and no
 * index signature, which would have forced every app to declare one.
 */
export interface SyncDoc {
  docId: string
  collab?: CollabCreds
  assets?: Record<string, string>
  blobs?: Record<string, BlobRef>
  modified?: string
}

export const DOC_NODE = '@doc'

/**
 * Sync format version — stamped into SyncStateJSON (`v`) and every wire
 * frame (`pv`). v1 keyed elements by bare id, which collapsed the same id
 * appearing on multiple slides (the morph idiom); v2 state/ops are keyed
 * by composite element keys and are NOT interoperable, so v1 saved state
 * and v1 frames are discarded on sight.
 */
export const SYNC_V = 2

/**
 * Largest asset value that may travel INSIDE an op, in characters of its data
 * URI. Above this the session offloads the bytes to the relay's blob store and
 * syncs a `blobs.<key>` reference instead — a Durable Object storage value
 * caps near 2MB, so a big asset simply cannot be an op at any frame size.
 * Small assets stay inline: the round trip is not worth it for an icon.
 */
export const BLOB_INLINE_MAX = 64 * 1024

/** composite element node key: slide id + separator + element id. U+001F
 * never appears in model ids (uid() emits [a-z0-9-]; generators use ASCII). */
const SEP = '\u001f'

/**
 * Names that address an object's PROTOTYPE when used as a property key.
 * `obj['__proto__'] = v` doesn't add a field, it swaps the prototype, so a
 * remote op naming it made doc.readonly / doc.collab READ a peer's values
 * through inheritance until reload, past any name-based refusal list. Every
 * name off the wire is checked whole and per segment: dotted map keys, composite
 * element keys (SEP), and register keys (`node key`, space-separated).
 */
const PROTO_NAMES = new Set(['__proto__', 'constructor', 'prototype'])
const protoName = (s: unknown): boolean =>
  typeof s === 'string' && s.split(/[.\u001f ]/).some((p) => PROTO_NAMES.has(p))

/** Does any own KEY, at any depth of a wire value, carry a prototype name?
 *  Fails CLOSED: an object nested past the cap counts as unsafe rather than
 *  passing uninspected (no real op payload comes close to 64 levels). */
function hasProtoKey(x: unknown, depth = 0): boolean {
  if (x === null || typeof x !== 'object') return false
  if (depth > 64) return true
  if (Array.isArray(x)) {
    // Walk ELEMENTS, not index keys: an index is never a prototype name, and
    // running protoName per index cost ~85ms on a 100k-row snapshot.
    for (const el of x) if (hasProtoKey(el, depth + 1)) return true
    // NAMED own keys on an array (structured clone over BroadcastChannel keeps
    // them) are walked too, values included — but only when the array has any,
    // so a plain array stays a single pass.
    const keys = Object.keys(x)
    if (keys.length !== x.length)
      for (const k of keys) {
        if (/^(0|[1-9]\d*)$/.test(k)) continue
        if (protoName(k) || hasProtoKey((x as unknown as Record<string, unknown>)[k], depth + 1)) return true
      }
    return false
  }
  for (const k of Object.keys(x)) {
    if (protoName(k)) return true
    if (hasProtoKey((x as Record<string, unknown>)[k], depth + 1)) return true
  }
  return false
}

/** A remote op that names a prototype anywhere — in an identifier it addresses
 *  (k, el, sl, id, a cascade key) or as a key inside its payload. */
function protoOp(op: Op): boolean {
  const o = op as unknown as Partial<Record<'k' | 'el' | 'sl' | 'id', unknown>> & { cas?: unknown }
  if ([o.k, o.el, o.sl, o.id].some(protoName)) return true
  if (Array.isArray(o.cas) && o.cas.some(protoName)) return true
  return hasProtoKey(op)
}
export const elKey = (sl: string, el: string): string => sl + SEP + el
export const keySlide = (key: string): string => key.slice(0, key.indexOf(SEP))
export const keyEl = (key: string): string => key.slice(key.indexOf(SEP) + 1)

/* eslint-disable no-console */
const dbg = (id: string, msg: string) => {
  const g = globalThis as unknown as { __dbgEl?: string; __dbgTag?: string }
  if (g.__dbgEl && g.__dbgEl === id) console.log(`      [dbg ${g.__dbgTag ?? ''} ${msg}]`)
}

// ---------------------------------------------------------------------------
// fractional order keys — base-62 midstrings, lexicographic, ASCII-sorted
// ---------------------------------------------------------------------------

const DIGITS = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
const D = (c: string) => DIGITS.indexOf(c)

/**
 * A key strictly between `a` and `b` ('' = unbounded on that side).
 * Classic midstring: walk digits; equal → copy; gap ≥ 2 → midpoint; adjacent
 * → keep low digit and continue against the open top. Never returns a key
 * ending in '0' (which would leave no room below it on extension).
 */
export function keyBetween(a: string, b: string): string {
  let out = ''
  for (let i = 0; ; i++) {
    const da = i < a.length ? D(a[i]) : 0
    const db = i < b.length ? D(b[i]) : 62
    if (da === db) {
      out += DIGITS[da]
      continue
    }
    if (db - da > 1) return out + DIGITS[Math.floor((da + db) / 2)]
    // adjacent digits: take the low one, then bisect a's tail against the top
    out += DIGITS[da]
    for (let j = i + 1; ; j++) {
      const ta = j < a.length ? D(a[j]) : 0
      if (62 - ta > 1) return out + DIGITS[Math.floor((ta + 62) / 2)]
      out += DIGITS[ta]
    }
  }
}

/** Deterministic evenly-spread key for index i of n (file adoption). */
export function spreadKey(i: number, n: number): string {
  let v = (i + 1) / (n + 1)
  let out = ''
  const need = Math.max(2, Math.ceil(Math.log(n + 2) / Math.log(62)) + 1)
  for (let k = 0; k < need; k++) {
    v *= 62
    const d = Math.min(61, Math.floor(v))
    out += DIGITS[d]
    v -= d
  }
  while (out.length > 1 && out.endsWith('0')) out = out.slice(0, -1)
  return out === '0' ? '1' : out
}

// ---------------------------------------------------------------------------
// ops
// ---------------------------------------------------------------------------

export type Reg = [number, string] // [lamport, actor]

const newer = (l: number, a: string, r: Reg | undefined): boolean =>
  !r || l > r[0] || (l === r[0] && a > r[1])
const regNewer = (x: Reg, y: Reg | undefined): boolean => newer(x[0], x[1], y)

export interface OpBase {
  a: string // actor
  s: number // per-actor contiguous sequence (delivery/vv)
  l: number // lamport (conflict order)
}
export interface SetOp extends OpBase {
  op: 'set'
  /** node id: composite element key (elKey), slide id, or absent → @doc */
  el?: string
  sl?: string
  /** property key; doc-level supports dotted sub-keys 'assets.<k>' */
  k: string
  /** undefined/absent = delete the key */
  v?: unknown
}
export interface InsOp extends OpBase {
  op: 'ins'
  kind: 'slide' | 'element'
  /** slide id, or composite element key (its slide part = `sl`) */
  id: string
  /** parent: slide id for elements, ignored for slides */
  sl?: string
  ord: string
  /** doc-shaped payload — element ids inside stay bare (the format never
   * sees composite keys) */
  node: Slide | SlideElement
}
export interface DelOp extends OpBase {
  op: 'del'
  kind: 'slide' | 'element'
  /** slide id, or composite element key */
  id: string
  /** slide delete: composite keys of the elements the deleter saw inside
   * (cascade tombstones) */
  cas?: string[]
}
export interface OrdOp extends OpBase {
  op: 'ord'
  kind: 'slide' | 'element'
  /** slide id, or composite element key */
  id: string
  ord: string
  /** elements: the parent slide (constant for a given key — moves across
   * slides change the key itself via del+ins) */
  sl?: string
}
/** M3 — text RGA delta for one element's html. */
export interface TxtOp extends OpBase {
  op: 'txt'
  /**
   * The node the text lives on: a composite element key, or a bare parent id
   * for an app whose text sits on the parent (bento/type's blocks). The field
   * keeps its name because it is on the wire in every shipped file.
   */
  el: string
  /** seed reference: (l,a) of the RGA base this delta applies to */
  sd: Reg
  /** present on the op that CREATES the seed: the base html it tokenized */
  base?: string
  /** deletions: token ids */
  del?: string[]
  /** insertions: after-anchor token id ('^' = start) + tokens */
  ins?: Array<{ at: string; toks: string[] }>
}
export type Op = SetOp | InsOp | DelOp | OrdOp | TxtOp

// ---------------------------------------------------------------------------
// sync state (per document, serializable)
// ---------------------------------------------------------------------------

interface PosEntry {
  p: string // parent node id (@doc for slides)
  o: string // fractional key
  r: Reg
}

export interface TxtTok {
  id: string
  t: string
  d?: 1
}
export interface TxtState {
  sd: Reg
  toks: TxtTok[]
  /** deletes that overtook their token's insert — resolved on arrival */
  pd?: string[]
}

export interface SyncStateJSON {
  /** sync format version (SYNC_V) — mismatched saved state is discarded */
  v: number
  lamport: number
  vv: Record<string, number>
  regs: Record<string, Reg>
  pos: Record<string, PosEntry>
  births: Record<string, Reg>
  tombs: Record<string, Reg>
  /**
   * Per-character token history for every text node — the structure that lets
   * two people type into one paragraph without either clobbering the other.
   *
   * OPTIONAL, and an app may choose not to stamp it. Measured: identical prose
   * costs ×0.2 of its own size when it arrives as one write (a paste, an
   * import, an agent) and ×25.8 when it is TYPED, because a typing run mints a
   * token per character and a deletion cannot remove one — a tombstone is how
   * "delete" is expressed to a replica that has not caught up yet, so the
   * history only ever grows. An emptied paragraph still carries everything ever
   * typed into it.
   *
   * EVERY shipping app stamps it — the default, via `stampInto` → `toJSON()`.
   * bento/slides and bento/spaces both do (spaces' `SyncSession` extends the
   * kernel one and does not override the stamp), and the differ runs with
   * `text: true` (session.ts). The `text: false` option below OMITS the history
   * and was meant for a future size optimisation — a space is typed prose, so
   * its token history would outweigh its own document many times over inside
   * the plaintext #bento-doc block. But NO shipping path uses it, only the sync
   * rigs, because it is NOT SAFE YET:
   *
   * ABSENT TOKEN HISTORY LOSES DATA ON A SNAPSHOT REUNION — and not only in the
   * same paragraph, the way this comment once claimed. A txt edit advances the
   * node's text GENERATION but NOT its `html` LWW register; a `text: false`
   * stamp drops the generation, so the only stamped carrier of that edit is
   * gone, and `mergeSnapshot` — the path a mailed-back copy reunites by — never
   * copies the edited value from the peer's document. Two offline forks that
   * edited DIFFERENT blocks lose one edit, silently (measured; convergence
   * still holds, which is exactly why it is silent — docs/DECISIONS.md
   * 2026-09-17). A LIVE op-replay session is unaffected: a `set`/`txt` op both
   * carries the value and stamps its register, so the loss is specific to a
   * lean stamp reunited by snapshot. `toJSON` therefore REFUSES `text: false`
   * without an explicit acknowledgement (see there). Making it safe — a stamped
   * carrier that survives dropping the generation — is a separate kernel change
   * gated on scripts/test-sync.
   *
   * Garbage-collecting the tombstones instead (what Yjs does by default) needs
   * to know every replica has seen the delete. A file that people mail to each
   * other has no closed set of peers and no moment at which that becomes true —
   * a copy can come back out of a mailbox a year later — so the causal cutoff
   * that makes GC safe never arrives here.
   */
  txt?: Record<string, TxtState>
  /** values set during a node's dead window — replayed on resurrection.
   * `r` is the register stamp the value belongs to: replay only while it
   * is still the current winner (a newer applied set invalidates it). */
  stash: Record<string, Record<string, { v?: unknown; r: Reg }>>
  /** live nodes whose winning parent is dead/absent (invisible but kept) */
  limbo: Record<string, SlideElement>
}

export interface ApplyResult {
  /** anything changed at all */
  changed: boolean
  /** slide list / element structure changed (sidebar + canvas rebuild) */
  structure: boolean
}

const clone = <T>(v: T): T => (v === undefined ? v : JSON.parse(JSON.stringify(v)))

/**
 * The engine, shape-injected. Not exported as the app-facing name — see
 * `SyncState` below.
 */
export class SyncEngine {
  actor: string
  lamport = 0
  /** per-actor max contiguous sequence applied */
  vv: Record<string, number> = {}
  private seq = 0
  regs: Record<string, Reg> = {}
  pos: Record<string, PosEntry> = {}
  births: Record<string, Reg> = {}
  tombs: Record<string, Reg> = {}
  txt: Record<string, TxtState> = {}
  /** dead-window set values, replayed if the node resurrects */
  stash: Record<string, Record<string, { v?: unknown; r: Reg }>> = {}
  /** live nodes whose winning parent is dead/absent — data parked here */
  limbo: Record<string, SlideElement> = {}
  // Both are keyed by REMOTE strings (node ids, actor ids) and never serialized,
  // so they are null-prototype: `??=` on a key like "constructor" must find
  // nothing, not Object.prototype.constructor. Defence in depth behind the
  // intake guards (applyOne / applyEffect).
  /** ops targeting nodes we haven't seen yet, keyed by node id */
  private pending: Record<string, Op[]> = Object.create(null)
  /** out-of-order ops per actor awaiting their gap to fill */
  private gap: Record<string, Op[]> = Object.create(null)

  /** The document shape. NO DEFAULT, deliberately: a default is how a spaces
   *  call site silently gets slides' shape and corrupts a room that then has
   *  no way to be repaired in the field. */
  readonly S: DocShape

  constructor(actor: string, shape: DocShape) {
    // A hand-built DocShape that omits `text` disables the token RGA SILENTLY:
    // every property comparison against `undefined` fails, so collaborative
    // text quietly degrades to last-writer-wins and two people typing in one
    // paragraph destroy each other's work. Measured — a literal missing this
    // field turned four passing checks red with no other symptom. Build shapes
    // with `shape()`; if you must hand-build one, this says so immediately.
    if (!shape.text) throw new Error('DocShape.text is required — build it with shape()')
    // Same reasoning for `maps`, which arrived later: a literal without it
    // does not degrade quietly, it throws deep inside the differ on the first
    // doc-property diff. Failing here names the actual cause.
    if (!shape.maps) throw new Error('DocShape.maps is required — build it with shape()')

    this.actor = actor
    this.S = shape
  }

  // --- the doc-level sender rule (see DocShape.classes) ----------------------

  /** May THIS peer emit doc-level key `k` (a top-level field, or a map's field
   *  name) on any path it mints? Content-class keys and per-key maps only; never
   *  a skipDoc key, a known non-content key, or an UNKNOWN key. */
  outboundDocKey(k: string): boolean {
    if (this.S.skipDoc.has(k)) return false // floor first — syncHistory can't reach it
    if (this.S.maps.has(k)) return true
    if (this.S.syncHistory.has(k)) return true // a history key the app chose to share
    return !this.S.classes || this.S.classes[k] === 'content'
  }

  /** Must THIS peer ignore an incoming value for doc-level key `k` (already
   *  resolved through docField)? Always for skipDoc — the never-synced set:
   *  capability, identity, file modes, history, volatile/encoding fields — so a
   *  remote peer or a local page on the channel can't replace the room keys,
   *  rewrite docId, or flip readonly/template in a victim's open deck (which the
   *  next save would write to the file). Also for a key an adopted class map
   *  knows as non-content; for an unknown key, per APPLY_UNKNOWN_DOC_KEYS. With
   *  no class map this is exactly the shipped skipDoc refusal. */
  private ignoreInboundDocKey(k: string): boolean {
    if (this.S.skipDoc.has(k)) return true // floor first — syncHistory can't reach it
    if (this.S.maps.has(k) || !this.S.classes) return false
    if (this.S.syncHistory.has(k)) return false // a history key the app chose to share
    const c = this.S.classes[k]
    if (c === undefined) return !APPLY_UNKNOWN_DOC_KEYS
    return c !== 'content'
  }

  /** The top-level field a doc-level register/op key addresses: `assets.x` →
   *  `assets` for a per-key map, else the key itself. */
  private docField(k: string): string {
    return this.mapKey(k)?.[0] ?? k
  }

  /** `regs` with every doc-level register this peer may not emit removed —
   *  the stamped / snapshot form of the state. Key order is preserved. */
  private outboundRegs(): Record<string, Reg> {
    const out: Record<string, Reg> = {}
    for (const [rk, r] of Object.entries(this.regs)) {
      if (rk.startsWith(`${DOC_NODE} `) && !this.outboundDocKey(this.docField(rk.slice(DOC_NODE.length + 1)))) continue
      out[rk] = r
    }
    return out
  }

  /** A shallow copy of `doc` holding only the top-level keys this peer may emit
   *  (plus the structural container), for a snapshot frame: the doc rides beside
   *  the state, so a value the state no longer carries must not travel either. */
  outboundDoc<T extends object>(doc: T): T {
    const src = doc as Record<string, unknown>
    const out: Record<string, unknown> = {}
    for (const k of Object.keys(src)) if (k === this.S.parents || this.outboundDocKey(k)) out[k] = src[k]
    return out as T
  }

  /** actors with buffered out-of-order ops → catch-up should be requested */
  get gappedActors(): string[] {
    return Object.keys(this.gap).filter((a) => this.gap[a].length)
  }

  /** dead iff the latest delete out-stamps the latest insert */
  dead(id: string): boolean {
    const t = this.tombs[id]
    if (!t) return false
    const b = this.births[id]
    return !b || !regNewer(b, t)
  }

  /**
   * The state, as it is stamped into a saved file.
   *
   * `opts.text: false` OMITS the token history — see the note on
   * SyncStateJSON.txt. The default is unchanged and always will be: every
   * bento/slides file in the field was written with `txt` present, and
   * scripts/test-sync-equiv.ts compares these bytes against the engine as
   * shipped.
   *
   * `text: false` is REFUSED without `unsafeOmitTextHistory: true`. Omitting the
   * history silently loses edits to different blocks on a snapshot reunion (the
   * note on SyncStateJSON.txt has the mechanism); no shipping stamp path may use
   * it, so a lean stamp must be an explicit, acknowledged act — the rigs that
   * measure the lean shape pass the flag. This is the wall that stops a future
   * size optimisation from wiring `stampInto` to a silent data loss.
   *
   * KEY ORDER IS PART OF THE FORMAT. `txt` is emitted in its original position
   * rather than appended, so a state WITH text is byte-identical whichever
   * call site produced it.
   */
  toJSON(opts: { text?: boolean; unsafeOmitTextHistory?: boolean } = {}): SyncStateJSON {
    if (opts.text === false && !opts.unsafeOmitTextHistory)
      throw new Error(
        'SyncState.toJSON({ text: false }) omits per-node token history, which silently LOSES ' +
        'edits to different blocks when a copy is reunited by snapshot (mergeSnapshot) — see the ' +
        'SyncStateJSON.txt note and docs/DECISIONS.md 2026-09-17. No shipping stamp path may use ' +
        'it; a rig that intends the lean shape passes { text: false, unsafeOmitTextHistory: true }.',
      )
    return {
      v: SYNC_V,
      lamport: this.lamport,
      vv: this.vv,
      // the sender rule: a stamped/snapshot state never carries a doc-level
      // register this peer may not emit (non-content, skipDoc, or unknown)
      regs: this.outboundRegs(),
      pos: this.pos,
      births: this.births,
      tombs: this.tombs,
      ...(opts.text === false ? {} : { txt: this.txt }),
      stash: this.stash,
      limbo: this.limbo,
    }
  }

  /**
   * `new this(actor)`, not `new SyncState(actor)`.
   *
   * The literal construction meant a SUBCLASS could not be produced through
   * fromJSON — it silently handed back the base class. That is why
   * scripts/test-sync-equiv.ts re-points prototypes to build its mutants, a
   * harness liberty its own comment flags; with this, a mutant (and every
   * app binding) restores as itself.
   */
  static fromJSON<T extends SyncEngine>(this: new (actor: string) => T, actor: string, j: SyncStateJSON): T {
    const s = new this(actor)
    if (j.v !== SYNC_V) return s // pre-v2 state keyed elements by bare id — unusable
    s.lamport = j.lamport
    s.vv = j.vv ?? {}
    s.seq = s.vv[actor] ?? 0
    // Loaded state follows the same rule as the wire: a doc-level register this
    // peer would IGNORE inbound (skipDoc, or a key its map knows as non-content)
    // is dropped, so state stamped before the allowlist can't replay a history /
    // mode / capability field. Exact by key, so no SYNC_V bump is needed.
    s.regs = {}
    for (const [rk, r] of Object.entries(j.regs ?? {})) {
      if (rk.startsWith(`${DOC_NODE} `) && s.ignoreInboundDocKey(s.docField(rk.slice(DOC_NODE.length + 1)))) continue
      s.regs[rk] = r
    }
    s.pos = j.pos ?? {}
    s.births = j.births ?? {}
    s.tombs = j.tombs ?? {}
    s.txt = j.txt ?? {}
    s.stash = j.stash ?? {}
    s.limbo = j.limbo ?? {}
    return s
  }

  // --- local op minting ----------------------------------------------------

  private stamp(): OpBase {
    this.lamport++
    this.seq++
    this.vv[this.actor] = this.seq
    return { a: this.actor, s: this.seq, l: this.lamport }
  }

  /**
   * Adopt a document that has never synced: assign deterministic pos entries
   * from current array order (both replicas of the same file derive the same
   * keys) with the null register [0,''] that loses to every real op.
   */
  adopt(doc: BentoDoc) {
    const ns = P(this.S, doc).length
    P(this.S, doc).forEach((sl, i) => {
      if (!this.pos[sl.id]) this.pos[sl.id] = { p: DOC_NODE, o: spreadKey(i, ns), r: [0, ''] }
      const ne = C(this.S, sl).length
      C(this.S, sl).forEach((el, j) => {
        const k = elKey(sl.id, el.id)
        if (!this.pos[k]) this.pos[k] = { p: sl.id, o: spreadKey(j, ne), r: [0, ''] }
      })
    })
  }

  // --- diffing (local mutations → ops) ------------------------------------

  /**
   * Structural diff between two document snapshots → ops, updating our own
   * registers as it mints (own ops are "pre-applied"; apply() skips them).
   */
  diff(before: BentoDoc, after: BentoDoc, opts: { text?: boolean } = {}): Op[] {
    const ops: Op[] = []
    this.seededInDiff.length = 0
    const push = <T extends Op>(o: T): T => {
      ops.push(o)
      return o
    }

    // ---- doc-level props
    const b = before as unknown as Record<string, unknown>
    const a = after as unknown as Record<string, unknown>
    for (const k of new Set([...Object.keys(b), ...Object.keys(a)])) {
      // The sender rule: only content-class keys (or per-key maps) are diffed.
      // A key this build doesn't classify is never emitted — and so a field it
      // doesn't know can never be DELETED by it either: silence is not a del.
      if (!this.outboundDocKey(k)) continue
      // `assets` and `blobs` are per-KEY registers, not whole-map ones, so two
      // people adding different assets concurrently both keep theirs.
      if (this.S.maps.has(k)) {
        const ba = (b[k] ?? {}) as Record<string, unknown>
        const aa = (a[k] ?? {}) as Record<string, unknown>
        for (const ak of new Set([...Object.keys(ba), ...Object.keys(aa)])) {
          if (JSON.stringify(ba[ak]) === JSON.stringify(aa[ak])) continue
          // An asset too big to ride in an op is skipped here and travels as a
          // blob instead: the session uploads it and publishes a reference
          // under `blobs.<key>`, which IS small enough. Deletions still sync
          // (v === undefined), so removing an asset is never stranded.
          if (k === 'assets' && typeof aa[ak] === 'string' && (aa[ak] as string).length > BLOB_INLINE_MAX) continue
          const o = push<SetOp>({ ...this.stamp(), op: 'set', k: `${k}.${ak}`, v: clone(aa[ak]) })
          this.regs[`${DOC_NODE} ${k}.${ak}`] = [o.l, o.a]
        }
        continue
      }
      if (JSON.stringify(b[k]) === JSON.stringify(a[k])) continue
      const o = push<SetOp>({ ...this.stamp(), op: 'set', k, v: clone(a[k]) })
      this.regs[`${DOC_NODE} ${k}`] = [o.l, o.a]
    }

    // ---- slides by id; elements by COMPOSITE key (slide + bare id) — the
    // same element id on many slides is the morph idiom, each copy is its
    // own node. A cross-slide move therefore diffs as del(old)+ins(new).
    const bSlides = new Map(P(this.S, before).map((s) => [s.id, s]))
    const aSlides = new Map(P(this.S, after).map((s) => [s.id, s]))
    const bEls = new Map<string, { sl: string; el: SlideElement }>()
    const aEls = new Map<string, { sl: string; el: SlideElement }>()
    P(this.S, before).forEach((s) => C(this.S, s).forEach((el) => bEls.set(elKey(s.id, el.id), { sl: s.id, el })))
    P(this.S, after).forEach((s) => C(this.S, s).forEach((el) => aEls.set(elKey(s.id, el.id), { sl: s.id, el })))

    // deleted slides (cascade the elements the deleter saw, minus survivors)
    for (const [id, sl] of bSlides) {
      if (aSlides.has(id)) continue
      const cas = C(this.S, sl).map((e) => elKey(id, e.id)).filter((k) => !aEls.has(k))
      const o = push<DelOp>({ ...this.stamp(), op: 'del', kind: 'slide', id, cas })
      this.tombs[id] = [o.l, o.a]
      this.stashNode(sl as unknown as Record<string, unknown>, id)
      cas.forEach((ek) => {
        this.tombs[ek] = [o.l, o.a]
        const node = C(this.S, sl).find((e) => elKey(id, e.id) === ek)
        if (node) this.stashNode(node as unknown as Record<string, unknown>, ek)
        delete this.limbo[ek]
        delete this.txt[ek] // local tomb is the freshest stamp — always out-ranks
      })
    }
    // inserted (or resurrected) slides
    const afterIds = P(this.S, after).map((s) => s.id)
    for (let i = 0; i < afterIds.length; i++) {
      const id = afterIds[i]
      if (bSlides.has(id)) continue
      const sl = aSlides.get(id)!
      const ord = this.keyAround(DOC_NODE, afterIds, i)
      const o = push<InsOp>({ ...this.stamp(), op: 'ins', kind: 'slide', id, ord, node: clone(sl) })
      this.births[id] = [o.l, o.a]
      this.pos[id] = { p: DOC_NODE, o: ord, r: [o.l, o.a] }
      delete this.txt[id]
      delete this.stash[id] // fresh birth voids parked values (receivers do this in replayStash)
      const ne = C(this.S, sl).length
      C(this.S, sl).forEach((el, j) => {
        const k = elKey(id, el.id)
        this.births[k] = [o.l, o.a]
        this.pos[k] = { p: id, o: spreadKey(j, ne), r: [o.l, o.a] }
        delete this.txt[k] // rebirth voids stale text generations
        delete this.stash[k]
      })
    }
    // kept slides: prop diffs
    for (const [id, sl] of aSlides) {
      const prev = bSlides.get(id)
      if (!prev || prev === sl) continue
      const bp = prev as unknown as Record<string, unknown>
      const ap = sl as unknown as Record<string, unknown>
      for (const k of new Set([...Object.keys(bp), ...Object.keys(ap)])) {
        if (k === this.S.children || k === 'id') continue
        if (JSON.stringify(bp[k]) === JSON.stringify(ap[k])) continue
        // Text on a PARENT gets the same token RGA as text on a child. An app
        // whose text lives one level up (bento/type: a block IS the paragraph)
        // would otherwise get a last-writer-wins register here, and two people
        // typing in one paragraph would silently destroy each other's work.
        if (k === this.S.text && opts.text && typeof bp[k] === 'string' && typeof ap[k] === 'string') {
          const t = this.diffText(id, bp[k] as string, ap[k] as string)
          if (t) {
            push(t)
            continue
          }
        }
        const o = push<SetOp>({ ...this.stamp(), op: 'set', sl: id, k, v: clone(ap[k]) })
        this.regs[`${id} ${k}`] = [o.l, o.a]
        if (k === this.S.text) delete this.txt[id] // LWW reset wins over RGA state
      }
    }
    // slide order: minimal ord ops (keep the longest already-ordered run).
    // ALL ids participate — fresh inserts got keys above, but the reorder
    // pass must see them or its re-keying can leapfrog their positions
    this.diffOrder(afterIds, DOC_NODE, 'slide', push)

    // ---- elements
    for (const [id, rec] of bEls) {
      if (aEls.has(id)) continue
      if (this.tombs[id] && this.dead(id)) continue // died with its slide above
      const o = push<DelOp>({ ...this.stamp(), op: 'del', kind: 'element', id })
      this.tombs[id] = [o.l, o.a]
      this.stashNode(rec.el as unknown as Record<string, unknown>, id)
      delete this.limbo[id]
      delete this.txt[id]
    }
    for (const [id, { sl, el }] of aEls) {
      const prev = bEls.get(id)
      if (!prev) {
        if (this.births[id] && !this.dead(id) && this.pos[id]?.p === sl) continue // came with a fresh slide ins above
        const sib = C(this.S, aSlides.get(sl)!).map((e) => elKey(sl, e.id))
        const ord = this.keyAround(sl, sib, sib.indexOf(id))
        const o = push<InsOp>({ ...this.stamp(), op: 'ins', kind: 'element', id, sl, ord, node: clone(el) })
        this.births[id] = [o.l, o.a]
        this.pos[id] = { p: sl, o: ord, r: [o.l, o.a] }
        delete this.txt[id] // rebirth voids stale text generations
        delete this.stash[id]
        continue
      }
      if (prev.el !== el || JSON.stringify(prev.el) !== JSON.stringify(el)) {
        const bp = prev.el as unknown as Record<string, unknown>
        const ap = el as unknown as Record<string, unknown>
        for (const k of new Set([...Object.keys(bp), ...Object.keys(ap)])) {
          if (k === 'id') continue
          if (JSON.stringify(bp[k]) === JSON.stringify(ap[k])) continue
          if (k === this.S.text && opts.text && typeof bp[this.S.text] === 'string' && typeof ap[this.S.text] === 'string') {
            const t = this.diffText(id, bp[this.S.text] as string, ap[this.S.text] as string)
            if (t) {
              push(t)
              continue
            }
          }
          const o = push<SetOp>({ ...this.stamp(), op: 'set', sl, el: id, k, v: clone(ap[k]) })
          this.regs[`${id} ${k}`] = [o.l, o.a]
          if (k === this.S.text) delete this.txt[id] // LWW reset wins over RGA state
        }
      }
      // no cross-slide move branch: the composite key IS (slide, id), so a
      // moved element always lands in the delete/insert passes above
    }
    // element order within each surviving slide (all ids — see slide pass)
    for (const [id, sl] of aSlides) {
      if (!bSlides.has(id)) continue
      this.diffOrder(C(this.S, sl).map((e) => elKey(id, e.id)), id, 'element', push)
    }

    // remote ops that pended awaiting a seed can resolve against seeds this
    // diff just created — drained AFTER diffing so comparisons stay stable
    for (const el of this.seededInDiff) this.drainPending(after, el)
    this.seededInDiff.length = 0

    return ops
  }

  private seededInDiff: string[] = []

  /** ord key for position i within the id list `ids` under parent `p`. */
  private keyAround(p: string, ids: string[], i: number): string {
    const ordOf = (id: string | undefined) =>
      id && this.pos[id] && this.pos[id].p === p ? this.pos[id].o : undefined
    let lo = ''
    for (let k = i - 1; k >= 0; k--) {
      const o = ordOf(ids[k])
      if (o) {
        lo = o
        break
      }
    }
    let hi = ''
    for (let k = i + 1; k < ids.length; k++) {
      const o = ordOf(ids[k])
      if (o && (!lo || o > lo)) {
        hi = o
        break
      }
    }
    return keyBetween(lo, hi)
  }

  /**
   * Emit ord ops for ids whose relative order changed: keep a longest
   * increasing run (by current pos key) untouched, re-key the rest.
   */
  private diffOrder(
    ids: string[],
    parent: string,
    kind: 'slide' | 'element',
    push: <T extends Op>(o: T) => T,
  ) {
    if (ids.some((id) => !this.pos[id])) return // unknown ids — keyed this diff
    const keys = ids.map((id) => this.pos[id].o + ' ' + id)
    const keep = new Set(longestIncreasing(keys))
    for (let i = 0; i < ids.length; i++) {
      if (keep.has(i) && this.pos[ids[i]].p === parent) continue
      const id = ids[i]
      let lo = ''
      for (let k = i - 1; k >= 0; k--) {
        const e = this.pos[ids[k]]
        if (e && e.p === parent) {
          lo = e.o
          break
        }
      }
      let hi = ''
      for (let k = i + 1; k < ids.length; k++) {
        if (!keep.has(k)) continue
        const e = this.pos[ids[k]]
        if (e && e.p === parent && e.o > lo) {
          hi = e.o
          break
        }
      }
      const ord = keyBetween(lo, hi)
      const o = push<OrdOp>({
        ...this.stamp(),
        op: 'ord',
        kind,
        id,
        ord,
        ...(kind === 'element' ? { sl: parent } : {}),
      })
      this.pos[id] = { p: parent, o: ord, r: [o.l, o.a] }
    }
  }

  // --- text RGA (M3) -------------------------------------------------------

  /** local html edit → txt op (or null → caller falls back to set-html) */
  private diffText(el: string, oldHtml: string, newHtml: string): TxtOp | null {
    const had = !!this.txt[el]
    let st = this.txt[el]
    if (!st) {
      // Deterministic seed: (current html-register/birth lamport, content
      // hash). Concurrent first-editors of the same base derive the SAME
      // seed, so both their edits merge; after a set-html reset or a node
      // rebirth the lamport has grown, so fresh seeds out-rank stale ones.
      const sd: Reg = [
        Math.max(this.regs[`${el} ${this.S.text}`]?.[0] ?? 0, this.births[el]?.[0] ?? 0),
        contentHash(oldHtml),
      ]
      st = this.txt[el] = { sd, toks: seedTokens(sd, oldHtml) }
      this.seededInDiff.push(el)
    }
    if (materialize(st) !== oldHtml) {
      delete this.txt[el] // RGA drifted from the model — heal via LWW reset
      return null
    }
    const vis = st.toks.filter((t) => !t.d)
    const oldT = vis.map((t) => t.t)
    const newT = tokenize(newHtml)
    let p = 0
    while (p < oldT.length && p < newT.length && oldT[p] === newT[p]) p++
    let sOld = oldT.length
    let sNew = newT.length
    while (sOld > p && sNew > p && oldT[sOld - 1] === newT[sNew - 1]) {
      sOld--
      sNew--
    }
    const del = vis.slice(p, sOld).map((t) => t.id)
    const insToks = newT.slice(p, sNew)
    const op: TxtOp = {
      ...this.stamp(),
      op: 'txt',
      el,
      sd: st.sd,
      ...(had ? {} : { base: oldHtml }),
      ...(del.length ? { del } : {}),
      ...(insToks.length ? { ins: [{ at: p > 0 ? vis[p - 1].id : '^', toks: insToks }] } : {}),
    }
    applyTxtToState(st, op)
    if (materialize(st) !== newHtml) {
      delete this.txt[el]
      return null // self-heal: fall back to whole-value set
    }
    return op
  }

  // --- applying remote ops -------------------------------------------------

  apply(doc: BentoDoc, ops: Op[]): ApplyResult {
    const res: ApplyResult = { changed: false, structure: false }
    for (const op of ops) this.applyOne(doc, op, res)
    if (res.structure) this.rematerialize(doc)
    return res
  }

  private applyOne(doc: BentoDoc, op: Op, res: ApplyResult) {
    if (op.a === this.actor) return // own ops are pre-applied at diff time
    // An actor id is used as a key in vv / gap; a prototype-shaped one is no real
    // peer, so it is dropped before it can touch either table.
    if (protoName(op.a)) return
    const seen = this.vv[op.a] ?? 0
    if (op.s <= seen) return // duplicate
    if (op.s > seen + 1) {
      // gap — buffer until the missing ops arrive (catch-up fills them)
      const g = (this.gap[op.a] ??= [])
      if (!g.some((o) => o.s === op.s)) {
        g.push(op)
        g.sort((x, y) => x.s - y.s)
      }
      return
    }
    this.vv[op.a] = op.s
    this.lamport = Math.max(this.lamport, op.l)
    this.applyEffect(doc, op, res)
    const g = this.gap[op.a]
    while (g && g.length && g[0].s === this.vv[op.a] + 1) {
      const next = g.shift()!
      this.vv[op.a] = next.s
      this.lamport = Math.max(this.lamport, next.l)
      this.applyEffect(doc, next, res)
    }
  }

  private applyEffect(doc: BentoDoc, op: Op, res: ApplyResult) {
    // A prototype-shaped name anywhere in the op: CONSUMED, never applied. The
    // version vector already advanced in applyOne, so the sender's later ops
    // still deliver — dropping it from the sequence would stall them.
    if (protoOp(op)) {
      dbg(String((op as { el?: string }).el ?? '?'), `${op.op} DROP prototype-shaped name`)
      return
    }
    // A FLAT document has no element layer, so an element-scoped op has
    // nowhere to land. It should never arrive — peers in a room share a shape
    // — but the frame came off the wire, and materializing it would either
    // throw against the frozen child array or invent a key the format does not
    // have. Dropping is the only safe reading, and the version vector still
    // advanced in applyOne, so delivery does not stall behind it.
    const scope = op as Partial<{ el: string; kind: string; id: string }>
    // `el` does NOT mean "element" on a txt op — there it is the NODE key,
    // which for a flat document is the block's own id. Reading it as an
    // element key here dropped every collaborative keystroke type would ever
    // send, while structure ops kept converging: the rig saw one author's
    // edits land and the other's silently vanish.
    const elementScoped = scope.kind === 'element' ||
      (op.op === 'txt' ? String(scope.el).includes(SEP) : scope.el !== undefined)
    if (this.S.children === null && elementScoped) {
      dbg(scope.el ?? scope.id ?? '?', `${op.op} DROP no element layer in this shape`)
      return
    }
    switch (op.op) {
      case 'set':
        this.applySet(doc, op, res)
        break
      case 'ins':
        this.applyIns(doc, op, res)
        break
      case 'del':
        this.applyDel(doc, op, res)
        break
      case 'ord':
        this.applyOrd(doc, op, res)
        break
      case 'txt':
        this.applyTxt(doc, op, res)
        break
    }
  }

  private findSlide(doc: BentoDoc, id: string): Slide | undefined {
    return P(this.S, doc).find((s) => s.id === id)
  }
  /** composite-key lookup: an element node only ever lives on its key's
   * slide (or in limbo) — the same bare id on other slides is other nodes */
  private findEl(doc: BentoDoc, key: string): SlideElement | undefined {
    const s = this.findSlide(doc, keySlide(key))
    const bare = keyEl(key)
    return (s ? C(this.S, s) : undefined)?.find((e) => e.id === bare) ?? this.limbo[key]
  }

  /**
   * Split a doc-level property key into (map, entry) if it addresses a
   * declared map — `assets.logo` → ['assets','logo'].
   *
   * Matched against the SHAPE rather than by looking for a dot: an ordinary
   * property whose name happens to contain one must not be mistaken for a map
   * entry and quietly written into a sub-object.
   */
  private mapKey(k: string): [string, string] | undefined {
    const i = k.indexOf('.')
    if (i <= 0) return undefined
    const field = k.slice(0, i)
    return this.S.maps.has(field) ? [field, k.slice(i + 1)] : undefined
  }

  /** either level: composite keys carry SEP, parent ids never do */
  private findNode(doc: BentoDoc, id: string): Record<string, unknown> | undefined {
    return (id.includes(SEP) ? this.findEl(doc, id) : this.findSlide(doc, id)) as
      | Record<string, unknown>
      | undefined
  }

  private applySet(doc: BentoDoc, op: SetOp, res: ApplyResult) {
    const nodeId = op.el ?? op.sl ?? DOC_NODE
    // A doc-level key this peer's map knows as non-content (or skipDoc) is never
    // applied, whatever the sender claims — no register, no value. Checked before
    // any bookkeeping so a hostile or older peer leaves no trace. With no class
    // map this is exactly the shipped skipDoc refusal.
    if (nodeId === DOC_NODE && this.ignoreInboundDocKey(this.docField(op.k))) return
    const rk = `${nodeId} ${op.k}`
    if (!newer(op.l, op.a, this.regs[rk])) return
    // birth gate: an ins is a whole-node assignment — sets older than the
    // node's (re)birth are superseded everywhere (register still advances)
    const birth = nodeId !== DOC_NODE ? this.births[nodeId] : undefined
    if (birth && !newer(op.l, op.a, birth)) {
      dbg(nodeId, `set ${op.k}@${op.l},${op.a} GATED by birth ${JSON.stringify(birth)}`)
      this.regs[rk] = [op.l, op.a]
      return
    }
    if (nodeId !== DOC_NODE && this.dead(nodeId)) {
      // register still advances (state convergence) and the value parks in
      // the stash — a resurrecting ins replays stashed values whose regs
      // outrank it, so every replica lands on the same post-resurrect state
      dbg(nodeId, `set ${op.k}@${op.l},${op.a} DEAD-STASH`)
      this.regs[rk] = [op.l, op.a]
      ;(this.stash[nodeId] ??= {})[op.k] =
        op.v === undefined ? { r: [op.l, op.a] } : { v: clone(op.v), r: [op.l, op.a] }
      return
    }
    if (nodeId === DOC_NODE) {
      this.regs[rk] = [op.l, op.a]
      const dot = this.mapKey(op.k)
      if (dot) {
        const [field, ak] = dot
        const map = ((doc as unknown as Record<string, Record<string, unknown>>)[field] ??= {})
        if (op.v === undefined) delete map[ak]
        else map[ak] = clone(op.v)
      } else {
        const d = doc as unknown as Record<string, unknown>
        if (op.v === undefined) delete d[op.k]
        else d[op.k] = clone(op.v)
      }
      res.changed = true
      res.structure = true
      return
    }
    const target = (op.el ? this.findEl(doc, op.el) : this.findSlide(doc, op.sl!)) as
      | Record<string, unknown>
      | undefined
    if (!target) {
      dbg(nodeId, `set ${op.k}@${op.l},${op.a} PEND no-target`)
      ;(this.pending[nodeId] ??= []).push(op)
      return
    }
    // NB: v === undefined means "delete the key" (handled below), and
    // JSON.stringify(undefined) is undefined — String() keeps this debug
    // line from throwing on every property REMOVAL.
    dbg(nodeId, `set ${op.k}@${op.l},${op.a} APPLY ${String(JSON.stringify(op.v)).slice(0, 40)}`)
    if (nodeId !== DOC_NODE && op.k === this.S.text) {
      const gen = this.txt[nodeId]
      if (gen && cmpReg([op.l, op.a], gen.sd) < 0) {
        // a live text generation outranks this set — value loses, reg advances
        this.regs[rk] = [op.l, op.a]
        return
      }
      dbg(nodeId, `set-text@${op.l},${op.a} RESET kills gen`)
      delete this.txt[nodeId] // the set out-stamps the generation: reset
    }
    this.regs[rk] = [op.l, op.a]
    if (op.v === undefined) delete target[op.k]
    else target[op.k] = clone(op.v)
    res.changed = true
    if (!op.el) res.structure = true // slide props show in the sidebar
  }

  private applyIns(doc: BentoDoc, op: InsOp, res: ApplyResult) {
    const stamp: Reg = [op.l, op.a]
    if (op.kind === 'slide') {
      // a slide ins = one slide-level assignment + an independent element
      // ins per member. Member processing must NOT be skipped when the
      // slide-level record loses its LWW race — replicas that saw this op
      // first ran it, so everyone must.
      const src = op.node as Slide
      this.insertSlideLevel(doc, op.id, op.ord, src, stamp, res)
      const ne = C(this.S, src).length
      C(this.S, src).forEach((e, j) => this.insertElement(doc, elKey(op.id, e.id), op.id, spreadKey(j, ne), e, stamp, res))
      this.drainPending(doc, op.id)
      C(this.S, src).forEach((e) => this.drainPending(doc, elKey(op.id, e.id)))
    } else {
      this.insertElement(doc, op.id, op.sl!, op.ord, op.node as SlideElement, stamp, res)
      this.drainPending(doc, op.id)
    }
  }

  private insertSlideLevel(doc: BentoDoc, id: string, ord: string, src: Slide, stamp: Reg, res: ApplyResult) {
    const birth = this.births[id]
    if (birth && !newer(stamp[0], stamp[1], birth)) return // an older create
    this.births[id] = stamp
    if (!this.pos[id] || regNewer(stamp, this.pos[id].r)) this.pos[id] = { p: DOC_NODE, o: ord, r: stamp }
    if (this.txt[id] && this.txt[id].sd[0] < stamp[0]) {
      dbg(id, `slide-ins@${stamp[0]},${stamp[1]} voids gen`)
      delete this.txt[id]
    }
    res.changed = true
    res.structure = true
    if (this.dead(id)) return // a delete still out-stamps this insert
    const existing = this.findSlide(doc, id)
    if (existing) {
      this.assignNode(existing as unknown as Record<string, unknown>, src as unknown as Record<string, unknown>, id, stamp, this.S.children === null ? ['id'] : ['id', this.S.children])
    } else {
      const sl = clone(src)
      setC(this.S, sl, []) // members materialize separately via insertElement
      P(this.S, doc).push(sl)
      this.replayStash(sl as unknown as Record<string, unknown>, id, stamp)
    }
  }

  private insertElement(doc: BentoDoc, id: string, parent: string, ord: string, node: SlideElement, stamp: Reg, res: ApplyResult) {
    const birth = this.births[id]
    dbg(id, `insertElement stamp=${JSON.stringify(stamp)} birth=${JSON.stringify(birth)} accepted=${!birth || newer(stamp[0], stamp[1], birth)}`)
    if (birth && !newer(stamp[0], stamp[1], birth)) return // an older create
    this.births[id] = stamp
    if (!this.pos[id] || regNewer(stamp, this.pos[id].r)) this.pos[id] = { p: parent, o: ord, r: stamp }
    // rebirth voids STALE generations only — a late-arriving old ins must
    // not kill a generation seeded above its lamport
    if (this.txt[id] && this.txt[id].sd[0] < stamp[0]) {
      dbg(id, `el-ins@${stamp[0]},${stamp[1]} voids gen`)
      delete this.txt[id]
    }
    res.changed = true
    res.structure = true
    if (this.dead(id)) return // a delete still out-stamps this insert
    const existing = this.findEl(doc, id)
    let live: SlideElement
    if (existing) {
      // the live copy (doc or limbo) keeps applied set-values; the payload
      // assigns over properties whose registers are older than the birth
      this.assignNode(existing as unknown as Record<string, unknown>, node as unknown as Record<string, unknown>, id, stamp, ['id'])
      live = existing
    } else {
      const el = clone(node)
      const p = this.pos[id].p
      const sl = this.findSlide(doc, p)
      if (sl && !this.dead(p)) C(this.S, sl).push(el)
      else this.limbo[id] = el
      this.replayStash(el as unknown as Record<string, unknown>, id, stamp)
      live = el
    }
    // a text generation that survived the node's death (it out-ranked the
    // tomb) is the html authority — re-materialize over the ins payload
    const g = this.txt[id]
    if (g && this.S.text in live) (live as unknown as Record<string, string>)[this.S.text] = materialize(g)
  }

  /**
   * Whole-node assignment from an ins payload: every property whose register
   * is OLDER than the (re)birth takes the payload's value; properties with
   * newer registers keep the set-winner (value present locally, or parked in
   * the stash). Runs identically on every replica — including ones where the
   * node never died — which is what makes resurrection convergent.
   */
  private assignNode(node: Record<string, unknown>, payload: Record<string, unknown>, id: string, birth: Reg, skip: string[]) {
    for (const k of new Set([...Object.keys(node), ...Object.keys(payload)])) {
      if (skip.includes(k)) continue
      if (k === this.S.text && this.txt[id]) {
        if (this.txt[id].sd[0] < birth[0]) {
          // the RGA's seed predates this rebirth — void it; the assignment
          // wins even over higher-lamport deltas (they drop on every replica)
          delete this.txt[id]
          if (payload[k] === undefined) delete node[k]
          else node[k] = clone(payload[k])
        }
        // else: the generation outranks the assignment — keep its text
        continue
      }
      const r = this.regs[`${id} ${k}`]
      if (r && regNewer(r, birth)) {
        dbg(id, `assign ${k} KEEP (reg ${JSON.stringify(r)} > birth ${JSON.stringify(birth)})`)
        continue // a newer set beats the assignment
      }
      // String(...) is NOT belt-and-braces: `k` comes from the union of the
      // local node's keys and the payload's, so `payload[k]` is undefined
      // exactly on the property-REMOVAL path two lines below — and
      // JSON.stringify(undefined) is undefined, not "undefined". dbg() builds
      // its argument eagerly, so this threw whether or not anyone was
      // debugging. Third occurrence of this one bug in this file; the other
      // two already carry the same guard.
      dbg(id, `assign ${k} := ${String(JSON.stringify(payload[k])).slice(0, 40)}`)
      if (payload[k] === undefined) delete node[k]
      else node[k] = clone(payload[k])
    }
    this.replayStash(node, id, birth)
  }

  /**
   * Park a to-be-removed node's registered property values: a register newer
   * than an eventual rebirth must win over the rebirth payload, so its value
   * has to survive the removal (replayStash decides at rebirth time).
   */
  private stashNode(node: Record<string, unknown>, id: string) {
    const pref = `${id} `
    for (const rk of Object.keys(this.regs)) {
      if (!rk.startsWith(pref)) continue
      const k = rk.slice(pref.length)
      const r = clone(this.regs[rk])
      const st = (this.stash[id] ??= {})
      // overwrite entries whose register is stale — the current register's
      // value (living on this node) is the authoritative parked value
      if (!(k in st) || cmpReg(st[k].r, r) !== 0)
        st[k] = node[k] === undefined ? { r } : { v: clone(node[k]), r }
    }
  }

  /** replay dead-window values that out-rank a resurrecting ins, then drop the stash */
  private replayStash(node: Record<string, unknown>, id: string, birth: Reg) {
    const st = this.stash[id]
    if (!st) return
    for (const [k, ent] of Object.entries(st)) {
      const r = this.regs[`${id} ${k}`]
      if (!r || !regNewer(r, birth)) continue
      // stale guard: the parked value must belong to the CURRENT register —
      // a newer set that applied elsewhere supersedes it
      if (cmpReg(ent.r, r) !== 0) continue
      // String(): a REMOVAL parks an entry with no `v`, and
      // JSON.stringify(undefined) is undefined — `.slice` on that throws, and
      // dbg's argument is built eagerly whether or not debugging is on. This is
      // the SAME defect fixed at the `set` site above, in the second place it
      // occurs: the fix went where the bug was found rather than everywhere the
      // pattern was, and the rig covered the found site only. Reached whenever a
      // property removal is stashed during a node's dead window and replayed on
      // resurrection.
      dbg(id, `stash-replay ${k} := ${String(JSON.stringify(ent.v)).slice(0, 40)}`)
      if ('v' in ent) node[k] = clone(ent.v)
      else delete node[k]
      if (k === this.S.text) delete this.txt[id]
    }
    delete this.stash[id]
  }

  private drainPending(doc: BentoDoc, id: string) {
    const ps = this.pending[id]
    if (!ps) return
    delete this.pending[id]
    const r: ApplyResult = { changed: false, structure: false }
    for (const p of ps) this.applyEffect(doc, p, r)
  }

  private applyDel(doc: BentoDoc, op: DelOp, res: ApplyResult) {
    const bump = (id: string) => {
      if (!this.tombs[id] || newer(op.l, op.a, this.tombs[id])) this.tombs[id] = [op.l, op.a]
    }
    const removeElement = (key: string) => {
      dbg(key, `removeElement (tomb ${JSON.stringify(this.tombs[key])})`)
      const lb = this.limbo[key]
      if (lb) this.stashNode(lb as unknown as Record<string, unknown>, key)
      delete this.limbo[key]
      // a tombstone kills only generations it out-ranks; an out-ranking gen
      // survives the node's death (pend-on-dead replicas rebuild it on
      // resurrection from their buffered ops — this side keeps it directly)
      const g = this.txt[key]
      if (g && cmpReg(this.tombs[key] ?? [0, ''], g.sd) > 0) delete this.txt[key]
      const s = this.findSlide(doc, keySlide(key))
      const bare = keyEl(key)
      const i = s ? C(this.S, s).findIndex((e) => e.id === bare) : -1
      if (s && i >= 0) {
        this.stashNode(C(this.S, s)[i] as unknown as Record<string, unknown>, key)
        C(this.S, s).splice(i, 1)
      }
    }
    bump(op.id)
    if (op.kind === 'slide') {
      for (const eid of op.cas ?? []) {
        bump(eid)
        // the cascaded element may have been concurrently moved elsewhere —
        // delete-wins removes it wherever it currently lives
        if (this.dead(eid)) removeElement(eid)
      }
      if (this.dead(op.id)) {
        const i = P(this.S, doc).findIndex((s) => s.id === op.id)
        if (i >= 0) {
          const [gone] = P(this.S, doc).splice(i, 1)
          this.stashNode(gone as unknown as Record<string, unknown>, op.id)
          // survivors (concurrently inserted) park in limbo under their key
          for (const el of C(this.S, gone)) {
            const k = elKey(op.id, el.id)
            if (!this.dead(k)) this.limbo[k] = el
          }
        }
      }
    } else if (this.dead(op.id)) {
      removeElement(op.id)
    }
    // a tombstone is a liveness record: buffered ops resolve against it
    this.drainPending(doc, op.id)
    for (const eid of op.cas ?? []) this.drainPending(doc, eid)
    res.changed = true
    res.structure = true
  }

  private applyOrd(doc: BentoDoc, op: OrdOp, res: ApplyResult) {
    const cur = this.pos[op.id]
    if (cur && !newer(op.l, op.a, cur.r)) return
    const p = op.kind === 'slide' ? DOC_NODE : (op.sl ?? cur?.p)
    if (!p) {
      ;(this.pending[op.id] ??= []).push(op)
      return
    }
    this.pos[op.id] = { p, o: op.ord, r: [op.l, op.a] }
    if (this.dead(op.id)) return // moves never resurrect — data may be gone
    if (op.kind === 'element' && !this.findEl(doc, op.id)) {
      ;(this.pending[op.id] ??= []).push(op)
      return
    }
    res.changed = true
    res.structure = true
  }

  private applyTxt(doc: BentoDoc, op: TxtOp, res: ApplyResult) {
    // Text generations: the html REGISTER holds plain-set stamps only; a
    // generation (seed) duels sets AS A UNIT. Void whenever the generation
    // predates a rebirth or a winning set-reset — even for deltas with
    // higher lamports (a delta needs its base; the base was reassigned).
    // txt ops never touch regs, so registers converge by construction.
    const birth = this.births[op.el]
    if (birth && op.sd[0] < birth[0]) {
      dbg(op.el, `txt@${op.l},${op.a} DROP birth ${JSON.stringify(birth)} > sd ${op.sd[0]}`)
      return
    }
    const rr = this.regs[`${op.el} ${this.S.text}`]
    if (rr && cmpReg(op.sd, rr) < 0) {
      dbg(op.el, `txt@${op.l},${op.a} DROP reg ${JSON.stringify(rr)}`)
      return
    }
    if (this.dead(op.el)) {
      // dead is a TRANSIENT local view (a resurrect may be in flight) — pend
      // rather than drop, so survival depends only on converged state
      dbg(op.el, `txt@${op.l},${op.a} PEND dead`)
      ;(this.pending[op.el] ??= []).push(op)
      return
    }
    let st = this.txt[op.el]
    dbg(op.el, `txt@${op.l},${op.a} apply st=${st ? JSON.stringify(st.sd) : 'none'} base=${op.base !== undefined}`)
    const c = st ? cmpReg(op.sd, st.sd) : 1
    if (c > 0) {
      if (op.base === undefined) {
        // seeds are deterministic (lamport + content hash): if our current
        // html IS the seed's base we can rebuild it without the base op
        const node = this.findNode(doc, op.el)
        const html = node && this.S.text in node ? ((node as unknown as Record<string, string>)[this.S.text] as string) : undefined
        if (html !== undefined && contentHash(html) === op.sd[1]) {
          dbg(op.el, `txt@${op.l},${op.a} RECONSTRUCT from html`)
          st = this.txt[op.el] = { sd: clone(op.sd), toks: seedTokens(op.sd, html) }
        } else {
          dbg(op.el, `txt@${op.l},${op.a} PEND`)
          ;(this.pending[op.el] ??= []).push(op) // seed def hasn't arrived
          return
        }
      } else {
        dbg(op.el, `txt@${op.l},${op.a} REBUILD from base`)
        st = this.txt[op.el] = { sd: clone(op.sd), toks: seedTokens(op.sd, op.base) }
      }
      this.drainPending(doc, op.el) // ops that pended awaiting this seed
    } else if (c < 0) {
      return // op against a superseded seed — dropped everywhere
    }
    // same-seed unknown anchor = the anchor's insert is still in flight
    // (cross-actor delivery race) — pend until it lands
    if (op.ins && op.ins.some((g) => g.at !== '^' && !st!.toks.some((t) => t.id === g.at))) {
      dbg(op.el, `txt@${op.l},${op.a} PEND anchor`)
      ;(this.pending[op.el] ??= []).push(op)
      return
    }
    const advanced = applyTxtToState(st!, op)
    const el = this.findNode(doc, op.el)
    if (el && this.S.text in el) {
      ;(el as unknown as Record<string, string>)[this.S.text] = materialize(st!)
      res.changed = true
    } else if (!el) {
      ;(this.pending[op.el] ??= []).push(op)
    }
    // this op's tokens may be the anchor a pended op was waiting for —
    // drain only on real progress (a replayed no-op must not re-drain)
    if (advanced) this.drainPending(doc, op.el)
  }

  /** rebuild array orders (and limbo restores) from pos registers */
  private rematerialize(doc: BentoDoc) {
    const ord = (id: string) => (this.pos[id] ? this.pos[id].o : '')
    const cmp = (x: string, y: string) => {
      const a = ord(x)
      const b = ord(y)
      if (a !== b) return a < b ? -1 : 1
      return x < y ? -1 : 1
    }
    P(this.S, doc).sort((s1, s2) => cmp(s1.id, s2.id))
    const slideById = new Map(P(this.S, doc).map((s) => [s.id, s]))
    for (const [key, el] of Object.entries(this.limbo)) {
      const p = this.pos[key]?.p
      if (p && slideById.has(p) && !this.dead(p) && !this.dead(key)) {
        const dest = slideById.get(p)!
        if (!C(this.S, dest).some((e) => e.id === el.id)) C(this.S, dest).push(el)
        else dbg(key, `limbo-restore DROP dup x=${(el as any).x}`)
        delete this.limbo[key]
        this.drainPending(doc, key)
      }
    }
    // elements never relocate across slides (the composite key pins them to
    // one slide for life) — only sort by pos key and dedupe within the slide
    // (a node whose data travelled two routes can transiently duplicate)
    for (const sl of P(this.S, doc)) {
      C(this.S, sl).sort((e1, e2) => cmp(elKey(sl.id, e1.id), elKey(sl.id, e2.id)))
      setC(this.S, sl, C(this.S, sl).filter((e, i) => {
        const dup = i > 0 && e.id === C(this.S, sl)[i - 1].id
        if (dup) dbg(elKey(sl.id, e.id), `remat dedupe DROP x=${(e as any).x}`)
        return !dup
      }))
    }
  }

  // --- state-based merge (snapshots, file forks, catch-up beyond the log) --

  /**
   * Merge a remote (doc, state) snapshot into ours. Register-wise LWW with
   * value adoption from the winning side; liveness max; RGA token union.
   * merge(A←B) then merge(B←A) leaves both sides identical.
   */
  mergeSnapshot(doc: BentoDoc, rdoc: BentoDoc, rstate: SyncStateJSON): ApplyResult {
    const res: ApplyResult = { changed: false, structure: false }
    if (rstate.v !== SYNC_V) return res // pre-v2 snapshot: bare-id keys, unusable
    // A snapshot whose state or doc carries a prototype-shaped key anywhere is
    // refused whole: its ids/keys feed pos, births, regs, stash and doc writes,
    // and no honest peer ever produces one. Catch-up still arrives via ops.
    if (hasProtoKey(rstate) || hasProtoKey(rdoc)) return res
    this.lamport = Math.max(this.lamport, rstate.lamport)
    for (const [a, s] of Object.entries(rstate.vv ?? {})) {
      if ((this.vv[a] ?? 0) < s) {
        this.vv[a] = s
        if (a === this.actor) this.seq = s
        this.gap[a] = (this.gap[a] ?? []).filter((o) => o.s > s)
        res.changed = true
      }
    }
    // liveness records (order matters: births before tombs use of dead())
    const rebirths: string[] = []
    for (const [id, r] of Object.entries(rstate.births ?? {})) {
      if (!this.births[id] || regNewer(r, this.births[id])) {
        this.births[id] = clone(r)
        rebirths.push(id) // remote saw a newer whole-node assignment
      }
    }
    for (const [id, r] of Object.entries(rstate.tombs ?? {})) {
      if (!this.tombs[id] || regNewer(r, this.tombs[id])) {
        this.tombs[id] = clone(r)
        if (this.dead(id)) {
          const g = this.txt[id]
          if (g && cmpReg(r, g.sd) > 0) delete this.txt[id]
          const lb = this.limbo[id]
          if (lb) this.stashNode(lb as unknown as Record<string, unknown>, id)
          delete this.limbo[id]
        }
        res.changed = true
      }
    }
    // pos registers
    for (const [id, rp] of Object.entries(rstate.pos ?? {})) {
      const cur = this.pos[id]
      if (!cur || regNewer(rp.r, cur.r)) {
        this.pos[id] = clone(rp)
        res.changed = true
        res.structure = true
      }
    }
    // drop nodes that are dead under merged liveness
    for (let i = P(this.S, doc).length - 1; i >= 0; i--) {
      const sl = P(this.S, doc)[i]
      if (this.dead(sl.id)) {
        P(this.S, doc).splice(i, 1)
        this.stashNode(sl as unknown as Record<string, unknown>, sl.id)
        for (const el of C(this.S, sl)) {
          const k = elKey(sl.id, el.id)
          if (!this.dead(k)) this.limbo[k] = el
          else this.stashNode(el as unknown as Record<string, unknown>, k)
        }
        res.structure = true
        res.changed = true
      } else {
        for (let j = C(this.S, sl).length - 1; j >= 0; j--) {
          const k = elKey(sl.id, C(this.S, sl)[j].id)
          if (this.dead(k)) {
            this.stashNode(C(this.S, sl)[j] as unknown as Record<string, unknown>, k)
            C(this.S, sl).splice(j, 1)
            res.structure = true
            res.changed = true
          }
        }
      }
    }
    for (const id of Object.keys(this.limbo)) {
      if (this.dead(id)) {
        this.stashNode(this.limbo[id] as unknown as Record<string, unknown>, id)
        delete this.limbo[id]
      }
    }
    // adopt remote nodes we don't have (slides first, then elements, both
    // keyed composite; remote limbo nodes count — they're invisible but
    // their data is real)
    const rEls = new Map<string, SlideElement>()
    P(this.S, rdoc).forEach((s) => C(this.S, s).forEach((e) => rEls.set(elKey(s.id, e.id), e)))
    for (const [key, el] of Object.entries(rstate.limbo ?? {})) if (!rEls.has(key)) rEls.set(key, el)
    for (const sl of P(this.S, rdoc)) {
      if (this.dead(sl.id) || this.findSlide(doc, sl.id)) continue
      const copy = clone(sl)
      setC(this.S, copy, C(this.S, copy)
        .filter((e) => !this.dead(elKey(sl.id, e.id)))
        .map((e) => {
          const lb = this.limbo[elKey(sl.id, e.id)]
          if (lb) {
            delete this.limbo[elKey(sl.id, e.id)]
            return lb
          }
          return e
        }))
      P(this.S, doc).push(copy)
      res.changed = true
      res.structure = true
    }
    for (const [key, el] of rEls) {
      if (this.dead(key) || this.findEl(doc, key)) continue
      const p = this.pos[key]?.p
      const host = p ? this.findSlide(doc, p) : undefined
      if (host && !this.dead(host.id)) C(this.S, host).push(clone(el))
      else this.limbo[key] = clone(el)
      res.changed = true
      res.structure = true
    }
    // property registers: the winning side's value lives in its doc
    const rSlides = new Map(P(this.S, rdoc).map((s) => [s.id, s]))
    const rNode = (id: string): Record<string, unknown> | undefined =>
      id === DOC_NODE
        ? (rdoc as unknown as Record<string, unknown>)
        : ((rSlides.get(id) ?? rEls.get(id)) as unknown as Record<string, unknown> | undefined)
    const lNode = (id: string): Record<string, unknown> | undefined =>
      id === DOC_NODE
        ? (doc as unknown as Record<string, unknown>)
        : ((this.findSlide(doc, id) ?? this.findEl(doc, id)) as unknown as
            | Record<string, unknown>
            | undefined)
    // whole-node assignments the remote saw and we didn't: their node value
    // supersedes our properties whose registers are older than the birth
    for (const id of rebirths) {
      if (this.dead(id)) continue
      const src = rNode(id)
      const dst = lNode(id)
      if (!src || !dst) continue
      const isSlide = rSlides.has(id) || !!this.findSlide(doc, id)
      this.assignNode(dst, src, id, this.births[id], isSlide ? this.S.children === null ? ['id'] : ['id', this.S.children] : ['id'])
      res.changed = true
      if (isSlide) res.structure = true
    }
    for (const [rk, rr] of Object.entries(rstate.regs ?? {})) {
      const sp = rk.indexOf(' ')
      const nodeId = rk.slice(0, sp)
      const key = rk.slice(sp + 1)
      // The snapshot path writes doc fields too, so it obeys the same receive
      // rule as applySet: a key this peer knows as non-content never lands.
      if (nodeId === DOC_NODE && this.ignoreInboundDocKey(this.docField(key))) continue
      if (!regNewer(rr, this.regs[rk])) continue
      this.regs[rk] = clone(rr) // registers advance even for dead nodes
      if (nodeId !== DOC_NODE) {
        const b = this.births[nodeId]
        if (b && !regNewer(rr, b)) continue // superseded by a whole-node assignment
      }
      if (nodeId !== DOC_NODE && this.dead(nodeId)) {
        // park the winning value for a potential resurrection
        const src = rNode(nodeId)
        const rstash = rstate.stash?.[nodeId]?.[key]
        if (src && src[key] !== undefined)
          (this.stash[nodeId] ??= {})[key] = { v: clone(src[key]), r: clone(rr) }
        else if (rstash) (this.stash[nodeId] ??= {})[key] = clone(rstash)
        continue
      }
      const src = rNode(nodeId)
      const dst = lNode(nodeId)
      if (!src || !dst) continue
      if (key === this.S.text) {
        const gen = this.txt[nodeId]
        if (gen && cmpReg(rr, gen.sd) < 0) continue // generation outranks the set
        if (gen) delete this.txt[nodeId]
      }
      const mk = nodeId === DOC_NODE ? this.mapKey(key) : undefined
      if (mk) {
        const [field, ak] = mk
        const rm = ((rdoc as unknown as Record<string, Record<string, unknown>>)[field] ?? {})
        const lm = ((doc as unknown as Record<string, Record<string, unknown>>)[field] ??= {})
        if (rm[ak] === undefined) delete lm[ak]
        else lm[ak] = clone(rm[ak])
      } else if (src[key] === undefined) delete dst[key]
      else dst[key] = clone(src[key])
      res.changed = true
      if (nodeId === DOC_NODE || rSlides.has(nodeId)) res.structure = true
    }
    // text RGA union (generations void when out-ranked by births or sets)
    for (const el of Object.keys(this.txt)) {
      const b = this.births[el]
      const rr = this.regs[`${el} ${this.S.text}`]
      if ((b && this.txt[el].sd[0] < b[0]) || (rr && cmpReg(this.txt[el].sd, rr) < 0))
        delete this.txt[el]
    }
    for (const [el, rt] of Object.entries(rstate.txt ?? {})) {
      if (this.dead(el)) continue
      const b = this.births[el]
      if (b && rt.sd[0] < b[0]) continue
      const rr = this.regs[`${el} ${this.S.text}`]
      if (rr && cmpReg(rt.sd, rr) < 0) continue
      const lt = this.txt[el]
      const c = lt ? cmpReg(rt.sd, lt.sd) : 1
      if (c > 0) this.txt[el] = clone(rt)
      else if (c === 0) mergeToks(lt!, rt)
      else continue
      const node = this.findNode(doc, el)
      if (node && this.S.text in node) (node as unknown as Record<string, string>)[this.S.text] = materialize(this.txt[el])
      res.changed = true
    }
    if (res.structure) this.rematerialize(doc)
    return res
  }

  /** ops from our log that this version vector is missing (peer catch-up) */
  missingFor(log: Op[], vv: Record<string, number>): Op[] {
    return log.filter((o) => o.s > (vv[o.a] ?? 0))
  }
}

const cmpReg = (x: Reg, y: Reg): number => x[0] - y[0] || (x[1] < y[1] ? -1 : x[1] > y[1] ? 1 : 0)

/** FNV-1a — deterministic content hash for RGA seed identity */
export function contentHash(s: string): string {
  let h = 0x811c9dc5
  for (let i = 0; i < s.length; i++) {
    h ^= s.charCodeAt(i)
    h = Math.imul(h, 0x01000193)
  }
  return 'h' + (h >>> 0).toString(36)
}

// ---------------------------------------------------------------------------
// text RGA internals
// ---------------------------------------------------------------------------

/** html → tokens: tags and entities are atomic, everything else per-char */
export function tokenize(html: string): string[] {
  const out: string[] = []
  let i = 0
  while (i < html.length) {
    const c = html[i]
    if (c === '<') {
      const j = html.indexOf('>', i)
      if (j >= 0) {
        out.push(html.slice(i, j + 1))
        i = j + 1
        continue
      }
    }
    if (c === '&') {
      const j = html.indexOf(';', i)
      if (j >= 0 && j - i <= 10) {
        out.push(html.slice(i, j + 1))
        i = j + 1
        continue
      }
    }
    out.push(c)
    i++
  }
  return out
}

function seedTokens(sd: Reg, html: string): TxtTok[] {
  return tokenize(html).map((t, i) => ({ id: `s${sd[0]}.${sd[1]}.${i}`, t }))
}

export function materialize(st: TxtState): string {
  let out = ''
  for (const t of st.toks) if (!t.d) out += t.t
  return out
}

/** (lamport, actor, i) comparison for token ids `<l>.<a>.<i>` / `s<l>.<a>.<i>` */
function tokCmp(x: string, y: string): number {
  const px = x.split('.')
  const py = y.split('.')
  const lx = parseInt(px[0].replace(/^s/, ''), 10)
  const ly = parseInt(py[0].replace(/^s/, ''), 10)
  if (lx !== ly) return lx - ly
  if (px[1] !== py[1]) return px[1] < py[1] ? -1 : 1
  return parseInt(px[2], 10) - parseInt(py[2], 10)
}

function applyTxtToState(st: TxtState, op: TxtOp): boolean {
  let changed = false
  if (op.del) {
    const dead = new Set(op.del)
    for (const t of st.toks)
      if (dead.has(t.id)) {
        if (!t.d) changed = true
        t.d = 1
        dead.delete(t.id)
      }
    // deletes can overtake their token's insert (cross-actor) — park them
    if (dead.size) {
      const before = (st.pd ?? []).length
      st.pd = [...new Set([...(st.pd ?? []), ...dead])].sort()
      if (st.pd.length !== before) changed = true
    }
  }
  for (const grp of op.ins ?? []) {
    let idx = 0
    if (grp.at !== '^') {
      idx = st.toks.findIndex((t) => t.id === grp.at) + 1
      if (idx === 0) continue // anchor unknown (older-seed remnant) — drop
    }
    if (st.toks.some((t) => t.id === `${op.l}.${op.a}.0`)) continue // replayed
    changed = true
    const newId = `${op.l}.${op.a}.0`
    // RGA skip rule: pass over tokens with a greater id (concurrent inserts
    // at one anchor order newest-first; causality guarantees descendants
    // carry higher lamports than their anchors)
    while (idx < st.toks.length && tokCmp(st.toks[idx].id, newId) > 0) idx++
    const toks: TxtTok[] = grp.toks.map((t, i) => ({ id: `${op.l}.${op.a}.${i}`, t }))
    // NOT splice(idx, 0, ...toks): tokenize is per-character, so a large text
    // element is hundreds of thousands of tokens, and spreading them as call
    // ARGUMENTS overflows the stack (~200KB of text was enough). That threw
    // inside diff(), so session.flush() failed and NOTHING synced for the rest
    // of the session — not just the oversized element. Splice in place without
    // a spread instead; cost is one array copy.
    st.toks = idx === st.toks.length
      ? st.toks.concat(toks)
      : st.toks.slice(0, idx).concat(toks, st.toks.slice(idx))
    if (st.pd?.length) {
      const pend = new Set(st.pd)
      for (const t of toks)
        if (pend.has(t.id)) {
          t.d = 1
          pend.delete(t.id)
        }
      if (pend.size) st.pd = [...pend].sort()
      else delete st.pd
    }
  }
  return changed
}

/** same-seed token union for snapshot merges */
function mergeToks(dst: TxtState, src: TxtState) {
  const have = new Map(dst.toks.map((t, i) => [t.id, i]))
  for (let i = 0; i < src.toks.length; i++) {
    const t = src.toks[i]
    const at = have.get(t.id)
    if (at !== undefined) {
      if (t.d) dst.toks[at].d = 1
      continue
    }
    // insert after the nearest preceding src token we do have (RGA order)
    let anchorIdx = -1
    for (let k = i - 1; k >= 0; k--) {
      const a = have.get(src.toks[k].id)
      if (a !== undefined) {
        anchorIdx = a
        break
      }
    }
    let idx = anchorIdx + 1
    while (idx < dst.toks.length && tokCmp(dst.toks[idx].id, t.id) > 0) idx++
    dst.toks.splice(idx, 0, { ...t })
    have.clear()
    dst.toks.forEach((x, j) => have.set(x.id, j))
  }
  // union pending deletes, resolving any that now have their token
  const pend = new Set([...(dst.pd ?? []), ...(src.pd ?? [])])
  if (pend.size) {
    for (const t of dst.toks)
      if (pend.has(t.id)) {
        t.d = 1
        pend.delete(t.id)
      }
  }
  if (pend.size) dst.pd = [...pend].sort()
  else delete dst.pd
}

// ---------------------------------------------------------------------------
// helpers
// ---------------------------------------------------------------------------

/** indices of a longest strictly-increasing subsequence */
function longestIncreasing(keys: string[]): number[] {
  const tails: number[] = []
  const prev = new Array<number>(keys.length).fill(-1)
  for (let i = 0; i < keys.length; i++) {
    let lo = 0
    let hi = tails.length
    while (lo < hi) {
      const mid = (lo + hi) >> 1
      if (keys[tails[mid]] < keys[i]) lo = mid + 1
      else hi = mid
    }
    if (lo > 0) prev[i] = tails[lo - 1]
    tails[lo] = i
  }
  const out: number[] = []
  let k = tails.length ? tails[tails.length - 1] : -1
  while (k >= 0) {
    out.push(k)
    k = prev[k]
  }
  return out.reverse()
}