Convergent Replicated Struct (CR-Struct)

This document defines Convergent Replicated Struct (CR-Struct), a delta CRDT for a fixed-key object-like data structure. Each field resolves to one visible value. Every overwrite is assigned a UUIDv7, and overwritten identifiers are retained as per-field tombstones.

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

Core Algorithms

CRUD

Create

Attempt to copy the supplied defaults object with structuredClone. If copying fails, then fail.
Let the result be a new empty CR-Struct replica whose entries member is empty and whose defaults member is the copied defaults object.
Let snapshotIsRecord be true if the supplied snapshot is a record, otherwise false.
Let allowMissing be the supplied allow-missing flag, or false if no flag was supplied.
For each own field key of the original defaults object:
1. Let defaultValue be the copied default value for that key.
2. If snapshotIsRecord is true, the snapshot has an own property for that key, and the snapshot entry successfully runs the transform a snapshot entry to a state entry algorithm against defaultValue, then store the minted entry as the live field entry and continue to the next key.
3. If allowMissing is true, then continue to the next key.
4. Otherwise mint one fresh root UUIDv7 and one fresh winning UUIDv7.
5. Store a field entry whose uuidv7 is the fresh winning UUIDv7, whose predecessor is the fresh root UUIDv7, whose value is defaultValue, and whose tombstones set initially contains only the fresh root UUIDv7.
Return the result.

Read

Let entry be the current live field entry for the supplied field key.
Return a detached structured clone of entry's value.

Local Overwrite

If no current local field entry exists for the supplied key, mint one fresh root UUIDv7 and one fresh winning UUIDv7, then store a field entry whose uuidv7 is the fresh winning UUIDv7, whose predecessor is the fresh root UUIDv7, whose value is that key's default value, and whose tombstones set initially contains only the fresh root UUIDv7.
Let target be the current local field entry for the supplied key.
Let oldUuidv7 be target's current uuidv7.
Replace target's uuidv7 with a fresh UUIDv7, replace its value with the supplied value, replace its predecessor with oldUuidv7, and add oldUuidv7 to its tombstones.
Return the result of running transform a state entry to a snapshot entry on target.

Update

If the supplied key is not a known field key, then return no change.
Attempt to copy the supplied value with structuredClone. If copying fails, then fail.
If the runtime prototype of the copied value does not equal the runtime prototype of the default value for the supplied field key, then fail.
Run the local overwrite procedure for that field using the copied value.
Return a delta containing the new snapshot entry for that field together with a visible change patch mapping the key to the copied value.

Delete

If a specific key was supplied and the replica does not contain that key, then fail.
If a specific key was supplied, then run the local overwrite procedure for that field using the field's default value.
Otherwise, for each field key in the replica, run the local overwrite procedure for that field using that field's default value.
Return a delta containing the resulting snapshot entries together with a visible change patch mapping each touched key to its reset value.

MAGS

Merge

If the supplied candidate is not a record, then return no change.
Let the reply delta be an empty record.
Let the visible change patch be an empty record.
For each own property of the incoming candidate:
1. If the property name is not a known field key, then continue.
2. Run the transform a snapshot entry to a state entry algorithm against the local default value for that key. If minting fails, then continue.
3. Let target be the current local field entry for that key.
4. If target does not exist, store the candidate entry as the current local field entry, record the visible field change, and continue.
5. Let current be a shallow copy of target.
6. Let frontier be the lexicographically greatest tombstone currently retained by target.
7. For each incoming tombstone in the candidate field entry:
  1. If the tombstone is less than or equal to frontier, continue.
  2. If target already retains that tombstone, continue.
  3. Add the tombstone to target.
8. If target already tombstones the candidate uuidv7, then continue.
9. If current's uuidv7 equals the candidate uuidv7:
  1. If current's predecessor is lexicographically less than the candidate predecessor, then adopt the candidate value and predecessor, add the candidate predecessor to the tombstone set, record the visible field change, and continue.
  2. Otherwise run the local overwrite procedure using current's value, append the resulting snapshot entry to the reply delta, and continue.
