[PATCH 0/2] Declare merge-ort ready for general usage

[PATCH 0/2] Declare merge-ort ready for general usage

[Elijah Newren via GitGitGadget]

This tiny series depends on ort-perf-batch-10[1].

If the ort-remainder topic[2] is merged with this series, then the result is
a version of merge-ort ready for general usage. Users can select it by (a)
passing -sort to either git merge or git rebase, or (b) by setting
pull.twohead=ort [3], or (c) by setting GIT_TEST_MERGE_ALGORITHM=ort.

There are still more optimizations that will be submitted for merge-ort, but
folks don't need to wait for all of them to start using it. The version of
merge-ort that comes from merging both these topics will run the testsuite
cleanly under GIT_MERGE_TEST_ALGORITHM=ort, which includes passing every
test that merge-recursive does and passing dozens of tests that
merge-recursive doesn't. merge-ort is also already significantly faster than
merge-recursive when rename detection is involved.

I'll send out a separate email later requesting feedback about what people
would like to see before switching the default from merge-recursive to
merge-ort.

[1]
https://lore.kernel.org/git/pull.853.git.1615674128.gitgitgadget@gmail.com/
[2]
https://lore.kernel.org/git/pull.973.v2.git.git.1615271086.gitgitgadget@gmail.com/
[3] See commit 14c4586c2d ("merge,rebase,revert: select ort or recursive by
config or environment", 2020-11-02)

Elijah Newren (2):
  Revert "merge-ort: ignore the directory rename split conflict for now"
  t6423: mark remaining expected failure under merge-ort as such

 merge-ort.c                         | 13 +------------
 t/t6423-merge-rename-directories.sh |  2 +-
 2 files changed, 2 insertions(+), 13 deletions(-)


base-commit: ac0ba91ce275227f5df8f16fb986308ff88b198b
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-905%2Fgitgitgadget%2Fort-readiness-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-905/gitgitgadget/ort-readiness-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/905
-- 
gitgitgadget

[PATCH 1/2] Revert "merge-ort: ignore the directory rename split conflict for now"

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

This reverts commit 5ced7c3da009090c5a926e3123a71314c7f28d42, which was
put in place as a temporary measure to avoid optimizations unstably
erroring out on no destination having a majority of the necessary
renames for directories that had no new files and thus no need for
directory rename detection anyway.  Now that optimizations are in place
to prevent us from trying to compute directory rename count computations
for directories that do not need it, we can undo this temporary measure.

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

diff --git a/merge-ort.c b/merge-ort.c
index 7f5750ce6ab0..60270feadc54 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -1562,18 +1562,7 @@ static void get_provisional_directory_renames(struct merge_options *opt,
 				 "no destination getting a majority of the "
 				 "files."),
 			       source_dir);
