Rga
A Replicated Growable Array (RGA): an op-based sequence CRDT for ordered collections such as chat messages or collaborative text.
How it fits Quilted. Unlike the delta-state types in this module, RGA's natural unit is an operation, not a state fragment. The "state" here is the full op-log: a set of RgaOps. piece is an idempotent union of two op-logs — that union satisfies the lattice laws (idempotent, commutative, associative) because the ops are uniquely identified and set-union has those properties. Any two replicas that have absorbed the same set of ops compute the identical sequence from toList, regardless of the order in which they absorbed them.
Concurrent-insert tiebreak. When two Insert(idA, _, p) and Insert(idB, _, p) share the same predecessor p, the larger id wins the immediately-after slot. With idA > idB the resulting list is … p A B ….
Tombstones. Removed elements remain in the op-log. This is deliberate: a future Insert(id, _, removedId) must still find the predecessor. GC of tombstones is performed by compact.
Lamport clock. Each replica tracks a local lamport counter. Minting a new op increments it and records the current maximum observed across all received ops.
Type Parameters
the element type. Must be serializable for wire transport.
Samples
val a = ReplicaId("A")
val b = ReplicaId("B")
val (rgaA, opA) = Rga.empty<String>().insertAt(a, 0, "Hello")
val (rgaB, opB) = Rga.empty<String>().insertAt(b, 0, "World")
// Both replicas absorb both ops.
val mergedByA = rgaA.apply(opB)
val mergedByB = rgaB.apply(opA)
// Convergence: both produce the same list regardless of delivery order.
check(mergedByA.toList() == mergedByB.toList())Properties
Per-author high-water of dots this replica has compacted away — every dot (r, s) with s <= compactedBelow[r] is permanently suppressed.
All ids that have been garbage-collected by any RgaOp.Compact in this op-log — the unbounded half of the compaction record, as against the O(authors) compactedBelow floor.
How many RgaOp.Compact ops this log retains.
The set of all RgaIds that have been tombstoned (and not yet compacted).
Functions
The causal Dots this op-log has delivered: every Insert's own dot (id.dot = (replicaId, seq)) plus every dot recorded in a Compact op.
The delivered dots this replica compacted away without keeping their ids — exactly compactedBelow.
Garbage-collect tombstoned elements that are causally stable under the eviction-safe causal-stability barrier (ADR-003 addendum v3, #262).
Append values as a chain starting immediately after after, minting one RgaOp.Insert per element on behalf of replica.
The ops this replica currently holds — see OpLogCrdt.operations.
The canonical RgaOpSerializer — see OpLogCrdt.opSerializer.
Returns a positions map for ids: each id mapped to its RgaOp.Insert.after. All ids must be present in insertsById (non-compacted — live or tombstoned). Used by us.tractat.kuilt.quilter.RgaGcCoordinator to build positions for window-dropped live elements when constructing a combined RgaOp.Compact.
Tombstone the first count visible elements, minting one RgaOp.Remove each.