lattice_sets/or_set

An observed-remove set (OR-Set) CRDT.

The most flexible set CRDT: supports add, remove, and re-add. Each add creates a unique tag. Remove only deletes tags observed locally, so a concurrent add on another replica survives (add-wins semantics). This makes OR-Set suitable for collaborative data where elements may be toggled.

Example

import lattice_core/replica_id
import lattice_sets/or_set

let a = or_set.new(replica_id.new("node-a")) |> or_set.add("item")
let b = or_set.new(replica_id.new("node-b")) |> or_set.add("item") |> or_set.remove("item")
let merged = or_set.merge(a, b)
or_set.contains(merged, "item")  // -> True (concurrent add wins)

Types

ORSet

opaque </>

An OR-Set (observed-remove set) CRDT.

Each element maps to a set of tags representing the add operations that are currently “live” for that element. An element is present in the set when its tag set is non-empty. Removed tags are retained in tombstones so stale replicas cannot resurrect elements that were already observed and removed elsewhere. A concurrent add on another replica will have created a new tag that survives the remove.

The pruned vector tracks the causal history that has been safely garbage collected (tombstones removed). Use prune to compact tombstones once events are causally stable across all replicas.

pub opaque type ORSet(a)

Tag

opaque </>

A unique tag identifying a specific add operation.

Tags are opaque: users never construct them directly. They are created internally by add and stored in the entries dict so that remove can target exactly the tags observed at remove time, enabling add-wins semantics for concurrent operations.

pub opaque type Tag

Values

add

</>

pub fn add(orset: ORSet(a), element: a) -> ORSet(a)

Add an element to the set.

Creates a fresh unique tag for this add operation using the replica’s monotonically-increasing counter. The element may already be present; in that case a new tag is added alongside existing ones.

contains

</>

pub fn contains(orset: ORSet(a), element: a) -> Bool

Check if the set contains the given element.

Returns True if the element has at least one live tag (i.e., it has been added and not yet removed on this replica, or a concurrent add survived a remove after merging).

from_json

</>

pub fn from_json(
  json_string: String,
) -> Result(ORSet(String), json.DecodeError)

Decode an ORSet(String) from a JSON string produced by to_json.

Supports both v1 (no pruned field) and v2 formats. Returns Error if the string is not valid JSON or does not match the expected format.

merge

</>

pub fn merge(a: ORSet(el), b: ORSet(el)) -> ORSet(el)

Merge two OR-Sets.

For each element, the merged tag set is the union of both sides’ tags, minus merged tombstones, and minus any tags dominated by the merged pruned vector that are not live on the side that pruned them (zombie detection). An element is present if it has at least one surviving tag.

The merged counter is the maximum of both sides, ensuring future adds on either replica generate unique tags.

Merge is commutative, associative, and idempotent (a valid CRDT join).

new

</>

pub fn new(replica_id: replica_id.ReplicaId) -> ORSet(a)

Create a new empty OR-Set for the given replica.

Each replica should have a unique replica_id to ensure that tags generated on different replicas never collide.

prune

</>

pub fn prune(
  orset: ORSet(a),
  stable_vv: version_vector.VersionVector,
) -> ORSet(a)

Prune tombstones based on a stable version vector.

Updates the pruned vector by merging it with stable_vv. Any tombstones dominated by the new pruned vector are removed. This function should only be called with a version vector representing events that have been seen by all replicas (causally stable), otherwise “zombie” updates might be incorrectly ignored.

pruned_vv

</>

pub fn pruned_vv(orset: ORSet(a)) -> version_vector.VersionVector

Return the pruned version vector.

This is the causal horizon below which tombstones have been garbage collected. Useful for determining whether a remove bound is fully dominated (causally stable).

remove

</>

pub fn remove(orset: ORSet(a), element: a) -> ORSet(a)

Remove an element from the set.

Removes all currently observed tags for the element (observed-remove semantics). Any concurrent add on another replica that created a new tag not yet observed here will survive this remove after merging.

remove_with_bound

</>

pub fn remove_with_bound(
  orset: ORSet(a),
  element: a,
) -> #(ORSet(a), version_vector.VersionVector)

Remove an element and return a causal bound for the removed tags.

Behaves identically to remove but also returns a VersionVector representing the maximum counter per replica across all tags that were live for the element. This bound can be compared against a pruned vector to determine when the removal is causally stable.

Returns an empty VersionVector if the element had no live tags.

to_json

</>

pub fn to_json(orset: ORSet(String)) -> json.Json

Encode an ORSet(String) as a self-describing JSON value.

Entries are encoded as a JSON dict where values are arrays of tag objects {"r": replica_id, "c": counter}. Removed tags are encoded separately in tombstones. The pruned version vector tracks garbage-collected causal history.

Format: {"type": "or_set", "v": 2, "state": {"replica_id": "...", "counter": N, "entries": {...}, "tombstones": [...], "pruned": {...}}}

The encoded value can be restored with from_json.

value

</>

pub fn value(orset: ORSet(a)) -> set.Set(a)

Return the set of all elements currently in the OR-Set.

An element is included only when its tag set is non-empty.