-			/*
-			 * We should mark this as unclean IF something attempts
-			 * to use this rename.  We do not yet have the logic
-			 * in place to detect if this directory rename is being
-			 * used, and optimizations that reduce the number of
-			 * renames cause this to falsely trigger.  For now,
-			 * just disable it, causing t6423 testcase 2a to break.
-			 * We'll later fix the detection, and when we do we
-			 * will re-enable setting *clean to 0 (and thereby fix
-			 * t6423 testcase 2a).
-			 */
-			/*   *clean = 0;   */
+			*clean = 0;
 		} else {
 			strmap_put(&renames->dir_renames[side],
 				   source_dir, (void*)best);
-- 
gitgitgadget

[PATCH 2/2] t6423: mark remaining expected failure under merge-ort as such

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

When we started on merge-ort, thousands of tests failed when run with
the GIT_TEST_MERGE_ALGORITHM=ort flag; with so many, it didn't make
sense to flip all their test expectations.  The ones in t6409, t6418,
and the submodule tests are being handled by an independent in-flight
topic ("Complete merge-ort implemenation...almost").  The ones in
t6423 were left out of the other series because other ongoing series
that this commit depends upon were addressing those.  Now that we only
have one remaining test failure in t6423, let's mark it as such.

This remaining test will be fixed by a future optimization series, but
since merge-recursive doesn't pass this test either, passing it is not
necessary for declaring merge-ort ready for general use.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 t/t6423-merge-rename-directories.sh | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

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

Re: [PATCH 0/2] Declare merge-ort ready for general usage

[Derrick Stolee]

On 3/16/2021 12:05 AM, Elijah Newren via GitGitGadget wrote:
> This tiny series depends on ort-perf-batch-10[1].
> 
> If the ort-remainder topic[2] is merged with this series, then the result is
> a version of merge-ort ready for general usage. Users can select it by (a)
> passing -sort to either git merge or git rebase, or (b) by setting
> pull.twohead=ort [3], or (c) by setting GIT_TEST_MERGE_ALGORITHM=ort.

Does the other topic add GIT_TEST_MERGE_ALGORITHM=ort to the CI builds?

Specifically, the Linux builds have a second run with some optional
GIT_TEST_* environment variables. This seems like a nice addition.
 Other than that extra request, this series was easy to review. LGTM.
-Stolee

Re: [PATCH 0/2] Declare merge-ort ready for general usage

[Elijah Newren]

On Tue, Mar 16, 2021 at 10:01 AM Derrick Stolee <stolee@gmail.com> wrote:
>
> On 3/16/2021 12:05 AM, Elijah Newren via GitGitGadget wrote:
> > This tiny series depends on ort-perf-batch-10[1].
> >
> > If the ort-remainder topic[2] is merged with this series, then the result is
> > a version of merge-ort ready for general usage. Users can select it by (a)
> > passing -sort to either git merge or git rebase, or (b) by setting
> > pull.twohead=ort [3], or (c) by setting GIT_TEST_MERGE_ALGORITHM=ort.
>
> Does the other topic add GIT_TEST_MERGE_ALGORITHM=ort to the CI builds?
>
> Specifically, the Linux builds have a second run with some optional
> GIT_TEST_* environment variables. This seems like a nice addition.
>  Other than that extra request, this series was easy to review. LGTM.

The other topic left tests in t6423 failing.  This topic leaves the
tests in t6409 and t6418 failing; it's only the merge of the two that
has all passing tests.

I guess since the ort-remainder topic still hasn't been picked up, I
could just combine it with this series (basing on ort-perf-batch-10).
Then I could either add a patch at the end of the series that runs
tests under GIT_TEST_MERGE_ALGORITHM=ort, or which changes the default
merge backend to ort.

Re: [PATCH 0/2] Declare merge-ort ready for general usage

[Derrick Stolee]

On 3/16/2021 1:25 PM, Elijah Newren wrote:
> On Tue, Mar 16, 2021 at 10:01 AM Derrick Stolee <stolee@gmail.com> wrote:
>>
>> On 3/16/2021 12:05 AM, Elijah Newren via GitGitGadget wrote:
>>> This tiny series depends on ort-perf-batch-10[1].
>>>
>>> If the ort-remainder topic[2] is merged with this series, then the result is
>>> a version of merge-ort ready for general usage. Users can select it by (a)
>>> passing -sort to either git merge or git rebase, or (b) by setting
>>> pull.twohead=ort [3], or (c) by setting GIT_TEST_MERGE_ALGORITHM=ort.
>>
>> Does the other topic add GIT_TEST_MERGE_ALGORITHM=ort to the CI builds?
>>
>> Specifically, the Linux builds have a second run with some optional
>> GIT_TEST_* environment variables. This seems like a nice addition.
>>  Other than that extra request, this series was easy to review. LGTM.
> 
> The other topic left tests in t6423 failing.  This topic leaves the
> tests in t6409 and t6418 failing; it's only the merge of the two that
> has all passing tests.

Combining the series might be the right call, or say this one depends
on that one.
 
> I guess since the ort-remainder topic still hasn't been picked up, I
> could just combine it with this series (basing on ort-perf-batch-10).
> Then I could either add a patch at the end of the series that runs
> tests under GIT_TEST_MERGE_ALGORITHM=ort, or which changes the default
> merge backend to ort. 

Perhaps change the backend to "ort" only when "features.experimental"
is enabled, at least for one full release? I'll do my part to do some
testing with our repos in that time, too.

Thanks,
-Stolee

[PATCH v2 00/13] Declare merge-ort ready for general usage

[Elijah Newren via GitGitGadget]

This series depends on ort-perf-batch-10[1], and obsoletes the ort-remainder
topic[2] (that hadn't been picked up yet, so hopefully this doesn't cause
any confusion)

With this series, merge-ort is ready for general usage -- it passes all
tests, passes dozens of tests that don't under merge-recursive, and
merge-ort is is already significantly faster than merge-recursive when
rename detection is involved. Users can select merge-ort by (a) passing
-sort to either git merge or git rebase, or (b) by setting pull.twohead=ort
[3], or (c) by setting GIT_TEST_MERGE_ALGORITHM=ort.

Changes since v1:

 * subsumed the ort-remainder topic (the first 10 patches), which has
   already been reviewed by both Ævar and Stolee[2].
 * the next two patches were the original v1, reviewed by Stolee
 * the final patch is new and adds testing.

[1]
https://lore.kernel.org/git/pull.853.git.1615674128.gitgitgadget@gmail.com/
[2]
https://lore.kernel.org/git/pull.973.v2.git.git.1615271086.gitgitgadget@gmail.com/
[3] See commit 14c4586c2d ("merge,rebase,revert: select ort or recursive by
config or environment", 2020-11-02)

Elijah Newren (13):
  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
  Revert "merge-ort: ignore the directory rename split conflict for now"
  t6423: mark remaining expected failure under merge-ort as such
  Add testing with merge-ort merge strategy

 .github/workflows/main.yml                    |   1 +
 branch.c                                      |   1 +
 builtin/rebase.c                              |   1 +
 ci/lib.sh                                     |   6 +
 merge-ort.c                                   | 242 ++++++++++++++++--
 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/t6423-merge-rename-directories.sh           |   2 +-
 t/t6428-merge-conflicts-sparse.sh             | 158 ++++++++++++
 t/t6437-submodule-merge.sh                    |   5 +-
 t/t6438-submodule-directory-file-conflicts.sh |   7 +-
 16 files changed, 449 insertions(+), 38 deletions(-)
 create mode 100755 t/t6428-merge-conflicts-sparse.sh


base-commit: ac0ba91ce275227f5df8f16fb986308ff88b198b
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-905%2Fgitgitgadget%2Fort-readiness-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-905/gitgitgadget/ort-readiness-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/905

Range-diff vs v1:

  -:  ------------ >  1:  e223f842748c merge-ort: use STABLE_QSORT instead of QSORT where required
  -:  ------------ >  2:  6d34cc466bd5 merge-ort: add a special minimal index just for renormalization
  -:  ------------ >  3:  4ff23d2f52a0 merge-ort: have ll_merge() use a special attr_index for renormalization
  -:  ------------ >  4:  c1c9605c1932 merge-ort: let renormalization change modify/delete into clean delete
  -:  ------------ >  5:  41fffcdd3b78 merge-ort: support subtree shifting
  -:  ------------ >  6:  6aec1f499b80 t6428: new test for SKIP_WORKTREE handling and conflicts
  -:  ------------ >  7:  fe3baf696785 merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries
  -:  ------------ >  8:  f9325647a9fc t: mark several submodule merging tests as fixed under merge-ort
  -:  ------------ >  9:  4a79e6134691 merge-ort: write $GIT_DIR/AUTO_MERGE whenever we hit a conflict
  -:  ------------ > 10:  a37979454069 merge-recursive: add a bunch of FIXME comments documenting known bugs
  1:  7a8e26638a16 = 11:  6bda855f2980 Revert "merge-ort: ignore the directory rename split conflict for now"
  2:  0d41038fad91 = 12:  1c6361c9b88a t6423: mark remaining expected failure under merge-ort as such
  -:  ------------ > 13:  d8536f56ab29 Add testing with merge-ort merge strategy

-- 
gitgitgadget

[PATCH v2 01/13] 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 7f5750ce6ab0..34a91c435737 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2405,7 +2405,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);
@@ -2550,6 +2550,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 */
@@ -3325,6 +3326,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/13] 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 34a91c435737..3c606fa7e4b3 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"
@@ -220,6 +221,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
 	 *
