Snapshot

Runtime

Consumer

Create

1. Let replica be a new runtime state whose values and relations are empty maps and whose tombstones and predecessors are empty sets.
2. If the supplied snapshot is not a record, then return replica.
3. If the snapshot exposes a tombstones member and that member is a list:
   1. For each listed tombstone, if it is a valid UUIDv7 identifier and is not already retained, add it to replica's tombstone set.
4. If the snapshot does not expose a values member, or that member is not a list, then return replica.
5. For each listed candidate value entry:
   1. If the candidate is not a record, then continue.
   2. If replica already tombstones the candidate uuidv7, then continue.
   3. Run the transform a snapshot value entry to a state entry algorithm. If it returns failure, continue.
   4. Let current be the presently visible local winner for the same map key, if one exists.
   5. If current exists, has the same uuidv7 as the candidate, and its predecessor is lexicographically greater than or equal to the candidate's predecessor, then continue.
   6. If current exists, has a different uuidv7, is not the candidate's direct predecessor, and its uuidv7 is lexicographically greater than or equal to the candidate's uuidv7, then continue.
   7. If current exists:
      1. Remove current's uuidv7 from the relations index.
      2. Remove current's predecessor from the predecessors set.
   8. Store the candidate as the winning entry for its map key.
   9. Map the candidate uuidv7 back to its key in the relations index.
   10. Record the candidate predecessor in the predecessors set.
6. Return replica.

Read

1. Let entry be the current visible entry for the supplied map key.
2. If entry does not exist, then return undefined.
3. Return a detached structured clone of entry's map value.

Update

1. If the supplied key is not a non-empty string, then return failure.
2. Attempt to detach the supplied value with structuredClone. If that fails, return failure.
3. Let old be the current visible entry for the supplied key, if one exists.
4. Let predecessor be:
   1. old's winning uuidv7, if old exists.
   2. Otherwise a newly minted UUIDv7 identifier.
5. Let winner be a new state entry whose uuidv7 is a newly minted UUIDv7 identifier, whose value stores the key and detached payload, and whose predecessor is predecessor.
6. If old exists:
   1. Remove old's winning identifier from the relations index.
   2. Remove old's predecessor from the predecessors set.
7. Store winner as the current visible entry for the key.
8. Map winner's uuidv7 to the key in the relations index.
9. Record predecessor in the predecessors set.
10. Retain predecessor as a tombstone entry.
11. Return:
    1. a delta whose values list contains the new winning snapshot value entry and whose tombstones list contains predecessor; and
    2. a CRMapChange mapping the key to a detached clone of the new visible value.

Delete

1. If a key was supplied:
   1. Let entry be the current visible entry for that key.
   2. If entry does not exist, then return failure.
   3. Retain entry's winning uuidv7 as a tombstone entry.
   4. Remove the key from the visible values map.
   5. Remove entry's winning identifier from the relations index.
   6. Remove entry's predecessor from the predecessors set.
   7. Return:
      1. a delta whose tombstones list contains only the deleted winner's UUIDv7; and
      2. a CRMapChange mapping that key to undefined.
2. Otherwise, if the replica has no visible values, then return failure.
3. Let delta be a new delta whose tombstones list is empty.
4. Let change be an empty CRMapChange.
5. For each visible entry currently stored by the replica:
   1. Retain the entry's winning uuidv7 as a tombstone entry.
   2. Append that UUIDv7 to delta's tombstones list.
   3. Set change[key] to undefined.
6. Clear the visible values map, the relations index, and the predecessors set.
7. Return delta together with change.

Merge

1. If the supplied delta is not a record, then return failure.
2. Let change be an empty CRMapChange.
3. Let reply be an empty delta.
4. Let hasChange be false.
5. Let hasReply be false.
6. If the incoming delta exposes a tombstones member and that member is a list:
   1. For each listed tombstone:
      1. If it is not a valid UUIDv7 identifier, or is already locally retained, then continue.
      2. Retain it as a local tombstone entry.
      3. Let liveKey be the key presently mapped from that tombstone in the relations index.
      4. If liveKey does not exist, then continue.
      5. Let current be the visible entry for liveKey.
      6. If current does not exist, or its winning uuidv7 is not equal to the tombstone being processed:
         1. Remove the stale relation mapping for that tombstone.
         2. Continue.
      7. Remove current from the visible values map.
      8. Remove the tombstoned winner from the relations index.
      9. Remove current's predecessor from the predecessors set.
      10. Set change[liveKey] to undefined.
      11. Set hasChange to true.
7. If the incoming delta does not expose a values member, or that member is not a list:
   1. If hasChange is true, return change together with reply.
   2. Otherwise return failure.
