Beginning of new merge strategy: New API, empty implementation

In this series, I try to show the new merge API I have developed in merge-ort and show how it differs from that provided by merge-recursive. I do this in four steps, each corresponding to a patch:

* Provide the new merge-ort.h header file and an empty die-immediately implementation
* Provide new merge-ort-wrappers.[ch] files, showing how to implement the old API using the new API. The wrappers make it easy to convert existing callsites, too.
* Provide a demonstration of the flexibility of the new API and its separation of merging steps and updating the index/worktree steps, with a "fast-rebase". [Doesn't yet function since merge-ort.c is still an empty die-immediately implementation]
* Provide the changes to merge, rebase, revert, and cherry-pick so that with an environment variable or config option the new or old backend can be called.

My next patch series will focus on testsuite changes needed to simultaneously support both merge backends, keyed off an environment variable (thus related to and building on patch 4). Let me know if I'm submitting series too close together or otherwise need to tweak how I'm sending these out...

Elijah Newren (4):
merge-ort: barebones API of new merge strategy with empty
implementation
merge-ort-wrappers: new convience wrappers to mimic the old merge API
fast-rebase: demonstrate merge-ort's API via temporary/hidden command merge,rebase,revert: select ort or recursive by config or environment

 Makefile              |   3 +
 builtin.h             |   1 +
 builtin/fast-rebase.c | 210 ++++++++++++++++++++++++++++++++++++++++++
 builtin/merge.c       |  26 +++++-
 builtin/rebase.c      |   9 +-
 builtin/revert.c      |   2 +
 git.c                 |   1 +
 merge-ort-wrappers.c  |  62 +++++++++++++
 merge-ort-wrappers.h  |  25 +++++
 merge-ort.c           |  52 +++++++++++
 merge-ort.h           |  49 ++++++++++
 sequencer.c           |  71 +++++++++++---
 12 files changed, 496 insertions(+), 15 deletions(-)
 create mode 100644 builtin/fast-rebase.c
 create mode 100644 merge-ort-wrappers.c
 create mode 100644 merge-ort-wrappers.h
 create mode 100644 merge-ort.c
 create mode 100644 merge-ort.h

base-commit: 69986e19ffcfb9af674ae5180689ab7bbf92ed28
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-895%2Fnewren%2Fort-api-with-empty-implementation-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-895/newren/ort-api-with-empty-implementation-v1
Pull-Request: https://github.com/git/git/pull/895

gitgitgadget

From: Elijah Newren <[email protected]>

This is the beginning of a new merge strategy. While there are some API differences, and the implementation has some differences in behavior, it is essentially meant as an eventual drop-in replacement for merge-recursive.c. However, it is being built to exist side-by-side with merge-recursive so that we have plenty of time to find out how those differences pan out in the real world while people can still fall back to merge-recursive. (Also, I intend to avoid modifying merge-recursive during this process, to keep it stable.)

The primary difference noticable here is that the updating of the working tree and index is not done simultaneously with the merge algorithm, but is a separate post-processing step. The new API is designed so that one can do repeated merges (e.g. during a rebase or cherry-pick) and only update the index and working tree one time at the end instead of updating it with every intermediate result. Also, one can perform a merge between two branches, neither of which match the index or the working tree, without clobbering the index or working tree.

---
 Makefile    |  1 +
 merge-ort.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 merge-ort.h | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 102 insertions(+)
 create mode 100644 merge-ort.c
 create mode 100644 merge-ort.h

index 95571ee3fc..088770c2ae 100644
@@ -921,6 +921,7 @@ LIB_OBJS += mailmap.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += mem-pool.o
 LIB_OBJS += merge-blobs.o
+LIB_OBJS += merge-ort.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += merge.o
 LIB_OBJS += mergesort.o

gitgitgadget

Thanks,
Taylor

The remainder of this series, all 3 patches, are solely about this. I think smashing all four patches into one would just make it too large, and obscure the different types of usage.

I could do that, however. (Though it'd be THE_NEXT_THREE_PATCHES, rather than just FILE_MODIFIED_BY_NEXT_PATCH)

I don't have such a thing. Since there are basically just two functions that callers would be calling (one of either the recursive or nonrecursive variants, plus one of either merge_finalize() or merge_switch_to_result()), it didn't occur to me to write anything like that up. I had thought about documenting the implementation strategy and performance strategies and whatnot, but haven't yet done that either (other than my talk at Git Merge 2020, of course). If the API usage is confusing, I can add that, though if calling two functions is confusing, there might be something wrong with the two functions.

Yeah, this one is a little weird. It technically could be dropped, but is there solely to help catch API mis-use; most of the API is relatively obvious but there's one gotcha...

The merge_inmemory_*recursive() functions accept both a struct merge_options and a struct merge_result. merge_result is _mostly_ an output so people might omit zeroing it out beforehand, but the merge_result can be re-used between multiple calls when cherry-picking or rebasing a sequence of commits. When it is re-used in such a manner, it enables some performance optimizations (information computed in a picking a previous commit need not be recomputed). However, that raises a sticky question: how can you tell the difference between result->priv being reused, vs. being nonzero just because it's uninitialized garbage? If it's the latter, looking into result->priv might give you a segfault or at least nonsensical results that take a while to debug. The simple way I avoided this problem for callers is that I expect result->_ to either be 0 or have a special value, and if it doesn't have one of those two values, then I BUG(). At the end of a merge, I set result->_ to that special value. The special value is not exported and is only known within merge-ort.c.

You could get away without this _ member and just let valgrind or segfaults catch the accidental use of uninitialized values, but since result looks and feels like an output-only variable it was something that was easy to misuse and I wanted an extra helping guardrail to make that kind of debugging loop be shorter.

I guess if I were to rename it, I would call it 'initialized' or "carry_over" or something. It's really just a boolean variable rather than a set of flags, but an actual boolean bit that is uninitialized provides ~0% confidence in knowing whether the struct really is initialized or not, while an unsigned has enough bits of safety that an uninitialized value is cosmically unlikely to match my special 'RESULT_INITIALIZED' value.

With this field, the one gotcha is basically trivial to debug; without it, it takes a bit more effort. If I were to remove this extra field, then it'd make more sense to write up more documentation about API usage.

Yes, it'd make the API slightly less self-documenting, but would be more flexible for adding additional flags in the future. I had thought about that earlier, but I really just don't see what other flags could possibly be added. Maybe when I resume working on evil-(merge/revert/cherry-pick) detection I'll have a better feel for that, but I had just leaned towards leaving it as these two flags for now.

Am Do., 22. Okt. 2020 um 03:28 Uhr schrieb Elijah Newren via GitGitGadget <[email protected]>:
[... snipping a lot of unneeded context ...]

                                                                   ^^^^^^^^^^^^^

                                           ^^^^^^^^^

                                                                  ^^^^^^^^^^^^^

                                            ^^^^^^^^^^^^

Whoops, indeed. Will fix; thanks for spotting.

From: Elijah Newren <[email protected]>

There are a few differences between the new API in merge-ort and the old API in merge-recursive. While the new API is more flexible, it might feel like more work at times than the old API. merge-ort-wrappers creates two convenience wrappers taking the exact same arguments as the old merge_trees() and merge_recursive() functions and implements them via the new API. This makes converting existing callsites easier, and serves to highlight some of the differences in the API.

---
 Makefile             |  1 +
 merge-ort-wrappers.c | 62 ++++++++++++++++++++++++++++++++++++++++++++
 merge-ort-wrappers.h | 25 ++++++++++++++++++
 3 files changed, 88 insertions(+)
 create mode 100644 merge-ort-wrappers.c
 create mode 100644 merge-ort-wrappers.h

index 088770c2ae..382fe73c76 100644
@@ -922,6 +922,7 @@ LIB_OBJS += match-trees.o
 LIB_OBJS += mem-pool.o
 LIB_OBJS += merge-blobs.o
 LIB_OBJS += merge-ort.o
+LIB_OBJS += merge-ort-wrappers.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += merge.o
 LIB_OBJS += mergesort.o

new file mode 100644
index 0000000000..0c4c57adbb
@@ -0,0 +1,25 @@
+#ifndef MERGE_ORT_WRAPPERS_H
+#define MERGE_ORT_WRAPPERS_H
+
+#include "merge-recursive.h"
+
+/*
+ * rename-detecting three-way merge, no recursion.
+ * Wrapper mimicking the old merge_trees() function.
+ */
+int merge_ort_nonrecursive(struct merge_options *opt,
+			   struct tree *head,
+			   struct tree *merge,
+			   struct tree *common);
+
+/*
+ * rename-detecting three-way merge with recursive ancestor consolidation.
+ * Wrapper mimicking the old merge_recursive() function.
+ */
+int merge_ort_recursive(struct merge_options *opt,
+			struct commit *h1,
+			struct commit *h2,
+			struct commit_list *ancestors,
+			struct commit **result);
+
+#endif

gitgitgadget

From: Elijah Newren <[email protected]>

Add a special built-in that is only of use to git-developers and only during the development of merge-ort, and which is designed to immediately fail and print:
git: 'fast-rebase' is not a git command
unless a special GIT_TEST_MERGE_ALGORITHM environment variable is set.

This special builtin serves two purposes:

1) Demonstrate the desired API of merge-ort. In particular, fast-rebase takes advantage of the separation of the merging operation from the updating of the index and working tree, to allow it to pick N commits, but only update the index and working tree once at the end. Look for the calls to merge_inmemory_nonrecursive() and merge_switch_to_result().

2) Provide a convenient benchmark that isn't polluted by the heavy disk writing and forking of unnecessary processes that comes from sequencer.c and merge-recursive.c. fast-rebase is not meant to replace sequencer.c, just give ideas on how sequencer.c can be changed. Updating sequencer.c with these goals is probably a large amount of work; writing a simple targeted command with no documentation, less-than-useful help messages, numerous limitations in terms of flags it can accept and situations it can handle, and which is flagged off from users is a much easier interim step.

---
 Makefile              |   1 +
 builtin.h             |   1 +
 builtin/fast-rebase.c | 210 ++++++++++++++++++++++++++++++++++++++++++
 git.c                 |   1 +
 4 files changed, 213 insertions(+)
 create mode 100644 builtin/fast-rebase.c

index 382fe73c76..1b40d780fa 100644
@@ -1087,6 +1087,7 @@ BUILTIN_OBJS += builtin/difftool.o
 BUILTIN_OBJS += builtin/env--helper.o
 BUILTIN_OBJS += builtin/fast-export.o
 BUILTIN_OBJS += builtin/fast-import.o
+BUILTIN_OBJS += builtin/fast-rebase.o
 BUILTIN_OBJS += builtin/fetch-pack.o
 BUILTIN_OBJS += builtin/fetch.o
 BUILTIN_OBJS += builtin/fmt-merge-msg.o

index 53fb290963..75ff7dc8a9 100644
@@ -151,6 +151,7 @@ int cmd_difftool(int argc, const char **argv, const char *prefix);
 int cmd_env__helper(int argc, const char **argv, const char *prefix);
 int cmd_fast_export(int argc, const char **argv, const char *prefix);
 int cmd_fast_import(int argc, const char **argv, const char *prefix);
+int cmd_fast_rebase(int argc, const char **argv, const char *prefix);
 int cmd_fetch(int argc, const char **argv, const char *prefix);
 int cmd_fetch_pack(int argc, const char **argv, const char *prefix);
 int cmd_fmt_merge_msg(int argc, const char **argv, const char *prefix);