@@ -399,6 +410,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) {
 		strintmap_func(&renames->dirs_removed[i]);
@@ -3407,6 +3421,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);
@@ -3482,6 +3498,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/13] 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 3c606fa7e4b3..cdc1e2fe7a24 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -410,7 +410,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 */
@@ -1201,6 +1201,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,
@@ -1215,6 +1272,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;
@@ -1253,7 +1313,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/13] 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 cdc1e2fe7a24..c7083e3769aa 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2549,6 +2549,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)
@@ -3136,8 +3191,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/13] 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 c7083e3769aa..c4fe234d8972 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -3551,6 +3551,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;
@@ -3680,6 +3697,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/13] 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/13] 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 c4fe234d8972..303e89414274 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -3369,23 +3369,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;
@@ -3426,9 +3430,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
@@ -3478,8 +3496,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 */
@@ -3489,13 +3505,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/13] 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/13] 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 840dbd7eb777..6c252d62758c 100644
--- a/builtin/rebase.c
+++ b/builtin/rebase.c
@@ -737,6 +737,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 303e89414274..e8f1a435f99a 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -3496,6 +3496,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 */
@@ -3514,6 +3517,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/13] 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

[PATCH v2 11/13] Revert "merge-ort: ignore the directory rename split conflict for now"

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

This reverts commit 5ced7c3da009090c5a926e3123a71314c7f28d42, which was
put in place as a temporary measure to avoid optimizations unstably
erroring out on no destination having a majority of the necessary
renames for directories that had no new files and thus no need for
directory rename detection anyway.  Now that optimizations are in place
to prevent us from trying to compute directory rename count computations
for directories that do not need it, we can undo this temporary measure.

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

diff --git a/merge-ort.c b/merge-ort.c
index e8f1a435f99a..8258d3fd621e 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -1636,18 +1636,7 @@ static void get_provisional_directory_renames(struct merge_options *opt,
 				 "no destination getting a majority of the "
 				 "files."),
 			       source_dir);