8. For each listed candidate value entry:
   1. If the candidate is not a record, then continue.
   2. If the replica already tombstones the candidate uuidv7, then continue.
   3. Run the transform a snapshot value entry to a state entry algorithm. If it returns failure, continue.
   4. Let current be the current visible winner for the same map key, if one exists.
   5. If current does not exist:
      1. Adopt the candidate as the visible winner for that key.
      2. Add the candidate uuidv7 to the relations index.
      3. Add the candidate predecessor to the predecessors set.
      4. Retain the candidate predecessor as a tombstone.
      5. Set change[key] to a detached clone of the candidate's visible value.
      6. Set hasChange to true.
      7. Continue.
   6. If current's uuidv7 equals the candidate's uuidv7:
      1. If current's predecessor is lexicographically less than the candidate predecessor:
         1. Remove current's old predecessor from the predecessors set.
         2. Replace current's visible value with the candidate value.
         3. Replace current's predecessor with the candidate predecessor.
         4. Add the candidate predecessor to the predecessors set.
         5. Retain the candidate predecessor as a tombstone.
         6. Set change[key] to a detached clone of the new visible value.
         7. Set hasChange to true.
      2. Otherwise, if the predecessor is equal and the visible values are identical, then continue.
      3. Otherwise:
         1. Append the current local winner to reply's values list.
         2. Set hasReply to true.
      4. Continue.
   7. If the candidate is a direct descendant of the current winner, or the current winner is already tombstoned, or the candidate uuidv7 is lexicographically greater than the current winner's uuidv7:
      1. Retain the candidate predecessor as a tombstone.
      2. Retain the current winner's UUIDv7 as a tombstone.
      3. Remove the current winner's identifier from the relations index.
      4. Remove the current winner's predecessor from the predecessors set.
      5. Adopt the candidate as the visible winner for the key.
      6. Map the candidate uuidv7 to the key in the relations index.
      7. Add the candidate predecessor to the predecessors set.
      8. Set change[key] to a detached clone of the candidate value.
      9. Set hasChange to true.
      10. Continue.
   8. Otherwise:
      1. Retain the losing candidate's UUIDv7 as a local tombstone.
      2. Append that UUIDv7 to reply's tombstones list.
      3. Append the current local winner to reply's values list.
      4. Set hasReply to true.
9. If neither hasChange nor hasReply is true, then return failure.
10. Return change together with reply.

Acknowledge

1. Let largest be the empty string ''.
2. For each retained tombstone:
   1. If it is not a valid UUIDv7 identifier, then continue.
   2. If it is lexicographically less than largest, then continue.
   3. Set largest to that tombstone.
3. Return largest as the current acknowledgement frontier.

Garbage Collect

1. If the supplied list of acknowledgement frontiers is empty, then return.
2. Let smallest be the empty string ''.
3. For each supplied frontier:
   1. If it is not a valid UUIDv7 identifier, then continue.
   2. If smallest is not empty and is lexicographically less than or equal to the frontier, then continue.
   3. Set smallest to that frontier.
4. If smallest is still the empty string, then return.
5. For each retained tombstone:
   1. If it is lexicographically greater than smallest, then continue.
   2. If it is still present in the predecessors set, then continue.
   3. Remove it from the tombstone set.

This algorithm is only safe when the caller supplies 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

1. Let out be a new snapshot whose values list is empty and whose tombstones list contains all retained tombstones.
2. For each visible state entry, run the transform a state entry to a snapshot value entry algorithm and append the result to out's values list.
3. Return out.

API Summary

callback CRMapForEachCallback = undefined (any value, DOMString key, CRMap map);

[Exposed=*]
interface CRMap {
  constructor(optional object snapshot = {});
  readonly attribute unsigned long size;
  any get(DOMString key);
  boolean has(DOMString key);
  undefined set(DOMString key, any value);
  undefined delete(DOMString key);
  undefined clear();
  undefined merge(optional object delta = {});
  undefined acknowledge();
  undefined garbageCollect(sequence<DOMString> frontiers);
  undefined snapshot();
  sequence<DOMString> keys();
  sequence<any> values();
  sequence<sequence<any>> entries();
  undefined forEach(CRMapForEachCallback callback, optional any thisArg);
  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 CRMapKeyValue {
  required DOMString key;
  required any value;
};

dictionary CRMapSnapshotValueEntry {
  required DOMString uuidv7;
  required CRMapKeyValue value;
  required DOMString predecessor;
};

dictionary CRMapSnapshot {
  required sequence<CRMapSnapshotValueEntry> values;
  required sequence<DOMString> tombstones;
};

dictionary CRMapDelta {
  sequence<CRMapSnapshotValueEntry> values;
  sequence<DOMString> tombstones;
};

typedef record<DOMString, any> CRMapChange;
typedef DOMString CRMapAck;
        

The constructor and merge() method 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 CRMapSnapshot and CRMapDelta as defined earlier.

size returns the current number of visible members. get(), values(), entries(), forEach(), and for...of expose detached structured clones rather than mutable references into replica state.

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

Errors

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

INVALID_KEY

Thrown when a local keyed mutation receives a key that is not a non-empty string.

VALUE_NOT_CLONEABLE

Thrown when a local set() receives a value that is not supported by structuredClone.

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, merges, acknowledgement emission, and snapshot emission 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 writes and for merges that emit a non-empty reply delta.

change event

A CustomEvent whose detail is a sparse visible patch mapping changed member identifiers to their new visible values, with deleted keys mapped to undefined.

ack event

A CustomEvent whose detail is the current acknowledgement frontier produced when acknowledge() observes at least one retained valid tombstone.

snapshot event

A CustomEvent whose detail is the full current snapshot produced when snapshot() is invoked.

set(), delete(), 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 an ack event only when the computed frontier is non-empty, and snapshot() MUST dispatch a snapshot event.

Auxiliary Algorithms

Methods