Skip to content

Git designed for AI agents.

14.1 KB
Raw Blame
package graph

import (
	"bytes"
	"context"
	"encoding/hex"
	"errors"
	"fmt"
	"math/bits"
	"math/rand"
	"sort"
	"testing"

	"github.com/feder-cr/git-ai/internal/git"
	"github.com/feder-cr/git-ai/internal/graft/derived"
	"github.com/stretchr/testify/require"
)

// fakeSource is an in-memory history. It counts the reads of parents, and it can fail
// a number of reads before it answers, to test that a failed walk does not poison the
// index.
type fakeSource struct {
	parents  map[git.ObjectID][]git.ObjectID
	failures int
	calls    int
}

func (s *fakeSource) Parents(ctx context.Context, id git.ObjectID) ([]git.ObjectID, error) {
	s.calls++
	if err := ctx.Err(); err != nil {
		return nil, err
	}
	if s.failures > 0 {
		s.failures--
		return nil, errors.New("transient read failure")
	}

	parents, ok := s.parents[id]
	if !ok {
		return nil, fmt.Errorf("unknown commit %s", id)
	}
	return parents, nil
}

func commitID(i int) git.ObjectID { return git.ObjectID(fmt.Sprintf("c%d", i)) }

// hexID returns a valid object ID of the SHA-1 size for commit i. Stored entries
// encode their skip pointers as raw object IDs, so the stored tests use these.
func hexID(i int) git.ObjectID { return git.ObjectID(fmt.Sprintf("%040x", i+1)) }

// noStore returns the store of an Index that persists nothing.
func noStore() derived.KindStore { return (*derived.Store)(nil).Kind(kindName, kindVersion) }

// randomDAG returns n commits c0..c(n-1), see randomDAGWith.
func randomDAG(rnd *rand.Rand, n int) map[git.ObjectID][]git.ObjectID {
	return randomDAGWith(rnd, n, commitID)
}

// randomDAGWith returns the parents of n commits named by id. Every commit has a
// first parent that is often the previous commit, and some have a second parent. A
// few commits start a new root, so that the history can be disconnected.
func randomDAGWith(rnd *rand.Rand, n int, id func(int) git.ObjectID) map[git.ObjectID][]git.ObjectID {
	parents := make(map[git.ObjectID][]git.ObjectID, n)
	for i := 0; i < n; i++ {
		if i == 0 || rnd.Float64() < 0.05 {
			parents[id(i)] = nil
			continue
		}

		first := i - 1
		if rnd.Intn(2) == 0 {
			first = rnd.Intn(i)
		}
		list := []git.ObjectID{id(first)}
		if rnd.Intn(3) == 0 {
			if second := rnd.Intn(i); second != first {
				list = append(list, id(second))
			}
		}
		parents[id(i)] = list
	}
	return parents
}

// bruteAncestors returns every commit reachable from id, including id itself.
func bruteAncestors(parents map[git.ObjectID][]git.ObjectID, id git.ObjectID) map[git.ObjectID]bool {
	seen := map[git.ObjectID]bool{id: true}
	stack := []git.ObjectID{id}
	for len(stack) > 0 {
		current := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		for _, parent := range parents[current] {
			if !seen[parent] {
				seen[parent] = true
				stack = append(stack, parent)
			}
		}
	}
	return seen
}

// ancestorSets returns the ancestors of every commit of parents.
func ancestorSets(parents map[git.ObjectID][]git.ObjectID) map[git.ObjectID]map[git.ObjectID]bool {
	sets := make(map[git.ObjectID]map[git.ObjectID]bool, len(parents))
	for id := range parents {
		sets[id] = bruteAncestors(parents, id)
	}
	return sets
}

// bruteMergeBases returns the common ancestors of a and b that no other common
// ancestor reaches, sorted by ID.
func bruteMergeBases(parents map[git.ObjectID][]git.ObjectID, a, b git.ObjectID) []git.ObjectID {
	return bruteMergeBasesWith(ancestorSets(parents), a, b)
}

// bruteMergeBasesWith is bruteMergeBases with the ancestor sets computed by the caller.
func bruteMergeBasesWith(sets map[git.ObjectID]map[git.ObjectID]bool, a, b git.ObjectID) []git.ObjectID {
	var common []git.ObjectID
	for id := range sets[a] {
		if sets[b][id] {
			common = append(common, id)
		}
	}

	var best []git.ObjectID
	for _, c := range common {
		redundant := false
		for _, d := range common {
			if d != c && sets[d][c] {
				redundant = true
				break
			}
		}
		if !redundant {
			best = append(best, c)
		}
	}

	sort.Slice(best, func(i, j int) bool { return best[i] < best[j] })
	return best
}

