Something went wrong. Try again.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253/** * Materialize a document body into plain JSON. * * A document body is a list of value objects (see `reducer.ts`): registers * (`#value`), OR-Sets (`#set`), and RGA sequences (`#sequence`). Materializing * starts from a root id and walks the graph, resolving references (see `ref.ts`): * * - A `$ref` may appear only as a direct member of a value object's root * container (depth-1). Deeper containers are inline data and are copied * through verbatim, with keys unescaped at every depth. * - A `$idx` (positional reference into a sequence) may appear at *any* depth of * inline data. It resolves to a position in the fully-materialized target * sequence: a byte offset for a string sequence, an item index for an array * one. * - A reference that resolves to nothing is *absent*: an object key is dropped, * an array element is dropped (the array compacts), the root becomes an empty * document (`undefined`). A reference resolves to nothing when its target is * missing (dangling) or is already being expanded on the current path (a * cycle). The cycle check is path-based, so a shared id that is not a cycle * still expands everywhere it is referenced. * * Projections: * - `#value` materializes its `value` (refs resolved). * - `#set` materializes to an array of its members' values (refs resolved, order * preserved; the element-identity keys are dropped). * - `#sequence` materializes to a string (string-origin runs re-joined) or an * array (array-origin elements, refs resolved). Tombstoned runs contribute * nothing. */import { isRef, isIdxRef, unescapeKey, type IdxRef } from "./ref.js";import type { ValueObject, DocBodyItem, DocSequence,} from "./reducer.js";
export type { ValueObject };
/** A reference that resolved to nothing. */const ABSENT: unique symbol = Symbol("absent");
/** Shared state for one materialization: the object map and a cache of sequence offset maps. */interface Ctx { items: Map<string, DocBodyItem>; /** Per-sequence offset maps, keyed by target then by `"<id>.<idx>"`. Built lazily. */ offsets: Map<string, Map<string, Span>>;}
/** Where an element sits in its materialized sequence: `[start, end)` offset. */interface Span { start: number; end: number;}
/** * Materialize a document body (the reducer's output) from `rootId` (default * `"ROOT"`) into plain JSON, or `undefined` for an empty/missing root. */export function materializeDocument( body: DocBodyItem[], rootId = "ROOT",): unknown { const ctx: Ctx = { items: new Map(body.map((item) => [item.id, item])), offsets: new Map(), }; const result = expand(rootId, ctx, []); return result === ABSENT ? undefined : result;}
/** * Materialize a register graph given as plain value objects (`{ id, value }`). * A thin adapter over `materializeDocument` for callers that hold value-space * objects rather than a full document body. */export function materialize( rootId: string, objects: Map<string, ValueObject>,): unknown { const body: DocBodyItem[] = [...objects.values()].map((o) => ({ $type: "local.crdt.document#value", id: o.id, value: o.value, lastOpId: o.lastOpId, })); return materializeDocument(body, rootId);}
/** Resolve the value object `id`, or `ABSENT` if dangling or on the path. */function expand(id: string, ctx: Ctx, path: string[]): unknown { if (path.includes(id)) return ABSENT; // cycle: id is an ancestor being expanded const item = ctx.items.get(id); if (!item) return ABSENT; // dangling: no such value object const next = [...path, id]; if (item.$type === "local.crdt.document#set") { const out: unknown[] = []; for (const member of Object.values(item.set)) { if (isRef(member)) { const resolved = expand(member.$ref, ctx, next); if (resolved !== ABSENT) out.push(resolved); } else { out.push(data(member, ctx)); } } return out; } if (item.$type === "local.crdt.document#sequence") { return materializeSequence(item, ctx, next); } return container(item.value, ctx, next);}
/** * Walk a value object's root container: `$ref` among the direct members is * resolved; everything else is inline data. */function container(value: unknown, ctx: Ctx, path: string[]): unknown { if (isRef(value)) return expand(value.$ref, ctx, path); if (isIdxRef(value)) return resolveIdx(value, ctx);
if (Array.isArray(value)) { const out: unknown[] = []; for (const element of value) { if (isRef(element)) { const resolved = expand(element.$ref, ctx, path); if (resolved !== ABSENT) out.push(resolved); } else { out.push(data(element, ctx)); } } return out; }
if (isPlainObject(value)) { const out: Record<string, unknown> = {}; for (const [key, member] of Object.entries(value)) { if (isRef(member)) { const resolved = expand(member.$ref, ctx, path); if (resolved !== ABSENT) out[unescapeKey(key)] = resolved; } else { out[unescapeKey(key)] = data(member, ctx); } } return out; }
return value; // scalar}
/** * Copy inline data through, unescaping keys and resolving `$idx` positions at any * depth. `$ref` is *not* resolved here — references live only at depth-1. */function data(value: unknown, ctx: Ctx): unknown { if (isIdxRef(value)) return resolveIdx(value, ctx); if (Array.isArray(value)) return value.map((v) => data(v, ctx)); if (isPlainObject(value)) { const out: Record<string, unknown> = {}; for (const [key, member] of Object.entries(value)) { out[unescapeKey(key)] = data(member, ctx); } return out; } return value;}
/** Materialize a `#sequence`: a re-joined string (string origin) or an array (array origin). */function materializeSequence( item: DocSequence, ctx: Ctx, path: string[],): unknown { const live = item.seq.filter( (run) => run.$type === "local.crdt.document#seqValues", ); const isString = live.every((run) => typeof run.values === "string"); if (isString) { return live.map((run) => run.values as string).join(""); } const out: unknown[] = []; for (const run of live) { for (const element of run.values as unknown[]) { if (isRef(element)) { const resolved = expand(element.$ref, ctx, path); if (resolved !== ABSENT) out.push(resolved); } else { out.push(data(element, ctx)); } } } return out;}
/** * Resolve a `$idx` to a position in its target sequence: the offset of element * `<id>.<idx>` (a byte offset for a string sequence, an item index for an array * one), or its exclusive end when `after` is set. Returns `undefined` if the * target is not a sequence or the position is unknown (e.g. it names a tombstoned * or missing element). */function resolveIdx(ref: IdxRef, ctx: Ctx): number | undefined { const { target, id, idx, after } = ref.$idx; const span = offsetsFor(target, ctx)?.get(`${id}.${idx}`); if (!span) return undefined; return after ? span.end : span.start;}
/** * Build (and cache) the offset map for a sequence: each live element `<id>.<idx>` * mapped to its `[start, end)` offset span. Strings count UTF-8 bytes per code * point; arrays count items. */function offsetsFor( target: string, ctx: Ctx,): Map<string, Span> | undefined { const cached = ctx.offsets.get(target); if (cached) return cached; const item = ctx.items.get(target); if (!item || item.$type !== "local.crdt.document#sequence") return undefined;
const map = new Map<string, Span>(); let cursor = 0; for (const run of item.seq) { if (run.$type !== "local.crdt.document#seqValues") continue; // tombstones hold no position const elements = typeof run.values === "string" ? [...run.values] // one element per code point : (run.values as unknown[]); elements.forEach((element, k) => { const width = typeof element === "string" ? utf8Length(element) : 1; map.set(`${run.id}.${run.startIdx + k}`, { start: cursor, end: cursor + width }); cursor += width; }); } ctx.offsets.set(target, map); return map;}
/** UTF-8 byte length of a string, counted per code point. */function utf8Length(s: string): number { let bytes = 0; for (const cp of s) { const c = cp.codePointAt(0)!; bytes += c <= 0x7f ? 1 : c <= 0x7ff ? 2 : c <= 0xffff ? 3 : 4; } return bytes;}
function isPlainObject(value: unknown): value is Record<string, unknown> { return typeof value === "object" && value !== null && !Array.isArray(value);}