chris.pardy.family
This repository has no description
1export interface Operation {
2 opId: string;
3 /** Causal predecessors. Omitted or empty for a root op. */
4 previousOpIds?: string[];
5}
6
7/**
8 * Sort operations into a deterministic order, deduplicated by opId.
9 *
10 * Algorithm:
11 * - Deduplicate by opId — opId is identity, so duplicate copies of an op fold
12 * once (a redelivered insert must not splice twice). A deterministic
13 * representative is kept (see the body), so the result is independent of
14 * input order.
15 * - Each operation is assigned a bucket. An op with no previousOpIds is in
16 * bucket 0. Otherwise its bucket is MAX(bucket of each previousOpId) + 1.
17 * - Operations are ordered by bucket ascending, then lexically by opId
18 * within a bucket. opIds are unique after dedup, so the order is total.
19 *
20 * An op is dropped from the result if its previousOpIds can never be satisfied
21 * by an applied op. That covers references to a missing opId, ops in a cycle,
22 * and ops that transitively depend on either.
23 */
24export function sortOperations<T extends Operation>(operations: T[]): T[] {
25 // Deduplicate by opId: the opId *is* the op's identity (see `identity.ts`), so
26 // two ops sharing one are the same op and must fold once — otherwise a redelivered
27 // insert would splice its block twice. Same-opId copies are byte-identical except
28 // possibly in `previousOpIds` (a content id that excludes deps, e.g. `delete`, can
29 // be issued from different causal views). We keep a deterministic representative —
30 // the one whose sorted `previousOpIds` is lexicographically smallest — so the pick
31 // never depends on input order and every replica converges on it. The choice is
32 // arbitrary but stable; it is sound because a deps-excluding id is, by definition,
33 // one whose effect does not depend on its causal position. Deps-bearing ids carry
34 // their deps in the id, so all their copies tie here and the first is kept.
35 const depsKey = (op: Operation): string =>
36 JSON.stringify([...(op.previousOpIds ?? [])].sort());
37 const byId = new Map<string, T>();
38 for (const op of operations) {
39 const existing = byId.get(op.opId);
40 if (!existing || depsKey(op) < depsKey(existing)) byId.set(op.opId, op);
41 }
42
43 // Final memoized bucket per opId. `null` means unresolvable (cyclic or
44 // depends on a cycle) and the op is excluded from the result.
45 const buckets = new Map<string, number | null>();
46 const onStack = new Set<string>();
47
48 const bucketOf = (opId: string): number | null => {
49 if (buckets.has(opId)) return buckets.get(opId)!;
50
51 const op = byId.get(opId);
52 // Missing reference: never applied -> unresolvable.
53 if (!op) {
54 buckets.set(opId, null);
55 return null;
56 }
57 // No predecessors (omitted or empty) -> root, bucket 0.
58 const previousOpIds = op.previousOpIds ?? [];
59 if (previousOpIds.length === 0) {
60 buckets.set(opId, 0);
61 return 0;
62 }
63
64 // Back edge: opId is still resolving further up the stack -> cycle.
65 // Don't cache here; this frame finishes resolving below.
66 if (onStack.has(opId)) return null;
67 onStack.add(opId);
68
69 let max = -1;
70 let resolvable = true;
71 for (const prev of previousOpIds) {
72 const prevBucket = bucketOf(prev);
73 if (prevBucket === null) {
74 resolvable = false;
75 break;
76 }
77 max = Math.max(max, prevBucket);
78 }
79 onStack.delete(opId);
80
81 const bucket = resolvable ? max + 1 : null;
82 buckets.set(opId, bucket);
83 return bucket;
84 };
85
86 return [...byId.values()]
87 .filter((op) => bucketOf(op.opId) !== null)
88 .sort((a, b) => {
89 const bucketDiff = bucketOf(a.opId)! - bucketOf(b.opId)!;
90 if (bucketDiff !== 0) return bucketDiff;
91 return a.opId < b.opId ? -1 : a.opId > b.opId ? 1 : 0;
92 });
93}