version_vector_test.go

package yin

import (
	"fmt"
	"math/rand"
	"reflect"
	"testing"
	"testing/quick"
)

func TestVersionVectorGetIncrementAndCopySemantics(t *testing.T) {
	source := map[ReplicaID]uint64{
		ReplicaID("replica-a"): 1,
		ReplicaID("replica-b"): 0,
	}
	vector := NewVersionVector(source)
	source[ReplicaID("replica-a")] = 99
	source[ReplicaID("replica-c")] = 7

	if got := vector.Get(ReplicaID("replica-a")); got != 1 {
		t.Fatalf("NewVersionVector did not copy input: Get(replica-a) = %d, want 1", got)
	}
	if got := vector.Get(ReplicaID("replica-b")); got != 0 {
		t.Fatalf("zero counters should read as absent: Get(replica-b) = %d, want 0", got)
	}
	if got := vector.Get(ReplicaID("replica-c")); got != 0 {
		t.Fatalf("input mutation leaked into vector: Get(replica-c) = %d, want 0", got)
	}

	counters := vector.Counters()
	counters[ReplicaID("replica-a")] = 42
	if got := vector.Get(ReplicaID("replica-a")); got != 1 {
		t.Fatalf("Counters did not return a copy: Get(replica-a) = %d, want 1", got)
	}

	incremented := vector.Increment(ReplicaID("replica-a"))
	if got := vector.Get(ReplicaID("replica-a")); got != 1 {
		t.Fatalf("Increment mutated receiver: original Get(replica-a) = %d, want 1", got)
	}
	if got := incremented.Get(ReplicaID("replica-a")); got != 2 {
		t.Fatalf("Increment(replica-a).Get(replica-a) = %d, want 2", got)
	}
	if got := incremented.Increment(ReplicaID("replica-c")).Get(ReplicaID("replica-c")); got != 1 {
		t.Fatalf("Increment on missing replica = %d, want 1", got)
	}
}

func TestVersionVectorJoin(t *testing.T) {
	left := NewVersionVector(map[ReplicaID]uint64{
		ReplicaID("replica-a"): 2,
		ReplicaID("replica-b"): 1,
	})
	right := NewVersionVector(map[ReplicaID]uint64{
		ReplicaID("replica-a"): 1,
		ReplicaID("replica-c"): 5,
	})
	want := NewVersionVector(map[ReplicaID]uint64{
		ReplicaID("replica-a"): 2,
		ReplicaID("replica-b"): 1,
		ReplicaID("replica-c"): 5,
	})

	joined := left.Join(right)
	if !joined.Equal(want) {
		t.Fatalf("Join = %#v, want %#v", joined.Counters(), want.Counters())
	}
	if got := left.Get(ReplicaID("replica-c")); got != 0 {
		t.Fatalf("Join mutated receiver: left.Get(replica-c) = %d, want 0", got)
	}
	if got := right.Get(ReplicaID("replica-b")); got != 0 {
		t.Fatalf("Join mutated argument: right.Get(replica-b) = %d, want 0", got)
	}
}

func TestVersionVectorCompare(t *testing.T) {
	tests := []struct {
		name  string
		left  VersionVector
		right VersionVector
		want  VersionVectorComparison
	}{
		{
			name:  "empty equal",
			left:  VersionVector{},
			right: VersionVector{},
			want:  VersionVectorEqual,
		},
		{
			name: "same counters equal",
			left: NewVersionVector(map[ReplicaID]uint64{
				ReplicaID("replica-a"): 2,
				ReplicaID("replica-b"): 5,
			}),
			right: NewVersionVector(map[ReplicaID]uint64{
				ReplicaID("replica-a"): 2,
				ReplicaID("replica-b"): 5,
			}),
			want: VersionVectorEqual,
		},
		{
			name: "left dominates",
			left: NewVersionVector(map[ReplicaID]uint64{
				ReplicaID("replica-a"): 3,
				ReplicaID("replica-b"): 5,
			}),
			right: NewVersionVector(map[ReplicaID]uint64{
				ReplicaID("replica-a"): 2,
				ReplicaID("replica-b"): 5,
			}),
			want: VersionVectorDominates,
		},
		{
			name: "left dominated by right",
			left: NewVersionVector(map[ReplicaID]uint64{
				ReplicaID("replica-a"): 2,
			}),
			right: NewVersionVector(map[ReplicaID]uint64{
				ReplicaID("replica-a"): 2,
				ReplicaID("replica-b"): 1,
			}),
			want: VersionVectorDominatedBy,
		},
		{
			name: "concurrent",
			left: NewVersionVector(map[ReplicaID]uint64{
				ReplicaID("replica-a"): 3,
				ReplicaID("replica-b"): 1,
			}),
			right: NewVersionVector(map[ReplicaID]uint64{
				ReplicaID("replica-a"): 2,
				ReplicaID("replica-b"): 4,
			}),
			want: VersionVectorConcurrent,
		},
		{
			name: "present counter dominates absent counter",
			left: NewVersionVector(map[ReplicaID]uint64{
				ReplicaID("replica-a"): 1,
			}),
			right: VersionVector{},
			want:  VersionVectorDominates,
		},
	}

	for _, tc := range tests {
		t.Run(tc.name, func(t *testing.T) {
			if got := tc.left.Compare(tc.right); got != tc.want {
				t.Fatalf("Compare = %s, want %s", got, tc.want)
			}
		})
	}
}

