Skip to content

Git designed for AI agents.

11.6 KB
Raw Blame
// Black-box spec tests for WP25 (graph kind), written from PLAN3.md only.
//
// ADAPTATION POINTS (adapted at the WP25 gate to the binding API of the
// RECONCILIATION section, which keeps the draft Index):
//   - newSpecStore: derived.NewStore over a temp dir.
//   - specIndex: NewIndex(NewCatfileSource(reader), store.Kind("graph", 1)).
//   - Module path github.com/feder-cr/git-ai.
//   - MergeBase(ctx, a, b) (git.ObjectID, error); the empty ID means no base.
package graph

import (
	"encoding/binary"
	"encoding/hex"
	"fmt"
	"math/rand"
	"os/exec"
	"slices"
	"strings"
	"testing"

	"github.com/feder-cr/git-ai/internal/git"
	"github.com/feder-cr/git-ai/internal/git/catfile"
	"github.com/feder-cr/git-ai/internal/git/gittest"
	"github.com/feder-cr/git-ai/internal/git/localrepo"
	"github.com/feder-cr/git-ai/internal/gitaly/config"
	"github.com/feder-cr/git-ai/internal/graft/derived"
	"github.com/feder-cr/git-ai/internal/testhelper"
	"github.com/feder-cr/git-ai/internal/testhelper/testcfg"
	"github.com/feder-cr/git-ai/proto/go/gitalypb"
	"github.com/stretchr/testify/require"
)

// specRepo is a repository plus the recorded DAG used as ground truth.
type specRepo struct {
	cfg     config.Cfg
	repo    *gitalypb.Repository
	path    string
	ids     []git.ObjectID // commits in creation order (parents always precede children)
	gen     []uint32       // expected generation, computed from the recorded parents
	indexOf map[git.ObjectID]int
}

// newSpecRepo creates a repository and n random commits (merges included).
// If roots is true, a few commits are unrelated roots. n == 0 yields an empty repo.
func newSpecRepo(t *testing.T, n int, seed int64, roots bool) *specRepo {
	t.Helper()
	cfg := testcfg.Build(t)
	repo, path := gittest.CreateRepository(t, testhelper.Context(t), cfg, gittest.CreateRepositoryConfig{
		SkipCreationViaService: true,
	})
	sr := &specRepo{cfg: cfg, repo: repo, path: path, indexOf: map[git.ObjectID]int{}}

	rng := rand.New(rand.NewSource(seed))
	for i := 0; i < n; i++ {
		var parents []git.ObjectID
		if i > 0 && !(roots && rng.Float64() < 0.03) {
			parents = append(parents, sr.ids[rng.Intn(i)])
			if rng.Float64() < 0.3 {
				if q := sr.ids[rng.Intn(i)]; q != parents[0] {
					parents = append(parents, q) // merge commit
				}
			}
		}
		id := sr.commit(t, fmt.Sprintf("c%d", i), parents...)
		sr.gen = append(sr.gen, sr.expectedGen(parents))
		sr.indexOf[id] = i
		sr.ids = append(sr.ids, id)
	}
	return sr
}

func (sr *specRepo) commit(t *testing.T, msg string, parents ...git.ObjectID) git.ObjectID {
	t.Helper()
	return gittest.WriteCommit(t, sr.cfg, sr.path,
		gittest.WithMessage(msg),
		gittest.WithParents(parents...),
	)
}

func (sr *specRepo) expectedGen(parents []git.ObjectID) uint32 {
	g := uint32(1)
	for _, p := range parents {
		if pg := sr.gen[sr.indexOf[p]]; pg+1 > g {
			g = pg + 1
		}
	}
	return g
}

// specIndex builds the graph index for the repository.
// ADAPT: source/store construction is not fixed by the spec.
func specIndex(t *testing.T, sr *specRepo) (*Index, derived.KindStore) {
	t.Helper()
	store := newSpecStore(t)
	kind := store.Kind("graph", 1)
	repo := localrepo.NewTestRepo(t, sr.cfg, sr.repo)
	catfileCache := catfile.NewCache(sr.cfg)
	t.Cleanup(catfileCache.Stop)
	reader, cancel, err := catfileCache.ObjectReader(testhelper.Context(t), repo)
	require.NoError(t, err)
	t.Cleanup(cancel)
	idx := NewIndex(NewCatfileSource(reader), kind)
	return idx, kind
}

// newSpecStore is an ADAPT point: returns a derived store backed by a temp dir.
func newSpecStore(t *testing.T) *derived.Store {
	t.Helper()
	return derived.NewStore(t.TempDir())
}

// gitRun runs git -C repoPath args and returns trimmed stdout and the exit code.
func gitRun(t *testing.T, cfg config.Cfg, repoPath string, args ...string) (string, int) {
	t.Helper()
	cmd := gittest.NewCommand(t, cfg, append([]string{"-C", repoPath}, args...)...)
	out, err := cmd.Output()
	if err != nil {
		if exitErr, ok := err.(*exec.ExitError); ok {
			return strings.TrimSpace(string(out)), exitErr.ExitCode()
		}
		require.NoError(t, err)
	}
	return strings.TrimSpace(string(out)), 0
}