10. If current's uuidv7 equals the candidate predecessor, or the target tombstones already contain current's uuidv7, or the candidate uuidv7 is lexicographically greater than current's uuidv7, then:
  1. Adopt the candidate uuidv7, value, and predecessor.
  2. Add the candidate predecessor and the previous local winner's UUIDv7 to the target tombstone set.
  3. Record the visible field change.
  4. Continue.
11. Otherwise add the candidate uuidv7 to the target tombstone set and append the current local field entry to the reply delta.
If neither the reply delta nor the visible change patch contains any own properties, then return no change.
Return the reply delta together with the visible change patch.

Acknowledge

Let the result be an empty acknowledgement record.
For each local field entry:
1. Iterate the retained tombstones and keep the lexicographically greatest tombstone seen so far.
2. Store that greatest tombstone in the result under the field's key.
Return the result.

Garbage Collect

If the supplied list of acknowledgement frontier objects is empty, then return.
Let smallestPerKey be an empty record.
For each supplied acknowledgement frontier object:
1. For each own property of that frontier:
  1. If the property name is not a known field key, then continue.
  2. If the frontier value is not a valid UUIDv7 identifier, then continue.
  3. If smallestPerKey already stores a value for that key and that stored value is lexicographically less than or equal to the new frontier, then continue.
  4. Otherwise store the new frontier as the smallest known acknowledgement for that key.
For each key stored in smallestPerKey:
1. Let target be the current local field entry for that key.
2. Remove every retained tombstone less than or equal to the smallest acknowledgement for that key, except the field's current predecessor.

This algorithm is only safe when the caller supplies a membership-complete set of acknowledgement frontiers 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

Let the result be an empty record.
For each current local field entry, run the transform a state entry to a snapshot entry algorithm.
Store each serialized field entry in the result under its field key.
Return the resulting snapshot.

Reference JavaScript Binding

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

API Summary

[Exposed=*]
interface CRStruct {
  constructor(
    object defaults,
    optional object snapshot = {},
    optional boolean allowMissing = false
  );
  undefined merge(optional object delta = {});
  undefined acknowledge();
  undefined garbageCollect(sequence<object> frontiers);
  undefined snapshot();
  sequence<DOMString> keys();
  undefined clear();
  object clone();
  sequence<any> values();
  sequence<sequence<any>> entries();
  undefined addEventListener(
    DOMString type,
    EventListener? listener,
    optional (AddEventListenerOptions or boolean) options = {}
  );
  undefined removeEventListener(
    DOMString type,
    EventListener? listener,
    optional (EventListenerOptions or boolean) options = {}
  );
  object toJSON();
  stringifier DOMString ();
  iterable<DOMString, any>;
};

dictionary CRStructSnapshotEntry {
  required DOMString uuidv7;
  required any value;
  required DOMString predecessor;
  required sequence<DOMString> tombstones;
};

typedef record<DOMString, CRStructSnapshotEntry> CRStructSnapshot;
typedef record<DOMString, CRStructSnapshotEntry> CRStructDelta;
typedef record<DOMString, any> CRStructChange;
typedef record<DOMString, DOMString> CRStructAck;

The binding additionally exposes direct property access through a JavaScript Proxy. Reading struct.key returns a detached copy of the current value for that field. Writing struct.key = value performs a local overwrite, and delete struct.key resets that field to its default value. In allow-missing mode, reading a known field that has not yet been materialized returns undefined.

Only keys present in the constructor's defaults object participate in proxy field access. The binding resolves those known field keys before ordinary reflective property access.

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 CRStructSnapshot and CRStructDelta as defined by the declarations above.

When the constructor's allowMissing argument is true, missing or invalid snapshot entries remain absent instead of being initialized from defaults. Direct writes and valid merges materialize those absent known fields.