func TestVersionVectorSince(t *testing.T) {
	current := NewVersionVector(map[ReplicaID]uint64{
		ReplicaID("replica-a"): 2,
		ReplicaID("replica-b"): 5,
		ReplicaID("replica-c"): 7,
	})
	base := NewVersionVector(map[ReplicaID]uint64{
		ReplicaID("replica-a"): 1,
		ReplicaID("replica-b"): 5,
		ReplicaID("replica-d"): 9,
	})
	want := NewVersionVector(map[ReplicaID]uint64{
		ReplicaID("replica-a"): 2,
		ReplicaID("replica-c"): 7,
	})

	progress := current.Since(base)
	if !progress.Equal(want) {
		t.Fatalf("Since = %#v, want %#v", progress.Counters(), want.Counters())
	}
	if got := current.Since(current); !got.Equal(VersionVector{}) {
		t.Fatalf("Since self = %#v, want empty", got.Counters())
	}
	if got := base.Since(current); !got.Equal(NewVersionVector(map[ReplicaID]uint64{ReplicaID("replica-d"): 9})) {
		t.Fatalf("Since keeps only counters greater than base: got %#v", got.Counters())
	}
}

func TestVersionVectorJoinLaws(t *testing.T) {
	t.Run("commutative", func(t *testing.T) {
		checkVersionVectorProperty(t, "join commutative", 0x7656_6a01, func(a, b quickVersionVector) bool {
			return a.V.Join(b.V).Equal(b.V.Join(a.V))
		})
	})

	t.Run("associative", func(t *testing.T) {
		checkVersionVectorProperty(t, "join associative", 0x7656_6a02, func(a, b, c quickVersionVector) bool {
			left := a.V.Join(b.V).Join(c.V)
			right := a.V.Join(b.V.Join(c.V))
			return left.Equal(right)
		})
	})

	t.Run("idempotent", func(t *testing.T) {
		checkVersionVectorProperty(t, "join idempotent", 0x7656_6a03, func(a quickVersionVector) bool {
			return a.V.Join(a.V).Equal(a.V)
		})
	})
}

func TestVersionVectorCompareConsistentWithJoin(t *testing.T) {
	var reason string
	checkVersionVectorProperty(t, "compare consistent with join", 0x7656_6a04, func(a, b quickVersionVector) bool {
		left := a.V
		right := b.V
		joined := left.Join(right)
		cmp := left.Compare(right)
		reverse := right.Compare(left)

		if !comparisonIsReverse(cmp, reverse) {
			reason = fmt.Sprintf("reverse compare mismatch: left=%#v right=%#v cmp=%s reverse=%s", left.Counters(), right.Counters(), cmp, reverse)
			return false
		}

		switch cmp {
		case VersionVectorEqual:
			if joined.Equal(left) && joined.Equal(right) {
				return true
			}
			reason = fmt.Sprintf("equal vectors should join to both: left=%#v right=%#v joined=%#v", left.Counters(), right.Counters(), joined.Counters())
			return false
		case VersionVectorDominates:
			if joined.Equal(left) && !left.Equal(right) {
				return true
			}
			reason = fmt.Sprintf("dominating left should equal join: left=%#v right=%#v joined=%#v", left.Counters(), right.Counters(), joined.Counters())
			return false
		case VersionVectorDominatedBy:
			if joined.Equal(right) && !left.Equal(right) {
				return true
			}
			reason = fmt.Sprintf("dominated left should join to right: left=%#v right=%#v joined=%#v", left.Counters(), right.Counters(), joined.Counters())
			return false
		case VersionVectorConcurrent:
			if !joined.Equal(left) && !joined.Equal(right) {
				return true
			}
			reason = fmt.Sprintf("concurrent vectors should join to a strict combined vector: left=%#v right=%#v joined=%#v", left.Counters(), right.Counters(), joined.Counters())
			return false
		default:
			reason = fmt.Sprintf("unknown comparison result %d", cmp)
			return false
		}
	}, &reason)
}

