lattice_maps/crdt

Typed recursive CRDT composition.

Maps and dispatch share this module to keep the module graph acyclic. A map has one recursive child schema. Text has a concrete grapheme payload; the other parameterized leaves share the application’s payload type.

Types

Crdt

</>

Built-in states, including recursive containers.

Registers, sets, and Sequence share the payload type a. Text always stores String graphemes. Maps hold one recursive child schema, not a schema per key. VersionVector is available through dispatch but has no constructor spec.

Examples

let state: crdt.Crdt(Int) = crdt.CrdtOrMap(
  or_map.new(replica_id.new("A"), crdt.SequenceSpec),
)
crdt.type_name(state) // -> "or_map"

pub type Crdt(a) {
  CrdtGCounter(g_counter.GCounter)
  CrdtPnCounter(pn_counter.PNCounter)
  CrdtLwwRegister(lww_register.LWWRegister(a))
  CrdtMvRegister(mv_register.MVRegister(a))
  CrdtGSet(g_set.GSet(a))
  CrdtTwoPSet(two_p_set.TwoPSet(a))
  CrdtOrSet(or_set.ORSet(a))
  CrdtVersionVector(version_vector.VersionVector)
  CrdtSequence(sequence.Sequence(a))
  CrdtText(text.Text)
  CrdtOrMap(ORMap(a))
  CrdtLwwMap(LWWMap(a))
}

Constructors

```
CrdtGCounter(g_counter.GCounter)
```
```
CrdtPnCounter(pn_counter.PNCounter)
```

CrdtLwwRegister(lww_register.LWWRegister(a))

CrdtMvRegister(mv_register.MVRegister(a))

```
CrdtGSet(g_set.GSet(a))
```
```
CrdtTwoPSet(two_p_set.TwoPSet(a))
```
```
CrdtOrSet(or_set.ORSet(a))
```

CrdtVersionVector(version_vector.VersionVector)

```
CrdtSequence(sequence.Sequence(a))
```
```
CrdtText(text.Text)
```
```
CrdtOrMap(ORMap(a))
```
```
CrdtLwwMap(LWWMap(a))
```

CrdtDelta

</>

State deltas and sparse recursive map changes are distinct.

Use StateDelta for a leaf delta or an explicit full snapshot. Use OrMapChange for a sparse nested ORMap change. LWWMap assignments use complete snapshots, not a separate LWWMap delta type. NoChange carries a schema and avoids treating a configured register default as a universal merge identity.

Examples

let map = or_map.new(replica_id.new("A"), crdt.LwwRegisterSpec(42))
let delta: crdt.CrdtDelta(Int) =
  crdt.OrMapChange(or_map.empty_delta(map))
crdt.matches_delta(delta, crdt.OrMapSpec(crdt.LwwRegisterSpec(42)))
// -> True

pub type CrdtDelta(a) {
  NoChange(CrdtSpec(a))
  StateDelta(Crdt(a))
  OrMapChange(ORMapDelta(a))
}

Constructors

```
NoChange(CrdtSpec(a))
```
```
StateDelta(Crdt(a))
```
```
OrMapChange(ORMapDelta(a))
```

CrdtSpec

</>

A complete child schema, including configured register defaults.

OrMapSpec and LwwMapSpec each describe one child schema recursively. Two maps must agree on the complete schema, including register initial values. A register’s current value can differ from its configured initial value.

Examples

let schema: crdt.CrdtSpec(Int) =
  crdt.OrMapSpec(crdt.LwwMapSpec(crdt.LwwRegisterSpec(42)))
let state = crdt.default_crdt(schema, replica_id.new("A"))
crdt.matches_spec(state, schema) // -> True

pub type CrdtSpec(a) {
  GCounterSpec
  PnCounterSpec
  LwwRegisterSpec(initial_value: a)
  MvRegisterSpec
  GSetSpec
  TwoPSetSpec
  OrSetSpec
  SequenceSpec
  TextSpec
  OrMapSpec(child_spec: CrdtSpec(a))
  LwwMapSpec(child_spec: CrdtSpec(a))
}