When the current snapshot is JSON-compatible, JSON.stringify(struct) serializes the binding through that snapshot. for...of iterates detached [key, value] pairs for the current live fields, and toString() attempts to return the JSON string form of the current snapshot.

Errors

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

DEFAULTS_NOT_CLONEABLE: Thrown when construction receives a defaults object that is not supported by structuredClone.
VALUE_NOT_CLONEABLE: Thrown when a local field overwrite receives a value that is not supported by structuredClone.
VALUE_TYPE_MISMATCH: Thrown when a local field overwrite receives a value whose runtime prototype does not match that field's default value runtime prototype.

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 field mutations and for merges that need to emit a reply delta.
change event: A CustomEvent whose detail is a partial object mapping changed field keys to their new visible values.
ack event: A CustomEvent whose detail is the current per-field acknowledgement frontier produced when acknowledge() is invoked.
snapshot event: A CustomEvent whose detail is the full current snapshot produced when snapshot() is invoked.

Direct property writes, direct property deletes, and clear() MUST dispatch delta event before change event. merge() MAY dispatch delta event, change event, or both, and when both are dispatched the delta event MUST be dispatched first. acknowledge() MUST dispatch ack event, and snapshot() MUST dispatch a snapshot event.

Auxiliary Algorithms

transform a snapshot entry to a state entry

If the candidate value is not a record, then return failure.
If the candidate value does not have its own uuidv7, value, predecessor, and tombstones members, 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 not a valid UUIDv7 identifier, then return failure.
If the candidate value's tombstones member is not a list, then return failure.
Attempt to copy the candidate value's value member with structuredClone. If copying fails, then return failure.
If the copied value's runtime prototype does not equal the supplied default value's runtime prototype, then return failure.
Initialize a new tombstone set from the listed tombstones, retaining only valid UUIDv7 identifier(s).
If the resulting tombstone set contains the candidate uuidv7, then return failure.
If the resulting tombstone set does not contain the candidate predecessor, then return failure.
Return the minted field entry.

transform a state entry to a snapshot entry

Return a new serializable object whose uuidv7, value, predecessor, and tombstones members equal the current live field entry after converting the tombstone set into a list and after detaching the value with structuredClone.

Methods

Constructor

Construct a new binding whose internal state is the result of the core create algorithm applied to the supplied defaults object and optional snapshot. If allowMissing is true, missing or invalid snapshot entries remain absent until first local write or valid merge.

direct property access

Reading struct.key returns the current visible field value copy for that key. Writing struct.key = value runs a one-field local overwrite. Deleting delete struct.key resets that field to its default value. A known unmaterialized key reads as undefined.

merge()

Merge the supplied delta into the internal replica and dispatch any resulting delta event or change event.

acknowledge()

Compute the current per-field acknowledgement frontier and dispatch an ack event.

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.

keys()

Return the current field key(s) as a list of strings.

clear()

Reset every field in the replica back to its default value and dispatch the resulting delta event and change event.

clone()

Return a detached plain object containing the current visible field values keyed by their field names.

values()

Return detached copies of the current visible field values.

entries()

Return detached [key, value] pairs for the current visible fields.

@@iterator

Iterate detached [key, value] pairs for the current visible fields.

toJSON()

Return the same detached structured-clone shape as snapshot. This is the value used by JSON.stringify.

toString()

Attempt to return the JSON string form of the current snapshot. This can fail when field values are not JSON-compatible.

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

Core Algorithms

CRUD

Create

Read

Local Overwrite

Update

Delete

MAGS

Merge

Acknowledge

Garbage Collect

Snapshot

Reference JavaScript Binding

API Summary

Errors

Events

Auxiliary Algorithms

transform a snapshot entry to a state entry

transform a state entry to a snapshot entry

Methods

Constructor

direct property access

merge()

acknowledge()

garbageCollect()

snapshot()

keys()

clear()

clone()

values()

entries()

@@iterator

toJSON()

toString()

addEventListener() and removeEventListener()