Something went wrong. Try again.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221/** * Operation identity — deriving a deterministic `opId` from an op's content. * * Convergence in this system comes entirely from folding the *same* causally * sorted op stream on every replica (see `sortOperations`). The sort boundary * deduplicates by `opId`, so two ops sharing an `opId` are treated as one. That * makes `opId` the unit of identity: *how it is assigned decides which ops merge.* * * - Assign `opId` from a per-replica nonce (`replica:counter`) and only a literal * re-delivery of the byte-identical op ever dedups. * - Assign `opId` as a hash of the op's *content* and two replicas that * independently produce the same edit produce the same `opId`, so the dedup at * the sort boundary collapses them. Two editors who both fix "a typa" -> "a * typo" converge on a single insert instead of "typoo". * * This module mints the content-addressed ids. The hash is the easy part; the * contract every client must share is *what gets hashed*. That contract has three * layers, and all three must match or the ids won't collide: * * 1. **Canonical serialization.** We hash via `cidForLex` (AT Protocol canonical * DAG-CBOR + CID) — the same canonicalization the repo already uses for record * CIDs, so clients agree on it for free. It fixes map key order, number * encoding, etc. Note it inherits the AT data model constraints (e.g. no * non-integer numbers); op `value`s are lexicon records and already satisfy * this. * 2. **Identity fields (this module).** Which fields of each op are identity — * see the table below. * 3. **Canonical op construction (the client's editor).** Two clients must emit * the *same* identity fields for "the same edit": a canonical anchor choice * for inserts (anchor the left neighbour, side `after`), a canonical range for * deletes (omit bounds for open ranges), and a canonical, *minimal* dependency * set where deps are part of identity. This module sorts `previousOpIds` so * ordering is not a divergence source, but it cannot canonicalize the client's * choice of *which* deps to list. * * ## What is content-addressed, and what includes `previousOpIds` * * The rule is one criterion: include `previousOpIds` in the identity exactly when * the op's *effect depends on its causal position* — i.e. its result changes with * what sorts before it. Otherwise the op is position-independent and deps are * excluded so the same act always collapses; and occurrence-bearing ops are not * content-addressed at all. * * | Op (`$type`) | Strategy | Identity fields | Incl. `prev`? | Why | * |-------------------|-----------------|-----------------------------------------|---------------|-----| * | `insert` (RGA) | content | target, anchor, side, value | **yes** | placement among concurrent peers; re-insert after delete must stay distinct | * | `set` (LWW) | content | target, value | **yes** | last-write-wins recency is causal-bucket order; re-assertion must stay distinct | * | `assign` | content | target, value | **yes** | per-key LWW; same as `set` | * | `add` ref (OR-Set)| content | target, valueId | **yes** | observed-remove: a re-add after a remove must stay distinct to re-appear | * | `add` inline, set | content | target, value | **yes** | opt-in set semantics; otherwise see below | * | `remove` (OR-Set) | content | target, valueId | **yes** | observed-remove cancels what sorts before it; two removes with different views differ | * | `delete` (RGA) | content | target, id, startIdx, endIdx | **no** | monotonic tombstone of elements named by stable id; effect is position-independent | * | `add` inline, multiset | **nonce** | — | — | each add is a distinct member; collapsing identical data would lose multiplicity | * | `incr` | **nonce** | — | — | accumulation: two `+1`s must total `+2`; content-addressing would wrongly merge them | * * Inline OR-Set `add` (no `valueId`) is the one per-*collection* choice: a set * (collapse identical data) or a multiset (keep duplicates). It defaults to * multiset — the existing semantics, where each inline add is keyed by its own * `opId` — and set semantics are opt-in via {@link MintOptions.inlineAdd}. * * Nonce ops (`incr`, multiset inline `add`) are *not* minted here: they must carry * a client-assigned unique `opId`. {@link mintOpId} throws for them rather than * silently returning a colliding hash. */import { cidForLex, type LexValue } from "@atproto/lex-cbor";import type { InsertOperation, DeleteOperation } from "./rga.js";import type { AddOperation, RemoveOperation } from "./orset.js";import type { SetOperation } from "./lww.js";import type { AssignOperation } from "./assign.js";import type { IncrOperation } from "./increment.js";
/** Any op whose identity policy this module knows. */export type IdentifiableOp = | InsertOperation | DeleteOperation | AddOperation | RemoveOperation | SetOperation | AssignOperation | IncrOperation;
/** `Omit` that distributes over a union, preserving the `$type` discriminant. */type DistributiveOmit<T, K extends PropertyKey> = T extends unknown ? Omit<T, K> : never;
/** * An op as seen by minting: identical to an {@link IdentifiableOp} but with no * `opId` — the id is *derived* here, so callers don't supply it (passing a full * op with its `opId` set is also fine; the field is ignored). */export type IdentityInput = DistributiveOmit<IdentifiableOp, "opId"> & { /** Ignored by minting; allowed so a fully-formed op can be passed unchanged. */ opId?: string;};
/** How an op's `opId` is derived. */export interface IdentityPolicy { /** * `"content"` — `opId` is a hash of the identity fields (this module mints it). * `"nonce"` — `opId` is a client-assigned unique value (this module refuses to * mint it; minting would collapse occurrences that must stay distinct). */ strategy: "content" | "nonce"; /** For `"content"`: whether `previousOpIds` are part of the identity. */ includesDeps: boolean;}
export interface MintOptions { /** * Identity policy for an inline OR-Set `add` (an `add` with no `valueId`): * - `"multiset"` (default): each add is a distinct member — `nonce`, not * content-addressed (the existing semantics). * - `"set"`: adds of identical data collapse — content-addressed (with deps). */ inlineAdd?: "multiset" | "set";}
/** Sorted copy of an op's `previousOpIds`, so dep *ordering* never changes identity. */function sortedDeps(op: { previousOpIds?: string[] }): string[] { return [...(op.previousOpIds ?? [])].sort();}
/** The identity policy for `op` — see the table in the module doc comment. */export function identityPolicy( op: IdentityInput, opts: MintOptions = {},): IdentityPolicy { switch (op.$type) { case "local.crdt.ops#delete": return { strategy: "content", includesDeps: false }; case "local.crdt.ops#insert": case "local.crdt.ops#set": case "local.crdt.ops#assign": case "local.crdt.ops#remove": return { strategy: "content", includesDeps: true }; case "local.crdt.ops#add": // A ref add is always content-addressed; an inline add follows the // per-collection set/multiset choice. if (op.valueId !== undefined) return { strategy: "content", includesDeps: true }; return (opts.inlineAdd ?? "multiset") === "set" ? { strategy: "content", includesDeps: true } : { strategy: "nonce", includesDeps: false }; case "local.crdt.ops#incr": return { strategy: "nonce", includesDeps: false }; }}
/** True if `op` gets a content-addressed `opId` (vs. a client-assigned nonce). */export function isContentAddressed(op: IdentityInput, opts: MintOptions = {}): boolean { return identityPolicy(op, opts).strategy === "content";}
/** * The canonical identity fields of `op` — the object that gets hashed into its * `opId`. Throws for nonce ops (which must carry a client-assigned `opId`). * * Optional fields are normalized to explicit sentinels (`side` defaults to * `"after"`, an open delete bound to `null`) so that two clients which differ only * in what they *omit* still produce identical fields. */export function identityFields( op: IdentityInput, opts: MintOptions = {},): Record<string, unknown> { const policy = identityPolicy(op, opts); if (policy.strategy === "nonce") { throw new Error( `${op.$type} is occurrence-bearing (nonce identity); it must carry a ` + `client-assigned unique opId, not a content hash.`, ); } const withDeps = (fields: Record<string, unknown>): Record<string, unknown> => policy.includesDeps ? { ...fields, prev: sortedDeps(op) } : fields;
switch (op.$type) { case "local.crdt.ops#insert": return withDeps({ $type: op.$type, target: op.target, anchor: op.anchor, side: op.side ?? "after", // lexicon default; omitted and "after" are one identity value: op.value, }); case "local.crdt.ops#delete": return withDeps({ $type: op.$type, target: op.target, id: op.id, startIdx: op.startIdx ?? null, // open bound -> null sentinel endIdx: op.endIdx ?? null, }); case "local.crdt.ops#set": case "local.crdt.ops#assign": return withDeps({ $type: op.$type, target: op.target, value: op.value }); case "local.crdt.ops#add": // Inline-multiset already threw above; here add is ref or inline-as-set. return op.valueId !== undefined ? withDeps({ $type: op.$type, target: op.target, valueId: op.valueId }) : withDeps({ $type: op.$type, target: op.target, value: op.value }); case "local.crdt.ops#remove": return withDeps({ $type: op.$type, target: op.target, valueId: op.valueId }); // `incr` is nonce and threw above; this default is unreachable for valid ops. default: throw new Error(`cannot mint a content opId for ${(op as { $type: string }).$type}`); }}
/** * Mint the content-addressed `opId` for `op`: the CID of its canonical identity * fields. Deterministic across clients that share the identity contract. Throws * for nonce ops. */export async function mintOpId( op: IdentityInput, opts: MintOptions = {},): Promise<string> { const cid = await cidForLex(identityFields(op, opts) as LexValue); return cid.toString();}