lattice_maps - v1.0.0

lattice_maps/or_map

An observed-remove map (OR-Map) CRDT.

Keys are tracked using an OR-Set with add-wins semantics: concurrent update and remove of the same key resolves in favor of the update. Each value is itself a CRDT (specified by CrdtSpec at construction), enabling nested convergent data structures.

Example

import lattice_maps/crdt
import lattice_core/replica_id
import lattice_counters/g_counter
import lattice_maps/or_map

let map = or_map.new(replica_id.new("node-a"), crdt.GCounterSpec)
  |> or_map.update("score", fn(c) {
    let assert crdt.CrdtGCounter(gc) = c
    crdt.CrdtGCounter(g_counter.increment(gc, 10))
  })

Types

ORMap

opaque </>

An OR-Map (observed-remove map) CRDT.

Keys are tracked using an ORSet(String) which provides add-wins semantics: if an update and a remove of the same key happen concurrently on different replicas, the update wins after merging.

Values are stored as the Crdt tagged union so they can be merged per-key using type-specific logic. The crdt_spec field records which CRDT type is used for values, enabling auto-creation of default values for new keys.

pub opaque type ORMap

Values

from_json

</> 
pub fn from_json(
  json_string: String,
) -> Result(ORMap, json.DecodeError)

Decode an ORMap from a JSON string produced by to_json.

Supports both v1 (no remove_bounds) and v2 (with remove_bounds) formats. v1 maps are decoded with empty remove_bounds, meaning no value compaction is possible until new removes are performed.

Returns Error if the string is not valid JSON, does not match the expected format, or contains an unknown crdt_spec string.

get

</> 
pub fn get(map: ORMap, key: String) -> Result(crdt.Crdt, Nil)

Get the CRDT value at key.

Returns Ok(crdt) if the key is active in the OR-Set. Returns Error(Nil) if the key has never been added, or has been removed and not re-added.

keys

</> 
pub fn keys(map: ORMap) -> List(String)

Return the list of all active keys (those present in the OR-Set).

Order is not guaranteed.

merge

</> 
pub fn merge(
  a: ORMap,
  b: ORMap,
) -> Result(ORMap, crdt.MergeError)

Merge two OR-Maps.

The OR-Set key trackers are merged with add-wins semantics: if a key was concurrently updated on one replica and removed on another, the key survives in the merged result. CRDT values are merged per-key using crdt.merge for type-specific convergence.

Returns Error(TypeMismatch(...)) if the two maps have different crdt_spec values (e.g., one holds counters and the other holds sets).

new

</> 
pub fn new(
  replica_id: replica_id.ReplicaId,
  crdt_spec: crdt.CrdtSpec,
) -> ORMap

Create a new empty OR-Map for the given replica with the specified CRDT type.

The crdt_spec determines what type of CRDT is auto-created when update is called on a key that does not yet exist in the map.

prune

</> 
pub fn prune(
  map: ORMap,
  stable_vv: version_vector.VersionVector,
) -> ORMap

Prune tombstones for keys and compact removed values whose removal is causally stable.

Delegates to or_set.prune to remove tombstones from the internal key tracker. Then, for each removed key that has a recorded causal bound, if the pruned version vector dominates that bound, the key’s CRDT value is discarded (the removal is stable and no concurrent re-add can reference the old value).

Only call this with a version vector representing events that have been seen by all replicas (causally stable), otherwise zombie updates might be incorrectly ignored.

remove

</> 
pub fn remove(map: ORMap, key: String) -> ORMap

Remove a key from the OR-Map.

Removes the key from the OR-Set (marking it inactive). The underlying CRDT value is retained until prune determines the removal is causally stable. A causal bound is recorded so prune can later decide when it is safe to discard the value.

to_json

</> 
pub fn to_json(map: ORMap) -> json.Json

Encode an ORMap as a self-describing JSON value.

The nested OR-Set (key_set) and CRDT values are double-encoded as JSON strings so they can be decoded using the existing from_json APIs.

Format: {"type": "or_map", "v": 2, "state": {"replica_id": "...", "crdt_spec": "...", "key_set": "...", "values": [...], "remove_bounds": {...}}}

The encoded value can be restored with from_json.

update

</> 
pub fn update(
  map: ORMap,
  key: String,
  f: fn(crdt.Crdt) -> crdt.Crdt,
) -> ORMap

Apply a function to the CRDT value at key, auto-creating it if absent.

If the key does not exist, a default value is created from crdt_spec and passed to f. The key is added to the OR-Set, marking it active. The return value of f replaces (or sets) the value for that key.

values

</> 
pub fn values(map: ORMap) -> List(crdt.Crdt)

Return the CRDT values for all active keys.

Order is not guaranteed and does not correspond to the order of keys.

✨ Search Document