Skip to content

Git designed for AI agents.

14.8 KB
Raw Blame
package rebase

import (
	"context"
	"errors"
	"fmt"
	"maps"
	"math/rand"
	"slices"
	"strings"
	"testing"

	"github.com/feder-cr/git-ai/internal/featureflag"
	"github.com/feder-cr/git-ai/internal/git"
	"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/ancestry"
	"github.com/feder-cr/git-ai/internal/testhelper"
	"github.com/feder-cr/git-ai/internal/testhelper/testcfg"
	"github.com/stretchr/testify/require"
)

var testCommitter = git.Signature{
	Name:  gittest.DefaultCommitterName,
	Email: gittest.DefaultCommitterMail,
	When:  gittest.DefaultCommitTime,
}

// state maps file names to contents. It is the whole tree of a commit written by fixture.commit.
type state map[string]string

func (s state) entries() []gittest.TreeEntry {
	var entries []gittest.TreeEntry
	for _, name := range slices.Sorted(maps.Keys(s)) {
		entries = append(entries, gittest.TreeEntry{Mode: "100644", Path: name, Content: s[name]})
	}
	return entries
}

// fixture is a repository with a helper to write commits into it.
type fixture struct {
	tb       testing.TB
	ctx      context.Context
	cfg      config.Cfg
	repo     *localrepo.Repo
	repoPath string
}

func newFixture(tb testing.TB) *fixture {
	tb.Helper()

	ctx := featureflag.ContextWithFeatureFlag(testhelper.Context(tb), featureflag.GPGSigning, false)
	cfg := testcfg.Build(tb)
	repoProto, repoPath := gittest.CreateRepository(tb, ctx, cfg, gittest.CreateRepositoryConfig{
		SkipCreationViaService: true,
	})

	return &fixture{
		tb:       tb,
		ctx:      ctx,
		cfg:      cfg,
		repo:     localrepo.NewTestRepo(tb, cfg, repoProto),
		repoPath: repoPath,
	}
}

// commit writes a commit whose tree holds exactly the files of s.
func (f *fixture) commit(s state, message string, parents ...git.ObjectID) git.ObjectID {
	f.tb.Helper()

	return gittest.WriteCommit(f.tb, f.cfg, f.repoPath,
		gittest.WithMessage(message),
		gittest.WithTreeEntries(s.entries()...),
		gittest.WithParents(parents...),
	)
}

// buildHistories writes a random upstream and branch history with a seeded generator. The
// histories conflict on some files, contain empty commits, clean cherry-picks of upstream
// content, and merges of side branches within the rebased range.
func buildHistories(f *fixture, rng *rand.Rand) (upstream, branch git.ObjectID) {
	files := []string{"f0", "f1", "f2", "f3", "f4"}
	pick := func() string { return files[rng.Intn(len(files))] }

	base := state{"a": "base\n"}
	baseOID := f.commit(base, "base")

	up := maps.Clone(base)
	upTip := baseOID
	for i := range 3 + rng.Intn(3) {
		up[pick()] = fmt.Sprintf("upstream %d %d\n", i, rng.Intn(3))
		upTip = f.commit(up, fmt.Sprintf("upstream %d", i), upTip)
	}

	br := maps.Clone(base)
	brTip := baseOID
	side := maps.Clone(base)
	sideTip := baseOID
	for i := range 5 + rng.Intn(4) {
		switch rng.Intn(10) {
		case 0: // empty commit
			brTip = f.commit(br, fmt.Sprintf("empty %d", i), brTip)
		case 1: // clean cherry-pick of upstream content
			if v, ok := up[pick()]; ok {
				br[pick()] = v
			}
			brTip = f.commit(br, fmt.Sprintf("cherry %d", i), brTip)
		case 2: // merge of a side branch
			side[pick()] = fmt.Sprintf("side %d %d\n", i, rng.Intn(3))
			sideTip = f.commit(side, fmt.Sprintf("side %d", i), sideTip)

			br[pick()] = fmt.Sprintf("merged %d\n", i)
			brTip = f.commit(br, fmt.Sprintf("merge %d", i), brTip, sideTip)
		default:
			br[pick()] = fmt.Sprintf("branch %d %d\n", i, rng.Intn(3))
			brTip = f.commit(br, fmt.Sprintf("branch %d", i), brTip)
		}
	}

	return upTip, brTip
}

