Merge branch '4580-reimplement-resolveconflicts-without-git2go-2' into 'master'

conflict: Introduce new `Resolve` function

See merge request https://gitlab.com/gitlab-org/gitaly/-/merge_requests/5955

Merged-by: karthik nayak <knayak@gitlab.com>
Approved-by: Justin Tobler <jtobler@gitlab.com>
Reviewed-by: John Cai <jcai@gitlab.com>
Reviewed-by: Justin Tobler <jtobler@gitlab.com>
Reviewed-by: karthik nayak <knayak@gitlab.com>

6 files changed, 506 insertions, 55 deletions

diff --git a/internal/git/conflict/parser.go b/internal/git/conflict/parser.go
index 9a8997afd..b106f8599 100644
--- a/internal/git/conflict/parser.go
+++ b/internal/git/conflict/parser.go
@@ -14,33 +14,6 @@ import (
 	"strings"
 )
 
-// Errors that can occur during parsing of a merge conflict file
-var (
-	ErrUnmergeableFile     = errors.New("merging is not supported for file")
-	ErrUnexpectedDelimiter = errors.New("unexpected conflict delimiter")
-	ErrMissingEndDelimiter = errors.New("missing last delimiter")
-)
-
-type section uint
-
-const (
-	sectionNone = section(iota)
-	sectionOld
-	sectionNew
-	sectionNoNewline
-)
-
-const fileLimit = 200 * (1 << 10) // 200k
-
-type line struct {
-	objIndex uint // where are we in the object?
-	oldIndex uint // where are we in the old file?
-	newIndex uint // where are we in the new file?
-
-	payload string // actual line contents (minus the newline)
-	section section
-}
-
 // File contains an ordered list of lines with metadata about potential
 // conflicts.
 type File struct {
@@ -54,23 +27,6 @@ func (f File) sectionID(l line) string {
 	return fmt.Sprintf("%x_%d_%d", pathSHA1, l.oldIndex, l.newIndex)
 }
 
-// Resolution indicates how to resolve a conflict
-type Resolution struct {
-	OldPath string `json:"old_path"`
-	NewPath string `json:"new_path"`
-
-	// key is a sectionID, value is "head" or "origin"
-	Sections map[string]string `json:"sections"`
-
-	// Content is used when no sections are defined
-	Content string `json:"content"`
-}
-
-const (
-	head   = "head"
-	origin = "origin"
-)
-
 // Resolve will iterate through each conflict line and replace it with the
 // specified resolution
 func (f File) Resolve(resolution Resolution) ([]byte, error) {
diff --git a/internal/git/conflict/resolve.go b/internal/git/conflict/resolve.go
new file mode 100644
index 000000000..85e0f7096
--- /dev/null
+++ b/internal/git/conflict/resolve.go
@@ -0,0 +1,240 @@
+package conflict
+
+import (
+	"bufio"
+	"bytes"
+	"crypto/sha1"
+	"errors"
+	"fmt"
+	"io"
+	"strings"
+
+	"gitlab.com/gitlab-org/gitaly/v16/internal/git"
+)
+
+// section denotes the various conflict sections
+type section uint
+
+const (
+	// Resolutions for conflict is done by clients providing selections for
+	// the different conflict sections. "head"/"origin" is used to denote the
+	// selection for ours/their trees respectively.
+	head   = "head"
+	origin = "origin"
+
+	// fileLimit is used to set the limit on the buffer size for bufio.Scanner,
+	// we don't support conflict resolution for files which require bigger buffers.
+	fileLimit = 200 * (1 << 10)
+)
+
+const (
+	// The sections are used to define various lines of the conflicted file.
+	// Here Old/New is used to denote ours/their respectively.
+	sectionNone = section(iota)
+	sectionOld
+	sectionNew
+	sectionNoNewline
+)
+
+// Errors that can occur during parsing of a merge conflict file
+var (
+	// ErrUnmergeableFile is returned when the either the file exceeds the
+	// fileLimit or no data was read from the file (in case of a binary file).
+	ErrUnmergeableFile = errors.New("merging is not supported for file")
+	// ErrUnexpectedDelimiter is returned  when the previous section doesn't
+	// match the expected flow of sections.
+	ErrUnexpectedDelimiter = errors.New("unexpected conflict delimiter")
+	// ErrMissingEndDelimiter is returned when the final section parsed doesn't
+	// match the expected end state.
+	ErrMissingEndDelimiter = errors.New("missing last delimiter")
+)
+
+// line is a structure used to denote individual lines in the conflicted blob,
+// with information around how that line maps to ours/theirs blobs.
+type line struct {
+	// objIndex states the cursor position in the conflicted blob
+	objIndex uint
+	// oldIndex states the cursor position in the 'ours' blob
+	oldIndex uint
+	// oldIndex states the cursor position in the 'theirs' blob
+	newIndex uint
+	// payload denotes the content of line (sans the newline)
+	payload string
+	// section denotes which section this line belongs to.
+	section section
+}
+
+// Resolution indicates how to resolve a conflict
+type Resolution struct {
+	// OldPath is the mapping of the path wrt to 'ours' OID
+	OldPath string `json:"old_path"`
+	// OldPath is the mapping of the path wrt to 'their' OID
+	NewPath string `json:"new_path"`
+
+	// Sections is a map which is used to denote which section to select
+	// for each conflict. Key is the sectionID, while the value is either
+	// "head" or "origin", which denotes the ours/theirs OIDs respectively.
+	Sections map[string]string `json:"sections"`
+
+	// Content is used when no sections are defined
+	Content string `json:"content"`
+}
+
+// Resolve is used to resolve conflicts for a given blob. It expects the blob
+// to be provided as an io.Reader along with the resolutions for the provided
+// blob.
+func Resolve(src io.Reader, ours, theirs git.ObjectID, path string, resolution Resolution) (io.Reader, error) {
+	var (
+		// conflict markers, git-merge-tree(1) appends the tree OIDs to the markers
+		start  = "<<<<<<< " + ours.String()
+		middle = "======="
+		end    = ">>>>>>> " + theirs.String()
+
+		objIndex, oldIndex, newIndex uint = 0, 1, 1
+		currentSection               section
+		bytesRead                    int
+		resolvedContent              bytes.Buffer
+
+		s = bufio.NewScanner(src)
+	)
+
+	// allow for line scanning up to the file limit
+	s.Buffer(make([]byte, 4096), fileLimit)
+
+	s.Split(func(data []byte, atEOF bool) (advance int, token []byte, err error) {
+		defer func() { bytesRead += advance }()
+
+		if bytesRead >= fileLimit {
+			return 0, nil, ErrUnmergeableFile
+		}
+
+		// The remaining function is a modified version of
+		// bufio.ScanLines that does not consume carriage returns
+		if atEOF && len(data) == 0 {
+			return 0, nil, nil
+		}
+		if i := bytes.IndexByte(data, '\n'); i >= 0 {
+			// We have a full newline-terminated line.
+			return i + 1, data[0:i], nil
+		}
+		if atEOF {
+			return len(data), data, nil
+		}
+		return 0, nil, nil
+	})
+
+	lines := []line{}
+
+	for s.Scan() {
+		switch l := s.Text(); l {
+		case start:
+			if currentSection != sectionNone {
+				return &resolvedContent, fmt.Errorf("resolve: parse conflict for %q: %w", path, ErrUnexpectedDelimiter)
+			}
+			currentSection = sectionNew
+		case middle:
+			if currentSection != sectionNew {
+				return &resolvedContent, fmt.Errorf("resolve: parse conflict for %q: %w", path, ErrUnexpectedDelimiter)
+			}
+			currentSection = sectionOld
+		case end:
+			if currentSection != sectionOld {
+				return &resolvedContent, fmt.Errorf("resolve: parse conflict for %q: %w", path, ErrUnexpectedDelimiter)
+			}
+			currentSection = sectionNone
+		default:
+			if len(l) > 0 && l[0] == '\\' {
+				currentSection = sectionNoNewline
+				lines = append(lines, line{
+					objIndex: objIndex,
+					oldIndex: oldIndex,
+					newIndex: newIndex,
+					payload:  l,
+					section:  currentSection,
+				})
+				continue
+			}
+			lines = append(lines, line{
+				objIndex: objIndex,
+				oldIndex: oldIndex,
+				newIndex: newIndex,
+				payload:  l,
+				section:  currentSection,
+			})
+
+			objIndex++
+			if currentSection != sectionNew {
+				oldIndex++
+			}
+			if currentSection != sectionOld {
+				newIndex++
+			}
+		}
+	}
+
+	if err := s.Err(); err != nil {
+		if errors.Is(err, bufio.ErrTooLong) {
+			return &resolvedContent, fmt.Errorf("resolve: parse conflict for %q: %w", path, ErrUnmergeableFile)
+		}
+		return &resolvedContent, err
+	}
+
+	if currentSection == sectionOld || currentSection == sectionNew {
+		return &resolvedContent, fmt.Errorf("resolve: parse conflict for %q: %w", path, ErrMissingEndDelimiter)
+	}
+
+	if bytesRead == 0 {
+		return &resolvedContent, fmt.Errorf("resolve: parse conflict for %q: %w", path, ErrUnmergeableFile) // typically a binary file
+	}
+
+	var sectionID string
+
+	if len(resolution.Sections) == 0 {
+		_, err := resolvedContent.Write([]byte(resolution.Content))
+		if err != nil {
+			return &resolvedContent, fmt.Errorf("writing bytes: %w", err)
+		}
+
+		return &resolvedContent, nil
+	}
+
+	resolvedLines := make([]string, 0, len(lines))
+	for _, l := range lines {
+		if l.section == sectionNone {
+			sectionID = ""
+			resolvedLines = append(resolvedLines, l.payload)
+			continue
+		}
+
+		if sectionID == "" {
+			sectionID = fmt.Sprintf("%x_%d_%d", sha1.Sum([]byte(path)), l.oldIndex, l.newIndex)
+		}
+
+		r, ok := resolution.Sections[sectionID]
+		if !ok {
+			return nil, fmt.Errorf("Missing resolution for section ID: %s", sectionID) //nolint
+		}
+
+		switch r {
+		case head:
+			if l.section != sectionNew {
+				continue
+			}
+		case origin:
+			if l.section != sectionOld {
+				continue
+			}
+		default:
+			return nil, fmt.Errorf("Missing resolution for section ID: %s", sectionID) //nolint
+		}
+
+		resolvedLines = append(resolvedLines, l.payload)
+	}
+
+	_, err := resolvedContent.Write([]byte(strings.Join(resolvedLines, "\n")))
+	if err != nil {
+		return &resolvedContent, fmt.Errorf("writing bytes: %w", err)
+	}
+
+	return &resolvedContent, nil
+}
diff --git a/internal/git/conflict/resolve_test.go b/internal/git/conflict/resolve_test.go
new file mode 100644
index 000000000..d189d901a
--- /dev/null
+++ b/internal/git/conflict/resolve_test.go
@@ -0,0 +1,181 @@
+package conflict
+
+import (
+	"fmt"
+	"io"
+	"strings"
+	"testing"
+
+	"github.com/stretchr/testify/require"
+	"gitlab.com/gitlab-org/gitaly/v16/internal/git"
+	"gitlab.com/gitlab-org/gitaly/v16/internal/git/gittest"
+)
+
+func TestResolve(t *testing.T) {
+	t.Parallel()
+
+	type args struct {
+		src        io.Reader
+		ours       git.ObjectID
+		theirs     git.ObjectID
+		path       string
+		resolution Resolution
+	}
+	tests := []struct {
+		name            string
+		args            args
+		resolvedContent []byte
+		expectedErr     error
+	}{
+		{
+			name: "select ours",
+			args: args{
+				src: strings.NewReader(fmt.Sprintf(`# this file is very conflicted
+<<<<<<< %s
+we want this line
+=======
+but they want this line
+>>>>>>> %s
+we can both agree on this line though
+`, gittest.DefaultObjectHash.EmptyTreeOID, gittest.DefaultObjectHash.EmptyTreeOID)),
+				ours:   gittest.DefaultObjectHash.EmptyTreeOID,
+				theirs: gittest.DefaultObjectHash.EmptyTreeOID,
+				path:   "conflict.txt",
+				resolution: Resolution{
+					NewPath: "conflict.txt",
+					OldPath: "conflict.txt",
+					Sections: map[string]string{
+						"dc1c302824bab8da29f7c06fec1c77cf16b975e6_2_2": "head",
+					},
+				},
+			},
+			resolvedContent: []byte(`# this file is very conflicted
+we want this line
+we can both agree on this line though`),
+		},
+		{
+			name: "select theirs",
+			args: args{
+				src: strings.NewReader(fmt.Sprintf(`# this file is very conflicted
+<<<<<<< %s
+we want this line
+=======
+but they want this line
+>>>>>>> %s
+we can both agree on this line though
+`, gittest.DefaultObjectHash.EmptyTreeOID, gittest.DefaultObjectHash.EmptyTreeOID)),
+				ours:   gittest.DefaultObjectHash.EmptyTreeOID,
+				theirs: gittest.DefaultObjectHash.EmptyTreeOID,
+				path:   "conflict.txt",
+				resolution: Resolution{
+					NewPath: "conflict.txt",
+					OldPath: "conflict.txt",
+					Sections: map[string]string{
+						"dc1c302824bab8da29f7c06fec1c77cf16b975e6_2_2": "origin",
+					},
+				},
+			},
+			resolvedContent: []byte(`# this file is very conflicted
+but they want this line
+we can both agree on this line though`),
+		},
+		{
+			name: "UnexpectedDelimiter",
+			args: args{
+				src: strings.NewReader(fmt.Sprintf(`# this file is very conflicted
+<<<<<<< %s
+we want this line
+<<<<<<< %s
+=======
+but they want this line
+>>>>>>> %s
+we can both agree on this line though
+`, gittest.DefaultObjectHash.EmptyTreeOID, gittest.DefaultObjectHash.EmptyTreeOID, gittest.DefaultObjectHash.EmptyTreeOID)),
+				ours:   gittest.DefaultObjectHash.EmptyTreeOID,
+				theirs: gittest.DefaultObjectHash.EmptyTreeOID,
+				path:   "conflict.txt",
+			},
+
+			expectedErr: fmt.Errorf("resolve: parse conflict for %q: %w", "conflict.txt", ErrUnexpectedDelimiter),
+		},
+		{
+			name: "MissingEndDelimiter",
+			args: args{
+				src: strings.NewReader(fmt.Sprintf(`# this file is very conflicted
+<<<<<<< %s
+we want this line
+=======
+but they want this line
+we can both agree on this line though
+`, gittest.DefaultObjectHash.EmptyTreeOID)),
+				ours:   gittest.DefaultObjectHash.EmptyTreeOID,
+				theirs: gittest.DefaultObjectHash.EmptyTreeOID,
+				path:   "conflict.txt",
+			},
+
+			expectedErr: fmt.Errorf("resolve: parse conflict for %q: %w", "conflict.txt", ErrMissingEndDelimiter),
+		},
+		{
+			name: "Uses resolution.Content when there is no resolution sections",
+			args: args{
+				src:    strings.NewReader("foo\n"),
+				ours:   gittest.DefaultObjectHash.EmptyTreeOID,
+				theirs: gittest.DefaultObjectHash.EmptyTreeOID,
+				path:   "conflict.txt",
+				resolution: Resolution{
+					OldPath: "conflict.txt",
+					NewPath: "conflict.txt",
+					Content: "bar\n",
+				},
+			},
+			resolvedContent: []byte("bar\n"),
+		},
+		{
+			name: "Conflict file under file limit",
+			args: args{
+				src:    strings.NewReader(strings.Repeat("x", fileLimit-2) + "\n"),
+				ours:   gittest.DefaultObjectHash.EmptyTreeOID,
+				theirs: gittest.DefaultObjectHash.EmptyTreeOID,
+				path:   "conflict.txt",
+			},
+			resolvedContent: []byte(""),
+		},
+		{
+			name: "Conflict file over file limit",
+			args: args{
+				src:    strings.NewReader(strings.Repeat("x", fileLimit+2) + "\n"),
+				ours:   gittest.DefaultObjectHash.EmptyTreeOID,
+				theirs: gittest.DefaultObjectHash.EmptyTreeOID,
+				path:   "conflict.txt",
+			},
+			expectedErr: fmt.Errorf("resolve: parse conflict for %q: %w", "conflict.txt", ErrUnmergeableFile),
+		},
+		{
+			name: "empty file",
+			args: args{
+				src:    strings.NewReader(""),
+				ours:   gittest.DefaultObjectHash.EmptyTreeOID,
+				theirs: gittest.DefaultObjectHash.EmptyTreeOID,
+				path:   "conflict.txt",
+			},
+			expectedErr: fmt.Errorf("resolve: parse conflict for %q: %w", "conflict.txt", ErrUnmergeableFile),
+		},
+	}
+	for _, tt := range tests {
+		tt := tt
+
+		t.Run(tt.name, func(t *testing.T) {
+			t.Parallel()
+
+			resolvedReader, err := Resolve(tt.args.src, tt.args.ours, tt.args.theirs, tt.args.path, tt.args.resolution)
+			if err != nil || tt.expectedErr != nil {
+				require.Equal(t, tt.expectedErr, err)
+				return
+			}
+
+			resolvedContent, err := io.ReadAll(resolvedReader)
+			require.NoError(t, err)
+			require.Equal(t, tt.resolvedContent, resolvedContent)
+		})
+	}
+}
diff --git a/internal/git/localrepo/merge.go b/internal/git/localrepo/merge.go
index 26949c47f..936a5758f 100644
--- a/internal/git/localrepo/merge.go
+++ b/internal/git/localrepo/merge.go
@@ -256,3 +256,23 @@ func (c *MergeTreeConflictError) Error() string {
 	// and the InfoMessage.
 	return "merge: there are conflicting files"
 }
+
+// ConflictedFiles is used to get the list of the names of the conflicted files from the
+// MergeTreeConflictError.
+func (c *MergeTreeConflictError) ConflictedFiles() []string {
+	// We use a map for quick access to understand which files were already
+	// accounted for.
+	m := make(map[string]struct{})
+	var files []string
+
+	for _, fileInfo := range c.ConflictingFileInfo {
+		if _, ok := m[fileInfo.FileName]; ok {
+			continue
+		}
+
+		m[fileInfo.FileName] = struct{}{}
+		files = append(files, fileInfo.FileName)
+	}
+
+	return files
+}
diff --git a/internal/git/localrepo/merge_test.go b/internal/git/localrepo/merge_test.go
index 7a41d6a82..47dec2eda 100644
--- a/internal/git/localrepo/merge_test.go
+++ b/internal/git/localrepo/merge_test.go
@@ -24,8 +24,9 @@ func TestMergeTree(t *testing.T) {
 		ours   git.ObjectID
 		theirs git.ObjectID
 
-		expectedTreeEntries []gittest.TreeEntry
-		expectedErr         error
+		expectedTreeEntries   []gittest.TreeEntry
+		expectedErr           error
+		expectedConflictFiles []string
 	}
 
 	testCases := []struct {
@@ -198,6 +199,7 @@ func TestMergeTree(t *testing.T) {
 							},
 						},
 					},
+					expectedConflictFiles: []string{"file2"},
 				}
 			},
 		},