// gitIsAncestor is the ground truth for IsAncestor.
func gitIsAncestor(t *testing.T, cfg config.Cfg, repoPath string, a, b git.ObjectID) bool {
	t.Helper()
	_, code := gitRun(t, cfg, repoPath, "merge-base", "--is-ancestor", a.String(), b.String())
	require.Contains(t, []int{0, 1}, code, "unexpected git exit code")
	return code == 0
}

// gitMergeBaseAll is the ground truth for best common ancestors (empty if none).
func gitMergeBaseAll(t *testing.T, cfg config.Cfg, repoPath string, a, b git.ObjectID) map[string]bool {
	t.Helper()
	out, code := gitRun(t, cfg, repoPath, "merge-base", "--all", a.String(), b.String())
	set := map[string]bool{}
	if code == 1 {
		return set
	}
	require.Equal(t, 0, code, "git merge-base --all failed")
	for _, line := range strings.Split(out, "\n") {
		if line != "" {
			set[line] = true
		}
	}
	return set
}

func TestSpecGenerationRootAndMerge(t *testing.T) {
	ctx := testhelper.Context(t)
	sr := newSpecRepo(t, 0, 0, false)

	// Hand-built: r; a<-r; b<-a; c<-r; m = merge(b, c).
	r := sr.commit(t, "r")
	a := sr.commit(t, "a", r)
	b := sr.commit(t, "b", a)
	c := sr.commit(t, "c", r)
	m := sr.commit(t, "m", b, c)

	idx, _ := specIndex(t, sr)
	want := map[git.ObjectID]uint32{r: 1, a: 2, b: 3, c: 2, m: 4}
	for id, w := range want {
		got, err := idx.Generation(ctx, id)
		require.NoError(t, err)
		require.Equal(t, w, got, "generation of %s: root must be 1, child 1+parent, merge 1+max(parents)", id)
	}
}

func TestSpecGenerationMatchesRecordedDAG(t *testing.T) {
	ctx := testhelper.Context(t)
	sr := newSpecRepo(t, 220, 7, true)
	idx, _ := specIndex(t, sr)

	for i, id := range sr.ids {
		got, err := idx.Generation(ctx, id)
		require.NoError(t, err)
		require.Equal(t, sr.gen[i], got, "generation mismatch for commit %d (%s)", i, id)
	}
}

func TestSpecIsAncestorReflexiveAndBasic(t *testing.T) {
	ctx := testhelper.Context(t)
	sr := newSpecRepo(t, 0, 0, false)
	r := sr.commit(t, "r")
	x := sr.commit(t, "x", r)
	y := sr.commit(t, "y", x)
	other := sr.commit(t, "other")

	idx, _ := specIndex(t, sr)

	ok, err := idx.IsAncestor(ctx, y, y)
	require.NoError(t, err)
	require.True(t, ok, "a commit must be an ancestor of itself")

	ok, err = idx.IsAncestor(ctx, r, y)
	require.NoError(t, err)
	require.True(t, ok, "root must be an ancestor of descendant")

	ok, err = idx.IsAncestor(ctx, y, r)
	require.NoError(t, err)
	require.False(t, ok, "descendant must not be an ancestor of its ancestor")

	ok, err = idx.IsAncestor(ctx, other, y)
	require.NoError(t, err)
	require.False(t, ok, "unrelated history must not be an ancestor")
}

func TestSpecIsAncestorAgainstGit(t *testing.T) {
	ctx := testhelper.Context(t)
	sr := newSpecRepo(t, 220, 11, true)
	idx, _ := specIndex(t, sr)

	rng := rand.New(rand.NewSource(99))
	for i := 0; i < 400; i++ {
		a := sr.ids[rng.Intn(len(sr.ids))]
		b := sr.ids[rng.Intn(len(sr.ids))]
		want := gitIsAncestor(t, sr.cfg, sr.path, a, b)
		got, err := idx.IsAncestor(ctx, a, b)
		require.NoError(t, err)
		require.Equal(t, want, got, "IsAncestor(%s, %s) disagrees with git merge-base --is-ancestor", a, b)
	}
}

func TestSpecMergeBaseIsBestCommonAncestor(t *testing.T) {
	ctx := testhelper.Context(t)
	sr := newSpecRepo(t, 220, 23, true)
	idx, _ := specIndex(t, sr)

	rng := rand.New(rand.NewSource(5))
	for i := 0; i < 300; i++ {
		a := sr.ids[rng.Intn(len(sr.ids))]
		b := sr.ids[rng.Intn(len(sr.ids))]
		best := gitMergeBaseAll(t, sr.cfg, sr.path, a, b)

		base, err := idx.MergeBase(ctx, a, b)
		require.NoError(t, err)
		ok := base != ""
		if len(best) == 0 {
			require.False(t, ok, "MergeBase(%s, %s) must report no base for disjoint histories", a, b)
			continue
		}
		require.True(t, ok, "MergeBase(%s, %s) must find a base", a, b)
		// On criss-cross histories any best base is acceptable; it must be one
		// of the bases git reports as best (non-redundant common ancestors).
		require.True(t, best[base.String()],
			"MergeBase(%s, %s) = %s is not among git's best common ancestors %v", a, b, base, best)
	}
}

