Convergent Replicated List (CR-List)

This document defines Convergent Replicated List (CR-List), a delta CRDT for an ordered sequence of entries. Each index resolves to a single visible value. Every update is assigned a UUIDv7, and deletions are tracked as a list of UUIDv7 identifiers.

The specification defines the data structure, merge rules, snapshot and delta formats, garbage-collection rules, acknowledgement formats, and one conforming JavaScript binding.

Terminology

A CR-List replica is one independently mutable instance of the data structure.

A UUIDv7 identifier is an identifier that is a valid UUID version 7 as defined by [[RFC9562]].

a linked list is a list implemented by each item having a link to the next item. [[LINKED_LIST]].

a doubly linked list is a variant of a linked list in which each item has a link to the previous item as well as the next. [[DOUBLY_LINKED_LIST]].

a serializable object is an object that supports being serialized, and later deserialized as defined by [[HTML]].

A predecessor identifier is an UUIDv7 identifier or the root sentinel '\0' pointing to what list value a list value comes after.

A list index is the position of a list value, starting at 0 and ending at the list length, in the resolved conflict-free ordering of a CR-List replica.

A list value is the consumer defined payload presently selected for a given list index.

The list length is the number of list value(s) in a CR-List replica.

A replica state is a struct consisting of replica values and replica tombstones tracked by CR-List replica.

The replica values is the set of 0 or more values entry(s) tracked by replica state.

A values entry is a struct consisting of a UUIDv7 Identifier, list value, and predecessor identifier tracked by replica values. A conforming runtime MAY additionally project those same entries into a local doubly linked list by tracking members such as prev, next, and index.

The replica tombstones is a list of 0 or more overwritten tombstones entry(s) tracked by replica state.

A tombstones entry is a UUIDv7 identifier representing a deleted list value tracked by replica tombstones.

An acknowledgement is a serializable string containing the current acknowledgement frontier of a single CR-List replica.

An acknowledgement frontier is the largest tombstones entry presently retained by replica tombstones under lexicographic comparison.

A snapshot is a serializable object presentation of a replica state.

A delta is a partial snapshot containing only the entries a CR-List replica wishes to share.

Algorithms

CRUD

Create

Let the result be a new empty CR-List replica whose replica values and replica tombstones are empty.
If the supplied snapshot is not a record, then return the result.
If snapshot has an own tombstones member whose value is a list, then for each listed item:
1. If the item is not a valid UUIDv7 identifier, continue.
2. If the result already retains that tombstones entry, continue.
3. Add the item to replica tombstones.
If snapshot does not have an own values member whose value is a list, then return the result.
For each listed candidate value entry, run the mint a snapshot value entry algorithm. If minting fails, continue.
For each successfully minted values entry, add it to the live UUID index and to the bucket keyed by its predecessor identifier.
Clear all live prev and next members.
Sort the bucket keys lexicographically by predecessor identifier.
For each bucket key in sorted order, if its bucket is resolvable, sort its siblings lexicographically by UUIDv7 and link them into the visible doubly linked list.
If at least one new bucket was resolved in that pass, repeat the previous step.
Walk to the visible tail and then back toward the head, assigning descending indexes so that the final visible head-to-tail order is zero-based and starts at 0.
Return the result.

Read

If the supplied list index is out of bounds, then return undefined.
Walk the current visible doubly linked list using the local cursor until the target index is reached.
Return a detached structured clone of the visible list value at that index.

Update

If the supplied list index is less than 0 or greater than the current list length, then fail.
If the supplied values input is not a list, then fail.
If the supplied values input is empty, then return no change.
For each supplied value, attempt to copy it with structuredClone. If copying fails, then fail.
For each copied value, mint a fresh UUIDv7 identifier for the inserted visible entry.
If the mode is after, insert the copied values in the given order after the target index. If the target index equals the current list length, append at the tail.
If the mode is before, insert the copied values in the given order before the target index.
If the mode is overwrite, replace the visible range beginning at the target index and extending for the number of supplied values. If the visible list ends first, append the remaining copied values at the tail.
Any visible entries replaced by overwrite MUST become new tombstones entry(s).
Return a delta describing the inserted values and the new tombstones, together with a visible change patch.

Delete

Let the effective start index be the supplied start index, or 0 if it was omitted.
Let the effective end index be the supplied end index, or the current list length if it was omitted.
If the effective range is invalid, then fail.
If the effective range is empty, then return no change.
Delete each visible entry in the range [startIndex, endIndex).
Add each deleted entry's UUIDv7 identifier to replica tombstones.
Return a delta containing the new tombstones together with a visible change patch that marks the deleted indexes as undefined.