-			/*
-			 * We should mark this as unclean IF something attempts
-			 * to use this rename.  We do not yet have the logic
-			 * in place to detect if this directory rename is being
-			 * used, and optimizations that reduce the number of
-			 * renames cause this to falsely trigger.  For now,
-			 * just disable it, causing t6423 testcase 2a to break.
-			 * We'll later fix the detection, and when we do we
-			 * will re-enable setting *clean to 0 (and thereby fix
-			 * t6423 testcase 2a).
-			 */
-			/*   *clean = 0;   */
+			*clean = 0;
 		} else {
 			strmap_put(&renames->dir_renames[side],
 				   source_dir, (void*)best);
-- 
gitgitgadget

[PATCH v2 12/13] t6423: mark remaining expected failure under merge-ort as such

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

When we started on merge-ort, thousands of tests failed when run with
the GIT_TEST_MERGE_ALGORITHM=ort flag; with so many, it didn't make
sense to flip all their test expectations.  The ones in t6409, t6418,
and the submodule tests are being handled by an independent in-flight
topic ("Complete merge-ort implemenation...almost").  The ones in
t6423 were left out of the other series because other ongoing series
that this commit depends upon were addressing those.  Now that we only
have one remaining test failure in t6423, let's mark it as such.

This remaining test will be fixed by a future optimization series, but
since merge-recursive doesn't pass this test either, passing it is not
necessary for declaring merge-ort ready for general use.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 t/t6423-merge-rename-directories.sh | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

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

[PATCH v2 13/13] Add testing with merge-ort merge strategy

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

In preparation for switching from merge-recursive to merge-ort as the
default strategy, ensure that we are testing it.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 .github/workflows/main.yml | 1 +
 ci/lib.sh                  | 6 ++++++
 2 files changed, 7 insertions(+)

diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml
index 5f2f884b92f6..e1f59861a2ca 100644
--- a/.github/workflows/main.yml
+++ b/.github/workflows/main.yml
@@ -252,6 +252,7 @@ jobs:
         MSYSTEM: MINGW64
         NO_SVN_TESTS: 1
         GIT_TEST_SKIP_REBASE_P: 1
+        GIT_TEST_MERGE_ALGORITHM: ort
       run: |
         & .\git-sdk-64-minimal\usr\bin\bash.exe -lc @"
           # Let Git ignore the SDK and the test-cache
diff --git a/ci/lib.sh b/ci/lib.sh
index d848c036c50f..2a869b598c7f 100755
--- a/ci/lib.sh
+++ b/ci/lib.sh
@@ -182,6 +182,12 @@ export DEFAULT_TEST_TARGET=prove
 export GIT_TEST_CLONE_2GB=true
 export SKIP_DASHED_BUILT_INS=YesPlease
 
+case "$jobname" in
+*-gcc)
+	export GIT_TEST_MERGE_ALGORITHM=ort
+	;;
+esac
+
 case "$jobname" in
 linux-clang|linux-gcc)
 	if [ "$jobname" = linux-gcc ]
-- 
gitgitgadget

Re: [PATCH v2 13/13] Add testing with merge-ort merge strategy

[Derrick Stolee]

On 3/17/2021 5:28 PM, Elijah Newren via GitGitGadget wrote:
> From: Elijah Newren <newren@gmail.com>
> 
> In preparation for switching from merge-recursive to merge-ort as the
> default strategy, ensure that we are testing it.

OK, so here we are testing it by default in CI, not just in that
second round of optional environment variables. If that is what
you intended, then this is the diff I was expecting:

diff --git a/ci/run-build-and-tests.sh b/ci/run-build-and-tests.sh
index a66b5e8c75a..c013e9e646a 100755
--- a/ci/run-build-and-tests.sh
+++ b/ci/run-build-and-tests.sh
@@ -25,6 +25,7 @@ linux-gcc)
 	export GIT_TEST_ADD_I_USE_BUILTIN=1
 	export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=master
 	export GIT_TEST_WRITE_REV_INDEX=1
+	export GIT_TEST_MERGE_STRATEGY=org
 	make test
 	;;
 linux-clang)

However, if we want to be aggressive in adopting the ort strategy
very soon, then your approach of testing more frequently is
valuable.

Would it be worth setting GIT_TEST_MERGE_ALGORITHM=ort by default
in test-lib.sh, too? That could help developers working on top of
your topic avoid creating test failures that only show up in CI.

Thanks,
-Stolee

Re: [PATCH v2 00/13] Declare merge-ort ready for general usage

[Derrick Stolee]

