lattice/two_p_set

A two-phase set (2P-Set) CRDT.

Supports both add and remove, but an element can only be removed once. Once removed (tombstoned), an element can never be re-added. Internally tracks two sets: added and removed. An element is active if it is in added but not in removed. Use ORSet if you need re-add after remove.

Example

import lattice/two_p_set

let set = two_p_set.new()
  |> two_p_set.add("alice")
  |> two_p_set.add("bob")
  |> two_p_set.remove("bob")
two_p_set.contains(set, "alice")  // -> True
two_p_set.contains(set, "bob")    // -> False (tombstoned)

Types

TwoPSet

</>

A 2P-Set (two-phase set) CRDT.

Tracks two monotonically-growing sets: added (elements ever added) and removed (elements ever tombstoned). An element is active only when it is in added but not in removed. Tombstoning is permanent — once removed, an element cannot be re-added to the active set.

pub type TwoPSet(a) {
  TwoPSet(added: set.Set(a), removed: set.Set(a))
}

Constructors

TwoPSet(added: set.Set(a), removed: set.Set(a))

Values

add

</>

pub fn add(tpset: TwoPSet(a), element: a) -> TwoPSet(a)

Add an element to the set.

If the element has already been tombstoned (removed), this call records the element in added but the element will not be considered active because the tombstone takes precedence.

contains

</>

pub fn contains(tpset: TwoPSet(a), element: a) -> Bool

Check if the set currently contains the given element.

Returns True only if element is in added and NOT in removed.

from_json

</>

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

Decode a TwoPSet(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: TwoPSet(el), b: TwoPSet(el)) -> TwoPSet(el)

Merge two 2P-Sets by taking the union of both added sets and both removed sets.

A tombstone on any replica propagates to all replicas after merge. Merge is commutative, associative, and idempotent (a valid CRDT join).

new

</>

pub fn new() -> TwoPSet(a)

Create a new empty 2P-Set.

remove

</>

pub fn remove(tpset: TwoPSet(a), element: a) -> TwoPSet(a)

Remove an element from the set by adding it to the tombstone set.

Once tombstoned, the element is permanently inactive. Removing an element that was never added is also valid and creates a preemptive tombstone.

to_json

</>

pub fn to_json(tpset: TwoPSet(String)) -> json.Json

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

Format: {"type": "two_p_set", "v": 1, "state": {"added": [...], "removed": [...]}}

The encoded value can be restored with from_json.

value

</>

pub fn value(tpset: TwoPSet(a)) -> set.Set(a)

Return the set of all currently active elements.

Active elements are those in added that have not been tombstoned. Equivalent to added ∖ removed.