MAGS

Merge

If the supplied candidate is not a record, then return no change.
If the candidate has an own tombstones member whose value is a list, then for each listed item:
1. If the item is not a valid UUIDv7 identifier, continue.
2. If the local replica already retains that tombstones entry, continue.
3. Add the tombstone to local tombstone state.
4. If a matching live entry exists, remove it from the visible projection and mark the merge as requiring relinking.
If the candidate does not have an own values member whose value is a list, then return the tombstone-only change, if any.
For each listed candidate value entry:
1. If the candidate is not a record, does not have its own uuidv7, value, and predecessor members, or its uuidv7 or predecessor member is not valid, continue.
2. If the local replica already tombstones the candidate uuidv7, continue.
3. If a live entry with the same UUIDv7 identifier already exists locally, adopt the incoming predecessor identifier only when it is lexicographically greater than the local predecessor identifier; otherwise ignore the incoming entry. Then continue to the next listed candidate value entry.
4. Run the mint a snapshot value entry algorithm. If it returns failure, continue.
5. Add the minted incoming entry to the live UUID index and to the bucket keyed by its predecessor identifier.
If every accepted incoming entry can be attached as a simple tail append, the implementation MAY update the visible projection incrementally and skip the next three steps.
Otherwise, clear all live prev and next members.
Otherwise, resolve predecessor buckets using the same sorted-pass bucket-resolution procedure defined in Core Model.
Otherwise, assign visible indexes so that the final head-to-tail order is zero-based and starts at 0.
Return the minimal visible change patch, or no change if nothing was adopted.

Acknowledge

If the local replica retains no tombstones entry, then return no acknowledgement.
Iterate the retained tombstones and keep the lexicographically greatest tombstone seen so far.
Return that greatest tombstone as the replica's acknowledgement.

Garbage Collect

If the supplied list of acknowledgement(s) is empty, then return.
Sort the supplied acknowledgements lexicographically.
Let the safe collection boundary be the smallest supplied acknowledgement.
Remove every retained tombstones entry less than or equal to that safe collection boundary.

This algorithm is only safe when the caller supplies acknowledgement(s) covering every replica whose future convergence must still be preserved. Supplying only a partial frontier set is caller misuse and does not guarantee that an offline replica can later catch up from deltas alone.

Snapshot

For each current live entry, run the shed a live value entry algorithm.
Assemble the shed live entries into the snapshot's values list.
Assemble all retained replica tombstones into the snapshot's tombstones list.
Return the resulting snapshot.

Reference JavaScript Binding

This section defines one conforming JavaScript binding for the model above.

API Summary

callback CRListForEachCallback = undefined (any value, unsigned long index, CRList list);

[Exposed=*]
interface CRList {
  constructor(optional object snapshot = {});
  readonly attribute unsigned long size;
  undefined append(any value, optional unsigned long afterIndex);
  undefined prepend(any value, optional unsigned long beforeIndex);
  undefined remove(unsigned long index);
  undefined merge(optional object delta = {});
  undefined acknowledge();
  undefined garbageCollect(sequence<DOMString> frontiers);
  undefined snapshot();
  undefined addEventListener(
    DOMString type,
    EventListener? listener,
    optional (AddEventListenerOptions or boolean) options = {}
  );
  undefined removeEventListener(
    DOMString type,
    EventListener? listener,
    optional (EventListenerOptions or boolean) options = {}
  );
  undefined forEach(CRListForEachCallback callback, optional any thisArg);
  object toJSON();
  iterable<any>;
};

dictionary CRListSnapshotValueEntry {
  required DOMString uuidv7;
  required any value;
  required DOMString predecessor;
};

dictionary CRListSnapshot {
  required sequence<CRListSnapshotValueEntry> values;
  required sequence<DOMString> tombstones;
};

dictionary CRListDelta {
  sequence<CRListSnapshotValueEntry> values;
  sequence<DOMString> tombstones;
};

The binding additionally exposes numeric property access through a JavaScript Proxy. Reading list[i] returns a detached copy of the visible value at index i. Writing list[i] = value performs an overwrite-style local mutation, and delete list[i] removes one visible entry.

The constructor and merge() methods are typed as taking generic objects in the coarse Web IDL summary above so that the IDL matches the permissive JavaScript ingress behavior. The expected object shapes are CRListSnapshot and CRListDelta as defined by the dictionaries above.

The root predecessor is represented by the null character '\0', which serializes to "\u0000" in JSON.