On 3/17/2021 5:27 PM, Elijah Newren via GitGitGadget wrote:
> This series depends on ort-perf-batch-10[1], and obsoletes the ort-remainder
> topic[2] (that hadn't been picked up yet, so hopefully this doesn't cause
> any confusion)
> 
> With this series, merge-ort is ready for general usage -- it passes all
> tests, passes dozens of tests that don't under merge-recursive, and
> merge-ort is is already significantly faster than merge-recursive when
> rename detection is involved. Users can select merge-ort by (a) passing
> -sort to either git merge or git rebase, or (b) by setting pull.twohead=ort
> [3], or (c) by setting GIT_TEST_MERGE_ALGORITHM=ort.
> 
> Changes since v1:
> 
>  * subsumed the ort-remainder topic (the first 10 patches), which has
>    already been reviewed by both Ævar and Stolee[2].
>  * the next two patches were the original v1, reviewed by Stolee
>  * the final patch is new and adds testing.

Sorry for the delay in looking at this. I read the two series before
this, and found this to be a good union of them.

My only question on the final patch is a two parter:

1. Did you mean to go this far?
2. Did you want to go farther?

Mostly: how much do we want to prepare for ORT as the default
strategy, at the expense of reducing testing of the recursive
strategy?

Thanks,
-Stolee

Re: [PATCH v2 13/13] Add testing with merge-ort merge strategy

[Elijah Newren]

On Fri, Mar 19, 2021 at 6:05 AM Derrick Stolee <stolee@gmail.com> wrote:
>
> On 3/17/2021 5:28 PM, Elijah Newren via GitGitGadget wrote:
> > From: Elijah Newren <newren@gmail.com>
> >
> > In preparation for switching from merge-recursive to merge-ort as the
> > default strategy, ensure that we are testing it.
>
> OK, so here we are testing it by default in CI, not just in that
> second round of optional environment variables. If that is what

Note quite; my patch adds testing of merge-ort with *-gcc variants on
each of the major platforms, but still includes merge-recursive
testing in the *-clang variants.

> you intended, then this is the diff I was expecting:
>
> diff --git a/ci/run-build-and-tests.sh b/ci/run-build-and-tests.sh
> index a66b5e8c75a..c013e9e646a 100755
> --- a/ci/run-build-and-tests.sh
> +++ b/ci/run-build-and-tests.sh
> @@ -25,6 +25,7 @@ linux-gcc)
>         export GIT_TEST_ADD_I_USE_BUILTIN=1
>         export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=master
>         export GIT_TEST_WRITE_REV_INDEX=1
> +       export GIT_TEST_MERGE_STRATEGY=org

"ort", not "org".  :-)

>         make test
>         ;;
>  linux-clang)
>
> However, if we want to be aggressive in adopting the ort strategy
> very soon, then your approach of testing more frequently is
> valuable.

I don't think testing limited to linux-gcc is very valuable:

* I've got opt-in volunteers (~60 of them) using it for the last half
year for their daily work (on Mac & Linux)
* For these volunteers, `git log -p` _also_ remerges every 2-parent
merge automatically (there's a --remerge-diff capability)
* We also had a bug where an internal script ('sparsify') looked for
files changed in "local-only" commits via `git log --name-only HEAD
--not --remotes=origin`.
* At least one person renamed their default remote to something other
than "origin"

The upshot is we not only have many testers using it for daily work,
we had at least one guinea pig redoing every merge in his
repository...and found a platform specific bug in some commit from
years ago because of it.

In the last half year, I've only had three bug reports, none reported
by more than one person:

* Platform specific merge issue triggered only in a commit in a
certain repository from years ago (fixed by first patch of this
series, the STABLE_QSORT() one)
* Mis-handling of present-despite-SKIP_WORKTREE file that *also* was
involved in a merge conflict (see t6428 addition in this series; note
that merge-recursive still fails it)
* A bug in the --remerge-diff results

So, at this point, beyond avoiding regressions the primary value I
find in testing is in expanding it.  windows is my big hole so more
than anything I want ort testing there.

> Would it be worth setting GIT_TEST_MERGE_ALGORITHM=ort by default
> in test-lib.sh, too? That could help developers working on top of
> your topic avoid creating test failures that only show up in CI.

Actually, that sounds like a good idea, and we could just pick one or
two special CI jobs to test with GIT_TEST_MERGE_STRATEGY=recursive.

Re: [PATCH v2 00/13] Declare merge-ort ready for general usage

[Elijah Newren]

On Fri, Mar 19, 2021 at 6:09 AM Derrick Stolee <stolee@gmail.com> wrote:
>
> On 3/17/2021 5:27 PM, Elijah Newren via GitGitGadget wrote:
> > This series depends on ort-perf-batch-10[1], and obsoletes the ort-remainder
> > topic[2] (that hadn't been picked up yet, so hopefully this doesn't cause
> > any confusion)
> >
> > With this series, merge-ort is ready for general usage -- it passes all
> > tests, passes dozens of tests that don't under merge-recursive, and
> > merge-ort is is already significantly faster than merge-recursive when
> > rename detection is involved. Users can select merge-ort by (a) passing
> > -sort to either git merge or git rebase, or (b) by setting pull.twohead=ort
> > [3], or (c) by setting GIT_TEST_MERGE_ALGORITHM=ort.
> >
> > Changes since v1:
> >
> >  * subsumed the ort-remainder topic (the first 10 patches), which has
> >    already been reviewed by both Ævar and Stolee[2].
> >  * the next two patches were the original v1, reviewed by Stolee
> >  * the final patch is new and adds testing.
>
> Sorry for the delay in looking at this. I read the two series before
> this, and found this to be a good union of them.
>
> My only question on the final patch is a two parter:
>
> 1. Did you mean to go this far?

At least, yes.

> 2. Did you want to go farther?

I like your suggestion in the other email; I'll resubmit to take
advantage of it.  :-)

