crdt/orset
ORSet
(defstruct ORSet [elems : int ctx : DotContext])
observed-remove set of interned names.
Since: crdt-spice-plan C2
orset-new
(orset-new :)
an empty OR-Set.
An OR-Set with no elements and an empty causal history.
(orset-new)
Since: crdt-spice-plan C2
orset-add
(orset-add [s : ORSet e : Sym r : Sym] :)
add an element on behalf of a replica.
| s | the set | |
| e | the element | |
| r | the replica performing the add |
A new OR-Set in which e is present, tagged with a fresh dot for r.
(orset-add (orset-new) (quote apple) (quote alice))
Since: crdt-spice-plan C2
orset-remove
(orset-remove [s : ORSet e : Sym] :)
remove an element.
| s | the set | |
| e | the element |
A new OR-Set without e.
(orset-remove s (quote apple))
Since: crdt-spice-plan C2
orset-has?
(orset-has? [^borrow s : ORSet e : Sym] :)
is e present?
| s | the set | |
| e | the element |
true when e has at least one surviving dot.
(orset-has? s (quote apple))
Since: crdt-spice-plan C2
orset-count
(orset-count [^borrow s : ORSet] :)
how many elements are present.
| s | the set |
The number of elements with at least one surviving dot.
(orset-count s) ; => 2
Since: crdt-spice-plan C2
orset-dots
(orset-dots [^borrow s : ORSet] :)
how many (element, replica) dots the set is carrying.
| s | the set |
The total size of the dot store, summed over every element.
(orset-dots s) ; => 3
Since: crdt-spice-plan C4
orset-ctx-size
(orset-ctx-size [^borrow s : ORSet] :)
how many replicas the causal context has heard from.
| s | the set |
The width of the version vector.
(orset-ctx-size s) ; => 2
Since: crdt-spice-plan C4
OrsetDelta
(defstruct OrsetDelta [adds : int rms : DotSet])
a dot-store fragment plus the EXACT dots it retracts.
Since: crdt-spice-plan C4
orset-delta-new
(orset-delta-new :)
the empty delta.
A delta that adds nothing and retracts nothing; applying it is a no-op.
(orset-delta-new)
Since: crdt-spice-plan C4
orset-delta-dots
(orset-delta-dots [^borrow d : OrsetDelta] :)
how many (element, replica) dots the delta asserts.
| d | the delta |
The size of its dot store.
(orset-delta-dots d) ; => 1
Since: crdt-spice-plan C4
orset-delta-retracts
(orset-delta-retracts [^borrow d : OrsetDelta] :)
how many dots the delta withdraws.
| d | the delta |
The size of its retraction set.
(orset-delta-retracts d) ; => 1
Since: crdt-spice-plan C4
orset-delta-add
(orset-delta-add [^borrow s : ORSet e : Sym r : Sym] :)
the DELTA of adding an element on behalf of a replica.
| s | the set, read for the replica's next dot | |
| e | the element | |
| r | the replica performing the add |
A delta asserting exactly one dot on e, retracting nothing.
(orset-delta-add s (quote apple) (quote alice))
Since: crdt-spice-plan C4
orset-delta-remove
(orset-delta-remove [^borrow s : ORSet e : Sym] :)
the DELTA of removing an element.
| s | the set, read for the dots currently on e | |
| e | the element |
A delta asserting nothing and retracting exactly the dots this replica has observed for e.
(orset-delta-remove s (quote apple))
Since: crdt-spice-plan C4
orset-apply
(orset-apply [s : ORSet ^borrow d : OrsetDelta] :)
fold a delta into a set.
| s | the set | |
| d | the delta |
The set with d's assertions added and d's retractions withdrawn.
(orset-apply s (orset-delta-add other (quote apple) (quote alice)))
Since: crdt-spice-plan C4
Internal definitions
__ctr-- internal: a map's counter for r, or 0.__put-kv-- internal: assoc into a Sym->int map, handle in, handle out.__inner-of-- internal: element e's dot map, or a fresh empty one.__imax__os-- internal.__inner-a-loop-- internal: A's dots that survive the merge.__inner-b-loop-- internal: B's dots that A does not already account for.__inner-a-- internal: merge one element's dot maps.__inner-b__inner-merge__outer-loop-- internal: merge every element of one side into acc.__fold-side-- internal: merge one side's elements into acc.__dots-count-loop-- internal.__dots-of-elem-- internal: one element's dot map as an exact DotSet.__dots-of-loop-- internal.JoinSemilattice[OrsetDelta]-- assert both sides, retract both sides.BoundedJoin[OrsetDelta]-- the empty delta is the least element.Eq[OrsetDelta]-- same number of asserted and retracted dots.__merge-adds-- internal: pointwise max over element -> replica -> counter.__merge-adds-loop-- internal.__max-inner-- internal: pointwise max of two replica -> counter maps.__max-inner-loop-- internal.JoinSemilattice[ORSet]-- add-wins merge, dot-aware.BoundedJoin[ORSet]-- the empty set is the least element.Eq[ORSet]-- same number of present elements.__witness-rms-- internal: witness a retraction carrier's dots.__witness-rms-loop-- internal.__max-ctr-of-- internal: the highest counter in a counter set.__max-ctr-loop-- internal.__rms-has?-- internal: is this exact dot in a retraction carrier?__apply-adds-- internal: fold a delta's assertions into the dot store.__apply-adds-loop-- internal.__absorb-inner-- internal: take the delta's dots the receiver may still take.__absorb-loop-- internal.__retract-- internal: drop every dot the delta withdraws.__retract-loop-- internal.__retract-inner-- internal: one element's surviving dots.__retract-inner-loop-- internal.__witness-adds-- internal: record a delta's asserted dots in the context.__witness-adds-loop-- internal.__witness-inner-- internal: witness one element's asserted dots.__witness-inner-loop-- internal.DeltaCRDT[ORSet]-- the delta is a dot-store fragment plus exact retractions.