func TestSpecMergeBaseDisjointHistories(t *testing.T) {
	ctx := testhelper.Context(t)
	sr := newSpecRepo(t, 0, 0, false)
	x := sr.commit(t, "x")
	xc := sr.commit(t, "xc", x)
	y := sr.commit(t, "y")

	idx, _ := specIndex(t, sr)
	base, err := idx.MergeBase(ctx, xc, y)
	require.NoError(t, err)
	ok := base != ""
	require.False(t, ok, "two unrelated roots have no merge base, got %s", base)
}

func TestSpecDeepLinearHistoryNoRecursion(t *testing.T) {
	if testing.Short() {
		t.Skip("5,000-commit history is slow to build; skipped in -short mode")
	}
	ctx := testhelper.Context(t)
	const depth = 5000
	sr := newLinearSpecRepo(t, depth)
	idx, _ := specIndex(t, sr)

	tip := sr.ids[depth-1]
	root := sr.ids[0]

	g, err := idx.Generation(ctx, tip)
	require.NoError(t, err)
	require.Equal(t, uint32(depth), g, "tip of a linear history of %d commits must have generation %d", depth, depth)

	ok, err := idx.IsAncestor(ctx, root, tip)
	require.NoError(t, err)
	require.True(t, ok, "root must be an ancestor of tip on a 5,000-deep chain")

	ok, err = idx.IsAncestor(ctx, tip, root)
	require.NoError(t, err)
	require.False(t, ok)

	mid := sr.ids[depth/2]
	base, err := idx.MergeBase(ctx, mid, tip)
	require.NoError(t, err)
	found := base != ""
	require.True(t, found)
	require.Equal(t, mid, base, "merge base of an ancestor and its descendant is the ancestor")
}

// newLinearSpecRepo builds a straight chain of n commits.
func newLinearSpecRepo(t *testing.T, n int) *specRepo {
	t.Helper()
	sr := newSpecRepo(t, 0, 0, false)
	var prev git.ObjectID
	for i := 0; i < n; i++ {
		var parents []git.ObjectID
		if i > 0 {
			parents = []git.ObjectID{prev}
		}
		prev = sr.commit(t, fmt.Sprintf("l%d", i), parents...)
		sr.gen = append(sr.gen, sr.expectedGen(parents))
		sr.indexOf[prev] = i
		sr.ids = append(sr.ids, prev)
	}
	return sr
}

func TestSpecStoredValueBinaryFormat(t *testing.T) {
	ctx := testhelper.Context(t)
	sr := newSpecRepo(t, 0, 0, false)
	c0 := sr.commit(t, "c0")
	c1 := sr.commit(t, "c1", c0)
	c2 := sr.commit(t, "c2", c1)
	c3 := sr.commit(t, "c3", c2)

	idx, kind := specIndex(t, sr)
	g, err := idx.Generation(ctx, c3)
	require.NoError(t, err)
	require.Equal(t, uint32(4), g)

	oidLen := len(c0.String()) / 2
	raw := func(id git.ObjectID) []byte {
		b, err := hex.DecodeString(id.String())
		require.NoError(t, err)
		return b
	}
	wantGen := map[git.ObjectID]uint32{c0: 1, c1: 2, c2: 3, c3: 4}

	for id, wg := range wantGen {
		val, found, err := kind.Get(id)
		require.NoError(t, err)
		require.True(t, found, "computed entry for %s must be persisted under kind graph v1", id)
		require.GreaterOrEqual(t, len(val), 5, "value must hold uint32 generation and uint8 count")

		// uint32 generation, little-endian, first; then uint8 n; then n object IDs.
		require.Equal(t, wg, binary.LittleEndian.Uint32(val[0:4]), "little-endian generation of %s", id)
		n := int(val[4])
		require.Len(t, val, 5+n*oidLen, "encoded length must be 5 + n object IDs for %s", id)
	}

	// c3: skip[0] = first parent c2, skip[1] = distance-2 ancestor c1.
	val, _, err := kind.Get(c3)
	require.NoError(t, err)
	n := int(val[4])
	require.GreaterOrEqual(t, n, 2, "c3 has ancestors at distances 1 and 2, so n must be at least 2")
	require.Equal(t, raw(c2), val[5:5+oidLen], "skip[0] must be the first parent")
	require.Equal(t, raw(c1), val[5+oidLen:5+2*oidLen], "skip[1] must be the distance-2 first-parent ancestor")

	// Root has no ancestors, so n is zero.
	rootVal, _, err := kind.Get(c0)
	require.NoError(t, err)
	require.Equal(t, byte(0), rootVal[4], "root must store zero skip pointers")
}

func TestSpecGraphWarmerRegistered(t *testing.T) {
	require.True(t, slices.Contains(derived.Warmers(), "graph"),
		"the graph kind must register an eager warmer named \"graph\" from init(); got %v", derived.Warmers())
}