func TestIndex_Generation(t *testing.T) {
	t.Parallel()

	src := &fakeSource{parents: map[git.ObjectID][]git.ObjectID{
		"root": nil,
		"a":    {"root"},
		"b":    {"root"},
		"m":    {"a", "b"},
		"n":    {"m"},
	}}
	ix := NewIndex(src, noStore())

	for id, expected := range map[git.ObjectID]uint32{"root": 1, "a": 2, "b": 2, "m": 3, "n": 4} {
		generation, err := ix.Generation(context.Background(), id)
		require.NoError(t, err)
		require.Equal(t, expected, generation, "generation of %s", id)
	}
}

func TestIndex_SkipPointers(t *testing.T) {
	t.Parallel()

	const length = 300
	src := &fakeSource{parents: make(map[git.ObjectID][]git.ObjectID, length)}
	for i := 0; i < length; i++ {
		if i == 0 {
			src.parents[commitID(i)] = nil
		} else {
			src.parents[commitID(i)] = []git.ObjectID{commitID(i - 1)}
		}
	}

	ix := NewIndex(src, noStore())
	_, err := ix.Generation(context.Background(), commitID(length-1))
	require.NoError(t, err)

	// The first-parent depth of commit i is i, so it has bits.Len(i) pointers, the
	// pointer k of which is the commit 2^k steps back.
	for i := 0; i < length; i++ {
		e, ok := ix.cache.Get(commitID(i))
		require.True(t, ok, "entry of c%d is cached", i)
		require.Len(t, e.skips, bits.Len(uint(i)), "pointers of c%d", i)
		for k, skip := range e.skips {
			require.Equal(t, commitID(i-(1<<k)), skip, "pointer %d of c%d", k, i)
		}
	}
}

func TestIndex_IsAncestorMatchesBruteForce(t *testing.T) {
	t.Parallel()

	for seed := int64(1); seed <= 5; seed++ {
		parents := randomDAG(rand.New(rand.NewSource(seed)), 60)
		ix := NewIndex(&fakeSource{parents: parents}, noStore())
		ctx := context.Background()

		for i := 0; i < 60; i++ {
			reachable := bruteAncestors(parents, commitID(i))
			for j := 0; j < 60; j++ {
				got, err := ix.IsAncestor(ctx, commitID(j), commitID(i))
				require.NoError(t, err)
				require.Equal(t, reachable[commitID(j)], got, "seed %d: IsAncestor(c%d, c%d)", seed, j, i)
			}
		}
	}
}

func TestIndex_MergeBasesMatchBruteForce(t *testing.T) {
	t.Parallel()

	for seed := int64(1); seed <= 5; seed++ {
		parents := randomDAG(rand.New(rand.NewSource(seed)), 60)
		ix := NewIndex(&fakeSource{parents: parents}, noStore())
		ctx := context.Background()

		for i := 0; i < 60; i++ {
			for j := i; j < 60; j++ {
				expected := bruteMergeBases(parents, commitID(i), commitID(j))

				got, err := ix.MergeBases(ctx, commitID(i), commitID(j))
				require.NoError(t, err)
				require.Equal(t, expected, got, "seed %d: MergeBases(c%d, c%d)", seed, i, j)

				one, err := ix.MergeBase(ctx, commitID(i), commitID(j))
				require.NoError(t, err)
				if len(expected) == 0 {
					require.Empty(t, one)
				} else {
					require.Equal(t, expected[0], one)
				}
			}
		}
	}
}

