lattice_sequence/sequence

A generic sequence CRDT using stable item IDs and YATA-style origins.

Each live item is stored with a stable internal ID plus left and right origins for deterministic ordering. Deletes are represented as tombstones that record the delete’s op ID; values returns only non-deleted items.

The public editing API exposes index-based insert, delete, and move operations while resolving stable item IDs internally, so callers do not need to construct or manage item identifiers. Moves preserve item identity and converge with single-winner semantics for concurrent moves of the same item.

Replica identity

A sequence carries the replica ID it mints item IDs under. Both merge and its alias merge_as require that identity explicitly: merge(state, incoming, local_replica). Operand order does not select the output identity. Deltas and decoded snapshots retain their sender’s identity; merge them under your local identity before editing. Independent writers must use distinct replica IDs.

Compaction

Long-lived sequences never shrink on their own: every delete leaves a tombstone and every item carries origins. compact takes a stability frontier — a VersionVector meaning “everything causally at or below this is stable; no in-flight or future op references it” — and rewrites the stable region: stable tombstones are dropped, runs of adjacent stable items from the same replica with sequential counters are merged into compact blocks, and origins of stable items are discarded. Items above the frontier keep their full YATA representation.

Every dropped ID gets a forwarding entry pointing at its retained neighbors, so anchors and rebased operations that still hold the ID can resolve to the gap it left behind. The forwarding map and the applied frontier travel with the state. Deriving a correct frontier is the host’s job (e.g. from a global sequencer’s acknowledgement floor); the frontier must be a causal cut over the ops applied to the sequence.

Example

import lattice_core/replica_id
import lattice_sequence/sequence

let assert Ok(list) =
  sequence.insert_many(sequence.new(replica_id.new("node-a")), 0, [
    "hello", "world",
  ])
let assert Ok(list) = sequence.move(list, 0, 1)

sequence.values(list)  // -> ["world", "hello"]

Types

Anchor

opaque </>

A stable position between items (positions 0..length inclusive).

Anchors are created from a visible index with anchor_at and resolved back to a current index with resolve after any sequence of local edits and merges. They live outside the CRDT state: creating and resolving anchors never mutates the sequence.

pub opaque type Anchor

AnchorError

</>

An error returned when an anchor cannot be created or resolved.

pub type AnchorError {
  AnchorIndexOutOfBounds(index: Int, length: Int)
  UnknownAnchorTarget
}

Constructors

AnchorIndexOutOfBounds(index: Int, length: Int)

```
UnknownAnchorTarget
```
The anchor references an item this replica cannot locate: either it was created remotely and not merged yet, or it was compacted away and its forwarding entry has expired. Treat this as “re-anchor”.

Bias

</>

Which side of its gap an anchor sticks to when content is inserted exactly at the anchor position.

pub type Bias {
  Before
  After
}

Constructors

```
Before
```
Attach to the item after the gap: inserts at the gap push the anchor right, so it stays glued to its item.
```
After
```
Attach to the item before the gap: inserts at the gap land after the anchor, so it stays put.

DeleteError

</>

An error returned when a delete cannot be applied.

pub type DeleteError {
  DeleteIndexOutOfBounds(index: Int, length: Int)
}

Constructors

DeleteIndexOutOfBounds(index: Int, length: Int)

ForwardingMap

opaque </>

The forwarding entries emitted by one compact pass.

Each entry maps a dropped item ID to the gap it left behind. The library keeps the cumulative map inside the sequence for anchor resolution and origin translation; retention is the host’s policy — keep the map returned by each compact round and expire old rounds with remove_forwardings.

pub opaque type ForwardingMap

InsertError

</>

An error returned when an insert cannot be applied.

pub type InsertError {
  IndexOutOfBounds(index: Int, length: Int)
}

Constructors

IndexOutOfBounds(index: Int, length: Int)

ItemId

opaque </>

pub opaque type ItemId

MoveError

</>

An error returned when a move cannot be applied.

pub type MoveError {
  MoveFromIndexOutOfBounds(index: Int, length: Int)
  MoveToIndexOutOfBounds(index: Int, length_after_removal: Int)
}

Constructors

MoveFromIndexOutOfBounds(index: Int, length: Int)

MoveToIndexOutOfBounds(index: Int, length_after_removal: Int)

Sequence

opaque </>

pub opaque type Sequence(a)

TranslateError

</>

An error returned when a delta’s origins cannot be translated onto a compacted state.

pub type TranslateError {
  UnknownOriginTarget
}

Constructors

```
UnknownOriginTarget
```
An origin references an ID that is neither present nor forwarded — its forwarding entry has expired. The host must degrade the op (e.g. re-insert by position) or drop it.

Values

anchor_at

</>

pub fn anchor_at(
  sequence: Sequence(a),
  index: Int,
  bias: Bias,
) -> Result(Anchor, AnchorError)

Create an anchor at the gap before the visible item at index.

Before bias binds the anchor to the item at index; After bias binds it to the item at index - 1. Boundary positions with no item on the chosen side degrade to the start / end sentinels.

Valid positions are 0 <= index <= length.

anchor_from_json

</>

