conflicts: Introduce and use `conflictFilesWithGitMergeTree`

The current implementation of `ListConflictFiles` uses Git2Go to find
the file conflicts, parses this data and returns the information to the
client.

As part of the plan to move away from Git2Go, we introduce a new
function `conflictFilesWithGitMergeTree` which uses git-merge-tree(1) to
find the conflicted files. We then use this implementation behind the
`ListConflictFilesMergeTree` featureflag.

2 files changed, 252 insertions, 21 deletions

diff --git a/internal/gitaly/service/conflicts/list_conflict_files.go b/internal/gitaly/service/conflicts/list_conflict_files.go
index 823198c43..c10ee8c0f 100644
--- a/internal/gitaly/service/conflicts/list_conflict_files.go
+++ b/internal/gitaly/service/conflicts/list_conflict_files.go
@@ -8,6 +8,7 @@ import (
 	"io"
 	"unicode/utf8"
 
+	"gitlab.com/gitlab-org/gitaly/v16/internal/featureflag"
 	"gitlab.com/gitlab-org/gitaly/v16/internal/git"
 	"gitlab.com/gitlab-org/gitaly/v16/internal/git/localrepo"
 	"gitlab.com/gitlab-org/gitaly/v16/internal/git2go"
@@ -41,9 +42,170 @@ func (s *server) ListConflictFiles(request *gitalypb.ListConflictFilesRequest, s
 		return err
 	}
 
+	if featureflag.ListConflictFilesMergeTree.IsEnabled(ctx) {
+		return s.conflictFilesWithGitMergeTree(ctx, request, stream, ours, theirs, repo)
+	}
+
 	return s.conflictFilesWithGit2Go(ctx, request, stream, ours, theirs, repo, repoPath)
 }
 