JSON.stringify(list) serializes the binding through its current snapshot, and for...of iterates detached copies of the current visible values in index order.

The binding also exposes a JavaScript toString() method whose return value is the JSON string form of the current snapshot.

Errors

The JavaScript binding throws CRListError with a string code attribute for local API misuse.

VALUE_NOT_CLONEABLE: Thrown when a local update receives a value that is not supported by structuredClone.
INDEX_OUT_OF_BOUNDS: Thrown when a local indexed mutation targets an invalid live range.
UPDATE_EXPECTED_AN_ARRAY: Thrown by the core update algorithm when its value input is not a list.
LIST_INTEGRITY_VIOLATION: Thrown when snapshot serialization detects impossible internal list state.

Events

The JavaScript binding maintains an internal EventTarget object as defined by DOM [[DOM]].

The binding forwards addEventListener() and removeEventListener() to that internal event target. Local mutations and merges dispatch synthetic events through the same target.

The JavaScript binding defines four synthetic event types. Each is a CustomEvent object whose detail attribute is initialized as described below [[DOM]].

delta event: A CustomEvent whose detail is a delta. The binding dispatches this event for local visible mutations that produce gossip material.
change event: A CustomEvent whose detail maps changed list indexes to their new visible values, or to undefined when an entry was removed.
ack event: A CustomEvent whose detail is the current acknowledgement frontier produced when acknowledge() is invoked.
snapshot event: A CustomEvent whose detail is the full current snapshot produced when snapshot() is invoked.

Numeric writes, numeric deletes, append(), prepend(), and remove() MUST dispatch delta event before change event. A merge MUST dispatch only change event when the visible live projection changes. acknowledge() MUST dispatch ack event when a frontier exists, and snapshot() MUST dispatch a snapshot event.

Auxiliary Algorithms

mint a snapshot value entry

If the candidate value is not a record, then return failure.
If the candidate value does not have its own uuidv7, value, or predecessor member, then return failure.
If the candidate value's uuidv7 member is not a valid UUIDv7 identifier, then return failure.
If the candidate value's predecessor member is neither a valid UUIDv7 identifier nor '\0', then return failure.
If the candidate value's value member cannot be copied with structuredClone, then return failure.
If the local replica already tombstones or already stores the candidate uuidv7, then return failure.
Return the minted values entry.

shed a live value entry

Return a new serializable object whose uuidv7, value, and predecessor members equal the live value entry, after shedding any local projection members such as prev, next, and index. The copied value MUST be a detached structured clone.

Methods

Constructor

Construct a new binding whose internal state is the result of the core create algorithm applied to the optional snapshot.

size

Return the current list length.

indexed property access

Reading list[i] returns the current visible list value copy at index i, or undefined when the index is out of bounds. Writing list[i] = value runs a one-value local overwrite mutation at that index and appends when i equals the current list length. Deleting delete list[i] deletes the single-item visible range [i, i + 1).

append()

Insert one visible value after the supplied index. If no index is supplied, append at the current tail.

prepend()

Insert one visible value before the supplied index. If no index is supplied, insert at the current head.

remove()

Delete the single visible entry at the supplied index.

merge()

Merge the supplied delta into the internal replica and, if the visible list changes, dispatch a change event whose detail is the minimal visible patch.

acknowledge()

Compute the current acknowledgement frontier and dispatch an ack event when a frontier exists.

garbageCollect()

Run the core garbage-collection algorithm with the supplied list of acknowledgement frontiers.

snapshot()

Create the current full snapshot and dispatch a snapshot event. The method returns undefined.

@@iterator

Iterate detached copies of the current visible list value(s) in ascending list index order.

forEach()

Call the supplied callback once for each visible list value copy in ascending list index order, passing value, index, and the list object.

toJSON()

Return the same serialized shape as snapshot. This is the value used by JSON.stringify.

addEventListener() and removeEventListener()

Forward listener registration and listener removal to the binding's internal EventTarget object using the provided type, listener, and options values.

Terminology

Core Model

Data Structure

Snapshot

Runtime

Consumer

Algorithms

CRUD

Create

Read

Update

Delete

MAGS

Merge

Acknowledge

Garbage Collect

Snapshot

Reference JavaScript Binding

API Summary

Errors

Events

Auxiliary Algorithms

mint a snapshot value entry

shed a live value entry

Methods

Constructor

size

indexed property access

append()

prepend()

remove()

merge()

acknowledge()

garbageCollect()

snapshot()

@@iterator

forEach()

toJSON()

addEventListener() and removeEventListener()