chris.pardy.family
This repository has no description
1/**
2 * Collections: the shared substrate under the OR-Set and the RGA.
3 *
4 * Both collection types (see `orset.ts` and `rga.ts`) fold to the *same* thing —
5 * an ordered list of element **nodes**, each a reference (by target id) or inline
6 * data, live or tombstoned. They differ only in how their ops touch that list:
7 *
8 * - OR-Set `add` appends (refs dedup by target); `remove` filters out by
9 * identity (the element is gone — a re-add re-appears, observed-remove).
10 * - RGA `insert` splices a block at an anchor; `delete` tombstones by element id
11 * (the node stays so later inserts can still anchor on it).
12 *
13 * Because the substrate is shared, a single `target` can be written by *both*
14 * families and the type **transforms across ops**: there is no conversion step,
15 * the one node list flows through whichever handler each op needs. An `insert`
16 * can anchor on an OR-Set-added element; a later `remove` imposes set dedup on
17 * inserted refs; an `add` appends onto an RGA list. The handler is chosen per op
18 * (`applyCollection`), so order in the causally-sorted stream is all that decides
19 * the outcome — the same convergence story as everywhere else.
20 *
21 * How the folded list is *projected* depends on the family of the **last** op
22 * (see `reducer.ts`): an OR-Set last op yields a `#set` (`collectionSet`), an RGA
23 * last op yields a `#sequence` (`collectionSeq`).
24 */
25import { makeRef } from "./ref.js";
26import { applyOrSet, isOrSetOp, type OrSetOperation } from "./orset.js";
27import { applyRga, isRgaOp, type RgaOperation } from "./rga.js";
28
29/** Any operation that contributes to a collection value object (OR-Set or RGA). */
30export type CollectionOperation = OrSetOperation | RgaOperation;
31
32/**
33 * A positioned element: a ref (by target id) or inline data, live or tombstoned.
34 *
35 * - `id` is the element identity used for anchoring (an OR-Set add's own `opId`,
36 * or an RGA element's `"<opId>.<index>"`) and, for inline data, the key under
37 * which it appears in a `#set` projection.
38 * - `srcId` is the op that produced this element — the run `id` in a `#sequence`
39 * projection. `idx` is the element's offset within that op's block.
40 * - `origin` records whether the source value was a string (so a `#sequence` run
41 * re-joins its elements into a string) or an array (the run collects them into
42 * an array). An OR-Set add is a one-element `array` origin.
43 * - `deleted` marks an RGA tombstone; OR-Set removes drop nodes outright, so
44 * they never set it.
45 */
46export type Node = {
47 id: string;
48 srcId: string;
49 idx: number;
50 origin: "string" | "array";
51 deleted: boolean;
52} & (
53 | { kind: "ref"; target: string }
54 | { kind: "data"; value: unknown }
55);
56
57export interface CollectionResult {
58 /** Elements in order, including tombstones. */
59 nodes: Node[];
60 /** The last op folded into this collection (decides projection and `lastOpId`). */
61 lastOp: CollectionOperation;
62}
63
64/** Reducer state: the collection so far, or `null` before any op is applied. */
65export type CollectionState = CollectionResult | null;
66
67/** True if `op` is a collection operation (OR-Set or RGA, vs. a register op). */
68export function isCollectionOp(op: { $type: string }): op is CollectionOperation {
69 return isOrSetOp(op) || isRgaOp(op);
70}
71
72/**
73 * Apply one collection operation to the running state, dispatching to the OR-Set
74 * or RGA handler by op kind. Both operate on the shared node list, so a target
75 * may freely mix the two families across its op stream.
76 */
77export function applyCollection(
78 state: CollectionState,
79 op: CollectionOperation,
80): CollectionResult {
81 if (isOrSetOp(op)) return applyOrSet(state, op);
82 return applyRga(state, op);
83}
84
85/** The display value of an element: a ref encodes as `{ $ref }`, data copies through. */
86function elementValue(node: Node): unknown {
87 return node.kind === "ref" ? makeRef(node.target) : node.value;
88}
89
90/**
91 * Project the folded collection as a `#set` value: an object keyed by element
92 * identity. A ref is keyed by its target (so duplicate refs collapse, the OR-Set
93 * dedup rule); inline data is keyed by its element id. Tombstones are dropped.
94 * References are left as `{ $ref }` — resolved later, at materialization.
95 */
96export function collectionSet(state: CollectionResult): Record<string, unknown> {
97 const out: Record<string, unknown> = {};
98 for (const node of state.nodes) {
99 if (node.deleted) continue;
100 if (node.kind === "ref") out[node.target] = makeRef(node.target);
101 else out[node.id] = node.value;
102 }
103 return out;
104}
105
106/** One run of a `#sequence` projection: live values or a tombstoned range. */
107export type SeqItem =
108 | {
109 $type: "local.crdt.document#seqValues";
110 id: string;
111 startIdx: number;
112 values: unknown;
113 }
114 | {
115 $type: "local.crdt.document#seqTombstones";
116 id: string;
117 startIdx: number;
118 endIdx: number;
119 };
120
121/** A run being accumulated by `collectionSeq`. */
122interface Run {
123 srcId: string;
124 deleted: boolean;
125 origin: "string" | "array";
126 startIdx: number;
127 /** The next contiguous sub-index this run would extend to. */
128 nextIdx: number;
129 values: unknown[];
130}
131
132/**
133 * Project the folded collection as a `#sequence`: a run-length encoding of the
134 * node list. Consecutive nodes that share a source op, deleted status, and run
135 * of sub-indices collapse into one run — `#seqValues` (with the re-joined values)
136 * for live runs, `#seqTombstones` (a `startIdx`/`endIdx` range) for dead ones.
137 */
138export function collectionSeq(state: CollectionResult): SeqItem[] {
139 const items: SeqItem[] = [];
140 let run: Run | null = null;
141
142 const flush = () => {
143 if (!run) return;
144 if (run.deleted) {
145 items.push({
146 $type: "local.crdt.document#seqTombstones",
147 id: run.srcId,
148 startIdx: run.startIdx,
149 endIdx: run.nextIdx - 1,
150 });
151 } else {
152 items.push({
153 $type: "local.crdt.document#seqValues",
154 id: run.srcId,
155 startIdx: run.startIdx,
156 values: run.origin === "string" ? run.values.join("") : run.values,
157 });
158 }
159 run = null;
160 };
161
162 for (const node of state.nodes) {
163 if (
164 run &&
165 run.srcId === node.srcId &&
166 run.deleted === node.deleted &&
167 node.idx === run.nextIdx
168 ) {
169 run.values.push(elementValue(node));
170 run.nextIdx = node.idx + 1;
171 } else {
172 flush();
173 run = {
174 srcId: node.srcId,
175 deleted: node.deleted,
176 origin: node.origin,
177 startIdx: node.idx,
178 nextIdx: node.idx + 1,
179 values: [elementValue(node)],
180 };
181 }
182 }
183 flush();
184 return items;
185}