[PATCH 00/11] Complete merge-ort implementation...almost

[PATCH 00/11] Complete merge-ort implementation...almost

[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].

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/877dmmkhnt.fsf@evledraar.gmail.com/ [2] See
https://lore.kernel.org/git/pull.845.git.1614484707.gitgitgadget@gmail.com/;
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
-- 
gitgitgadget

[PATCH 01/11] merge-ort: use STABLE_QSORT instead of QSORT where required

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

rename/rename conflict handling depends on the fact that if both sides
renamed the same path, that the one on the MERGE_SIDE1 will appear first
in the combined diff_queue_struct passed to process_renames().  Since we
add all pairs from MERGE_SIDE1 to combined first, and then all pairs
from MERGE_SIDE2, and then sort based on filename, this will only be
true if the sort used is stable.  This was found due to the fact that
Mac, unlike Linux, apparently has a system-defined qsort that is not
stable.

While we are at it, review the other callers of QSORT and add comments
about why they can remain as calls to QSORT instead of being modified
to call STABLE_QSORT.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-ort.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/merge-ort.c b/merge-ort.c
index 603d30c52170..5309488fd9d8 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2289,7 +2289,7 @@ static int detect_and_process_renames(struct merge_options *opt,
 	clean &= collect_renames(opt, &combined, MERGE_SIDE2,
 				 &renames->dir_renames[1],
 				 &renames->dir_renames[2]);
-	QSORT(combined.queue, combined.nr, compare_pairs);
+	STABLE_QSORT(combined.queue, combined.nr, compare_pairs);
 	trace2_region_leave("merge", "directory renames", opt->repo);
 
 	trace2_region_enter("merge", "process renames", opt->repo);
@@ -2415,6 +2415,7 @@ static void write_tree(struct object_id *result_oid,
 	 */
 	relevant_entries.items = versions->items + offset;
 	relevant_entries.nr = versions->nr - offset;
+	/* No need for STABLE_QSORT -- filenames must be unique */
 	QSORT(relevant_entries.items, relevant_entries.nr, tree_entry_order);
 
 	/* Pre-allocate some space in buf */
@@ -3190,6 +3191,11 @@ static int record_conflicted_index_entries(struct merge_options *opt,
 	 * entries we added to the end into their right locations.
 	 */
 	remove_marked_cache_entries(index, 1);
+	/*
+	 * No need for STABLE_QSORT -- cmp_cache_name_compare sorts primarily
+	 * on filename and secondarily on stage, and (name, stage #) are a
+	 * unique tuple.
+	 */
 	QSORT(index->cache, index->cache_nr, cmp_cache_name_compare);
 
 	return errs;
-- 
gitgitgadget

[PATCH 02/11] merge-ort: add a special minimal index just for renormalization

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-ort.c | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/merge-ort.c b/merge-ort.c
index 5309488fd9d8..d91b66a052b6 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -18,6 +18,7 @@
 #include "merge-ort.h"
 
 #include "alloc.h"
+#include "attr.h"
 #include "blob.h"
 #include "cache-tree.h"
 #include "commit.h"
@@ -170,6 +171,16 @@ struct merge_options_internal {
 	 */
 	struct rename_info renames;
 
+	/*
+	 * attr_index: hacky minimal index used for renormalization
+	 *
+	 * renormalization code _requires_ an index, though it only needs to
+	 * find a .gitattributes file within the index.  So, when
+	 * renormalization is important, we create a special index with just
+	 * that one file.
+	 */
+	struct index_state attr_index;
+
 	/*
 	 * current_dir_name, toplevel_dir: temporary vars
 	 *
@@ -349,6 +360,9 @@ 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;
 
+	if (opti->attr_index.cache_nr)
+		discard_index(&opti->attr_index);
+
 	/* Free memory used by various renames maps */
 	for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) {
 		struct hashmap_iter iter;
@@ -3272,6 +3286,8 @@ void merge_finalize(struct merge_options *opt,
 {
 	struct merge_options_internal *opti = result->priv;
 
+	if (opt->renormalize)
+		git_attr_set_direction(GIT_ATTR_CHECKIN);
 	assert(opt->priv == NULL);
 
 	clear_or_reinit_internal_opts(opti, 0);
@@ -3347,6 +3363,10 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)
 	/* Default to histogram diff.  Actually, just hardcode it...for now. */
 	opt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);
 
+	/* Handle attr direction stuff for renormalization */
+	if (opt->renormalize)
+		git_attr_set_direction(GIT_ATTR_CHECKOUT);
+
 	/* Initialization of opt->priv, our internal merge data */
 	trace2_region_enter("merge", "allocate/init", opt->repo);
 	if (opt->priv) {
-- 
gitgitgadget

[PATCH 03/11] merge-ort: add a function for initializing our special attr_index

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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 <newren@gmail.com>
---
 merge-ort.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 61 insertions(+)

diff --git a/merge-ort.c b/merge-ort.c
index d91b66a052b6..028d1adcd2c9 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -988,6 +988,67 @@ static int merge_submodule(struct merge_options *opt,
 	return 0;
 }
 
+MAYBE_UNUSED
+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.
+	 */
+	struct merged_info *mi;
+	struct index_state *attr_index = &opt->priv->attr_index;
+	struct cache_entry *ce;
+
+	if (!opt->renormalize)
+		return;
+
+	if (attr_index->initialized)
+		return;
+	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);
+		ce->ce_mode = create_ce_mode(mi->result.mode);
+		ce->ce_flags = create_ce_flags(0);
+		ce->ce_namelen = len;
+		oidcpy(&ce->oid, &mi->result.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);
+	}
+	else {
+		int stage, len;
+		struct conflict_info *ci;
+
+		ASSIGN_AND_VERIFY_CI(ci, mi);
+		for (stage=0; stage<3; ++stage) {
+			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);
+		}
+	}
+}
+
 static int merge_3way(struct merge_options *opt,
 		      const char *path,
 		      const struct object_id *o,
-- 
gitgitgadget

[PATCH 04/11] merge-ort: have ll_merge() calls use the attr_index for renormalization

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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 <newren@gmail.com>
---
 merge-ort.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/merge-ort.c b/merge-ort.c
index 028d1adcd2c9..87c553c0882c 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -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;
 
-	if (opti->attr_index.cache_nr)
+	if (opti->attr_index.cache_nr) /* true iff opt->renormalize */
 		discard_index(&opti->attr_index);
 
 	/* 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)
 {
 	/*
@@ -1063,6 +1062,8 @@ static int merge_3way(struct merge_options *opt,
 	char *base, *name1, *name2;
 	int merge_status;
 
+	initialize_attr_index(opt);
+
 	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);
-- 
gitgitgadget

[PATCH 05/11] merge-ort: let renormalization change modify/delete into clean delete

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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 <newren@gmail.com>
---
 merge-ort.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 61 insertions(+), 2 deletions(-)

diff --git a/merge-ort.c b/merge-ort.c
index 87c553c0882c..c4bd88b9d3db 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -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)
+{
+	void *buf;
+	enum object_type type;
+	unsigned long size;
+	buf = read_object_file(oid, &type, &size);
+	if (!buf)
+		return err(opt, _("cannot read object %s"), oid_to_hex(oid));
+	if (type != OBJ_BLOB) {
+		free(buf);
+		return err(opt, _("object %s is not a blob"), oid_to_hex(oid));
+	}
+	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 {
 	/*
 	 * 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;
 
-		if (ci->path_conflict &&
-		    oideq(&ci->stages[0].oid, &ci->stages[side].oid)) {
+		if (opt->renormalize &&
+		    blob_unchanged(opt, &ci->stages[0], &ci->stages[side],
+				   path)) {
+			ci->merged.is_null = 1;
+			ci->merged.clean = 1;
+		} else if (ci->path_conflict &&
+			   oideq(&ci->stages[0].oid, &ci->stages[side].oid)) {
 			/*
 			 * This came from a rename/delete; no action to take,
 			 * but avoid printing "modify/delete" conflict notice
-- 
gitgitgadget

[PATCH 06/11] merge-ort: support subtree shifting

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

merge-recursive has some simple code to support subtree shifting; copy
it over to merge-ort.  This fixes t6409.12 under
GIT_TEST_MERGE_ALGORITHM=ort.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-ort.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

diff --git a/merge-ort.c b/merge-ort.c
index c4bd88b9d3db..a998f843a1da 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -3417,6 +3417,23 @@ void merge_finalize(struct merge_options *opt,
 
 /*** Function Grouping: helper functions for merge_incore_*() ***/
 
+static struct tree *shift_tree_object(struct repository *repo,
+				      struct tree *one, struct tree *two,
+				      const char *subtree_shift)
+{
+	struct object_id shifted;
+
+	if (!*subtree_shift) {
+		shift_tree(repo, &one->object.oid, &two->object.oid, &shifted, 0);
+	} else {
+		shift_tree_by(repo, &one->object.oid, &two->object.oid, &shifted,
+			      subtree_shift);
+	}
+	if (oideq(&two->object.oid, &shifted))
+		return two;
+	return lookup_tree(repo, &shifted);
+}
+
 static inline void set_commit_tree(struct commit *c, struct tree *t)
 {
 	c->maybe_tree = t;
@@ -3544,6 +3561,13 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,
 {
 	struct object_id working_tree_oid;
 
+	if (opt->subtree_shift) {
+		side2 = shift_tree_object(opt->repo, side1, side2,
+					  opt->subtree_shift);
+		merge_base = shift_tree_object(opt->repo, side1, merge_base,
+					       opt->subtree_shift);
+	}
+
 	trace2_region_enter("merge", "collect_merge_info", opt->repo);
 	if (collect_merge_info(opt, merge_base, side1, side2) != 0) {
 		/*
-- 
gitgitgadget

[PATCH 07/11] t6428: new test for SKIP_WORKTREE handling and conflicts

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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 <newren@gmail.com>
---
 t/t6428-merge-conflicts-sparse.sh | 158 ++++++++++++++++++++++++++++++
 1 file changed, 158 insertions(+)
 create mode 100755 t/t6428-merge-conflicts-sparse.sh

diff --git a/t/t6428-merge-conflicts-sparse.sh b/t/t6428-merge-conflicts-sparse.sh
new file mode 100755
index 000000000000..1bb52ff6f38c
--- /dev/null
+++ b/t/t6428-merge-conflicts-sparse.sh
@@ -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'
+
+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" &&
+
+		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
+		=======
+		IV
+		>>>>>>> B^0
+		EOF
+
+	)
+}
+
+test_expect_merge_algorithm success failure 'conflicting entries written to worktree even if sparse' '
+	test_setup_numerals plain &&
+	(
+		cd numerals_plain &&
+
+		git checkout A^0 &&
+
+		test_path_is_file README &&
+		test_path_is_file numerals &&
+
+		git sparse-checkout init &&
+		git sparse-checkout set README &&
+
+		test_path_is_file README &&
+		test_path_is_missing numerals &&
+
+		test_must_fail git merge -s recursive B^0 &&
+
+		git ls-files -t >index_files &&
+		test_cmp expected-index index_files &&
+
+		test_path_is_file README &&
+		test_path_is_file numerals &&
+
+		test_cmp expected-merge numerals &&
+
+		# 4 other files:
+		#   * expected-merge
+		#   * expected-index
+		#   * index_files
+		#   * others
+		git ls-files -o >others &&
+		test_line_count = 4 others
+	)
+'
+
+test_expect_merge_algorithm failure failure 'present-despite-SKIP_WORKTREE handled reasonably' '
+	test_setup_numerals in_the_way &&
+	(
+		cd numerals_in_the_way &&
+
+		git checkout A^0 &&
+
+		test_path_is_file README &&
+		test_path_is_file numerals &&
+
+		git sparse-checkout init &&
+		git sparse-checkout set README &&
+
+		test_path_is_file README &&
+		test_path_is_missing numerals &&
+
+		echo foobar >numerals &&
+
+		test_must_fail git merge -s recursive B^0 &&
+
+		git ls-files -t >index_files &&
+		test_cmp expected-index index_files &&
+
+		test_path_is_file README &&
+		test_path_is_file numerals &&
+
+		test_cmp expected-merge numerals &&
+
+		# There should still be a file with "foobar" in it
+		grep foobar * &&
+
+		# 5 other files:
+		#   * expected-merge
+		#   * expected-index
+		#   * index_files
+		#   * others
+		#   * whatever name was given to the numerals file that had
+		#     "foobar" in it
+		git ls-files -o >others &&
+		test_line_count = 5 others
+	)
+'
+
+test_done
-- 
gitgitgadget

[PATCH 08/11] merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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 <newren@gmail.com>
---
 merge-ort.c                       | 43 +++++++++++++++++++++----------
 t/t6428-merge-conflicts-sparse.sh |  4 +--
 2 files changed, 32 insertions(+), 15 deletions(-)

diff --git a/merge-ort.c b/merge-ort.c
index a998f843a1da..37b69cbe0f9a 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -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)) {
+				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);
+					errs |= rename(path, new_name);
+					free(new_name);
+				}
+				errs |= checkout_entry(ce, &state, NULL, NULL);
+			}
 
 			/*
 			 * Mark this cache entry for removal and instead add
@@ -3344,8 +3362,6 @@ void merge_switch_to_result(struct merge_options *opt,
 {
 	assert(opt->priv == NULL);
 	if (result->clean >= 0 && update_worktree_and_index) {
-		struct merge_options_internal *opti = result->priv;
-
 		trace2_region_enter("merge", "checkout", opt->repo);
 		if (checkout(opt, head, result->tree)) {
 			/* failure to function */
@@ -3355,13 +3371,14 @@ void merge_switch_to_result(struct merge_options *opt,
 		trace2_region_leave("merge", "checkout", opt->repo);
 
 		trace2_region_enter("merge", "record_conflicted", opt->repo);
-		if (record_conflicted_index_entries(opt, opt->repo->index,
-						    &opti->paths,
-						    &opti->conflicted)) {
+		opt->priv = result->priv;
+		if (record_conflicted_index_entries(opt)) {
 			/* failure to function */
+			opt->priv = NULL;
 			result->clean = -1;
 			return;
 		}
+		opt->priv = NULL;
 		trace2_region_leave("merge", "record_conflicted", opt->repo);
 	}
 
diff --git a/t/t6428-merge-conflicts-sparse.sh b/t/t6428-merge-conflicts-sparse.sh
index 1bb52ff6f38c..7e8bf497f821 100755
--- a/t/t6428-merge-conflicts-sparse.sh
+++ b/t/t6428-merge-conflicts-sparse.sh
@@ -76,7 +76,7 @@ test_setup_numerals () {
 	)
 }
 
-test_expect_merge_algorithm success failure 'conflicting entries written to worktree even if sparse' '
+test_expect_success 'conflicting entries written to worktree even if sparse' '
 	test_setup_numerals plain &&
 	(
 		cd numerals_plain &&
@@ -112,7 +112,7 @@ test_expect_merge_algorithm success failure 'conflicting entries written to work
 	)
 '
 
-test_expect_merge_algorithm failure failure 'present-despite-SKIP_WORKTREE handled reasonably' '
+test_expect_merge_algorithm failure success 'present-despite-SKIP_WORKTREE handled reasonably' '
 	test_setup_numerals in_the_way &&
 	(
 		cd numerals_in_the_way &&
-- 
gitgitgadget

[PATCH 09/11] t: mark several submodule merging tests as fixed under merge-ort

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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 <newren@gmail.com>
---
 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(-)

diff --git a/t/t3512-cherry-pick-submodule.sh b/t/t3512-cherry-pick-submodule.sh
index 822f2d4bfbd5..eb7a47b9d98a 100755
--- a/t/t3512-cherry-pick-submodule.sh
+++ b/t/t3512-cherry-pick-submodule.sh
@@ -8,8 +8,13 @@ export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME
 . ./test-lib.sh
 . "$TEST_DIRECTORY"/lib-submodule-update.sh
 
-KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
-KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
+if test "$GIT_TEST_MERGE_ALGORITHM" = ort
+then
+	:  # No special additional KNOWN_FAILURE knobs to set
+else
+	KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
+	KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
+fi
 test_submodule_switch "cherry-pick"
 
 test_expect_success 'unrelated submodule/file conflict is ignored' '
diff --git a/t/t3513-revert-submodule.sh b/t/t3513-revert-submodule.sh
index a759f12cbb1d..1f8157ad5ba5 100755
--- a/t/t3513-revert-submodule.sh
+++ b/t/t3513-revert-submodule.sh
@@ -30,7 +30,12 @@ git_revert () {
 	git revert HEAD
 }
 
-KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
+if test "$GIT_TEST_MERGE_ALGORITHM" = ort
+then
+	:  # No special additional KNOWN_FAILURE knobs to set
+else
+	KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
+fi
 test_submodule_switch_func "git_revert"
 
 test_done
diff --git a/t/t5572-pull-submodule.sh b/t/t5572-pull-submodule.sh
index 29537f4798ef..4b4495613d04 100755
--- a/t/t5572-pull-submodule.sh
+++ b/t/t5572-pull-submodule.sh
@@ -42,8 +42,13 @@ git_pull_noff () {
 	$2 git pull --no-ff
 }
 
-KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
-KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
+if test "$GIT_TEST_MERGE_ALGORITHM" = ort
+then
+	:  # No special additional KNOWN_FAILURE knobs to set
+else
+	KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
+	KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
+fi
 test_submodule_switch_func "git_pull_noff"
 
 test_expect_success 'pull --recurse-submodule setup' '
diff --git a/t/t6437-submodule-merge.sh b/t/t6437-submodule-merge.sh
index 0f92bcf326c8..e5e89c2045e7 100755
--- a/t/t6437-submodule-merge.sh
+++ b/t/t6437-submodule-merge.sh
@@ -6,6 +6,7 @@ GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main
 export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME
 
 . ./test-lib.sh
+. "$TEST_DIRECTORY"/lib-merge.sh
 
 #
 # history
@@ -328,7 +329,7 @@ test_expect_success 'setup file/submodule conflict' '
 	)
 '
 
-test_expect_failure 'file/submodule conflict' '
+test_expect_merge_algorithm failure success 'file/submodule conflict' '
 	test_when_finished "git -C file-submodule reset --hard" &&
 	(
 		cd file-submodule &&
@@ -437,7 +438,7 @@ test_expect_failure 'directory/submodule conflict; keep submodule clean' '
 	)
 '
 
-test_expect_failure !FAIL_PREREQS 'directory/submodule conflict; should not treat submodule files as untracked or in the way' '
+test_expect_merge_algorithm failure success !FAIL_PREREQS 'directory/submodule conflict; should not treat submodule files as untracked or in the way' '
 	test_when_finished "git -C directory-submodule/path reset --hard" &&
 	test_when_finished "git -C directory-submodule reset --hard" &&
 	(
diff --git a/t/t6438-submodule-directory-file-conflicts.sh b/t/t6438-submodule-directory-file-conflicts.sh
index 04bf4be7d792..abfa59d3684c 100755
--- a/t/t6438-submodule-directory-file-conflicts.sh
+++ b/t/t6438-submodule-directory-file-conflicts.sh
@@ -12,8 +12,13 @@ test_submodule_switch "merge --ff"
 
 test_submodule_switch "merge --ff-only"
 
-KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
-KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
+if test "$GIT_TEST_MERGE_ALGORITHM" = ort
+then
+	:  # No special additional KNOWN_FAILURE knobs to set
+else
+	KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
+	KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
+fi
 test_submodule_switch "merge --no-ff"
 
 test_done
-- 
gitgitgadget

[PATCH 10/11] merge-ort: write $GIT_DIR/AUTO_MERGE whenever we hit a conflict

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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 <newren@gmail.com>
---
 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(+)

diff --git a/branch.c b/branch.c
index 9c9dae1eae32..b71a2de29dbe 100644
--- a/branch.c
+++ b/branch.c
@@ -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));
 }
 
diff --git a/builtin/rebase.c b/builtin/rebase.c
index de400f9a1973..7d9afe118fd4 100644
--- a/builtin/rebase.c
+++ b/builtin/rebase.c
@@ -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);
 	/*
diff --git a/merge-ort.c b/merge-ort.c
index 37b69cbe0f9a..cf927cd160e1 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -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);
+		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);
 	}
 
 	if (display_update_msgs) {
diff --git a/path.c b/path.c
index 7b385e5eb282..9e883eb52446 100644
--- a/path.c
+++ b/path.c
@@ -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")
diff --git a/path.h b/path.h
index e7e77da6aaa5..251c78d98000 100644
--- a/path.h
+++ b/path.h
@@ -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);
 
diff --git a/sequencer.c b/sequencer.c
index d2332d3e1787..472cdd8c620d 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -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));
 		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());
-- 
gitgitgadget

[PATCH 11/11] merge-recursive: add a bunch of FIXME comments documenting known bugs

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-recursive.c | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)

diff --git a/merge-recursive.c b/merge-recursive.c
index b052974f191c..99a197597db5 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1075,6 +1075,11 @@ static int merge_3way(struct merge_options *opt,
 	read_mmblob(&src1, &a->oid);
 	read_mmblob(&src2, &b->oid);
 
+	/*
+	 * FIXME: Using a->path for normalization rules in ll_merge could be
+	 * wrong if we renamed from a->path to b->path.  We should use the
+	 * target path for where the file will be written.
+	 */
 	merge_status = ll_merge(result_buf, a->path, &orig, base,
 				&src1, name1, &src2, name2,
 				opt->repo->index, &ll_opts);
@@ -1154,6 +1159,8 @@ static void print_commit(struct commit *commit)
 	struct strbuf sb = STRBUF_INIT;
 	struct pretty_print_context ctx = {0};
 	ctx.date_mode.type = DATE_NORMAL;
+	/* FIXME: Merge this with output_commit_title() */
+	assert(!merge_remote_util(commit));
 	format_commit_message(commit, " %h: %m %s", &sb, &ctx);
 	fprintf(stderr, "%s\n", sb.buf);
 	strbuf_release(&sb);
@@ -1177,6 +1184,11 @@ static int merge_submodule(struct merge_options *opt,
 	int search = !opt->priv->call_depth;
 
 	/* store a in result in case we fail */
+	/* FIXME: This is the WRONG resolution for the recursive case when
+	 * we need to be careful to avoid accidentally matching either side.
+	 * Should probably use o instead there, much like we do for merging
+	 * binaries.
+	 */
 	oidcpy(result, a);
 
 	/* we can not handle deletion conflicts */
@@ -1301,6 +1313,13 @@ static int merge_mode_and_contents(struct merge_options *opt,
 
 	if ((S_IFMT & a->mode) != (S_IFMT & b->mode)) {
 		result->clean = 0;
+		/*
+		 * FIXME: This is a bad resolution for recursive case; for
+		 * the recursive case we want something that is unlikely to
+		 * accidentally match either side.  Also, while it makes
+		 * sense to prefer regular files over symlinks, it doesn't
+		 * make sense to prefer regular files over submodules.
+		 */
 		if (S_ISREG(a->mode)) {
 			result->blob.mode = a->mode;
 			oidcpy(&result->blob.oid, &a->oid);
@@ -1349,6 +1368,7 @@ static int merge_mode_and_contents(struct merge_options *opt,
 			free(result_buf.ptr);
 			if (ret)
 				return ret;
+			/* FIXME: bug, what if modes didn't match? */
 			result->clean = (merge_status == 0);
 		} else if (S_ISGITLINK(a->mode)) {
 			result->clean = merge_submodule(opt, &result->blob.oid,
@@ -2664,6 +2684,14 @@ static int process_renames(struct merge_options *opt,
 	struct string_list b_by_dst = STRING_LIST_INIT_NODUP;
 	const struct rename *sre;
 
+	/*
+	 * FIXME: As string-list.h notes, it's O(n^2) to build a sorted
+	 * string_list one-by-one, but O(n log n) to build it unsorted and
+	 * then sort it.  Note that as we build the list, we do not need to
+	 * check if the existing destination path is already in the list,
+	 * because the structure of diffcore_rename guarantees we won't
+	 * have duplicates.
+	 */
 	for (i = 0; i < a_renames->nr; i++) {
 		sre = a_renames->items[i].util;
 		string_list_insert(&a_by_dst, sre->pair->two->path)->util
@@ -3602,6 +3630,15 @@ static int merge_recursive_internal(struct merge_options *opt,
 			return err(opt, _("merge returned no commit"));
 	}
 
+	/*
+	 * FIXME: Since merge_recursive_internal() is only ever called by
+	 * places that ensure the index is loaded first
+	 * (e.g. builtin/merge.c, rebase/sequencer, etc.), in the common
+	 * case where the merge base was unique that means when we get here
+	 * we immediately discard the index and re-read it, which is a
+	 * complete waste of time.  We should only be discarding and
+	 * re-reading if we were forced to recurse.
+	 */
 	discard_index(opt->repo->index);
 	if (!opt->priv->call_depth)
 		repo_read_index(opt->repo);
-- 
gitgitgadget

Re: [PATCH 03/11] merge-ort: add a function for initializing our special attr_index

[Ævar Arnfjörð Bjarmason]

On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:

> From: Elijah Newren <newren@gmail.com>
>
> 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 <newren@gmail.com>
> ---
>  merge-ort.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 61 insertions(+)
>
> diff --git a/merge-ort.c b/merge-ort.c
> index d91b66a052b6..028d1adcd2c9 100644
> --- a/merge-ort.c
> +++ b/merge-ort.c
> @@ -988,6 +988,67 @@ static int merge_submodule(struct merge_options *opt,
>  	return 0;
>  }
>  
> +MAYBE_UNUSED

As with the lst series you had I also think this is better squashed with
04/11.

> +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.
> +	 */
> +	struct merged_info *mi;
> +	struct index_state *attr_index = &opt->priv->attr_index;
> +	struct cache_entry *ce;
> +
> +	if (!opt->renormalize)
> +		return;
> +
> +	if (attr_index->initialized)
> +		return;

Will comment on this in 04/11.

> +	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);
> +		ce->ce_mode = create_ce_mode(mi->result.mode);
> +		ce->ce_flags = create_ce_flags(0);
> +		ce->ce_namelen = len;
> +		oidcpy(&ce->oid, &mi->result.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);
> +	}
> +	else {

Style nit: } else {

> +		int stage, len;
> +		struct conflict_info *ci;
> +
> +		ASSIGN_AND_VERIFY_CI(ci, mi);
> +		for (stage=0; stage<3; ++stage) {

Style nit: stage < 3

Style nit: I find just stage++ to be more readable in for-loops, makes
no difference to the compiler, just more idiomatic.

> +			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);
> +		}
> +	}
> +}
> +

Re: [PATCH 04/11] merge-ort: have ll_merge() calls use the attr_index for renormalization

[Ævar Arnfjörð Bjarmason]

On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:

> From: Elijah Newren <newren@gmail.com>
>
> 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 <newren@gmail.com>
> ---
>  merge-ort.c | 7 ++++---
>  1 file changed, 4 insertions(+), 3 deletions(-)
>
> diff --git a/merge-ort.c b/merge-ort.c
> index 028d1adcd2c9..87c553c0882c 100644
> --- a/merge-ort.c
> +++ b/merge-ort.c
> @@ -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;
>  
> -	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);

>  	/* 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)
>  {
>  	/*
> @@ -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.

>  	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);

Re: [PATCH 05/11] merge-ort: let renormalization change modify/delete into clean delete

[Ævar Arnfjörð Bjarmason]

On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:

> From: Elijah Newren <newren@gmail.com>
>
> 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 <newren@gmail.com>
> ---
>  merge-ort.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 61 insertions(+), 2 deletions(-)
>
> diff --git a/merge-ort.c b/merge-ort.c
> index 87c553c0882c..c4bd88b9d3db 100644
> --- a/merge-ort.c
> +++ b/merge-ort.c
> @@ -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)
> +{
> +	void *buf;
> +	enum object_type type;
> +	unsigned long size;
> +	buf = read_object_file(oid, &type, &size);
> +	if (!buf)
> +		return err(opt, _("cannot read object %s"), oid_to_hex(oid));
> +	if (type != OBJ_BLOB) {
> +		free(buf);
> +		return err(opt, _("object %s is not a blob"), oid_to_hex(oid));

As an aside I've got another series I'll submit soon which refactors all
these "object is not xyz" calls to a utility function, so in this case
we'd also say what it was other than a blob.

Fine to keep this here, just a #leftoverbits note to myself to
eventually migrate this.

> +	}
> +	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 {
>  	/*
>  	 * 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;
>  
> -		if (ci->path_conflict &&
> -		    oideq(&ci->stages[0].oid, &ci->stages[side].oid)) {
> +		if (opt->renormalize &&
> +		    blob_unchanged(opt, &ci->stages[0], &ci->stages[side],
> +				   path)) {
> +			ci->merged.is_null = 1;
> +			ci->merged.clean = 1;
> +		} else if (ci->path_conflict &&
> +			   oideq(&ci->stages[0].oid, &ci->stages[side].oid)) {

Small note (no need for re-roll or whatever) on having read a bit of
merge-ort.c code recently: I'd find this thing a bit easier on the eyes
if ci->stages[0] and ci->stages[side] were split into a variable before
the if/else, i.e. used as "side_0.oid and side_n.oid" and "side_0 and
side_n" in this case..

That would also avoid the wrapping of at least one argument list here.

Re: [PATCH 07/11] t6428: new test for SKIP_WORKTREE handling and conflicts

[Ævar Arnfjörð Bjarmason]

On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:

> From: Elijah Newren <newren@gmail.com>
>
> 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 <newren@gmail.com>
> ---
>  t/t6428-merge-conflicts-sparse.sh | 158 ++++++++++++++++++++++++++++++
>  1 file changed, 158 insertions(+)
>  create mode 100755 t/t6428-merge-conflicts-sparse.sh
>
> diff --git a/t/t6428-merge-conflicts-sparse.sh b/t/t6428-merge-conflicts-sparse.sh
> new file mode 100755
> index 000000000000..1bb52ff6f38c
> --- /dev/null
> +++ b/t/t6428-merge-conflicts-sparse.sh
> @@ -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'
> +
> +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 &&


> +
> +		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
> +		=======
> +		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.

Re: [PATCH 08/11] merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries

[Ævar Arnfjörð Bjarmason]

On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:

> From: Elijah Newren <newren@gmail.com>
>
> 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 <newren@gmail.com>
> ---
>  merge-ort.c                       | 43 +++++++++++++++++++++----------
>  t/t6428-merge-conflicts-sparse.sh |  4 +--
>  2 files changed, 32 insertions(+), 15 deletions(-)
>
> diff --git a/merge-ort.c b/merge-ort.c
> index a998f843a1da..37b69cbe0f9a 100644
> --- a/merge-ort.c
> +++ b/merge-ort.c
> @@ -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)) {
> +				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>

Re: [PATCH 09/11] t: mark several submodule merging tests as fixed under merge-ort

[Ævar Arnfjörð Bjarmason]

On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:

> From: Elijah Newren <newren@gmail.com>
>
> 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 <newren@gmail.com>
> ---
>  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(-)
>
> diff --git a/t/t3512-cherry-pick-submodule.sh b/t/t3512-cherry-pick-submodule.sh
> index 822f2d4bfbd5..eb7a47b9d98a 100755
> --- a/t/t3512-cherry-pick-submodule.sh
> +++ b/t/t3512-cherry-pick-submodule.sh
> @@ -8,8 +8,13 @@ export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME
>  . ./test-lib.sh
>  . "$TEST_DIRECTORY"/lib-submodule-update.sh
>  
> -KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
> -KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
> +if test "$GIT_TEST_MERGE_ALGORITHM" = ort
> +then
> +	:  # No special additional KNOWN_FAILURE knobs to set
> +else
> +	KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
> +	KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
> +fi

nit: I think this and the rest would be just as readable/obvious without
the comment as:

    if test "$x" != ort
    then
            some_vars=xyz
    fi

Re: [PATCH 10/11] merge-ort: write $GIT_DIR/AUTO_MERGE whenever we hit a conflict

[Ævar Arnfjörð Bjarmason]

On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:

> From: Elijah Newren <newren@gmail.com>
>
> 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.

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...)

> 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 <newren@gmail.com>
> ---
>  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(+)
>
> diff --git a/branch.c b/branch.c
> index 9c9dae1eae32..b71a2de29dbe 100644
> --- a/branch.c
> +++ b/branch.c
> @@ -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));
>  }
>  
> diff --git a/builtin/rebase.c b/builtin/rebase.c
> index de400f9a1973..7d9afe118fd4 100644
> --- a/builtin/rebase.c
> +++ b/builtin/rebase.c
> @@ -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);
>  	/*
> diff --git a/merge-ort.c b/merge-ort.c
> index 37b69cbe0f9a..cf927cd160e1 100644
> --- a/merge-ort.c
> +++ b/merge-ort.c
> @@ -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);
> +		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

>  	}
>  
>  	if (display_update_msgs) {
> diff --git a/path.c b/path.c
> index 7b385e5eb282..9e883eb52446 100644
> --- a/path.c
> +++ b/path.c
> @@ -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")
> diff --git a/path.h b/path.h
> index e7e77da6aaa5..251c78d98000 100644
> --- a/path.h
> +++ b/path.h
> @@ -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);
>  
> diff --git a/sequencer.c b/sequencer.c
> index d2332d3e1787..472cdd8c620d 100644
> --- a/sequencer.c
> +++ b/sequencer.c
> @@ -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()?

>  		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());

Re: [PATCH 11/11] merge-recursive: add a bunch of FIXME comments documenting known bugs

[Ævar Arnfjörð Bjarmason]

On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:

> From: Elijah Newren <newren@gmail.com>
>
> 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.

Yes, I think that's very useful.

Re: [PATCH 00/11] Complete merge-ort implementation...almost

[Ævar Arnfjörð Bjarmason]

On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:

> 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...

> 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.

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...

> [1] https://lore.kernel.org/git/877dmmkhnt.fsf@evledraar.gmail.com/ [2] See
> https://lore.kernel.org/git/pull.845.git.1614484707.gitgitgadget@gmail.com/;
> 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

1.:

diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh
index 5d3b711fe68..4f6ead11e51 100755
--- a/t/t6423-merge-rename-directories.sh
+++ b/t/t6423-merge-rename-directories.sh
@@ -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 &&

Re: [PATCH 07/11] t6428: new test for SKIP_WORKTREE handling and conflicts

[Elijah Newren]

On Mon, Mar 8, 2021 at 5:03 AM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>
>
> On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:
>
> > From: Elijah Newren <newren@gmail.com>
> >
> > 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 <newren@gmail.com>
> > ---
> >  t/t6428-merge-conflicts-sparse.sh | 158 ++++++++++++++++++++++++++++++
> >  1 file changed, 158 insertions(+)
> >  create mode 100755 t/t6428-merge-conflicts-sparse.sh
> >
> > diff --git a/t/t6428-merge-conflicts-sparse.sh b/t/t6428-merge-conflicts-sparse.sh
> > new file mode 100755
> > index 000000000000..1bb52ff6f38c
> > --- /dev/null
> > +++ b/t/t6428-merge-conflicts-sparse.sh
> > @@ -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'
> > +
> > +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 &&
>
>
> > +
> > +             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
> > +             =======
> > +             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.

I used to have tests follow that pattern, but Dscho objected
strenuously to it; see e.g.
https://lore.kernel.org/git/nycvar.QRO.7.76.6.1910141211130.46@tvgsbejvaqbjf.bet/

I went through and replaced most of the merge-recursive-related ones
to the current style to help him out.

Re: [PATCH 08/11] merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries

[Elijah Newren]

On Mon, Mar 8, 2021 at 5:06 AM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>
>
> On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:
>
> > From: Elijah Newren <newren@gmail.com>
> >
> > 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 <newren@gmail.com>
> > ---
> >  merge-ort.c                       | 43 +++++++++++++++++++++----------
> >  t/t6428-merge-conflicts-sparse.sh |  4 +--
> >  2 files changed, 32 insertions(+), 15 deletions(-)
> >
> > diff --git a/merge-ort.c b/merge-ort.c
> > index a998f843a1da..37b69cbe0f9a 100644
> > --- a/merge-ort.c
> > +++ b/merge-ort.c
> > @@ -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)) {
> > +                             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>

Makes sense, but it seems like something we'd want to do to a lot of
messages rather than just this one.  For now, especially given that I
expect this particular message to be *very* rare, I think I'll leave
this one as-is for now but we can address this idea in a subsequent
series or as #leftoverbits.

Re: [PATCH 10/11] merge-ort: write $GIT_DIR/AUTO_MERGE whenever we hit a conflict

[Elijah Newren]

On Mon, Mar 8, 2021 at 5:11 AM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>
>
> On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:
>
> > From: Elijah Newren <newren@gmail.com>
> >
> > 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.
>
> 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...)
>
> > 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 <newren@gmail.com>
> > ---
> >  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(+)
> >
> > diff --git a/branch.c b/branch.c
> > index 9c9dae1eae32..b71a2de29dbe 100644
> > --- a/branch.c
> > +++ b/branch.c
> > @@ -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));
> >  }
> >
> > diff --git a/builtin/rebase.c b/builtin/rebase.c
> > index de400f9a1973..7d9afe118fd4 100644
> > --- a/builtin/rebase.c
> > +++ b/builtin/rebase.c
> > @@ -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);
> >       /*
> > diff --git a/merge-ort.c b/merge-ort.c
> > index 37b69cbe0f9a..cf927cd160e1 100644
> > --- a/merge-ort.c
> > +++ b/merge-ort.c
> > @@ -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);
> > +             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

Looks like your comment got garbled/truncated.  Do you remember the
rest of what you were going to say here?

> >       }
> >
> >       if (display_update_msgs) {
> > diff --git a/path.c b/path.c
> > index 7b385e5eb282..9e883eb52446 100644
> > --- a/path.c
> > +++ b/path.c
> > @@ -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")
> > diff --git a/path.h b/path.h
> > index e7e77da6aaa5..251c78d98000 100644
> > --- a/path.h
> > +++ b/path.h
> > @@ -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);
> >
> > diff --git a/sequencer.c b/sequencer.c
> > index d2332d3e1787..472cdd8c620d 100644
> > --- a/sequencer.c
> > +++ b/sequencer.c
> > @@ -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()?

Perhaps, but I think that should be a follow-on series or
#leftoverbits.  I'm having enough trouble getting reviews (I think I'm
burning Stolee out after the last half year) without making my series
longer for tangential cleanups.  :-)

I'm starting to worry that despite having all the remaining patches
ready (and most have been ready for months), that we won't be able to
get merge-ort done before git-2.32 -- the -rc0 for it is now just
under three months away.

> >               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());

Re: [PATCH 00/11] Complete merge-ort implementation...almost

[Elijah Newren]

On Mon, Mar 8, 2021 at 6:43 AM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>
>
> On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:
>
> > 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...

Oh, um, mostly it was history and the fact that I just never took a
step back.  When I started adding merge-ort, there were 2200+ tests
that were failing, and marking them all as test_expect_fail was just a
useless code churn; we knew it'd fail when the implemenation basically
just called die().  At some point I got it down to 8 tests failing,
but felt I needed to quickly switch tracks to upstream the
diffcore-rename work since we had an Outreachy intern that was going
to be buildiing on it and/or making changes that might conflict with
it.  I was still in the mode of fixing them through completing the
implementation rather than stepping back and saying, "Hey, we only
have a few tests left failing; let's mark them as such.".

However, all that said, making this change _now_ would semantically
conflict with ort-perf-batch-9[1] (which was submitted first), since
it fixes one of the four tests.  It'd also mean a similar semantic
conflict for ort-perf-batch-10 (which fixes another) and
ort-perf-batch-12 (which fixes the last 2), or those series will have
to depend on a merge of ort-perf-batch-9 and this series.  Relying on
special merges for some of the earlier patches for merge-ort seems
like it was a bit of a pain and I'd rather not put Junio through that.
Also, if we do it, and don't have Junio mark the fixes as things are
merged, then we have to decide on a topic order.  So, Junio: thoughts?

[1] https://lore.kernel.org/git/pull.845.git.1614484707.gitgitgadget@gmail.com/

> > 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.
>
> 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).

Wahoo for helping catch regressions!  :-)

> 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.

Thanks for taking a look.  You had lots of good small suggestions that
I'll incorporate in a re-roll.  There were a couple that sounded like
they should be split off into their own sets of cleanup patches that
I'll defer for now.

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

>
> > [1] https://lore.kernel.org/git/877dmmkhnt.fsf@evledraar.gmail.com/ [2] See
> > https://lore.kernel.org/git/pull.845.git.1614484707.gitgitgadget@gmail.com/;
> > 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
>
> 1.:
>
> diff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh
> index 5d3b711fe68..4f6ead11e51 100755
> --- a/t/t6423-merge-rename-directories.sh
> +++ b/t/t6423-merge-rename-directories.sh
> @@ -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 &&

Re: [PATCH 04/11] merge-ort: have ll_merge() calls use the attr_index for renormalization

[Elijah Newren]

On Mon, Mar 8, 2021 at 4:49 AM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>
>
> On Fri, Mar 05 2021, Elijah Newren via GitGitGadget wrote:
>
> > From: Elijah Newren <newren@gmail.com>
> >
> > 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 <newren@gmail.com>
> > ---
> >  merge-ort.c | 7 ++++---
> >  1 file changed, 4 insertions(+), 3 deletions(-)
> >
> > diff --git a/merge-ort.c b/merge-ort.c
> > index 028d1adcd2c9..87c553c0882c 100644
> > --- a/merge-ort.c
> > +++ b/merge-ort.c
> > @@ -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;
> >
> > -     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);

I would, but opt isn't defined here, and passing it in merely for an
assertion seems overboard.

> >       /* 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)
> >  {
> >       /*
> > @@ -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.

Makes sense; I'll fix this up.

>
> >       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);
>

[PATCH v2 00/10] Complete merge-ort implementation...almost

[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].

Changes since v1, to address feedback from Ævar:

 * Squashed patches 3 & 4
 * Various style fixes
 * Check attr_index->initialized before calling initialize_attr_index()
   instead of inside initialize_attr_index()
 * Simplify GIT_TEST_MERGE_ALGORITHM comparison to only have if-then block

Stuff not included in v2:

 * Ævar suggested patching the test expectation on the 4 known failing tests
   so that all tests passed under GIT_TEST_MERGE_ALGORITHM=ort. Seems
   reasonable, but the semantic conflicts with other series might make it
   more trouble than it's worth and other series will fix all 4 tests.
   Leaving as-is for now to avoid putting more burden on Junio; see
   https://lore.kernel.org/git/CABPp-BHeR6m4-M=nSX5NZtA2js3E3EVbAyDSMtp3-rN2QnUjqw@mail.gmail.com/
 * Ævar noted a few bigger cleanups to surrounding code that could also be
   done, even if orthogonal to this series. I'll leave those for other
   series to address.

[1] See
https://lore.kernel.org/git/pull.845.git.1614484707.gitgitgadget@gmail.com/
and batch 10 and 12 from
https://github.com/gitgitgadget/git/pulls?q=is%3Apr+author%3Anewren+Optimization+batch

Elijah Newren (10):
  merge-ort: use STABLE_QSORT instead of QSORT where required
  merge-ort: add a special minimal index just for renormalization
  merge-ort: have ll_merge() use a special 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                                   | 229 ++++++++++++++++--
 merge-recursive.c                             |  37 +++
 path.c                                        |   1 +
 path.h                                        |   2 +
 sequencer.c                                   |   5 +
 t/t3512-cherry-pick-submodule.sh              |   7 +-
 t/t3513-revert-submodule.sh                   |   5 +-
 t/t5572-pull-submodule.sh                     |   7 +-
 t/t6428-merge-conflicts-sparse.sh             | 158 ++++++++++++
 t/t6437-submodule-merge.sh                    |   5 +-
 t/t6438-submodule-directory-file-conflicts.sh |   7 +-
 13 files changed, 440 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-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-973/newren/ort-remainder-v2
Pull-Request: https://github.com/git/git/pull/973

Range-diff vs v1:

  1:  3ca16a5e3466 =  1:  3ca16a5e3466 merge-ort: use STABLE_QSORT instead of QSORT where required
  2:  24454e67b186 =  2:  24454e67b186 merge-ort: add a special minimal index just for renormalization
  3:  815af5d30ebd !  3:  386cb3230b67 merge-ort: add a function for initializing our special attr_index
     @@ Metadata
      Author: Elijah Newren <newren@gmail.com>
      
       ## Commit message ##
     -    merge-ort: add a function for initializing our special attr_index
     +    merge-ort: have ll_merge() use a special attr_index for renormalization
      
     -    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.
     +    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.
      
          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
     @@ Commit message
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
       ## merge-ort.c ##
     +@@ merge-ort.c: 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;
     + 
     +-	if (opti->attr_index.cache_nr)
     ++	if (opti->attr_index.cache_nr) /* true iff opt->renormalize */
     + 		discard_index(&opti->attr_index);
     + 
     + 	/* Free memory used by various renames maps */
      @@ merge-ort.c: 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_submodule(struct merge_options *opt,
      +	struct index_state *attr_index = &opt->priv->attr_index;
      +	struct cache_entry *ce;
      +
     -+	if (!opt->renormalize)
     -+		return;
     ++	attr_index->initialized = 1;
      +
     -+	if (attr_index->initialized)
     ++	if (!opt->renormalize)
      +		return;
     -+	attr_index->initialized = 1;
      +
      +	mi = strmap_get(&opt->priv->paths, GITATTRIBUTES_FILE);
      +	if (!mi)
     @@ merge-ort.c: static int merge_submodule(struct merge_options *opt,
      +		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);
     -+	}
     -+	else {
     ++	} else {
      +		int stage, len;
      +		struct conflict_info *ci;
      +
      +		ASSIGN_AND_VERIFY_CI(ci, mi);
     -+		for (stage=0; stage<3; ++stage) {
     ++		for (stage = 0; stage < 3; stage++) {
      +			unsigned stage_mask = (1 << stage);
      +
      +			if (!(ci->filemask & stage_mask))
     @@ merge-ort.c: static int merge_submodule(struct merge_options *opt,
       static int merge_3way(struct merge_options *opt,
       		      const char *path,
       		      const struct object_id *o,
     +@@ merge-ort.c: static int merge_3way(struct merge_options *opt,
     + 	char *base, *name1, *name2;
     + 	int merge_status;
     + 
     ++	if (!opt->priv->attr_index.initialized)
     ++		initialize_attr_index(opt);
     ++
     + 	ll_opts.renormalize = opt->renormalize;
     + 	ll_opts.extra_marker_size = extra_marker_size;
     + 	ll_opts.xdl_opts = opt->xdl_opts;
     +@@ merge-ort.c: 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);
  4:  cb035ac5fe4a <  -:  ------------ merge-ort: have ll_merge() calls use the attr_index for renormalization
  5:  b70ef4d7000a !  4:  7fcabded5016 merge-ort: let renormalization change modify/delete into clean delete
     @@ merge-ort.c: static int string_list_df_name_compare(const char *one, const char
      +	int ret = 0; /* assume changed for safety */
      +	const struct index_state *idx = &opt->priv->attr_index;
      +
     -+	initialize_attr_index(opt);
     ++	if (!idx->initialized)
     ++		initialize_attr_index(opt);
      +
      +	if (base->mode != side->mode)
      +		return 0;
  6:  d04ddabde124 =  5:  e21eea71e707 merge-ort: support subtree shifting
  7:  6ccb24b557fc =  6:  d1d8c017b23f t6428: new test for SKIP_WORKTREE handling and conflicts
  8:  100c0187bdfe =  7:  90a57ade629d merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries
  9:  95a6c0abe558 !  8:  fcce88c5ac3d t: mark several submodule merging tests as fixed under merge-ort
     @@ t/t3512-cherry-pick-submodule.sh: export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME
       
      -KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
      -KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
     -+if test "$GIT_TEST_MERGE_ALGORITHM" = ort
     ++if test "$GIT_TEST_MERGE_ALGORITHM" != ort
      +then
     -+	:  # No special additional KNOWN_FAILURE knobs to set
     -+else
      +	KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
      +	KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
      +fi
     @@ t/t3513-revert-submodule.sh: git_revert () {
       }
       
      -KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
     -+if test "$GIT_TEST_MERGE_ALGORITHM" = ort
     ++if test "$GIT_TEST_MERGE_ALGORITHM" != ort
      +then
     -+	:  # No special additional KNOWN_FAILURE knobs to set
     -+else
      +	KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
      +fi
       test_submodule_switch_func "git_revert"
     @@ t/t5572-pull-submodule.sh: git_pull_noff () {
       
      -KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
      -KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
     -+if test "$GIT_TEST_MERGE_ALGORITHM" = ort
     ++if test "$GIT_TEST_MERGE_ALGORITHM" != ort
      +then
     -+	:  # No special additional KNOWN_FAILURE knobs to set
     -+else
      +	KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
      +	KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
      +fi
     @@ t/t6438-submodule-directory-file-conflicts.sh: test_submodule_switch "merge --ff
       
      -KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
      -KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
     -+if test "$GIT_TEST_MERGE_ALGORITHM" = ort
     ++if test "$GIT_TEST_MERGE_ALGORITHM" != ort
      +then
     -+	:  # No special additional KNOWN_FAILURE knobs to set
     -+else
      +	KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
      +	KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
      +fi
 10:  d8c6eb39aa7c =  9:  93b241c2f213 merge-ort: write $GIT_DIR/AUTO_MERGE whenever we hit a conflict
 11:  0409118d4ff7 = 10:  a9a95bb0391f merge-recursive: add a bunch of FIXME comments documenting known bugs

-- 
gitgitgadget

[PATCH v2 01/10] merge-ort: use STABLE_QSORT instead of QSORT where required

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

rename/rename conflict handling depends on the fact that if both sides
renamed the same path, that the one on the MERGE_SIDE1 will appear first
in the combined diff_queue_struct passed to process_renames().  Since we
add all pairs from MERGE_SIDE1 to combined first, and then all pairs
from MERGE_SIDE2, and then sort based on filename, this will only be
true if the sort used is stable.  This was found due to the fact that
Mac, unlike Linux, apparently has a system-defined qsort that is not
stable.

While we are at it, review the other callers of QSORT and add comments
about why they can remain as calls to QSORT instead of being modified
to call STABLE_QSORT.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-ort.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/merge-ort.c b/merge-ort.c
index 603d30c52170..5309488fd9d8 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2289,7 +2289,7 @@ static int detect_and_process_renames(struct merge_options *opt,
 	clean &= collect_renames(opt, &combined, MERGE_SIDE2,
 				 &renames->dir_renames[1],
 				 &renames->dir_renames[2]);
-	QSORT(combined.queue, combined.nr, compare_pairs);
+	STABLE_QSORT(combined.queue, combined.nr, compare_pairs);
 	trace2_region_leave("merge", "directory renames", opt->repo);
 
 	trace2_region_enter("merge", "process renames", opt->repo);
@@ -2415,6 +2415,7 @@ static void write_tree(struct object_id *result_oid,
 	 */
 	relevant_entries.items = versions->items + offset;
 	relevant_entries.nr = versions->nr - offset;
+	/* No need for STABLE_QSORT -- filenames must be unique */
 	QSORT(relevant_entries.items, relevant_entries.nr, tree_entry_order);
 
 	/* Pre-allocate some space in buf */
@@ -3190,6 +3191,11 @@ static int record_conflicted_index_entries(struct merge_options *opt,
 	 * entries we added to the end into their right locations.
 	 */
 	remove_marked_cache_entries(index, 1);
+	/*
+	 * No need for STABLE_QSORT -- cmp_cache_name_compare sorts primarily
+	 * on filename and secondarily on stage, and (name, stage #) are a
+	 * unique tuple.
+	 */
 	QSORT(index->cache, index->cache_nr, cmp_cache_name_compare);
 
 	return errs;
-- 
gitgitgadget

[PATCH v2 02/10] merge-ort: add a special minimal index just for renormalization

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-ort.c | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/merge-ort.c b/merge-ort.c
index 5309488fd9d8..d91b66a052b6 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -18,6 +18,7 @@
 #include "merge-ort.h"
 
 #include "alloc.h"
+#include "attr.h"
 #include "blob.h"
 #include "cache-tree.h"
 #include "commit.h"
@@ -170,6 +171,16 @@ struct merge_options_internal {
 	 */
 	struct rename_info renames;
 
+	/*
+	 * attr_index: hacky minimal index used for renormalization
+	 *
+	 * renormalization code _requires_ an index, though it only needs to
+	 * find a .gitattributes file within the index.  So, when
+	 * renormalization is important, we create a special index with just
+	 * that one file.
+	 */
+	struct index_state attr_index;
+
 	/*
 	 * current_dir_name, toplevel_dir: temporary vars
 	 *
@@ -349,6 +360,9 @@ 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;
 
+	if (opti->attr_index.cache_nr)
+		discard_index(&opti->attr_index);
+
 	/* Free memory used by various renames maps */
 	for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) {
 		struct hashmap_iter iter;
@@ -3272,6 +3286,8 @@ void merge_finalize(struct merge_options *opt,
 {
 	struct merge_options_internal *opti = result->priv;
 
+	if (opt->renormalize)
+		git_attr_set_direction(GIT_ATTR_CHECKIN);
 	assert(opt->priv == NULL);
 
 	clear_or_reinit_internal_opts(opti, 0);
@@ -3347,6 +3363,10 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)
 	/* Default to histogram diff.  Actually, just hardcode it...for now. */
 	opt->xdl_opts = DIFF_WITH_ALG(opt, HISTOGRAM_DIFF);
 
+	/* Handle attr direction stuff for renormalization */
+	if (opt->renormalize)
+		git_attr_set_direction(GIT_ATTR_CHECKOUT);
+
 	/* Initialization of opt->priv, our internal merge data */
 	trace2_region_enter("merge", "allocate/init", opt->repo);
 	if (opt->priv) {
-- 
gitgitgadget

[PATCH v2 03/10] merge-ort: have ll_merge() use a special attr_index for renormalization

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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 <newren@gmail.com>
---
 merge-ort.c | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 62 insertions(+), 2 deletions(-)

diff --git a/merge-ort.c b/merge-ort.c
index d91b66a052b6..ea720eb51971 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -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;
 
-	if (opti->attr_index.cache_nr)
+	if (opti->attr_index.cache_nr) /* true iff opt->renormalize */
 		discard_index(&opti->attr_index);
 
 	/* Free memory used by various renames maps */
@@ -988,6 +988,63 @@ static int merge_submodule(struct merge_options *opt,
 	return 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.
+	 */
+	struct merged_info *mi;
+	struct index_state *attr_index = &opt->priv->attr_index;
+	struct cache_entry *ce;
+
+	attr_index->initialized = 1;
+
+	if (!opt->renormalize)
+		return;
+
+	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);
+		ce->ce_mode = create_ce_mode(mi->result.mode);
+		ce->ce_flags = create_ce_flags(0);
+		ce->ce_namelen = len;
+		oidcpy(&ce->oid, &mi->result.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);
+	} else {
+		int stage, len;
+		struct conflict_info *ci;
+
+		ASSIGN_AND_VERIFY_CI(ci, mi);
+		for (stage = 0; stage < 3; stage++) {
+			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);
+		}
+	}
+}
+
 static int merge_3way(struct merge_options *opt,
 		      const char *path,
 		      const struct object_id *o,
@@ -1002,6 +1059,9 @@ static int merge_3way(struct merge_options *opt,
 	char *base, *name1, *name2;
 	int merge_status;
 
+	if (!opt->priv->attr_index.initialized)
+		initialize_attr_index(opt);
+
 	ll_opts.renormalize = opt->renormalize;
 	ll_opts.extra_marker_size = extra_marker_size;
 	ll_opts.xdl_opts = opt->xdl_opts;
@@ -1040,7 +1100,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);
-- 
gitgitgadget

[PATCH v2 04/10] merge-ort: let renormalization change modify/delete into clean delete

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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 <newren@gmail.com>
---
 merge-ort.c | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 62 insertions(+), 2 deletions(-)

diff --git a/merge-ort.c b/merge-ort.c
index ea720eb51971..db46f496cb82 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2414,6 +2414,61 @@ 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)
+{
+	void *buf;
+	enum object_type type;
+	unsigned long size;
+	buf = read_object_file(oid, &type, &size);
+	if (!buf)
+		return err(opt, _("cannot read object %s"), oid_to_hex(oid));
+	if (type != OBJ_BLOB) {
+		free(buf);
+		return err(opt, _("object %s is not a blob"), oid_to_hex(oid));
+	}
+	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;
+
+	if (!idx->initialized)
+		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 {
 	/*
 	 * versions: list of (basename -> version_info)
@@ -3001,8 +3056,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;
 
-		if (ci->path_conflict &&
-		    oideq(&ci->stages[0].oid, &ci->stages[side].oid)) {
+		if (opt->renormalize &&
+		    blob_unchanged(opt, &ci->stages[0], &ci->stages[side],
+				   path)) {
+			ci->merged.is_null = 1;
+			ci->merged.clean = 1;
+		} else if (ci->path_conflict &&
+			   oideq(&ci->stages[0].oid, &ci->stages[side].oid)) {
 			/*
 			 * This came from a rename/delete; no action to take,
 			 * but avoid printing "modify/delete" conflict notice
-- 
gitgitgadget

[PATCH v2 05/10] merge-ort: support subtree shifting

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

merge-recursive has some simple code to support subtree shifting; copy
it over to merge-ort.  This fixes t6409.12 under
GIT_TEST_MERGE_ALGORITHM=ort.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-ort.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

diff --git a/merge-ort.c b/merge-ort.c
index db46f496cb82..cfd956a3f435 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -3416,6 +3416,23 @@ void merge_finalize(struct merge_options *opt,
 
 /*** Function Grouping: helper functions for merge_incore_*() ***/
 
+static struct tree *shift_tree_object(struct repository *repo,
+				      struct tree *one, struct tree *two,
+				      const char *subtree_shift)
+{
+	struct object_id shifted;
+
+	if (!*subtree_shift) {
+		shift_tree(repo, &one->object.oid, &two->object.oid, &shifted, 0);
+	} else {
+		shift_tree_by(repo, &one->object.oid, &two->object.oid, &shifted,
+			      subtree_shift);
+	}
+	if (oideq(&two->object.oid, &shifted))
+		return two;
+	return lookup_tree(repo, &shifted);
+}
+
 static inline void set_commit_tree(struct commit *c, struct tree *t)
 {
 	c->maybe_tree = t;
@@ -3543,6 +3560,13 @@ static void merge_ort_nonrecursive_internal(struct merge_options *opt,
 {
 	struct object_id working_tree_oid;
 
+	if (opt->subtree_shift) {
+		side2 = shift_tree_object(opt->repo, side1, side2,
+					  opt->subtree_shift);
+		merge_base = shift_tree_object(opt->repo, side1, merge_base,
+					       opt->subtree_shift);
+	}
+
 	trace2_region_enter("merge", "collect_merge_info", opt->repo);
 	if (collect_merge_info(opt, merge_base, side1, side2) != 0) {
 		/*
-- 
gitgitgadget

[PATCH v2 06/10] t6428: new test for SKIP_WORKTREE handling and conflicts

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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 <newren@gmail.com>
---
 t/t6428-merge-conflicts-sparse.sh | 158 ++++++++++++++++++++++++++++++
 1 file changed, 158 insertions(+)
 create mode 100755 t/t6428-merge-conflicts-sparse.sh

diff --git a/t/t6428-merge-conflicts-sparse.sh b/t/t6428-merge-conflicts-sparse.sh
new file mode 100755
index 000000000000..1bb52ff6f38c
--- /dev/null
+++ b/t/t6428-merge-conflicts-sparse.sh
@@ -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'
+
+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" &&
+
+		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
+		=======
+		IV
+		>>>>>>> B^0
+		EOF
+
+	)
+}
+
+test_expect_merge_algorithm success failure 'conflicting entries written to worktree even if sparse' '
+	test_setup_numerals plain &&
+	(
+		cd numerals_plain &&
+
+		git checkout A^0 &&
+
+		test_path_is_file README &&
+		test_path_is_file numerals &&
+
+		git sparse-checkout init &&
+		git sparse-checkout set README &&
+
+		test_path_is_file README &&
+		test_path_is_missing numerals &&
+
+		test_must_fail git merge -s recursive B^0 &&
+
+		git ls-files -t >index_files &&
+		test_cmp expected-index index_files &&
+
+		test_path_is_file README &&
+		test_path_is_file numerals &&
+
+		test_cmp expected-merge numerals &&
+
+		# 4 other files:
+		#   * expected-merge
+		#   * expected-index
+		#   * index_files
+		#   * others
+		git ls-files -o >others &&
+		test_line_count = 4 others
+	)
+'
+
+test_expect_merge_algorithm failure failure 'present-despite-SKIP_WORKTREE handled reasonably' '
+	test_setup_numerals in_the_way &&
+	(
+		cd numerals_in_the_way &&
+
+		git checkout A^0 &&
+
+		test_path_is_file README &&
+		test_path_is_file numerals &&
+
+		git sparse-checkout init &&
+		git sparse-checkout set README &&
+
+		test_path_is_file README &&
+		test_path_is_missing numerals &&
+
+		echo foobar >numerals &&
+
+		test_must_fail git merge -s recursive B^0 &&
+
+		git ls-files -t >index_files &&
+		test_cmp expected-index index_files &&
+
+		test_path_is_file README &&
+		test_path_is_file numerals &&
+
+		test_cmp expected-merge numerals &&
+
+		# There should still be a file with "foobar" in it
+		grep foobar * &&
+
+		# 5 other files:
+		#   * expected-merge
+		#   * expected-index
+		#   * index_files
+		#   * others
+		#   * whatever name was given to the numerals file that had
+		#     "foobar" in it
+		git ls-files -o >others &&
+		test_line_count = 5 others
+	)
+'
+
+test_done
-- 
gitgitgadget

[PATCH v2 07/10] merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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 <newren@gmail.com>
---
 merge-ort.c                       | 43 +++++++++++++++++++++----------
 t/t6428-merge-conflicts-sparse.sh |  4 +--
 2 files changed, 32 insertions(+), 15 deletions(-)

diff --git a/merge-ort.c b/merge-ort.c
index cfd956a3f435..040287e3a998 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -3234,23 +3234,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;
@@ -3291,9 +3295,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)) {
+				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);
+					errs |= rename(path, new_name);
+					free(new_name);
+				}
+				errs |= checkout_entry(ce, &state, NULL, NULL);
+			}
 
 			/*
 			 * Mark this cache entry for removal and instead add
@@ -3343,8 +3361,6 @@ void merge_switch_to_result(struct merge_options *opt,
 {
 	assert(opt->priv == NULL);
 	if (result->clean >= 0 && update_worktree_and_index) {
-		struct merge_options_internal *opti = result->priv;
-
 		trace2_region_enter("merge", "checkout", opt->repo);
 		if (checkout(opt, head, result->tree)) {
 			/* failure to function */
@@ -3354,13 +3370,14 @@ void merge_switch_to_result(struct merge_options *opt,
 		trace2_region_leave("merge", "checkout", opt->repo);
 
 		trace2_region_enter("merge", "record_conflicted", opt->repo);
-		if (record_conflicted_index_entries(opt, opt->repo->index,
-						    &opti->paths,
-						    &opti->conflicted)) {
+		opt->priv = result->priv;
+		if (record_conflicted_index_entries(opt)) {
 			/* failure to function */
+			opt->priv = NULL;
 			result->clean = -1;
 			return;
 		}
+		opt->priv = NULL;
 		trace2_region_leave("merge", "record_conflicted", opt->repo);
 	}
 
diff --git a/t/t6428-merge-conflicts-sparse.sh b/t/t6428-merge-conflicts-sparse.sh
index 1bb52ff6f38c..7e8bf497f821 100755
--- a/t/t6428-merge-conflicts-sparse.sh
+++ b/t/t6428-merge-conflicts-sparse.sh
@@ -76,7 +76,7 @@ test_setup_numerals () {
 	)
 }
 
-test_expect_merge_algorithm success failure 'conflicting entries written to worktree even if sparse' '
+test_expect_success 'conflicting entries written to worktree even if sparse' '
 	test_setup_numerals plain &&
 	(
 		cd numerals_plain &&
@@ -112,7 +112,7 @@ test_expect_merge_algorithm success failure 'conflicting entries written to work
 	)
 '
 
-test_expect_merge_algorithm failure failure 'present-despite-SKIP_WORKTREE handled reasonably' '
+test_expect_merge_algorithm failure success 'present-despite-SKIP_WORKTREE handled reasonably' '
 	test_setup_numerals in_the_way &&
 	(
 		cd numerals_in_the_way &&
-- 
gitgitgadget

[PATCH v2 08/10] t: mark several submodule merging tests as fixed under merge-ort

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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 <newren@gmail.com>
---
 t/t3512-cherry-pick-submodule.sh              | 7 +++++--
 t/t3513-revert-submodule.sh                   | 5 ++++-
 t/t5572-pull-submodule.sh                     | 7 +++++--
 t/t6437-submodule-merge.sh                    | 5 +++--
 t/t6438-submodule-directory-file-conflicts.sh | 7 +++++--
 5 files changed, 22 insertions(+), 9 deletions(-)

diff --git a/t/t3512-cherry-pick-submodule.sh b/t/t3512-cherry-pick-submodule.sh
index 822f2d4bfbd5..c657840db33b 100755
--- a/t/t3512-cherry-pick-submodule.sh
+++ b/t/t3512-cherry-pick-submodule.sh
@@ -8,8 +8,11 @@ export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME
 . ./test-lib.sh
 . "$TEST_DIRECTORY"/lib-submodule-update.sh
 
-KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
-KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
+if test "$GIT_TEST_MERGE_ALGORITHM" != ort
+then
+	KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
+	KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
+fi
 test_submodule_switch "cherry-pick"
 
 test_expect_success 'unrelated submodule/file conflict is ignored' '
diff --git a/t/t3513-revert-submodule.sh b/t/t3513-revert-submodule.sh
index a759f12cbb1d..74cd96e58223 100755
--- a/t/t3513-revert-submodule.sh
+++ b/t/t3513-revert-submodule.sh
@@ -30,7 +30,10 @@ git_revert () {
 	git revert HEAD
 }
 
-KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
+if test "$GIT_TEST_MERGE_ALGORITHM" != ort
+then
+	KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
+fi
 test_submodule_switch_func "git_revert"
 
 test_done
diff --git a/t/t5572-pull-submodule.sh b/t/t5572-pull-submodule.sh
index 29537f4798ef..4f92a116e1f0 100755
--- a/t/t5572-pull-submodule.sh
+++ b/t/t5572-pull-submodule.sh
@@ -42,8 +42,11 @@ git_pull_noff () {
 	$2 git pull --no-ff
 }
 
-KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
-KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
+if test "$GIT_TEST_MERGE_ALGORITHM" != ort
+then
+	KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
+	KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
+fi
 test_submodule_switch_func "git_pull_noff"
 
 test_expect_success 'pull --recurse-submodule setup' '
diff --git a/t/t6437-submodule-merge.sh b/t/t6437-submodule-merge.sh
index 0f92bcf326c8..e5e89c2045e7 100755
--- a/t/t6437-submodule-merge.sh
+++ b/t/t6437-submodule-merge.sh
@@ -6,6 +6,7 @@ GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main
 export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME
 
 . ./test-lib.sh
+. "$TEST_DIRECTORY"/lib-merge.sh
 
 #
 # history
@@ -328,7 +329,7 @@ test_expect_success 'setup file/submodule conflict' '
 	)
 '
 
-test_expect_failure 'file/submodule conflict' '
+test_expect_merge_algorithm failure success 'file/submodule conflict' '
 	test_when_finished "git -C file-submodule reset --hard" &&
 	(
 		cd file-submodule &&
@@ -437,7 +438,7 @@ test_expect_failure 'directory/submodule conflict; keep submodule clean' '
 	)
 '
 
-test_expect_failure !FAIL_PREREQS 'directory/submodule conflict; should not treat submodule files as untracked or in the way' '
+test_expect_merge_algorithm failure success !FAIL_PREREQS 'directory/submodule conflict; should not treat submodule files as untracked or in the way' '
 	test_when_finished "git -C directory-submodule/path reset --hard" &&
 	test_when_finished "git -C directory-submodule reset --hard" &&
 	(
diff --git a/t/t6438-submodule-directory-file-conflicts.sh b/t/t6438-submodule-directory-file-conflicts.sh
index 04bf4be7d792..8df67a0ef99d 100755
--- a/t/t6438-submodule-directory-file-conflicts.sh
+++ b/t/t6438-submodule-directory-file-conflicts.sh
@@ -12,8 +12,11 @@ test_submodule_switch "merge --ff"
 
 test_submodule_switch "merge --ff-only"
 
-KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
-KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
+if test "$GIT_TEST_MERGE_ALGORITHM" != ort
+then
+	KNOWN_FAILURE_NOFF_MERGE_DOESNT_CREATE_EMPTY_SUBMODULE_DIR=1
+	KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
+fi
 test_submodule_switch "merge --no-ff"
 
 test_done
-- 
gitgitgadget

[PATCH v2 09/10] merge-ort: write $GIT_DIR/AUTO_MERGE whenever we hit a conflict

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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 <newren@gmail.com>
---
 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(+)

diff --git a/branch.c b/branch.c
index 9c9dae1eae32..b71a2de29dbe 100644
--- a/branch.c
+++ b/branch.c
@@ -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));
 }
 
diff --git a/builtin/rebase.c b/builtin/rebase.c
index de400f9a1973..7d9afe118fd4 100644
--- a/builtin/rebase.c
+++ b/builtin/rebase.c
@@ -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);
 	/*
diff --git a/merge-ort.c b/merge-ort.c
index 040287e3a998..1a07e39d2db4 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -3361,6 +3361,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 */
@@ -3379,6 +3382,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);
+		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);
 	}
 
 	if (display_update_msgs) {
diff --git a/path.c b/path.c
index 7b385e5eb282..9e883eb52446 100644
--- a/path.c
+++ b/path.c
@@ -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")
diff --git a/path.h b/path.h
index e7e77da6aaa5..251c78d98000 100644
--- a/path.h
+++ b/path.h
@@ -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);
 
diff --git a/sequencer.c b/sequencer.c
index d2332d3e1787..472cdd8c620d 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -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));
 		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());
-- 
gitgitgadget

[PATCH v2 10/10] merge-recursive: add a bunch of FIXME comments documenting known bugs

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-recursive.c | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)

diff --git a/merge-recursive.c b/merge-recursive.c
index b052974f191c..99a197597db5 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1075,6 +1075,11 @@ static int merge_3way(struct merge_options *opt,
 	read_mmblob(&src1, &a->oid);
 	read_mmblob(&src2, &b->oid);
 
+	/*
+	 * FIXME: Using a->path for normalization rules in ll_merge could be
+	 * wrong if we renamed from a->path to b->path.  We should use the
+	 * target path for where the file will be written.
+	 */
 	merge_status = ll_merge(result_buf, a->path, &orig, base,
 				&src1, name1, &src2, name2,
 				opt->repo->index, &ll_opts);
@@ -1154,6 +1159,8 @@ static void print_commit(struct commit *commit)
 	struct strbuf sb = STRBUF_INIT;
 	struct pretty_print_context ctx = {0};
 	ctx.date_mode.type = DATE_NORMAL;
+	/* FIXME: Merge this with output_commit_title() */
+	assert(!merge_remote_util(commit));
 	format_commit_message(commit, " %h: %m %s", &sb, &ctx);
 	fprintf(stderr, "%s\n", sb.buf);
 	strbuf_release(&sb);
@@ -1177,6 +1184,11 @@ static int merge_submodule(struct merge_options *opt,
 	int search = !opt->priv->call_depth;
 
 	/* store a in result in case we fail */
+	/* FIXME: This is the WRONG resolution for the recursive case when
+	 * we need to be careful to avoid accidentally matching either side.
+	 * Should probably use o instead there, much like we do for merging
+	 * binaries.
+	 */
 	oidcpy(result, a);
 
 	/* we can not handle deletion conflicts */
@@ -1301,6 +1313,13 @@ static int merge_mode_and_contents(struct merge_options *opt,
 
 	if ((S_IFMT & a->mode) != (S_IFMT & b->mode)) {
 		result->clean = 0;
+		/*
+		 * FIXME: This is a bad resolution for recursive case; for
+		 * the recursive case we want something that is unlikely to
+		 * accidentally match either side.  Also, while it makes
+		 * sense to prefer regular files over symlinks, it doesn't
+		 * make sense to prefer regular files over submodules.
+		 */
 		if (S_ISREG(a->mode)) {
 			result->blob.mode = a->mode;
 			oidcpy(&result->blob.oid, &a->oid);
@@ -1349,6 +1368,7 @@ static int merge_mode_and_contents(struct merge_options *opt,
 			free(result_buf.ptr);
 			if (ret)
 				return ret;
+			/* FIXME: bug, what if modes didn't match? */
 			result->clean = (merge_status == 0);
 		} else if (S_ISGITLINK(a->mode)) {
 			result->clean = merge_submodule(opt, &result->blob.oid,
@@ -2664,6 +2684,14 @@ static int process_renames(struct merge_options *opt,
 	struct string_list b_by_dst = STRING_LIST_INIT_NODUP;
 	const struct rename *sre;
 
+	/*
+	 * FIXME: As string-list.h notes, it's O(n^2) to build a sorted
+	 * string_list one-by-one, but O(n log n) to build it unsorted and
+	 * then sort it.  Note that as we build the list, we do not need to
+	 * check if the existing destination path is already in the list,
+	 * because the structure of diffcore_rename guarantees we won't
+	 * have duplicates.
+	 */
 	for (i = 0; i < a_renames->nr; i++) {
 		sre = a_renames->items[i].util;
 		string_list_insert(&a_by_dst, sre->pair->two->path)->util
@@ -3602,6 +3630,15 @@ static int merge_recursive_internal(struct merge_options *opt,
 			return err(opt, _("merge returned no commit"));
 	}
 
+	/*
+	 * FIXME: Since merge_recursive_internal() is only ever called by
+	 * places that ensure the index is loaded first
+	 * (e.g. builtin/merge.c, rebase/sequencer, etc.), in the common
+	 * case where the merge base was unique that means when we get here
+	 * we immediately discard the index and re-read it, which is a
+	 * complete waste of time.  We should only be discarding and
+	 * re-reading if we were forced to recurse.
+	 */
 	discard_index(opt->repo->index);
 	if (!opt->priv->call_depth)
 		repo_read_index(opt->repo);
-- 
gitgitgadget

Re: [PATCH v2 02/10] merge-ort: add a special minimal index just for renormalization

[Derrick Stolee]

On 3/9/2021 1:24 AM, Elijah Newren via GitGitGadget wrote:
> From: Elijah Newren <newren@gmail.com>
> 
> 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.

Is this the best way to solve this problem? Shouldn't we extract the
logic that interacts with the .gitattributes file from
renormalize_buffer() (say, to renormalize_buffer_attributes()) and
just pass the .gitattributes file instead of creating a fake index?

It probably moves more code to do it the way I recommend, but it
helps to separate the concerns a bit better. Of course, I haven't
tried doing it myself, so maybe it's harder than I think.
 
Thanks,
-Stolee

Re: [PATCH v2 03/10] merge-ort: have ll_merge() use a special attr_index for renormalization

[Derrick Stolee]

On 3/9/2021 1:24 AM, Elijah Newren via GitGitGadget wrote:
> From: Elijah Newren <newren@gmail.com>
> 
> 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.

I have similar concerns here. This strategy of creating an index with
only one entry is adding some deep coupling between the ORT code and
these normalization methods. It would be a better pattern to extract
the logic that normalizes based on some attributes file without caring
where it came from.

Thanks,
-Stolee

Re: [PATCH v2 06/10] t6428: new test for SKIP_WORKTREE handling and conflicts

[Derrick Stolee]

On 3/9/2021 1:24 AM, Elijah Newren via GitGitGadget wrote:
> From: Elijah Newren <newren@gmail.com>
> 
> 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.

Thank you for this test!
 
-Stolee

Re: [PATCH v2 08/10] t: mark several submodule merging tests as fixed under merge-ort

[Derrick Stolee]

On 3/9/2021 1:24 AM, Elijah Newren via GitGitGadget wrote:
> From: Elijah Newren <newren@gmail.com>
> 
> 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.

Nice!
-Stolee

Re: [PATCH v2 00/10] Complete merge-ort implementation...almost

[Derrick Stolee]

On 3/9/2021 1:24 AM, Elijah Newren via GitGitGadget wrote:
> 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.

Thanks,
-Stolee

Re: [PATCH v2 00/10] Complete merge-ort implementation...almost

[Elijah Newren]

On Thu, Mar 11, 2021 at 7:20 AM Derrick Stolee <stolee@gmail.com> wrote:
>
> On 3/9/2021 1:24 AM, Elijah Newren via GitGitGadget wrote:
> > 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.

Oh, I agree, I hate the "index with one entry" mechanism to activate
the renormalization code.  It feels like a capitulation on merge-ort's
design and is such a hack.  I tried to figure out how to do it a
different way, and failed pretty hard.  I was close to the point of
throwing my hands in the air and leaving the renormalization tests
failing ("who uses that stuff anyway?"), but it was the _only_ test
that merge-recursive passed that merge-ort didn't, so I kept trying
anyway.  At some point I realized that a hack along these lines might
work.  Although, to be honest, I still don't understand this code or
why my patches work -- in particular, the get_stream_filter() call has
me flummoxed.  It returns a value, but I throw it away -- yet the code
fails unless I call it.  What is it actually doing?  Clearly it has
some kind of side-effect somewhere, but reading the code didn't seem
to help me.  I discovered the function and others via various
debugging and trial-and-error attempts, and ended up finding out that
just calling that function is enough.  I know it works, but I don't
know why.  I understand everything else in merge-ort; I hate having a
magic corner here.  I'm not happy with it.

I'm certain that with enough effort the renormalization stuff could be
fixed and made callable without an istate.  Perhaps there's even a
simple way to extract the relevant logic and I'm just being dense, but
I got very lost in that code and I'm a bit afraid of it now.

Re: [PATCH v2 00/10] Complete merge-ort implementation...almost

[Elijah Newren]

On Mon, Mar 8, 2021 at 10:24 PM Elijah Newren via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> This series (nearly) completes the merge-ort implementation, cleaning up
> testsuite failures. The exceptions are some t6423 failures being addressed
> independently[1].

This series was subsumed into
https://lore.kernel.org/git/pull.905.v2.git.1616016485.gitgitgadget@gmail.com/.
So, ignore this topic and look for the changes over there.

(Reasons for the curious: This series had fixed t6409 and t6418 and
the submodule TODO passes, while the other series fixed t6423.  The
other series could not have been included when this was submitted
because it depended on the not-yet-submitted ort-perf-batch-10.  Why
not just wait?  Well Ævar wanted a way to test his changes against
merge-ort, this early submission provided that and helped him find a
bug -- see https://lore.kernel.org/git/20210308150650.18626-1-avarab@gmail.com/.
Now that we can fix all the tests, I'm withdrawing this one and
including it with the other fixes.)