@@ -282,6 +284,7 @@ func TestMergeTree(t *testing.T) {
 							},
 						},
 					},
+					expectedConflictFiles: []string{"file1"},
 				}
 			},
 		},
@@ -344,6 +347,7 @@ func TestMergeTree(t *testing.T) {
 							},
 						},
 					},
+					expectedConflictFiles: []string{"file2"},
 				}
 			},
 		},
@@ -445,6 +449,7 @@ func TestMergeTree(t *testing.T) {
 							},
 						},
 					},
+					expectedConflictFiles: []string{"file2", "file3"},
 				}
 			},
 		},
@@ -553,6 +558,7 @@ func TestMergeTree(t *testing.T) {
 							},
 						},
 					},
+					expectedConflictFiles: []string{"file1", "file2"},
 				}
 			},
 		},
@@ -644,6 +650,7 @@ func TestMergeTree(t *testing.T) {
 							},
 						},
 					},
+					expectedConflictFiles: []string{"file1", "file2"},
 				}
 			},
 		},
@@ -707,16 +714,18 @@ func TestMergeTree(t *testing.T) {
 			data := tc.setup(t, repoPath)
 
 			mergeTreeResult, err := repo.MergeTree(ctx, string(data.ours), string(data.theirs), tc.mergeTreeOptions...)
-
 			require.Equal(t, data.expectedErr, err)
-			if data.expectedErr == nil {
-				gittest.RequireTree(
-					t,
-					cfg,
-					repoPath,
-					string(mergeTreeResult),
-					data.expectedTreeEntries,
-				)
+
+			if len(data.expectedConflictFiles) > 0 {
+				var mergeConflictErr *MergeTreeConflictError
+				if !errors.As(err, &mergeConflictErr) {
+					require.Fail(t, "error should be a conflict error")
+				}
+				require.ElementsMatch(t, data.expectedConflictFiles, mergeConflictErr.ConflictedFiles())
+			}
+
+			if data.expectedErr == nil && err == nil {
+				gittest.RequireTree(t, cfg, repoPath, string(mergeTreeResult), data.expectedTreeEntries)
 			}
 		})
 	}
