Skip to content

Git designed for AI agents.

12.8 KB
Raw Blame
// Package rebase decides how a change lands onto a branch and replays its commits. Plan makes the
// decision from one listing of the range the change adds, made exact when the change diverges (see
// revrange), and an Engine replays the commits of a rebase through long-lived git helper processes. Together
// they produce the same commits as (*localrepo.Repo).Rebase with reapplied cherry-picks, without
// starting several git processes per commit.
package rebase

import (
	"bytes"
	"context"
	"errors"
	"fmt"
	"time"

	"github.com/feder-cr/git-ai/internal/git"
	"github.com/feder-cr/git-ai/internal/git/localrepo"
	"github.com/feder-cr/git-ai/internal/structerr"
	"github.com/feder-cr/git-ai/proto/go/gitalypb"
)

// mergeStream merges trees. It is implemented by *localrepo.MergeTreeStream.
type mergeStream interface {
	// Merge merges theirs into ours with base as the merge base ("" lets git compute it). A
	// conflicting merge returns *localrepo.MergeTreeConflictError.
	Merge(ctx context.Context, base, ours, theirs git.ObjectID) (git.ObjectID, error)
	Close() error
}

// commitWriter writes commit objects. It is implemented by *localrepo.CommitWriter.
type commitWriter interface {
	// Write returns localrepo.ErrCommitWriterUnsupported when the commit cannot be written by the
	// writer, in which case the commit is written with (*localrepo.Repo).WriteCommit.
	Write(ctx context.Context, cfg localrepo.WriteCommitConfig) (git.ObjectID, error)
	Close() error
}

// backends starts the helper processes of an Engine lazily.
type backends struct {
	newMergeStream  func(ctx context.Context) (mergeStream, error)
	newCommitWriter func(ctx context.Context) (commitWriter, error)
}

// Engine replays commits within one batch attempt using one merge-tree stream and one commit
// writer, started lazily and closed by Close. An Engine is not safe for concurrent use.
//
// The helper processes are started with the context of the call that needs them and die with
// it. A helper whose context is done is replaced by a new one on the next use, so a canceled
// context of one Replay does not fail the later Replay calls of the Engine. A helper that
// fails with an error other than a merge conflict is replaced in the same way, so that one
// failed replay does not fail the replays that follow it.
type Engine struct {
	repo     *localrepo.Repo
	backends backends

	stream mergeStream
	// streamDone is the Done channel of the context the stream was started with.
	streamDone <-chan struct{}

	writer commitWriter
	// writerDone is the Done channel of the context the writer was started with.
	writerDone <-chan struct{}
}

// Option configures an Engine.
type Option func(*engineConfig)

type engineConfig struct {
	helperOpts []localrepo.HelperOption
}

// WithDeferredDurability starts the helper processes without fsync of the loose objects they write.
// The caller takes over their durability: a quarantine's contract is that every object file in it
// is durable before the quarantine migration moves it into the repository, so the caller must make
// the objects durable before the migration, not rely on it. The batch attempts of UserLand do: they
// pack the objects of their quarantine into one fsynced pack before the update (doc/graft/PLAN8.md,
// section 3.2).
func WithDeferredDurability() Option {
	return func(cfg *engineConfig) {
		cfg.helperOpts = append(cfg.helperOpts, localrepo.WithoutObjectFsync())
	}
}

// New returns an Engine for repo.
func New(repo *localrepo.Repo, opts ...Option) *Engine {
	var cfg engineConfig
	for _, opt := range opts {
		opt(&cfg)
	}

	return newEngine(repo, backends{
		newMergeStream: func(ctx context.Context) (mergeStream, error) {
			stream, err := repo.NewMergeTreeStream(ctx, cfg.helperOpts...)
			if err != nil {
				return nil, err
			}
			return stream, nil
		},
		newCommitWriter: func(ctx context.Context) (commitWriter, error) {
			writer, err := repo.NewCommitWriter(ctx, cfg.helperOpts...)
			if err != nil {
				return nil, err
			}
			return writer, nil
		},
	})
}

func newEngine(repo *localrepo.Repo, b backends) *Engine {
	return &Engine{repo: repo, backends: b}
}

