Something went wrong. Try again.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178/** * Replicated Growable Array (RGA) — an ordered list value object. * * Like the OR-Set (see `orset.ts`), an RGA is a value object (one `target`) that * folds to an ordered list of elements, projected as a `#sequence` of runs (see * `collectionSeq` in `collection.ts`). What it adds over the OR-Set is *order*: * elements live at stable positions and new elements are inserted relative to an * existing position, not just appended. * * ## Elements and their ids * * A single `insert` inserts *several* elements at once. Its `value` is either a * **string** — one element per Unicode code point ("hi" -> two elements) — or an * **array** — one element per entry, each entry a reference (`{ $ref }`, detected * structurally as everywhere else) or inline data. Each element's identity is * `"<opId>.<index>"`: insert `c1` of `"hi"` yields `c1.0` and `c1.1`. That * per-element id is what later inserts anchor on; `delete` instead names the * source `opId` plus a sub-index range. * * ## Insert: anchor + side, with sentinels * * An insert places its block relative to an `anchor` on a `side`: * * - `anchor` is an existing element id, or the sentinel `"BEGIN"` / `"END"`. * - `side` is `"before"` or `"after"`. * * The block is spliced immediately before (or after) the anchor's *current* * position. As with the other types, convergence comes from the deterministic * sort (`sortOperations`), not a merge lattice: every replica folds the identical * stream, so "the anchor's current position" is identical everywhere. Concurrent * inserts at the same anchor are applied in sort order, each splicing nearest the * anchor, which lands them in a stable, deterministic order. Causality * (`previousOpIds`) keeps an anchor present when an op that references it runs; * an insert whose anchor is genuinely missing is dropped (its elements are not * added). `BEGIN`/`END` are virtual ends of the list — `after BEGIN` is the * front, `before END` is the back (either side of a sentinel resolves the same). * * ## Delete: observed-remove of known elements * * `delete` names a source `id` (the `opId` of the `insert` that created the * block) and an optional `startIdx`/`endIdx` sub-range (inclusive); with no range * it tombstones the whole block. The fold tombstones each named element: it stays * in the list (so inserts anchored on it still resolve) but drops out of the * projected value. Because a delete names ids rather than a positional span, an * element inserted *into* that span concurrently has a different id, is not named, * and survives — the observed-remove property: you can only delete what you have * already seen. * * An RGA folds over the shared collection node list (see `collection.ts`), so a * target may also receive OR-Set ops; the two families transform into one * another across the op stream. */import { isRef } from "./ref.js";import type { CollectionResult, CollectionState, Node } from "./collection.js";
/** The sentinel anchors: the virtual ends of the list. */export const BEGIN = "BEGIN";export const END = "END";
/** * Insert a block of elements relative to an anchor. * * `value` is a string (one element per code point) or an array (one element per * entry; entries are refs `{ $ref }` or inline data). Any other JSON value is * treated as a single inline element. */export interface InsertOperation { $type: "local.crdt.ops#insert"; opId: string; previousOpIds: string[]; /** The RGA value-object id this op writes to. */ target: string; /** Element id to anchor on, or the `BEGIN` / `END` sentinel. */ anchor: string; /** Which side of the anchor the block goes. Defaults to `"after"` when omitted. */ side?: "before" | "after"; /** The element(s) to insert: a string, an array, or a single value. */ value: unknown;}
/** Tombstone a block's elements by source op id, optionally narrowed to a sub-range. */export interface DeleteOperation { $type: "local.crdt.ops#delete"; opId: string; previousOpIds: string[]; /** The RGA value-object id this op writes to. */ target: string; /** The source `opId` whose elements are tombstoned. */ id: string; /** First sub-index to tombstone (inclusive). Omitted tombstones from the start. */ startIdx?: number; /** Last sub-index to tombstone (inclusive). Omitted tombstones to the end. */ endIdx?: number;}
/** Any operation that contributes to an RGA value object. */export type RgaOperation = InsertOperation | DeleteOperation;
/** RGA folds share the collection state (see `collection.ts`). */export type RgaState = CollectionState;
const RGA_TYPES = new Set(["local.crdt.ops#insert", "local.crdt.ops#delete"]);
/** True if `op` is an RGA operation (vs. an OR-Set or register op). */export function isRgaOp(op: { $type: string }): op is RgaOperation { return RGA_TYPES.has(op.$type);}
/** Split an insert's `value` into the elements it adds, keyed by `opId.index`. */function elementsOf(op: InsertOperation): Node[] { const isString = typeof op.value === "string"; const items = isString ? [...op.value as string] // one element per code point : Array.isArray(op.value) ? op.value : [op.value]; // any other value is a single inline element const origin: "string" | "array" = isString ? "string" : "array"; return items.map((item, i) => { const base = { id: `${op.opId}.${i}`, srcId: op.opId, idx: i, origin, deleted: false, }; return isRef(item) ? { ...base, kind: "ref" as const, target: item.$ref } : { ...base, kind: "data" as const, value: item }; });}
/** * Resolve the splice index for an insert, or `-1` if the anchor is missing. * * - `BEGIN` -> the front; `END` -> the back (either side resolves the same). * - `after` an element -> just past it; `before` an element -> just ahead of it. */function spliceIndex( nodes: Node[], anchor: string, side: "before" | "after" | undefined,): number { if (anchor === BEGIN) return 0; if (anchor === END) return nodes.length; const idx = nodes.findIndex((n) => n.id === anchor); if (idx === -1) return -1; // `side` defaults to "after" (lexicon default); only "before" splices ahead. return side === "before" ? idx : idx + 1;}
/** * Apply one RGA operation to the running state: `(state, op) => state`. * * - `insert` splices its block at the anchor; a missing anchor drops it. * - `delete` tombstones each currently-live element of the named source op that * falls in the (optional) sub-range. */export function applyRga( state: CollectionState, op: RgaOperation,): CollectionResult { const nodes = state ? state.nodes : []; if (op.$type === "local.crdt.ops#insert") { const at = spliceIndex(nodes, op.anchor, op.side); if (at === -1) return { nodes, lastOp: op }; // anchor gone: drop the insert const block = elementsOf(op); const next = [...nodes.slice(0, at), ...block, ...nodes.slice(at)]; return { nodes: next, lastOp: op }; } const inRange = (i: number) => (op.startIdx === undefined || i >= op.startIdx) && (op.endIdx === undefined || i <= op.endIdx); const next = nodes.map((n) => n.srcId === op.id && !n.deleted && inRange(n.idx) ? { ...n, deleted: true } : n, ); return { nodes: next, lastOp: op };}