// landRebase rebases branch onto upstream the way landing does: the plan and the replay of the
// engine. Like (*localrepo.Repo).Rebase it returns branch when upstream is
// reachable from it and upstream when branch is reachable from upstream.
func landRebase(ctx context.Context, repo *localrepo.Repo, engine *Engine, upstream, branch git.ObjectID, committer *git.Signature) (git.ObjectID, error) {
	plan, err := Plan(ctx, ancestry.Git(repo), upstream, branch)
	if err != nil {
		return "", err
	}

	switch plan.Kind() {
	case LandAlreadyLanded:
		return upstream, nil
	case LandFastForward:
		return branch, nil
	}

	todo, err := plan.Replay()
	if err != nil {
		return "", err
	}

	return engine.Replay(ctx, upstream, todo, committer)
}

// rebaseOptions returns the options of (*localrepo.Repo).Rebase that landing uses: reapplied
// cherry-picks, and the committer when it is set.
func rebaseOptions(committer *git.Signature) []localrepo.RebaseOption {
	opts := []localrepo.RebaseOption{localrepo.RebaseWithReappliedCherryPicks()}
	if committer != nil {
		opts = append(opts, localrepo.RebaseWithCommitter(*committer))
	}
	return opts
}

// hasMergesInRange reports whether git rev-list --merges upstream..branch lists a commit, which is
// how landing found merge commits before the plan.
func hasMergesInRange(t *testing.T, f *fixture, upstream, branch git.ObjectID) bool {
	t.Helper()
	return strings.TrimSpace(string(gittest.Exec(t, f.cfg, "-C", f.repoPath, "rev-list", "--merges", upstream.String()+".."+branch.String()))) != ""
}

// requireSameRebase rebases with landRebase and with localrepo and requires the same outcome: the
// same object ID, or an error from both, with the same conflicting commit and conflict contents for
// a conflict. It returns the error of the localrepo rebase.
func requireSameRebase(t *testing.T, f *fixture, engine *Engine, upstream, branch git.ObjectID, committer *git.Signature) error {
	t.Helper()

	wantOID, wantErr := f.repo.Rebase(f.ctx, upstream.String(), branch.String(), rebaseOptions(committer)...)
	gotOID, gotErr := landRebase(f.ctx, f.repo, engine, upstream, branch, committer)

	require.Equal(t, wantOID, gotOID)
	if wantErr == nil {
		require.NoError(t, gotErr)
		return nil
	}
	require.Error(t, gotErr)

	var wantConflict, gotConflict *localrepo.RebaseConflictError
	if errors.As(wantErr, &wantConflict) {
		require.ErrorAs(t, gotErr, &gotConflict)
		require.Equal(t, wantConflict.Commit, gotConflict.Commit)
		require.Equal(t, wantConflict.ConflictError, gotConflict.ConflictError)
	}

	return wantErr
}

// TestEngineReplayMatchesLocalrepo rebases random histories the way landing does and with
// localrepo. A range with merge commits is refused by the plan, as landing refused it before with
// git rev-list --merges; every other range gives the commits of localrepo, or its conflict.
func TestEngineReplayMatchesLocalrepo(t *testing.T) {
	t.Parallel()

	var conflicts, successes, merges int
	for seed := int64(1); seed <= 40; seed++ {
		f := newFixture(t)
		rng := rand.New(rand.NewSource(seed))
		upstream, branch := buildHistories(f, rng)

		engine := New(f.repo)
		t.Cleanup(func() { require.NoError(t, engine.Close()) })

		var committer *git.Signature
		if seed%2 == 1 {
			committer = &testCommitter
		}

		t.Run(fmt.Sprintf("seed %d", seed), func(t *testing.T) {
			if hasMergesInRange(t, f, upstream, branch) {
				merges++
				_, err := landRebase(f.ctx, f.repo, engine, upstream, branch, committer)
				require.ErrorIs(t, err, ErrMergesInRange)
				return
			}

			err := requireSameRebase(t, f, engine, upstream, branch, committer)

			var conflictErr *localrepo.RebaseConflictError
			switch {
			case errors.As(err, &conflictErr):
				conflicts++
			case err == nil:
				successes++
			}
		})
	}

	require.Positive(t, conflicts, "the seeds must cover conflicts")
	require.Positive(t, successes, "the seeds must cover successful rebases")
	require.Positive(t, merges, "the seeds must cover ranges with merge commits")
}

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

	f := newFixture(t)
	upstream := f.commit(state{"a": "upstream\n"}, "upstream")
	branch := f.commit(state{"b": "branch\n"}, "unrelated root")

	engine := New(f.repo)
	t.Cleanup(func() { require.NoError(t, engine.Close()) })

	// Without a merge base localrepo fails in its merge-base lookup, and the plan refuses the range.
	require.Error(t, requireSameRebase(t, f, engine, upstream, branch, &testCommitter))
	_, err := landRebase(f.ctx, f.repo, engine, upstream, branch, &testCommitter)
	require.ErrorIs(t, err, ErrUnrelated)
}

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

	f := newFixture(t)
	base := f.commit(state{"a": "base\n"}, "base")
	upstream := f.commit(state{"a": "base\n", "u": "upstream\n"}, "upstream", base)
	longMessage := "long\n\n" + strings.Repeat("0123456789abcdef\n", 2000)
	branch := f.commit(state{"a": "base\n", "b": "branch\n"}, longMessage, base)

	engine := New(f.repo)
	t.Cleanup(func() { require.NoError(t, engine.Close()) })

	require.NoError(t, requireSameRebase(t, f, engine, upstream, branch, nil))
}