> Mostly: how much do we want to prepare for ORT as the default
> strategy, at the expense of reducing testing of the recursive
> strategy?

We definitely should prepare for merge-ort as the default.  There's a
question of how soon the switch should be, but no question in my mind
that we should move towards it.

What do others think is needed before we switch the default?
Personally, I think there are three things:

1) merge-ort must handle the same cases that merge-recursive does
2) merge-ort must provide some benefit over merge-recursive
3) folks on the mailing list need to be comfortable with the default switch.

What would others add?

The first 2 conditions are already met, in spades.  For all the code
that calls merge-ort, merge-ort handles all the same cases, is more
correct, more performant, and more featureful than merge-recursive.  I
was surprised by how smooth the roll-out was and has continued to be
for internal users at $DAYJOB.

The only question is item #3.  If it weren't for that, I'd say we
should switch the default now, because AFAICT delaying the default
switch will just delay when expanded testing occurs, and I have run
out of other ways to expand testing.  But I realize I'm the only one
who knows that and is comfortable with that.  So I'm not proposing a
default switch yet; I want to hear feedback on what others want to see
done before we switch.  (At some point in the future, say another year
or two, I'll ask what needs to be done before we *delete*
merge-recursive.[ch].  But that's still off in the distant future.)

Re: [PATCH v2 00/13] Declare merge-ort ready for general usage

[Elijah Newren]

One more thing...

On Fri, Mar 19, 2021 at 6:09 AM Derrick Stolee <stolee@gmail.com> wrote:
>
> On 3/17/2021 5:27 PM, Elijah Newren via GitGitGadget wrote:

^^^ Note: 18 hours, 42 minutes difference.

> > This series depends on ort-perf-batch-10[1], and obsoletes the ort-remainder
> > topic[2] (that hadn't been picked up yet, so hopefully this doesn't cause
> > any confusion)
> >
> > With this series, merge-ort is ready for general usage -- it passes all
> > tests, passes dozens of tests that don't under merge-recursive, and
> > merge-ort is is already significantly faster than merge-recursive when
> > rename detection is involved. Users can select merge-ort by (a) passing
> > -sort to either git merge or git rebase, or (b) by setting pull.twohead=ort
> > [3], or (c) by setting GIT_TEST_MERGE_ALGORITHM=ort.
> >
> > Changes since v1:
> >
> >  * subsumed the ort-remainder topic (the first 10 patches), which has
> >    already been reviewed by both Ævar and Stolee[2].
> >  * the next two patches were the original v1, reviewed by Stolee
> >  * the final patch is new and adds testing.
>
> Sorry for the delay in looking at this.

Delay?!?  You only took a day and a half to respond!  That's a fast
turnaround, not a delay.  Don't apologize for that, or you'll set
unreasonably high expectations that'll scare the rest of us away.  :-)


Thanks for all your review efforts; it's very much appreciated!

[PATCH v3 00/13] Declare merge-ort ready for general usage

[Elijah Newren via GitGitGadget]

This series depends on ort-perf-batch-10[1], and obsoletes the ort-remainder
topic[2] (that hadn't been picked up yet, so hopefully this doesn't cause
any confusion)

With this series, merge-ort is ready for general usage -- it passes all
tests, passes dozens of tests that don't under merge-recursive, and
merge-ort is is already significantly faster than merge-recursive when
rename detection is involved. Users can select merge-ort by (a) passing
-sort to either git merge or git rebase, or (b) by setting pull.twohead=ort
[3], or (c) by setting GIT_TEST_MERGE_ALGORITHM=ort.

Changes since v2:

 * changed the last patch to default testing to ort so people don't have to
   wait until CI for failures (but still keep linux-gcc testing
   merge-recursive so it retains coverage), as suggested by Stolee

[1]
https://lore.kernel.org/git/pull.853.git.1615674128.gitgitgadget@gmail.com/
[2]
https://lore.kernel.org/git/pull.973.v2.git.git.1615271086.gitgitgadget@gmail.com/
[3] See commit 14c4586c2d ("merge,rebase,revert: select ort or recursive by
config or environment", 2020-11-02)

Elijah Newren (13):
  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
  Revert "merge-ort: ignore the directory rename split conflict for now"
  t6423: mark remaining expected failure under merge-ort as such
  Add testing with merge-ort merge strategy

 branch.c                                      |   1 +
 builtin/rebase.c                              |   1 +
 ci/run-build-and-tests.sh                     |   1 +
 merge-ort.c                                   | 242 ++++++++++++++++--
 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/t6423-merge-rename-directories.sh           |   2 +-
 t/t6428-merge-conflicts-sparse.sh             | 158 ++++++++++++
 t/t6437-submodule-merge.sh                    |   5 +-
 t/t6438-submodule-directory-file-conflicts.sh |   7 +-
 t/test-lib.sh                                 |   2 +
 16 files changed, 445 insertions(+), 38 deletions(-)
 create mode 100755 t/t6428-merge-conflicts-sparse.sh


base-commit: ac0ba91ce275227f5df8f16fb986308ff88b198b
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-905%2Fgitgitgadget%2Fort-readiness-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-905/gitgitgadget/ort-readiness-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/905

Range-diff vs v2:

  1:  e223f842748c =  1:  e223f842748c merge-ort: use STABLE_QSORT instead of QSORT where required
  2:  6d34cc466bd5 =  2:  6d34cc466bd5 merge-ort: add a special minimal index just for renormalization
  3:  4ff23d2f52a0 =  3:  4ff23d2f52a0 merge-ort: have ll_merge() use a special attr_index for renormalization
  4:  c1c9605c1932 =  4:  c1c9605c1932 merge-ort: let renormalization change modify/delete into clean delete
  5:  41fffcdd3b78 =  5:  41fffcdd3b78 merge-ort: support subtree shifting
  6:  6aec1f499b80 =  6:  6aec1f499b80 t6428: new test for SKIP_WORKTREE handling and conflicts
  7:  fe3baf696785 =  7:  fe3baf696785 merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries
  8:  f9325647a9fc =  8:  f9325647a9fc t: mark several submodule merging tests as fixed under merge-ort
  9:  4a79e6134691 =  9:  4a79e6134691 merge-ort: write $GIT_DIR/AUTO_MERGE whenever we hit a conflict
 10:  a37979454069 = 10:  a37979454069 merge-recursive: add a bunch of FIXME comments documenting known bugs
 11:  6bda855f2980 = 11:  6bda855f2980 Revert "merge-ort: ignore the directory rename split conflict for now"
 12:  1c6361c9b88a = 12:  1c6361c9b88a t6423: mark remaining expected failure under merge-ort as such
 13:  d8536f56ab29 <  -:  ------------ Add testing with merge-ort merge strategy
  -:  ------------ > 13:  c2d2a1ccaea7 Add testing with merge-ort merge strategy

-- 
gitgitgadget

[PATCH v3 01/13] 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 7f5750ce6ab0..34a91c435737 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2405,7 +2405,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);
@@ -2550,6 +2550,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 */
@@ -3325,6 +3326,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 v3 02/13] 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 34a91c435737..3c606fa7e4b3 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"
@@ -220,6 +221,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
 	 *
