Complete merge-ort implementation...almost

From: Elijah Newren <[email protected]>

Add a function which can be called to populate the attr_index with the appropriate .gitattributes contents when necessary. Make it return early if the attr_index is already initialized or if we are not renormalizing files.

NOTE 1: Even if the user has a working copy or a real index (which is not a given as merge-ort can be used in bare repositories), we explicitly ignore any .gitattributes file from either of these locations. merge-ort can be used to merge two branches that are unrelated to HEAD, so .gitattributes from the working copy and current index should not be considered relevant.

NOTE 2: Since we are in the middle of merging, there is a risk that .gitattributes itself is conflicted...leaving us with an ill-defined situation about how to perform the rest of the merge. It could be that the .gitattributes file does not even exist on one of the sides of the merge, or that it has been modified on both sides. If it's been modified on both sides, it's possible that it could itself be merged cleanly, though it's also possible that it only merges cleanly if you use the right version of the .gitattributes file to drive the merge. It gets kind of complicated. The only test we ever had that attempted to test behavior in this area was seemingly unaware of the undefined behavior, but knew the test wouldn't work for lack of attribute handling support, marked it as test_expect_failure from the beginning, but managed to fail for several reasons unrelated to attribute handling. See commit 6f6e7cfb52 ("t6038: remove problematic test", 2020-08-03) for details. So there are probably various ways to improve what initialize_attr_index() picks in the case of a conflicted .gitattributes but for now I just implemented something simple -- look for whatever .gitattributes file we can find in any of the higher order stages and use it.

Signed-off-by Elijah Newren <[email protected]>

---
 merge-ort.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 61 insertions(+)

merge-ort.c +0 -0

index d91b66a052b6..028d1adcd2c9 100644

merge-ort.c +7 -0