// fakeBackends counts the helper processes started and the operations done through them. Merges
// are done by the real merge-tree stream and commits by the real commit writer, unless the writer
// is made to report ErrCommitWriterUnsupported, in which case the commit goes through WriteCommit.
type fakeBackends struct {
	repo *localrepo.Repo

	unsupported bool // the commit writer reports localrepo.ErrCommitWriterUnsupported
	streamErr   error

	streamStarts, writerStarts int
	streamClosed, writerClosed int
	merges, writes             int
}

func (fb *fakeBackends) backends() backends {
	return backends{
		newMergeStream: func(ctx context.Context) (mergeStream, error) {
			fb.streamStarts++
			if fb.streamErr != nil {
				return nil, fb.streamErr
			}

			stream, err := fb.repo.NewMergeTreeStream(ctx)
			if err != nil {
				return nil, err
			}
			return &fakeStream{fb: fb, stream: stream}, nil
		},
		newCommitWriter: func(ctx context.Context) (commitWriter, error) {
			fb.writerStarts++

			writer, err := fb.repo.NewCommitWriter(ctx)
			if err != nil {
				return nil, err
			}
			return &fakeWriter{fb: fb, writer: writer}, nil
		},
	}
}

type fakeStream struct {
	fb     *fakeBackends
	stream *localrepo.MergeTreeStream
}

func (s *fakeStream) Merge(ctx context.Context, base, ours, theirs git.ObjectID) (git.ObjectID, error) {
	s.fb.merges++
	return s.stream.Merge(ctx, base, ours, theirs)
}

func (s *fakeStream) Close() error {
	s.fb.streamClosed++
	return s.stream.Close()
}

type fakeWriter struct {
	fb     *fakeBackends
	writer *localrepo.CommitWriter
}

func (w *fakeWriter) Write(ctx context.Context, cfg localrepo.WriteCommitConfig) (git.ObjectID, error) {
	w.fb.writes++
	if w.fb.unsupported {
		return "", localrepo.ErrCommitWriterUnsupported
	}
	return w.writer.Write(ctx, cfg)
}

func (w *fakeWriter) Close() error {
	w.fb.writerClosed++
	return w.writer.Close()
}

