Small new merge-ort features, prepping for deletion of merge-recursive.[ch]

I've got 19 patches covering the work needed to prep for and allow us to delete merge-recursive.[ch], and remap 'recursive' to 'ort', including some clean-up along the way. I've tried to divide it up into five smaller patch series.

These 3 patches are the first of those series, and each of these 3 patches provide a small new feature that together will be used to allow us to convert some callers over from recursive to ort. If the third patch, introducing merge_ort_generic(), doesn't make sense to submit without one of its new callers, I can extend this series to 6 patches and include the conversion of git-am.sh.

Elijah Newren (3):
merge-ort: add new merge_ort_generic() function
merge-ort: allow rename detection to be disabled
merge-ort: support having merge verbosity be set to 0

 Documentation/merge-strategies.adoc | 12 +++---
 merge-ort-wrappers.c                | 64 +++++++++++++++++++++++++++++
 merge-ort-wrappers.h                | 12 ++++++
 merge-ort.c                         | 24 ++++++++---
 merge-ort.h                         |  5 +++
 5 files changed, 106 insertions(+), 11 deletions(-)

base-commit: a36e024e989f4d35f35987a60e3af8022cac3420
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1875%2Fnewren%2Fendit-new-features-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1875/newren/endit-new-features-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1875

gitgitgadget

From: Elijah Newren <[email protected]>

merge-recursive.[ch] have three entry points:
* merge_trees()
* merge_recursive()
* merge_recursive_generic()
merge-ort*.[ch] only has equivalents for the first two. Add an equivalent for the final entry point, so we can switch callers to use it and remove merge-recursive.[ch].

---
 merge-ort-wrappers.c | 64 ++++++++++++++++++++++++++++++++++++++++++++
 merge-ort-wrappers.h | 12 +++++++++
 merge-ort.c          | 17 ++++++++----
 merge-ort.h          |  5 ++++
 4 files changed, 93 insertions(+), 5 deletions(-)

index d6f61359965..62834c30e9e 100644
@@ -1,9 +1,13 @@
 #include "git-compat-util.h"
 #include "gettext.h"
 #include "hash.h"
+#include "hex.h"
+#include "lockfile.h"
 #include "merge-ort.h"
 #include "merge-ort-wrappers.h"
 #include "read-cache-ll.h"
+#include "repository.h"
+#include "tag.h"
 #include "tree.h"
 
 #include "commit.h"

@@ -64,3 +68,63 @@ int merge_ort_recursive(struct merge_options *opt,
 
 	return tmp.clean;
 }
+
+static struct commit *get_ref(struct repository *repo,
+			      const struct object_id *oid,
+			      const char *name)
+{
+	struct object *object;
+
+	object = deref_tag(repo, parse_object(repo, oid),
+			   name, strlen(name));
+	if (!object)
+		return NULL;
+	if (object->type == OBJ_TREE)
+		return make_virtual_commit(repo, (struct tree*)object, name);
+	if (object->type != OBJ_COMMIT)
+		return NULL;
+	if (repo_parse_commit(repo, (struct commit *)object))
+		return NULL;
+	return (struct commit *)object;
+}
+
+int merge_ort_generic(struct merge_options *opt,
+		      const struct object_id *head,
+		      const struct object_id *merge,
+		      int num_merge_bases,
+		      const struct object_id *merge_bases,
+		      struct commit **result)
+{
+	int clean;
+	struct lock_file lock = LOCK_INIT;
+	struct commit *head_commit = get_ref(opt->repo, head, opt->branch1);
+	struct commit *next_commit = get_ref(opt->repo, merge, opt->branch2);
+	struct commit_list *ca = NULL;
+
+	if (merge_bases) {
+		int i;
+		for (i = 0; i < num_merge_bases; ++i) {
+			struct commit *base;
+			if (!(base = get_ref(opt->repo, &merge_bases[i],
+					     oid_to_hex(&merge_bases[i]))))
+				return error(_("Could not parse object '%s'"),
+					     oid_to_hex(&merge_bases[i]));
+			commit_list_insert(base, &ca);
+		}
+	}
+
+	repo_hold_locked_index(opt->repo, &lock, LOCK_DIE_ON_ERROR);
+	clean = merge_ort_recursive(opt, head_commit, next_commit, ca,
+				    result);
+	free_commit_list(ca);
+	if (clean < 0) {
+		rollback_lock_file(&lock);
+		return clean;
+	}
+
+	if (write_locked_index(opt->repo->index, &lock,
+			       COMMIT_LOCK | SKIP_IF_UNCHANGED))
+		return error(_("Unable to write index."));
+
+	return clean ? 0 : 1;
+}

index 90af1f69c55..aeffa1c87b4 100644
@@ -22,4 +22,16 @@ int merge_ort_recursive(struct merge_options *opt,
 			const struct commit_list *ancestors,
 			struct commit **result);
 
+/*
+ * rename-detecting three-way merge.  num_merge_bases must be at least 1.
+ * Recursive ancestor consolidation will be performed if num_merge_bases > 1.
+ * Wrapper mimicking the old merge_recursive_generic() function.
+ */
+int merge_ort_generic(struct merge_options *opt,
+		      const struct object_id *head,
+		      const struct object_id *merge,
+		      int num_merge_bases,
+		      const struct object_id *merge_bases,
+		      struct commit **result);
+
 #endif

index 46e78c3ffa6..b4ff24403a1 100644
@@ -4878,9 +4878,9 @@ static inline void set_commit_tree(struct commit *c, struct tree *t)
 	c->maybe_tree = t;
 }
 