diff --git a/internal/gitaly/service/conflicts/resolve_conflicts_test.go b/internal/gitaly/service/conflicts/resolve_conflicts_test.go
index d501ca540..cab98d472 100644
--- a/internal/gitaly/service/conflicts/resolve_conflicts_test.go
+++ b/internal/gitaly/service/conflicts/resolve_conflicts_test.go
@@ -53,6 +53,51 @@ func TestResolveConflicts(t *testing.T) {
 		setup func(testing.TB, context.Context) setupData
 	}{
 		{
+			"no conflict present",
+			func(tb testing.TB, ctx context.Context) setupData {
+				cfg, client := setupConflictsService(tb, nil)
+				repo, repoPath := gittest.CreateRepository(tb, ctx, cfg)
+
+				ourCommitID := gittest.WriteCommit(tb, cfg, repoPath, gittest.WithBranch("ours"),
+					gittest.WithTreeEntries(gittest.TreeEntry{Path: "b", Mode: "100644", Content: "apricot"}))
+				theirCommitID := gittest.WriteCommit(tb, cfg, repoPath, gittest.WithBranch("theirs"),
+					gittest.WithTreeEntries(gittest.TreeEntry{Path: "c", Mode: "100644", Content: "acai"}))
+
+				filesJSON, err := json.Marshal([]map[string]interface{}{})
+				require.NoError(t, err)
+
+				return setupData{
+					cfg:      cfg,
+					client:   client,
+					repoPath: repoPath,
+					repo:     repo,
+					requestHeader: &gitalypb.ResolveConflictsRequest_Header{
+						Header: &gitalypb.ResolveConflictsRequestHeader{
+							Repository:       repo,
+							TargetRepository: repo,
+							OurCommitOid:     ourCommitID.String(),
+							TheirCommitOid:   theirCommitID.String(),
+							TargetBranch:     []byte("theirs"),
+							SourceBranch:     []byte("ours"),
+							CommitMessage:    []byte(conflictResolutionCommitMessage),
+							User:             user,
+							Timestamp:        &timestamppb.Timestamp{},
+						},
+					},
+					requestsFilesJSON: []*gitalypb.ResolveConflictsRequest_FilesJson{
+						{FilesJson: filesJSON},
+					},
+					expectedResponse: &gitalypb.ResolveConflictsResponse{},
+					expectedContent: map[string]map[string][]byte{
+						"refs/heads/ours": {
+							"b": []byte("apricot"),
+							"c": []byte("acai"),
+						},
+					},
+				}
+			},
+		},
+		{
 			"single file conflict, pick ours",
 			func(tb testing.TB, ctx context.Context) setupData {
 				cfg, client := setupConflictsService(tb, nil)