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. merge is order-independent in its item set, order, and counter, but not in that id: the result keeps the FIRST argument’s. Always call it as merge(self, other), or use merge_as to state the local identity explicitly. Deltas are ordinary Sequence values stamped with the minting replica, so passing an incoming delta first would hand the local state the sender’s identity and make later local edits mint colliding item 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 list =
  sequence.new(replica_id.new("node-a"))
  |> sequence.insert(0, "hello")
  |> sequence.insert(1, "world")
  |> sequence.move(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,
) -> Anchor

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.

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

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.

Moves disable the pass entirely

A state holding ANY move record is left unchanged, even when every move op is already covered by stable. The guard is load-bearing for convergence, not conservatism, and it has to be this blunt:

Compaction is safe only because rebuild is frontier-invariant: a covered element is pinned at its stored position, and pinning it agrees with integrating it from origins, so raising the frontier cannot reorder anything. A mover is the one element that breaks this. It is never pinned — its stored position is post-move, but re-integrating it from its INSERT origins yields its PRE-move position — so the two disagree, and raising the frontier changes which elements are pinned around it and therefore where it lands.

That makes the frontier advance itself unsafe, not the element rewriting: a compact that changes NO element and only advances frontier already falsifies merge_commutes_with_compaction_for_deltas_above_frontier when a move record exists. So there is nothing to relax here — no subset of the pass is safe while a mover is present.

Nothing clears a move record — not a local op, and not merging a peer that stabilized the item before it heard about the move, because stable_or_live keeps a moved item live and supersedes the block slot. So a replica that performs or receives a move stops reclaiming for good, and its tombstones and origins grow without bound. Representing a settled move without discarding the geometry concurrent inserts rely on needs a redesign; tracked in issue #98.

delete

</>

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

Delete the value at the visible item index.

Panics with DeleteIndexOutOfBounds when index is outside [0, length). Use try_delete_with_delta to handle an untrusted index without crashing.

delete_with_delta

</>

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

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

Panics with DeleteIndexOutOfBounds when index is outside [0, length). Use try_delete_with_delta to handle an untrusted index without crashing.

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.

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,
) -> Sequence(a)

Insert a value at the visible item index.

Panics with IndexOutOfBounds when index is outside [0, length]. Use try_insert_with_delta to handle an untrusted index without crashing.

insert_many

</>

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

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. Panics with IndexOutOfBounds when index is outside [0, length]. Use try_insert_many_with_delta to handle an untrusted index without crashing.

insert_many_with_delta

</>

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

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

Panics with IndexOutOfBounds when index is outside [0, length]. Use try_insert_many_with_delta to handle an untrusted index without crashing.

insert_with_delta

</>

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

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

Panics with IndexOutOfBounds when index is outside [0, length]. Use try_insert_with_delta to handle an untrusted index without crashing.

length

</>

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

Return the count of visible values.

merge

</>

pub fn merge(a: Sequence(a), b: Sequence(a)) -> 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.

Argument order matters

The merged item set, order, and counter are order-independent, but the replica identity is NOT: the result adopts a’s replica id. Call this as merge(self, other) — local state first — or the result takes the remote’s identity and every later local edit mints item IDs under a replica id that is still minting its own. Those IDs collide silently and merge conflates two distinct items, dropping one.

Deltas returned by the *_with_delta functions are ordinary Sequence values stamped with the minting replica, so merge(incoming_delta, state) is the easy way to get this wrong. Use merge_as when the argument order is not statically obvious — it takes the local identity explicitly and is order-independent in every field.

merge_as

</>

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

Merge two sequence CRDT states under an explicitly named replica identity.

Same as merge, except the merged state is stamped with replica instead of inheriting the first argument’s id. That makes the call fully order-independent — merge_as(a, b, replica) equals merge_as(b, a, replica) in every field — so applying an incoming delta cannot re-mint local edits under the sender’s replica id, whichever side it is passed on.

Pass the identity this replica edits under. The merged counter is the max of both sides, so it still dominates every ID replica has minted here.

move

</>

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

Move a visible item to another visible index.

The to_index is interpreted after removing the item from from_index.

Panics with a MoveError when either index is out of bounds. Use try_move_with_delta to handle untrusted indices without crashing.

move_with_delta

</>

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

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.

Panics with a MoveError when either index is out of bounds. Use try_move_with_delta to handle untrusted indices without crashing.

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.

resolve

</>

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

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. Panics with UnknownAnchorTarget when the target was never merged or was compacted and its forwarding has expired — hosts holding anchors across compaction rounds should use try_resolve and treat failure as “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.

try_anchor_at

</>

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

Safely create an anchor at the gap before the visible item at index.

Valid positions are 0 <= index <= length.

try_delete_with_delta

</>

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

Safely delete a value and return both the updated sequence and deletion delta.

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

The delta is a Sequence stamped with this replica’s id. Apply it on a peer as merge(peer_state, delta) — local state first — or with merge_as; passing it first hands the peer this replica’s identity.

try_insert_many_with_delta

</>

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

Safely insert several values at consecutive visible indices starting at index, returning the updated sequence and a single delta of all new items.

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.

try_insert_with_delta

</>

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

Safely insert a value and return both the updated sequence and insertion delta.

try_move_with_delta

</>

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

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

try_resolve

</>

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

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

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.

values

</>

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

Return all visible values in sequence order.