// Replay replays the commits of todo, oldest first, onto upstream and returns the last commit
// written, or upstream when every commit became empty and was dropped. It is the replay of
// (*localrepo.Repo).Rebase: a commit whose merge onto the running tip changes nothing is dropped
// unless it is itself empty, each commit keeps its author and message, and its committer is
// committer, or its own committer when committer is nil. A commit that does not apply cleanly
// returns *localrepo.RebaseConflictError. The todo list comes from LandPlan.Replay.
func (e *Engine) Replay(ctx context.Context, upstream git.ObjectID, todo []git.ObjectID, committer *git.Signature) (git.ObjectID, error) {
	objectHash, err := e.repo.ObjectHash(ctx)
	if err != nil {
		return "", structerr.NewInternal("getting object hash %w", err)
	}

	upstreamCommit, err := e.repo.ReadCommit(ctx, git.Revision(upstream))
	if err != nil {
		return "", fmt.Errorf("reading upstream commit: %w", err)
	}

	oursCommitOID := upstream
	oursTreeOID := git.ObjectID(upstreamCommit.GetTreeId())
	for _, todoItem := range todo {
		theirsCommit, err := e.repo.ReadCommit(ctx, git.Revision(todoItem))
		if err != nil {
			return "", fmt.Errorf("reading todo list commit: %w", err)
		}

		var base git.ObjectID
		if len(theirsCommit.GetParentIds()) > 0 {
			base = git.ObjectID(theirsCommit.GetParentIds()[0])
		}

		newTreeOID, err := e.merge(ctx, base, oursCommitOID, git.ObjectID(theirsCommit.GetId()))
		if err != nil {
			var conflictErr *localrepo.MergeTreeConflictError
			if errors.As(err, &conflictErr) {
				return "", &localrepo.RebaseConflictError{
					Commit:        theirsCommit.GetId(),
					ConflictError: conflictErr,
				}
			}
			return "", fmt.Errorf("merging todo list commit: %w", err)
		}

		// Empty commits are handled as in (*localrepo.Repo).Rebase: a commit whose merge changes
		// nothing is picked only if it is itself empty, a root commit excepted when empty.
		if newTreeOID == oursTreeOID {
			if len(theirsCommit.GetParentIds()) == 0 {
				if theirsCommit.GetTreeId() != objectHash.EmptyTreeOID.String() {
					continue
				}
			} else {
				theirsParentCommit, err := e.repo.ReadCommit(ctx, git.Revision(theirsCommit.GetParentIds()[0]))
				if err != nil {
					return "", fmt.Errorf("reading parent commit: %w", err)
				}

				if theirsCommit.GetTreeId() != theirsParentCommit.GetTreeId() {
					continue
				}
			}
		}

		author := signatureFromCommitAuthor(theirsCommit.GetAuthor())
		commitCommitter := committer
		if commitCommitter == nil {
			commitCommitter = signatureFromCommitAuthor(theirsCommit.GetCommitter())
		}

		message, err := e.fullCommitMessage(ctx, theirsCommit)
		if err != nil {
			return "", fmt.Errorf("reading commit message: %w", err)
		}

		newCommitOID, err := e.writeCommit(ctx, localrepo.WriteCommitConfig{
			Parents:        []git.ObjectID{oursCommitOID},
			AuthorName:     author.Name,
			AuthorEmail:    author.Email,
			AuthorDate:     author.When,
			CommitterName:  commitCommitter.Name,
			CommitterEmail: commitCommitter.Email,
			CommitterDate:  commitCommitter.When,
			Message:        string(message),
			TreeID:         newTreeOID,
		})
		if err != nil {
			return "", fmt.Errorf("write commit: %w", err)
		}
		oursCommitOID = newCommitOID
		oursTreeOID = newTreeOID
	}

	return oursCommitOID, nil
}

// Close ends the helper processes started by the Engine. It is safe to call more than once. A
// helper that was already ended by the cancellation of its context is not an error.
func (e *Engine) Close() error {
	var errs []error
	if e.stream != nil {
		errs = append(errs, closeHelper(e.streamDone, e.stream.Close))
		e.stream, e.streamDone = nil, nil
	}
	if e.writer != nil {
		errs = append(errs, closeHelper(e.writerDone, e.writer.Close))
		e.writer, e.writerDone = nil, nil
	}
	return errors.Join(errs...)
}

// closeHelper closes a helper process. The error of a helper whose context is done is dropped,
// because the process was killed by the cancellation.
func closeHelper(done <-chan struct{}, closeFn func() error) error {
	err := closeFn()
	if isDone(done) {
		return nil
	}
	return err
}

// isDone reports whether the channel is closed. A nil channel, the Done channel of a context that
// can never be canceled, is never done.
func isDone(done <-chan struct{}) bool {
	select {
	case <-done:
		return true
	default:
		return false
	}
}

