lattice/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/or_set

let a = or_set.new("node-a") |> or_set.add("item")
let b = or_set.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

</>

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. Removing an element clears all its tags; a concurrent add on another replica will have created a new tag that survives the remove.

pub type ORSet(a) {
  ORSet(
    replica_id: String,
    counter: Int,
    entries: dict.Dict(a, set.Set(Tag)),
  )
}

Constructors

ORSet(
  replica_id: String,
  counter: Int,
  entries: dict.Dict(a, set.Set(Tag)),
)

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.

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. An element is present if it has at least one tag in the merged result. 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: String) -> 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.

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.

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}.

Format: {"type": "or_set", "v": 1, "state": {"replica_id": "...", "counter": N, "entries": {...}}}

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.