// TestIndex_RandomDAGWithMergesMatchesBruteForce compares the answers on histories of
// more than 200 commits with many merges, for sampled pairs of commits.
func TestIndex_RandomDAGWithMergesMatchesBruteForce(t *testing.T) {
	t.Parallel()

	const n = 220
	ctx := context.Background()

	for seed := int64(1); seed <= 2; seed++ {
		rnd := rand.New(rand.NewSource(seed))
		parents := randomDAGWith(rnd, n, hexID)

		merges := 0
		for _, list := range parents {
			if len(list) > 1 {
				merges++
			}
		}
		require.GreaterOrEqual(t, merges, 20, "seed %d has merges", seed)

		sets := ancestorSets(parents)
		ix := NewIndex(&fakeSource{parents: parents}, noStore())

		for k := 0; k < 500; k++ {
			i, j := rnd.Intn(n), rnd.Intn(n)

			isAncestor, err := ix.IsAncestor(ctx, hexID(i), hexID(j))
			require.NoError(t, err)
			require.Equal(t, sets[hexID(j)][hexID(i)], isAncestor, "seed %d: IsAncestor(%d, %d)", seed, i, j)

			bases, err := ix.MergeBases(ctx, hexID(i), hexID(j))
			require.NoError(t, err)
			require.Equal(t, bruteMergeBasesWith(sets, hexID(i), hexID(j)), bases, "seed %d: MergeBases(%d, %d)", seed, i, j)
		}
	}
}

func TestIndex_SourceFailuresAreRetried(t *testing.T) {
	t.Parallel()

	parents := randomDAG(rand.New(rand.NewSource(7)), 60)
	src := &fakeSource{parents: parents}
	ix := NewIndex(src, noStore())
	ctx := context.Background()

	// Each failure aborts a walk. Retries must eventually succeed with the right answer
	// rather than report a cycle from the half-expanded entries of the failed walks.
	src.failures = 25
	var got bool
	var err error
	for attempt := 0; attempt < 100; attempt++ {
		got, err = ix.IsAncestor(ctx, commitID(0), commitID(59))
		if err == nil {
			break
		}
		require.NotContains(t, err.Error(), "cycle")
	}
	require.NoError(t, err)
	require.Equal(t, bruteAncestors(parents, commitID(59))[commitID(0)], got)
}

func TestIndex_CycleIsReported(t *testing.T) {
	t.Parallel()

	src := &fakeSource{parents: map[git.ObjectID][]git.ObjectID{
		"a": {"b"},
		"b": {"a"},
	}}

	_, err := NewIndex(src, noStore()).IsAncestor(context.Background(), "a", "b")
	require.ErrorContains(t, err, "cycle")
}

func TestIndex_CanceledContext(t *testing.T) {
	t.Parallel()

	src := &fakeSource{parents: map[git.ObjectID][]git.ObjectID{"a": nil, "b": {"a"}}}
	ctx, cancel := context.WithCancel(context.Background())
	cancel()

	_, err := NewIndex(src, noStore()).IsAncestor(ctx, "a", "b")
	require.ErrorIs(t, err, context.Canceled)
}

// TestIndex_DeepHistoryWithoutRecursion uses a history longer than the cache, so that
// evictions happen, and checks that the cache stays bounded.
func TestIndex_DeepHistoryWithoutRecursion(t *testing.T) {
	t.Parallel()

	const length = 100000
	parents := make(map[git.ObjectID][]git.ObjectID, length+1)
	for i := 0; i < length; i++ {
		if i == 0 {
			parents[commitID(i)] = nil
		} else {
			parents[commitID(i)] = []git.ObjectID{commitID(i - 1)}
		}
	}
	// A branch that forks off the middle of the chain.
	parents["branch"] = []git.ObjectID{commitID(length / 2)}

	ix := NewIndex(&fakeSource{parents: parents}, noStore())
	ctx := context.Background()

	ancestor, err := ix.IsAncestor(ctx, commitID(0), commitID(length-1))
	require.NoError(t, err)
	require.True(t, ancestor)

	ancestor, err = ix.IsAncestor(ctx, commitID(length-1), commitID(0))
	require.NoError(t, err)
	require.False(t, ancestor)

	bases, err := ix.MergeBases(ctx, commitID(length-1), "branch")
	require.NoError(t, err)
	require.Equal(t, []git.ObjectID{commitID(length / 2)}, bases)

	require.LessOrEqual(t, ix.cache.Len(), maxCachedEntries)
}