index 4bdcdad2cc..af84f11e69 100644
@@ -512,6 +512,7 @@ static struct cmd_struct commands[] = {
 	{ "env--helper", cmd_env__helper },
 	{ "fast-export", cmd_fast_export, RUN_SETUP },
 	{ "fast-import", cmd_fast_import, RUN_SETUP | NO_PARSEOPT },
+	{ "fast-rebase", cmd_fast_rebase, RUN_SETUP /* | NEED_WORK_TREE */ },
 	{ "fetch", cmd_fetch, RUN_SETUP },
 	{ "fetch-pack", cmd_fetch_pack, RUN_SETUP | NO_PARSEOPT },
 	{ "fmt-merge-msg", cmd_fmt_merge_msg, RUN_SETUP },

gitgitgadget

From: Elijah Newren <[email protected]>

Allow the testsuite to run where it treats requests for "recursive" or the default merge algorithm via consulting the environment variable GIT_TEST_MERGE_ALGORITHM which is expected to either be "recursive" (the old traditional algorithm) or "ort" (the new algorithm).

Also, allow folks to pick the new algorithm via config setting. It turns out builtin/merge.c already had a way to allow users to specify a different default merge algorithm: pull.twohead. Rather odd configuration name (especially to be in the 'pull' namespace rather than 'merge') but it's there. Add that same configuration to rebase, cherry-pick, and revert.

This required updating the various callsites that called merge_trees() or merge_recursive() to conditionally call the new API, so this serves as another demonstration of what the new API looks and feels like. There are almost certainly some callsites that have not yet been modified to work with the new merge algorithm, but this represents the ones that I have been testing with thus far.

---
 builtin/merge.c  | 26 ++++++++++++++++--
 builtin/rebase.c |  9 +++++-
 builtin/revert.c |  2 ++
 sequencer.c      | 71 ++++++++++++++++++++++++++++++++++++++++--------
 4 files changed, 93 insertions(+), 15 deletions(-)

index 9d5359edc2..87dfc9bc06 100644
@@ -28,6 +28,7 @@
 #include "rerere.h"
 #include "help.h"
 #include "merge-recursive.h"
+#include "merge-ort-wrappers.h"
 #include "resolve-undo.h"
 #include "remote.h"
 #include "fmt-merge-msg.h"

@@ -88,6 +89,7 @@ static int no_verify;
 static struct strategy all_strategy[] = {
 	{ "recursive",  DEFAULT_TWOHEAD | NO_TRIVIAL },
 	{ "octopus",    DEFAULT_OCTOPUS },
+	{ "ort",        NO_TRIVIAL },
 	{ "resolve",    0 },
 	{ "ours",       NO_FAST_FORWARD | NO_TRIVIAL },
 	{ "subtree",    NO_FAST_FORWARD | NO_TRIVIAL },

@@ -159,10 +161,17 @@ static struct strategy *get_strategy(const char *name)
 	struct strategy *ret;
 	static struct cmdnames main_cmds, other_cmds;
 	static int loaded;
+	char *default_strategy = getenv("GIT_TEST_MERGE_ALGORITHM");
 
 	if (!name)
 		return NULL;
 
+	if (default_strategy &&
+	    !strcmp(default_strategy, "ort") &&
+	    !strcmp(name, "recursive")) {
+		name = "ort";
+	}
+
 	for (i = 0; i < ARRAY_SIZE(all_strategy); i++)
 		if (!strcmp(name, all_strategy[i].name))
 			return &all_strategy[i];

@@ -701,7 +710,8 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
 	if (refresh_and_write_cache(REFRESH_QUIET, SKIP_IF_UNCHANGED, 0) < 0)
 		return error(_("Unable to write index."));
 
-	if (!strcmp(strategy, "recursive") || !strcmp(strategy, "subtree")) {
+	if (!strcmp(strategy, "recursive") || !strcmp(strategy, "subtree") ||
+	    !strcmp(strategy, "ort")) {
 		struct lock_file lock = LOCK_INIT;
 		int clean, x;
 		struct commit *result;

@@ -732,8 +742,12 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
 			commit_list_insert(j->item, &reversed);
 
 		hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
-		clean = merge_recursive(&o, head,
-				remoteheads->item, reversed, &result);
+		if (!strcmp(strategy, "ort"))
+			clean = merge_ort_recursive(&o, head, remoteheads->item,
+						    reversed, &result);
+		else
+			clean = merge_recursive(&o, head, remoteheads->item,
+						reversed, &result);
 		if (clean < 0)
 			exit(128);
 		if (write_locked_index(&the_index, &lock,

@@ -1264,6 +1278,12 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 	if (branch)
 		skip_prefix(branch, "refs/heads/", &branch);
 
+	if (!pull_twohead) {
+		char *default_strategy = getenv("GIT_TEST_MERGE_ALGORITHM");
+		if (default_strategy && !strcmp(default_strategy, "ort"))
+			pull_twohead = "ort";
+	}
+
 	init_diff_ui_defaults();
 	git_config(git_merge_config, NULL);
 

index eeca53382f..9719aa25da 100644
@@ -119,6 +119,7 @@ static struct replay_opts get_replay_opts(const struct rebase_options *opts)
 	struct replay_opts replay = REPLAY_OPTS_INIT;
 
 	replay.action = REPLAY_INTERACTIVE_REBASE;
+	replay.strategy = NULL;
 	sequencer_init_config(&replay);
 
 	replay.signoff = opts->signoff;

@@ -136,7 +137,8 @@ static struct replay_opts get_replay_opts(const struct rebase_options *opts)
 					opts->committer_date_is_author_date;
 	replay.ignore_date = opts->ignore_date;
 	replay.gpg_sign = xstrdup_or_null(opts->gpg_sign_opt);
-	replay.strategy = opts->strategy;
+	if (opts->strategy)
+		replay.strategy = opts->strategy;
 
 	if (opts->strategy_opts)
 		parse_strategy_opts(&replay, opts->strategy_opts);

@@ -1771,6 +1773,11 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
 			    options.default_backend);
 	}
 
+	if (options.type == REBASE_MERGE &&
+	    !options.strategy &&
+	    getenv("GIT_TEST_MERGE_ALGORITHM"))
+		options.strategy = xstrdup(getenv("GIT_TEST_MERGE_ALGORITHM"));
+
 	switch (options.type) {
 	case REBASE_MERGE:
 	case REBASE_PRESERVE_MERGES:

index f61cc5d82c..c7cb0c1a18 100644
@@ -202,6 +202,8 @@ static int run_sequencer(int argc, const char **argv, struct replay_opts *opts)
 	/* These option values will be free()d */
 	opts->gpg_sign = xstrdup_or_null(opts->gpg_sign);
 	opts->strategy = xstrdup_or_null(opts->strategy);
+	if (!opts->strategy && getenv("GIT_TEST_MERGE_ALGORITHM"))
+		opts->strategy = xstrdup(getenv("GIT_TEST_MERGE_ALGORITHM"));
 
 	if (cmd == 'q') {
 		int ret = sequencer_remove_state(opts);

gitgitgadget

Hi,

I should probably call out that even if folks don't have time to review patches, I'm particularly interested in opinions on the following two questions:
* Are the "pull.twohead" and "GIT_TEST_MERGE_ALGORITHM" names in
patch 4 good/bad/ugly? (especially the mapping from "pull" to revert, cherry-pick, rebase, and merge?)
* Is it too weird to have a temporary/hidden builtin, in patch 3?
If so, what is a good alternative?

Thanks,
Elijah

I think GIT_TEST_MERGE_ALGORITHM is fine. I think extending "pull.twohead" is ugly - perhaps we could get away with not doing anything about it for now, and once this feature is ready, we could add a new config parameter specially for this.

An alternative is to implement it as part of test-tool - see t/helper/ for more information.

I'm not very familiar with the merge code, but overall this looks like a good, clear design. Thanks especially for showing how this code can be used (in patch 3) and a comparison to the old API (in patch 2).

Yeah, it is kinda ugly. I was thinking of adding "merge.backend" when I discovered that "pull.twohead" already existed. I didn't know if two configuration knobs doing the same thing was uglier, or using that old ugly misnomer was. Maybe we can use the merge.backend name or something like it once merge-ort is further along.

Oh, interesting idea; I hadn't thought of that. However, It seems like a bit of a misfit there too -- fast-rebase isn't used in the testsuite anywhere and I didn't have plans to add it. My plan was for fast-rebase to go away soon (perhaps as soon as the merge-ort implementation lands), probably long before merge-recursive.c goes away. fast-rebase exists just to (1) demonstrate the API and (2) demonstrate some performance benchmarks I used to guide my performance decisions. Once merge-ort has fully landed, reason (2) becomes obsolete. Reason (1) might still exist in part, but hopefully we can start updating sequencer.c to use those ideas and then make fast-rebase fully obsolete.

Thanks for taking a look. :-)

In this series, I try to show the new merge API I have developed in merge-ort and show how it differs from that provided by merge-recursive. I do this in four steps, each corresponding to a patch.

Changes since v1 (thanks to Taylor and Peter for the suggestions in their reviews):

* Point out in the first commit message that the next three patches will be providing example usage of the new API.
* Rename a variable away from '_' in a way that continues the "private" theme.
* Unswap function comments that were placed next to the wrong functions.

Elijah Newren (4):
merge-ort: barebones API of new merge strategy with empty
implementation
merge-ort-wrappers: new convience wrappers to mimic the old merge API
fast-rebase: demonstrate merge-ort's API via temporary/hidden command merge,rebase,revert: select ort or recursive by config or environment

 Makefile              |   3 +
 builtin.h             |   1 +
 builtin/fast-rebase.c | 210 ++++++++++++++++++++++++++++++++++++++++++
 builtin/merge.c       |  26 +++++-
 builtin/rebase.c      |   9 +-
 builtin/revert.c      |   2 +
 git.c                 |   1 +
 merge-ort-wrappers.c  |  62 +++++++++++++
 merge-ort-wrappers.h  |  25 +++++
 merge-ort.c           |  52 +++++++++++
 merge-ort.h           |  49 ++++++++++
 sequencer.c           |  71 +++++++++++---
 12 files changed, 496 insertions(+), 15 deletions(-)
 create mode 100644 builtin/fast-rebase.c
 create mode 100644 merge-ort-wrappers.c
 create mode 100644 merge-ort-wrappers.h
 create mode 100644 merge-ort.c
 create mode 100644 merge-ort.h

base-commit: 69986e19ffcfb9af674ae5180689ab7bbf92ed28
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-895%2Fnewren%2Fort-api-with-empty-implementation-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-895/newren/ort-api-with-empty-implementation-v2
Pull-Request: https://github.com/git/git/pull/895

Range-diff vs v1:

1: 54ef18182c ! 1: b9e73975ea merge-ort: barebones API of new merge strategy with empty implementation
@@ Commit message
can perform a merge between two branches, neither of which match the
index or the working tree, without clobbering the index or working tree.

+ The next three commits will demonstrate various uses of this new API.
+

## Makefile ##
@@ merge-ort.h (new)
+
+ /*
+ * Additional metadata used by merge_switch_to_result() or future calls
-+ * to merge_inmemory_*().
++ * to merge_inmemory_*(). Not for external use.
+ */
-+ unsigned _;
+ void *priv;
++ unsigned ate;
+};
+
-+/* rename-detecting three-way merge, no recursion. */
++/* rename-detecting three-way merge with recursive ancestor consolidation. */
+void merge_inmemory_recursive(struct merge_options *opt,
+ struct commit_list *merge_bases,
+ struct commit *side1,
+ struct commit *side2,
+ struct merge_result *result);
+
-+/* rename-detecting three-way merge with recursive ancestor consolidation. */ ++/* rename-detecting three-way merge, no recursion. */
+void merge_inmemory_nonrecursive(struct merge_options *opt,
+ struct tree *merge_base,
+ struct tree *side1,

 2:  f597609b88 = 2:  a9fff811a2 merge-ort-wrappers: new convience wrappers to mimic the old merge API
 3:  a1357fb3b3 = 3:  f38d140c15 fast-rebase: demonstrate merge-ort's API via temporary/hidden command
 4:  06ecea215f = 4:  5f6c97b889 merge,rebase,revert: select ort or recursive by config or environment

gitgitgadget

From: Elijah Newren <[email protected]>

This is the beginning of a new merge strategy. While there are some API differences, and the implementation has some differences in behavior, it is essentially meant as an eventual drop-in replacement for merge-recursive.c. However, it is being built to exist side-by-side with merge-recursive so that we have plenty of time to find out how those differences pan out in the real world while people can still fall back to merge-recursive. (Also, I intend to avoid modifying merge-recursive during this process, to keep it stable.)

The primary difference noticable here is that the updating of the working tree and index is not done simultaneously with the merge algorithm, but is a separate post-processing step. The new API is designed so that one can do repeated merges (e.g. during a rebase or cherry-pick) and only update the index and working tree one time at the end instead of updating it with every intermediate result. Also, one can perform a merge between two branches, neither of which match the index or the working tree, without clobbering the index or working tree.

The next three commits will demonstrate various uses of this new API.

---
 Makefile    |  1 +
 merge-ort.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 merge-ort.h | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 102 insertions(+)
 create mode 100644 merge-ort.c
 create mode 100644 merge-ort.h

index 95571ee3fc..088770c2ae 100644
@@ -921,6 +921,7 @@ LIB_OBJS += mailmap.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += mem-pool.o
 LIB_OBJS += merge-blobs.o
+LIB_OBJS += merge-ort.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += merge.o
 LIB_OBJS += mergesort.o

gitgitgadget

One thing that is quite unpleasant is "git grep ort" gives us too many hits already, and it will be hard to locate ort related changes with "git log --grep=ort", as the name is too short to serve as an effective way to limit the search.

Suggestions for an alternative name? merge-pandemic.c since it was mostly written during the pandemic?

I'm really not good at naming things...

This is something merge-recursive already does (and I've copied some of that code over, around merge_3way() and the call to write_object_file() with the results). I thought the reasoning behind this was memory -- we're okay assuming any given file fits in memory (and perhaps up to three copies of it so we can do a three-way merge), but we're not okay assuming all (changed) files from a commit simultaneously fit in memory.

I thought about that early on, but I was worried about out-of-memory situations if we attempt to do truly in-memory, at least for large changes in large repositories.

And as you have seen above, I do rely on being able to create trees.

I don't understand the union suggestion. Both fields are used.

Would you object if 'ate' was named '_'? That was my original name, but Taylor didn't like it. It is used on about 4 lines of code, I'm 99.9% sure it will never be used in additional locations, and callers shouldn't mess with it. I just don't have a good name for it. I guess maybe I should just call it "properly_initialized" or something.

I can add an underscore. Or switch to incore. Preference?

Yes, your reading is correct. We don't touch the index (or any index, or any cache_entry) at all. Among other things, data that can be used to update the index are in the "priv" field.

I'll try to add some notes to the file.

I thought "priv" shouldn't be "anything goes, so it is 'void *'" but is probably a "union { ... } priv;" with associated enum next to it that tells which one of the possibilities in the union is in effect.

Either is horrible name.

Anything shorter would get my vote.

Sounds good.

I guess I'm still not following where these "possibilities" come from or what I could have said that would have suggested possibilities.

priv is a pointer to a private data structure. The data structure is defined and used only in merge-ort.c and not exposed to callers. That data does need to be passed from merge_incore_*() to merge_switch_to_result() (or to merge_finalize()). Since those two are separate function calls invoked by the caller, and since callers shouldn't touch any of this data in priv, it's passed as an opaque field within merge_result. Thus void*.

I'll just rip it out, for now. It isn't relevant to early versions of merge-ort anyway, and when I re-introduce it with yet another horrible name, there will at least be more context for others to suggest a better name for me.

Besides, the variable isn't at all necessary for the algorithm; it exists solely as a way to catch a small gotcha in API usage of later versions of merge-ort, which I otherwise didn't have a clean way of detecting.

Sounds good, will do.

:-)

From: Elijah Newren <[email protected]>

There are a few differences between the new API in merge-ort and the old API in merge-recursive. While the new API is more flexible, it might feel like more work at times than the old API. merge-ort-wrappers creates two convenience wrappers taking the exact same arguments as the old merge_trees() and merge_recursive() functions and implements them via the new API. This makes converting existing callsites easier, and serves to highlight some of the differences in the API.

---
 Makefile             |  1 +
 merge-ort-wrappers.c | 62 ++++++++++++++++++++++++++++++++++++++++++++
 merge-ort-wrappers.h | 25 ++++++++++++++++++
 3 files changed, 88 insertions(+)
 create mode 100644 merge-ort-wrappers.c
 create mode 100644 merge-ort-wrappers.h

index 088770c2ae..382fe73c76 100644
@@ -922,6 +922,7 @@ LIB_OBJS += match-trees.o
 LIB_OBJS += mem-pool.o
 LIB_OBJS += merge-blobs.o
 LIB_OBJS += merge-ort.o
+LIB_OBJS += merge-ort-wrappers.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += merge.o
 LIB_OBJS += mergesort.o

new file mode 100644
index 0000000000..0c4c57adbb
@@ -0,0 +1,25 @@
+#ifndef MERGE_ORT_WRAPPERS_H
+#define MERGE_ORT_WRAPPERS_H
+
+#include "merge-recursive.h"
+
+/*
+ * rename-detecting three-way merge, no recursion.
+ * Wrapper mimicking the old merge_trees() function.
+ */
+int merge_ort_nonrecursive(struct merge_options *opt,
+			   struct tree *head,
+			   struct tree *merge,
+			   struct tree *common);
+
+/*
+ * rename-detecting three-way merge with recursive ancestor consolidation.
+ * Wrapper mimicking the old merge_recursive() function.
+ */
+int merge_ort_recursive(struct merge_options *opt,
+			struct commit *h1,
+			struct commit *h2,
+			struct commit_list *ancestors,
+			struct commit **result);
+
+#endif

gitgitgadget

From: Elijah Newren <[email protected]>

Add a special built-in that is only of use to git-developers and only during the development of merge-ort, and which is designed to immediately fail and print:
git: 'fast-rebase' is not a git command
unless a special GIT_TEST_MERGE_ALGORITHM environment variable is set.

This special builtin serves two purposes:

1) Demonstrate the desired API of merge-ort. In particular, fast-rebase takes advantage of the separation of the merging operation from the updating of the index and working tree, to allow it to pick N commits, but only update the index and working tree once at the end. Look for the calls to merge_inmemory_nonrecursive() and merge_switch_to_result().

2) Provide a convenient benchmark that isn't polluted by the heavy disk writing and forking of unnecessary processes that comes from sequencer.c and merge-recursive.c. fast-rebase is not meant to replace sequencer.c, just give ideas on how sequencer.c can be changed. Updating sequencer.c with these goals is probably a large amount of work; writing a simple targeted command with no documentation, less-than-useful help messages, numerous limitations in terms of flags it can accept and situations it can handle, and which is flagged off from users is a much easier interim step.

---
 Makefile              |   1 +
 builtin.h             |   1 +
 builtin/fast-rebase.c | 210 ++++++++++++++++++++++++++++++++++++++++++
 git.c                 |   1 +
 4 files changed, 213 insertions(+)
 create mode 100644 builtin/fast-rebase.c

index 382fe73c76..1b40d780fa 100644
@@ -1087,6 +1087,7 @@ BUILTIN_OBJS += builtin/difftool.o
 BUILTIN_OBJS += builtin/env--helper.o
 BUILTIN_OBJS += builtin/fast-export.o
 BUILTIN_OBJS += builtin/fast-import.o
+BUILTIN_OBJS += builtin/fast-rebase.o
 BUILTIN_OBJS += builtin/fetch-pack.o
 BUILTIN_OBJS += builtin/fetch.o
 BUILTIN_OBJS += builtin/fmt-merge-msg.o

index 53fb290963..75ff7dc8a9 100644
@@ -151,6 +151,7 @@ int cmd_difftool(int argc, const char **argv, const char *prefix);
 int cmd_env__helper(int argc, const char **argv, const char *prefix);
 int cmd_fast_export(int argc, const char **argv, const char *prefix);
 int cmd_fast_import(int argc, const char **argv, const char *prefix);
+int cmd_fast_rebase(int argc, const char **argv, const char *prefix);
 int cmd_fetch(int argc, const char **argv, const char *prefix);
 int cmd_fetch_pack(int argc, const char **argv, const char *prefix);
 int cmd_fmt_merge_msg(int argc, const char **argv, const char *prefix);

index 4bdcdad2cc..af84f11e69 100644
@@ -512,6 +512,7 @@ static struct cmd_struct commands[] = {
 	{ "env--helper", cmd_env__helper },
 	{ "fast-export", cmd_fast_export, RUN_SETUP },
 	{ "fast-import", cmd_fast_import, RUN_SETUP | NO_PARSEOPT },
+	{ "fast-rebase", cmd_fast_rebase, RUN_SETUP /* | NEED_WORK_TREE */ },
 	{ "fetch", cmd_fetch, RUN_SETUP },
 	{ "fetch-pack", cmd_fetch_pack, RUN_SETUP | NO_PARSEOPT },
 	{ "fmt-merge-msg", cmd_fmt_merge_msg, RUN_SETUP },

gitgitgadget

From: Elijah Newren <[email protected]>

Allow the testsuite to run where it treats requests for "recursive" or the default merge algorithm via consulting the environment variable GIT_TEST_MERGE_ALGORITHM which is expected to either be "recursive" (the old traditional algorithm) or "ort" (the new algorithm).

Also, allow folks to pick the new algorithm via config setting. It turns out builtin/merge.c already had a way to allow users to specify a different default merge algorithm: pull.twohead. Rather odd configuration name (especially to be in the 'pull' namespace rather than 'merge') but it's there. Add that same configuration to rebase, cherry-pick, and revert.

This required updating the various callsites that called merge_trees() or merge_recursive() to conditionally call the new API, so this serves as another demonstration of what the new API looks and feels like. There are almost certainly some callsites that have not yet been modified to work with the new merge algorithm, but this represents the ones that I have been testing with thus far.

---
 builtin/merge.c  | 26 ++++++++++++++++--
 builtin/rebase.c |  9 +++++-
 builtin/revert.c |  2 ++
 sequencer.c      | 71 ++++++++++++++++++++++++++++++++++++++++--------
 4 files changed, 93 insertions(+), 15 deletions(-)

index 9d5359edc2..87dfc9bc06 100644
@@ -28,6 +28,7 @@
 #include "rerere.h"
 #include "help.h"
 #include "merge-recursive.h"
+#include "merge-ort-wrappers.h"
 #include "resolve-undo.h"
 #include "remote.h"
 #include "fmt-merge-msg.h"

@@ -88,6 +89,7 @@ static int no_verify;
 static struct strategy all_strategy[] = {
 	{ "recursive",  DEFAULT_TWOHEAD | NO_TRIVIAL },
 	{ "octopus",    DEFAULT_OCTOPUS },
+	{ "ort",        NO_TRIVIAL },
 	{ "resolve",    0 },
 	{ "ours",       NO_FAST_FORWARD | NO_TRIVIAL },
 	{ "subtree",    NO_FAST_FORWARD | NO_TRIVIAL },

@@ -159,10 +161,17 @@ static struct strategy *get_strategy(const char *name)
 	struct strategy *ret;
 	static struct cmdnames main_cmds, other_cmds;
 	static int loaded;
+	char *default_strategy = getenv("GIT_TEST_MERGE_ALGORITHM");
 
 	if (!name)
 		return NULL;
 
+	if (default_strategy &&
+	    !strcmp(default_strategy, "ort") &&
+	    !strcmp(name, "recursive")) {
+		name = "ort";
+	}
+
 	for (i = 0; i < ARRAY_SIZE(all_strategy); i++)
 		if (!strcmp(name, all_strategy[i].name))
 			return &all_strategy[i];

@@ -701,7 +710,8 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
 	if (refresh_and_write_cache(REFRESH_QUIET, SKIP_IF_UNCHANGED, 0) < 0)
 		return error(_("Unable to write index."));
 
-	if (!strcmp(strategy, "recursive") || !strcmp(strategy, "subtree")) {
+	if (!strcmp(strategy, "recursive") || !strcmp(strategy, "subtree") ||
+	    !strcmp(strategy, "ort")) {
 		struct lock_file lock = LOCK_INIT;
 		int clean, x;
 		struct commit *result;

@@ -732,8 +742,12 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
 			commit_list_insert(j->item, &reversed);
 
 		hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
-		clean = merge_recursive(&o, head,
-				remoteheads->item, reversed, &result);
+		if (!strcmp(strategy, "ort"))
+			clean = merge_ort_recursive(&o, head, remoteheads->item,
+						    reversed, &result);
+		else
+			clean = merge_recursive(&o, head, remoteheads->item,
+						reversed, &result);
 		if (clean < 0)
 			exit(128);
 		if (write_locked_index(&the_index, &lock,

@@ -1264,6 +1278,12 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 	if (branch)
 		skip_prefix(branch, "refs/heads/", &branch);
 
+	if (!pull_twohead) {
+		char *default_strategy = getenv("GIT_TEST_MERGE_ALGORITHM");
+		if (default_strategy && !strcmp(default_strategy, "ort"))
+			pull_twohead = "ort";
+	}
+
 	init_diff_ui_defaults();
 	git_config(git_merge_config, NULL);
 

index eeca53382f..9719aa25da 100644
@@ -119,6 +119,7 @@ static struct replay_opts get_replay_opts(const struct rebase_options *opts)
 	struct replay_opts replay = REPLAY_OPTS_INIT;
 
 	replay.action = REPLAY_INTERACTIVE_REBASE;
+	replay.strategy = NULL;
 	sequencer_init_config(&replay);
 
 	replay.signoff = opts->signoff;

@@ -136,7 +137,8 @@ static struct replay_opts get_replay_opts(const struct rebase_options *opts)
 					opts->committer_date_is_author_date;
 	replay.ignore_date = opts->ignore_date;
 	replay.gpg_sign = xstrdup_or_null(opts->gpg_sign_opt);
-	replay.strategy = opts->strategy;
+	if (opts->strategy)
+		replay.strategy = opts->strategy;
 
 	if (opts->strategy_opts)
 		parse_strategy_opts(&replay, opts->strategy_opts);

@@ -1771,6 +1773,11 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
 			    options.default_backend);
 	}
 
+	if (options.type == REBASE_MERGE &&
+	    !options.strategy &&
+	    getenv("GIT_TEST_MERGE_ALGORITHM"))
+		options.strategy = xstrdup(getenv("GIT_TEST_MERGE_ALGORITHM"));
+
 	switch (options.type) {
 	case REBASE_MERGE:
 	case REBASE_PRESERVE_MERGES:

index f61cc5d82c..c7cb0c1a18 100644
@@ -202,6 +202,8 @@ static int run_sequencer(int argc, const char **argv, struct replay_opts *opts)
 	/* These option values will be free()d */
 	opts->gpg_sign = xstrdup_or_null(opts->gpg_sign);
 	opts->strategy = xstrdup_or_null(opts->strategy);
+	if (!opts->strategy && getenv("GIT_TEST_MERGE_ALGORITHM"))
+		opts->strategy = xstrdup(getenv("GIT_TEST_MERGE_ALGORITHM"));
 
 	if (cmd == 'q') {
 		int ret = sequencer_remove_state(opts);

gitgitgadget

In this series, I show the new merge API I have developed in merge-ort, and show how it differs from that provided by merge-recursive. I do this in four steps, each corresponding to a patch.

Changes since v2:

* Extended comments in struct merge_result and in front of function definitions to make API usage clearer; in particular, noting how this merge backend differs in not using the index (and only updating it as part of merge_switch_to_result()).
* Drop the other private field of struct merge_result, for now.
* Rename merge_inmemory_* to merge_incore_*

Elijah Newren (4):
merge-ort: barebones API of new merge strategy with empty
implementation
merge-ort-wrappers: new convience wrappers to mimic the old merge API
fast-rebase: demonstrate merge-ort's API via temporary/hidden command merge,rebase,revert: select ort or recursive by config or environment

 Makefile              |   3 +
 builtin.h             |   1 +
 builtin/fast-rebase.c | 210 ++++++++++++++++++++++++++++++++++++++++++
 builtin/merge.c       |  26 +++++-
 builtin/rebase.c      |   9 +-
 builtin/revert.c      |   2 +
 git.c                 |   1 +
 merge-ort-wrappers.c  |  62 +++++++++++++
 merge-ort-wrappers.h  |  25 +++++
 merge-ort.c           |  52 +++++++++++
 merge-ort.h           |  58 ++++++++++++
 sequencer.c           |  71 +++++++++++---
 12 files changed, 505 insertions(+), 15 deletions(-)
 create mode 100644 builtin/fast-rebase.c
 create mode 100644 merge-ort-wrappers.c
 create mode 100644 merge-ort-wrappers.h
 create mode 100644 merge-ort.c
 create mode 100644 merge-ort.h

base-commit: 69986e19ffcfb9af674ae5180689ab7bbf92ed28
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-895%2Fnewren%2Fort-api-with-empty-implementation-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-895/newren/ort-api-with-empty-implementation-v3
Pull-Request: https://github.com/git/git/pull/895

Range-diff vs v2:

1: b9e73975ea ! 1: 3357ea415e merge-ort: barebones API of new merge strategy with empty implementation

     @@ merge-ort.c (new)
      +	die("Not yet implemented");
      +}
      +
     -+void merge_inmemory_nonrecursive(struct merge_options *opt,
     -+				 struct tree *merge_base,
     -+				 struct tree *side1,
     -+				 struct tree *side2,
     -+				 struct merge_result *result)
     ++void merge_incore_nonrecursive(struct merge_options *opt,
     ++			       struct tree *merge_base,
     ++			       struct tree *side1,
     ++			       struct tree *side2,
     ++			       struct merge_result *result)
      +{
      +	die("Not yet implemented");
      +}
      +
     -+void merge_inmemory_recursive(struct merge_options *opt,
     -+			      struct commit_list *merge_bases,
     -+			      struct commit *side1,
     -+			      struct commit *side2,
     -+			      struct merge_result *result)
     ++void merge_incore_recursive(struct merge_options *opt,
     ++			    struct commit_list *merge_bases,
     ++			    struct commit *side1,
     ++			    struct commit *side2,
     ++			    struct merge_result *result)
      +{
      +	die("Not yet implemented");
      +}
     @@ merge-ort.h (new)
      +struct tree;
      +
      +struct merge_result {
     -+	/* whether the merge is clean */
     ++	/* Whether the merge is clean */
      +	int clean;
      +
     -+	/* Result of merge.  If !clean, represents what would go in worktree */
     ++	/*
     ++	 * Result of merge.  If !clean, represents what would go in worktree
     ++	 * (thus possibly including files containing conflict markers).
     ++	 */
      +	struct tree *tree;
      +
      +	/*
      +	 * Additional metadata used by merge_switch_to_result() or future calls
     -+	 * to merge_inmemory_*().  Not for external use.
     ++	 * to merge_incore_*().  Includes data needed to update the index (if
     ++	 * !clean) and to print "CONFLICT" messages.  Not for external use.
      +	 */
      +	void *priv;
     -+	unsigned ate;
      +};
      +
     -+/* rename-detecting three-way merge with recursive ancestor consolidation. */
     -+void merge_inmemory_recursive(struct merge_options *opt,
     -+			      struct commit_list *merge_bases,
     -+			      struct commit *side1,
     -+			      struct commit *side2,
     -+			      struct merge_result *result);
     ++/*
     ++ * rename-detecting three-way merge with recursive ancestor consolidation.
     ++ * working tree and index are untouched.
     ++ */
     ++void merge_incore_recursive(struct merge_options *opt,
     ++			    struct commit_list *merge_bases,
     ++			    struct commit *side1,
     ++			    struct commit *side2,
     ++			    struct merge_result *result);
      +
     -+/* rename-detecting three-way merge, no recursion. */
     -+void merge_inmemory_nonrecursive(struct merge_options *opt,
     -+				 struct tree *merge_base,
     -+				 struct tree *side1,
     -+				 struct tree *side2,
     -+				 struct merge_result *result);
     ++/*
     ++ * rename-detecting three-way merge, no recursion.
     ++ * working tree and index are untouched.
     ++ */
     ++void merge_incore_nonrecursive(struct merge_options *opt,
     ++			       struct tree *merge_base,
     ++			       struct tree *side1,
     ++			       struct tree *side2,
     ++			       struct merge_result *result);
      +
     -+/* Update the working tree and index from head to result after inmemory merge */
     ++/* Update the working tree and index from head to result after incore merge */
      +void merge_switch_to_result(struct merge_options *opt,
      +			    struct tree *head,
      +			    struct merge_result *result,
 2:  a9fff811a2 ! 2:  d7f6a834ab merge-ort-wrappers: new convience wrappers to mimic the old merge API
     @@ merge-ort-wrappers.c (new)
      +	}
      +
      +	memset(&result, 0, sizeof(result));
     -+	merge_inmemory_nonrecursive(opt, merge_base, head, merge, &result);
     ++	merge_incore_nonrecursive(opt, merge_base, head, merge, &result);
      +	merge_switch_to_result(opt, head, &result, 1, 1);
      +
      +	return result.clean;
     @@ merge-ort-wrappers.c (new)
      +		return -1;
      +
      +	memset(&tmp, 0, sizeof(tmp));
     -+	merge_inmemory_recursive(opt, merge_bases, side1, side2, &tmp);
     ++	merge_incore_recursive(opt, merge_bases, side1, side2, &tmp);
      +	merge_switch_to_result(opt, head, &tmp, 1, 1);
      +	*result = NULL;
      +
 3:  f38d140c15 ! 3:  27ad756600 fast-rebase: demonstrate merge-ort's API via temporary/hidden command
     @@ builtin/fast-rebase.c (new)
      +		merge_opt.branch2 = short_commit_name(commit);
      +		merge_opt.ancestor = xstrfmt("parent of %s", merge_opt.branch2);
      +
     -+		merge_inmemory_nonrecursive(&merge_opt,
     -+					    base_tree,
     -+					    result.tree,
     -+					    next_tree,
     -+					    &result);
     ++		merge_incore_nonrecursive(&merge_opt,
     ++					  base_tree,
     ++					  result.tree,
     ++					  next_tree,
     ++					  &result);
      +
      +		free((char*)merge_opt.ancestor);
      +		merge_opt.ancestor = NULL;

4: 5f6c97b889 ! 4: 0479d59c33 merge,rebase,revert: select ort or recursive by config or environment
@@ sequencer.c: static int do_recursive_merge(struct repository *r,
- strbuf_release(&o.obuf);
+ if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+ memset(&result, 0, sizeof(result));
-+ merge_inmemory_nonrecursive(&o, base_tree, head_tree, next_tree,
++ merge_incore_nonrecursive(&o, base_tree, head_tree, next_tree,
+ &result);
+ show_output = !is_rebase_i(opts) || !result.clean;
+ /*
@@ sequencer.c: static int do_merge(struct repository *r,
- ret = merge_recursive(&o, head_commit, merge_commit, reversed, &i);
+ if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+ /*
-+ * TODO: Should use merge_inmemory_recursive() and
++ * TODO: Should use merge_incore_recursive() and
+ * merge_switch_to_result(), skipping the call to
+ * merge_switch_to_result() when we don't actually need to
+ * update the index and working copy immediately.

gitgitgadget

From: Elijah Newren <[email protected]>

This is the beginning of a new merge strategy. While there are some API differences, and the implementation has some differences in behavior, it is essentially meant as an eventual drop-in replacement for merge-recursive.c. However, it is being built to exist side-by-side with merge-recursive so that we have plenty of time to find out how those differences pan out in the real world while people can still fall back to merge-recursive. (Also, I intend to avoid modifying merge-recursive during this process, to keep it stable.)

The primary difference noticable here is that the updating of the working tree and index is not done simultaneously with the merge algorithm, but is a separate post-processing step. The new API is designed so that one can do repeated merges (e.g. during a rebase or cherry-pick) and only update the index and working tree one time at the end instead of updating it with every intermediate result. Also, one can perform a merge between two branches, neither of which match the index or the working tree, without clobbering the index or working tree.

The next three commits will demonstrate various uses of this new API.

---
 Makefile    |  1 +
 merge-ort.c | 52 +++++++++++++++++++++++++++++++++++++++++++++++
 merge-ort.h | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 111 insertions(+)
 create mode 100644 merge-ort.c
 create mode 100644 merge-ort.h

index 95571ee3fc..088770c2ae 100644
@@ -921,6 +921,7 @@ LIB_OBJS += mailmap.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += mem-pool.o
 LIB_OBJS += merge-blobs.o
+LIB_OBJS += merge-ort.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += merge.o
 LIB_OBJS += mergesort.o

gitgitgadget

You forgot:

git merge -s newren

the "NEW Recursive ENgine" merge strategy. I won't bore you with some other backronyms I came up with[1].

FOOTNOTES

[1] Such as "Extended LInear Jump AHead", "UNabashedly Smart High INtelligence Eccentricity" and "UNsurprisingly SHallow and INsignificant Exception". Oh wait, don't read this if you don't want to be bored.

Haha, those are great! :-) Maybe we should come up with one for TUFF?

This "stuff" writes itself: Transitive Unified Fundamental Finalizer

Actually, I quite like "Extended LInear Jump AHead"; it sounds like it could be a genuine algorithm. "NEW Recursive ENgine" is also reasonably good in that it's a drop-in replacement for the old "recursive" strategy, although a bit generic as a name and doesn't give an indication of the algorithm like "Extended LInear Jump AHead" does (even if that algorithm is fanciful).

From: Elijah Newren <[email protected]>

There are a few differences between the new API in merge-ort and the old API in merge-recursive. While the new API is more flexible, it might feel like more work at times than the old API. merge-ort-wrappers creates two convenience wrappers taking the exact same arguments as the old merge_trees() and merge_recursive() functions and implements them via the new API. This makes converting existing callsites easier, and serves to highlight some of the differences in the API.

---
 Makefile             |  1 +
 merge-ort-wrappers.c | 62 ++++++++++++++++++++++++++++++++++++++++++++
 merge-ort-wrappers.h | 25 ++++++++++++++++++
 3 files changed, 88 insertions(+)
 create mode 100644 merge-ort-wrappers.c
 create mode 100644 merge-ort-wrappers.h

index 088770c2ae..382fe73c76 100644
@@ -922,6 +922,7 @@ LIB_OBJS += match-trees.o
 LIB_OBJS += mem-pool.o
 LIB_OBJS += merge-blobs.o
 LIB_OBJS += merge-ort.o
+LIB_OBJS += merge-ort-wrappers.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += merge.o
 LIB_OBJS += mergesort.o

new file mode 100644
index 0000000000..0c4c57adbb
@@ -0,0 +1,25 @@
+#ifndef MERGE_ORT_WRAPPERS_H
+#define MERGE_ORT_WRAPPERS_H
+
+#include "merge-recursive.h"
+
+/*
+ * rename-detecting three-way merge, no recursion.
+ * Wrapper mimicking the old merge_trees() function.
+ */
+int merge_ort_nonrecursive(struct merge_options *opt,
+			   struct tree *head,
+			   struct tree *merge,
+			   struct tree *common);
+
+/*
+ * rename-detecting three-way merge with recursive ancestor consolidation.
+ * Wrapper mimicking the old merge_recursive() function.
+ */
+int merge_ort_recursive(struct merge_options *opt,
+			struct commit *h1,
+			struct commit *h2,
+			struct commit_list *ancestors,
+			struct commit **result);
+
+#endif

gitgitgadget

From: Elijah Newren <[email protected]>

Add a special built-in that is only of use to git-developers and only during the development of merge-ort, and which is designed to immediately fail and print:
git: 'fast-rebase' is not a git command
unless a special GIT_TEST_MERGE_ALGORITHM environment variable is set.

This special builtin serves two purposes:

1) Demonstrate the desired API of merge-ort. In particular, fast-rebase takes advantage of the separation of the merging operation from the updating of the index and working tree, to allow it to pick N commits, but only update the index and working tree once at the end. Look for the calls to merge_inmemory_nonrecursive() and merge_switch_to_result().

2) Provide a convenient benchmark that isn't polluted by the heavy disk writing and forking of unnecessary processes that comes from sequencer.c and merge-recursive.c. fast-rebase is not meant to replace sequencer.c, just give ideas on how sequencer.c can be changed. Updating sequencer.c with these goals is probably a large amount of work; writing a simple targeted command with no documentation, less-than-useful help messages, numerous limitations in terms of flags it can accept and situations it can handle, and which is flagged off from users is a much easier interim step.

---
 Makefile              |   1 +
 builtin.h             |   1 +
 builtin/fast-rebase.c | 210 ++++++++++++++++++++++++++++++++++++++++++
 git.c                 |   1 +
 4 files changed, 213 insertions(+)
 create mode 100644 builtin/fast-rebase.c

index 382fe73c76..1b40d780fa 100644
@@ -1087,6 +1087,7 @@ BUILTIN_OBJS += builtin/difftool.o
 BUILTIN_OBJS += builtin/env--helper.o
 BUILTIN_OBJS += builtin/fast-export.o
 BUILTIN_OBJS += builtin/fast-import.o
+BUILTIN_OBJS += builtin/fast-rebase.o
 BUILTIN_OBJS += builtin/fetch-pack.o
 BUILTIN_OBJS += builtin/fetch.o
 BUILTIN_OBJS += builtin/fmt-merge-msg.o

index 53fb290963..75ff7dc8a9 100644
@@ -151,6 +151,7 @@ int cmd_difftool(int argc, const char **argv, const char *prefix);
 int cmd_env__helper(int argc, const char **argv, const char *prefix);
 int cmd_fast_export(int argc, const char **argv, const char *prefix);
 int cmd_fast_import(int argc, const char **argv, const char *prefix);
+int cmd_fast_rebase(int argc, const char **argv, const char *prefix);
 int cmd_fetch(int argc, const char **argv, const char *prefix);
 int cmd_fetch_pack(int argc, const char **argv, const char *prefix);
 int cmd_fmt_merge_msg(int argc, const char **argv, const char *prefix);

index 4bdcdad2cc..af84f11e69 100644
@@ -512,6 +512,7 @@ static struct cmd_struct commands[] = {
 	{ "env--helper", cmd_env__helper },
 	{ "fast-export", cmd_fast_export, RUN_SETUP },
 	{ "fast-import", cmd_fast_import, RUN_SETUP | NO_PARSEOPT },
+	{ "fast-rebase", cmd_fast_rebase, RUN_SETUP /* | NEED_WORK_TREE */ },
 	{ "fetch", cmd_fetch, RUN_SETUP },
 	{ "fetch-pack", cmd_fetch_pack, RUN_SETUP | NO_PARSEOPT },
 	{ "fmt-merge-msg", cmd_fmt_merge_msg, RUN_SETUP },

gitgitgadget

Please also list this new command in '.gitignore'.

Perhaps it should be listed in 'command-list.txt' as well, though I'm not sure. It starts with:

# All supported commands, builtin or external, must be described in

  # here. This info is used to list commands in various places.

though I'm not sure that we want to list such a special-purpose command in "various places", and it appears to work anyway...

Or perhaps this is a sign that this would be better added as a test-tool helper as suggested earlier?

From: Elijah Newren <[email protected]>

Allow the testsuite to run where it treats requests for "recursive" or the default merge algorithm via consulting the environment variable GIT_TEST_MERGE_ALGORITHM which is expected to either be "recursive" (the old traditional algorithm) or "ort" (the new algorithm).

Also, allow folks to pick the new algorithm via config setting. It turns out builtin/merge.c already had a way to allow users to specify a different default merge algorithm: pull.twohead. Rather odd configuration name (especially to be in the 'pull' namespace rather than 'merge') but it's there. Add that same configuration to rebase, cherry-pick, and revert.

This required updating the various callsites that called merge_trees() or merge_recursive() to conditionally call the new API, so this serves as another demonstration of what the new API looks and feels like. There are almost certainly some callsites that have not yet been modified to work with the new merge algorithm, but this represents the ones that I have been testing with thus far.

---
 builtin/merge.c  | 26 ++++++++++++++++--
 builtin/rebase.c |  9 +++++-
 builtin/revert.c |  2 ++
 sequencer.c      | 71 ++++++++++++++++++++++++++++++++++++++++--------
 4 files changed, 93 insertions(+), 15 deletions(-)

index 9d5359edc2..87dfc9bc06 100644
@@ -28,6 +28,7 @@
 #include "rerere.h"
 #include "help.h"
 #include "merge-recursive.h"
+#include "merge-ort-wrappers.h"
 #include "resolve-undo.h"
 #include "remote.h"
 #include "fmt-merge-msg.h"

@@ -88,6 +89,7 @@ static int no_verify;
 static struct strategy all_strategy[] = {
 	{ "recursive",  DEFAULT_TWOHEAD | NO_TRIVIAL },
 	{ "octopus",    DEFAULT_OCTOPUS },
+	{ "ort",        NO_TRIVIAL },
 	{ "resolve",    0 },
 	{ "ours",       NO_FAST_FORWARD | NO_TRIVIAL },
 	{ "subtree",    NO_FAST_FORWARD | NO_TRIVIAL },

@@ -159,10 +161,17 @@ static struct strategy *get_strategy(const char *name)
 	struct strategy *ret;
 	static struct cmdnames main_cmds, other_cmds;
 	static int loaded;
+	char *default_strategy = getenv("GIT_TEST_MERGE_ALGORITHM");
 
 	if (!name)
 		return NULL;
 
+	if (default_strategy &&
+	    !strcmp(default_strategy, "ort") &&
+	    !strcmp(name, "recursive")) {
+		name = "ort";
+	}
+
 	for (i = 0; i < ARRAY_SIZE(all_strategy); i++)
 		if (!strcmp(name, all_strategy[i].name))
 			return &all_strategy[i];

@@ -701,7 +710,8 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
 	if (refresh_and_write_cache(REFRESH_QUIET, SKIP_IF_UNCHANGED, 0) < 0)
 		return error(_("Unable to write index."));
 
-	if (!strcmp(strategy, "recursive") || !strcmp(strategy, "subtree")) {
+	if (!strcmp(strategy, "recursive") || !strcmp(strategy, "subtree") ||
+	    !strcmp(strategy, "ort")) {
 		struct lock_file lock = LOCK_INIT;
 		int clean, x;
 		struct commit *result;

@@ -732,8 +742,12 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
 			commit_list_insert(j->item, &reversed);
 
 		hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
-		clean = merge_recursive(&o, head,
-				remoteheads->item, reversed, &result);
+		if (!strcmp(strategy, "ort"))
+			clean = merge_ort_recursive(&o, head, remoteheads->item,
+						    reversed, &result);
+		else
+			clean = merge_recursive(&o, head, remoteheads->item,
+						reversed, &result);
 		if (clean < 0)
 			exit(128);
 		if (write_locked_index(&the_index, &lock,

@@ -1264,6 +1278,12 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 	if (branch)
 		skip_prefix(branch, "refs/heads/", &branch);
 
+	if (!pull_twohead) {
+		char *default_strategy = getenv("GIT_TEST_MERGE_ALGORITHM");
+		if (default_strategy && !strcmp(default_strategy, "ort"))
+			pull_twohead = "ort";
+	}
+
 	init_diff_ui_defaults();
 	git_config(git_merge_config, NULL);
 

index eeca53382f..9719aa25da 100644
@@ -119,6 +119,7 @@ static struct replay_opts get_replay_opts(const struct rebase_options *opts)
 	struct replay_opts replay = REPLAY_OPTS_INIT;
 
 	replay.action = REPLAY_INTERACTIVE_REBASE;
+	replay.strategy = NULL;
 	sequencer_init_config(&replay);
 
 	replay.signoff = opts->signoff;

@@ -136,7 +137,8 @@ static struct replay_opts get_replay_opts(const struct rebase_options *opts)
 					opts->committer_date_is_author_date;
 	replay.ignore_date = opts->ignore_date;
 	replay.gpg_sign = xstrdup_or_null(opts->gpg_sign_opt);
-	replay.strategy = opts->strategy;
+	if (opts->strategy)
+		replay.strategy = opts->strategy;
 
 	if (opts->strategy_opts)
 		parse_strategy_opts(&replay, opts->strategy_opts);

@@ -1771,6 +1773,11 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
 			    options.default_backend);
 	}
 
+	if (options.type == REBASE_MERGE &&
+	    !options.strategy &&
+	    getenv("GIT_TEST_MERGE_ALGORITHM"))
+		options.strategy = xstrdup(getenv("GIT_TEST_MERGE_ALGORITHM"));
+
 	switch (options.type) {
 	case REBASE_MERGE:
 	case REBASE_PRESERVE_MERGES:

index f61cc5d82c..c7cb0c1a18 100644
@@ -202,6 +202,8 @@ static int run_sequencer(int argc, const char **argv, struct replay_opts *opts)
 	/* These option values will be free()d */
 	opts->gpg_sign = xstrdup_or_null(opts->gpg_sign);
 	opts->strategy = xstrdup_or_null(opts->strategy);
+	if (!opts->strategy && getenv("GIT_TEST_MERGE_ALGORITHM"))
+		opts->strategy = xstrdup(getenv("GIT_TEST_MERGE_ALGORITHM"));
 
 	if (cmd == 'q') {
 		int ret = sequencer_remove_state(opts);

gitgitgadget

In this series, I show the new merge API I have developed in merge-ort, and show how it differs from that provided by merge-recursive. I do this in four steps, each corresponding to a patch.

Changes since v3:

* Make 'fast-rebase' be a test-tool subcommand instead of a special hidden builtin, as suggested by Jonathan Tan and SZEDER Gábor

Elijah Newren (4):
merge-ort: barebones API of new merge strategy with empty
implementation
merge-ort-wrappers: new convience wrappers to mimic the old merge API
fast-rebase: demonstrate merge-ort's API via new test-tool command merge,rebase,revert: select ort or recursive by config or environment

 Makefile                    |   3 +
 builtin/merge.c             |  26 ++++-
 builtin/rebase.c            |   9 +-
 builtin/revert.c            |   2 +
 merge-ort-wrappers.c        |  62 +++++++++++
 merge-ort-wrappers.h        |  25 +++++
 merge-ort.c                 |  52 +++++++++
 merge-ort.h                 |  58 ++++++++++
 sequencer.c                 |  71 ++++++++++--
 t/helper/test-fast-rebase.c | 211 ++++++++++++++++++++++++++++++++++++
 t/helper/test-tool.c        |   1 +
 t/helper/test-tool.h        |   1 +
 12 files changed, 506 insertions(+), 15 deletions(-)
 create mode 100644 merge-ort-wrappers.c
 create mode 100644 merge-ort-wrappers.h
 create mode 100644 merge-ort.c
 create mode 100644 merge-ort.h
 create mode 100644 t/helper/test-fast-rebase.c

base-commit: 69986e19ffcfb9af674ae5180689ab7bbf92ed28
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-895%2Fnewren%2Fort-api-with-empty-implementation-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-895/newren/ort-api-with-empty-implementation-v4
Pull-Request: https://github.com/git/git/pull/895

Range-diff vs v3:

 1:  3357ea415e = 1:  3357ea415e merge-ort: barebones API of new merge strategy with empty implementation
 2:  d7f6a834ab = 2:  d7f6a834ab merge-ort-wrappers: new convience wrappers to mimic the old merge API
 3:  27ad756600 ! 3:  fce0db8778 fast-rebase: demonstrate merge-ort's API via temporary/hidden command

@@ Metadata
Author: Elijah Newren <[email protected]>

## Commit message ##
- fast-rebase: demonstrate merge-ort's API via temporary/hidden command
+ fast-rebase: demonstrate merge-ort's API via new test-tool command

- Add a special built-in that is only of use to git-developers and only
- during the development of merge-ort, and which is designed to
- immediately fail and print:
- git: 'fast-rebase' is not a git command
- unless a special GIT_TEST_MERGE_ALGORITHM environment variable is set.
-
- This special builtin serves two purposes:
+ Add a new test-tool command named 'fast-rebase', which is a
+ super-slimmed down and nowhere near as capable version of 'git rebase'.
+ 'test-tool fast-rebase' is not currently planned for usage in the
+ testsuite, but is here for two purposes:

1) Demonstrate the desired API of merge-ort. In particular, fast-rebase takes advantage of the separation of the merging operation from the updating of the index and working tree, to allow it to pick N commits, but only update the index and working tree once at the end. Look for the calls to
- merge_inmemory_nonrecursive() and merge_switch_to_result().
+ merge_incore_nonrecursive() and merge_switch_to_result().

2) Provide a convenient benchmark that isn't polluted by the heavy disk writing and forking of unnecessary processes that comes from
@@ Commit message

## Makefile ##
-@@ Makefile: BUILTIN_OBJS += builtin/difftool.o
- BUILTIN_OBJS += builtin/env--helper.o
- BUILTIN_OBJS += builtin/fast-export.o
- BUILTIN_OBJS += builtin/fast-import.o
-+BUILTIN_OBJS += builtin/fast-rebase.o
- BUILTIN_OBJS += builtin/fetch-pack.o
- BUILTIN_OBJS += builtin/fetch.o
- BUILTIN_OBJS += builtin/fmt-merge-msg.o
-
- ## builtin.h ##
-@@ builtin.h: int cmd_difftool(int argc, const char **argv, const char *prefix);
- int cmd_env__helper(int argc, const char **argv, const char *prefix);
- int cmd_fast_export(int argc, const char **argv, const char *prefix);
- int cmd_fast_import(int argc, const char **argv, const char *prefix); -+int cmd_fast_rebase(int argc, const char **argv, const char *prefix);
- int cmd_fetch(int argc, const char **argv, const char *prefix);
- int cmd_fetch_pack(int argc, const char **argv, const char *prefix);
- int cmd_fmt_merge_msg(int argc, const char **argv, const char *prefix); +@@ Makefile: TEST_BUILTINS_OBJS += test-dump-fsmonitor.o
+ TEST_BUILTINS_OBJS += test-dump-split-index.o
+ TEST_BUILTINS_OBJS += test-dump-untracked-cache.o
+ TEST_BUILTINS_OBJS += test-example-decorate.o ++TEST_BUILTINS_OBJS += test-fast-rebase.o
+ TEST_BUILTINS_OBJS += test-genrandom.o
+ TEST_BUILTINS_OBJS += test-genzeros.o
+ TEST_BUILTINS_OBJS += test-hash-speed.o

- ## builtin/fast-rebase.c (new) ##
+ ## t/helper/test-fast-rebase.c (new) ##
@@
+/*
+ * "git fast-rebase" builtin command
@@ builtin/fast-rebase.c (new)
+ */
+
+#define USE_THE_INDEX_COMPATIBILITY_MACROS
-+#include "builtin.h"
++#include "test-tool.h"
+
+#include "cache-tree.h"
+#include "commit.h"
@@ builtin/fast-rebase.c (new)
+ return (struct commit *)obj;
+}
+
-+int cmd_fast_rebase(int argc, const char **argv, const char *prefix) ++int cmd__fast_rebase(int argc, const char **argv)
+{
+ struct commit *onto;
+ struct commit *last_commit = NULL, *last_picked_commit = NULL;
@@ builtin/fast-rebase.c (new)
+ struct strbuf reflog_msg = STRBUF_INIT;
+ struct strbuf branch_name = STRBUF_INIT;
+
++ /*
++ * test-tool stuff doesn't set up the git directory by default; need to
++ * do that manually.
++ */
++ setup_git_directory();
++
+ if (argc == 2 && !strcmp(argv[1], "-h")) {
+ printf("Sorry, I am not a psychiatrist; I can not give you the help you need. Oh, you meant usage...\n");
+ exit(129);
+ }
+
-+ if (!getenv("GIT_TEST_MERGE_ALGORITHM")) {
-+ fprintf_ln(stderr, _("git: 'fast-rebase' is not a git command. See 'git --help'."));
-+ exit(1);
-+ }
-+
+ if (argc != 5 || strcmp(argv[1], "--onto"))
+ die("usage: read the code, figure out how to use it, then do so");
+
@@ builtin/fast-rebase.c (new)
+ return (clean == 0);
+}

- ## git.c ##
-@@ git.c: static struct cmd_struct commands[] = {
- { "env--helper", cmd_env__helper },
- { "fast-export", cmd_fast_export, RUN_SETUP },
- { "fast-import", cmd_fast_import, RUN_SETUP | NO_PARSEOPT },
-+ { "fast-rebase", cmd_fast_rebase, RUN_SETUP /* | NEED_WORK_TREE */ },
- { "fetch", cmd_fetch, RUN_SETUP },
- { "fetch-pack", cmd_fetch_pack, RUN_SETUP | NO_PARSEOPT },
- { "fmt-merge-msg", cmd_fmt_merge_msg, RUN_SETUP },
+ ## t/helper/test-tool.c ##
+@@ t/helper/test-tool.c: static struct test_cmd cmds[] = {
+ { "dump-split-index", cmd__dump_split_index },
+ { "dump-untracked-cache", cmd__dump_untracked_cache },
+ { "example-decorate", cmd__example_decorate },
++ { "fast-rebase", cmd__fast_rebase },
+ { "genrandom", cmd__genrandom },
+ { "genzeros", cmd__genzeros },
+ { "hashmap", cmd__hashmap },
+
+ ## t/helper/test-tool.h ##
+@@ t/helper/test-tool.h: int cmd__dump_fsmonitor(int argc, const char **argv);
+ int cmd__dump_split_index(int argc, const char **argv);
+ int cmd__dump_untracked_cache(int argc, const char **argv);
+ int cmd__example_decorate(int argc, const char **argv);
++int cmd__fast_rebase(int argc, const char **argv);
+ int cmd__genrandom(int argc, const char **argv);
+ int cmd__genzeros(int argc, const char **argv);
+ int cmd__hashmap(int argc, const char **argv);
4: 0479d59c33 = 4: 75d19804bd merge,rebase,revert: select ort or recursive by config or environment

gitgitgadget

From: Elijah Newren <[email protected]>

This is the beginning of a new merge strategy. While there are some API differences, and the implementation has some differences in behavior, it is essentially meant as an eventual drop-in replacement for merge-recursive.c. However, it is being built to exist side-by-side with merge-recursive so that we have plenty of time to find out how those differences pan out in the real world while people can still fall back to merge-recursive. (Also, I intend to avoid modifying merge-recursive during this process, to keep it stable.)

The primary difference noticable here is that the updating of the working tree and index is not done simultaneously with the merge algorithm, but is a separate post-processing step. The new API is designed so that one can do repeated merges (e.g. during a rebase or cherry-pick) and only update the index and working tree one time at the end instead of updating it with every intermediate result. Also, one can perform a merge between two branches, neither of which match the index or the working tree, without clobbering the index or working tree.

The next three commits will demonstrate various uses of this new API.

---
 Makefile    |  1 +
 merge-ort.c | 52 +++++++++++++++++++++++++++++++++++++++++++++++
 merge-ort.h | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 111 insertions(+)
 create mode 100644 merge-ort.c
 create mode 100644 merge-ort.h

index 95571ee3fc..088770c2ae 100644
@@ -921,6 +921,7 @@ LIB_OBJS += mailmap.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += mem-pool.o
 LIB_OBJS += merge-blobs.o
+LIB_OBJS += merge-ort.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += merge.o
 LIB_OBJS += mergesort.o

gitgitgadget

From: Elijah Newren <[email protected]>

There are a few differences between the new API in merge-ort and the old API in merge-recursive. While the new API is more flexible, it might feel like more work at times than the old API. merge-ort-wrappers creates two convenience wrappers taking the exact same arguments as the old merge_trees() and merge_recursive() functions and implements them via the new API. This makes converting existing callsites easier, and serves to highlight some of the differences in the API.

---
 Makefile             |  1 +
 merge-ort-wrappers.c | 62 ++++++++++++++++++++++++++++++++++++++++++++
 merge-ort-wrappers.h | 25 ++++++++++++++++++
 3 files changed, 88 insertions(+)
 create mode 100644 merge-ort-wrappers.c
 create mode 100644 merge-ort-wrappers.h

index 088770c2ae..382fe73c76 100644
@@ -922,6 +922,7 @@ LIB_OBJS += match-trees.o
 LIB_OBJS += mem-pool.o
 LIB_OBJS += merge-blobs.o
 LIB_OBJS += merge-ort.o
+LIB_OBJS += merge-ort-wrappers.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += merge.o
 LIB_OBJS += mergesort.o

new file mode 100644
index 0000000000..0c4c57adbb
@@ -0,0 +1,25 @@
+#ifndef MERGE_ORT_WRAPPERS_H
+#define MERGE_ORT_WRAPPERS_H
+
+#include "merge-recursive.h"
+
+/*
+ * rename-detecting three-way merge, no recursion.
+ * Wrapper mimicking the old merge_trees() function.
+ */
+int merge_ort_nonrecursive(struct merge_options *opt,
+			   struct tree *head,
+			   struct tree *merge,
+			   struct tree *common);
+
+/*
+ * rename-detecting three-way merge with recursive ancestor consolidation.
+ * Wrapper mimicking the old merge_recursive() function.
+ */
+int merge_ort_recursive(struct merge_options *opt,
+			struct commit *h1,
+			struct commit *h2,
+			struct commit_list *ancestors,
+			struct commit **result);
+
+#endif

gitgitgadget

From: Elijah Newren <[email protected]>

Add a new test-tool command named 'fast-rebase', which is a super-slimmed down and nowhere near as capable version of 'git rebase'. 'test-tool fast-rebase' is not currently planned for usage in the testsuite, but is here for two purposes:

1) Demonstrate the desired API of merge-ort. In particular, fast-rebase takes advantage of the separation of the merging operation from the updating of the index and working tree, to allow it to pick N commits, but only update the index and working tree once at the end. Look for the calls to merge_incore_nonrecursive() and merge_switch_to_result().

2) Provide a convenient benchmark that isn't polluted by the heavy disk writing and forking of unnecessary processes that comes from sequencer.c and merge-recursive.c. fast-rebase is not meant to replace sequencer.c, just give ideas on how sequencer.c can be changed. Updating sequencer.c with these goals is probably a large amount of work; writing a simple targeted command with no documentation, less-than-useful help messages, numerous limitations in terms of flags it can accept and situations it can handle, and which is flagged off from users is a much easier interim step.

---
 Makefile                    |   1 +
 t/helper/test-fast-rebase.c | 211 ++++++++++++++++++++++++++++++++++++
 t/helper/test-tool.c        |   1 +
 t/helper/test-tool.h        |   1 +
 4 files changed, 214 insertions(+)
 create mode 100644 t/helper/test-fast-rebase.c

index 382fe73c76..24b9fecc0f 100644
@@ -704,6 +704,7 @@ TEST_BUILTINS_OBJS += test-dump-fsmonitor.o
 TEST_BUILTINS_OBJS += test-dump-split-index.o
 TEST_BUILTINS_OBJS += test-dump-untracked-cache.o
 TEST_BUILTINS_OBJS += test-example-decorate.o
+TEST_BUILTINS_OBJS += test-fast-rebase.o
 TEST_BUILTINS_OBJS += test-genrandom.o
 TEST_BUILTINS_OBJS += test-genzeros.o
 TEST_BUILTINS_OBJS += test-hash-speed.o

index a0d3966b29..8bce7db076 100644
@@ -28,6 +28,7 @@ static struct test_cmd cmds[] = {
 	{ "dump-split-index", cmd__dump_split_index },
 	{ "dump-untracked-cache", cmd__dump_untracked_cache },
 	{ "example-decorate", cmd__example_decorate },
+	{ "fast-rebase", cmd__fast_rebase },
 	{ "genrandom", cmd__genrandom },
 	{ "genzeros", cmd__genzeros },
 	{ "hashmap", cmd__hashmap },

index 07034d3f38..fd0cafe5ca 100644
@@ -18,6 +18,7 @@ int cmd__dump_fsmonitor(int argc, const char **argv);
 int cmd__dump_split_index(int argc, const char **argv);
 int cmd__dump_untracked_cache(int argc, const char **argv);
 int cmd__example_decorate(int argc, const char **argv);
+int cmd__fast_rebase(int argc, const char **argv);
 int cmd__genrandom(int argc, const char **argv);
 int cmd__genzeros(int argc, const char **argv);
 int cmd__hashmap(int argc, const char **argv);

gitgitgadget

From: Elijah Newren <[email protected]>

Allow the testsuite to run where it treats requests for "recursive" or the default merge algorithm via consulting the environment variable GIT_TEST_MERGE_ALGORITHM which is expected to either be "recursive" (the old traditional algorithm) or "ort" (the new algorithm).

Also, allow folks to pick the new algorithm via config setting. It turns out builtin/merge.c already had a way to allow users to specify a different default merge algorithm: pull.twohead. Rather odd configuration name (especially to be in the 'pull' namespace rather than 'merge') but it's there. Add that same configuration to rebase, cherry-pick, and revert.

This required updating the various callsites that called merge_trees() or merge_recursive() to conditionally call the new API, so this serves as another demonstration of what the new API looks and feels like. There are almost certainly some callsites that have not yet been modified to work with the new merge algorithm, but this represents the ones that I have been testing with thus far.

---
 builtin/merge.c  | 26 ++++++++++++++++--
 builtin/rebase.c |  9 +++++-
 builtin/revert.c |  2 ++
 sequencer.c      | 71 ++++++++++++++++++++++++++++++++++++++++--------
 4 files changed, 93 insertions(+), 15 deletions(-)

index 9d5359edc2..87dfc9bc06 100644
@@ -28,6 +28,7 @@
 #include "rerere.h"
 #include "help.h"
 #include "merge-recursive.h"
+#include "merge-ort-wrappers.h"
 #include "resolve-undo.h"
 #include "remote.h"
 #include "fmt-merge-msg.h"

@@ -88,6 +89,7 @@ static int no_verify;
 static struct strategy all_strategy[] = {
 	{ "recursive",  DEFAULT_TWOHEAD | NO_TRIVIAL },
 	{ "octopus",    DEFAULT_OCTOPUS },
+	{ "ort",        NO_TRIVIAL },
 	{ "resolve",    0 },
 	{ "ours",       NO_FAST_FORWARD | NO_TRIVIAL },
 	{ "subtree",    NO_FAST_FORWARD | NO_TRIVIAL },

@@ -159,10 +161,17 @@ static struct strategy *get_strategy(const char *name)
 	struct strategy *ret;
 	static struct cmdnames main_cmds, other_cmds;
 	static int loaded;
+	char *default_strategy = getenv("GIT_TEST_MERGE_ALGORITHM");
 
 	if (!name)
 		return NULL;
 
+	if (default_strategy &&
+	    !strcmp(default_strategy, "ort") &&
+	    !strcmp(name, "recursive")) {
+		name = "ort";
+	}
+
 	for (i = 0; i < ARRAY_SIZE(all_strategy); i++)
 		if (!strcmp(name, all_strategy[i].name))
 			return &all_strategy[i];

@@ -701,7 +710,8 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
 	if (refresh_and_write_cache(REFRESH_QUIET, SKIP_IF_UNCHANGED, 0) < 0)
 		return error(_("Unable to write index."));
 
-	if (!strcmp(strategy, "recursive") || !strcmp(strategy, "subtree")) {
+	if (!strcmp(strategy, "recursive") || !strcmp(strategy, "subtree") ||
+	    !strcmp(strategy, "ort")) {
 		struct lock_file lock = LOCK_INIT;
 		int clean, x;
 		struct commit *result;

@@ -732,8 +742,12 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
 			commit_list_insert(j->item, &reversed);
 
 		hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
-		clean = merge_recursive(&o, head,
-				remoteheads->item, reversed, &result);
+		if (!strcmp(strategy, "ort"))
+			clean = merge_ort_recursive(&o, head, remoteheads->item,
+						    reversed, &result);
+		else
+			clean = merge_recursive(&o, head, remoteheads->item,
+						reversed, &result);
 		if (clean < 0)
 			exit(128);
 		if (write_locked_index(&the_index, &lock,

@@ -1264,6 +1278,12 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 	if (branch)
 		skip_prefix(branch, "refs/heads/", &branch);
 
+	if (!pull_twohead) {
+		char *default_strategy = getenv("GIT_TEST_MERGE_ALGORITHM");
+		if (default_strategy && !strcmp(default_strategy, "ort"))
+			pull_twohead = "ort";
+	}
+
 	init_diff_ui_defaults();
 	git_config(git_merge_config, NULL);
 

index eeca53382f..9719aa25da 100644
@@ -119,6 +119,7 @@ static struct replay_opts get_replay_opts(const struct rebase_options *opts)
 	struct replay_opts replay = REPLAY_OPTS_INIT;
 
 	replay.action = REPLAY_INTERACTIVE_REBASE;
+	replay.strategy = NULL;
 	sequencer_init_config(&replay);
 
 	replay.signoff = opts->signoff;

@@ -136,7 +137,8 @@ static struct replay_opts get_replay_opts(const struct rebase_options *opts)
 					opts->committer_date_is_author_date;
 	replay.ignore_date = opts->ignore_date;
 	replay.gpg_sign = xstrdup_or_null(opts->gpg_sign_opt);
-	replay.strategy = opts->strategy;
+	if (opts->strategy)
+		replay.strategy = opts->strategy;
 
 	if (opts->strategy_opts)
 		parse_strategy_opts(&replay, opts->strategy_opts);

@@ -1771,6 +1773,11 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
 			    options.default_backend);
 	}
 
+	if (options.type == REBASE_MERGE &&
+	    !options.strategy &&
+	    getenv("GIT_TEST_MERGE_ALGORITHM"))
+		options.strategy = xstrdup(getenv("GIT_TEST_MERGE_ALGORITHM"));
+
 	switch (options.type) {
 	case REBASE_MERGE:
 	case REBASE_PRESERVE_MERGES:

index f61cc5d82c..c7cb0c1a18 100644
@@ -202,6 +202,8 @@ static int run_sequencer(int argc, const char **argv, struct replay_opts *opts)
 	/* These option values will be free()d */
 	opts->gpg_sign = xstrdup_or_null(opts->gpg_sign);
 	opts->strategy = xstrdup_or_null(opts->strategy);
+	if (!opts->strategy && getenv("GIT_TEST_MERGE_ALGORITHM"))
+		opts->strategy = xstrdup(getenv("GIT_TEST_MERGE_ALGORITHM"));
 
 	if (cmd == 'q') {
 		int ret = sequencer_remove_state(opts);

gitgitgadget

I'm definitely excited by this project. I'm curious if you have any further implementation as a WIP that could be played with to see the end result of the new merging?

I definitely like this approach where you work in smaller increments to make the implementation easier to review!

Thanks,
Jake

I usually keep the 'ort' branch of https://github.com/newren/git
functional (no promises, though). It has lots of ifdefs, super ugly commits, todos & fixmes, and random additional (non-code) files where I was tracking various things I was working on, so the code and the tree may not be super readable, but it should be usable (and passes all the tests) -- just set pull.twohead=ort in your git config, or set the environment variable GIT_TEST_MERGE_ALGORITHM=ort.

One warning: git cherry-pick --continue fails with "Cannot specify both --continue and --strategy"; my handling to set a --strategy option when pull.twohead was set apparently needs some tweaks. If you spot any bugs or other issues, let me know.

Hi Jake,

In addition to fixing this "cherry-pick --continue" bug last Monday, I discovered a bug yesterday while re-merging all the merge commits in the linux kernel causing it to fail an assertion. I'm surprised I hadn't hit that sooner, but if you're testing it out you may want to update your copy to the latest version of the 'ort' branch (make sure it has commit 067e5c1a38, "merge-ort: fix bug with cached_target_names not being initialized in redos", 2020-11-06).

In this series, I show the new merge API I have developed in merge-ort, and show how it differs from that provided by merge-recursive. I do this in four steps, each corresponding to a patch.

Changes since v4:

* Fix a bug where 'cherry-pick --continue' would report 'fatal:
cherry-pick: --strategy cannot be used with --continue' when pull.twohead was set to ort (found by user of internal deployment at $DAYJOB)

Elijah Newren (4):
merge-ort: barebones API of new merge strategy with empty
implementation
merge-ort-wrappers: new convience wrappers to mimic the old merge API
fast-rebase: demonstrate merge-ort's API via new test-tool command merge,rebase,revert: select ort or recursive by config or environment

 Makefile                    |   3 +
 builtin/merge.c             |  26 ++++-
 builtin/rebase.c            |  13 ++-
 builtin/revert.c            |   7 ++
 merge-ort-wrappers.c        |  62 +++++++++++
 merge-ort-wrappers.h        |  25 +++++
 merge-ort.c                 |  52 +++++++++
 merge-ort.h                 |  58 ++++++++++
 sequencer.c                 |  72 ++++++++++--
 sequencer.h                 |   1 +
 t/helper/test-fast-rebase.c | 211 ++++++++++++++++++++++++++++++++++++
 t/helper/test-tool.c        |   1 +
 t/helper/test-tool.h        |   1 +
 13 files changed, 517 insertions(+), 15 deletions(-)
 create mode 100644 merge-ort-wrappers.c
 create mode 100644 merge-ort-wrappers.h
 create mode 100644 merge-ort.c
 create mode 100644 merge-ort.h
 create mode 100644 t/helper/test-fast-rebase.c

base-commit: 69986e19ffcfb9af674ae5180689ab7bbf92ed28
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-895%2Fnewren%2Fort-api-with-empty-implementation-v5
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-895/newren/ort-api-with-empty-implementation-v5
Pull-Request: https://github.com/git/git/pull/895

Range-diff vs v4:

 1:  3357ea415e = 1:  3357ea415e merge-ort: barebones API of new merge strategy with empty implementation
 2:  d7f6a834ab = 2:  d7f6a834ab merge-ort-wrappers: new convience wrappers to mimic the old merge API
 3:  fce0db8778 = 3:  fce0db8778 fast-rebase: demonstrate merge-ort's API via new test-tool command
 4:  75d19804bd ! 4:  61217a83bd merge,rebase,revert: select ort or recursive by config or environment
     @@ builtin/rebase.c: static struct replay_opts get_replay_opts(const struct rebase_
      -	replay.strategy = opts->strategy;
      +	if (opts->strategy)
      +		replay.strategy = opts->strategy;
     ++	else if (!replay.strategy && replay.default_strategy) {
     ++		replay.strategy = replay.default_strategy;
     ++		replay.default_strategy = NULL;
     ++	}
       
       	if (opts->strategy_opts)
       		parse_strategy_opts(&replay, opts->strategy_opts);
     @@ builtin/rebase.c: int cmd_rebase(int argc, const char **argv, const char *prefix
       	case REBASE_PRESERVE_MERGES:
      
       ## builtin/revert.c ##
     +@@ builtin/revert.c: static int run_sequencer(int argc, const char **argv, struct replay_opts *opts)
     + 				NULL);
     + 	}
     + 
     ++	if (!opts->strategy && opts->default_strategy) {
     ++		opts->strategy = opts->default_strategy;
     ++		opts->default_strategy = NULL;
     ++	}
     ++
     + 	if (opts->allow_ff)
     + 		verify_opt_compatible(me, "--ff",
     + 				"--signoff", opts->signoff,
      @@ builtin/revert.c: static int run_sequencer(int argc, const char **argv, struct replay_opts *opts)
       	/* These option values will be free()d */
       	opts->gpg_sign = xstrdup_or_null(opts->gpg_sign);
     @@ sequencer.c: static int git_sequencer_config(const char *k, const char *v, void
       		return 0;
       	}
       
     -+	if (!opts->strategy && !strcmp(k, "pull.twohead")) {
     -+		int ret = git_config_string((const char**)&opts->strategy, k, v);
     ++	if (!opts->default_strategy && !strcmp(k, "pull.twohead")) {
     ++		int ret = git_config_string((const char**)&opts->default_strategy, k, v);
      +		if (ret == 0) {
      +			/*
      +			 * pull.twohead is allowed to be multi-valued; we only
      +			 * care about the first value.
      +			 */
     -+			char *tmp = strchr(opts->strategy, ' ');
     ++			char *tmp = strchr(opts->default_strategy, ' ');
      +			if (tmp)
      +				*tmp = '\0';
      +		}
     @@ sequencer.c: static int git_sequencer_config(const char *k, const char *v, void
       	status = git_gpg_config(k, v, NULL);
       	if (status)
       		return status;
     +@@ sequencer.c: int sequencer_remove_state(struct replay_opts *opts)
     + 	free(opts->committer_name);
     + 	free(opts->committer_email);
     + 	free(opts->gpg_sign);
     ++	free(opts->default_strategy);
     + 	free(opts->strategy);
     + 	for (i = 0; i < opts->xopts_nr; i++)
     + 		free(opts->xopts[i]);
      @@ sequencer.c: static int do_recursive_merge(struct repository *r,
       			      struct replay_opts *opts)
       {
     @@ sequencer.c: static int do_merge(struct repository *r,
       	if (ret <= 0)
       		fputs(o.obuf.buf, stdout);
       	strbuf_release(&o.obuf);
     +
     + ## sequencer.h ##
     +@@ sequencer.h: struct replay_opts {
     + 	int explicit_cleanup;
     + 
     + 	/* Merge strategy */
     ++	char *default_strategy;  /* from config options */
     + 	char *strategy;
     + 	char **xopts;
     + 	size_t xopts_nr, xopts_alloc;

gitgitgadget

From: Elijah Newren <[email protected]>

This is the beginning of a new merge strategy. While there are some API differences, and the implementation has some differences in behavior, it is essentially meant as an eventual drop-in replacement for merge-recursive.c. However, it is being built to exist side-by-side with merge-recursive so that we have plenty of time to find out how those differences pan out in the real world while people can still fall back to merge-recursive. (Also, I intend to avoid modifying merge-recursive during this process, to keep it stable.)

The primary difference noticable here is that the updating of the working tree and index is not done simultaneously with the merge algorithm, but is a separate post-processing step. The new API is designed so that one can do repeated merges (e.g. during a rebase or cherry-pick) and only update the index and working tree one time at the end instead of updating it with every intermediate result. Also, one can perform a merge between two branches, neither of which match the index or the working tree, without clobbering the index or working tree.

The next three commits will demonstrate various uses of this new API.

---
 Makefile    |  1 +
 merge-ort.c | 52 +++++++++++++++++++++++++++++++++++++++++++++++
 merge-ort.h | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 111 insertions(+)
 create mode 100644 merge-ort.c
 create mode 100644 merge-ort.h

index 95571ee3fc..088770c2ae 100644
@@ -921,6 +921,7 @@ LIB_OBJS += mailmap.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += mem-pool.o
 LIB_OBJS += merge-blobs.o
+LIB_OBJS += merge-ort.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += merge.o
 LIB_OBJS += mergesort.o

gitgitgadget

From: Elijah Newren <[email protected]>

There are a few differences between the new API in merge-ort and the old API in merge-recursive. While the new API is more flexible, it might feel like more work at times than the old API. merge-ort-wrappers creates two convenience wrappers taking the exact same arguments as the old merge_trees() and merge_recursive() functions and implements them via the new API. This makes converting existing callsites easier, and serves to highlight some of the differences in the API.

---
 Makefile             |  1 +
 merge-ort-wrappers.c | 62 ++++++++++++++++++++++++++++++++++++++++++++
 merge-ort-wrappers.h | 25 ++++++++++++++++++
 3 files changed, 88 insertions(+)
 create mode 100644 merge-ort-wrappers.c
 create mode 100644 merge-ort-wrappers.h

index 088770c2ae..382fe73c76 100644
@@ -922,6 +922,7 @@ LIB_OBJS += match-trees.o
 LIB_OBJS += mem-pool.o
 LIB_OBJS += merge-blobs.o
 LIB_OBJS += merge-ort.o
+LIB_OBJS += merge-ort-wrappers.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += merge.o
 LIB_OBJS += mergesort.o

new file mode 100644
index 0000000000..0c4c57adbb
@@ -0,0 +1,25 @@
+#ifndef MERGE_ORT_WRAPPERS_H
+#define MERGE_ORT_WRAPPERS_H
+
+#include "merge-recursive.h"
+
+/*
+ * rename-detecting three-way merge, no recursion.
+ * Wrapper mimicking the old merge_trees() function.
+ */
+int merge_ort_nonrecursive(struct merge_options *opt,
+			   struct tree *head,
+			   struct tree *merge,
+			   struct tree *common);
+
+/*
+ * rename-detecting three-way merge with recursive ancestor consolidation.
+ * Wrapper mimicking the old merge_recursive() function.
+ */
+int merge_ort_recursive(struct merge_options *opt,
+			struct commit *h1,
+			struct commit *h2,
+			struct commit_list *ancestors,
+			struct commit **result);
+
+#endif

gitgitgadget

From: Elijah Newren <[email protected]>

Add a new test-tool command named 'fast-rebase', which is a super-slimmed down and nowhere near as capable version of 'git rebase'. 'test-tool fast-rebase' is not currently planned for usage in the testsuite, but is here for two purposes:

1) Demonstrate the desired API of merge-ort. In particular, fast-rebase takes advantage of the separation of the merging operation from the updating of the index and working tree, to allow it to pick N commits, but only update the index and working tree once at the end. Look for the calls to merge_incore_nonrecursive() and merge_switch_to_result().

2) Provide a convenient benchmark that isn't polluted by the heavy disk writing and forking of unnecessary processes that comes from sequencer.c and merge-recursive.c. fast-rebase is not meant to replace sequencer.c, just give ideas on how sequencer.c can be changed. Updating sequencer.c with these goals is probably a large amount of work; writing a simple targeted command with no documentation, less-than-useful help messages, numerous limitations in terms of flags it can accept and situations it can handle, and which is flagged off from users is a much easier interim step.

---
 Makefile                    |   1 +
 t/helper/test-fast-rebase.c | 211 ++++++++++++++++++++++++++++++++++++
 t/helper/test-tool.c        |   1 +
 t/helper/test-tool.h        |   1 +
 4 files changed, 214 insertions(+)
 create mode 100644 t/helper/test-fast-rebase.c

index 382fe73c76..24b9fecc0f 100644
@@ -704,6 +704,7 @@ TEST_BUILTINS_OBJS += test-dump-fsmonitor.o
 TEST_BUILTINS_OBJS += test-dump-split-index.o
 TEST_BUILTINS_OBJS += test-dump-untracked-cache.o
 TEST_BUILTINS_OBJS += test-example-decorate.o
+TEST_BUILTINS_OBJS += test-fast-rebase.o
 TEST_BUILTINS_OBJS += test-genrandom.o
 TEST_BUILTINS_OBJS += test-genzeros.o
 TEST_BUILTINS_OBJS += test-hash-speed.o

index a0d3966b29..8bce7db076 100644
@@ -28,6 +28,7 @@ static struct test_cmd cmds[] = {
 	{ "dump-split-index", cmd__dump_split_index },
 	{ "dump-untracked-cache", cmd__dump_untracked_cache },
 	{ "example-decorate", cmd__example_decorate },
+	{ "fast-rebase", cmd__fast_rebase },
 	{ "genrandom", cmd__genrandom },
 	{ "genzeros", cmd__genzeros },
 	{ "hashmap", cmd__hashmap },

index 07034d3f38..fd0cafe5ca 100644
@@ -18,6 +18,7 @@ int cmd__dump_fsmonitor(int argc, const char **argv);
 int cmd__dump_split_index(int argc, const char **argv);
 int cmd__dump_untracked_cache(int argc, const char **argv);
 int cmd__example_decorate(int argc, const char **argv);
+int cmd__fast_rebase(int argc, const char **argv);
 int cmd__genrandom(int argc, const char **argv);
 int cmd__genzeros(int argc, const char **argv);
 int cmd__hashmap(int argc, const char **argv);

gitgitgadget

From: Elijah Newren <[email protected]>

Allow the testsuite to run where it treats requests for "recursive" or the default merge algorithm via consulting the environment variable GIT_TEST_MERGE_ALGORITHM which is expected to either be "recursive" (the old traditional algorithm) or "ort" (the new algorithm).

Also, allow folks to pick the new algorithm via config setting. It turns out builtin/merge.c already had a way to allow users to specify a different default merge algorithm: pull.twohead. Rather odd configuration name (especially to be in the 'pull' namespace rather than 'merge') but it's there. Add that same configuration to rebase, cherry-pick, and revert.

This required updating the various callsites that called merge_trees() or merge_recursive() to conditionally call the new API, so this serves as another demonstration of what the new API looks and feels like. There are almost certainly some callsites that have not yet been modified to work with the new merge algorithm, but this represents the ones that I have been testing with thus far.

---
 builtin/merge.c  | 26 +++++++++++++++--
 builtin/rebase.c | 13 ++++++++-
 builtin/revert.c |  7 +++++
 sequencer.c      | 72 ++++++++++++++++++++++++++++++++++++++++--------
 sequencer.h      |  1 +
 5 files changed, 104 insertions(+), 15 deletions(-)

index 9d5359edc2..87dfc9bc06 100644
@@ -28,6 +28,7 @@
 #include "rerere.h"
 #include "help.h"
 #include "merge-recursive.h"
+#include "merge-ort-wrappers.h"
 #include "resolve-undo.h"
 #include "remote.h"
 #include "fmt-merge-msg.h"

@@ -88,6 +89,7 @@ static int no_verify;
 static struct strategy all_strategy[] = {
 	{ "recursive",  DEFAULT_TWOHEAD | NO_TRIVIAL },
 	{ "octopus",    DEFAULT_OCTOPUS },
+	{ "ort",        NO_TRIVIAL },
 	{ "resolve",    0 },
 	{ "ours",       NO_FAST_FORWARD | NO_TRIVIAL },
 	{ "subtree",    NO_FAST_FORWARD | NO_TRIVIAL },

@@ -159,10 +161,17 @@ static struct strategy *get_strategy(const char *name)
 	struct strategy *ret;
 	static struct cmdnames main_cmds, other_cmds;
 	static int loaded;
+	char *default_strategy = getenv("GIT_TEST_MERGE_ALGORITHM");
 
 	if (!name)
 		return NULL;
 
+	if (default_strategy &&
+	    !strcmp(default_strategy, "ort") &&
+	    !strcmp(name, "recursive")) {
+		name = "ort";
+	}
+
 	for (i = 0; i < ARRAY_SIZE(all_strategy); i++)
 		if (!strcmp(name, all_strategy[i].name))
 			return &all_strategy[i];

@@ -701,7 +710,8 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
 	if (refresh_and_write_cache(REFRESH_QUIET, SKIP_IF_UNCHANGED, 0) < 0)
 		return error(_("Unable to write index."));
 
-	if (!strcmp(strategy, "recursive") || !strcmp(strategy, "subtree")) {
+	if (!strcmp(strategy, "recursive") || !strcmp(strategy, "subtree") ||
+	    !strcmp(strategy, "ort")) {
 		struct lock_file lock = LOCK_INIT;
 		int clean, x;
 		struct commit *result;

@@ -732,8 +742,12 @@ static int try_merge_strategy(const char *strategy, struct commit_list *common,
 			commit_list_insert(j->item, &reversed);
 
 		hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
-		clean = merge_recursive(&o, head,
-				remoteheads->item, reversed, &result);
+		if (!strcmp(strategy, "ort"))
+			clean = merge_ort_recursive(&o, head, remoteheads->item,
+						    reversed, &result);
+		else
+			clean = merge_recursive(&o, head, remoteheads->item,
+						reversed, &result);
 		if (clean < 0)
 			exit(128);
 		if (write_locked_index(&the_index, &lock,

@@ -1264,6 +1278,12 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 	if (branch)
 		skip_prefix(branch, "refs/heads/", &branch);
 
+	if (!pull_twohead) {
+		char *default_strategy = getenv("GIT_TEST_MERGE_ALGORITHM");
+		if (default_strategy && !strcmp(default_strategy, "ort"))
+			pull_twohead = "ort";
+	}
+
 	init_diff_ui_defaults();
 	git_config(git_merge_config, NULL);
 

index eeca53382f..4ba5295ddf 100644
@@ -119,6 +119,7 @@ static struct replay_opts get_replay_opts(const struct rebase_options *opts)
 	struct replay_opts replay = REPLAY_OPTS_INIT;
 
 	replay.action = REPLAY_INTERACTIVE_REBASE;
+	replay.strategy = NULL;
 	sequencer_init_config(&replay);
 
 	replay.signoff = opts->signoff;

@@ -136,7 +137,12 @@ static struct replay_opts get_replay_opts(const struct rebase_options *opts)
 					opts->committer_date_is_author_date;
 	replay.ignore_date = opts->ignore_date;
 	replay.gpg_sign = xstrdup_or_null(opts->gpg_sign_opt);
-	replay.strategy = opts->strategy;
+	if (opts->strategy)
+		replay.strategy = opts->strategy;
+	else if (!replay.strategy && replay.default_strategy) {
+		replay.strategy = replay.default_strategy;
+		replay.default_strategy = NULL;
+	}
 
 	if (opts->strategy_opts)
 		parse_strategy_opts(&replay, opts->strategy_opts);

@@ -1771,6 +1777,11 @@ int cmd_rebase(int argc, const char **argv, const char *prefix)
 			    options.default_backend);
 	}
 
+	if (options.type == REBASE_MERGE &&
+	    !options.strategy &&
+	    getenv("GIT_TEST_MERGE_ALGORITHM"))
+		options.strategy = xstrdup(getenv("GIT_TEST_MERGE_ALGORITHM"));
+
 	switch (options.type) {
 	case REBASE_MERGE:
 	case REBASE_PRESERVE_MERGES:

index f61cc5d82c..5b01a9baca 100644
@@ -172,6 +172,11 @@ static int run_sequencer(int argc, const char **argv, struct replay_opts *opts)
 				NULL);
 	}
 
+	if (!opts->strategy && opts->default_strategy) {
+		opts->strategy = opts->default_strategy;
+		opts->default_strategy = NULL;
+	}
+
 	if (opts->allow_ff)
 		verify_opt_compatible(me, "--ff",
 				"--signoff", opts->signoff,

@@ -202,6 +207,8 @@ static int run_sequencer(int argc, const char **argv, struct replay_opts *opts)
 	/* These option values will be free()d */
 	opts->gpg_sign = xstrdup_or_null(opts->gpg_sign);
 	opts->strategy = xstrdup_or_null(opts->strategy);
+	if (!opts->strategy && getenv("GIT_TEST_MERGE_ALGORITHM"))
+		opts->strategy = xstrdup(getenv("GIT_TEST_MERGE_ALGORITHM"));
 
 	if (cmd == 'q') {
 		int ret = sequencer_remove_state(opts);

index b2a501e445..020b7fa118 100644
@@ -57,6 +57,7 @@ struct replay_opts {
 	int explicit_cleanup;
 
 	/* Merge strategy */
+	char *default_strategy;  /* from config options */
 	char *strategy;
 	char **xopts;
 	size_t xopts_nr, xopts_alloc;

gitgitgadget

Will replace. Thanks.