Conflicts and CRDTs

// Inc adds n (n >= 0) to replica r's own entry. It returns the new state and the delta to send.
func (g GCounter) Inc(r string, n int64) (GCounter, GCounter) {
  if n < 0 {
    panic(fmt.Sprintf("GCounter.Inc: negative amount %d", n))
  }
  out := maps.Clone(g)
  if out == nil {
    out = GCounter{}
  }
  out[r] += n
  return out, GCounter{r: out[r]}
}

// Value is the sum of every replica's entry.
func (g GCounter) Value() int64 {
  var v int64
  for _, n := range g {
    v += n
  }
  return v
}

// Merge takes the larger entry for each replica. An entry only grows, so the larger one has
// seen more of that replica's increments.
func (g GCounter) Merge(o GCounter) GCounter {
  out := maps.Clone(g)
  if out == nil {
    out = GCounter{}
  }
  for r, n := range o {
    out[r] = max(out[r], n)
  }
  return out
}

// PNCounter counts up and down with two grow-only counters: increments and decrements.
type PNCounter struct {
  P GCounter `json:"p"`
  N GCounter `json:"n"`
}

// Add adds n, which may be negative, at replica r.
func (c PNCounter) Add(r string, n int64) (PNCounter, PNCounter) {
  if n >= 0 {
    p, d := c.P.Inc(r, n)
    return PNCounter{P: p, N: c.N}, PNCounter{P: d}
  }
  m, d := c.N.Inc(r, -n)
  return PNCounter{P: c.P, N: m}, PNCounter{N: d}
}

// Value is increments minus decrements.
func (c PNCounter) Value() int64 { return c.P.Value() - c.N.Value() }

// Merge merges both halves.
func (c PNCounter) Merge(o PNCounter) PNCounter {
  return PNCounter{P: c.P.Merge(o.P), N: c.N.Merge(o.N)}
}

// Set writes v at replica r with timestamp ts from r's clock.
func (l LWW[T]) Set(r string, v T, ts int64) (LWW[T], LWW[T]) {
  w := LWW[T]{Value: v, TS: ts, Replica: r}
  return l.Merge(w), w
}

// Merge keeps the later write. Equal timestamps fall back to the replica name, so every
// replica picks the same winner. The loser is gone, even if it happened later in real time.
func (l LWW[T]) Merge(o LWW[T]) LWW[T] {
  if o.TS > l.TS || (o.TS == l.TS && o.Replica > l.Replica) {
    return o
  }
  return l
}

// MV is a multi-value register. Each write carries a version vector. A write that has seen
// another write replaces it; two concurrent writes are both kept, as siblings, until a later
// write that has seen both replaces them.
type MV[T comparable] struct {
  Entries []MVEntry[T] `json:"entries"`
}

// MVEntry is one sibling: a value and the version vector of its write.
type MVEntry[T comparable] struct {
  Value T  `json:"value"`
  VV    VV `json:"vv"`
}

// Set writes v at replica r. Its vector is the join of every sibling's vector plus one for r,
// so it supersedes every sibling this replica has seen.
func (m MV[T]) Set(r string, v T) (MV[T], MV[T]) {
  vv := VV{}
  for _, e := range m.Entries {
    vv = vv.Join(e.VV)
  }
  vv[r]++
  w := MV[T]{Entries: []MVEntry[T]{{Value: v, VV: vv}}}
  return m.Merge(w), w
}

// Merge keeps every entry that no other entry's vector dominates.
func (m MV[T]) Merge(o MV[T]) MV[T] {
  all := append(slices.Clone(m.Entries), o.Entries...)
  var out []MVEntry[T]
  for i, e := range all {
    keep := true
    for j, f := range all {
      if i != j && (e.VV.Before(f.VV) || (e.VV.Equal(f.VV) && j < i)) {
        keep = false // dominated, or a duplicate of an earlier entry
        break
      }
    }
    if keep {
      out = append(out, e)
    }
  }
  sortEntries(out)
  return MV[T]{Entries: out}
}

// Add adds e at replica r with a new tag.
func (s ORSet) Add(r, e string) (ORSet, ORSet) {
  t := Tag{R: r, N: s.lastTag(r) + 1}
  d := ORSet{Adds: map[string]map[Tag]bool{e: {t: true}}}
  return s.Merge(d), d
}

// Remove removes e: it tombstones every tag of e that this replica has observed.
func (s ORSet) Remove(e string) (ORSet, ORSet) {
  d := ORSet{Removed: map[Tag]bool{}}
  for t := range s.Adds[e] {
    if !s.Removed[t] {
      d.Removed[t] = true
    }
  }
  return s.Merge(d), d
}

// Has reports whether e has a tag that no remove has observed.
func (s ORSet) Has(e string) bool {
  for t := range s.Adds[e] {
    if !s.Removed[t] {
      return true
    }
  }
  return false
}

// Merge is the union of the adds and the union of the tombstones.
func (s ORSet) Merge(o ORSet) ORSet {
  out := ORSet{Adds: map[string]map[Tag]bool{}, Removed: map[Tag]bool{}}
  for _, x := range []ORSet{s, o} {
    for e, tags := range x.Adds {
      if out.Adds[e] == nil {
        out.Adds[e] = map[Tag]bool{}
      }
      maps.Copy(out.Adds[e], tags)
    }
    maps.Copy(out.Removed, x.Removed)
  }
  return out
}

// Insert inserts s at visible position pos, at replica r. Each character gets an ID above every
// ID this replica has seen, and hangs under the character before it.
func (t Text) Insert(r string, pos int, s string) (Text, Text) {
  after := root
  if pos > 0 {
    after = t.visible()[pos-1]
  }
  c := t.maxCounter()
  d := Text{Chars: map[ID]Char{}}
  for _, l := range s {
    c++
    id := ID{C: c, R: r}
    d.Chars[id] = Char{ID: id, After: after, Letter: string(l)}
    after = id
  }
  return t.Merge(d), d
}

// Delete marks n visible characters from pos as tombstones.
func (t Text) Delete(pos, n int) (Text, Text) {
  d := Text{Deleted: map[ID]bool{}}
  for _, id := range t.visible()[pos : pos+n] {
    d.Deleted[id] = true
  }
  return t.Merge(d), d
}

// Merge is the union of the characters and the union of the tombstones.
func (t Text) Merge(o Text) Text {
  out := Text{Chars: map[ID]Char{}, Deleted: map[ID]bool{}}
  for _, x := range []Text{t, o} {
    maps.Copy(out.Chars, x.Chars)
    maps.Copy(out.Deleted, x.Deleted)
  }
  return out
}

// walk visits the tree depth first, children newest first. A character whose anchor has not
// arrived yet is not reachable, so it stays hidden until the anchor arrives.
func (t Text) walk(visit func(Char)) {
  kids := map[ID][]Char{}
  for _, c := range t.Chars {
    kids[c.After] = append(kids[c.After], c)
  }
  var down func(ID)
  down = func(at ID) {
    ks := kids[at]
    slices.SortFunc(ks, func(a, b Char) int { return b.ID.compare(a.ID) })
    for _, k := range ks {
      visit(k)
      down(k.ID)
    }
  }
  down(root)
}