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
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.
Garbage-collect tombstoned elements that are causally stable under the eviction-safe causal-stability barrier (ADR-003 addendum v3, #262).
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.