// linearBranches returns an upstream with one commit on base and a branch with three commits on
// base that touch other files, so that the rebase needs three merges and three writes.
func linearBranches(f *fixture) (base, upstream, branch git.ObjectID) {
	base = f.commit(state{"a": "base\n"}, "base")
	upstream = f.commit(state{"a": "base\n", "u": "upstream\n"}, "upstream", base)

	tip := base
	s := state{"a": "base\n"}
	for i := range 3 {
		s[fmt.Sprintf("b%d", i)] = fmt.Sprintf("branch %d\n", i)
		tip = f.commit(s, fmt.Sprintf("branch %d", i), tip)
	}

	return base, upstream, tip
}

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

	f := newFixture(t)
	base, upstream, branch := linearBranches(f)

	fb := &fakeBackends{repo: f.repo}
	engine := newEngine(f.repo, fb.backends())

	// A fast-forward, as the base is an ancestor of the branch, needs no helper process.
	oid, err := landRebase(f.ctx, f.repo, engine, base, branch, nil)
	require.NoError(t, err)
	require.Equal(t, branch, oid)
	require.Zero(t, fb.streamStarts)
	require.Zero(t, fb.writerStarts)

	// A real rebase starts one helper of each kind, once.
	oid, err = landRebase(f.ctx, f.repo, engine, upstream, branch, &testCommitter)
	require.NoError(t, err)
	require.NotEmpty(t, oid)
	require.Equal(t, 1, fb.streamStarts)
	require.Equal(t, 1, fb.writerStarts)
	require.Equal(t, 3, fb.merges)
	require.Equal(t, 3, fb.writes)

	require.NoError(t, engine.Close())
	require.Equal(t, 1, fb.streamClosed)
	require.Equal(t, 1, fb.writerClosed)

	// Close is idempotent and closes nothing more.
	require.NoError(t, engine.Close())
	require.Equal(t, 1, fb.streamClosed)
	require.Equal(t, 1, fb.writerClosed)
}

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

	f := newFixture(t)
	fb := &fakeBackends{repo: f.repo}
	engine := newEngine(f.repo, fb.backends())

	require.NoError(t, engine.Close())
	require.Zero(t, fb.streamStarts+fb.writerStarts+fb.streamClosed+fb.writerClosed)
}

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

	f := newFixture(t)
	_, upstream, branch := linearBranches(f)

	fb := &fakeBackends{repo: f.repo, unsupported: true}
	engine := newEngine(f.repo, fb.backends())
	t.Cleanup(func() { require.NoError(t, engine.Close()) })

	require.NoError(t, requireSameRebase(t, f, engine, upstream, branch, &testCommitter))
	require.Equal(t, 3, fb.writes, "every commit is offered to the writer first")
}

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

	f := newFixture(t)
	_, upstream, branch := linearBranches(f)

	startErr := errors.New("no merge-tree stream")
	fb := &fakeBackends{repo: f.repo, streamErr: startErr}
	engine := newEngine(f.repo, fb.backends())
	t.Cleanup(func() { require.NoError(t, engine.Close()) })

	_, err := landRebase(f.ctx, f.repo, engine, upstream, branch, nil)
	require.ErrorIs(t, err, startErr)
	require.Zero(t, fb.writes)
}

func BenchmarkRebaseEngine(b *testing.B) {
	benchmarkRebase(b, func(f *fixture, upstream, branch git.ObjectID) {
		// The fake backends count the helper processes the engine starts. The git command that lists
		// the range and the object reads are not counted.
		fb := &fakeBackends{repo: f.repo}
		engine := newEngine(f.repo, fb.backends())
		defer func() { require.NoError(b, engine.Close()) }()

		var iterations int
		for b.Loop() {
			iterations++
			if _, err := landRebase(f.ctx, f.repo, engine, upstream, branch, &testCommitter); err != nil {
				b.Fatal(err)
			}
		}

		b.ReportMetric(float64(fb.streamStarts+fb.writerStarts)/float64(iterations), "helper-starts/op")
	})
}

func BenchmarkLocalrepoRebase(b *testing.B) {
	benchmarkRebase(b, func(f *fixture, upstream, branch git.ObjectID) {
		for b.Loop() {
			if _, err := f.repo.Rebase(f.ctx, upstream.String(), branch.String(), rebaseOptions(&testCommitter)...); err != nil {
				b.Fatal(err)
			}
		}
	})
}

// benchmarkRebase rebases a 40 commit chain onto a single upstream commit.
func benchmarkRebase(b *testing.B, run func(f *fixture, upstream, branch git.ObjectID)) {
	f := newFixture(b)

	base := f.commit(state{"a": "base\n"}, "base")
	upstream := f.commit(state{"a": "base\n", "u": "upstream\n"}, "upstream", base)

	s := state{"a": "base\n"}
	tip := base
	for i := range 40 {
		s[fmt.Sprintf("b%02d", i)] = fmt.Sprintf("member %d\n", i)
		tip = f.commit(s, fmt.Sprintf("member %d", i), tip)
	}

	b.ResetTimer()
	run(f, upstream, tip)
}