Skip to content

Git designed for AI agents.

6.4 KB
Raw Blame
package graph

import (
	"bytes"
	"fmt"
	"math/rand"
	"path/filepath"
	"sort"
	"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/testhelper"
	"github.com/feder-cr/git-ai/internal/testhelper/testcfg"
	"github.com/feder-cr/git-ai/proto/go/gitalypb"
	"github.com/stretchr/testify/require"
)

// randomHistory returns the parents of n commits as indexes. Commit 0 is the only
// root, so every pair of commits has a common ancestor and git merge-base always
// prints something.
func randomHistory(rnd *rand.Rand, n int) [][]int {
	parents := make([][]int, n)
	for i := 1; i < n; i++ {
		first := i - 1
		if rnd.Intn(2) == 0 {
			first = rnd.Intn(i)
		}
		parents[i] = []int{first}

		if rnd.Intn(3) == 0 {
			if second := rnd.Intn(i); second != first {
				parents[i] = append(parents[i], second)
			}
		}
	}
	return parents
}

// writeCommits creates the commits with git fast-import. Commit i has the parents
// parents[i], which must be lower indexes, and is also reachable as refs/heads/c<i>.
func writeCommits(tb testing.TB, cfg config.Cfg, repoPath string, parents [][]int) []git.ObjectID {
	tb.Helper()

	var stream bytes.Buffer
	for i, list := range parents {
		name := fmt.Sprintf("c%d", i)
		fmt.Fprintf(&stream, "commit refs/heads/%s\n", name)
		fmt.Fprintf(&stream, "mark :%d\n", i+1)
		fmt.Fprintf(&stream, "committer Tester <[email protected]> %d +0000\n", 1600000000+i)
		fmt.Fprintf(&stream, "data %d\n%s\n", len(name), name)
		for j, parent := range list {
			if j == 0 {
				fmt.Fprintf(&stream, "from :%d\n", parent+1)
			} else {
				fmt.Fprintf(&stream, "merge :%d\n", parent+1)
			}
		}
		stream.WriteString("\n")
	}

	gittest.ExecOpts(tb, cfg, gittest.ExecConfig{Stdin: &stream}, "-C", repoPath, "fast-import", "--quiet")

	ids := make([]git.ObjectID, 0, len(parents))
	for i := range parents {
		ids = append(ids, gittest.ResolveRevision(tb, cfg, repoPath, fmt.Sprintf("refs/heads/c%d", i)))
	}
	return ids
}

// gitAncestors returns the commits that git rev-list prints for id.
func gitAncestors(tb testing.TB, cfg config.Cfg, repoPath string, id git.ObjectID) map[git.ObjectID]bool {
	tb.Helper()

	ancestors := make(map[git.ObjectID]bool)
	for _, line := range splitLines(gittest.Exec(tb, cfg, "-C", repoPath, "rev-list", id.String())) {
		ancestors[git.ObjectID(line)] = true
	}
	return ancestors
}

// gitMergeBases returns the sorted output of git merge-base --all for a and b.
func gitMergeBases(tb testing.TB, cfg config.Cfg, repoPath string, a, b git.ObjectID) []string {
	tb.Helper()

	bases := splitLines(gittest.Exec(tb, cfg, "-C", repoPath, "merge-base", "--all", a.String(), b.String()))
	sort.Strings(bases)
	return bases
}

func splitLines(out []byte) []string {
	var lines []string
	for _, line := range bytes.Split(bytes.TrimSpace(out), []byte("\n")) {
		if len(line) > 0 {
			lines = append(lines, string(line))
		}
	}
	return lines
}

// createRepo creates an empty bare repository with the object format of the test
// configuration.
func createRepo(tb testing.TB, cfg config.Cfg) (*gitalypb.Repository, string) {
	tb.Helper()

	storagePath := cfg.Storages[0].Path
	repo := gittest.InitRepoDir(tb, storagePath, gittest.NewRepositoryName(tb))
	repoPath := filepath.Join(storagePath, repo.GetRelativePath())

	objectFormat := "sha1"
	if gittest.ObjectHashIsSHA256() {
		objectFormat = "sha256"
	}
	gittest.Exec(tb, cfg, "init", "--bare", "--quiet", "--object-format="+objectFormat, repoPath)

	return repo, repoPath
}

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

	ctx := testhelper.Context(t)
	cfg := testcfg.Build(t)
	repoProto, repoPath := createRepo(t, cfg)
	repo := localrepo.NewTestRepo(t, cfg, repoProto)

	rnd := rand.New(rand.NewSource(42))
	const n = 70
	ids := writeCommits(t, cfg, repoPath, randomHistory(rnd, n))

	catfileCache := catfile.NewCache(cfg)
	t.Cleanup(catfileCache.Stop)
	reader, cancel, err := catfileCache.ObjectReader(ctx, repo)
	require.NoError(t, err)
	t.Cleanup(cancel)

	ix := NewIndex(NewCatfileSource(reader), noStore())

	ancestors := make([]map[git.ObjectID]bool, n)
	for i, id := range ids {
		ancestors[i] = gitAncestors(t, cfg, repoPath, id)
	}

	for j := range ids {
		for i := range ids {
			got, err := ix.IsAncestor(ctx, ids[i], ids[j])
			require.NoError(t, err)
			require.Equal(t, ancestors[j][ids[i]], got, "IsAncestor(c%d, c%d)", i, j)
		}
	}

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

		bases, err := ix.MergeBases(ctx, ids[i], ids[j])
		require.NoError(t, err)

		var got []string
		for _, base := range bases {
			got = append(got, base.String())
		}
		sort.Strings(got)

		require.Equal(t, gitMergeBases(t, cfg, repoPath, ids[i], ids[j]), got, "MergeBases(c%d, c%d)", i, j)
	}
}

// TestIndex_MatchesGitOnRandomDAGWithMerges compares the answers with git on a history
// of more than 200 commits with many merges.
func TestIndex_MatchesGitOnRandomDAGWithMerges(t *testing.T) {
	t.Parallel()

	ctx := testhelper.Context(t)
	cfg := testcfg.Build(t)
	repoProto, repoPath := createRepo(t, cfg)
	repo := localrepo.NewTestRepo(t, cfg, repoProto)

	rnd := rand.New(rand.NewSource(9))
	const n = 220
	parents := randomHistory(rnd, n)
	merges := 0
	for _, list := range parents {
		if len(list) > 1 {
			merges++
		}
	}
	require.GreaterOrEqual(t, merges, 20)

	ids := writeCommits(t, cfg, repoPath, parents)

	catfileCache := catfile.NewCache(cfg)
	t.Cleanup(catfileCache.Stop)
	reader, cancel, err := catfileCache.ObjectReader(ctx, repo)
	require.NoError(t, err)
	t.Cleanup(cancel)

	ix := NewIndex(NewCatfileSource(reader), noStore())

	ancestors := make([]map[git.ObjectID]bool, n)
	for i, id := range ids {
		ancestors[i] = gitAncestors(t, cfg, repoPath, id)
	}

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

		got, err := ix.IsAncestor(ctx, ids[i], ids[j])
		require.NoError(t, err)
		require.Equal(t, ancestors[j][ids[i]], got, "IsAncestor(c%d, c%d)", i, j)
	}

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

		bases, err := ix.MergeBases(ctx, ids[i], ids[j])
		require.NoError(t, err)

		var got []string
		for _, base := range bases {
			got = append(got, base.String())
		}
		sort.Strings(got)

		require.Equal(t, gitMergeBases(t, cfg, repoPath, ids[i], ids[j]), got, "MergeBases(c%d, c%d)", i, j)
	}
}