lattice_sets/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_sets/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

opaque </>

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 opaque type TwoPSet(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.

See add_with_delta for the delta-state variant that also returns a small payload suitable for incremental sync (e.g. over websockets).

add_with_delta

</>

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

Add an element and return both the new state and a delta.

The returned delta is a TwoPSet whose added set contains only the inserted element and whose removed set is empty. Merging the delta into a remote via merge (union of both halves) produces the same result as merging the full new state.

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.

See remove_with_delta for the delta-state variant.

remove_with_delta

</>

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

Remove an element and return both the new state and a delta.

The returned delta is a TwoPSet whose removed set contains only the tombstoned element and whose added set is empty. Merging the delta into a remote via merge propagates the tombstone, deactivating the element in the remote replica regardless of its prior state.

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.