+func (s *server) conflictFilesWithGitMergeTree(
+	ctx context.Context,
+	request *gitalypb.ListConflictFilesRequest,
+	stream gitalypb.ConflictsService_ListConflictFilesServer,
+	ours, theirs git.ObjectID,
+	repo *localrepo.Repo,
+) error {
+	var mergeConflictErr *localrepo.MergeTreeConflictError
+
+	oid, err := repo.MergeTree(ctx, ours.String(), theirs.String(), localrepo.WithAllowUnrelatedHistories())
+	if err == nil {
+		// When there are no errors, it denotes that there are no conflicts.
+		return nil
+	} else if !errors.As(err, &mergeConflictErr) {
+		// If its not a conflict, we return the error to the user.
+		return structerr.NewInternal("couldn't find conflict: %w", err)
+	}
+
+	type conflictHeader struct {
+		theirPath    string
+		ourPath      string
+		ancestorPath string
+		ourMode      int32
+	}
+
+	objectReader, cancel, err := s.catfileCache.ObjectReader(ctx, repo)
+	if err != nil {
+		return err
+	}
+	defer cancel()
+
+	// We need to combine data with same path, but we also want to retain
+	// the ordering. We use a map to track the data with the same path, but
+	// retain ordering by using a slice.
+	pathToConflict := make(map[string]*conflictHeader)
+	var conflicts []*conflictHeader
+
+	for _, conflictFile := range mergeConflictErr.ConflictingFileInfo {
+		val, ok := pathToConflict[conflictFile.FileName]
+		if !ok {
+			val = &conflictHeader{}
+			conflicts = append(conflicts, val)
+		}
+
+		switch conflictFile.Stage {
+		case localrepo.MergeStageAncestor:
+			val.ancestorPath = conflictFile.FileName
+		case localrepo.MergeStageOurs:
+			val.ourPath = conflictFile.FileName
+			val.ourMode = conflictFile.Mode
+		case localrepo.MergeStageTheirs:
+			val.theirPath = conflictFile.FileName
+		}
+
+		pathToConflict[conflictFile.FileName] = val
+	}
+
+	var conflictFiles []*gitalypb.ConflictFile
+	msgSize := 0
+
+	// Git2Go conflict markers have filenames and git-merge-tree(1) has commit OIDs,
+	// to keep the content the same, we replace commit OID with filenames.
+	replaceOids := func(conflict *conflictHeader, chunk []byte) []byte {
+		chunk = bytes.ReplaceAll(chunk, []byte(request.OurCommitOid), []byte(conflict.ourPath))
+		chunk = bytes.ReplaceAll(chunk, []byte(request.TheirCommitOid), []byte(conflict.theirPath))
+
+		return chunk
+	}
+
+	for _, conflict := range conflicts {
+		if !request.AllowTreeConflicts && (conflict.theirPath == "" || conflict.ourPath == "") {
+			return structerr.NewFailedPrecondition("conflict side missing")
+		}
+
+		conflictFiles = append(conflictFiles, &gitalypb.ConflictFile{
+			ConflictFilePayload: &gitalypb.ConflictFile_Header{
+				Header: &gitalypb.ConflictFileHeader{
+					CommitOid:    request.OurCommitOid,
+					TheirPath:    []byte(conflict.theirPath),
+					OurPath:      []byte(conflict.ourPath),
+					AncestorPath: []byte(conflict.ancestorPath),
+					OurMode:      conflict.ourMode,
+				},
+			},
+		})
+
+		path := conflict.ourPath
+		if path == "" {
+			path = conflict.theirPath
+		}
+
+		fileOID, err := repo.ResolveRevision(ctx, oid.Revision()+":"+git.Revision(path))
+		if err != nil {
+			return structerr.NewFailedPrecondition("getting file revision: %w", err)
+		}
+
+		object, err := objectReader.Object(ctx, fileOID.Revision())
+		if err != nil {
+			return structerr.NewFailedPrecondition("getting objectreader: %w", err)
+		}
+
+		var content bytes.Buffer
+		_, err = content.ReadFrom(object)
+		if err != nil && err != io.EOF {
+			return structerr.NewInternal("reading conflict object: %w", err)
+		}
+
+		if !utf8.Valid(content.Bytes()) {
+			return structerr.NewFailedPrecondition("unsupported encoding")
+		}
+
+		parsedContent := replaceOids(conflict, content.Bytes())
+		contentLen := len(parsedContent)
+
+		for i := 0; i < contentLen; i += streamio.WriteBufferSize {
+			end := i + streamio.WriteBufferSize
+			if contentLen < end {
+				end = contentLen
+			}
+
+			conflictFiles = append(conflictFiles, &gitalypb.ConflictFile{
+				ConflictFilePayload: &gitalypb.ConflictFile_Content{
+					Content: parsedContent[i:end],
+				},
+			})
+
+			// We don't send a message for each chunk because the content of
+			// a file may be smaller than the size limit, which means we can
+			// keep adding data to the message
+			msgSize += end - i
+			if msgSize < streamio.WriteBufferSize {
+				continue
+			}
+
+			if err := stream.Send(&gitalypb.ListConflictFilesResponse{
+				Files: conflictFiles,
+			}); err != nil {
+				return structerr.NewInternal("error streaming conflict files: %w", err)
+			}
+
+			conflictFiles = conflictFiles[:0]
+			msgSize = 0
+		}
+	}
+
+	// Send leftover data, if any
+	if len(conflictFiles) > 0 {
+		if err := stream.Send(&gitalypb.ListConflictFilesResponse{
+			Files: conflictFiles,
+		}); err != nil {
+			return structerr.NewInternal("error streaming conflict files: %w", err)
+		}
+	}
+
+	return nil
+}
+
 func (s *server) conflictFilesWithGit2Go(
 	ctx context.Context,
 	request *gitalypb.ListConflictFilesRequest,
diff --git a/internal/gitaly/service/conflicts/list_conflict_files_test.go b/internal/gitaly/service/conflicts/list_conflict_files_test.go
index 07e92d0ab..b74d78a29 100644
--- a/internal/gitaly/service/conflicts/list_conflict_files_test.go
+++ b/internal/gitaly/service/conflicts/list_conflict_files_test.go
@@ -9,6 +9,7 @@ import (
 	"strings"
 	"testing"
 
+	"gitlab.com/gitlab-org/gitaly/v16/internal/featureflag"
 	"gitlab.com/gitlab-org/gitaly/v16/internal/git/gittest"
 	"gitlab.com/gitlab-org/gitaly/v16/internal/structerr"
 	"gitlab.com/gitlab-org/gitaly/v16/internal/testhelper"
@@ -23,7 +24,11 @@ type conflictFile struct {
 func TestListConflictFiles(t *testing.T) {
 	t.Parallel()
 
-	ctx := testhelper.Context(t)
+	testhelper.NewFeatureSets(featureflag.ListConflictFilesMergeTree).Run(t, testListConflictFiles)
+}
+
+func testListConflictFiles(t *testing.T, ctx context.Context) {
+	t.Parallel()
 
 	type setupData struct {
 		request       *gitalypb.ListConflictFilesRequest
@@ -84,6 +89,59 @@ func TestListConflictFiles(t *testing.T) {
 			},
 		},
 		{
+			"conflict in submodules commits are not handled",
+			func(tb testing.TB, ctx context.Context) setupData {
+				cfg, client := setupConflictsServiceWithoutRepo(tb, nil)
+				repo, repoPath := gittest.CreateRepository(tb, ctx, cfg)
+				_, subRepoPath := gittest.CreateRepository(tb, ctx, cfg)
+
+				subCommitID := gittest.WriteCommit(t, cfg, subRepoPath, gittest.WithTreeEntries(gittest.TreeEntry{
+					Mode:    "100644",
+					Path:    "abc",
+					Content: "foo",
+				}))
+				ourCommitID := gittest.WriteCommit(t, cfg, repoPath, gittest.WithBranch("master"), gittest.WithTreeEntries(
+					gittest.TreeEntry{
+						Mode:    "100644",
+						Path:    ".gitmodules",
+						Content: fmt.Sprintf(`[submodule %q]\n\tpath = %s\n\turl = file://%s`, "sub", "sub", subRepoPath),
+					},
+					gittest.TreeEntry{OID: subCommitID, Mode: "160000", Path: "sub"},
+				))
+
+				newSubCommitID := gittest.WriteCommit(t, cfg, subRepoPath, gittest.WithTreeEntries(gittest.TreeEntry{
+					Mode:    "100644",
+					Path:    "abc",
+					Content: "bar",
+				}))
+				theirCommitID := gittest.WriteCommit(t, cfg, repoPath, gittest.WithBranch("master"), gittest.WithTreeEntries(
+					gittest.TreeEntry{
+						Mode:    "100644",
+						Path:    ".gitmodules",
+						Content: fmt.Sprintf(`[submodule %q]\n\tpath = %s\n\turl = file://%s`, "sub", "sub", subRepoPath),
+					},
+					gittest.TreeEntry{OID: newSubCommitID, Mode: "160000", Path: "sub"},
+				))
+
+				request := &gitalypb.ListConflictFilesRequest{
+					Repository:     repo,
+					OurCommitOid:   ourCommitID.String(),
+					TheirCommitOid: theirCommitID.String(),
+				}
+
+				expectedErr := structerr.NewFailedPrecondition("could not get conflicting blob: object not found - no match for id (%s)", subCommitID)
+				if featureflag.ListConflictFilesMergeTree.IsEnabled(ctx) {
+					expectedErr = structerr.NewFailedPrecondition("getting objectreader: object not found")
+				}
+
+				return setupData{
+					client:        client,
+					request:       request,
+					expectedError: expectedErr,
+				}
+			},
+		},
+		{
 			"Lists the expected conflict files with ancestor path",
 			func(tb testing.TB, ctx context.Context) setupData {
 				cfg, client := setupConflictsServiceWithoutRepo(tb, nil)
@@ -303,29 +361,38 @@ func TestListConflictFiles(t *testing.T) {
 					AllowTreeConflicts: true,
 				}
 
-				return setupData{
-					client:  client,
-					request: request,
-					expectedFiles: []*conflictFile{
-						{
-							Header: &gitalypb.ConflictFileHeader{
-								CommitOid:    ourCommitID.String(),
-								OurPath:      []byte("a"),
-								OurMode:      int32(0o100644),
-								AncestorPath: []byte("a"),
-							},
-							Content: []byte("<<<<<<< a\nmango\n=======\n>>>>>>> \n"),
+				expectedFiles := []*conflictFile{
+					{
+						Header: &gitalypb.ConflictFileHeader{
+							CommitOid:    ourCommitID.String(),
+							OurPath:      []byte("a"),
+							OurMode:      int32(0o100644),
+							AncestorPath: []byte("a"),
 						},
-						{
-							Header: &gitalypb.ConflictFileHeader{
-								CommitOid:    ourCommitID.String(),
-								TheirPath:    []byte("b"),
-								AncestorPath: []byte("b"),
-							},
-							Content: []byte("<<<<<<< \n=======\npeach\n>>>>>>> b\n"),
+						Content: []byte("<<<<<<< a\nmango\n=======\n>>>>>>> \n"),
+					},
+					{
+						Header: &gitalypb.ConflictFileHeader{
+							CommitOid:    ourCommitID.String(),
+							TheirPath:    []byte("b"),
+							AncestorPath: []byte("b"),
 						},
+						Content: []byte("<<<<<<< \n=======\npeach\n>>>>>>> b\n"),
 					},
 				}
+
+				// When using git-merge-tree(1), deleted files don't contain conflict markers.
+				// Whereas if you see above, Git2Go contains conflict markers.
+				if featureflag.ListConflictFilesMergeTree.IsEnabled(ctx) {
+					expectedFiles[0].Content = []byte("mango")
+					expectedFiles[1].Content = []byte("peach")
+				}
+
+				return setupData{
+					client:        client,
+					request:       request,
+					expectedFiles: expectedFiles,
+				}
 			},
 		},
 		{
@@ -481,7 +548,9 @@ func getConflictFiles(t *testing.T, c gitalypb.ConflictsService_ListConflictFile
 	}
 
 	// Append leftover file
-	files = append(files, currentFile)
+	if currentFile != nil {
+		files = append(files, currentFile)
+	}
 
 	return files, nil
 }