@@ -399,6 +410,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) {
 		strintmap_func(&renames->dirs_removed[i]);
@@ -3407,6 +3421,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);
@@ -3482,6 +3498,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 v3 03/13] 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 3c606fa7e4b3..cdc1e2fe7a24 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -410,7 +410,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 */
@@ -1201,6 +1201,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,
@@ -1215,6 +1272,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;
@@ -1253,7 +1313,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 v3 04/13] 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 cdc1e2fe7a24..c7083e3769aa 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -2549,6 +2549,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)
@@ -3136,8 +3191,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 v3 05/13] 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 c7083e3769aa..c4fe234d8972 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -3551,6 +3551,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;
@@ -3680,6 +3697,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 v3 06/13] 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 v3 07/13] 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 c4fe234d8972..303e89414274 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -3369,23 +3369,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;
@@ -3426,9 +3430,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
@@ -3478,8 +3496,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 */
@@ -3489,13 +3505,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 v3 08/13] 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 v3 09/13] 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 840dbd7eb777..6c252d62758c 100644
--- a/builtin/rebase.c
+++ b/builtin/rebase.c
@@ -737,6 +737,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 303e89414274..e8f1a435f99a 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -3496,6 +3496,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 */
@@ -3514,6 +3517,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 v3 10/13] 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

[PATCH v3 11/13] Revert "merge-ort: ignore the directory rename split conflict for now"

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

This reverts commit 5ced7c3da009090c5a926e3123a71314c7f28d42, which was
put in place as a temporary measure to avoid optimizations unstably
erroring out on no destination having a majority of the necessary
renames for directories that had no new files and thus no need for
directory rename detection anyway.  Now that optimizations are in place
to prevent us from trying to compute directory rename count computations
for directories that do not need it, we can undo this temporary measure.

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