func TestVersionVectorIncrementMonotonic(t *testing.T) {
	var reason string
	checkVersionVectorProperty(t, "increment monotonic", 0x7656_6a05, func(vector quickVersionVector, replica quickReplicaID) bool {
		before := vector.V
		after := before.Increment(replica.ID)
		if got, want := after.Get(replica.ID), before.Get(replica.ID)+1; got != want {
			reason = fmt.Sprintf("incremented counter mismatch: before=%#v replica=%q got=%d want=%d", before.Counters(), replica.ID, got, want)
			return false
		}
		if cmp := after.Compare(before); cmp != VersionVectorDominates {
			reason = fmt.Sprintf("increment should strictly dominate: before=%#v after=%#v cmp=%s", before.Counters(), after.Counters(), cmp)
			return false
		}
		return true
	}, &reason)
}

func checkVersionVectorProperty(t *testing.T, name string, seed int64, property any, reasons ...*string) {
	t.Helper()
	cfg := &quick.Config{
		MaxCount: 512,
		Rand:     rand.New(rand.NewSource(seed)),
	}
	if err := quick.Check(property, cfg); err != nil {
		details := ""
		if len(reasons) > 0 && reasons[0] != nil && *reasons[0] != "" {
			details = "\nreason: " + *reasons[0]
		}
		t.Fatalf("%s failed with seed %#x: %v%s", name, seed, err, details)
	}
}

func comparisonIsReverse(left, right VersionVectorComparison) bool {
	switch left {
	case VersionVectorEqual:
		return right == VersionVectorEqual
	case VersionVectorDominates:
		return right == VersionVectorDominatedBy
	case VersionVectorDominatedBy:
		return right == VersionVectorDominates
	case VersionVectorConcurrent:
		return right == VersionVectorConcurrent
	default:
		return false
	}
}

type quickVersionVector struct {
	V VersionVector
}

func (quickVersionVector) Generate(r *rand.Rand, size int) reflect.Value {
	replicas := []ReplicaID{
		ReplicaID("replica-a"),
		ReplicaID("replica-b"),
		ReplicaID("replica-c"),
		ReplicaID("replica-d"),
		ReplicaID("replica-e"),
	}

	entries := r.Intn(len(replicas) + 1)
	order := r.Perm(len(replicas))
	counters := make(map[ReplicaID]uint64, entries)
	for i := 0; i < entries; i++ {
		// Keep counters far below uint64 max so Increment's monotonic property is
		// not obscured by overflow behavior.
		counters[replicas[order[i]]] = uint64(1 + r.Intn(128))
	}
	return reflect.ValueOf(quickVersionVector{V: NewVersionVector(counters)})
}

func (v quickVersionVector) String() string {
	return fmt.Sprintf("%#v", v.V.Counters())
}

type quickReplicaID struct {
	ID ReplicaID
}

func (quickReplicaID) Generate(r *rand.Rand, size int) reflect.Value {
	replicas := []ReplicaID{
		ReplicaID("replica-a"),
		ReplicaID("replica-b"),
		ReplicaID("replica-c"),
		ReplicaID("replica-d"),
		ReplicaID("replica-e"),
		ReplicaID("replica-new"),
	}
	return reflect.ValueOf(quickReplicaID{ID: replicas[r.Intn(len(replicas))]})
}

func (id quickReplicaID) String() string {
	return string(id.ID)
}