// merge merges theirs into ours with base as the merge base. base is empty for a root commit.
// A merge conflict leaves the stream usable. Any other error ends the stream, because git aborts
// the process on an unmergeable input, and the next merge starts a new stream.
func (e *Engine) merge(ctx context.Context, base, ours, theirs git.ObjectID) (git.ObjectID, error) {
	stream, err := e.getStream(ctx)
	if err != nil {
		return "", fmt.Errorf("starting merge-tree stream: %w", err)
	}

	oid, err := stream.Merge(ctx, base, ours, theirs)
	var conflictErr *localrepo.MergeTreeConflictError
	if err != nil && !errors.As(err, &conflictErr) {
		e.dropStream()
	}

	return oid, err
}

// writeCommit writes the commit with the commit writer and falls back to WriteCommit when the
// writer does not support it. Any other error ends the writer, and the next write starts a new
// one.
func (e *Engine) writeCommit(ctx context.Context, cfg localrepo.WriteCommitConfig) (git.ObjectID, error) {
	writer, err := e.getWriter(ctx)
	if err != nil {
		return "", fmt.Errorf("starting commit writer: %w", err)
	}

	oid, err := writer.Write(ctx, cfg)
	if errors.Is(err, localrepo.ErrCommitWriterUnsupported) {
		return e.repo.WriteCommit(ctx, cfg)
	}
	if err != nil {
		e.dropWriter()
	}

	return oid, err
}

// getStream returns the running merge-tree stream, starting one if there is none or if the
// context the stream was started with is done.
func (e *Engine) getStream(ctx context.Context) (mergeStream, error) {
	if e.stream != nil && isDone(e.streamDone) {
		e.dropStream()
	}

	if e.stream == nil {
		stream, err := e.backends.newMergeStream(ctx)
		if err != nil {
			return nil, err
		}
		e.stream, e.streamDone = stream, ctx.Done()
	}

	return e.stream, nil
}

// getWriter returns the running commit writer, starting one if there is none or if the context
// the writer was started with is done.
func (e *Engine) getWriter(ctx context.Context) (commitWriter, error) {
	if e.writer != nil && isDone(e.writerDone) {
		e.dropWriter()
	}

	if e.writer == nil {
		writer, err := e.backends.newCommitWriter(ctx)
		if err != nil {
			return nil, err
		}
		e.writer, e.writerDone = writer, ctx.Done()
	}

	return e.writer, nil
}

// dropStream closes the merge-tree stream so that the next merge starts a new one. The error of
// closing is dropped: the stream is broken or ended by its context, and the merge that failed
// already reports why.
func (e *Engine) dropStream() {
	_ = closeHelper(e.streamDone, e.stream.Close)
	e.stream, e.streamDone = nil, nil
}

// dropWriter closes the commit writer so that the next write starts a new one. The error of
// closing is dropped for the same reason as in dropStream.
func (e *Engine) dropWriter() {
	_ = closeHelper(e.writerDone, e.writer.Close)
	e.writer, e.writerDone = nil, nil
}

// fullCommitMessage returns the whole message of the commit. ReadCommit cuts the body of commits
// to a maximum size, so the message is read again from the raw object when it was cut.
func (e *Engine) fullCommitMessage(ctx context.Context, commit *gitalypb.GitCommit) ([]byte, error) {
	body := commit.GetBody()
	if int64(len(body)) >= commit.GetBodySize() {
		return body, nil
	}

	object, err := e.repo.ReadObject(ctx, git.ObjectID(commit.GetId()))
	if err != nil {
		return nil, fmt.Errorf("reading commit object: %w", err)
	}

	// The headers end with the first empty line. Continuation lines of multi-line headers, such
	// as signatures, start with a space and so are never empty.
	_, message, found := bytes.Cut(object, []byte("\n\n"))
	if !found || int64(len(message)) != commit.GetBodySize() {
		return nil, fmt.Errorf("commit %s: message of %d bytes does not match its size of %d bytes",
			commit.GetId(), len(message), commit.GetBodySize())
	}

	return message, nil
}

// signatureFromCommitAuthor converts a commit author to a signature, keeping its timezone. It
// mirrors the conversion of (*localrepo.Repo).Rebase.
func signatureFromCommitAuthor(author *gitalypb.CommitAuthor) *git.Signature {
	signature := &git.Signature{
		Name:  string(author.GetName()),
		Email: string(author.GetEmail()),
		When:  time.Now().In(time.UTC),
	}

	if timestamp := author.GetDate(); timestamp != nil {
		signature.When = timestamp.AsTime().In(time.UTC)
	}

	timezone := author.GetTimezone()
	if len(timezone) != 5 {
		return signature
	}

	loc, err := time.Parse("-0700", string(timezone))
	if err != nil {
		return signature
	}

	signature.When = signature.When.In(loc.Location())

	return signature
}