Constructors

```
GCounterSpec
```
```
PnCounterSpec
```
```
LwwRegisterSpec(initial_value: a)
```
```
MvRegisterSpec
```
```
GSetSpec
```
```
TwoPSetSpec
```
```
OrSetSpec
```
```
SequenceSpec
```
```
TextSpec
```
```
OrMapSpec(child_spec: CrdtSpec(a))
```
```
LwwMapSpec(child_spec: CrdtSpec(a))
```

EditContext

</>

Use replica_id to author new leaf writes, not to rewrite old authors.

The reserved lattice-map: namespace uses length-framed scope components. OR scopes include key and generation; LWW scopes also include the new write.

Examples

let map = or_map.new(replica_id.new("A"), crdt.LwwRegisterSpec(""))
let assert Ok(#(updated, _)) =
  or_map.update_delta(map, "title", fn(value, context) {
    let assert crdt.CrdtLwwRegister(register) = value
    let written = lww_register.set(
      register, "Ready", lww_register.timestamp(register) + 1,
      context.replica_id,
    )
    Ok(crdt.StateDelta(crdt.CrdtLwwRegister(written)))
  })
or_map.keys(updated) // -> ["title"]

pub type EditContext {
  EditContext(replica_id: replica_id.ReplicaId)
}

Constructors

EditContext(replica_id: replica_id.ReplicaId)

LWWMap

opaque </>

A map of immutable atomic child assignments.

Construct and edit it through lattice_maps/lww_map.

Examples

let map: crdt.LWWMap(Int) =
  lww_map.new(replica_id.new("A"), crdt.SequenceSpec)
lww_map.keys(map) // -> []

pub opaque type LWWMap(a)

MergeError

</>

Invalid schemas and immutable writes are reported rather than replaced.

AtKey identifies the affected nested key. A ConflictingWrite means two different active payloads claim the same immutable modern LWW write identity. An active assignment and tombstone at the same identity select the tombstone.

Examples

let local = replica_id.new("A")
let counter = crdt.default_crdt(crdt.GCounterSpec, local)
let text = crdt.default_crdt(crdt.TextSpec, local)
crdt.merge(counter, text, local)
// -> Error(crdt.TypeMismatch("g_counter", "text"))

pub type MergeError {
  TypeMismatch(expected: String, found: String)
  SchemaMismatch
  AtKey(key: String, cause: MergeError)
  TimestampNotAdvanced(key: String, timestamp: Int, floor: Int)
  ConflictingWrite(key: String, timestamp: Int)
  ClockExhausted(key: String)
  InvalidTimestamp(key: String, timestamp: Int)
}

Constructors

TypeMismatch(expected: String, found: String)

```
SchemaMismatch
```
```
AtKey(key: String, cause: MergeError)
```

TimestampNotAdvanced(key: String, timestamp: Int, floor: Int)

ConflictingWrite(key: String, timestamp: Int)

```
ClockExhausted(key: String)
```

InvalidTimestamp(key: String, timestamp: Int)

ORMap

opaque </>

An observed-remove map with permanent newest-generation floors.

Construct and edit it through lattice_maps/or_map.

Examples

let map: crdt.ORMap(Int) =
  or_map.new(replica_id.new("A"), crdt.LwwRegisterSpec(42))
or_map.keys(map) // -> []

pub opaque type ORMap(a)

ORMapDelta

opaque </>

A sparse, generation-qualified ORMap change.

Construct and apply changes through lattice_maps/or_map.

Examples

let map = or_map.new(replica_id.new("A"), crdt.LwwRegisterSpec(42))
let delta: crdt.ORMapDelta(Int) = or_map.empty_delta(map)
or_map.apply_delta(map, delta) // -> Ok(map)

pub opaque type ORMapDelta(a)

UpdateError

</>

A callback failure is distinct from a composition failure.

Examples

let map = or_map.new(replica_id.new("A"), crdt.TextSpec)
or_map.update_delta(map, "body", fn(_, _) { Error("read-only") })
// -> Error(crdt.CallbackError("read-only"))

pub type UpdateError(e) {
  CallbackError(e)
  CompositionError(MergeError)
}

Constructors

```
CallbackError(e)
```
```
CompositionError(MergeError)
```

Values

apply_delta

</>

pub fn apply_delta(
  value: Crdt(a),
  delta: CrdtDelta(a),
  spec: CrdtSpec(a),
  replica: replica_id.ReplicaId,
) -> Result(Crdt(a), MergeError)

Apply a typed change without trusting a caller-supplied replacement state.

The current state and the delta must both match spec. The returned state is bound to replica; nested ORMap changes retain their generation checks.

Examples

let local = replica_id.new("A")
let before = sequence.new(local)
let assert Ok(#(after, change)) =
  sequence.insert_with_delta(before, 0, 42)
crdt.apply_delta(
  crdt.CrdtSequence(before), crdt.StateDelta(crdt.CrdtSequence(change)),
  crdt.SequenceSpec, local,
)
// -> Ok(crdt.CrdtSequence(after))

bind

</>

pub fn bind(
  value: Crdt(a),
  replica: replica_id.ReplicaId,
) -> Crdt(a)

Bind local editing identity without changing historical IDs or write authors.

Use this after loading or adopting a remote state. It does not author a new LWWRegister write; use lww_register.set for that operation.

Examples

let original = crdt.CrdtLwwRegister(
  lww_register.new("Old write", 1, replica_id.new("A")),
)
crdt.bind(original, replica_id.new("B")) // -> original

default_crdt

</>

pub fn default_crdt(
  spec: CrdtSpec(a),
  replica: replica_id.ReplicaId,
) -> Crdt(a)

Create a valid empty/default child for the configured schema.

Maps start without entries; Sequence and Text start empty. A register uses its configured initial value at timestamp zero.

Examples

let assert crdt.CrdtLwwRegister(register) =
  crdt.default_crdt(crdt.LwwRegisterSpec(42), replica_id.new("A"))
lww_register.value(register) // -> 42

default_delta

</>

pub fn default_delta(
  spec: CrdtSpec(a),
  replica: replica_id.ReplicaId,
) -> CrdtDelta(a)

The delta identity is explicit; configured initial values are not bottoms.

The replica argument does not affect NoChange. It is not an authored write.

Examples

crdt.default_delta(crdt.LwwRegisterSpec(42), replica_id.new("A"))
// -> crdt.NoChange(crdt.LwwRegisterSpec(42))

delta_from_json

</>

pub fn delta_from_json(
  input: String,
) -> Result(CrdtDelta(String), json.DecodeError)

Decode a String-payload dispatch delta.

Examples

let delta = crdt.NoChange(crdt.LwwRegisterSpec(""))
let encoded = delta |> crdt.delta_to_json |> json.to_string
let assert Ok(decoded) = crdt.delta_from_json(encoded)
crdt.is_empty_delta(decoded) // -> True

delta_from_json_with

</>

pub fn delta_from_json_with(
  input: String,
  decoder: decode.Decoder(a),
) -> Result(CrdtDelta(a), json.DecodeError)

Decode a typed dispatch delta.

Apply it with apply_delta and the receiver’s expected schema. Decoding a change does not establish that it belongs to a particular receiving map.

Examples

let local = replica_id.new("A")
let schema = crdt.LwwRegisterSpec(42)
let delta = crdt.NoChange(schema)
let encoded = crdt.delta_to_json_with(delta, json.int) |> json.to_string
let assert Ok(decoded) = crdt.delta_from_json_with(encoded, decode.int)
let state = crdt.default_crdt(schema, local)
crdt.apply_delta(state, decoded, schema, local) // -> Ok(state)

delta_to_json

</>

pub fn delta_to_json(delta: CrdtDelta(String)) -> json.Json

Encode a String-payload dispatch delta.

Examples

let delta = crdt.NoChange(crdt.LwwRegisterSpec(""))
let encoded = delta |> crdt.delta_to_json |> json.to_string
crdt.delta_from_json(encoded) // -> Ok(delta)

delta_to_json_with

</>

pub fn delta_to_json_with(
  delta: CrdtDelta(a),
  encode: fn(a) -> json.Json,
) -> json.Json

Encode a typed dispatch delta without expanding nested ORMap changes.

Examples

let map = or_map.new(replica_id.new("A"), crdt.LwwRegisterSpec(42))
let delta = crdt.OrMapChange(or_map.empty_delta(map))
let encoded = crdt.delta_to_json_with(delta, json.int) |> json.to_string
crdt.delta_from_json_with(encoded, decode.int) // -> Ok(delta)

from_json

</>

pub fn from_json(
  input: String,
) -> Result(Crdt(String), json.DecodeError)

Decode String states, including legacy String leaf codecs (not legacy maps).

Use the map facades’ explicit import adapters for legacy map baselines.

Examples

let state = crdt.default_crdt(crdt.LwwRegisterSpec(""), replica_id.new("A"))
let encoded = state |> crdt.to_json |> json.to_string
crdt.from_json(encoded) // -> Ok(state)

from_json_with

</>

pub fn from_json_with(
  input: String,
  decoder: decode.Decoder(a),
) -> Result(Crdt(a), json.DecodeError)

Decode a generic state; bare Sequence envelopes always dispatch as Sequence.

Bind the result before editing as another writer. A bare Sequence of Strings is not inferred to be Text; only the explicit Text dispatch wrapper is Text.

Examples

let state = crdt.default_crdt(crdt.LwwRegisterSpec(42), replica_id.new("A"))
let encoded = crdt.to_json_with(state, json.int) |> json.to_string
let assert Ok(decoded) = crdt.from_json_with(encoded, decode.int)
crdt.matches_spec(decoded, crdt.LwwRegisterSpec(42)) // -> True

is_empty_delta

</>

pub fn is_empty_delta(value: CrdtDelta(a)) -> Bool

Return whether this delta has no leaf or membership changes.

A StateDelta is not treated as empty, even if its child looks like a default. An ORMap update that returns NoChange still refreshes outer membership.

Examples

crdt.is_empty_delta(crdt.NoChange(crdt.LwwRegisterSpec(42))) // -> True

matches_delta

</>

pub fn matches_delta(
  delta: CrdtDelta(a),
  spec: CrdtSpec(a),
) -> Bool

Validate a delta against the complete child schema.

Examples

let delta = crdt.NoChange(crdt.LwwRegisterSpec(42))
crdt.matches_delta(delta, crdt.LwwRegisterSpec(42)) // -> True
crdt.matches_delta(delta, crdt.LwwRegisterSpec(0)) // -> False

matches_spec

</>

pub fn matches_spec(value: Crdt(a), spec: CrdtSpec(a)) -> Bool

Check complete recursive schema agreement.

Examples

let state = crdt.default_crdt(
  crdt.OrMapSpec(crdt.LwwRegisterSpec(42)), replica_id.new("A"),
)
crdt.matches_spec(state, crdt.OrMapSpec(crdt.LwwRegisterSpec(42)))
// -> True
crdt.matches_spec(state, crdt.OrMapSpec(crdt.LwwRegisterSpec(0)))
// -> False

merge

</>

pub fn merge(
  a: Crdt(a),
  b: Crdt(a),
  replica: replica_id.ReplicaId,
) -> Result(Crdt(a), MergeError)

Merge states with an explicit receiving identity, including incoming-only children.

ORMaps join children within the winning generation. LWWMaps select atomic child assignments instead. Different variants or recursive schemas return Error; a mismatch is never replaced by a default state.

Examples

let a = crdt.default_crdt(
  crdt.OrMapSpec(crdt.TextSpec), replica_id.new("A"),
)
let b = crdt.default_crdt(
  crdt.OrMapSpec(crdt.TextSpec), replica_id.new("B"),
)
let local = replica_id.new("C")
let assert Ok(crdt.CrdtOrMap(merged)) = crdt.merge(a, b, local)
or_map.replica_id(merged) // -> local

merge_deltas

</>

pub fn merge_deltas(
  a: CrdtDelta(a),
  b: CrdtDelta(a),
  spec: CrdtSpec(a),
  replica: replica_id.ReplicaId,
) -> Result(CrdtDelta(a), MergeError)

Batch sparse ORMap changes without expanding them to child snapshots.

A batch that includes an explicit StateDelta snapshot may remain a snapshot.

Examples

let local = replica_id.new("A")
let map = or_map.new(local, crdt.LwwRegisterSpec(42))
let assert Ok(#(_, change)) =
  or_map.update_with_delta(map, "answer", fn(value) { value })
let schema = crdt.OrMapSpec(crdt.LwwRegisterSpec(42))
crdt.merge_deltas(
  crdt.NoChange(schema), crdt.OrMapChange(change), schema, local,
)
// -> Ok(crdt.OrMapChange(change))

spec_from_json_with

</>

pub fn spec_from_json_with(
  input: String,
  decoder: decode.Decoder(a),
) -> Result(CrdtSpec(a), json.DecodeError)

Decode a complete recursive schema.

The payload decoder also decodes configured register initial values.

Examples

let schema = crdt.OrMapSpec(crdt.LwwRegisterSpec(42))
let encoded = crdt.spec_to_json_with(schema, json.int) |> json.to_string
let assert Ok(decoded) = crdt.spec_from_json_with(encoded, decode.int)
decoded == schema // -> True

spec_name

</>

pub fn spec_name(spec: CrdtSpec(a)) -> String

Return a schema’s outer discriminator.

This name alone does not identify a complete recursive schema or its defaults.

Examples

crdt.spec_name(crdt.OrMapSpec(crdt.LwwRegisterSpec(42))) // -> "or_map"

spec_to_json_with

</>

pub fn spec_to_json_with(
  spec: CrdtSpec(a),
  encode: fn(a) -> json.Json,
) -> json.Json

Encode a recursive schema, including the register’s configured initial value.

Examples

let schema = crdt.OrMapSpec(crdt.LwwMapSpec(crdt.LwwRegisterSpec(42)))
let encoded = crdt.spec_to_json_with(schema, json.int) |> json.to_string
crdt.spec_from_json_with(encoded, decode.int) // -> Ok(schema)

to_json

</>

pub fn to_json(value: Crdt(String)) -> json.Json

Encode String payloads, preserving existing standalone leaf formats.

Maps use the modern recursive protocols. Text uses a distinct dispatch wrapper around its unchanged standalone Sequence envelope.

Examples

let state = crdt.CrdtGSet(g_set.new() |> g_set.add("ready"))
let encoded = state |> crdt.to_json |> json.to_string
crdt.from_json(encoded) // -> Ok(state)

to_json_with

</>

pub fn to_json_with(
  value: Crdt(a),
  encode: fn(a) -> json.Json,
) -> json.Json

Encode generic payloads. Text has a distinct dispatch envelope.

The encoder is used at every generic payload position, including map schema defaults. Generic ORSet values use their value/tag-entry protocol.

Examples

let state = crdt.default_crdt(
  crdt.OrMapSpec(crdt.LwwRegisterSpec(42)), replica_id.new("A"),
)
let encoded = crdt.to_json_with(state, json.int) |> json.to_string
crdt.from_json_with(encoded, decode.int) // -> Ok(state)

type_name

</>

pub fn type_name(value: Crdt(a)) -> String

Return the dispatch discriminator.

Examples

let state = crdt.default_crdt(crdt.TextSpec, replica_id.new("A"))
crdt.type_name(state) // -> "text"