-static struct commit *make_virtual_commit(struct repository *repo,
-					  struct tree *tree,
-					  const char *comment)
+struct commit *make_virtual_commit(struct repository *repo,
+				   struct tree *tree,
+				   const char *comment)
 {
 	struct commit *commit = alloc_commit_node(repo);
 

@@ -5186,6 +5186,8 @@ static void merge_ort_internal(struct merge_options *opt,
 		ancestor_name = "empty tree";
 	} else if (merge_bases) {
 		ancestor_name = "merged common ancestors";
+	} else if (opt->ancestor) {
+		ancestor_name = opt->ancestor;
 	} else {
 		strbuf_add_unique_abbrev(&merge_base_abbrev,
 					 &merged_merge_bases->object.oid,

@@ -5275,8 +5277,13 @@ void merge_incore_recursive(struct merge_options *opt,
 {
 	trace2_region_enter("merge", "incore_recursive", opt->repo);
 
-	/* We set the ancestor label based on the merge_bases */
-	assert(opt->ancestor == NULL);
+	/*
+	 * We set the ancestor label based on the merge_bases...but we
+	 * allow one exception through so that builtin/am can override
+	 * with its constructed fake ancestor.
+	 */
+	assert(opt->ancestor == NULL ||
+	       (merge_bases && !merge_bases->next));
 
 	trace2_region_enter("merge", "merge_start", opt->repo);
 	merge_start(opt, result);

index 82f2b3222d2..b63bc5424e7 100644
@@ -44,6 +44,11 @@ struct merge_result {
 	unsigned _properly_initialized;
 };
 
+/* Mostly internal function also used by merge-ort-wrappers.c */
+struct commit *make_virtual_commit(struct repository *repo,
+				   struct tree *tree,
+				   const char *comment);
+
 /*
  * rename-detecting three-way merge with recursive ancestor consolidation.
  * working tree and index are untouched.

gitgitgadget

From: Elijah Newren <[email protected]>

When merge-ort was written, I did not at first allow rename detection to be disabled, because I suspected that most folks disabling rename detection were doing so solely for performance reasons. Since I put a lot of working into providing dramatic speedups for rename detection performance as used by the merge machinery, I wanted to know if there were still real world repositories where rename detection was problematic from a performance perspective. We have had years now to collect such information, and while we never received one, waiting longer with the option disabled seems unlikely to help surface such issues at this point. Also, there has been at least one request to allow rename detection to be disabled for behavioral rather than performance reasons, so let's start heeding the config and command line settings.

---
 Documentation/merge-strategies.adoc | 12 ++++++------
 merge-ort.c                         |  5 +++++
 2 files changed, 11 insertions(+), 6 deletions(-)

index 93822ebc4e8..59f5ae36ccb 100644
@@ -82,6 +82,11 @@ find-renames[=<n>];;
 rename-threshold=<n>;;
 	Deprecated synonym for `find-renames=<n>`.
 
+no-renames;;
+	Turn off rename detection. This overrides the `merge.renames`
+	configuration variable.
+	See also linkgit:git-diff[1] `--no-renames`.
+
 subtree[=<path>];;
 	This option is a more advanced form of 'subtree' strategy, where
 	the strategy makes a guess on how two trees must be shifted to

@@ -107,7 +112,7 @@ For a path that is a submodule, the same caution as 'ort' applies to this
 strategy.
 +
 The 'recursive' strategy takes the same options as 'ort'.  However,
-there are three additional options that 'ort' ignores (not documented
+there are two additional options that 'ort' ignores (not documented
 above) that are potentially useful with the 'recursive' strategy:
 
 patience;;

@@ -121,11 +126,6 @@ diff-algorithm=[patience|minimal|histogram|myers];;
 	specifically uses `diff-algorithm=histogram`, while `recursive`
 	defaults to the `diff.algorithm` config setting.
 
-no-renames;;
-	Turn off rename detection. This overrides the `merge.renames`
-	configuration variable.
-	See also linkgit:git-diff[1] `--no-renames`.
-
 resolve::
 	This can only resolve two heads (i.e. the current branch
 	and another branch you pulled from) using a 3-way merge

index b4ff24403a1..a6960b6a1b4 100644
@@ -3448,6 +3448,11 @@ static int detect_and_process_renames(struct merge_options *opt)
 
 	if (!possible_renames(renames))
 		goto cleanup;
+	if (opt->detect_renames == 0) {
+		renames->redo_after_renames = 0;
+		renames->cached_pairs_valid_side = 0;
+		goto cleanup;
+	}
 
 	trace2_region_enter("merge", "regular renames", opt->repo);
 	detection_run |= detect_regular_renames(opt, MERGE_SIDE1);

gitgitgadget

From: Elijah Newren <[email protected]>

Various callers such as am & checkout set the merge verbosity to 0 to avoid having conflict messages printed. While this could be achieved by avoiding the wrappers from merge-ort-wrappers and instead passing 0 for display_update_msgs to merge_switch_to_result(), for simplicity of converting callers simply allow them to also achieve this with the merge-ort-wrappers by setting verbosity to 0.

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

index a6960b6a1b4..8021083c112 100644
@@ -799,6 +799,8 @@ static void path_msg(struct merge_options *opt,
 		return; /* Do not record mere hints in headers */
 	if (opt->priv->call_depth && opt->verbosity < 5)
 		return; /* Ignore messages from inner merges */
+	if (!opt->verbosity)
+		return;
 
 	/* Ensure path_conflicts (ptr to array of logical_conflict) allocated */
 	path_conflicts = strmap_get(&opt->priv->conflicts, primary_path);

gitgitgadget

I think extending it to 6 patches would make sense as it's somewhat unfortunate that this version introduces the function, but has no callers at all.

Patrick

It might be nice to provide a link to that request for more context.

Yeah, I noticed the same thing and agree that it would be helpful to see that spelled out in the commit message.

Thanks,
Taylor

I don't know if a link exists; I suspect the request referred to here is an email that Johannes Schindelin wrote to Elijah privately).

But I am almost certain that the behavior requested here is to disable rename detection to match the behavior of GitHub's prior use of libgit2 to perform merges, where we also had rename detection disabled (for reasons that are unclear to me, but Peff might know).

    if (!opt->detect_renames)

?

Yeah, having a test here would be nice.

Thanks,
Taylor

Eh. I have gone back and forth about that over the years. I think in cases where the either caller(s) or implementation is sufficiently complicated, it's OK to introduce a (non-static) function without any callers.

I don't feel strongly about it, so I think the multi-series structure is fine as it is (especially since we know that more are coming in the future). But I'm also not opposed to seeing this series extended out to include the three additional patches.

Thanks,
Taylor

Yeah, it looks like when I was splitting commits, I had more of this explanation in a commit which was explaining differences in testcases. I'll copy the relevant bits here. Thanks for reading carefully.

Will add.

It exists: https://lore.kernel.org/git/CABPp-BG-Nx6SCxxkGXn_Fwd2wseifMFND8eddvWxiZVZk0zRaA@mail.gmail.com/

...which wasn't Johannes' request.

No, if that were the sole reason, I'd say it probably only belongs in our internal fork. Disabling of rename detection within GitHub was a temporary internal migration measure, not a desired end state -- at least that's the way Johannes portrayed it to me. I know that "temporary" sometimes lasts longer than we want, but now that I've become internal to GitHub, one of the things I want to do is add some weight to that "temporary" modifier.

Yeah, I wanted an opt->detect_renames == DIFF_DETECT_NONE, but we never defined that and only defined DIFF_DETECT_RENAME and DIFF_DETECT_COPY. I'll switch it over.

Will add.

Yeah, but after thinking about it more I don't like it here. I don't really like the opt->verbosity thing from merge-recursive, it simply survived because it was a semi-public API, but I'd rather minimize it. So, in the next round I think I'm going to stick this in the merge-ort-wrappers rather than have it appear here.

I'd rather reuse git {switch,checkout} -m's tests for this purpose rather than adding new ones (and perhaps the ones from git-am; can't remember if those also caught this). If you feel strongly about this, I'll just squash this into the later patch and make it bigger so we don't need more redundant tests.

Ah, thanks for the link!

:-).

Thanks,
Taylor

No, I don't feel strongly.

Thanks,
Taylor

I've got 19 patches covering the work needed to prep for and allow us to delete merge-recursive.[ch], and remap 'recursive' to 'ort', including some clean-up along the way. I've tried to divide it up into some smaller patch series.

These 6 patches are the first of those series. Breakdown:

* The first 3 patches provide small new features to allow us to convert later callers
* Patches 4-5 document and fix a bug with directory rename detection being turned off (since git am always turned off directory rename detection, this is a prerequisite for converting git am)
* Patch 6 converts git am from using merge_recursive_generic() to use the new merge_ort_generic().

Changes since v1:

* Patch 1: Added an explanation in the commit message about the one difference between merge_recursive_generic() and merge_ort_generic() -- the label for the ancestor commit
* Patch 2: Linked the relevant discussion in the commit message, fixed a style issue, and added a testcase
* Patch 3: Since the opt->verbosity stuff was an unwanted carryover (due to being partially public API), move the tweak to the merge-ort-wrappers to avoid promoting it
* Added 3 more patches, so folks can see one of the callers of merge_ort_generic().

Elijah Newren (5):
merge-ort: add new merge_ort_generic() function
merge-ort: allow rename detection to be disabled
merge-ort: support having merge verbosity be set to 0
merge-ort: fix merge.directoryRenames=false
am: switch from merge_recursive_generic() to merge_ort_generic()

Johannes Schindelin (1):
t3650: document bug when directory renames are turned off

 Documentation/merge-strategies.adoc | 12 ++---
 builtin/am.c                        |  5 +-
 merge-ort-wrappers.c                | 72 ++++++++++++++++++++++++++++-
 merge-ort-wrappers.h                | 12 +++++
 merge-ort.c                         | 53 ++++++++++++++++++---
 merge-ort.h                         |  5 ++
 t/t3650-replay-basics.sh            | 22 +++++++++
 t/t4151-am-abort.sh                 |  2 +-
 t/t4255-am-submodule.sh             |  1 -
 t/t4301-merge-tree-write-tree.sh    |  6 +++
 t/t6427-diff3-conflict-markers.sh   |  2 +-
 11 files changed, 172 insertions(+), 20 deletions(-)

base-commit: a36e024e989f4d35f35987a60e3af8022cac3420
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1875%2Fnewren%2Fendit-new-features-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1875/newren/endit-new-features-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1875

Range-diff vs v1:

1: 9f73e54224d ! 1: c2f2e3e0cd6 merge-ort: add new merge_ort_generic() function
@@ Commit message
equivalent for the final entry point, so we can switch callers to use it and remove merge-recursive.[ch].

+ While porting it over, finally fix the issue with the label for the
+ ancestor (used when merge.conflictStyle=diff3 as a conflict label).
+ merge-recursive.c has traditionally not allowed callers to set that
+ label, but I have found that problematic for years.
+
+ (Side note: This function was initially part of the merge-ort rewrite,
+ but reviewers questioned the ancestor label funnyness which I was
+ never really happy with anyway. It resulted in me jettisoning it and
+ hoping at the time that I would eventually be able to force the existing
+ callers to use some other API. That worked with git stash, as per
+ 874cf2a60444 (stash: apply stash using 'merge_ort_nonrecursive()',
+ 2022-05-10), but this API is the most reasonable one for git am and
+ git merge-recursive, if we can just allow them some freedom over the
+ ancestor label.)
+
+ The merge_recursive_generic() function did not know whether it was being
+ invoked by git stash, git merge-recursive, or git am, and the
+ choice of meaningful ancestor label, when there is a unique ancestor,
+ varies for these different callers:
+
+ * git am: ancestor is a constructed "fake ancestor" that user knows
+ nothing about and has no access to. (And is different than
+ the normal thing we mean by a "virtual merge base" which is
+ the merging of merge bases.)
+ * git merge-recursive: ancestor might be a tree, but at least it
+ was one specified by the user (if they invoked
+ merge-recursive directly)
+ * git stash: ancestor was the commit serving as the stash base
+
+ Thus, using a label like "constructed merge base" (as
+ merge_recursive_generic() does) presupposes that git am is the only
+ caller; it is incorrect for other callers. This label has thrown me off
+ more than once. Allow the caller to override when there is a unique
+ merge base.
+

## merge-ort-wrappers.c ##
2: 4292b22723f ! 2: f401a8e0967 merge-ort: allow rename detection to be disabled
@@ Commit message
longer with the option disabled seems unlikely to help surface such issues at this point. Also, there has been at least one request to allow rename detection to be disabled for behavioral rather than
- performance reasons, so let's start heeding the config and command line
- settings.
+ performance reasons (see the thread including
+ https://lore.kernel.org/git/CABPp-BG-Nx6SCxxkGXn_Fwd2wseifMFND8eddvWxiZVZk0zRaA@mail.gmail.com/
+ ), so let's start heeding the config and command line settings.

@@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt)

if (!possible_renames(renames))
goto cleanup;
-+ if (opt->detect_renames == 0) {
++ if (!opt->detect_renames) {
+ renames->redo_after_renames = 0;
+ renames->cached_pairs_valid_side = 0;
+ goto cleanup;
@@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt)

trace2_region_enter("merge", "regular renames", opt->repo); detection_run |= detect_regular_renames(opt, MERGE_SIDE1);
+
+ ## t/t4301-merge-tree-write-tree.sh ##
+@@ t/t4301-merge-tree-write-tree.sh: test_expect_success 'Clean merge' '
+ test_cmp expect actual
+ '
+
++# Repeat the previous test, but turn off rename detection ++test_expect_success 'Failed merge without rename detection' '
++ test_must_fail git -c diff.renames=false merge-tree --write-tree side1 side3 >out &&
++ grep "CONFLICT (modify/delete): numbers deleted" out
++'
++
+ test_expect_success 'Content merge and a few conflicts' '
+ git checkout side1^0 &&
+ test_must_fail git merge side2 &&

 3:  c2a2be336e0 < -:  ----------- merge-ort: support having merge verbosity be set to 0
 -:  ----------- > 3:  a508b0a0fe2 merge-ort: support having merge verbosity be set to 0
 -:  ----------- > 4:  fefda4add11 t3650: document bug when directory renames are turned off
 -:  ----------- > 5:  b25225c3cab merge-ort: fix merge.directoryRenames=false
 -:  ----------- > 6:  3f4b74eb3b9 am: switch from merge_recursive_generic() to merge_ort_generic()

gitgitgadget

From: Elijah Newren <[email protected]>

merge-recursive.[ch] have three entry points:
* merge_trees()
* merge_recursive()
* merge_recursive_generic()
merge-ort*.[ch] only has equivalents for the first two. Add an equivalent for the final entry point, so we can switch callers to use it and remove merge-recursive.[ch].

While porting it over, finally fix the issue with the label for the ancestor (used when merge.conflictStyle=diff3 as a conflict label). merge-recursive.c has traditionally not allowed callers to set that label, but I have found that problematic for years.

(Side note: This function was initially part of the merge-ort rewrite, but reviewers questioned the ancestor label funnyness which I was never really happy with anyway. It resulted in me jettisoning it and hoping at the time that I would eventually be able to force the existing callers to use some other API. That worked with git stash, as per 874cf2a60444 (stash: apply stash using 'merge_ort_nonrecursive()', 2022-05-10), but this API is the most reasonable one for git am and git merge-recursive, if we can just allow them some freedom over the ancestor label.)

The merge_recursive_generic() function did not know whether it was being invoked by git stash, git merge-recursive, or git am, and the choice of meaningful ancestor label, when there is a unique ancestor, varies for these different callers:

* git am: ancestor is a constructed "fake ancestor" that user knows nothing about and has no access to. (And is different than the normal thing we mean by a "virtual merge base" which is the merging of merge bases.)
* git merge-recursive: ancestor might be a tree, but at least it was one specified by the user (if they invoked merge-recursive directly)
* git stash: ancestor was the commit serving as the stash base

Thus, using a label like "constructed merge base" (as merge_recursive_generic() does) presupposes that git am is the only caller; it is incorrect for other callers. This label has thrown me off more than once. Allow the caller to override when there is a unique merge base.

---
 merge-ort-wrappers.c | 64 ++++++++++++++++++++++++++++++++++++++++++++
 merge-ort-wrappers.h | 12 +++++++++
 merge-ort.c          | 17 ++++++++----
 merge-ort.h          |  5 ++++
 4 files changed, 93 insertions(+), 5 deletions(-)

index d6f61359965..62834c30e9e 100644
@@ -1,9 +1,13 @@
 #include "git-compat-util.h"
 #include "gettext.h"
 #include "hash.h"
+#include "hex.h"
+#include "lockfile.h"
 #include "merge-ort.h"
 #include "merge-ort-wrappers.h"
 #include "read-cache-ll.h"
+#include "repository.h"
+#include "tag.h"
 #include "tree.h"
 
 #include "commit.h"

@@ -64,3 +68,63 @@ int merge_ort_recursive(struct merge_options *opt,
 
 	return tmp.clean;
 }
+
+static struct commit *get_ref(struct repository *repo,
+			      const struct object_id *oid,
+			      const char *name)
+{
+	struct object *object;
+
+	object = deref_tag(repo, parse_object(repo, oid),
+			   name, strlen(name));
+	if (!object)
+		return NULL;
+	if (object->type == OBJ_TREE)
+		return make_virtual_commit(repo, (struct tree*)object, name);
+	if (object->type != OBJ_COMMIT)
+		return NULL;
+	if (repo_parse_commit(repo, (struct commit *)object))
+		return NULL;
+	return (struct commit *)object;
+}
+
+int merge_ort_generic(struct merge_options *opt,
+		      const struct object_id *head,
+		      const struct object_id *merge,
+		      int num_merge_bases,
+		      const struct object_id *merge_bases,
+		      struct commit **result)
+{
+	int clean;
+	struct lock_file lock = LOCK_INIT;
+	struct commit *head_commit = get_ref(opt->repo, head, opt->branch1);
+	struct commit *next_commit = get_ref(opt->repo, merge, opt->branch2);
+	struct commit_list *ca = NULL;
+
+	if (merge_bases) {
+		int i;
+		for (i = 0; i < num_merge_bases; ++i) {
+			struct commit *base;
+			if (!(base = get_ref(opt->repo, &merge_bases[i],
+					     oid_to_hex(&merge_bases[i]))))
+				return error(_("Could not parse object '%s'"),
+					     oid_to_hex(&merge_bases[i]));
+			commit_list_insert(base, &ca);
+		}
+	}
+
+	repo_hold_locked_index(opt->repo, &lock, LOCK_DIE_ON_ERROR);
+	clean = merge_ort_recursive(opt, head_commit, next_commit, ca,
+				    result);
+	free_commit_list(ca);
+	if (clean < 0) {
+		rollback_lock_file(&lock);
+		return clean;
+	}
+
+	if (write_locked_index(opt->repo->index, &lock,
+			       COMMIT_LOCK | SKIP_IF_UNCHANGED))
+		return error(_("Unable to write index."));
+
+	return clean ? 0 : 1;
+}

index 90af1f69c55..aeffa1c87b4 100644
@@ -22,4 +22,16 @@ int merge_ort_recursive(struct merge_options *opt,
 			const struct commit_list *ancestors,
 			struct commit **result);
 
+/*
+ * rename-detecting three-way merge.  num_merge_bases must be at least 1.
+ * Recursive ancestor consolidation will be performed if num_merge_bases > 1.
+ * Wrapper mimicking the old merge_recursive_generic() function.
+ */
+int merge_ort_generic(struct merge_options *opt,
+		      const struct object_id *head,
+		      const struct object_id *merge,
+		      int num_merge_bases,
+		      const struct object_id *merge_bases,
+		      struct commit **result);
+
 #endif

index 46e78c3ffa6..b4ff24403a1 100644
@@ -4878,9 +4878,9 @@ static inline void set_commit_tree(struct commit *c, struct tree *t)
 	c->maybe_tree = t;
 }
 
-static struct commit *make_virtual_commit(struct repository *repo,
-					  struct tree *tree,
-					  const char *comment)
+struct commit *make_virtual_commit(struct repository *repo,
+				   struct tree *tree,
+				   const char *comment)
 {
 	struct commit *commit = alloc_commit_node(repo);
 

@@ -5186,6 +5186,8 @@ static void merge_ort_internal(struct merge_options *opt,
 		ancestor_name = "empty tree";
 	} else if (merge_bases) {
 		ancestor_name = "merged common ancestors";
+	} else if (opt->ancestor) {
+		ancestor_name = opt->ancestor;
 	} else {
 		strbuf_add_unique_abbrev(&merge_base_abbrev,
 					 &merged_merge_bases->object.oid,

@@ -5275,8 +5277,13 @@ void merge_incore_recursive(struct merge_options *opt,
 {
 	trace2_region_enter("merge", "incore_recursive", opt->repo);
 
-	/* We set the ancestor label based on the merge_bases */
-	assert(opt->ancestor == NULL);
+	/*
+	 * We set the ancestor label based on the merge_bases...but we
+	 * allow one exception through so that builtin/am can override
+	 * with its constructed fake ancestor.
+	 */
+	assert(opt->ancestor == NULL ||
+	       (merge_bases && !merge_bases->next));
 
 	trace2_region_enter("merge", "merge_start", opt->repo);
 	merge_start(opt, result);

index 82f2b3222d2..b63bc5424e7 100644
@@ -44,6 +44,11 @@ struct merge_result {
 	unsigned _properly_initialized;
 };
 
+/* Mostly internal function also used by merge-ort-wrappers.c */
+struct commit *make_virtual_commit(struct repository *repo,
+				   struct tree *tree,
+				   const char *comment);
+
 /*
  * rename-detecting three-way merge with recursive ancestor consolidation.
  * working tree and index are untouched.

gitgitgadget

From: Elijah Newren <[email protected]>

When merge-ort was written, I did not at first allow rename detection to be disabled, because I suspected that most folks disabling rename detection were doing so solely for performance reasons. Since I put a lot of working into providing dramatic speedups for rename detection performance as used by the merge machinery, I wanted to know if there were still real world repositories where rename detection was problematic from a performance perspective. We have had years now to collect such information, and while we never received one, waiting longer with the option disabled seems unlikely to help surface such issues at this point. Also, there has been at least one request to allow rename detection to be disabled for behavioral rather than performance reasons (see the thread including
https://lore.kernel.org/git/CABPp-BG-Nx6SCxxkGXn_Fwd2wseifMFND8eddvWxiZVZk0zRaA@mail.gmail.com/
), so let's start heeding the config and command line settings.

---
 Documentation/merge-strategies.adoc | 12 ++++++------
 merge-ort.c                         |  5 +++++
 t/t4301-merge-tree-write-tree.sh    |  6 ++++++
 3 files changed, 17 insertions(+), 6 deletions(-)

index 93822ebc4e8..59f5ae36ccb 100644
@@ -82,6 +82,11 @@ find-renames[=<n>];;
 rename-threshold=<n>;;
 	Deprecated synonym for `find-renames=<n>`.
 
+no-renames;;
+	Turn off rename detection. This overrides the `merge.renames`
+	configuration variable.
+	See also linkgit:git-diff[1] `--no-renames`.
+
 subtree[=<path>];;
 	This option is a more advanced form of 'subtree' strategy, where
 	the strategy makes a guess on how two trees must be shifted to

@@ -107,7 +112,7 @@ For a path that is a submodule, the same caution as 'ort' applies to this
 strategy.
 +
 The 'recursive' strategy takes the same options as 'ort'.  However,
-there are three additional options that 'ort' ignores (not documented
+there are two additional options that 'ort' ignores (not documented
 above) that are potentially useful with the 'recursive' strategy:
 
 patience;;

@@ -121,11 +126,6 @@ diff-algorithm=[patience|minimal|histogram|myers];;
 	specifically uses `diff-algorithm=histogram`, while `recursive`
 	defaults to the `diff.algorithm` config setting.
 
-no-renames;;
-	Turn off rename detection. This overrides the `merge.renames`
-	configuration variable.
-	See also linkgit:git-diff[1] `--no-renames`.
-
 resolve::
 	This can only resolve two heads (i.e. the current branch
 	and another branch you pulled from) using a 3-way merge

index b4ff24403a1..1d3b690224e 100644
@@ -3448,6 +3448,11 @@ static int detect_and_process_renames(struct merge_options *opt)
 
 	if (!possible_renames(renames))
 		goto cleanup;
+	if (!opt->detect_renames) {
+		renames->redo_after_renames = 0;
+		renames->cached_pairs_valid_side = 0;
+		goto cleanup;
+	}
 
 	trace2_region_enter("merge", "regular renames", opt->repo);
 	detection_run |= detect_regular_renames(opt, MERGE_SIDE1);

index eea19907b55..44f7d077593 100755
@@ -73,6 +73,12 @@ test_expect_success 'Clean merge' '
 	test_cmp expect actual
 '
 
+# Repeat the previous test, but turn off rename detection
+test_expect_success 'Failed merge without rename detection' '
+	test_must_fail git -c diff.renames=false merge-tree --write-tree side1 side3 >out &&
+	grep "CONFLICT (modify/delete): numbers deleted" out
+'
+
 test_expect_success 'Content merge and a few conflicts' '
 	git checkout side1^0 &&
 	test_must_fail git merge side2 &&

gitgitgadget

From: Elijah Newren <[email protected]>

Various callers such as am & checkout set the merge verbosity to 0 to avoid having conflict messages printed. While this could be achieved by avoiding the wrappers from merge-ort-wrappers and instead passing 0 for display_update_msgs to merge_switch_to_result(), for simplicity of converting callers simply allow them to also achieve this with the merge-ort-wrappers by setting verbosity to 0.

---
 merge-ort-wrappers.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

index 62834c30e9e..c54d56b3446 100644
@@ -33,6 +33,7 @@ int merge_ort_nonrecursive(struct merge_options *opt,
 			   struct tree *merge_base)
 {
 	struct merge_result result;
+	int show_msgs;
 
 	if (unclean(opt, head))
 		return -1;

@@ -42,9 +43,10 @@ int merge_ort_nonrecursive(struct merge_options *opt,
 		return 1;
 	}
 
+	show_msgs = !!opt->verbosity;
 	memset(&result, 0, sizeof(result));
 	merge_incore_nonrecursive(opt, merge_base, head, merge, &result);
-	merge_switch_to_result(opt, head, &result, 1, 1);
+	merge_switch_to_result(opt, head, &result, 1, show_msgs);
 
 	return result.clean;
 }

@@ -57,13 +59,15 @@ int merge_ort_recursive(struct merge_options *opt,
 {
 	struct tree *head = repo_get_commit_tree(opt->repo, side1);
 	struct merge_result tmp;
+	int show_msgs;
 
 	if (unclean(opt, head))
 		return -1;
 
+	show_msgs = !!opt->verbosity;
 	memset(&tmp, 0, sizeof(tmp));
 	merge_incore_recursive(opt, merge_bases, side1, side2, &tmp);
-	merge_switch_to_result(opt, head, &tmp, 1, 1);
+	merge_switch_to_result(opt, head, &tmp, 1, show_msgs);
 	*result = NULL;
 
 	return tmp.clean;

gitgitgadget

From: Johannes Schindelin <[email protected]>

There is a bug in the way renames are cached that rears its head when merge.directoryRenames is set to false; it results in the following message:

    merge-ort.c:3002: process_renames: Assertion `newinfo && !newinfo->merged.clean' failed.
    Aborted

It is quite a curious bug: the same test case will succeed, without any assertion, if instead run with merge.directoryRenames=true.

Further, the assertion does not manifest while replaying the first commit, it manifests while replaying the _second_ commit of the commit range. But it does _not_ manifest when the second commit is replayed individually.

This would indicate that there is an incomplete rename cache left-over from the first replayed commit which is being reused for the second commit, and if directory rename detection is enabled, the missing paths are somehow regenerated.

Incidentally, the same bug can by triggered by modifying t6429 to switch from merge.directoryRenames=true to merge.directoryRenames=false.

[en: tweaked the commit message slightly, including adjusting the
line number of the assertion to the latest version, and the much later discovery that a simple t6429 tweak would also display the issue.]

---
 t/t3650-replay-basics.sh | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

index 389670262e4..cade7930765 100755
@@ -195,4 +195,26 @@ test_expect_success 'using replay on bare repo to rebase multiple divergent bran
 	done
 '
 
+test_expect_failure 'merge.directoryRenames=false' '
+	# create a test case that stress-tests the rename caching
+	git switch -c rename-onto &&
+
+	mkdir -p to-rename &&
+	test_commit to-rename/move &&
+
+	mkdir -p renamed-directory &&
+	git mv to-rename/move* renamed-directory/ &&
+	test_tick &&
+	git commit -m renamed-directory &&
+
+	git switch -c rename-from HEAD^ &&
+	test_commit to-rename/add-a-file &&
+	echo modified >to-rename/add-a-file.t &&
+	test_tick &&
+	git commit -m modified to-rename/add-a-file.t &&
+
+	git -c merge.directoryRenames=false replay \
+		--onto rename-onto rename-onto..rename-from
+'
+
 test_done

gitgitgadget

From: Elijah Newren <[email protected]>

There are two issues here.

First, when merge.directoryRenames is set to false, there are a few code paths that should be turned off. I missed one; collect_renames() was still doing some directory rename detection logic unconditionally. It ended up not having much effect because get_provisional_directory_renames() was skipped earlier and not setting up renames->dir_renames, but the code should still be skipped.

Second, the larger issue is that sometimes we get a cached_pair rename from a previous commit being replayed mapping A->B, but in a subsequent commit but collect_merge_info() doesn't even recurse into the directory containing B because there are no source pairings for that rename that are relevant; we can merge that commit fine without knowing the rename. But since the cached renames are added to the normal renames, when we go to process it and find that B is not part of opt->priv->paths, we hit the assertion error
process_renames: Assertion newinfo && ~newinfo->merged.clean failed.
I think we could fix this at the beginning of detect_regular_renames() by pruning from cached_pairs any entry whose destination isn't in opt->priv->paths, but it's suboptimal in that we'd kind of like the cached_pair to be restored afterwards so that it can help the subsequent commit, but more importantly since it sits at the intersection of the caching renames optimization and the relevant renames optimization, and the trivial directory resolution optimization, and I don't currently have Documentation/technical/remembering-renames.txt fully paged in, I'm not sure if that's a full solution or a bandaid for the current testcase. However, since the remembering renames optimization was the weakest of the set, and the optimization is far less important when directory rename detection is off (as that implies far fewer potential renames), let's just use a bigger hammer to ensure this special case is
fixed: turn off the rename caching. We do the same thing already when we encounter rename/rename(1to1) cases (as per git grep -3 disabling.the.optimization, though it uses a slightly different triggering mechanism since it's trying to affect the next time that merge_check_renames_reusable() is called), and I think it makes sense to do the same here.

---
 merge-ort.c              | 31 +++++++++++++++++++++++++++++--
 t/t3650-replay-basics.sh |  2 +-
 2 files changed, 30 insertions(+), 3 deletions(-)

index 1d3b690224e..785e5c6f24a 100644
@@ -3404,6 +3404,11 @@ static int collect_renames(struct merge_options *opt,
 			pool_diff_free_filepair(&opt->priv->pool, p);
 			continue;
 		}
+		if (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_NONE &&
+		    p->status == 'R' && 1) {
+			possibly_cache_new_pair(renames, p, side_index, NULL);
+			goto skip_directory_renames;
+		}
 
 		new_path = check_for_directory_rename(opt, p->two->path,
 						      side_index,

@@ -3421,6 +3426,7 @@ static int collect_renames(struct merge_options *opt,
 		if (new_path)
 			apply_directory_rename_modifications(opt, p, new_path);
 
+skip_directory_renames:
 		/*
 		 * p->score comes back from diffcore_rename_extended() with
 		 * the similarity of the renamed file.  The similarity is

@@ -5025,7 +5031,8 @@ static void merge_start(struct merge_options *opt, struct merge_result *result)
 	trace2_region_leave("merge", "allocate/init", opt->repo);
 }
 
-static void merge_check_renames_reusable(struct merge_result *result,
+static void merge_check_renames_reusable(struct merge_options *opt,
+					 struct merge_result *result,
 					 struct tree *merge_base,
 					 struct tree *side1,
 					 struct tree *side2)

@@ -5050,6 +5057,26 @@ static void merge_check_renames_reusable(struct merge_result *result,
 		return;
 	}
 
+	/*
+	 * Avoid using cached renames when directory rename detection is
+	 * turned off.  Cached renames are far less important in that case,
+	 * and they lead to testcases with an interesting intersection of
+	 * effects from relevant renames optimization, trivial directory
+	 * resolution optimization, and cached renames all converging when
+	 * the target of a cached rename is in a directory that
+	 * collect_merge_info() does not recurse into.  To avoid such
+	 * problems, simply disable cached renames for this case (similar
+	 * to the rename/rename(1to1) case; see the "disabling the
+	 * optimization" comment near that case).
+	 *
+	 * This could be revisited in the future; see the commit message
+	 * where this comment was added for some possible pointers.
+	 */
+	if (opt->detect_directory_renames == MERGE_DIRECTORY_RENAMES_NONE) {
+		renames->cached_pairs_valid_side = 0; /* neither side valid */
+		return;
+	}
+
 	/*
 	 * Handle other cases; note that merge_trees[0..2] will only
 	 * be NULL if opti is, or if all three were manually set to

@@ -5258,7 +5285,7 @@ void merge_incore_nonrecursive(struct merge_options *opt,
 
 	trace2_region_enter("merge", "merge_start", opt->repo);
 	assert(opt->ancestor != NULL);
-	merge_check_renames_reusable(result, merge_base, side1, side2);
+	merge_check_renames_reusable(opt, result, merge_base, side1, side2);
 	merge_start(opt, result);
 	/*
 	 * Record the trees used in this merge, so if there's a next merge in

index cade7930765..58b37599357 100755
@@ -195,7 +195,7 @@ test_expect_success 'using replay on bare repo to rebase multiple divergent bran
 	done
 '
 
-test_expect_failure 'merge.directoryRenames=false' '
+test_expect_success 'merge.directoryRenames=false' '
 	# create a test case that stress-tests the rename caching
 	git switch -c rename-onto &&
 

gitgitgadget

From: Elijah Newren <[email protected]>

Switch from merge-recursive to merge-ort. Adjust the following testcases due to the switch:

* t4151: This test left an untracked file in the way of the merge. merge-recursive could only sometimes tell when untracked files were in the way, and by the time it discovers others, it has already made too many changes to back out of the merge. So, instead of writing the results to e.g. 'file1' it would instead write them to 'file1~branch1'. This is confusing for users, because they might not notice 'file1~branch1' and accidentally add and commit 'file1'. In contrast, merge-ort correctly notices the file in the way before making any changes and aborts. Since this test didn't care about the file in the way, just remove it before calling git-am.

* t4255: Usage of merge-ort allows us to change two known failures into successes.

* t6427: As noted a few commits ago, the choice of conflict label for diff3 markers for the ancestor commit was previously handled by merge-recursive.c rather than by callers. Since that has now changed, git am needs to specify that label. Although the previous conflict label ("constructed merge base") was already fairly somewhat slanted towards git am, let's use wording more along the lines of the related command-line flag from git apply and function involved to tie it more closely to git am.

---
 builtin/am.c                      | 5 +++--
 t/t4151-am-abort.sh               | 2 +-
 t/t4255-am-submodule.sh           | 1 -
 t/t6427-diff3-conflict-markers.sh | 2 +-
 4 files changed, 5 insertions(+), 5 deletions(-)

index 2921bb89ef1..3b61bd4c333 100644
@@ -31,7 +31,7 @@
 #include "preload-index.h"
 #include "sequencer.h"
 #include "revision.h"
-#include "merge-recursive.h"
+#include "merge-ort-wrappers.h"
 #include "log-tree.h"
 #include "notes-utils.h"
 #include "rerere.h"

@@ -1638,12 +1638,13 @@ static int fall_back_threeway(const struct am_state *state, const char *index_pa
 	o.branch1 = "HEAD";
 	their_tree_name = xstrfmt("%.*s", linelen(state->msg), state->msg);
 	o.branch2 = their_tree_name;
+	o.ancestor = "constructed fake ancestor";
 	o.detect_directory_renames = MERGE_DIRECTORY_RENAMES_NONE;
 
 	if (state->quiet)
 		o.verbosity = 0;
 
-	if (merge_recursive_generic(&o, &our_tree, &their_tree, 1, bases, &result)) {
+	if (merge_ort_generic(&o, &our_tree, &their_tree, 1, bases, &result)) {
 		repo_rerere(the_repository, state->allow_rerere_autoupdate);
 		free(their_tree_name);
 		return error(_("Failed to merge in the changes."));

index edb38da7010..8e1ecf8a685 100755
@@ -112,7 +112,7 @@ test_expect_success 'am --abort will keep dirty index intact' '
 test_expect_success 'am -3 stops on conflict on unborn branch' '
 	git checkout -f --orphan orphan &&
 	git reset &&
-	rm -f otherfile-4 &&
+	rm -f file-1 otherfile-4 &&
 	test_must_fail git am -3 0003-*.patch &&
 	test 2 -eq $(git ls-files -u | wc -l) &&
 	test 4 = "$(cat otherfile-4)"

index a7ba08f728c..e6679a01b44 100755
@@ -19,7 +19,6 @@ am_3way () {
 	$2 git am --3way patch
 }
 
-KNOWN_FAILURE_NOFF_MERGE_ATTEMPTS_TO_MERGE_REMOVED_SUBMODULE_FILES=1
 test_submodule_switch_func "am_3way"
 
 test_expect_success 'setup diff.submodule' '

index dd5fe6a4021..57569c4f4bd 100755
@@ -207,7 +207,7 @@ test_expect_success 'rebase --apply describes fake ancestor base' '
 		cd rebase &&
 		git rebase --abort &&
 		test_must_fail git -c merge.conflictstyle=diff3 rebase --apply main &&
-		grep "||||||| constructed merge base" file
+		grep "||||||| constructed fake ancestor" file
 	)
 '
 

gitgitgadget

Yes, I think it was a series of hysterical raisins. The original PR merge test at GitHub was done using a shell script around git-merge-file (because git-merge insisted on a working tree). And naturally that did not support renames. (I think I probably wrote that script, but it's so long ago I could be wrong, and I don't have access to the repo anymore).

And then we switched from that to libgit2, after Ed Thomson implemented merge support there (mostly for performance). And the decision was made to disable renames there at first, to confirm that it otherwise performed identically to the existing shell script (to confirm the results, but also because it was unclear if rename detection for automated merges would always produce what the user wanted, or have bad corner cases). So it was mostly temporary, with the idea that somebody would explore turning it on later. But I don't think that ever happened. Those with access to the correct repositories can probably find the arguments in the issue tracker. ;)

I don't think I was around for switching from libgit2 to merge-tree, but I'd guess the same "only change one thing at a time" logic applied.

So yes, mostly temporary-but-never-revisited, with a dash of conservatism.

I don't have any real opinion on what should happen in the future, except that renames on GitHub are probably reasonable, and having an option to disable renames for everyone is probably also a reasonable feature. ;)

-Peff

This is already marked as ready to merge to 'next' in the last WC, but I took a look at the range-diff and everything LGTM:

Thanks,
Taylor