+static void initialize_attr_index(struct merge_options *opt)
+{
+	/*
+	 * The renormalize_buffer() functions require attributes, and
+	 * annoyingly those can only be read from the working tree or from
+	 * an index_state.  merge-ort doesn't have an index_state, so we
+	 * generate a fake one containing only attribute information.

merge-ort.c +9 -0

+	attr_index->initialized = 1;
+
+	mi = strmap_get(&opt->priv->paths, GITATTRIBUTES_FILE);
+	if (!mi)
+		return;
+
+	if (mi->clean) {
+		int len = strlen(GITATTRIBUTES_FILE);
+		ce = make_empty_cache_entry(attr_index, len);

merge-ort.c +19 -0

+			unsigned stage_mask = (1 << stage);
+
+			if (!(ci->filemask & stage_mask))
+				continue;
+			len = strlen(GITATTRIBUTES_FILE);
+			ce = make_empty_cache_entry(attr_index, len);
+			ce->ce_mode = create_ce_mode(ci->stages[stage].mode);
+			ce->ce_flags = create_ce_flags(stage);
+			ce->ce_namelen = len;
+			oidcpy(&ce->oid, &ci->stages[stage].oid);
+			memcpy(ce->name, GITATTRIBUTES_FILE, len);
+			add_index_entry(attr_index, ce,
+					ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE);
+			get_stream_filter(attr_index, GITATTRIBUTES_FILE,
+					  &ce->oid);
+		}
+	}
+}
+

From: Elijah Newren <[email protected]>

ll_merge() needs an index when renormalization is requested. Give it the special one we created exactly for that purpose. This fixes t6418.4 and t6418.5 under GIT_TEST_MERGE_ALGORITHM=ort.

Signed-off-by Elijah Newren <[email protected]>

---
 merge-ort.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

merge-ort.c +0 -0

index 028d1adcd2c9..87c553c0882c 100644

merge-ort.c +0 -1

 	/* Free memory used by various renames maps */

@@ -988,7 +988,6 @@ static int merge_submodule(struct merge_options *opt,
 	return 0;
 }
 
-MAYBE_UNUSED
 static void initialize_attr_index(struct merge_options *opt)
 {
 	/*

merge-ort.c +1 -1

 	ll_opts.renormalize = opt->renormalize;
 	ll_opts.extra_marker_size = extra_marker_size;
 	ll_opts.xdl_opts = opt->xdl_opts;

@@ -1101,7 +1102,7 @@ static int merge_3way(struct merge_options *opt,
 
 	merge_status = ll_merge(result_buf, path, &orig, base,
 				&src1, name1, &src2, name2,
-				opt->repo->index, &ll_opts);
+				&opt->priv->attr_index, &ll_opts);
 
 	free(base);
 	free(name1);

From: Elijah Newren <[email protected]>

When we have a modify/delete conflict, but the only change to the modification is e.g. change of line endings, then if renormalization is requested then we should be able to recognize such a case as a not-modified/delete and resolve the conflict automatically.

This fixes t6418.10 under GIT_TEST_MERGE_ALGORITHM=ort.

Signed-off-by Elijah Newren <[email protected]>

---
 merge-ort.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 61 insertions(+), 2 deletions(-)

merge-ort.c +3 -0

index 87c553c0882c..c4bd88b9d3db 100644
@@ -2416,6 +2416,60 @@ static int string_list_df_name_compare(const char *one, const char *two)
 	return onelen - twolen;
 }
 
+static int read_oid_strbuf(struct merge_options *opt,
+			   const struct object_id *oid,
+			   struct strbuf *dst)

merge-ort.c +41 -0

+	}
+	strbuf_attach(dst, buf, size, size + 1);
+	return 0;
+}
+
+static int blob_unchanged(struct merge_options *opt,
+			  const struct version_info *base,
+			  const struct version_info *side,
+			  const char *path)
+{
+	struct strbuf basebuf = STRBUF_INIT;
+	struct strbuf sidebuf = STRBUF_INIT;
+	int ret = 0; /* assume changed for safety */
+	const struct index_state *idx = &opt->priv->attr_index;
+
+	initialize_attr_index(opt);
+
+	if (base->mode != side->mode)
+		return 0;
+	if (oideq(&base->oid, &side->oid))
+		return 1;
+
+	if (read_oid_strbuf(opt, &base->oid, &basebuf) ||
+	    read_oid_strbuf(opt, &side->oid, &sidebuf))
+		goto error_return;
+	/*
+	 * Note: binary | is used so that both renormalizations are
+	 * performed.  Comparison can be skipped if both files are
+	 * unchanged since their sha1s have already been compared.
+	 */
+	if (renormalize_buffer(idx, path, basebuf.buf, basebuf.len, &basebuf) |
+	    renormalize_buffer(idx, path, sidebuf.buf, sidebuf.len, &sidebuf))
+		ret = (basebuf.len == sidebuf.len &&
+		       !memcmp(basebuf.buf, sidebuf.buf, basebuf.len));
+
+error_return:
+	strbuf_release(&basebuf);
+	strbuf_release(&sidebuf);
+	return ret;
+}
+
 
 struct directory_versions {
 	/*

merge-ort.c +0 -0

 	 * versions: list of (basename -> version_info)

@@ -3003,8 +3057,13 @@ static void process_entry(struct merge_options *opt,
 		modify_branch = (side == 1) ? opt->branch1 : opt->branch2;
 		delete_branch = (side == 1) ? opt->branch2 : opt->branch1;

From: Elijah Newren <[email protected]>

If there is a conflict during a merge for a SKIP_WORKTREE entry, we expect that file to be written to the working copy and have the SKIP_WORKTREE bit cleared in the index. If the user had manually created a file in the working tree despite SKIP_WORKTREE being set, we do not want to clobber their changes to that file, but want to move it out of the way. Add tests that check for these behaviors.

Signed-off-by Elijah Newren <[email protected]>

---
 t/t6428-merge-conflicts-sparse.sh | 158 ++++++++++++++++++++++++++++++
 1 file changed, 158 insertions(+)
 create mode 100755 t/t6428-merge-conflicts-sparse.sh

t/t6428-merge-conflicts-sparse.sh new file +30 -0

new file mode 100755
index 000000000000..1bb52ff6f38c
@@ -0,0 +1,158 @@
+#!/bin/sh
+
+test_description="merge cases"
+
+# The setup for all of them, pictorially, is:
+#
+#      A
+#      o
+#     / \
+#  O o   ?
+#     \ /
+#      o
+#      B
+#
+# To help make it easier to follow the flow of tests, they have been
+# divided into sections and each test will start with a quick explanation
+# of what commits O, A, and B contain.
+#
+# Notation:
+#    z/{b,c}   means  files z/b and z/c both exist
+#    x/d_1     means  file x/d exists with content d1.  (Purpose of the
+#                     underscore notation is to differentiate different
+#                     files that might be renamed into each other's paths.)
+
+. ./test-lib.sh
+. "$TEST_DIRECTORY"/lib-merge.sh
+
+
+# Testcase basic, conflicting changes in 'numerals'
+

t/t6428-merge-conflicts-sparse.sh new file +30 -0

+
+		git branch O &&
+		git branch A &&
+		git branch B &&
+
+		git checkout A &&
+		test_write_lines I II III IIII >numerals &&
+		git add numerals &&
+		test_tick &&
+		git commit -m "A" &&
+
+		git checkout B &&
+		test_write_lines I II III IV >numerals &&
+		git add numerals &&
+		test_tick &&
+		git commit -m "B" &&
+
+		cat <<-EOF >expected-index &&
+		H README
+		M numerals
+		M numerals
+		M numerals
+		EOF
+
+		cat <<-EOF >expected-merge
+		I
+		II
+		III
+		<<<<<<< HEAD
+		IIII

From: Elijah Newren <[email protected]>

When merge conflicts occur in paths removed by a sparse-checkout, we need to unsparsify those paths (clear the SKIP_WORKTREE bit), and write out the conflicted file to the working copy. In the very unlikely case that someone manually put a file into the working copy at the location of the SKIP_WORKTREE file, we need to avoid overwriting whatever edits they have made and move that file to a different location first.

Signed-off-by Elijah Newren <[email protected]>

---
 merge-ort.c                       | 43 +++++++++++++++++++++----------
 t/t6428-merge-conflicts-sparse.sh |  4 +--
 2 files changed, 32 insertions(+), 15 deletions(-)

merge-ort.c +11 -8

index a998f843a1da..37b69cbe0f9a 100644
@@ -3235,23 +3235,27 @@ static int checkout(struct merge_options *opt,
 	return ret;
 }
 
-static int record_conflicted_index_entries(struct merge_options *opt,
-					   struct index_state *index,
-					   struct strmap *paths,
-					   struct strmap *conflicted)
+static int record_conflicted_index_entries(struct merge_options *opt)
 {
 	struct hashmap_iter iter;
 	struct strmap_entry *e;
+	struct index_state *index = opt->repo->index;
+	struct checkout state = CHECKOUT_INIT;
 	int errs = 0;
 	int original_cache_nr;
 
-	if (strmap_empty(conflicted))
+	if (strmap_empty(&opt->priv->conflicted))
 		return 0;
 
+	/* If any entries have skip_worktree set, we'll have to check 'em out */
+	state.force = 1;
+	state.quiet = 1;
+	state.refresh_cache = 1;
+	state.istate = index;
 	original_cache_nr = index->cache_nr;
 
 	/* Put every entry from paths into plist, then sort */
-	strmap_for_each_entry(conflicted, &iter, e) {
+	strmap_for_each_entry(&opt->priv->conflicted, &iter, e) {
 		const char *path = e->key;
 		struct conflict_info *ci = e->value;
 		int pos;

@@ -3292,9 +3296,23 @@ static int record_conflicted_index_entries(struct merge_options *opt,
 			 * the higher order stages.  Thus, we need override
 			 * the CE_SKIP_WORKTREE bit and manually write those
 			 * files to the working disk here.
-			 *
-			 * TODO: Implement this CE_SKIP_WORKTREE fixup.
 			 */
+			if (ce_skip_worktree(ce)) {

From: Elijah Newren <[email protected]>

merge-ort handles submodules (and directory/file conflicts in general) differently than merge-recursive does; it basically puts all the special handling for different filetypes into one place in the codebase instead of needing special handling for different filetypes in many different code paths. This one code path in merge-ort could perhaps use some work still (there are still test_expect_failure cases in the testsuite), but it passes all the tests that merge-recursive does as well as 12 additional ones that merge-recursive fails. Mark those 12 tests as test_expect_success under merge-ort.

Signed-off-by Elijah Newren <[email protected]>

---
 t/t3512-cherry-pick-submodule.sh              | 9 +++++++--
 t/t3513-revert-submodule.sh                   | 7 ++++++-
 t/t5572-pull-submodule.sh                     | 9 +++++++--
 t/t6437-submodule-merge.sh                    | 5 +++--
 t/t6438-submodule-directory-file-conflicts.sh | 9 +++++++--
 5 files changed, 30 insertions(+), 9 deletions(-)

t/t3512-cherry-pick-submodule.sh +0 -0

index 822f2d4bfbd5..eb7a47b9d98a 100755
@@ -8,8 +8,13 @@ export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME
 . ./test-lib.sh
 . "$TEST_DIRECTORY"/lib-submodule-update.sh

From: Elijah Newren <[email protected]>

There are a variety of questions users might ask while resolving conflicts:
* What changes have been made since the previous (first) parent?
* What changes are staged?
* What is still unstaged? (or what is still conflicted?)
* What changes did I make to resolve conflicts so far?
The first three of these have simple answers:
* git diff HEAD
* git diff --cached
* git diff
There was no way to answer the final question previously. Adding one is trivial in merge-ort, since it works by creating a tree representing what should be written to the working copy complete with conflict markers. Simply write that tree to .git/AUTO_MERGE, allowing users to answer the fourth question with
* git diff AUTO_MERGE

I avoided using a name like "MERGE_AUTO", because that would be merge-specific (much like MERGE_HEAD, REBASE_HEAD, REVERT_HEAD, CHERRY_PICK_HEAD) and I wanted a name that didn't change depending on which type of operation the merge was part of.

Ensure that paths which clean out other temporary operation-specific files (e.g. CHERRY_PICK_HEAD, MERGE_MSG, rebase-merge/ state directory) also clean out this AUTO_MERGE file.

Signed-off-by Elijah Newren <[email protected]>

---
 branch.c         |  1 +
 builtin/rebase.c |  1 +
 merge-ort.c      | 10 ++++++++++
 path.c           |  1 +
 path.h           |  2 ++
 sequencer.c      |  5 +++++
 6 files changed, 20 insertions(+)

branch.c +1 -0

index 9c9dae1eae32..b71a2de29dbe 100644
@@ -344,6 +344,7 @@ void remove_merge_branch_state(struct repository *r)
 	unlink(git_path_merge_rr(r));
 	unlink(git_path_merge_msg(r));
 	unlink(git_path_merge_mode(r));
+	unlink(git_path_auto_merge(r));
 	save_autostash(git_path_merge_autostash(r));
 }
 

builtin/rebase.c +1 -0

index de400f9a1973..7d9afe118fd4 100644
@@ -739,6 +739,7 @@ static int finish_rebase(struct rebase_options *opts)
 	int ret = 0;
 
 	delete_ref(NULL, "REBASE_HEAD", NULL, REF_NO_DEREF);
+	unlink(git_path_auto_merge(the_repository));
 	apply_autostash(state_dir_path("autostash", opts));
 	close_object_store(the_repository->objects);
 	/*

merge-ort.c +3 -0

index 37b69cbe0f9a..cf927cd160e1 100644
@@ -3362,6 +3362,9 @@ void merge_switch_to_result(struct merge_options *opt,
 {
 	assert(opt->priv == NULL);
 	if (result->clean >= 0 && update_worktree_and_index) {
+		const char *filename;
+		FILE *fp;
+
 		trace2_region_enter("merge", "checkout", opt->repo);
 		if (checkout(opt, head, result->tree)) {
 			/* failure to function */

merge-ort.c +0 -0

 	}
 
 	if (display_update_msgs) {

path.c +1 -0

index 7b385e5eb282..9e883eb52446 100644
@@ -1534,5 +1534,6 @@ REPO_GIT_PATH_FUNC(merge_rr, "MERGE_RR")
 REPO_GIT_PATH_FUNC(merge_mode, "MERGE_MODE")
 REPO_GIT_PATH_FUNC(merge_head, "MERGE_HEAD")
 REPO_GIT_PATH_FUNC(merge_autostash, "MERGE_AUTOSTASH")
+REPO_GIT_PATH_FUNC(auto_merge, "AUTO_MERGE")
 REPO_GIT_PATH_FUNC(fetch_head, "FETCH_HEAD")
 REPO_GIT_PATH_FUNC(shallow, "shallow")

path.h +2 -0

index e7e77da6aaa5..251c78d98000 100644
@@ -176,6 +176,7 @@ struct path_cache {
 	const char *merge_mode;
 	const char *merge_head;
 	const char *merge_autostash;
+	const char *auto_merge;
 	const char *fetch_head;
 	const char *shallow;
 };

@@ -191,6 +192,7 @@ const char *git_path_merge_rr(struct repository *r);
 const char *git_path_merge_mode(struct repository *r);
 const char *git_path_merge_head(struct repository *r);
 const char *git_path_merge_autostash(struct repository *r);
+const char *git_path_auto_merge(struct repository *r);
 const char *git_path_fetch_head(struct repository *r);
 const char *git_path_shallow(struct repository *r);
 

sequencer.c +0 -0

index d2332d3e1787..472cdd8c620d 100644

sequencer.c +4 -0

 		fprintf(stderr,
 			_("dropping %s %s -- patch contents already upstream\n"),
 			oid_to_hex(&commit->object.oid), msg.subject);

@@ -2451,6 +2452,8 @@ void sequencer_post_commit_cleanup(struct repository *r, int verbose)
 		need_cleanup = 1;
 	}
 
+	unlink(git_path_auto_merge(r));
+
 	if (!need_cleanup)
 		return;
 

@@ -4111,6 +4114,7 @@ static int pick_commits(struct repository *r,
 			unlink(rebase_path_stopped_sha());
 			unlink(rebase_path_amend());
 			unlink(git_path_merge_head(r));
+			unlink(git_path_auto_merge(r));
 			delete_ref(NULL, "REBASE_HEAD", NULL, REF_NO_DEREF);
 
 			if (item->command == TODO_BREAK) {

@@ -4505,6 +4509,7 @@ static int commit_staged_changes(struct repository *r,
 		return error(_("could not commit staged changes."));
 	unlink(rebase_path_amend());
 	unlink(git_path_merge_head(r));
+	unlink(git_path_auto_merge(r));
 	if (final_fixup) {
 		unlink(rebase_path_fixup_msg());
 		unlink(rebase_path_squash_msg());

From: Elijah Newren <[email protected]>

The plan is to just delete merge-recursive, but not until everyone is comfortable with merge-ort as a replacement. Given that I haven't switched all callers of merge-recursive over yet (e.g. git-am still uses merge-recursive), maybe there's some value documenting known bugs in the algorithm in case we end up keeping it or someone wants to dig it up in the future.

In order to help Ævar test his tree-walk changes against merge-ort[1], this series completes the merge-ort implementation and cleans up testsuite failures...EXCEPT for some t6423 failures. It also leaves out a lot of performance work, which incidentally will fix the t6423 failures and is being reviewed independently[2].

This 11-patch series could be submitted as 7 independent series, 1-4 patches in length each, but it's probably easier for Ævar if we can merge just one more thing and it's only 11 total patches. This series sub-divides as follows:

* Patch 1: Fix bug in already-merged portion of merge-ort affecting rename/rename conflicts on platforms where qsort isn't stable. (Could be considered for merging before 2.31 since it is a new bug in the 2.31 cycle that I just learned of last night, but not sure it matters since merge-ort wasn't complete anyway and we're not even mentioning merge-ort in the release notes.)
* Patches 2-5: Add support for renormalization
* Patch 6: Add support for subtree shifting
* Patch 7-8: Add test and support for conflicts affecting sparse-checkout entries
* Patch 9: Update submodule related merge tests to note the ones that merge-ort fixes relative to merge-recursive
* Patch 10: New feature -- allow "git diff AUTO_MERGE" during conflict resolution to let user review changes they made since merge/rebase/cherry-pick/revert stopped and informed them of conflicts
* Patch 11: Add comments noting various bugs in merge-recursive

The last two patches aren't needed by Ævar, so they could be left out and submitted later. I just figured that it was only two more patches and they were part of "completing the merge-ort implementation" in my view.

[1] https://lore.kernel.org/git/[email protected]/ [2] See
https://lore.kernel.org/git/[email protected]/;
there are five more waiting after that -- viewable by the curious at
https://github.com/gitgitgadget/git/pulls?q=is%3Apr+author%3Anewren+Optimization+batch

Elijah Newren (11):
merge-ort: use STABLE_QSORT instead of QSORT where required
merge-ort: add a special minimal index just for renormalization
merge-ort: add a function for initializing our special attr_index
merge-ort: have ll_merge() calls use the attr_index for
renormalization
merge-ort: let renormalization change modify/delete into clean delete
merge-ort: support subtree shifting
t6428: new test for SKIP_WORKTREE handling and conflicts
merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries
t: mark several submodule merging tests as fixed under merge-ort
merge-ort: write $GIT_DIR/AUTO_MERGE whenever we hit a conflict
merge-recursive: add a bunch of FIXME comments documenting known bugs

 branch.c                                      |   1 +
 builtin/rebase.c                              |   1 +
 merge-ort.c                                   | 230 ++++++++++++++++--
 merge-recursive.c                             |  37 +++
 path.c                                        |   1 +
 path.h                                        |   2 +
 sequencer.c                                   |   5 +
 t/t3512-cherry-pick-submodule.sh              |   9 +-
 t/t3513-revert-submodule.sh                   |   7 +-
 t/t5572-pull-submodule.sh                     |   9 +-
 t/t6428-merge-conflicts-sparse.sh             | 158 ++++++++++++
 t/t6437-submodule-merge.sh                    |   5 +-
 t/t6438-submodule-directory-file-conflicts.sh |   9 +-
 13 files changed, 449 insertions(+), 25 deletions(-)
 create mode 100755 t/t6428-merge-conflicts-sparse.sh

base-commit: f01623b2c9d14207e497b21ebc6b3ec4afaf4b46
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-973%2Fnewren%2Fort-remainder-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-973/newren/ort-remainder-v1
Pull-Request: https://github.com/git/git/pull/973

Quoted 51 lines · Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>

If there is a conflict during a merge for a SKIP_WORKTREE entry, we expect that file to be written to the working copy and have the SKIP_WORKTREE bit cleared in the index. If the user had manually created a file in the working tree despite SKIP_WORKTREE being set, we do not want to clobber their changes to that file, but want to move it out of the way. Add tests that check for these behaviors.

Signed-off-by Elijah Newren <[email protected]>

---
 t/t6428-merge-conflicts-sparse.sh | 158 ++++++++++++++++++++++++++++++
 1 file changed, 158 insertions(+)
 create mode 100755 t/t6428-merge-conflicts-sparse.sh

t/t6428-merge-conflicts-sparse.sh new file +30 -0

new file mode 100755
index 000000000000..1bb52ff6f38c
@@ -0,0 +1,158 @@
+#!/bin/sh
+
+test_description="merge cases"
+
+# The setup for all of them, pictorially, is:
+#
+#      A
+#      o
+#     / \
+#  O o   ?
+#     \ /
+#      o
+#      B
+#
+# To help make it easier to follow the flow of tests, they have been
+# divided into sections and each test will start with a quick explanation
+# of what commits O, A, and B contain.
+#
+# Notation:
+#    z/{b,c}   means  files z/b and z/c both exist
+#    x/d_1     means  file x/d exists with content d1.  (Purpose of the
+#                     underscore notation is to differentiate different
+#                     files that might be renamed into each other's paths.)
+
+. ./test-lib.sh
+. "$TEST_DIRECTORY"/lib-merge.sh
+
+
+# Testcase basic, conflicting changes in 'numerals'
+

t/t6428-merge-conflicts-sparse.sh line 40

Quoted 10 lines

t/t6428-merge-conflicts-sparse.sh new file +10 -0

+test_setup_numerals () {
+     test_create_repo numerals_$1 &&
+     (
+             cd numerals_$1 &&
+
+             >README &&
+             test_write_lines I II III >numerals &&
+             git add README numerals &&
+             test_tick &&
+             git commit -m "O" &&

As an aside this could use the --printf option to test_commit I've got in next, but that's also a bit painful to use since you can't use test_write_lines.

I've wanted to just support something like this for this use-case of using an existing file:

    test_write_lines A B C D >lines &&
    test_commit --add O lines &&

Quoted 30 lines

t/t6428-merge-conflicts-sparse.sh new file +30 -0

+
+             git branch O &&
+             git branch A &&
+             git branch B &&
+
+             git checkout A &&
+             test_write_lines I II III IIII >numerals &&
+             git add numerals &&
+             test_tick &&
+             git commit -m "A" &&
+
+             git checkout B &&
+             test_write_lines I II III IV >numerals &&
+             git add numerals &&
+             test_tick &&
+             git commit -m "B" &&
+
+             cat <<-EOF >expected-index &&
+             H README
+             M numerals
+             M numerals
+             M numerals
+             EOF
+
+             cat <<-EOF >expected-merge
+             I
+             II
+             III
+             <<<<<<< HEAD
+             IIII

t/t6428-merge-conflicts-sparse.sh line 80

Quoted 10 lines

t/t6428-merge-conflicts-sparse.sh new file +10 -0

+             =======
+             IV
+             >>>>>>> B^0
+             EOF
+
+     )
+}
+
+test_expect_merge_algorithm success failure 'conflicting entries written to worktree even if sparse' '
+     test_setup_numerals plain &&

A small nit, but makes it easier to debug things: I think having what you have in "test_setup_numerals" above in a test_expect_success is a better pattern, then if it fails we can see where exactly.

Then instead of calling "test_setup_numerals" here you'd do:

    cp -R template plain &&

To just copy over that existing setup template, or re-use it and have have the tests call a small helper to "test_when_finish" reset --hard back as appropriate.

Quoted 61 lines · Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>

When merge conflicts occur in paths removed by a sparse-checkout, we need to unsparsify those paths (clear the SKIP_WORKTREE bit), and write out the conflicted file to the working copy. In the very unlikely case that someone manually put a file into the working copy at the location of the SKIP_WORKTREE file, we need to avoid overwriting whatever edits they have made and move that file to a different location first.

Signed-off-by Elijah Newren <[email protected]>

---
 merge-ort.c                       | 43 +++++++++++++++++++++----------
 t/t6428-merge-conflicts-sparse.sh |  4 +--
 2 files changed, 32 insertions(+), 15 deletions(-)

merge-ort.c +11 -8

index a998f843a1da..37b69cbe0f9a 100644
@@ -3235,23 +3235,27 @@ static int checkout(struct merge_options *opt,
      return ret;
 }
 
-static int record_conflicted_index_entries(struct merge_options *opt,
-                                        struct index_state *index,
-                                        struct strmap *paths,
-                                        struct strmap *conflicted)
+static int record_conflicted_index_entries(struct merge_options *opt)
 {
      struct hashmap_iter iter;
      struct strmap_entry *e;
+     struct index_state *index = opt->repo->index;
+     struct checkout state = CHECKOUT_INIT;
      int errs = 0;
      int original_cache_nr;
 
-     if (strmap_empty(conflicted))
+     if (strmap_empty(&opt->priv->conflicted))
              return 0;
 
+     /* If any entries have skip_worktree set, we'll have to check 'em out */
+     state.force = 1;
+     state.quiet = 1;
+     state.refresh_cache = 1;
+     state.istate = index;
      original_cache_nr = index->cache_nr;
 
      /* Put every entry from paths into plist, then sort */
-     strmap_for_each_entry(conflicted, &iter, e) {
+     strmap_for_each_entry(&opt->priv->conflicted, &iter, e) {
              const char *path = e->key;
              struct conflict_info *ci = e->value;
              int pos;

@@ -3292,9 +3296,23 @@ static int record_conflicted_index_entries(struct merge_options *opt,
                       * the higher order stages.  Thus, we need override
                       * the CE_SKIP_WORKTREE bit and manually write those
                       * files to the working disk here.
-                      *
-                      * TODO: Implement this CE_SKIP_WORKTREE fixup.
                       */
+                     if (ce_skip_worktree(ce)) {

merge-ort.c static int record_conflicted_index_entries(struct merge_options *opt, · line 3310

Quoted 10 lines

merge-ort.c +10 -0

+                             struct stat st;
+
+                             if (!lstat(path, &st)) {
+                                     char *new_name = unique_path(&opt->priv->paths,
+                                                                  path,
+                                                                  "cruft");
+
+                                     path_msg(opt, path, 1,
+                                              _("Note: %s not up to date and in way of checking out conflicted version; old copy renamed to %s"),
+                                              path, new_name);

I see this follows existing uses in merge-ort.c, but I wonder if this won't be quite unreadable on long paths, i.e.:

<long x> renamed to <long x.new>

As opposed to:

We had to rename your thing:
from: <long x>
to: <long x.new>

Quoted 19 lines · Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>

There are a variety of questions users might ask while resolving conflicts:
* What changes have been made since the previous (first) parent?
* What changes are staged?
* What is still unstaged? (or what is still conflicted?)
* What changes did I make to resolve conflicts so far?
The first three of these have simple answers:
* git diff HEAD
* git diff --cached
* git diff
There was no way to answer the final question previously. Adding one is trivial in merge-ort, since it works by creating a tree representing what should be written to the working copy complete with conflict markers. Simply write that tree to .git/AUTO_MERGE, allowing users to answer the fourth question with
* git diff AUTO_MERGE

Quoted 4 lines

I avoided using a name like "MERGE_AUTO", because that would be merge-specific (much like MERGE_HEAD, REBASE_HEAD, REVERT_HEAD, CHERRY_PICK_HEAD) and I wanted a name that didn't change depending on which type of operation the merge was part of.

That's a really cool feature. I'm starting to like this "ort" thing :)

(After knowing almost nothing about it until a few days ago...)

Quoted 58 lines

Ensure that paths which clean out other temporary operation-specific files (e.g. CHERRY_PICK_HEAD, MERGE_MSG, rebase-merge/ state directory) also clean out this AUTO_MERGE file.

Signed-off-by Elijah Newren <[email protected]>

---
 branch.c         |  1 +
 builtin/rebase.c |  1 +
 merge-ort.c      | 10 ++++++++++
 path.c           |  1 +
 path.h           |  2 ++
 sequencer.c      |  5 +++++
 6 files changed, 20 insertions(+)

branch.c +1 -0

index 9c9dae1eae32..b71a2de29dbe 100644
@@ -344,6 +344,7 @@ void remove_merge_branch_state(struct repository *r)
      unlink(git_path_merge_rr(r));
      unlink(git_path_merge_msg(r));
      unlink(git_path_merge_mode(r));
+     unlink(git_path_auto_merge(r));
      save_autostash(git_path_merge_autostash(r));
 }
 

builtin/rebase.c +1 -0

index de400f9a1973..7d9afe118fd4 100644
@@ -739,6 +739,7 @@ static int finish_rebase(struct rebase_options *opts)
      int ret = 0;
 
      delete_ref(NULL, "REBASE_HEAD", NULL, REF_NO_DEREF);
+     unlink(git_path_auto_merge(the_repository));
      apply_autostash(state_dir_path("autostash", opts));
      close_object_store(the_repository->objects);
      /*

merge-ort.c +5 -0

index 37b69cbe0f9a..cf927cd160e1 100644
@@ -3362,6 +3362,9 @@ void merge_switch_to_result(struct merge_options *opt,
 {
      assert(opt->priv == NULL);
      if (result->clean >= 0 && update_worktree_and_index) {
+             const char *filename;
+             FILE *fp;
+
              trace2_region_enter("merge", "checkout", opt->repo);
              if (checkout(opt, head, result->tree)) {
                      /* failure to function */

@@ -3380,6 +3383,13 @@ void merge_switch_to_result(struct merge_options *opt,
              }
              opt->priv = NULL;
              trace2_region_leave("merge", "record_conflicted", opt->repo);
+
+             trace2_region_enter("merge", "write_auto_merge", opt->repo);

merge-ort.c void merge_switch_to_result(struct merge_options *opt, · line 3392

Quoted 5 lines

merge-ort.c +5 -0

+             filename = git_path_auto_merge(opt->repo);
+             fp = xfopen(filename, "w");
+             fprintf(fp, "%s\n", oid_to_hex(&result->tree->object.oid));
+             fclose(fp);
+             trace2_region_leave("merge", "write_auto_merge", opt->repo);

This isn't a new problem since you're just folling an existing pattern, but here you (rightly) do xopen()< and the:n

Quoted 34 lines

merge-ort.c +0 -0

      }
 
      if (display_update_msgs) {

path.c +1 -0

index 7b385e5eb282..9e883eb52446 100644
@@ -1534,5 +1534,6 @@ REPO_GIT_PATH_FUNC(merge_rr, "MERGE_RR")
 REPO_GIT_PATH_FUNC(merge_mode, "MERGE_MODE")
 REPO_GIT_PATH_FUNC(merge_head, "MERGE_HEAD")
 REPO_GIT_PATH_FUNC(merge_autostash, "MERGE_AUTOSTASH")
+REPO_GIT_PATH_FUNC(auto_merge, "AUTO_MERGE")
 REPO_GIT_PATH_FUNC(fetch_head, "FETCH_HEAD")
 REPO_GIT_PATH_FUNC(shallow, "shallow")

path.h +2 -0

index e7e77da6aaa5..251c78d98000 100644
@@ -176,6 +176,7 @@ struct path_cache {
      const char *merge_mode;
      const char *merge_head;
      const char *merge_autostash;
+     const char *auto_merge;
      const char *fetch_head;
      const char *shallow;
 };

@@ -191,6 +192,7 @@ const char *git_path_merge_rr(struct repository *r);
 const char *git_path_merge_mode(struct repository *r);
 const char *git_path_merge_head(struct repository *r);
 const char *git_path_merge_autostash(struct repository *r);
+const char *git_path_auto_merge(struct repository *r);
 const char *git_path_fetch_head(struct repository *r);
 const char *git_path_shallow(struct repository *r);
 

sequencer.c static int do_pick_commit(struct repository *r, · line 2099

Quoted 9 lines

sequencer.c +1 -0

index d2332d3e1787..472cdd8c620d 100644
@@ -2096,6 +2096,7 @@ static int do_pick_commit(struct repository *r,
              refs_delete_ref(get_main_ref_store(r), "", "CHERRY_PICK_HEAD",
                              NULL, 0);
              unlink(git_path_merge_msg(r));
+             unlink(git_path_auto_merge(r));

Shouldn't this & the rest ideally be at least unlink_or_warn()?

Quoted 28 lines

sequencer.c +4 -0

              fprintf(stderr,
                      _("dropping %s %s -- patch contents already upstream\n"),
                      oid_to_hex(&commit->object.oid), msg.subject);

@@ -2451,6 +2452,8 @@ void sequencer_post_commit_cleanup(struct repository *r, int verbose)
              need_cleanup = 1;
      }
 
+     unlink(git_path_auto_merge(r));
+
      if (!need_cleanup)
              return;
 

@@ -4111,6 +4114,7 @@ static int pick_commits(struct repository *r,
                      unlink(rebase_path_stopped_sha());
                      unlink(rebase_path_amend());
                      unlink(git_path_merge_head(r));
+                     unlink(git_path_auto_merge(r));
                      delete_ref(NULL, "REBASE_HEAD", NULL, REF_NO_DEREF);
 
                      if (item->command == TODO_BREAK) {

@@ -4505,6 +4509,7 @@ static int commit_staged_changes(struct repository *r,
              return error(_("could not commit staged changes."));
      unlink(rebase_path_amend());
      unlink(git_path_merge_head(r));
+     unlink(git_path_auto_merge(r));
      if (final_fixup) {
              unlink(rebase_path_fixup_msg());
              unlink(rebase_path_squash_msg());

Quoted 5 lines · Elijah Newren via GitGitGadget

In order to help Ævar test his tree-walk changes against merge-ort[1], this series completes the merge-ort implementation and cleans up testsuite failures...EXCEPT for some t6423 failures. It also leaves out a lot of performance work, which incidentally will fix the t6423 failures and is being reviewed independently[2].

For those testing this in combination with their work, the expected failures are these specific tests:

    ./t6423-merge-rename-directories.sh (Wstat: 256 Tests: 68 Failed: 4)
      Failed tests:  7, 53, 55, 59

Perhaps I'm missing something but why not have [1] below on top of this series? It makes that test pass in both modes, and means we could e.g. follow-up by running CI with "ort".

That CI step seems worth doing sooner than later, even if it needs some GIT_TEST_SKIP for now...

Quoted 22 lines

This 11-patch series could be submitted as 7 independent series, 1-4 patches in length each, but it's probably easier for Ævar if we can merge just one more thing and it's only 11 total patches. This series sub-divides as follows:

* Patch 1: Fix bug in already-merged portion of merge-ort affecting rename/rename conflicts on platforms where qsort isn't stable. (Could be considered for merging before 2.31 since it is a new bug in the 2.31 cycle that I just learned of last night, but not sure it matters since merge-ort wasn't complete anyway and we're not even mentioning merge-ort in the release notes.)
* Patches 2-5: Add support for renormalization
* Patch 6: Add support for subtree shifting
* Patch 7-8: Add test and support for conflicts affecting sparse-checkout entries
* Patch 9: Update submodule related merge tests to note the ones that merge-ort fixes relative to merge-recursive
* Patch 10: New feature -- allow "git diff AUTO_MERGE" during conflict resolution to let user review changes they made since merge/rebase/cherry-pick/revert stopped and informed them of conflicts
* Patch 11: Add comments noting various bugs in merge-recursive

Quoted 3 lines

The last two patches aren't needed by Ævar, so they could be left out and submitted later. I just figured that it was only two more patches and they were part of "completing the merge-ort implementation" in my view.

This whole thing was a pleasant read, and helped me catch a subtle regression in my WIP "mode" work (which I'm now about to submit).

Reviewing this series suffered from the problem you have with writing code that's clearly good enough: Mostly all I had were minor nits, suggestions to re-arrange code differently etc.

That being said I'm not all that familiar with the guts of the merge logic, so I may have missed other issues...

Quoted 36 lines

[1] https://lore.kernel.org/git/[email protected]/ [2] See
https://lore.kernel.org/git/[email protected]/;
there are five more waiting after that -- viewable by the curious at
https://github.com/gitgitgadget/git/pulls?q=is%3Apr+author%3Anewren+Optimization+batch

Elijah Newren (11):
merge-ort: use STABLE_QSORT instead of QSORT where required
merge-ort: add a special minimal index just for renormalization
merge-ort: add a function for initializing our special attr_index
merge-ort: have ll_merge() calls use the attr_index for
renormalization
merge-ort: let renormalization change modify/delete into clean delete
merge-ort: support subtree shifting
t6428: new test for SKIP_WORKTREE handling and conflicts
merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries
t: mark several submodule merging tests as fixed under merge-ort
merge-ort: write $GIT_DIR/AUTO_MERGE whenever we hit a conflict
merge-recursive: add a bunch of FIXME comments documenting known bugs

 branch.c                                      |   1 +
 builtin/rebase.c                              |   1 +
 merge-ort.c                                   | 230 ++++++++++++++++--
 merge-recursive.c                             |  37 +++
 path.c                                        |   1 +
 path.h                                        |   2 +
 sequencer.c                                   |   5 +
 t/t3512-cherry-pick-submodule.sh              |   9 +-
 t/t3513-revert-submodule.sh                   |   7 +-
 t/t5572-pull-submodule.sh                     |   9 +-
 t/t6428-merge-conflicts-sparse.sh             | 158 ++++++++++++
 t/t6437-submodule-merge.sh                    |   5 +-
 t/t6438-submodule-directory-file-conflicts.sh |   9 +-
 13 files changed, 449 insertions(+), 25 deletions(-)
 create mode 100755 t/t6428-merge-conflicts-sparse.sh

Quoted 4 lines

base-commit: f01623b2c9d14207e497b21ebc6b3ec4afaf4b46
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-973%2Fnewren%2Fort-remainder-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-973/newren/ort-remainder-v1
Pull-Request: https://github.com/git/git/pull/973

1.:

t/t6423-merge-rename-directories.sh +5 -5

index 5d3b711fe68..4f6ead11e51 100755
@@ -507,7 +507,7 @@ test_setup_2a () {
        )
 }
 
-test_expect_success '2a: Directory split into two on one side, with equal numbers of paths' '
+test_expect_merge_algorithm success failure '2a: Directory split into two on one side, with equal numbers of paths' '
        test_setup_2a &&
        (
                cd 2a &&

@@ -3060,7 +3060,7 @@ test_setup_9g () {
        )
 }
 
-test_expect_failure '9g: Renamed directory that only contained immediate subdirs, immediate subdirs renamed' '
+test_expect_merge_algorithm failure failure '9g: Renamed directory that only contained immediate subdirs, immediate subdirs renamed' '
        test_setup_9g &&
        (
                cd 9g &&

@@ -4267,7 +4267,7 @@ test_setup_12b1 () {
        )
 }
 
-test_expect_merge_algorithm failure success '12b1: Moving two directory hierarchies into each other' '
+test_expect_merge_algorithm failure failure '12b1: Moving two directory hierarchies into each other' '
        test_setup_12b1 &&
        (
                cd 12b1 &&

@@ -4435,7 +4435,7 @@ test_setup_12c1 () {
        )
 }
 
-test_expect_merge_algorithm failure success '12c1: Moving one directory hierarchy into another w/ content merge' '
+test_expect_merge_algorithm failure failure '12c1: Moving one directory hierarchy into another w/ content merge' '
        test_setup_12c1 &&
        (
                cd 12c1 &&

@@ -4797,7 +4797,7 @@ test_setup_12f () {
        )
 }
 
-test_expect_merge_algorithm failure success '12f: Trivial directory resolve, caching, all kinds of fun' '
+test_expect_merge_algorithm failure failure '12f: Trivial directory resolve, caching, all kinds of fun' '
        test_setup_12f &&
        (
                cd 12f &&

Quoted 19 lines · Elijah Newren via GitGitGadget

From: Elijah Newren <[email protected]>

ll_merge() needs an index when renormalization is requested. Give it the special one we created exactly for that purpose. This fixes t6418.4 and t6418.5 under GIT_TEST_MERGE_ALGORITHM=ort.

Signed-off-by Elijah Newren <[email protected]>

---
 merge-ort.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

merge-ort.c +0 -0

index 028d1adcd2c9..87c553c0882c 100644
@@ -360,7 +360,7 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti,
      string_list_clear(&opti->paths_to_free, 0);
      opti->paths_to_free.strdup_strings = 0;
 

merge-ort.c static void clear_or_reinit_internal_opts(struct merge_options_internal *opti, · line 364

Quoted 3 lines

merge-ort.c +1 -1

-     if (opti->attr_index.cache_nr)
+     if (opti->attr_index.cache_nr) /* true iff opt->renormalize */
              discard_index(&opti->attr_index);

Perhaps instead of a comment, in that "if":

    assert(opt->renormalize);

Quoted 10 lines

merge-ort.c +0 -1

      /* Free memory used by various renames maps */

@@ -988,7 +988,6 @@ static int merge_submodule(struct merge_options *opt,
      return 0;
 }
 
-MAYBE_UNUSED
 static void initialize_attr_index(struct merge_options *opt)
 {
      /*

merge-ort.c static int merge_3way(struct merge_options *opt, · line 1065

Quoted 4 lines

merge-ort.c +1 -0

@@ -1063,6 +1062,8 @@ static int merge_3way(struct merge_options *opt,
      char *base, *name1, *name2;
      int merge_status;
 
+     initialize_attr_index(opt);

Subjective, but I think it's more readable to move the "initialized" check in initialize_attr_index() here, so:

    if (!attr_index->initialized)
        initialize_attr_index(opt);

Saves the reader a trip to the function to see that it doesn't do anything except exit early on that flag.

Quoted 13 lines

merge-ort.c +1 -1

      ll_opts.renormalize = opt->renormalize;
      ll_opts.extra_marker_size = extra_marker_size;
      ll_opts.xdl_opts = opt->xdl_opts;

@@ -1101,7 +1102,7 @@ static int merge_3way(struct merge_options *opt,
 
      merge_status = ll_merge(result_buf, path, &orig, base,
                              &src1, name1, &src2, name2,
-                             opt->repo->index, &ll_opts);
+                             &opt->priv->attr_index, &ll_opts);
 
      free(base);
      free(name1);

From: Elijah Newren <[email protected]>

renormalize_buffer() requires an index_state, which is something that merge-ort does not operate with. However, all the renormalization code needs is an index with a .gitattributes file...plus a little bit of setup. Create such an index, along with the deallocation and attr_direction handling.

A subsequent commit will add a function to finish the initialization of this index.

From: Elijah Newren <[email protected]>

ll_merge() needs an index when renormalization is requested. Create one specifically for just this purpose with just the one needed entry. This fixes t6418.4 and t6418.5 under GIT_TEST_MERGE_ALGORITHM=ort.

From: Elijah Newren <[email protected]>

If there is a conflict during a merge for a SKIP_WORKTREE entry, we expect that file to be written to the working copy and have the SKIP_WORKTREE bit cleared in the index. If the user had manually created a file in the working tree despite SKIP_WORKTREE being set, we do not want to clobber their changes to that file, but want to move it out of the way. Add tests that check for these behaviors.

From: Elijah Newren <[email protected]>

merge-ort handles submodules (and directory/file conflicts in general) differently than merge-recursive does; it basically puts all the special handling for different filetypes into one place in the codebase instead of needing special handling for different filetypes in many different code paths. This one code path in merge-ort could perhaps use some work still (there are still test_expect_failure cases in the testsuite), but it passes all the tests that merge-recursive does as well as 12 additional ones that merge-recursive fails. Mark those 12 tests as test_expect_success under merge-ort.

This series (nearly) completes the merge-ort implementation, cleaning up testsuite failures. The exceptions are some t6423 failures being addressed independently[1].

Quoted 3 lines · Elijah Newren via GitGitGadget

This series (nearly) completes the merge-ort implementation, cleaning up testsuite failures. The exceptions are some t6423 failures being addressed independently[1].

I like that most of the patches here are small and straight-forward, and are backed up by tests.

I'm concerned about the coupling of the "index with one entry" mechanism. I'd like to see that built differently by creating methods that can operate on an attributes file directly. If this method extraction is truly too difficult, then I'm willing to concede this point. It is worth some effort to try, though.

This series (nearly) completes the merge-ort implementation, cleaning up testsuite failures. The exceptions are some t6423 failures being addressed independently[1].