add

Add element on behalf of replica, minting a fresh dot — and return the change, one element and a short causal note, rather than the whole new set.

This is what to put on the wire. A replicator broadcasts a patch's delta verbatim, so a mutator that handed back the new set would ship every element on every write, at a cost that grows with the set; this frame's size does not depend on how large the set is. The idiom is quilter.mutate { it.add(replica, element) } — read-modify-write inside the replicator's own lock. To hold the resulting set locally, absorb the patch: set.piece(set.add(…)).

A delta is itself an ORSet, so a peer absorbs it with the ordinary piece join, in any order, with any repeats, and lands on a state that encodes byte-for-byte identically to the author's own. Nothing has to be buffered or delivered in causal order.

The delta's context names the minted dot and the dots this add supersedes, and that second term must not be simplified away. An add replaces an element's dots rather than growing them, so a delta announcing only the new dot would leave the superseded ones alive on every receiver — and a later remove, retiring only the dot it knew about, would resurrect the element. That failure was measured while designing this method (#2044) and is pinned by ORSetDeltaMutatorLawTest.

Samples

val a = ReplicaId("A")
val b = ReplicaId("B")

// Two peers have converged: "alice" is present on both, added by B.
var alpha = ORSet.empty<String>().piece { it.add(b, "alice") }
var bravo = alpha

// A re-adds "alice" and puts only the change on the wire. The delta names A's new dot
// *and* B's older one, which the re-add supersedes — so both peers drop the old dot.
val readd = alpha.add(a, "alice")
alpha = alpha.piece(readd)
bravo = bravo.piece(readd)
check(alpha == bravo)

// A concurrent add beats a concurrent remove: B's re-add mints a dot A's remove never saw.
val concurrent = alpha.add(b, "alice")
check(alpha.piece(alpha.remove("alice")).piece(concurrent).contains("alice"))

// A remove lands everywhere, because both peers agree on which dot is live. Had the delta
// above kept quiet about B's dot, it would still be alive on bravo — and "alice" would come
// back from the dead there.
val forget = alpha.remove("alice")
alpha = alpha.piece(forget)
bravo = bravo.piece(forget)
check(!alpha.contains("alice"))
check(!bravo.contains("alice"))