pub fn anchor_from_json(
  json_string: String,
) -> Result(Anchor, json.DecodeError)

Decode an anchor from a JSON string produced by anchor_to_json.

anchor_to_json

</>

pub fn anchor_to_json(anchor: Anchor) -> json.Json

Encode an anchor as a self-describing JSON value.

Produces an envelope with type, v (schema version), and anchor, so anchors can travel between replicas (e.g. shared cursors).

bind

</>

pub fn bind(
  sequence: Sequence(a),
  replica: replica_id.ReplicaId,
) -> Sequence(a)

Select the identity for subsequent edits without rebuilding the sequence.

Preserves item IDs, counters, stored order, and compaction metadata. Independent writers must use distinct replica IDs.

Examples

let local = replica_id.new("B")
sequence.new(replica_id.new("A"))
|> sequence.bind(local)
|> sequence.replica_id()
// -> local

compact

</>

pub fn compact(
  sequence: Sequence(a),
  stable: version_vector.VersionVector,
) -> #(Sequence(a), ForwardingMap)

Compact everything at or below a stability frontier.

stable must describe a causal cut the host knows no in-flight or future op can reference (e.g. the version vector accumulated by replaying ops up to a global sequencer’s acknowledgement floor). For the stable region the pass drops tombstones, merges runs of adjacent same-replica items with sequential counters into blocks, and strips origins and move slots.

Returns the compacted sequence and the forwarding entries emitted by this pass (one per dropped ID). The cumulative forwarding map is also carried in the sequence; hosts bound its growth with remove_forwardings.

Compacting at the current frontier, at an older one, or at one concurrent with it is a no-op — frontiers only advance.

Moved items remain live so their move records and insertion origins survive. The pass can still stabilize unrelated items and reclaim tombstones, while retaining any target-gap boundaries referenced by a live move.

delete

</>

pub fn delete(
  sequence: Sequence(a),
  index: Int,
) -> Result(Sequence(a), DeleteError)

Delete the value at the visible item index.

Returns DeleteIndexOutOfBounds when index is outside [0, length).

delete_with_delta

</>

