Something went wrong. Try again.
Something went wrong. Try again.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394export interface Operation { opId: string; /** Causal predecessors. Omitted or empty for a root op. */ previousOpIds?: string[];}
/** * Sort operations into a deterministic order, deduplicated by opId. * * Algorithm: * - Deduplicate by opId — opId is identity, so duplicate copies of an op fold * once (a redelivered insert must not splice twice). A deterministic * representative is kept (see the body), so the result is independent of * input order. * - Each operation is assigned a bucket. An op with no previousOpIds is in * bucket 0. Otherwise its bucket is MAX(bucket of each previousOpId) + 1. * - Operations are ordered by bucket ascending, then lexically by opId * within a bucket. opIds are unique after dedup, so the order is total. * * An op is dropped from the result if its previousOpIds can never be satisfied * by an applied op. That covers references to a missing opId, ops in a cycle, * and ops that transitively depend on either. */export function sortOperations<T extends Operation>(operations: T[]): T[] { // Deduplicate by opId: the opId *is* the op's identity (see `identity.ts`), so // two ops sharing one are the same op and must fold once — otherwise a redelivered // insert would splice its block twice. Same-opId copies are byte-identical except // possibly in `previousOpIds` (a content id that excludes deps, e.g. `delete`, can // be issued from different causal views). We keep a deterministic representative — // the one whose sorted `previousOpIds` is lexicographically smallest — so the pick // never depends on input order and every replica converges on it. The choice is // arbitrary but stable; it is sound because a deps-excluding id is, by definition, // one whose effect does not depend on its causal position. Deps-bearing ids carry // their deps in the id, so all their copies tie here and the first is kept. const depsKey = (op: Operation): string => JSON.stringify([...(op.previousOpIds ?? [])].sort()); const byId = new Map<string, T>(); for (const op of operations) { const existing = byId.get(op.opId); if (!existing || depsKey(op) < depsKey(existing)) byId.set(op.opId, op); }
// Final memoized bucket per opId. `null` means unresolvable (cyclic or // depends on a cycle) and the op is excluded from the result. const buckets = new Map<string, number | null>(); const onStack = new Set<string>();
const bucketOf = (opId: string): number | null => { if (buckets.has(opId)) return buckets.get(opId)!;
const op = byId.get(opId); // Missing reference: never applied -> unresolvable. if (!op) { buckets.set(opId, null); return null; } // No predecessors (omitted or empty) -> root, bucket 0. const previousOpIds = op.previousOpIds ?? []; if (previousOpIds.length === 0) { buckets.set(opId, 0); return 0; }
// Back edge: opId is still resolving further up the stack -> cycle. // Don't cache here; this frame finishes resolving below. if (onStack.has(opId)) return null; onStack.add(opId);
let max = -1; let resolvable = true; for (const prev of previousOpIds) { const prevBucket = bucketOf(prev); if (prevBucket === null) { resolvable = false; break; } max = Math.max(max, prevBucket); } onStack.delete(opId);
const bucket = resolvable ? max + 1 : null; buckets.set(opId, bucket); return bucket; };
return [...byId.values()] .filter((op) => bucketOf(op.opId) !== null) .sort((a, b) => { const bucketDiff = bucketOf(a.opId)! - bucketOf(b.opId)!; if (bucketDiff !== 0) return bucketDiff; return a.opId < b.opId ? -1 : a.opId > b.opId ? 1 : 0; });}