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
Observable value changes between two OR-Sets.
Diff values are based on value, not internal tags. Re-adding an element
that was already observable does not appear in added; removing one tag
while another live tag remains does not appear in removed.
pub type Diff(a) {
Diff(added: set.Set(a), removed: set.Set(a))
}Constructors
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)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 TagValues
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.
See add_with_delta for the delta-state variant that also returns a
small payload suitable for incremental sync (e.g. over websockets).
pub fn add_with_delta(
orset: ORSet(a),
element: a,
) -> #(ORSet(a), ORSet(a))Add an element and return both the new state and a delta.
The returned delta is an ORSet whose entries contains only the newly
inserted element with its single fresh tag, with empty tombstones and
pruned vector. Merging the delta into a remote via merge adds the new
tag to the remote’s entry for element (creating it if necessary),
producing the same observable result as merging the full new state.
The delta carries this replica’s replica_id and the post-mutation
counter, so successive deltas remain causally distinguishable.
pub fn contains(orset: ORSet(a), element: a) -> BoolCheck 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).
pub fn diff(before: ORSet(a), after: ORSet(a)) -> Diff(a)Compare the observable values of two OR-Sets.
added contains values present in after but not before.
removed contains values present in before but not after.
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.
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).
pub fn merge_with_diff(
local: ORSet(a),
remote: ORSet(a),
) -> #(ORSet(a), Diff(a))Merge two OR-Sets and report observable value changes from local.
The returned OR-Set is exactly the same as merge(local, remote). The
diff compares value(local) with value(merged), so it reports only
externally visible additions and removals.
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.
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.
pub fn pruned_vv(orset: ORSet(a)) -> version_vector.VersionVectorReturn 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).
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.
See remove_with_delta for the delta-state variant.
pub fn remove_all(orset: ORSet(a), elements: List(a)) -> ORSet(a)Remove each element in elements using observed-remove semantics.
Missing elements are ignored, matching remove.
pub fn remove_where(
orset: ORSet(a),
predicate: fn(a) -> Bool,
) -> ORSet(a)Remove every currently observable element matching predicate.
The predicate is evaluated against value(orset), then each matching value
is removed with normal observed-remove semantics.
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.
pub fn remove_with_delta(
orset: ORSet(a),
element: a,
) -> #(ORSet(a), ORSet(a))Remove an element and return both the new state and a delta.
The returned delta is an ORSet whose tombstones contains exactly the
tags that were live for element at the time of the remove, with empty
entries and pruned vector. Merging the delta into a remote via merge
retracts those tags from the remote’s entry for element. Tags that the
remote has but the delta source had not yet observed (concurrent adds)
survive — preserving the add-wins property of OR-Set.
pub fn to_json(orset: ORSet(String)) -> json.JsonEncode 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.