pub fn delete_with_delta(
  sequence: Sequence(a),
  index: Int,
) -> Result(#(Sequence(a), Sequence(a)), DeleteError)

Delete a value and return both the updated sequence and deletion delta.

Returns DeleteIndexOutOfBounds when index is outside [0, length).

Deletes mint an op ID (bumping this replica’s counter) so a compaction frontier can distinguish acknowledged deletes from in-flight ones.

Apply the delta with merge(peer_state, delta, peer_replica).

end_anchor

</>

pub fn end_anchor() -> Anchor

Create an anchor at the end of the sequence. Always resolves to the current visible length, tracking growth.

forwarding_size

</>

pub fn forwarding_size(map: ForwardingMap) -> Int

The number of entries in a forwarding map.

from_json

</>

pub fn from_json(
  json_string: String,
  value_decoder: decode.Decoder(a),
) -> Result(Sequence(a), json.DecodeError)

Decode a sequence CRDT from a JSON string produced by to_json.

Returns Ok(Sequence) on success, or Error(json.DecodeError) if the input is not a valid sequence JSON envelope. Live items are reordered deterministically from their stable origins before the Sequence is returned. If retained IDs or the compaction frontier exceed the encoded allocation counter, the counter is raised to that high-water mark. This prevents ID reuse when the snapshot is edited under any replica identity.

frontier

</>

pub fn frontier(
  sequence: Sequence(a),
) -> version_vector.VersionVector

The stability frontier this sequence was last compacted at.

Empty until the first compact call. Carried in the state so merging can tell which side is compacted further.

insert

</>

pub fn insert(
  sequence: Sequence(a),
  index: Int,
  value: a,
) -> Result(Sequence(a), InsertError)

Insert a value at the visible item index.

Returns IndexOutOfBounds when index is outside [0, length].

insert_many

</>

pub fn insert_many(
  sequence: Sequence(a),
  index: Int,
  values: List(a),
) -> Result(Sequence(a), InsertError)

Insert several values at consecutive visible indices starting at index.

values are placed in order — the first at index, the next at index + 1, and so on — exactly as looping insert would, but the whole run is spliced in a single pass and reported as one delta. Returns IndexOutOfBounds when index is outside [0, length].

insert_many_with_delta

</>

pub fn insert_many_with_delta(
  sequence: Sequence(a),
  index: Int,
  values: List(a),
) -> Result(#(Sequence(a), Sequence(a)), InsertError)

Insert several values and return both the updated sequence and the merged insertion delta covering every new item.

Returns IndexOutOfBounds when index is outside [0, length].

Each new item’s left origin is the previous new item (the first pins to the visible left neighbor) and every item shares the same right origin — the left neighbor’s canonical successor — so the run integrates contiguously on every replica. When the state holds no live move record, stored order is already the canonical order, so the run is spliced directly in place rather than re-deriving the whole order; otherwise it falls back to a full rebuild.

Apply the delta with merge(peer_state, delta, peer_replica).

insert_with_delta

</>

pub fn insert_with_delta(
  sequence: Sequence(a),
  index: Int,
  value: a,
) -> Result(#(Sequence(a), Sequence(a)), InsertError)

Insert a value and return both the updated sequence and insertion delta.

Returns IndexOutOfBounds when index is outside [0, length]. Apply the delta with merge(peer_state, delta, peer_replica).

length

</>

pub fn length(sequence: Sequence(a)) -> Int

Return the count of visible values.

merge

</>

pub fn merge(
  a: Sequence(a),
  b: Sequence(a),
  replica: replica_id.ReplicaId,
) -> Sequence(a)

Merge two sequence CRDT states.

Items are joined by their stable IDs. Concurrent deletes are preserved by keeping the winning delete op, and the merged item set is deterministically reordered using each item’s left and right origins. Stable blocks form a fixed skeleton that live items are ordered around.

States compacted at different frontiers merge as long as one frontier dominates the other (with a global sequencer, floors are totally ordered so this always holds). An item absent from the further-compacted side and covered by its frontier is treated as compacted away and stays dropped.

Pass the identity this replica edits under. The output uses replica regardless of operand order, and its counter is the maximum of both inputs. Independent writers must use distinct identities.

Examples

let local = replica_id.new("A")
sequence.merge(sequence.new(local), sequence.new(replica_id.new("B")), local)
|> sequence.replica_id()
// -> local

merge_as

</>

pub fn merge_as(
  a: Sequence(a),
  b: Sequence(a),
  replica: replica_id.ReplicaId,
) -> Sequence(a)

Alias for merge, with the same explicit output replica identity.

Examples

sequence.merge_as(a, b, local) == sequence.merge(a, b, local)
// -> True

move

</>

pub fn move(
  sequence: Sequence(a),
  from_index: Int,
  to_index: Int,
) -> Result(Sequence(a), MoveError)

Move a visible item to another visible index.

The to_index is interpreted after removing the item from from_index.

Returns a MoveError when either index is out of bounds.

move_with_delta

</>

pub fn move_with_delta(
  sequence: Sequence(a),
  from_index: Int,
  to_index: Int,
) -> Result(#(Sequence(a), Sequence(a)), MoveError)

Move a visible item and return both the updated sequence and move delta.

The to_index is interpreted after removing the item from from_index.

Returns a MoveError when either index is out of bounds. Apply the delta with merge(peer_state, delta, peer_replica).

new

</>

pub fn new(replica_id: replica_id.ReplicaId) -> Sequence(a)

Create an empty sequence for a replica.

remove_forwardings

</>

pub fn remove_forwardings(
  sequence: Sequence(a),
  map: ForwardingMap,
) -> Sequence(a)

Remove previously emitted forwarding entries from the sequence.

Forwardings are bounded by the host’s retention policy: keep the map returned by each compact round and expire old rounds by passing them here. Anchors and deltas referencing removed entries hard-fail (UnknownAnchorTarget / UnknownOriginTarget) and must re-anchor or resync.

replica_id

</>

pub fn replica_id(sequence: Sequence(a)) -> replica_id.ReplicaId

Return the replica identity used for subsequent local edits.

This accessor does not change the state. Use bind to adopt a snapshot without merging, or merge when combining state or deltas.

Examples

let replica = replica_id.new("A")
sequence.replica_id(sequence.new(replica)) == replica
// -> True

resolve

</>

pub fn resolve(
  sequence: Sequence(a),
  anchor: Anchor,
) -> Result(Int, AnchorError)

Resolve an anchor to a current visible index in [0, length].

Anchors on deleted items still resolve: both biases collapse to the gap where the item used to be. Anchors follow moved items.

Anchors to compacted items resolve through the forwarding map to the gap the item left behind — semantically the same as tombstone collapse.

Returns Error(UnknownAnchorTarget) when the anchor references an item this replica has never seen (created remotely and not yet merged), or one that was compacted away and whose forwarding entry has since been removed by the host’s retention policy. Either way the anchor is unusable and the holder should re-anchor.

start_anchor

</>

pub fn start_anchor() -> Anchor

Create an anchor at the start of the sequence. Always resolves to 0.

to_json

</>

pub fn to_json(
  sequence: Sequence(a),
  encode_value: fn(a) -> json.Json,
) -> json.Json

Encode a sequence CRDT as a self-describing JSON value.

Produces an envelope with type, v (schema version), and state. The state includes this replica ID, local counter, applied compaction frontier, forwarding entries, and every segment: compact blocks of stable values and full items including tombstones.

translate_origins

</>

pub fn translate_origins(
  delta: Sequence(a),
  onto: Sequence(a),
) -> Result(Sequence(a), TranslateError)

Translate a delta’s origins onto a compacted state.

Rebase support for evicted clients: origins (including move origins) referencing compacted IDs are rewritten through onto’s forwarding map to the gap the ID left behind. Items whose own ID was compacted away are dropped from the delta — the op is already settled. Returns Error(UnknownOriginTarget) when an origin is neither present, part of the delta itself, nor forwarded (the forwarding expired); the host must degrade the op to a positional edit or discard it.

values

</>

pub fn values(sequence: Sequence(a)) -> List(a)

Return all visible values in sequence order.