// TestIndex_PersistedEntriesAreReused checks that the entries stored by one Index are
// read back by another one instead of being computed from the parents again.
func TestIndex_PersistedEntriesAreReused(t *testing.T) {
	t.Parallel()

	const n = 220
	ctx := context.Background()
	parents := randomDAGWith(rand.New(rand.NewSource(11)), n, hexID)
	store := derived.NewStore(t.TempDir()).Kind(kindName, kindVersion)
	// The tip is the commit with the longest history of the history, so that the walk
	// it causes is long enough to compare the reads.
	tip := hexID(n - 1)
	for i := 0; i < n; i++ {
		if len(bruteAncestors(parents, hexID(i))) > len(bruteAncestors(parents, tip)) {
			tip = hexID(i)
		}
	}
	require.GreaterOrEqual(t, len(bruteAncestors(parents, tip)), 30)

	first := &fakeSource{parents: parents}
	expected, err := NewIndex(first, store).Generation(ctx, tip)
	require.NoError(t, err)
	require.Greater(t, first.calls, 0)

	history := bruteAncestors(parents, tip)
	for id := range history {
		_, found, err := store.Get(id)
		require.NoError(t, err)
		require.True(t, found, "entry of %s is stored", id)
	}

	second := &fakeSource{parents: parents}
	ix := NewIndex(second, store)
	generation, err := ix.Generation(ctx, tip)
	require.NoError(t, err)
	require.Equal(t, expected, generation)
	require.Zero(t, second.calls, "the stored entries are not computed again")

	sets := ancestorSets(parents)
	rnd := rand.New(rand.NewSource(12))
	for k := 0; k < 200; k++ {
		i, j := rnd.Intn(n), rnd.Intn(n)

		isAncestor, err := ix.IsAncestor(ctx, hexID(i), hexID(j))
		require.NoError(t, err)
		require.Equal(t, sets[hexID(j)][hexID(i)], isAncestor)

		bases, err := ix.MergeBases(ctx, hexID(i), hexID(j))
		require.NoError(t, err)
		require.Equal(t, bruteMergeBasesWith(sets, hexID(i), hexID(j)), bases)
	}
}

// TestIndex_CorruptStoredEntryIsRecomputed checks that an undecodable stored value is
// computed again and replaced.
func TestIndex_CorruptStoredEntryIsRecomputed(t *testing.T) {
	t.Parallel()

	ctx := context.Background()
	parents := randomDAGWith(rand.New(rand.NewSource(13)), 50, hexID)
	store := derived.NewStore(t.TempDir()).Kind(kindName, kindVersion)
	tip := hexID(49)

	expected, err := NewIndex(&fakeSource{parents: parents}, store).Generation(ctx, tip)
	require.NoError(t, err)

	require.NoError(t, store.Put(tip, []byte("corrupt")))

	ix := NewIndex(&fakeSource{parents: parents}, store)
	generation, err := ix.Generation(ctx, tip)
	require.NoError(t, err)
	require.Equal(t, expected, generation)

	data, found, err := store.Get(tip)
	require.NoError(t, err)
	require.True(t, found)
	_, err = decodeEntry(data)
	require.NoError(t, err, "the corrupt value is replaced")
}

func TestEntryEncoding(t *testing.T) {
	t.Parallel()

	for _, size := range []int{sha1Size, sha256Size} {
		skipID := func(b byte) git.ObjectID {
			return git.ObjectID(hex.EncodeToString(bytes.Repeat([]byte{b}, size)))
		}

		e := &entry{generation: 42, skips: []git.ObjectID{skipID(1), skipID(2), skipID(3)}}
		data, err := encodeEntry(e)
		require.NoError(t, err)
		require.Len(t, data, encodedHeaderSize+3*size)

		decoded, err := decodeEntry(data)
		require.NoError(t, err)
		require.True(t, decoded.done)
		require.Equal(t, e.generation, decoded.generation)
		require.Equal(t, e.skips, decoded.skips)
	}

	root, err := encodeEntry(&entry{generation: 1, done: true})
	require.NoError(t, err)
	require.Len(t, root, encodedHeaderSize)
	decoded, err := decodeEntry(root)
	require.NoError(t, err)
	require.Equal(t, uint32(1), decoded.generation)
	require.Empty(t, decoded.skips)

	_, err = encodeEntry(&entry{generation: 2, skips: []git.ObjectID{"not-hex"}})
	require.Error(t, err)

	for name, data := range map[string][]byte{
		"too short":          {1, 0, 0},
		"generation zero":    {0, 0, 0, 0, 0},
		"root with trailing": {1, 0, 0, 0, 0, 9},
		"uneven pointers":    append([]byte{2, 0, 0, 0, 2}, make([]byte, 21)...),
		"odd pointer size":   append([]byte{2, 0, 0, 0, 1}, make([]byte, 7)...),
	} {
		_, err := decodeEntry(data)
		require.Error(t, err, name)
	}
}