codec.ts · Source

codec.tspackages/collaboration/src/codec.tsraw ← src45,998 B← Back to the app
1/**
2 * @factory/collaboration — the block tree ↔ Yjs doc codec (TASK-0092 R1).
3 *
4 * Doc shape (frontend-architecture §3.3 + realtime-architecture §4):
5 * one `Y.XmlElement` per block (type `factoryBlock`, from `mapping.ts`),
6 * attrs `{id, position, type}`, block `properties` as JSON-encoded element
7 * attrs (`p.{key}` — atomic LWW metadata, not CRDT), and the
8 * CRDT-mergeable text content as **named `Y.XmlText` children**
9 * (`name` attr = the slot key: text / language / caption / title) — plus
10 * a named `factoryRows` child element for tables (`factoryRow` children,
11 * each holding `name="cell"` `Y.XmlText` cells — row/cell text merges,
12 * structural row moves are CRDT). The block tree lives in a top-level
13 * `Y.XmlFragment` (`blocks`); a `yMeta` `Y.Map` carries
14 * `{pageId, schemaVersion}`.
15 *
16 * Yjs model note (recorded): `Y.XmlElement` has no named-slot API in yjs
17 * 13.6 (`getText`/`getArray`/`getMap` do not exist) — `Y.Map`/`Y.Array`
18 * also carry no attributes, so children are located by a `name` attribute
19 * ({@link namedChild}). Text slots are `Y.XmlText` (character-level CRDT
20 * merge); the rows/properties containers are `Y.XmlElement` (attrs are
21 * supported, CRDT-merged).
22 *
23 * The load-bearing rule (recorded in the task sheet): **Yjs array order and
24 * `position` order must never diverge** — a move rewrites the `position`
25 * attr AND the fragment order in one transaction. `blocksToYDoc` builds the
26 * fragment position-ordered; `yDocToBlockList` reads fragment order (the
27 * doc's own order is the truth at decode time) and stamps `position` from
28 * attrs. The round-trip property test asserts both.
29 *
30 * Persistence (`yDocToBlocks(doc, lastPersisted)`): walk the fragment,
31 * diff against `lastPersistedBlocks` by id + content/properties/position,
32 * emit the **minimal** `BlockOperation[]` set in the wire order
33 * (deletes → updates → moves → inserts — the same contract as
34 * `@factory/editor`'s `diffBlocks`, which this function mirrors structurally
35 * so the two codecs agree — the two-codecs-agree property test).
36 *
37 * Pure + Node-testable: no DOM, no tiptap. The y-prosemirror bridge
38 * (ProseMirror ↔ this doc) lives in the canvas (`apps/web`), which
39 * implements `YjsDocBinding`.
40 */
41 
42import { comparePositions, type Position } from "@factory/shared/positions";
43import type {
44  BlockContentByType,
45  BlockOperation,
46  BlockPatch,
47  BlockType,
48} from "@factory/shared/dto";
49import { betweenPosition, minPosition } from "@factory/shared/positions";
50import * as Y from "yjs";
51 
52import { mappingForType } from "./mapping.js";
53 
54/** The codec's schema version (bumped when the doc shape changes). */
55export const Y_SCHEMA_VERSION = 1;
56 
57/** The top-level fragment name. */
58export const FRAGMENT_NAME = "blocks";
59 
60/** The meta map name (carries `{pageId, schemaVersion}`). */
61export const META_NAME = "yMeta";
62 
63/** Y.XmlElement type name for the table rows container. */
64const ROWS_ELEMENT_TYPE = "factoryRows";
65 
66/** Y.XmlElement type name for one table row. */
67const ROW_ELEMENT_TYPE = "factoryRow";
68 
69/** The `name` attr value of the rows container child. */
70const ROWS_SLOT = "rows";
71 
72/** The `name` attr value of a row child. */
73const ROW_SLOT = "row";
74 
75/** The `name` attr value of a cell text child. */
76const CELL_SLOT = "cell";
77 
78/** Prefix of the element attrs that carry block properties. */
79const PROP_ATTR_PREFIX = "p.";
80 
81/** Block-shaped record (structural — the editor package's `BlockDto`). */
82export interface BlockLike {
83  id: string;
84  type: BlockType;
85  content: BlockContentByType[BlockType];
86  parentId: string | null;
87  position: Position;
88  /** Block properties (custom attributes) — wholesale-replaced on update. */
89  properties?: Record<string, unknown>;
90}
91 
92export interface BlocksToYDocOptions {
93  readonly pageId?: string;
94}
95 
96function newFragment(doc: Y.Doc): Y.XmlFragment {
97  return doc.getXmlFragment(FRAGMENT_NAME);
98}
99 
100function setMeta(doc: Y.Doc, pageId?: string): void {
101  const meta = doc.getMap(META_NAME);
102  meta.set("schemaVersion", Y_SCHEMA_VERSION);
103  if (pageId !== undefined) meta.set("pageId", pageId);
104}
105 
106function byPosition(a: { position: Position }, b: { position: Position }): number {
107  return comparePositions(a.position, b.position);
108}
109 
110/**
111 * Set a node attr, widening past yjs 13.6's d.ts (`setAttribute` is typed
112 * against `KV = Record<string, string>`), but the runtime — and y-prosemirror,
113 * which stores ProseMirror attrs the same way — keeps `string | number |
114 * boolean | null` values natively. The value must NOT be stringified here:
115 * the round-trip read returns the stored type, and content equality (`5` vs
116 * `"5"`) depends on it. `null` deletes the attr (yjs runtime behavior).
117 */
118function setAttr(
119  el: Y.XmlElement,
120  key: string,
121  value: string | number | boolean | null,
122): void {
123  (el as unknown as { setAttribute(k: string, v: unknown): void }).setAttribute(key, value);
124}
125 
126/**
127 * The named child of an element (children are located by their `name`
128 * attr — see the module doc: yjs 13.6 `Y.XmlElement` has no named-slot
129 * API). Returns null when absent.
130 */
131export function namedChild(el: Y.XmlElement, name: string): Y.XmlElement | Y.XmlText | null {
132  for (const child of el.toArray()) {
133    if (child instanceof Y.XmlText || child instanceof Y.XmlElement) {
134      if (child.getAttribute("name") === name) return child;
135    }
136  }
137  return null;
138}
139 
140/** The named `Y.XmlText` slot (created on first use). */
141function textSlot(el: Y.XmlElement, key: string): Y.XmlText {
142  const existing = namedChild(el, key);
143  if (existing instanceof Y.XmlText) return existing;
144  if (existing instanceof Y.XmlElement) {
145    // A slot changed shape (should not happen within one doc lifetime);
146    // remove the stale child and create the text slot.
147    const idx = (el.toArray() as (Y.XmlElement | Y.XmlText)[]).indexOf(existing);
148    if (idx >= 0) el.delete(idx, 1);
149  }
150  const text = new Y.XmlText("");
151  text.setAttribute("name", key);
152  el.insert(0, [text]);
153  return text;
154}
155 
156/** Set a text slot to exactly `value` with minimal CRDT edits. */
157function setTextSlot(el: Y.XmlElement, key: string, value: string): void {
158  const text = textSlot(el, key);
159  const current = text.toString();
160  if (current.length > value.length) text.delete(value.length, current.length - value.length);
161  else if (value.length > current.length) text.insert(current.length, value.slice(current.length));
162}
163 
164/** The named rows container (created on first use). */
165function rowsSlot(el: Y.XmlElement): Y.XmlElement {
166  const existing = namedChild(el, ROWS_SLOT);
167  if (existing instanceof Y.XmlElement) return existing;
168  if (existing instanceof Y.XmlText) {
169    const idx = (el.toArray() as (Y.XmlElement | Y.XmlText)[]).indexOf(existing);
170    if (idx >= 0) el.delete(idx, 1);
171  }
172  const rows = new Y.XmlElement(ROWS_ELEMENT_TYPE);
173  rows.setAttribute("name", ROWS_SLOT);
174  el.insert(0, [rows]);
175  return rows;
176}
177 
178/**
179 * Reconcile the rows container with `targetRows` using minimal CRDT
180 * edits (row add/remove/resize + per-cell text edits).
181 */
182function setRows(el: Y.XmlElement, targetRows: readonly (string | undefined)[]): void {
183  const rows = rowsSlot(el);
184  const currentRows = rows.toArray() as Y.XmlElement[];
185  if (currentRows.length > targetRows.length) {
186    rows.delete(targetRows.length, currentRows.length - targetRows.length);
187  }
188  for (let r = 0; r < targetRows.length; r += 1) {
189    const targetRow = targetRows[r] ?? [];
190    let row = (rows.toArray() as Y.XmlElement[])[r];
191    if (row === undefined) {
192      row = new Y.XmlElement(ROW_ELEMENT_TYPE);
193      row.setAttribute("name", ROW_SLOT);
194      rows.insert(r, [row]);
195    }
196    const cells = row.toArray() as Y.XmlText[];
197    if (cells.length > targetRow.length) {
198      row.delete(targetRow.length, cells.length - targetRow.length);
199    }
200    for (let c = 0; c < targetRow.length; c += 1) {
201      const value = String(targetRow[c] ?? "");
202      let cell = (row.toArray() as Y.XmlText[])[c];
203      if (cell === undefined || !(cell instanceof Y.XmlText)) {
204        cell = new Y.XmlText("");
205        cell.setAttribute("name", CELL_SLOT);
206        row.insert(c, [cell]);
207      }
208      const current = cell.toString();
209      if (current.length > value.length) cell.delete(value.length, current.length - value.length);
210      else if (value.length > current.length) cell.insert(current.length, value.slice(current.length));
211    }
212  }
213}
214 
215function setSlot(
216  el: Y.XmlElement,
217  key: string,
218  value: unknown,
219): void {
220  if (typeof value === "string") {
221    setTextSlot(el, key, value);
222  } else if (Array.isArray(value)) {
223    setRows(el, value as readonly (string | undefined)[]);
224  } else if (value !== undefined) {
225    setAttr(el, key, value as string | number | boolean | null);
226  }
227}
228 
229/** Build one `factoryBlock` Y.XmlElement from a block (content per mapping). */
230export function blockToYElement(block: BlockLike): Y.XmlElement {
231  const mapping = mappingForType(block.type);
232  const el = new Y.XmlElement(mapping.yNodeType);
233  el.setAttribute("id", block.id);
234  el.setAttribute("position", block.position);
235  el.setAttribute("type", block.type);
236 
237  const content = block.content as Record<string, unknown>;
238  for (const key of mapping.textSlots) {
239    if (content[key] !== undefined) setSlot(el, key, content[key]);
240  }
241  if (mapping.hasRows && content.rows !== undefined) {
242    setSlot(el, "rows", content.rows as unknown[]);
243  }
244  for (const key of mapping.attrKeys) {
245    if (content[key] !== undefined) {
246      setAttr(el, key, content[key] as string | number | boolean | null);
247    }
248  }
249  if (block.properties !== undefined) {
250    for (const [k, v] of Object.entries(block.properties)) {
251      if (v !== undefined) el.setAttribute(PROP_ATTR_PREFIX + k, JSON.stringify(v));
252    }
253  }
254  return el;
255}
256 
257/**
258 * Build the Y.Doc from a flat block forest (the hydrator's entry).
259 * Siblings are appended in `position` order (children nested under their
260 * parent's element); throws on duplicate ids or a missing parent.
261 */
262export function blocksToYDoc(
263  blocks: readonly BlockLike[],
264  opts: BlocksToYDocOptions = {},
265): Y.Doc {
266  const doc = new Y.Doc();
267  setMeta(doc, opts.pageId);
268 
269  const seen = new Set<string>();
270  for (const block of blocks) {
271    if (seen.has(block.id)) {
272      throw new Error(`blocksToYDoc: duplicate block id "${block.id}"`);
273    }
274    seen.add(block.id);
275  }
276  const childrenByParent = new Map<string | null, BlockLike[]>();
277  for (const block of blocks) {
278    if (block.parentId !== null && !seen.has(block.parentId)) {
279      throw new Error(
280        `blocksToYDoc: block "${block.id}" references missing parent "${block.parentId}"`,
281      );
282    }
283    const list = childrenByParent.get(block.parentId) ?? [];
284    list.push(block);
285    childrenByParent.set(block.parentId, list);
286  }
287 
288  const fragment = newFragment(doc);
289  // Build recursively: a block's element has its children NESTED (inserted
290  // into the parent element), so the fragment/element tree matches the
291  // parentId forest. Children are created fresh (not yet integrated), so
292  // inserting them into the (also un-integrated) parent is safe — the
293  // prelim content flushes on first integration.
294  const childrenByParentId = (id: string): BlockLike[] =>
295    (childrenByParent.get(id) ?? []).slice().sort(byPosition);
296  const build = (block: BlockLike): Y.XmlElement => buildSubtree(block, childrenByParentId);
297  for (const root of (childrenByParent.get(null) ?? []).slice().sort(byPosition)) {
298    fragment.insert(fragment.length, [build(root)]);
299  }
300  return doc;
301}
302 
303/** Build a fresh (never-integrated) `factoryBlock` element for `block` with
304 *  its children (looked up by id, position-sorted) NESTED underneath. Shared
305 *  by the hydrator ({@link blocksToYDoc}) and the move applier (a moved
306 *  subtree is deleted and re-built this way — re-inserting an ALREADY
307 *  integrated Y.XmlElement crashes yjs 13.6, and `clone(true)` silently
308 *  drops the XmlText slots' `name` attribute because `YXmlText.clone()`
309 *  re-creates the text from its delta without copying attrs). */
310function buildSubtree(
311  block: BlockLike,
312  childrenOf: (id: string) => BlockLike[],
313): Y.XmlElement {
314  const el = blockToYElement(block);
315  for (const child of childrenOf(block.id)) {
316    el.insert(el.length, [buildSubtree(child, childrenOf)]);
317  }
318  return el;
319}
320 
321function textOf(el: Y.XmlElement, key: string): string | null {
322  const slot = namedChild(el, key);
323  return slot instanceof Y.XmlText ? slot.toString() : null;
324}
325 
326function rowsOf(el: Y.XmlElement): string[][] | null {
327  const rows = namedChild(el, ROWS_SLOT);
328  if (!(rows instanceof Y.XmlElement)) return null;
329  return (rows.toArray() as Y.XmlElement[]).map((row) =>
330    (row.toArray() as (Y.XmlText | Y.XmlElement)[]).map((cell) =>
331      cell instanceof Y.XmlText ? cell.toString() : "",
332    ),
333  );
334}
335 
336function propertiesOf(el: Y.XmlElement): Record<string, unknown> | undefined {
337  const properties: Record<string, unknown> = {};
338  let has = false;
339  const attrs = el.getAttributes() as Record<string, unknown>;
340  for (const [k, v] of Object.entries(attrs)) {
341    if (k.startsWith(PROP_ATTR_PREFIX) && typeof v === "string") {
342      properties[k.slice(PROP_ATTR_PREFIX.length)] = JSON.parse(v);
343      has = true;
344    }
345  }
346  return has ? properties : undefined;
347}
348 
349/** Extract one block (without children) from a `factoryBlock` element. */
350export function yElementToBlock(el: Y.XmlElement, parentId: string | null): BlockLike {
351  const type = el.getAttribute("type") as BlockType;
352  const mapping = mappingForType(String(type));
353  const content: Record<string, unknown> = {};
354  for (const key of mapping.textSlots) {
355    const value = textOf(el, key);
356    if (value !== null) content[key] = value;
357  }
358  if (mapping.hasRows) {
359    const rows = rowsOf(el);
360    if (rows !== null) content.rows = rows;
361  }
362  for (const key of mapping.attrKeys) {
363    const value = el.getAttribute(key);
364    if (value !== null && value !== undefined) content[key] = value;
365  }
366  const block: BlockLike = {
367    id: String(el.getAttribute("id") ?? ""),
368    type,
369    content: content as BlockContentByType[BlockType],
370    parentId,
371    position: String(el.getAttribute("position") ?? ""),
372  };
373  const properties = propertiesOf(el);
374  if (properties !== undefined) block.properties = properties;
375  return block;
376}
377 
378/**
379 * The block children of a parent (a block is recognized by its `id` attr —
380 * the slot children, named text/rows cells, carry no `id` and must never be
381 * mistaken for blocks by the walkers). `getAttribute` returns `undefined`
382 * for absent attrs (yjs 13.6 — not null), so the check is loose.
383 */
384function blockChildren(parent: YParent): Y.XmlElement[] {
385  return (parent.toArray() as (Y.XmlElement | Y.XmlText)[]).filter(
386    (c): c is Y.XmlElement => c instanceof Y.XmlElement && c.getAttribute("id") != null,
387  );
388}
389 
390/** Recursively capture the block subtree rooted at `el` (it and its block
391 *  descendants) as plain {@link BlockLike} data (DFS, children right after
392 *  their parent; each block's `parentId` is its in-tree parent). The inverse
393 *  of {@link buildSubtree}: a moved subtree is captured with this, the
394 *  original is deleted, and the fresh rebuild goes through the encoder's own
395 *  builder — yjs 13.6 crashes when an ALREADY-integrated `Y.XmlElement` is
396 *  re-inserted, and `clone(true)` silently drops the XmlText slots' `name`
397 *  attribute (`YXmlText.clone` rebuilds from the delta without attrs). */
398function captureSubtree(el: Y.XmlElement, parentId: string | null): BlockLike[] {
399  const out: BlockLike[] = [yElementToBlock(el, parentId)];
400  for (const child of blockChildren(el)) {
401    out.push(...captureSubtree(child, String(el.getAttribute("id"))));
402  }
403  return out;
404}
405 
406/**
407 * Walk the fragment to a flat block list — DFS, children immediately after
408 * their parent, fragment order is the sibling order (the decode-time truth;
409 * the encoder always wrote it position-ordered).
410 */
411export function yDocToBlockList(doc: Y.Doc): BlockLike[] {
412  const fragment = newFragment(doc);
413  const out: BlockLike[] = [];
414  const walk = (els: Y.XmlElement[], parentId: string | null): void => {
415    for (const el of els) {
416      out.push(yElementToBlock(el, parentId));
417      walk(blockChildren(el), el.getAttribute("id") as string);
418    }
419  };
420  walk(blockChildren(fragment), null);
421  return out;
422}
423 
424/**
425 * The persister's entry (TASK-0092 R1): walk the fragment position-ordered,
426 * diff against `lastPersistedBlocks` (by id + content/properties/position),
427 * emit the **minimal** `BlockOperation[]` set (wire order: deletes →
428 * updates → moves → inserts). Returns `[]` when the doc equals the
429 * baseline (the idempotency assert: the post-rebase flush is a no-op).
430 */
431export function yDocToBlocks(
432  doc: Y.Doc,
433  lastPersisted: readonly BlockLike[],
434): BlockOperation[] {
435  const current = yDocToBlockList(doc);
436  return diffBlockSets(lastPersisted, current);
437}
438 
439/** Deep, deterministic equality for plain-JSON values. */
440export function jsonEqual(a: unknown, b: unknown): boolean {
441  if (a === b) return true;
442  if (typeof a !== typeof b || a === null || b === null || typeof a !== "object") {
443    return false;
444  }
445  const ka = Object.keys(a as Record<string, unknown>).sort();
446  const kb = Object.keys(b as Record<string, unknown>).sort();
447  if (ka.length !== kb.length || ka.some((k, i) => k !== kb[i])) return false;
448  return ka.every((k) => jsonEqual((a as Record<string, unknown>)[k], (b as Record<string, unknown>)[k]));
449}
450 
451export interface BlockSetDiff {
452  readonly deletes: readonly string[];
453  readonly updates: readonly {
454    readonly id: string;
455    readonly patch: {
456      content?: Record<string, unknown>;
457      properties?: Record<string, unknown>;
458    };
459  }[];
460  readonly moves: readonly { readonly id: string; readonly before?: string; readonly after?: string }[];
461  readonly inserts: readonly BlockLike[];
462}
463 
464/**
465 * Minimal structural diff between two same-page block sets (the shared
466 * logic behind {@link yDocToBlocks}; mirrors `@factory/editor`'s
467 * `diffBlocks` so both codecs agree — the two-codecs-agree property test).
468 *
469 * - A `move`'s `before`/`after` are sibling ids in the *destination* order
470 *   (at most one; a cross-parent move with no anchors still emits — the
471 *   server resolves end-of-list; wire gap: `moveOp` has no `parentId`,
472 *   recorded in the editor package).
473 * - Send order: deletes → updates → moves → inserts.
474 */
475export function diffBlockSets(
476  previous: readonly BlockLike[],
477  next: readonly BlockLike[],
478): BlockOperation[] {
479  const prevById = new Map<string, BlockLike>();
480  for (const b of previous) prevById.set(b.id, b);
481  const nextById = new Map<string, BlockLike>();
482  for (const b of next) nextById.set(b.id, b);
483 
484  const deletes = previous.filter((b) => !nextById.has(b.id)).map((b) => b.id);
485  const inserts = next.filter((b) => !prevById.has(b.id));
486 
487  const byParent = new Map<string | null, BlockLike[]>();
488  for (const b of next) {
489    const list = byParent.get(b.parentId) ?? [];
490    list.push(b);
491    byParent.set(b.parentId, list);
492  }
493  for (const list of byParent.values()) list.sort(byPosition);
494 
495  const updates: {
496    id: string;
497    patch: { content?: Record<string, unknown>; properties?: Record<string, unknown> };
498  }[] = [];
499  const moves: { id: string; before?: string; after?: string }[] = [];
500  for (const [id, nb] of nextById) {
501    const pb = prevById.get(id);
502    if (pb === undefined) continue;
503    const contentChanged = !jsonEqual(pb.content, nb.content);
504    const propertiesChanged =
505      (pb.properties === undefined) !== (nb.properties === undefined) ||
506      (pb.properties !== undefined &&
507        nb.properties !== undefined &&
508        !jsonEqual(pb.properties, nb.properties));
509    if (contentChanged || propertiesChanged) {
510      // A properties-ONLY change still emits an update (the persister's
511      // flush must not drop a color/checkbox toggle that carries no text
512      // or structural edit).
513      const patch: { content?: Record<string, unknown>; properties?: Record<string, unknown> } = {};
514      if (contentChanged) patch.content = nb.content as Record<string, unknown>;
515      if (propertiesChanged && nb.properties !== undefined) patch.properties = nb.properties;
516      updates.push({ id, patch });
517    }
518    if (pb.position !== nb.position || pb.parentId !== nb.parentId) {
519      const siblings = byParent.get(nb.parentId) ?? [];
520      const idx = siblings.findIndex((s) => s.id === id);
521      const before = idx > 0 ? siblings[idx - 1]?.id : undefined;
522      const after = idx >= 0 && idx < siblings.length - 1 ? siblings[idx + 1]?.id : undefined;
523      const move: { id: string; before?: string; after?: string } = { id };
524      if (before !== undefined) move.before = before;
525      if (after !== undefined) move.after = after;
526      if (before !== undefined || after !== undefined || pb.parentId !== nb.parentId) {
527        moves.push(move);
528      }
529    }
530  }
531 
532  return toOperations(deletes, updates, moves, inserts);
533}
534 
535/** Assemble a diff into wire `BlockOperation`s (send order). */
536export function toOperations(
537  deletes: readonly string[],
538  updates: BlockSetDiff["updates"],
539  moves: BlockSetDiff["moves"],
540  inserts: readonly BlockLike[],
541): BlockOperation[] {
542  const ops: BlockOperation[] = [];
543  for (const id of deletes) ops.push({ op: "delete", id });
544  for (const u of updates) ops.push({ op: "update", id: u.id, patch: u.patch });
545  for (const m of moves) {
546    const move: { op: "move"; id: string; before?: string; after?: string } = { op: "move", id: m.id };
547    // Wire contract: at most one of before/after (the shared
548    // blockOperationSchema's superRefine). Prefer the `before` anchor;
549    // fall back to `after` when the block leads its destination siblings.
550    if (m.before !== undefined) move.before = m.before;
551    else if (m.after !== undefined) move.after = m.after;
552    ops.push(move);
553  }
554  for (const b of inserts) {
555    const block: {
556      id?: string;
557      type: BlockType;
558      content: Record<string, unknown>;
559      properties?: Record<string, unknown>;
560      parentId?: string;
561      position: Position;
562    } = {
563      type: b.type,
564      content: b.content as Record<string, unknown>,
565      position: b.position,
566    };
567    // Preserve the block's id when it has one (the wire insert accepts an
568    // explicit id; the CRDT applier honors it — required for the server's
569    // flush-rebase, which round-trips diffBlockSets ops back into the doc
570    // and must land the block at its REAL id, not a server-minted one).
571    if (b.id !== undefined && b.id !== "") block.id = b.id;
572    if (b.properties !== undefined) block.properties = b.properties;
573    if (b.parentId !== null) block.parentId = b.parentId;
574    ops.push({ op: "insert", block });
575  }
576  return ops;
577}
578 
579// --- plain-blocks op applier (the non-CRDT path of the two-codecs test) -------
580 
581/** "After everything" sentinel: the max-length position (64 z's — the
582 *  alphabet's top char) sorts above every valid position (a position
583 *  equal to it is never assigned; one greater would exceed MAX_LEN). */
584const END_SENTINEL = "z".repeat(64);
585// The smallest valid position ("0"). The virtual lower bound when a block
586// lands at the FRONT of its destination list (the anchor is the list's first
587// sibling, so there is no previous-sibling position to use as the lower
588// bound). The empty string is NOT a valid position (isValidPosition rejects
589// length 0), so it must never be passed to betweenPosition.
590const START_SENTINEL = minPosition();
591 
592/**
593 * The canonical position for a block landing at the wire anchors
594 * (at most one, the wire contract), given the destination siblings
595 * ALREADY EXCLUDING the landing block (position-sorted). Anchor
596 * semantics (the diff's contract, pinned by the editor codec tests):
597 *   - `before: X` — X is the landing block's PREDECESSOR ("X is before
598 *     me") → land AFTER X: `between(X, X's next sibling)`.
599 *   - `after: X`  — X is the landing block's SUCCESSOR ("X is after me")
600 *     → land BEFORE X: `between(X's previous sibling, X)`.
601 * Shared by both appliers so the plain and Yjs results agree byte-for-byte
602 * (the two-codecs test).
603 */
604export function positionForAnchors(
605  siblings: readonly { id: string; position: Position }[],
606  before: string | undefined,
607  after: string | undefined,
608): Position {
609  if (before !== undefined) {
610    const idx = siblings.findIndex((s) => s.id === before);
611    if (idx >= 0) {
612      const anchor = siblings[idx];
613      const next = siblings[idx + 1];
614      if (anchor !== undefined) {
615        return betweenPosition(anchor.position, next !== undefined ? next.position : END_SENTINEL);
616      }
617    }
618  }
619  if (after !== undefined) {
620    const idx = siblings.findIndex((s) => s.id === after);
621    if (idx >= 0) {
622      const anchor = siblings[idx];
623      const prev = siblings[idx - 1];
624      if (anchor !== undefined) {
625        return betweenPosition(prev !== undefined ? prev.position : START_SENTINEL, anchor.position);
626      }
627    }
628  }
629  const last = siblings[siblings.length - 1];
630  return last !== undefined ? betweenPosition(last.position, END_SENTINEL) : betweenPosition(START_SENTINEL, END_SENTINEL);
631}
632 
633/** The array index a block lands at for `before`/`after` (siblings are
634 *  position-sorted — findIndex is valid). Same semantics as
635 * {@link positionForAnchors}: `before` = predecessor (land at idx+1),
636 *  `after` = successor (land at idx). */
637export function indexForAnchors<T extends { id: string }>(
638  siblings: readonly T[],
639  before: string | undefined,
640  after: string | undefined,
641): number {
642  if (before !== undefined) {
643    const idx = siblings.findIndex((s) => s.id === before);
644    return idx >= 0 ? idx + 1 : siblings.length;
645  }
646  if (after !== undefined) {
647    const idx = siblings.findIndex((s) => s.id === after);
648    return idx >= 0 ? idx : siblings.length;
649  }
650  return siblings.length;
651}
652 
653/**
654 * Apply wire block operations to a plain block set (pure — the non-CRDT
655 * half of the two-codecs-agree property test; the REST batch path applies
656 * the same ops server-side). Ops must arrive in wire order (deletes →
657 * updates → moves → inserts). A `move`'s destination is the anchor's
658 * parent (the wire `move` has no `parentId` — recorded gap); cross-page
659 * moves (`toPageId`) are out of scope for the single-page test (the ops
660 * never carry one — recorded).
661 */
662export function applyBlockOperations(
663  blocks: readonly BlockLike[],
664  operations: readonly BlockOperation[],
665): BlockLike[] {
666  let current: BlockLike[] = blocks.map((b) => ({ ...b }));
667  for (const op of operations) {
668    current = applyOne(current, op);
669  }
670  // Canonical order (parents before children, siblings by position) —
671  // the same order yDocToBlockList emits (the two-appliers test).
672  return canonicalOrder(current);
673}
674 
675function applyOne(current: BlockLike[], op: BlockOperation): BlockLike[] {
676  switch (op.op) {
677    case "delete": {
678      return current.filter((b) => b.id !== op.id);
679    }
680    case "update": {
681      return current.map((b) => {
682        if (b.id !== op.id) return b;
683        const next: BlockLike = { ...b };
684        if (op.patch.content !== undefined) {
685          next.content = op.patch.content as BlockContentByType[BlockType];
686        }
687        if (op.patch.properties !== undefined) next.properties = op.patch.properties;
688        if (op.patch.position !== undefined) next.position = op.patch.position;
689        return next;
690      });
691    }
692    case "move": {
693      const moved = current.find((b) => b.id === op.id);
694      if (moved === undefined || op.toPageId !== undefined) return current;
695      const rest = current.filter((b) => b.id !== op.id);
696      const destParentId = resolveDestParentId(current, moved.parentId, op.before, op.after);
697      return placeBlock(rest, moved, destParentId, op.before, op.after);
698    }
699    case "insert": {
700      // `position` is optional on the wire insert; the landing position is
701      // re-derived from the anchors / payload in `placeBlock`, so a blank
702      // placeholder is safe (it is never observed).
703      const block: BlockLike = {
704        id: op.block.id ?? `blk_${Math.floor(Math.random() * 1e9).toString(16)}`,
705        type: op.block.type,
706        content: op.block.content as BlockContentByType[BlockType],
707        parentId: op.block.parentId ?? null,
708        position: op.block.position ?? "",
709        ...(op.block.properties !== undefined ? { properties: { ...op.block.properties } } : {}),
710      };
711      const destParentId = resolveDestParentId(current, block.parentId, op.before, op.after);
712      return placeBlock(current, block, destParentId, op.before, op.after);
713    }
714  }
715}
716 
717/** The destination parent id, mirroring the Yjs applier exactly: the
718 *  anchor's parent wins (the wire `move` has no `parentId` — the anchor IS
719 *  the destination; a cross-parent move is expressible only via its
720 *  anchors). With no anchor: a move keeps its current parent (the recorded
721 *  wire gap — a move into an empty new parent is unanchorable), an insert
722 *  keeps its payload parent (root when null — the Yjs applier's root
723 *  fragment is the mirror). */
724function resolveDestParentId(
725  blocks: readonly BlockLike[],
726  explicitParentId: string | null,
727  before: string | undefined,
728  after: string | undefined,
729): string | null {
730  const anchorId = before ?? after;
731  if (anchorId !== undefined) {
732    const anchor = blocks.find((b) => b.id === anchorId);
733    if (anchor !== undefined) return anchor.parentId;
734  }
735  return explicitParentId;
736}
737 
738/** Rebuild the flat list in CANONICAL order (parents before children,
739 *  siblings by position) — the same order `yDocToBlockList` emits, so
740 *  plain-vs-Yjs comparison is position-independent. */
741function canonicalOrder(blocks: readonly BlockLike[]): BlockLike[] {
742  const ids = new Set(blocks.map((b) => b.id));
743  const byParent = new Map<string | null, BlockLike[]>();
744  for (const b of blocks) {
745    const list = byParent.get(b.parentId) ?? [];
746    list.push(b);
747    byParent.set(b.parentId, list);
748  }
749  for (const list of byParent.values()) list.sort(byPosition);
750  const out: BlockLike[] = [];
751  const walk = (parentId: string | null): void => {
752    for (const b of byParent.get(parentId) ?? []) {
753      out.push(b);
754      if (ids.has(b.id)) walk(b.id);
755    }
756  };
757  walk(null);
758  return out;
759}
760 
761/** Place a block: resolve the destination parent, compute the landing
762 *  position, rebuild canonical. Shared by move and insert (the Yjs
763 *  applier's twin — both re-derive the identical result). */
764function placeBlock(
765  current: readonly BlockLike[],
766  block: BlockLike,
767  destParentId: string | null,
768  before: string | undefined,
769  after: string | undefined,
770): BlockLike[] {
771  const landing = block.id;
772  const siblings = current
773    .filter((b) => b.parentId === destParentId && b.id !== landing)
774    .sort(byPosition);
775  const next: BlockLike = {
776    ...block,
777    parentId: destParentId,
778    position: landingPosition(siblings, block.position, before, after),
779  };
780  return canonicalOrder([...current, next]);
781}
782 
783// --- Yjs-doc op applier (the CRDT half of the two-codecs test) ----------------
784 
785type YParent = Y.XmlElement | Y.XmlFragment;
786 
787function elementOf(doc: Y.Doc, id: string): Y.XmlElement | undefined {
788  const walk = (els: Y.XmlElement[]): Y.XmlElement | undefined => {
789    for (const el of els) {
790      if (el.getAttribute("id") === id) return el;
791      const found = walk(blockChildren(el));
792      if (found !== undefined) return found;
793    }
794    return undefined;
795  };
796  return walk(blockChildren(newFragment(doc)));
797}
798 
799function parentOf(doc: Y.Doc, el: Y.XmlElement): YParent | null {
800  const walk = (els: Y.XmlElement[], parent: YParent | null): YParent | null => {
801    for (const candidate of els) {
802      if (candidate === el) return parent;
803      const found = walk(blockChildren(candidate), candidate);
804      if (found !== null) return found;
805    }
806    return null;
807  };
808  return walk(blockChildren(newFragment(doc)), newFragment(doc));
809}
810 
811function removeElement(parent: YParent, el: Y.XmlElement): void {
812  const idx = (parent.toArray() as Y.XmlElement[]).indexOf(el);
813  if (idx >= 0) parent.delete(idx, 1);
814}
815 
816/** The parent block id of a `YParent` (null for the root fragment). */
817function parentIdOf(doc: Y.Doc, parent: YParent): string | null {
818  if (parent === newFragment(doc)) return null;
819  return String((parent as Y.XmlElement).getAttribute("id") ?? "");
820}
821 
822/** The destination parent of a move/insert: the anchor's parent (the wire
823 *  `move` has no `parentId` — the anchor IS the destination; recorded wire
824 *  gap); `null` when no anchor resolves. */
825function anchorParent(doc: Y.Doc, before: string | undefined, after: string | undefined): YParent | null {
826  const anchorId = before ?? after;
827  if (anchorId === undefined) return null;
828  const anchor = elementOf(doc, anchorId);
829  return anchor !== undefined ? parentOf(doc, anchor) : null;
830}
831 
832/**
833 * The destination siblings (position-sorted, excluding the landing block)
834 * as plain `{id, position}` records — the shared input to
835 * {@link positionForAnchors} / {@link indexForAnchors}, so the Yjs and
836 * plain appliers compute identical positions (the two-codecs test).
837 */
838function siblingsOf(parent: YParent, excludeId: string): { id: string; position: Position }[] {
839  return blockChildren(parent)
840    .filter((e) => e.getAttribute("id") !== excludeId)
841    .map((e) => ({
842      id: String(e.getAttribute("id") ?? ""),
843      position: String(e.getAttribute("position") ?? ""),
844    }))
845    .sort(byPosition);
846}
847 
848/** Compute the landing position for a block (shared by move and insert;
849 *  `siblings` is the destination's current siblings, position-sorted,
850 *  EXCLUDING the landing block). Mirrors the Yjs applier exactly:
851 *   - an anchor resolves → the canonical anchor position (the diff
852 *     derived the same value from the same destination siblings);
853 *   - no anchor + a payload position (inserts) → the payload position
854 *     (the diff set it from the next order — exact);
855 *   - no anchor + no payload position (the wire `move` gap — a move into
856 *     an empty new parent is unanchorable; recorded) → append after the
857 *     destination's last sibling (`between(last, END)`, or the empty-doc
858 *     position when the destination is empty).
859 */
860function landingPosition(
861  siblings: readonly { id: string; position: Position }[],
862  payloadPosition: Position | undefined,
863  before: string | undefined,
864  after: string | undefined,
865): Position {
866  if (before !== undefined || after !== undefined) {
867    return positionForAnchors(siblings, before, after);
868  }
869  if (payloadPosition !== undefined && payloadPosition !== "") return payloadPosition;
870  const last = siblings[siblings.length - 1];
871  return last !== undefined ? betweenPosition(last.position, END_SENTINEL) : betweenPosition(START_SENTINEL, END_SENTINEL);
872}
873 
874/**
875 * Apply a block patch to an element (text slots → Y.Text edits, attr keys
876 *  → atomic attrs, properties → `p.*` JSON attrs, position → attr). The
877 *  patch's `content` is the block's FULL next content (the diff's
878 *  contract — the plain applier replaces `content` wholesale), so a key
879 *  ABSENT from the patch clears the slot (text → "", attr → deleted); a
880 *  key present sets it. This keeps the Y.Doc and the plain block set in
881 *  lockstep.
882 */
883function applyPatchToElement(el: Y.XmlElement, patch: BlockPatch): void {
884  if (patch.type !== undefined) el.setAttribute("type", patch.type);
885  const mapping = mappingForType(String(patch.type ?? el.getAttribute("type") ?? ""));
886  if (patch.content !== undefined) {
887    // WHOLESALE content replacement (mirrors the plain applier's
888    // `next.content = op.patch.content`). The diff emits the block's ENTIRE
889    // next content, never a character delta — raw Yjs text deltas ride the
890    // 0x01 binary channel, not these ops. So a slot's previous value is
891    // deleted before the new value is written: applying `"edited"` to a slot
892    // holding `"Ta"` must yield `"edited"`, not the incremental-edit
893    // `"Taited"`. All deletes run before any inserts (deleting one child
894    // does not shift the index of a sibling we address by reference).
895    const childArray = () => el.toArray() as (Y.XmlElement | Y.XmlText)[];
896    for (const key of mapping.textSlots) {
897      const slot = namedChild(el, key);
898      if (slot instanceof Y.XmlText) el.delete(childArray().indexOf(slot), 1);
899    }
900    const rowsEl = namedChild(el, ROWS_SLOT);
901    if (rowsEl !== null) el.delete(childArray().indexOf(rowsEl), 1);
902    for (const key of mapping.textSlots) {
903      const value = patch.content[key];
904      // A key ABSENT from the replacement stays deleted (cleared above) —
905      // a wholesale replacement must not materialize an empty slot, which
906      // the next read would emit as an empty-string key the plain applier
907      // omits. A present-but-empty value (`""`) still creates the slot.
908      if (value !== undefined) {
909        setTextSlot(el, key, typeof value === "string" ? value : String(value));
910      }
911    }
912    if (mapping.hasRows) {
913      const value = patch.content.rows;
914      if (Array.isArray(value)) {
915        setRows(el, value as readonly (string | undefined)[]);
916      }
917    }
918    for (const key of mapping.attrKeys) {
919      const value = patch.content[key];
920      // `undefined`/absent → delete the attr (the read omits absent keys,
921      // matching the plain applier's wholesale content replacement); yjs
922      // `setAttribute(key, null)` deletes the attr too, but `undefined`
923      // would be a no-op — so use null for the absent case.
924      setAttr(el, key, value === undefined ? null : (value as string | number | boolean | null));
925    }
926  }
927  if (patch.properties !== undefined) {
928    // Wholesale replacement: clear every `p.*` attr, then set the patch's.
929    const attrs = el.getAttributes() as Record<string, unknown>;
930    for (const k of Object.keys(attrs)) {
931      if (k.startsWith(PROP_ATTR_PREFIX)) el.removeAttribute(k);
932    }
933    for (const [k, v] of Object.entries(patch.properties)) {
934      if (v === undefined) continue;
935      el.setAttribute(PROP_ATTR_PREFIX + k, JSON.stringify(v));
936    }
937  }
938  if (patch.position !== undefined) el.setAttribute("position", patch.position);
939}
940 
941/**
942 * Apply wire block operations to the Y.Doc (the CRDT half of the
943 * two-codecs-agree property test). A `move` rewrites the `position` attr
944 * AND the fragment order in one transaction (the load-bearing codec rule);
945 * the destination parent resolves from the anchors (the wire gap: no
946 * `parentId` on moves). Cross-`toPageId` moves are no-ops here — the
947 * property test is single-page; cross-page moves ride the REST batch path
948 * (recorded).
949 */
950export function applyBlockOperationsToYDoc(
951  doc: Y.Doc,
952  operations: readonly BlockOperation[],
953): void {
954  for (const op of operations) {
955    switch (op.op) {
956      case "delete": {
957        const el = elementOf(doc, op.id);
958        if (el !== undefined) {
959          const parent = parentOf(doc, el);
960          if (parent !== null) removeElement(parent, el);
961        }
962        break;
963      }
964      case "update": {
965        const el = elementOf(doc, op.id);
966        if (el !== undefined) applyPatchToElement(el, op.patch);
967        break;
968      }
969      case "move": {
970        const el = elementOf(doc, op.id);
971        if (el === undefined || op.toPageId !== undefined) break;
972        const currentParent = parentOf(doc, el);
973        // el exists in the doc (elementOf just found it), so its parent
974        // resolves — `null` means the walk never matched, which cannot
975        // happen; guard anyway so `currentParent` narrows below.
976        if (currentParent === null) break;
977        // Destination: the anchor's parent (the wire `move` has no
978        // `parentId` — the anchor IS the destination); no anchor keeps
979        // the current parent (mirrors the plain applier's
980        // resolveDestParentId exactly).
981        const destParent = anchorParent(doc, op.before, op.after) ?? currentParent;
982        if (destParent === null) break;
983        const siblings = siblingsOf(destParent, op.id);
984        // The load-bearing rule: the `position` attr and the fragment
985        // order are rewritten in the SAME operation (never diverge).
986        const newPosition = landingPosition(
987          siblings,
988          String(el.getAttribute("position") ?? ""),
989          op.before,
990          op.after,
991        );
992        if (
993          destParent === currentParent &&
994          op.before === undefined &&
995          op.after === undefined
996        ) {
997          // No-anchor same-parent move: only the position attr changes
998          // (the order is untouched — mirrors the plain applier, whose
999          // canonical rebuild is a no-op when the position is unchanged).
1000          el.setAttribute("position", newPosition);
1001          break;
1002        }
1003        // Move = delete old + insert FRESH (the y-prosemirror 1.3.7
1004        // snapshot-diff model: a reordered node is deleted and re-created
1005        // from its data, never re-inserted). Re-inserting an ALREADY
1006        // integrated Y.XmlElement crashes yjs 13.6 (`YXmlFragment._integrate`
1007        // re-runs `insert(0, _prelimContent)` with null), and `clone(true)`
1008        // is no good either: `YXmlText.clone()` rebuilds the text from its
1009        // delta WITHOUT copying the `name` attr, so a cloned slot is
1010        // unreadable by the codec (spurious empty-content update). Capture
1011        // the subtree as plain data instead, delete the original, and
1012        // rebuild it fresh through the encoder's own builder (blockToYElement
1013        // — the property-tested lossless path).
1014        const captured = captureSubtree(el, parentIdOf(doc, currentParent)).map((b) => ({
1015          ...b,
1016          position: newPosition,
1017        }));
1018        removeElement(currentParent, el);
1019        const childrenOf = (id: string): BlockLike[] =>
1020          captured.filter((b) => b.parentId === id);
1021        const fresh = buildSubtree(captured[0]!, childrenOf);
1022        destParent.insert(indexForAnchors(siblings, op.before, op.after), [fresh]);
1023        break;
1024      }
1025      case "insert": {
1026        const id = op.block.id ?? `blk_${Math.floor(Math.random() * 1e9).toString(16)}`;
1027        // Destination parent (mirrors the plain applier's
1028        // resolveDestParentId exactly): the anchor's parent wins (the
1029        // anchors are the destination); then the payload's `parentId`
1030        // when it exists in the doc; else the root fragment.
1031        let destParent: YParent = newFragment(doc);
1032        const anchor = anchorParent(doc, op.before, op.after);
1033        if (anchor !== null) {
1034          destParent = anchor;
1035        } else if (op.block.parentId !== undefined) {
1036          const parentEl = elementOf(doc, op.block.parentId);
1037          if (parentEl !== undefined) destParent = parentEl;
1038        }
1039        // `position` is optional on the wire insert; `landingPosition`
1040        // re-derives it below (anchors → payload → end-of-list), so a blank
1041        // placeholder is safe (it is never observed).
1042        const block: BlockLike = {
1043          id,
1044          type: op.block.type,
1045          content: op.block.content as BlockContentByType[BlockType],
1046          parentId: op.block.parentId ?? null,
1047          position: op.block.position ?? "",
1048          ...(op.block.properties !== undefined ? { properties: { ...op.block.properties } } : {}),
1049        };
1050        const el = blockToYElement(block);
1051        el.setAttribute(
1052          "position",
1053          landingPosition(siblingsOf(destParent, id), op.block.position, op.before, op.after),
1054        );
1055        destParent.insert(indexForAnchors(siblingsOf(destParent, id), op.before, op.after), [el]);
1056        break;
1057      }
1058    }
1059  }
1060}
1061 
1062// --- state vector / update encodings (base64 over the wire) -------------------
1063 
1064const B64_CHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
1065 
1066export function bytesToBase64(bytes: Uint8Array): string {
1067  let out = "";
1068  for (let i = 0; i < bytes.length; i += 3) {
1069    const b0 = bytes[i] ?? 0;
1070    const b1 = i + 1 < bytes.length ? (bytes[i + 1] ?? 0) : 0;
1071    const b2 = i + 2 < bytes.length ? (bytes[i + 2] ?? 0) : 0;
1072    out += B64_CHARS[(b0 >> 2) & 0x3f] ?? "";
1073    out += B64_CHARS[((b0 & 0x03) << 4) | ((b1 >> 4) & 0x0f)] ?? "";
1074    out += i + 1 < bytes.length ? (B64_CHARS[((b1 & 0x0f) << 2) | ((b2 >> 6) & 0x03)] ?? "") : "=";
1075    out += i + 2 < bytes.length ? (B64_CHARS[b2 & 0x3f] ?? "") : "=";
1076  }
1077  return out;
1078}
1079 
1080const B64_LOOKUP: Record<string, number> = {};
1081for (let i = 0; i < B64_CHARS.length; i += 1) B64_LOOKUP[B64_CHARS[i] ?? ""] = i;
1082 
1083export function base64ToBytes(input: string): Uint8Array {
1084  const clean = input.replace(/=+$/, "");
1085  const out = new Uint8Array(Math.floor((clean.length * 3) / 4));
1086  let o = 0;
1087  for (let i = 0; i < clean.length; i += 4) {
1088    const a = B64_LOOKUP[clean[i] ?? ""] ?? 0;
1089    const b = B64_LOOKUP[clean[i + 1] ?? ""] ?? 0;
1090    const c = i + 2 < clean.length ? (B64_LOOKUP[clean[i + 2] ?? ""] ?? 0) : 0;
1091    const d = i + 3 < clean.length ? (B64_LOOKUP[clean[i + 3] ?? ""] ?? 0) : 0;
1092    const n = (a << 18) | (b << 12) | (c << 6) | d;
1093    if (o < out.length) out[o] = (n >> 16) & 0xff;
1094    if (o + 1 < out.length) out[o + 1] = (n >> 8) & 0xff;
1095    if (o + 2 < out.length) out[o + 2] = n & 0xff;
1096    o += 3;
1097  }
1098  return out;
1099}
1100 
1101/** Encode the doc's full state as a base64 Yjs update (the `sync.state` payload). */
1102export function encodeDocAsUpdate(doc: Y.Doc): string {
1103  return bytesToBase64(Y.encodeStateAsUpdate(doc));
1104}
1105 
1106/** Encode the doc's state vector as base64 (the `sync.request` payload). */
1107export function encodeDocStateVector(doc: Y.Doc): string {
1108  return bytesToBase64(Y.encodeStateVector(doc));
1109}
1110 
1111/** Decode a base64 Yjs update / state vector back to bytes. */
1112export function decodeBase64Yjs(input: string): Uint8Array {
1113  return base64ToBytes(input);
1114}
1115