diff --git a/merge-ort.c b/merge-ort.c
index e8f1a435f99a..8258d3fd621e 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -1636,18 +1636,7 @@ static void get_provisional_directory_renames(struct merge_options *opt,
 				 "no destination getting a majority of the "
 				 "files."),
 			       source_dir);
-			/*
-			 * We should mark this as unclean IF something attempts
-			 * to use this rename.  We do not yet have the logic
-			 * in place to detect if this directory rename is being
-			 * used, and optimizations that reduce the number of
-			 * renames cause this to falsely trigger.  For now,
-			 * just disable it, causing t6423 testcase 2a to break.
-			 * We'll later fix the detection, and when we do we
-			 * will re-enable setting *clean to 0 (and thereby fix
-			 * t6423 testcase 2a).
-			 */
-			/*   *clean = 0;   */
+			*clean = 0;
 		} else {
 			strmap_put(&renames->dir_renames[side],
 				   source_dir, (void*)best);
-- 
gitgitgadget

[PATCH v3 12/13] t6423: mark remaining expected failure under merge-ort as such

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

When we started on merge-ort, thousands of tests failed when run with
the GIT_TEST_MERGE_ALGORITHM=ort flag; with so many, it didn't make
sense to flip all their test expectations.  The ones in t6409, t6418,
and the submodule tests are being handled by an independent in-flight
topic ("Complete merge-ort implemenation...almost").  The ones in
t6423 were left out of the other series because other ongoing series
that this commit depends upon were addressing those.  Now that we only
have one remaining test failure in t6423, let's mark it as such.

This remaining test will be fixed by a future optimization series, but
since merge-recursive doesn't pass this test either, passing it is not
necessary for declaring merge-ort ready for general use.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 t/t6423-merge-rename-directories.sh | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

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

[PATCH v3 13/13] Add testing with merge-ort merge strategy

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

In preparation for switching from merge-recursive to merge-ort as the
default strategy, have the testsuite default to running with merge-ort.
Keep coverage of the recursive backend by having the linux-gcc job run
with it.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 ci/run-build-and-tests.sh | 1 +
 t/test-lib.sh             | 2 ++
 2 files changed, 3 insertions(+)

diff --git a/ci/run-build-and-tests.sh b/ci/run-build-and-tests.sh
index 50e0b90073f1..2279ff70a735 100755
--- a/ci/run-build-and-tests.sh
+++ b/ci/run-build-and-tests.sh
@@ -16,6 +16,7 @@ linux-gcc)
 	export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main
 	make test
 	export GIT_TEST_SPLIT_INDEX=yes
+	export GIT_TEST_MERGE_ALGORITHM=recursive
 	export GIT_TEST_FULL_IN_PACK_ARRAY=true
 	export GIT_TEST_OE_SIZE=10
 	export GIT_TEST_OE_DELTA_SIZE=5
diff --git a/t/test-lib.sh b/t/test-lib.sh
index 431adba0fb3f..6f4185037183 100644
--- a/t/test-lib.sh
+++ b/t/test-lib.sh
@@ -448,6 +448,8 @@ export EDITOR
 
 GIT_DEFAULT_HASH="${GIT_TEST_DEFAULT_HASH:-sha1}"
 export GIT_DEFAULT_HASH
+GIT_TEST_MERGE_ALGORITHM="${GIT_TEST_MERGE_ALGORITHM:-ort}"
+export GIT_TEST_MERGE_ALGORITHM
 
 # Tests using GIT_TRACE typically don't want <timestamp> <file>:<line> output
 GIT_TRACE_BARE=1
-- 
gitgitgadget

Re: [PATCH v3 00/13] Declare merge-ort ready for general usage

[Derrick Stolee]

On 3/19/2021 8:03 PM, Elijah Newren via GitGitGadget wrote:
> This series depends on ort-perf-batch-10[1], and obsoletes the ort-remainder
> topic[2] (that hadn't been picked up yet, so hopefully this doesn't cause
> any confusion)
> 
> With this series, merge-ort is ready for general usage -- it passes all
> tests, passes dozens of tests that don't under merge-recursive, and
> merge-ort is is already significantly faster than merge-recursive when
> rename detection is involved. Users can select merge-ort by (a) passing
> -sort to either git merge or git rebase, or (b) by setting pull.twohead=ort
> [3], or (c) by setting GIT_TEST_MERGE_ALGORITHM=ort.
> 
> Changes since v2:
> 
>  * changed the last patch to default testing to ort so people don't have to
>    wait until CI for failures (but still keep linux-gcc testing
>    merge-recursive so it retains coverage), as suggested by Stolee

What a great suggestion! This series gets

Reviewed-by: Derrick Stolee <dstolee@microsoft.com>