toy_documents_test.go

package yin

import (
	"math/rand"
	"testing"
)

const toyGSetDeltaKind = "toy-g-set"

type toyGSet struct {
	replica ReplicaID
	values  map[int]struct{}
	version VersionVector
}

func newToyGSet(replica ReplicaID) *toyGSet {
	return &toyGSet{
		replica: replica,
		values:  make(map[int]struct{}),
	}
}

func (s *toyGSet) Add(value int) {
	if s.values == nil {
		s.values = make(map[int]struct{})
	}
	s.values[value] = struct{}{}
	s.version = s.version.Increment(s.replica)
}

func (s *toyGSet) Merge(other Document) (changed bool) {
	otherSet, ok := other.(*toyGSet)
	if !ok || otherSet == nil {
		return false
	}
	return s.applyDelta(cloneIntSet(otherSet.values), otherSet.version)
}

func (s *toyGSet) ExtractDelta(since VersionVector) Delta {
	switch since.Compare(s.version) {
	case VersionVectorEqual, VersionVectorDominates:
		return nil
	default:
		return toyGSetDelta{
			values:  cloneIntSet(s.values),
			version: s.version,
		}
	}
}

func (s *toyGSet) ApplyDelta(d Delta) (changed bool) {
	if d == nil {
		return false
	}
	switch delta := d.(type) {
	case toyGSetDelta:
		return s.applyDelta(delta.values, delta.version)
	case *toyGSetDelta:
		if delta == nil {
			return false
		}
		return s.applyDelta(delta.values, delta.version)
	default:
		return false
	}
}

func (s *toyGSet) Equal(other Document) bool {
	otherSet, ok := other.(*toyGSet)
	if !ok || otherSet == nil || len(s.values) != len(otherSet.values) || !s.version.Equal(otherSet.version) {
		return false
	}
	for value := range s.values {
		if _, exists := otherSet.values[value]; !exists {
			return false
		}
	}
	return true
}

func (s *toyGSet) Version() VersionVector {
	return s.version.Clone()
}

func (s *toyGSet) applyDelta(values map[int]struct{}, version VersionVector) (changed bool) {
	if s.values == nil {
		s.values = make(map[int]struct{}, len(values))
	}
	for value := range values {
		if _, exists := s.values[value]; exists {
			continue
		}
		s.values[value] = struct{}{}
		changed = true
	}
	joined := s.version.Join(version)
	if !joined.Equal(s.version) {
		s.version = joined
		changed = true
	}
	return changed
}

type toyGSetDelta struct {
	values  map[int]struct{}
	version VersionVector
}

func (d toyGSetDelta) Kind() string {
	return toyGSetDeltaKind
}

func (d toyGSetDelta) Version() VersionVector {
	return d.version.Clone()
}

func cloneIntSet(values map[int]struct{}) map[int]struct{} {
	clone := make(map[int]struct{}, len(values))
	for value := range values {
		clone[value] = struct{}{}
	}
	return clone
}

const brokenAdditiveCounterDeltaKind = "broken-additive-counter"

type brokenAdditiveCounter struct {
	replica ReplicaID
	total   int
	version VersionVector
}

func (c *brokenAdditiveCounter) Add(value int) {
	c.total += value
	c.version = c.version.Increment(c.replica)
}

func (c *brokenAdditiveCounter) Merge(other Document) (changed bool) {
	otherCounter, ok := other.(*brokenAdditiveCounter)
	if !ok || otherCounter == nil {
		return false
	}
	return c.applyDelta(otherCounter.total, otherCounter.version)
}

func (c *brokenAdditiveCounter) ExtractDelta(since VersionVector) Delta {
	switch since.Compare(c.version) {
	case VersionVectorEqual, VersionVectorDominates:
		return nil
	default:
		return brokenAdditiveCounterDelta{
			total:   c.total,
			version: c.version,
		}
	}
}

func (c *brokenAdditiveCounter) ApplyDelta(d Delta) (changed bool) {
	if d == nil {
		return false
	}
	switch delta := d.(type) {
	case brokenAdditiveCounterDelta:
		return c.applyDelta(delta.total, delta.version)
	case *brokenAdditiveCounterDelta:
		if delta == nil {
			return false
		}
		return c.applyDelta(delta.total, delta.version)
	default:
		return false
	}
}

func (c *brokenAdditiveCounter) Equal(other Document) bool {
	otherCounter, ok := other.(*brokenAdditiveCounter)
	return ok && otherCounter != nil && c.total == otherCounter.total && c.version.Equal(otherCounter.version)
}

func (c *brokenAdditiveCounter) Version() VersionVector {
	return c.version.Clone()
}

func (c *brokenAdditiveCounter) applyDelta(total int, version VersionVector) (changed bool) {
	beforeTotal := c.total
	beforeVersion := c.version
	c.total += total
	c.version = c.version.Join(version)
	return c.total != beforeTotal || !c.version.Equal(beforeVersion)
}

type brokenAdditiveCounterDelta struct {
	total   int
	version VersionVector
}

func (d brokenAdditiveCounterDelta) Kind() string {
	return brokenAdditiveCounterDeltaKind
}

func (d brokenAdditiveCounterDelta) Version() VersionVector {
	return d.version.Clone()
}

func TestHarnessDetectsBrokenMerge(t *testing.T) {
	const seed int64 = 0x5eed_c0de

	correct := convergenceConfig[int]{
		name:        "toy G-Set",
		seed:        seed,
		replicas:    4,
		operations:  64,
		mergeRounds: 3,
		newReplica: func(replica int) Document {
			return newToyGSet(harnessReplicaID("toy-gset", replica))
		},
		generateOp: func(r *rand.Rand, step int, replica int) int {
			return replica*1_000 + step*10 + r.Intn(10)
		},
		apply: func(replica Document, op int) {
			replica.(*toyGSet).Add(op)
		},
	}
	if _, err := runConvergenceHarness(correct); err != nil {
		t.Fatalf("correct toy CRDT did not converge: %v", err)
	}

	broken := convergenceConfig[int]{
		name:        "broken additive counter",
		seed:        seed,
		replicas:    4,
		operations:  64,
		mergeRounds: 3,
		newReplica: func(replica int) Document {
			return &brokenAdditiveCounter{replica: harnessReplicaID("broken-counter", replica)}
		},
		generateOp: func(r *rand.Rand, step int, replica int) int {
			return 1 + r.Intn(7) + replica + step%3
		},
		apply: func(replica Document, op int) {
			replica.(*brokenAdditiveCounter).Add(op)
		},
	}
	if _, err := runConvergenceHarness(broken); err == nil {
		t.Fatal("broken toy CRDT unexpectedly converged; harness did not catch non-idempotent merge")
	} else {
		t.Logf("harness caught broken merge as expected: %v", err)
	}
}