[PATCH 0/4] Beginning of new merge strategy: New API, empty implementation

[PATCH 0/4] Beginning of new merge strategy: New API, empty implementation

[Elijah Newren via GitGitGadget]

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

[PATCH 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 95571ee3fc..088770c2ae 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/merge-ort.c b/merge-ort.c
new file mode 100644
index 0000000000..5230364a8d
--- /dev/null
+++ b/merge-ort.c
@@ -0,0 +1,52 @@
+/*
+ * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short.  Meant
+ * as a drop-in replacement for the "recursive" merge strategy, allowing one
+ * to replace
+ *
+ *   git merge [-s recursive]
+ *
+ * with
+ *
+ *   git merge -s ort
+ *
+ * Note: git's parser allows the space between '-s' and its argument to be
+ * missing.  (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
+ * "cale", "peedy", or "ins" instead of "ort"?)
+ */
+
+#include "cache.h"
+#include "merge-ort.h"
+
+void merge_switch_to_result(struct merge_options *opt,
+			    struct tree *head,
+			    struct merge_result *result,
+			    int update_worktree_and_index,
+			    int display_update_msgs)
+{
+	die("Not yet implemented");
+	merge_finalize(opt, result);
+}
+
+void merge_finalize(struct merge_options *opt,
+		    struct merge_result *result)
+{
+	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)
+{
+	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)
+{
+	die("Not yet implemented");
+}
diff --git a/merge-ort.h b/merge-ort.h
new file mode 100644
index 0000000000..9c655cd3ad
--- /dev/null
+++ b/merge-ort.h
@@ -0,0 +1,49 @@
+#ifndef MERGE_ORT_H
+#define MERGE_ORT_H
+
+#include "merge-recursive.h"
+
+struct commit;
+struct tree;
+
+struct merge_result {
+	/* whether the merge is clean */
+	int clean;
+
+	/* Result of merge.  If !clean, represents what would go in worktree */
+	struct tree *tree;
+
+	/*
+	 * Additional metadata used by merge_switch_to_result() or future calls
+	 * to merge_inmemory_*().
+	 */
+	unsigned _;
+	void *priv;
+};
+
+/* rename-detecting three-way merge, no recursion. */
+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. */
+void merge_inmemory_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 */
+void merge_switch_to_result(struct merge_options *opt,
+			    struct tree *head,
+			    struct merge_result *result,
+			    int update_worktree_and_index,
+			    int display_update_msgs);
+
+/* Do needed cleanup when not calling merge_switch_to_result() */
+void merge_finalize(struct merge_options *opt,
+		    struct merge_result *result);
+
+#endif
-- 
gitgitgadget

[PATCH 2/4] merge-ort-wrappers: new convience wrappers to mimic the old merge API

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 088770c2ae..382fe73c76 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/merge-ort-wrappers.c b/merge-ort-wrappers.c
new file mode 100644
index 0000000000..e96c1a71be
--- /dev/null
+++ b/merge-ort-wrappers.c
@@ -0,0 +1,62 @@
+#include "cache.h"
+#include "merge-ort.h"
+#include "merge-ort-wrappers.h"
+
+#include "commit.h"
+
+static int unclean(struct merge_options *opt, struct tree *head)
+{
+	/* Sanity check on repo state; index must match head */
+	struct strbuf sb = STRBUF_INIT;
+
+	if (head && repo_index_has_changes(opt->repo, head, &sb)) {
+		fprintf(stderr, _("Your local changes to the following files would be overwritten by merge:\n  %s"),
+		    sb.buf);
+		strbuf_release(&sb);
+		return -1;
+	}
+
+	return 0;
+}
+
+int merge_ort_nonrecursive(struct merge_options *opt,
+			   struct tree *head,
+			   struct tree *merge,
+			   struct tree *merge_base)
+{
+	struct merge_result result;
+
+	if (unclean(opt, head))
+		return -1;
+
+	if (oideq(&merge_base->object.oid, &merge->object.oid)) {
+		printf(_("Already up to date!"));
+		return 1;
+	}
+
+	memset(&result, 0, sizeof(result));
+	merge_inmemory_nonrecursive(opt, merge_base, head, merge, &result);
+	merge_switch_to_result(opt, head, &result, 1, 1);
+
+	return result.clean;
+}
+
+int merge_ort_recursive(struct merge_options *opt,
+			struct commit *side1,
+			struct commit *side2,
+			struct commit_list *merge_bases,
+			struct commit **result)
+{
+	struct tree *head = repo_get_commit_tree(opt->repo, side1);
+	struct merge_result tmp;
+
+	if (unclean(opt, head))
+		return -1;
+
+	memset(&tmp, 0, sizeof(tmp));
+	merge_inmemory_recursive(opt, merge_bases, side1, side2, &tmp);
+	merge_switch_to_result(opt, head, &tmp, 1, 1);
+	*result = NULL;
+
+	return tmp.clean;
+}
diff --git a/merge-ort-wrappers.h b/merge-ort-wrappers.h
new file mode 100644
index 0000000000..0c4c57adbb
--- /dev/null
+++ b/merge-ort-wrappers.h
@@ -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

[PATCH 3/4] fast-rebase: demonstrate merge-ort's API via temporary/hidden command

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 382fe73c76..1b40d780fa 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/builtin.h b/builtin.h
index 53fb290963..75ff7dc8a9 100644
--- a/builtin.h
+++ b/builtin.h
@@ -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);
diff --git a/builtin/fast-rebase.c b/builtin/fast-rebase.c
new file mode 100644
index 0000000000..ae78a8b1c1
--- /dev/null
+++ b/builtin/fast-rebase.c
@@ -0,0 +1,210 @@
+/*
+ * "git fast-rebase" builtin command
+ *
+ * FAST: Forking Any Subprocesses (is) Taboo
+ *
+ * This is meant SOLELY as a demo of what is possible.  sequencer.c and
+ * rebase.c should be refactored to use the ideas here, rather than attempting
+ * to extend this file to replace those (unless Phillip or Dscho say that
+ * refactoring is too hard and we need a clean slate, but I'm guessing that
+ * refactoring is the better route).
+ */
+
+#define USE_THE_INDEX_COMPATIBILITY_MACROS
+#include "builtin.h"
+
+#include "cache-tree.h"
+#include "commit.h"
+#include "lockfile.h"
+#include "merge-ort.h"
+#include "refs.h"
+#include "revision.h"
+#include "sequencer.h"
+#include "strvec.h"
+#include "tree.h"
+
+static const char *short_commit_name(struct commit *commit)
+{
+	return find_unique_abbrev(&commit->object.oid, DEFAULT_ABBREV);
+}
+
+static struct commit *peel_committish(const char *name)
+{
+	struct object *obj;
+	struct object_id oid;
+
+	if (get_oid(name, &oid))
+		return NULL;
+	obj = parse_object(the_repository, &oid);
+	return (struct commit *)peel_to_type(name, 0, obj, OBJ_COMMIT);
+}
+
+static char *get_author(const char *message)
+{
+	size_t len;
+	const char *a;
+
+	a = find_commit_header(message, "author", &len);
+	if (a)
+		return xmemdupz(a, len);
+
+	return NULL;
+}
+
+static struct commit *create_commit(struct tree *tree,
+				    struct commit *based_on,
+				    struct commit *parent)
+{
+	struct object_id ret;
+	struct object *obj;
+	struct commit_list *parents = NULL;
+	char *author;
+	char *sign_commit = NULL;
+	struct commit_extra_header *extra;
+	struct strbuf msg = STRBUF_INIT;
+	const char *out_enc = get_commit_output_encoding();
+	const char *message = logmsg_reencode(based_on, NULL, out_enc);
+	const char *orig_message = NULL;
+	const char *exclude_gpgsig[] = { "gpgsig", NULL };
+
+	commit_list_insert(parent, &parents);
+	extra = read_commit_extra_headers(based_on, exclude_gpgsig);
+	find_commit_subject(message, &orig_message);
+	strbuf_addstr(&msg, orig_message);
+	author = get_author(message);
+	reset_ident_date();
+	if (commit_tree_extended(msg.buf, msg.len, &tree->object.oid, parents,
+				 &ret, author, NULL, sign_commit, extra)) {
+		error(_("failed to write commit object"));
+		return NULL;
+	}
+	free(author);
+	strbuf_release(&msg);
+
+	obj = parse_object(the_repository, &ret);
+	return (struct commit *)obj;
+}
+
+int cmd_fast_rebase(int argc, const char **argv, const char *prefix)
+{
+	struct commit *onto;
+	struct commit *last_commit = NULL, *last_picked_commit = NULL;
+	struct object_id head;
+	struct lock_file lock = LOCK_INIT;
+	int clean = 1;
+	struct strvec rev_walk_args = STRVEC_INIT;
+	struct rev_info revs;
+	struct commit *commit;
+	struct merge_options merge_opt;
+	struct tree *next_tree, *base_tree, *head_tree;
+	struct merge_result result;
+	struct strbuf reflog_msg = STRBUF_INIT;
+	struct strbuf branch_name = STRBUF_INIT;
+
+	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");
+
+	onto = peel_committish(argv[2]);
+	strbuf_addf(&branch_name, "refs/heads/%s", argv[4]);
+
+	/* Sanity check */
+	if (get_oid("HEAD", &head))
+		die(_("Cannot read HEAD"));
+	assert(oideq(&onto->object.oid, &head));
+
+	hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
+	assert(repo_read_index(the_repository) >= 0);
+
+	repo_init_revisions(the_repository, &revs, NULL);
+	revs.verbose_header = 1;
+	revs.max_parents = 1;
+	revs.cherry_mark = 1;
+	revs.limited = 1;
+	revs.reverse = 1;
+	revs.right_only = 1;
+	revs.sort_order = REV_SORT_IN_GRAPH_ORDER;
+	revs.topo_order = 1;
+	strvec_pushl(&rev_walk_args, "", argv[4], "--not", argv[3], NULL);
+
+	if (setup_revisions(rev_walk_args.nr, rev_walk_args.v, &revs, NULL) > 1)
+		return error(_("unhandled options"));
+
+	strvec_clear(&rev_walk_args);
+
+	if (prepare_revision_walk(&revs) < 0)
+		return error(_("error preparing revisions"));
+
+	init_merge_options(&merge_opt, the_repository);
+	memset(&result, 0, sizeof(result));
+	merge_opt.show_rename_progress = 1;
+	merge_opt.branch1 = "HEAD";
+	head_tree = get_commit_tree(onto);
+	result.tree = head_tree;
+	last_commit = onto;
+	while ((commit = get_revision(&revs))) {
+		struct commit *base;
+
+		fprintf(stderr, "Rebasing %s...\r",
+			oid_to_hex(&commit->object.oid));
+		assert(commit->parents && !commit->parents->next);
+		base = commit->parents->item;
+
+		next_tree = get_commit_tree(commit);
+		base_tree = get_commit_tree(base);
+
+		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);
+
+		free((char*)merge_opt.ancestor);
+		merge_opt.ancestor = NULL;
+		if (!result.clean)
+			die("Aborting: Hit a conflict and restarting is not implemented.");
+		last_picked_commit = commit;
+		last_commit = create_commit(result.tree, commit, last_commit);
+	}
+	fprintf(stderr, "\nDone.\n");
+	/* TODO: There should be some kind of rev_info_free(&revs) call... */
+	memset(&revs, 0, sizeof(revs));
+
+	merge_switch_to_result(&merge_opt, head_tree, &result, 1, !result.clean);
+
+	if (result.clean < 0)
+		exit(128);
+
+	strbuf_addf(&reflog_msg, "finish rebase %s onto %s",
+		    oid_to_hex(&last_picked_commit->object.oid),
+		    oid_to_hex(&last_commit->object.oid));
+	if (update_ref(reflog_msg.buf, branch_name.buf,
+		       &last_commit->object.oid,
+		       &last_picked_commit->object.oid,
+		       REF_NO_DEREF, UPDATE_REFS_MSG_ON_ERR)) {
+		error(_("could not update %s"), argv[4]);
+		die("Failed to update %s", argv[4]);
+	}
+	if (create_symref("HEAD", branch_name.buf, reflog_msg.buf) < 0)
+		die(_("unable to update HEAD"));
+	strbuf_release(&reflog_msg);
+	strbuf_release(&branch_name);
+
+	prime_cache_tree(the_repository, the_repository->index, result.tree);
+	if (write_locked_index(&the_index, &lock,
+			       COMMIT_LOCK | SKIP_IF_UNCHANGED))
+		die(_("unable to write %s"), get_index_file());
+	return (clean == 0);
+}
diff --git a/git.c b/git.c
index 4bdcdad2cc..af84f11e69 100644
--- a/git.c
+++ b/git.c
@@ -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

[PATCH 4/4] merge,rebase,revert: select ort or recursive by config or environment

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 builtin/merge.c  | 26 ++++++++++++++++--
 builtin/rebase.c |  9 +++++-
 builtin/revert.c |  2 ++
 sequencer.c      | 71 ++++++++++++++++++++++++++++++++++++++++--------
 4 files changed, 93 insertions(+), 15 deletions(-)

diff --git a/builtin/merge.c b/builtin/merge.c
index 9d5359edc2..87dfc9bc06 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -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);
 
diff --git a/builtin/rebase.c b/builtin/rebase.c
index eeca53382f..9719aa25da 100644
--- a/builtin/rebase.c
+++ b/builtin/rebase.c
@@ -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:
diff --git a/builtin/revert.c b/builtin/revert.c
index f61cc5d82c..c7cb0c1a18 100644
--- a/builtin/revert.c
+++ b/builtin/revert.c
@@ -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);
diff --git a/sequencer.c b/sequencer.c
index 00acb12496..163475ae31 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -14,7 +14,8 @@
 #include "diff.h"
 #include "revision.h"
 #include "rerere.h"
-#include "merge-recursive.h"
+#include "merge-ort.h"
+#include "merge-ort-wrappers.h"
 #include "refs.h"
 #include "strvec.h"
 #include "quote.h"
@@ -204,6 +205,20 @@ static int git_sequencer_config(const char *k, const char *v, void *cb)
 		return 0;
 	}
 
+	if (!opts->strategy && !strcmp(k, "pull.twohead")) {
+		int ret = git_config_string((const char**)&opts->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, ' ');
+			if (tmp)
+				*tmp = '\0';
+		}
+		return ret;
+	}
+
 	status = git_gpg_config(k, v, NULL);
 	if (status)
 		return status;
@@ -595,8 +610,9 @@ static int do_recursive_merge(struct repository *r,
 			      struct replay_opts *opts)
 {
 	struct merge_options o;
+	struct merge_result result;
 	struct tree *next_tree, *base_tree, *head_tree;
-	int clean;
+	int clean, show_output;
 	int i;
 	struct lock_file index_lock = LOCK_INIT;
 
@@ -620,12 +636,27 @@ static int do_recursive_merge(struct repository *r,
 	for (i = 0; i < opts->xopts_nr; i++)
 		parse_merge_opt(&o, opts->xopts[i]);
 
-	clean = merge_trees(&o,
-			    head_tree,
-			    next_tree, base_tree);
-	if (is_rebase_i(opts) && clean <= 0)
-		fputs(o.obuf.buf, stdout);
-	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,
+					    &result);
+		show_output = !is_rebase_i(opts) || !result.clean;
+		/*
+		 * TODO: merge_switch_to_result will update index/working tree;
+		 * we only really want to do that if !result.clean || this is
+		 * the final patch to be picked.  But determining this is the
+		 * final patch would take some work, and "head_tree" would need
+		 * to be replace with the tree the index matched before we
+		 * started doing any picks.
+		 */
+		merge_switch_to_result(&o, head_tree, &result, 1, show_output);
+		clean = result.clean;
+	} else {
+		clean = merge_trees(&o, head_tree, next_tree, base_tree);
+		if (is_rebase_i(opts) && clean <= 0)
+			fputs(o.obuf.buf, stdout);
+		strbuf_release(&o.obuf);
+	}
 	if (clean < 0) {
 		rollback_lock_file(&index_lock);
 		return clean;
@@ -1991,7 +2022,10 @@ static int do_pick_commit(struct repository *r,
 
 	if (is_rebase_i(opts) && write_author_script(msg.message) < 0)
 		res = -1;
-	else if (!opts->strategy || !strcmp(opts->strategy, "recursive") || command == TODO_REVERT) {
+	else if (!opts->strategy ||
+		 !strcmp(opts->strategy, "recursive") ||
+		 !strcmp(opts->strategy, "ort") ||
+		 command == TODO_REVERT) {
 		res = do_recursive_merge(r, base, next, base_label, next_label,
 					 &head, &msgbuf, opts);
 		if (res < 0)
@@ -3485,7 +3519,9 @@ static int do_merge(struct repository *r,
 	struct commit_list *bases, *j, *reversed = NULL;
 	struct commit_list *to_merge = NULL, **tail = &to_merge;
 	const char *strategy = !opts->xopts_nr &&
-		(!opts->strategy || !strcmp(opts->strategy, "recursive")) ?
+		(!opts->strategy ||
+		 !strcmp(opts->strategy, "recursive") ||
+		 !strcmp(opts->strategy, "ort")) ?
 		NULL : opts->strategy;
 	struct merge_options o;
 	int merge_arg_len, oneline_offset, can_fast_forward, ret, k;
@@ -3722,7 +3758,20 @@ static int do_merge(struct repository *r,
 	o.branch2 = ref_name.buf;
 	o.buffer_output = 2;
 
-	ret = merge_recursive(&o, head_commit, merge_commit, reversed, &i);
+	if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+		/*
+		 * TODO: Should use merge_inmemory_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.
+		 */
+		ret = merge_ort_recursive(&o,
+					  head_commit, merge_commit, reversed,
+					  &i);
+	} else {
+		ret = merge_recursive(&o, head_commit, merge_commit, reversed,
+				      &i);
+	}
 	if (ret <= 0)
 		fputs(o.obuf.buf, stdout);
 	strbuf_release(&o.obuf);
-- 
gitgitgadget

Re: [PATCH 0/4] Beginning of new merge strategy: New API, empty implementation

[Elijah Newren]

Hi,

On Wed, Oct 21, 2020 at 6:22 AM Elijah Newren via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> 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:

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

Re: [PATCH 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Taylor Blau]

On Wed, Oct 21, 2020 at 01:22:32PM +0000, Elijah Newren via GitGitGadget wrote:
> From: Elijah Newren <newren@gmail.com>
>
> 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.
>
> Signed-off-by: Elijah Newren <newren@gmail.com>
> ---
>  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
>
> diff --git a/Makefile b/Makefile
> index 95571ee3fc..088770c2ae 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -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
> diff --git a/merge-ort.c b/merge-ort.c
> new file mode 100644
> index 0000000000..5230364a8d
> --- /dev/null
> +++ b/merge-ort.c
> @@ -0,0 +1,52 @@
> +/*
> + * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short.  Meant
> + * as a drop-in replacement for the "recursive" merge strategy, allowing one
> + * to replace
> + *
> + *   git merge [-s recursive]
> + *
> + * with
> + *
> + *   git merge -s ort
> + *
> + * Note: git's parser allows the space between '-s' and its argument to be
> + * missing.  (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
> + * "cale", "peedy", or "ins" instead of "ort"?)
> + */

One thing that might be good here (and I realize that you sort of get to
it in your next patch) is some example usage. Maybe it's good enough to
say "see the $FILE_MODIFIED_BY_NEXT_PATCH for example usage", but it may
be good to be a little bit clearer here.

Perhaps it may even be appropriate to add a
Documentation/technical/api-merge-ort.txt or something (if you haven't
already in one of your other branches...).

> +
> +#include "cache.h"
> +#include "merge-ort.h"
> +
> +void merge_switch_to_result(struct merge_options *opt,
> +			    struct tree *head,
> +			    struct merge_result *result,
> +			    int update_worktree_and_index,
> +			    int display_update_msgs)
> +{
> +	die("Not yet implemented");
> +	merge_finalize(opt, result);
> +}
> +
> +void merge_finalize(struct merge_options *opt,
> +		    struct merge_result *result)
> +{
> +	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)
> +{
> +	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)
> +{
> +	die("Not yet implemented");
> +}
> diff --git a/merge-ort.h b/merge-ort.h
> new file mode 100644
> index 0000000000..9c655cd3ad
> --- /dev/null
> +++ b/merge-ort.h
> @@ -0,0 +1,49 @@
> +#ifndef MERGE_ORT_H
> +#define MERGE_ORT_H
> +
> +#include "merge-recursive.h"
> +
> +struct commit;
> +struct tree;
> +
> +struct merge_result {
> +	/* whether the merge is clean */
> +	int clean;
> +
> +	/* Result of merge.  If !clean, represents what would go in worktree */
> +	struct tree *tree;
> +
> +	/*
> +	 * Additional metadata used by merge_switch_to_result() or future calls
> +	 * to merge_inmemory_*().
> +	 */
> +	unsigned _;

I was a little surprised that '_' is allowed, since I can't think of any
other variable that is called that (and a search with "git grep ' _;' --
**/*.h" confirms that this is the only one. It does compile with
DEVELOPER=1, so...

Is this meant to be a flags-like? I believe you that it's necessary, but
I wonder if it could be named more clearly, even though it's private.

> +	void *priv;
> +};
> +
> +/* rename-detecting three-way merge, no recursion. */
> +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. */
> +void merge_inmemory_nonrecursive(struct merge_options *opt,
> +				 struct tree *merge_base,
> +				 struct tree *side1,
> +				 struct tree *side2,
> +				 struct merge_result *result);

Good. This API looks sane to me, and contains nothing more nor less than
I'd expect. I appreciate that the _recursive declaration is separate
from the _nonrecursive one (and not hidden behind a flag that switches
between the two).

> +/* Update the working tree and index from head to result after inmemory merge */
> +void merge_switch_to_result(struct merge_options *opt,
> +			    struct tree *head,
> +			    struct merge_result *result,
> +			    int update_worktree_and_index,
> +			    int display_update_msgs);

Seems like these last two could probably be made into an enum and passed
as flags instead of adding more parameters on the end.

> +/* Do needed cleanup when not calling merge_switch_to_result() */
> +void merge_finalize(struct merge_options *opt,
> +		    struct merge_result *result);
> +
> +#endif
> --
> gitgitgadget
>
Thanks,
Taylor

Re: [PATCH 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Elijah Newren]

On Fri, Oct 23, 2020 at 11:12 AM Taylor Blau <me@ttaylorr.com> wrote:
>
> On Wed, Oct 21, 2020 at 01:22:32PM +0000, Elijah Newren via GitGitGadget wrote:
> > From: Elijah Newren <newren@gmail.com>
> >
> > 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.
> >
> > Signed-off-by: Elijah Newren <newren@gmail.com>
> > ---
> >  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
> >
> > diff --git a/Makefile b/Makefile
> > index 95571ee3fc..088770c2ae 100644
> > --- a/Makefile
> > +++ b/Makefile
> > @@ -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
> > diff --git a/merge-ort.c b/merge-ort.c
> > new file mode 100644
> > index 0000000000..5230364a8d
> > --- /dev/null
> > +++ b/merge-ort.c
> > @@ -0,0 +1,52 @@
> > +/*
> > + * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short.  Meant
> > + * as a drop-in replacement for the "recursive" merge strategy, allowing one
> > + * to replace
> > + *
> > + *   git merge [-s recursive]
> > + *
> > + * with
> > + *
> > + *   git merge -s ort
> > + *
> > + * Note: git's parser allows the space between '-s' and its argument to be
> > + * missing.  (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
> > + * "cale", "peedy", or "ins" instead of "ort"?)
> > + */
>
> One thing that might be good here (and I realize that you sort of get to
> it in your next patch) is some example usage. Maybe it's good enough to

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.

> say "see the $FILE_MODIFIED_BY_NEXT_PATCH for example usage", but it may
> be good to be a little bit clearer here.

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

> Perhaps it may even be appropriate to add a
> Documentation/technical/api-merge-ort.txt or something (if you haven't
> already in one of your other branches...).

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.

> > +
> > +#include "cache.h"
> > +#include "merge-ort.h"
> > +
> > +void merge_switch_to_result(struct merge_options *opt,
> > +                         struct tree *head,
> > +                         struct merge_result *result,
> > +                         int update_worktree_and_index,
> > +                         int display_update_msgs)
> > +{
> > +     die("Not yet implemented");
> > +     merge_finalize(opt, result);
> > +}
> > +
> > +void merge_finalize(struct merge_options *opt,
> > +                 struct merge_result *result)
> > +{
> > +     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)
> > +{
> > +     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)
> > +{
> > +     die("Not yet implemented");
> > +}
> > diff --git a/merge-ort.h b/merge-ort.h
> > new file mode 100644
> > index 0000000000..9c655cd3ad
> > --- /dev/null
> > +++ b/merge-ort.h
> > @@ -0,0 +1,49 @@
> > +#ifndef MERGE_ORT_H
> > +#define MERGE_ORT_H
> > +
> > +#include "merge-recursive.h"
> > +
> > +struct commit;
> > +struct tree;
> > +
> > +struct merge_result {
> > +     /* whether the merge is clean */
> > +     int clean;
> > +
> > +     /* Result of merge.  If !clean, represents what would go in worktree */
> > +     struct tree *tree;
> > +
> > +     /*
> > +      * Additional metadata used by merge_switch_to_result() or future calls
> > +      * to merge_inmemory_*().
> > +      */
> > +     unsigned _;
>
> I was a little surprised that '_' is allowed, since I can't think of any
> other variable that is called that (and a search with "git grep ' _;' --
> **/*.h" confirms that this is the only one. It does compile with
> DEVELOPER=1, so...
>
> Is this meant to be a flags-like? I believe you that it's necessary, but
> I wonder if it could be named more clearly, even though it's private.

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.

>
> > +     void *priv;
> > +};
> > +
> > +/* rename-detecting three-way merge, no recursion. */
> > +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. */
> > +void merge_inmemory_nonrecursive(struct merge_options *opt,
> > +                              struct tree *merge_base,
> > +                              struct tree *side1,
> > +                              struct tree *side2,
> > +                              struct merge_result *result);
>
> Good. This API looks sane to me, and contains nothing more nor less than
> I'd expect. I appreciate that the _recursive declaration is separate
> from the _nonrecursive one (and not hidden behind a flag that switches
> between the two).
>
> > +/* Update the working tree and index from head to result after inmemory merge */
> > +void merge_switch_to_result(struct merge_options *opt,
> > +                         struct tree *head,
> > +                         struct merge_result *result,
> > +                         int update_worktree_and_index,
> > +                         int display_update_msgs);
>
> Seems like these last two could probably be made into an enum and passed
> as flags instead of adding more parameters on the end.

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.

> > +/* Do needed cleanup when not calling merge_switch_to_result() */
> > +void merge_finalize(struct merge_options *opt,
> > +                 struct merge_result *result);
> > +
> > +#endif
> > --
> > gitgitgadget

Re: [PATCH 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Peter Baumann]

Am Do., 22. Okt. 2020 um 03:28 Uhr schrieb Elijah Newren via
GitGitGadget <gitgitgadget@gmail.com>:
[... snipping a lot of unneeded context ...]
> diff --git a/merge-ort.h b/merge-ort.h
> new file mode 100644
> index 0000000000..9c655cd3ad
> --- /dev/null
> +++ b/merge-ort.h
> @@ -0,0 +1,49 @@
> +#ifndef MERGE_ORT_H
> +#define MERGE_ORT_H
> +
> +#include "merge-recursive.h"
> +
> +struct commit;
> +struct tree;
> +
> +struct merge_result {
> +       /* whether the merge is clean */
> +       int clean;
> +
> +       /* Result of merge.  If !clean, represents what would go in worktree */
> +       struct tree *tree;
> +
> +       /*
> +        * Additional metadata used by merge_switch_to_result() or future calls
> +        * to merge_inmemory_*().
> +        */
> +       unsigned _;
> +       void *priv;
> +};
> +
> +/* rename-detecting three-way merge, no recursion. */
                                                                   ^^^^^^^^^^^^^
> +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. */
                                                                  ^^^^^^^^^^^^^
> +void merge_inmemory_nonrecursive(struct merge_options *opt,
                                            ^^^^^^^^^^^^
> +                                struct tree *merge_base,
> +                                struct tree *side1,
> +                                struct tree *side2,
> +                                struct merge_result *result);
> +

The comments don't fit to the actually method name. I assume they
should be switched?

-Peter

Re: [PATCH 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Elijah Newren]

On Sat, Oct 24, 2020 at 3:57 AM Peter Baumann <peter.baumann@gmail.com> wrote:
>
> Am Sa., 24. Okt. 2020 um 11:58 Uhr schrieb Peter Baumann <peter.baumann@gmail.com>:
>>>
>>> Am Do., 22. Okt. 2020 um 03:28 Uhr schrieb Elijah Newren via GitGitGadget <gitgitgadget@gmail.com>:
>>> [... ]
>>>>
>>>> diff --git a/merge-ort.h b/merge-ort.h
>>>> new file mode 100644
>>>> index 0000000000..9c655cd3ad
>>>> --- /dev/null
>>>> +++ b/merge-ort.h
>>>> @@ -0,0 +1,49 @@
>>>> +#ifndef MERGE_ORT_H
>>>> +#define MERGE_ORT_H
>>>> +
>>>> +#include "merge-recursive.h"
>>>> +
>>>> +struct commit;
>>>> +struct tree;
>>>> +
>>>> +struct merge_result {
>>>> +       /* whether the merge is clean */
>>>> +       int clean;
>>>> +
>>>> +       /* Result of merge.  If !clean, represents what would go in worktree */
>>>> +       struct tree *tree;
>>>> +
>>>> +       /*
>>>> +        * Additional metadata used by merge_switch_to_result() or future calls
>>>> +        * to merge_inmemory_*().
>>>> +        */
>>>> +       unsigned _;
>>>> +       void *priv;
>>>> +};
>>>> +
>>>> +/* rename-detecting three-way merge, no recursion. */
>>>
>>>                                                                     ^^^^^^^^^^^^
>>>>
>>>> +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. */
>>>
>>>                                                                    ^^^^^^^^^^^^^^^^^^^^^^
>>>>
>>>> +void merge_inmemory_nonrecursive(struct merge_options *opt,
>>>
>>>                                             ^^^^^^^^^^^^^
>>>>
>>>> +                                struct tree *merge_base,
>>>> +                                struct tree *side1,
>>>> +                                struct tree *side2,
>>>> +                                struct merge_result *result);
>>>> +
>>>> [...]
>>>
>>>
>>> Looks like the comments above don't match the method names they are describing.
>>> I assume they should be just switched?

Whoops, indeed.  Will fix; thanks for spotting.

>>>
>>> -Peter
>>>
> Sorry, I completely messed up the markers. Serves me well for not using a fixed with font.
> Here it is again, highlighting only the relevant section:
>
> > +/* rename-detecting three-way merge, no recursion. */
>                                         ^^^^^^^^^^^^^
> > +void merge_inmemory_recursive(struct merge_options *opt,
>                        ^^^^^^^^^
>
> [...]
> > +/* rename-detecting three-way merge with recursive ancestor consolidation. */
>                                  ^^^^^^^^^^^^^^^^^^^^^^
> > +void merge_inmemory_nonrecursive(struct merge_options *opt,
>                        ^^^^^^^^^^^^
>
>

[PATCH v2 0/4] Beginning of new merge strategy: New API, empty implementation

[Elijah Newren via GitGitGadget]

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.
     +
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
       ## 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

[PATCH v2 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 95571ee3fc..088770c2ae 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/merge-ort.c b/merge-ort.c
new file mode 100644
index 0000000000..5230364a8d
--- /dev/null
+++ b/merge-ort.c
@@ -0,0 +1,52 @@
+/*
+ * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short.  Meant
+ * as a drop-in replacement for the "recursive" merge strategy, allowing one
+ * to replace
+ *
+ *   git merge [-s recursive]
+ *
+ * with
+ *
+ *   git merge -s ort
+ *
+ * Note: git's parser allows the space between '-s' and its argument to be
+ * missing.  (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
+ * "cale", "peedy", or "ins" instead of "ort"?)
+ */
+
+#include "cache.h"
+#include "merge-ort.h"
+
+void merge_switch_to_result(struct merge_options *opt,
+			    struct tree *head,
+			    struct merge_result *result,
+			    int update_worktree_and_index,
+			    int display_update_msgs)
+{
+	die("Not yet implemented");
+	merge_finalize(opt, result);
+}
+
+void merge_finalize(struct merge_options *opt,
+		    struct merge_result *result)
+{
+	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)
+{
+	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)
+{
+	die("Not yet implemented");
+}
diff --git a/merge-ort.h b/merge-ort.h
new file mode 100644
index 0000000000..47d30cf538
--- /dev/null
+++ b/merge-ort.h
@@ -0,0 +1,49 @@
+#ifndef MERGE_ORT_H
+#define MERGE_ORT_H
+
+#include "merge-recursive.h"
+
+struct commit;
+struct tree;
+
+struct merge_result {
+	/* whether the merge is clean */
+	int clean;
+
+	/* Result of merge.  If !clean, represents what would go in worktree */
+	struct tree *tree;
+
+	/*
+	 * Additional metadata used by merge_switch_to_result() or future calls
+	 * to merge_inmemory_*().  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, no recursion. */
+void merge_inmemory_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 */
+void merge_switch_to_result(struct merge_options *opt,
+			    struct tree *head,
+			    struct merge_result *result,
+			    int update_worktree_and_index,
+			    int display_update_msgs);
+
+/* Do needed cleanup when not calling merge_switch_to_result() */
+void merge_finalize(struct merge_options *opt,
+		    struct merge_result *result);
+
+#endif
-- 
gitgitgadget

[PATCH v2 2/4] merge-ort-wrappers: new convience wrappers to mimic the old merge API

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 088770c2ae..382fe73c76 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/merge-ort-wrappers.c b/merge-ort-wrappers.c
new file mode 100644
index 0000000000..e96c1a71be
--- /dev/null
+++ b/merge-ort-wrappers.c
@@ -0,0 +1,62 @@
+#include "cache.h"
+#include "merge-ort.h"
+#include "merge-ort-wrappers.h"
+
+#include "commit.h"
+
+static int unclean(struct merge_options *opt, struct tree *head)
+{
+	/* Sanity check on repo state; index must match head */
+	struct strbuf sb = STRBUF_INIT;
+
+	if (head && repo_index_has_changes(opt->repo, head, &sb)) {
+		fprintf(stderr, _("Your local changes to the following files would be overwritten by merge:\n  %s"),
+		    sb.buf);
+		strbuf_release(&sb);
+		return -1;
+	}
+
+	return 0;
+}
+
+int merge_ort_nonrecursive(struct merge_options *opt,
+			   struct tree *head,
+			   struct tree *merge,
+			   struct tree *merge_base)
+{
+	struct merge_result result;
+
+	if (unclean(opt, head))
+		return -1;
+
+	if (oideq(&merge_base->object.oid, &merge->object.oid)) {
+		printf(_("Already up to date!"));
+		return 1;
+	}
+
+	memset(&result, 0, sizeof(result));
+	merge_inmemory_nonrecursive(opt, merge_base, head, merge, &result);
+	merge_switch_to_result(opt, head, &result, 1, 1);
+
+	return result.clean;
+}
+
+int merge_ort_recursive(struct merge_options *opt,
+			struct commit *side1,
+			struct commit *side2,
+			struct commit_list *merge_bases,
+			struct commit **result)
+{
+	struct tree *head = repo_get_commit_tree(opt->repo, side1);
+	struct merge_result tmp;
+
+	if (unclean(opt, head))
+		return -1;
+
+	memset(&tmp, 0, sizeof(tmp));
+	merge_inmemory_recursive(opt, merge_bases, side1, side2, &tmp);
+	merge_switch_to_result(opt, head, &tmp, 1, 1);
+	*result = NULL;
+
+	return tmp.clean;
+}
diff --git a/merge-ort-wrappers.h b/merge-ort-wrappers.h
new file mode 100644
index 0000000000..0c4c57adbb
--- /dev/null
+++ b/merge-ort-wrappers.h
@@ -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

[PATCH v2 3/4] fast-rebase: demonstrate merge-ort's API via temporary/hidden command

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 382fe73c76..1b40d780fa 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/builtin.h b/builtin.h
index 53fb290963..75ff7dc8a9 100644
--- a/builtin.h
+++ b/builtin.h
@@ -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);
diff --git a/builtin/fast-rebase.c b/builtin/fast-rebase.c
new file mode 100644
index 0000000000..ae78a8b1c1
--- /dev/null
+++ b/builtin/fast-rebase.c
@@ -0,0 +1,210 @@
+/*
+ * "git fast-rebase" builtin command
+ *
+ * FAST: Forking Any Subprocesses (is) Taboo
+ *
+ * This is meant SOLELY as a demo of what is possible.  sequencer.c and
+ * rebase.c should be refactored to use the ideas here, rather than attempting
+ * to extend this file to replace those (unless Phillip or Dscho say that
+ * refactoring is too hard and we need a clean slate, but I'm guessing that
+ * refactoring is the better route).
+ */
+
+#define USE_THE_INDEX_COMPATIBILITY_MACROS
+#include "builtin.h"
+
+#include "cache-tree.h"
+#include "commit.h"
+#include "lockfile.h"
+#include "merge-ort.h"
+#include "refs.h"
+#include "revision.h"
+#include "sequencer.h"
+#include "strvec.h"
+#include "tree.h"
+
+static const char *short_commit_name(struct commit *commit)
+{
+	return find_unique_abbrev(&commit->object.oid, DEFAULT_ABBREV);
+}
+
+static struct commit *peel_committish(const char *name)
+{
+	struct object *obj;
+	struct object_id oid;
+
+	if (get_oid(name, &oid))
+		return NULL;
+	obj = parse_object(the_repository, &oid);
+	return (struct commit *)peel_to_type(name, 0, obj, OBJ_COMMIT);
+}
+
+static char *get_author(const char *message)
+{
+	size_t len;
+	const char *a;
+
+	a = find_commit_header(message, "author", &len);
+	if (a)
+		return xmemdupz(a, len);
+
+	return NULL;
+}
+
+static struct commit *create_commit(struct tree *tree,
+				    struct commit *based_on,
+				    struct commit *parent)
+{
+	struct object_id ret;
+	struct object *obj;
+	struct commit_list *parents = NULL;
+	char *author;
+	char *sign_commit = NULL;
+	struct commit_extra_header *extra;
+	struct strbuf msg = STRBUF_INIT;
+	const char *out_enc = get_commit_output_encoding();
+	const char *message = logmsg_reencode(based_on, NULL, out_enc);
+	const char *orig_message = NULL;
+	const char *exclude_gpgsig[] = { "gpgsig", NULL };
+
+	commit_list_insert(parent, &parents);
+	extra = read_commit_extra_headers(based_on, exclude_gpgsig);
+	find_commit_subject(message, &orig_message);
+	strbuf_addstr(&msg, orig_message);
+	author = get_author(message);
+	reset_ident_date();
+	if (commit_tree_extended(msg.buf, msg.len, &tree->object.oid, parents,
+				 &ret, author, NULL, sign_commit, extra)) {
+		error(_("failed to write commit object"));
+		return NULL;
+	}
+	free(author);
+	strbuf_release(&msg);
+
+	obj = parse_object(the_repository, &ret);
+	return (struct commit *)obj;
+}
+
+int cmd_fast_rebase(int argc, const char **argv, const char *prefix)
+{
+	struct commit *onto;
+	struct commit *last_commit = NULL, *last_picked_commit = NULL;
+	struct object_id head;
+	struct lock_file lock = LOCK_INIT;
+	int clean = 1;
+	struct strvec rev_walk_args = STRVEC_INIT;
+	struct rev_info revs;
+	struct commit *commit;
+	struct merge_options merge_opt;
+	struct tree *next_tree, *base_tree, *head_tree;
+	struct merge_result result;
+	struct strbuf reflog_msg = STRBUF_INIT;
+	struct strbuf branch_name = STRBUF_INIT;
+
+	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");
+
+	onto = peel_committish(argv[2]);
+	strbuf_addf(&branch_name, "refs/heads/%s", argv[4]);
+
+	/* Sanity check */
+	if (get_oid("HEAD", &head))
+		die(_("Cannot read HEAD"));
+	assert(oideq(&onto->object.oid, &head));
+
+	hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
+	assert(repo_read_index(the_repository) >= 0);
+
+	repo_init_revisions(the_repository, &revs, NULL);
+	revs.verbose_header = 1;
+	revs.max_parents = 1;
+	revs.cherry_mark = 1;
+	revs.limited = 1;
+	revs.reverse = 1;
+	revs.right_only = 1;
+	revs.sort_order = REV_SORT_IN_GRAPH_ORDER;
+	revs.topo_order = 1;
+	strvec_pushl(&rev_walk_args, "", argv[4], "--not", argv[3], NULL);
+
+	if (setup_revisions(rev_walk_args.nr, rev_walk_args.v, &revs, NULL) > 1)
+		return error(_("unhandled options"));
+
+	strvec_clear(&rev_walk_args);
+
+	if (prepare_revision_walk(&revs) < 0)
+		return error(_("error preparing revisions"));
+
+	init_merge_options(&merge_opt, the_repository);
+	memset(&result, 0, sizeof(result));
+	merge_opt.show_rename_progress = 1;
+	merge_opt.branch1 = "HEAD";
+	head_tree = get_commit_tree(onto);
+	result.tree = head_tree;
+	last_commit = onto;
+	while ((commit = get_revision(&revs))) {
+		struct commit *base;
+
+		fprintf(stderr, "Rebasing %s...\r",
+			oid_to_hex(&commit->object.oid));
+		assert(commit->parents && !commit->parents->next);
+		base = commit->parents->item;
+
+		next_tree = get_commit_tree(commit);
+		base_tree = get_commit_tree(base);
+
+		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);
+
+		free((char*)merge_opt.ancestor);
+		merge_opt.ancestor = NULL;
+		if (!result.clean)
+			die("Aborting: Hit a conflict and restarting is not implemented.");
+		last_picked_commit = commit;
+		last_commit = create_commit(result.tree, commit, last_commit);
+	}
+	fprintf(stderr, "\nDone.\n");
+	/* TODO: There should be some kind of rev_info_free(&revs) call... */
+	memset(&revs, 0, sizeof(revs));
+
+	merge_switch_to_result(&merge_opt, head_tree, &result, 1, !result.clean);
+
+	if (result.clean < 0)
+		exit(128);
+
+	strbuf_addf(&reflog_msg, "finish rebase %s onto %s",
+		    oid_to_hex(&last_picked_commit->object.oid),
+		    oid_to_hex(&last_commit->object.oid));
+	if (update_ref(reflog_msg.buf, branch_name.buf,
+		       &last_commit->object.oid,
+		       &last_picked_commit->object.oid,
+		       REF_NO_DEREF, UPDATE_REFS_MSG_ON_ERR)) {
+		error(_("could not update %s"), argv[4]);
+		die("Failed to update %s", argv[4]);
+	}
+	if (create_symref("HEAD", branch_name.buf, reflog_msg.buf) < 0)
+		die(_("unable to update HEAD"));
+	strbuf_release(&reflog_msg);
+	strbuf_release(&branch_name);
+
+	prime_cache_tree(the_repository, the_repository->index, result.tree);
+	if (write_locked_index(&the_index, &lock,
+			       COMMIT_LOCK | SKIP_IF_UNCHANGED))
+		die(_("unable to write %s"), get_index_file());
+	return (clean == 0);
+}
diff --git a/git.c b/git.c
index 4bdcdad2cc..af84f11e69 100644
--- a/git.c
+++ b/git.c
@@ -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

[PATCH v2 4/4] merge,rebase,revert: select ort or recursive by config or environment

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 builtin/merge.c  | 26 ++++++++++++++++--
 builtin/rebase.c |  9 +++++-
 builtin/revert.c |  2 ++
 sequencer.c      | 71 ++++++++++++++++++++++++++++++++++++++++--------
 4 files changed, 93 insertions(+), 15 deletions(-)

diff --git a/builtin/merge.c b/builtin/merge.c
index 9d5359edc2..87dfc9bc06 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -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);
 
diff --git a/builtin/rebase.c b/builtin/rebase.c
index eeca53382f..9719aa25da 100644
--- a/builtin/rebase.c
+++ b/builtin/rebase.c
@@ -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:
diff --git a/builtin/revert.c b/builtin/revert.c
index f61cc5d82c..c7cb0c1a18 100644
--- a/builtin/revert.c
+++ b/builtin/revert.c
@@ -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);
diff --git a/sequencer.c b/sequencer.c
index 00acb12496..163475ae31 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -14,7 +14,8 @@
 #include "diff.h"
 #include "revision.h"
 #include "rerere.h"
-#include "merge-recursive.h"
+#include "merge-ort.h"
+#include "merge-ort-wrappers.h"
 #include "refs.h"
 #include "strvec.h"
 #include "quote.h"
@@ -204,6 +205,20 @@ static int git_sequencer_config(const char *k, const char *v, void *cb)
 		return 0;
 	}
 
+	if (!opts->strategy && !strcmp(k, "pull.twohead")) {
+		int ret = git_config_string((const char**)&opts->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, ' ');
+			if (tmp)
+				*tmp = '\0';
+		}
+		return ret;
+	}
+
 	status = git_gpg_config(k, v, NULL);
 	if (status)
 		return status;
@@ -595,8 +610,9 @@ static int do_recursive_merge(struct repository *r,
 			      struct replay_opts *opts)
 {
 	struct merge_options o;
+	struct merge_result result;
 	struct tree *next_tree, *base_tree, *head_tree;
-	int clean;
+	int clean, show_output;
 	int i;
 	struct lock_file index_lock = LOCK_INIT;
 
@@ -620,12 +636,27 @@ static int do_recursive_merge(struct repository *r,
 	for (i = 0; i < opts->xopts_nr; i++)
 		parse_merge_opt(&o, opts->xopts[i]);
 
-	clean = merge_trees(&o,
-			    head_tree,
-			    next_tree, base_tree);
-	if (is_rebase_i(opts) && clean <= 0)
-		fputs(o.obuf.buf, stdout);
-	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,
+					    &result);
+		show_output = !is_rebase_i(opts) || !result.clean;
+		/*
+		 * TODO: merge_switch_to_result will update index/working tree;
+		 * we only really want to do that if !result.clean || this is
+		 * the final patch to be picked.  But determining this is the
+		 * final patch would take some work, and "head_tree" would need
+		 * to be replace with the tree the index matched before we
+		 * started doing any picks.
+		 */
+		merge_switch_to_result(&o, head_tree, &result, 1, show_output);
+		clean = result.clean;
+	} else {
+		clean = merge_trees(&o, head_tree, next_tree, base_tree);
+		if (is_rebase_i(opts) && clean <= 0)
+			fputs(o.obuf.buf, stdout);
+		strbuf_release(&o.obuf);
+	}
 	if (clean < 0) {
 		rollback_lock_file(&index_lock);
 		return clean;
@@ -1991,7 +2022,10 @@ static int do_pick_commit(struct repository *r,
 
 	if (is_rebase_i(opts) && write_author_script(msg.message) < 0)
 		res = -1;
-	else if (!opts->strategy || !strcmp(opts->strategy, "recursive") || command == TODO_REVERT) {
+	else if (!opts->strategy ||
+		 !strcmp(opts->strategy, "recursive") ||
+		 !strcmp(opts->strategy, "ort") ||
+		 command == TODO_REVERT) {
 		res = do_recursive_merge(r, base, next, base_label, next_label,
 					 &head, &msgbuf, opts);
 		if (res < 0)
@@ -3485,7 +3519,9 @@ static int do_merge(struct repository *r,
 	struct commit_list *bases, *j, *reversed = NULL;
 	struct commit_list *to_merge = NULL, **tail = &to_merge;
 	const char *strategy = !opts->xopts_nr &&
-		(!opts->strategy || !strcmp(opts->strategy, "recursive")) ?
+		(!opts->strategy ||
+		 !strcmp(opts->strategy, "recursive") ||
+		 !strcmp(opts->strategy, "ort")) ?
 		NULL : opts->strategy;
 	struct merge_options o;
 	int merge_arg_len, oneline_offset, can_fast_forward, ret, k;
@@ -3722,7 +3758,20 @@ static int do_merge(struct repository *r,
 	o.branch2 = ref_name.buf;
 	o.buffer_output = 2;
 
-	ret = merge_recursive(&o, head_commit, merge_commit, reversed, &i);
+	if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+		/*
+		 * TODO: Should use merge_inmemory_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.
+		 */
+		ret = merge_ort_recursive(&o,
+					  head_commit, merge_commit, reversed,
+					  &i);
+	} else {
+		ret = merge_recursive(&o, head_commit, merge_commit, reversed,
+				      &i);
+	}
 	if (ret <= 0)
 		fputs(o.obuf.buf, stdout);
 	strbuf_release(&o.obuf);
-- 
gitgitgadget

Re: [PATCH v2 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Junio C Hamano]

"Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com> writes:

> + *   git merge [-s recursive]
> + *
> + * with
> + *
> + *   git merge -s ort
> + *
> + * Note: git's parser allows the space between '-s' and its argument to be
> + * missing.  (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
> + * "cale", "peedy", or "ins" instead of "ort"?)

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.

> diff --git a/merge-ort.h b/merge-ort.h
> new file mode 100644
> index 0000000000..47d30cf538
> --- /dev/null
> +++ b/merge-ort.h
> @@ -0,0 +1,49 @@
> +#ifndef MERGE_ORT_H
> +#define MERGE_ORT_H
> +
> +#include "merge-recursive.h"
> +
> +struct commit;
> +struct tree;
> +
> +struct merge_result {
> +	/* whether the merge is clean */
> +	int clean;
> +
> +	/* Result of merge.  If !clean, represents what would go in worktree */
> +	struct tree *tree;

Curious.  Because there is no way for "struct tree" to hold an
in-core pointer to a "struct blob" (iow, for a blob to be in a
"struct tree", it has to have been assigned an object name), unless
we are using the "pretend" mechanism, which has its own downsides,
we are committed to create a throw-away blob objects with conflict
markers in them, and write them to the object store.

If we were writing a new merge machinery from scratch, I would have
preferred a truly in-core implementation that does not have to write
out to the object store but if this makes the implementation simpler,
perhaps it is a small enough price to pay.

> +	/*
> +	 * Additional metadata used by merge_switch_to_result() or future calls
> +	 * to merge_inmemory_*().  Not for external use.
> +	 */
> +	void *priv;
> +	unsigned ate;

I'd prefer to see this named not so cute.  Will we hang random
variations of things, or would this be better to be made into a
pointer to union, with an enum that tells us which kind it is in
use?

> +};


> +/* 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);

I've seen "incore" spelled as a squashed-into-a-single-word, but not
"in_memory".

> +/* 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);
> +
> +/* Update the working tree and index from head to result after inmemory merge */
> +void merge_switch_to_result(struct merge_options *opt,
> +			    struct tree *head,
> +			    struct merge_result *result,
> +			    int update_worktree_and_index,
> +			    int display_update_msgs);

To those who have known how our merge works, a natural expectation
for an "in-core" merge is that when the "in-core" merge finishes,
the index would hold the higher stages for the conflicted paths, and
cleanly merged paths would have the result at stage 0, and there is
an extra thing that we haven't had that represents what the working
tree files for conflicted paths should look like (historically we
wrote out the conflicted result to the working tree files---being
in-core operation we cannot afford to), so that (1) cleanly merged
paths can be externalized by writing from their stage 0 entries and
(2) contents with conflicts can be externalized by that "extra
thing".

But this helper says "working tree and index" are both updated, so
the "in-core" merge it expects must have not just the working tree
result (in result->tree, as the comment in the structure says) but
also how the higher stages of the index should look like somewhere
in the result structure.  How the latter is done is not at all clear
at this point in the mock-up.  Leaving it opaque is fine, but the
function, and the result structure, deserve clarification to avoid
confusing readers by highlighting how it is different from the
traditional ways (e.g. "we don't touch the index at all---instead we
store that in the priv/ate fields", if that is what is going on).

Thanks.

Re: [PATCH v2 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Elijah Newren]

On Mon, Oct 26, 2020 at 1:45 PM Junio C Hamano <gitster@pobox.com> wrote:
>
> "Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com> writes:
>
> > + *   git merge [-s recursive]
> > + *
> > + * with
> > + *
> > + *   git merge -s ort
> > + *
> > + * Note: git's parser allows the space between '-s' and its argument to be
> > + * missing.  (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
> > + * "cale", "peedy", or "ins" instead of "ort"?)
>
> 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...

> > diff --git a/merge-ort.h b/merge-ort.h
> > new file mode 100644
> > index 0000000000..47d30cf538
> > --- /dev/null
> > +++ b/merge-ort.h
> > @@ -0,0 +1,49 @@
> > +#ifndef MERGE_ORT_H
> > +#define MERGE_ORT_H
> > +
> > +#include "merge-recursive.h"
> > +
> > +struct commit;
> > +struct tree;
> > +
> > +struct merge_result {
> > +     /* whether the merge is clean */
> > +     int clean;
> > +
> > +     /* Result of merge.  If !clean, represents what would go in worktree */
> > +     struct tree *tree;
>
> Curious.  Because there is no way for "struct tree" to hold an
> in-core pointer to a "struct blob" (iow, for a blob to be in a
> "struct tree", it has to have been assigned an object name), unless
> we are using the "pretend" mechanism, which has its own downsides,
> we are committed to create a throw-away blob objects with conflict
> markers in them, and write them to the object store.

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.

> If we were writing a new merge machinery from scratch, I would have
> preferred a truly in-core implementation that does not have to write
> out to the object store but if this makes the implementation simpler,
> perhaps it is a small enough price to pay.

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.

> > +     /*
> > +      * Additional metadata used by merge_switch_to_result() or future calls
> > +      * to merge_inmemory_*().  Not for external use.
> > +      */
> > +     void *priv;
> > +     unsigned ate;
>
> I'd prefer to see this named not so cute.  Will we hang random
> variations of things, or would this be better to be made into a
> pointer to union, with an enum that tells us which kind it is in
> use?

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.

> > +};
>
>
> > +/* 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);
>
> I've seen "incore" spelled as a squashed-into-a-single-word, but not
> "in_memory".

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

> > +/* 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);
> > +
> > +/* Update the working tree and index from head to result after inmemory merge */
> > +void merge_switch_to_result(struct merge_options *opt,
> > +                         struct tree *head,
> > +                         struct merge_result *result,
> > +                         int update_worktree_and_index,
> > +                         int display_update_msgs);
>
> To those who have known how our merge works, a natural expectation
> for an "in-core" merge is that when the "in-core" merge finishes,
> the index would hold the higher stages for the conflicted paths, and
> cleanly merged paths would have the result at stage 0, and there is
> an extra thing that we haven't had that represents what the working
> tree files for conflicted paths should look like (historically we
> wrote out the conflicted result to the working tree files---being
> in-core operation we cannot afford to), so that (1) cleanly merged
> paths can be externalized by writing from their stage 0 entries and
> (2) contents with conflicts can be externalized by that "extra
> thing".
>
> But this helper says "working tree and index" are both updated, so
> the "in-core" merge it expects must have not just the working tree
> result (in result->tree, as the comment in the structure says) but
> also how the higher stages of the index should look like somewhere
> in the result structure.  How the latter is done is not at all clear
> at this point in the mock-up.  Leaving it opaque is fine, but the
> function, and the result structure, deserve clarification to avoid
> confusing readers by highlighting how it is different from the
> traditional ways (e.g. "we don't touch the index at all---instead we
> store that in the priv/ate fields", if that is what is going on).

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.

Re: [PATCH 0/4] Beginning of new merge strategy: New API, empty implementation

[Jonathan Tan]

> Hi,
> 
> On Wed, Oct 21, 2020 at 6:22 AM Elijah Newren via GitGitGadget
> <gitgitgadget@gmail.com> wrote:
> >
> > 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:
> 
> 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?)

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.

>   * Is it too weird to have a temporary/hidden builtin, in patch 3?
> If so, what is a good alternative?

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

Re: [PATCH v2 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

>> > +     /*
>> > +      * Additional metadata used by merge_switch_to_result() or future calls
>> > +      * to merge_inmemory_*().  Not for external use.
>> > +      */
>> > +     void *priv;
>> > +     unsigned ate;
>>
>> I'd prefer to see this named not so cute.  Will we hang random
>> variations of things, or would this be better to be made into a
>> pointer to union, with an enum that tells us which kind it is in
>> use?
>
> I don't understand the union suggestion.  Both fields are used.

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.

> Would you object if 'ate' was named '_'?

Either is horrible name.

>> > +/* 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);
>>
>> I've seen "incore" spelled as a squashed-into-a-single-word, but not
>> "in_memory".
>
> I can add an underscore.  Or switch to incore.  Preference?

Anything shorter would get my vote.

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

Sounds good.

Re: [PATCH v2 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Elijah Newren]

On Mon, Oct 26, 2020 at 3:10 PM Junio C Hamano <gitster@pobox.com> wrote:
>
> Elijah Newren <newren@gmail.com> writes:

> >> > +     /*
> >> > +      * Additional metadata used by merge_switch_to_result() or future calls
> >> > +      * to merge_inmemory_*().  Not for external use.
> >> > +      */
> >> > +     void *priv;
> >> > +     unsigned ate;
> >>
> >> I'd prefer to see this named not so cute.  Will we hang random
> >> variations of things, or would this be better to be made into a
> >> pointer to union, with an enum that tells us which kind it is in
> >> use?
> >
> > I don't understand the union suggestion.  Both fields are used.
>
> 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.

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

> > Would you object if 'ate' was named '_'?
>
> Either is horrible name.

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.

> >> > +/* 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);
> >>
> >> I've seen "incore" spelled as a squashed-into-a-single-word, but not
> >> "in_memory".
> >
> > I can add an underscore.  Or switch to incore.  Preference?
>
> Anything shorter would get my vote.

Sounds good, will do.

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

:-)

Re: [PATCH 0/4] Beginning of new merge strategy: New API, empty implementation

[Elijah Newren]

On Mon, Oct 26, 2020 at 2:56 PM Jonathan Tan <jonathantanmy@google.com> wrote:
>
> > Hi,
> >
> > On Wed, Oct 21, 2020 at 6:22 AM Elijah Newren via GitGitGadget
> > <gitgitgadget@gmail.com> wrote:
> > >
> > > 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:
> >
> > 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?)
>
> 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.

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.

> >   * Is it too weird to have a temporary/hidden builtin, in patch 3?
> > If so, what is a good alternative?
>
> An alternative is to implement it as part of test-tool - see t/helper/
> for more information.

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.

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

Thanks for taking a look.  :-)

[PATCH v3 0/4] Beginning of new merge strategy: New API, empty implementation

[Elijah Newren via 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

[PATCH v3 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 95571ee3fc..088770c2ae 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/merge-ort.c b/merge-ort.c
new file mode 100644
index 0000000000..b487901d3e
--- /dev/null
+++ b/merge-ort.c
@@ -0,0 +1,52 @@
+/*
+ * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short.  Meant
+ * as a drop-in replacement for the "recursive" merge strategy, allowing one
+ * to replace
+ *
+ *   git merge [-s recursive]
+ *
+ * with
+ *
+ *   git merge -s ort
+ *
+ * Note: git's parser allows the space between '-s' and its argument to be
+ * missing.  (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
+ * "cale", "peedy", or "ins" instead of "ort"?)
+ */
+
+#include "cache.h"
+#include "merge-ort.h"
+
+void merge_switch_to_result(struct merge_options *opt,
+			    struct tree *head,
+			    struct merge_result *result,
+			    int update_worktree_and_index,
+			    int display_update_msgs)
+{
+	die("Not yet implemented");
+	merge_finalize(opt, result);
+}
+
+void merge_finalize(struct merge_options *opt,
+		    struct merge_result *result)
+{
+	die("Not yet implemented");
+}
+
+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_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");
+}
diff --git a/merge-ort.h b/merge-ort.h
new file mode 100644
index 0000000000..74adccad16
--- /dev/null
+++ b/merge-ort.h
@@ -0,0 +1,58 @@
+#ifndef MERGE_ORT_H
+#define MERGE_ORT_H
+
+#include "merge-recursive.h"
+
+struct commit;
+struct tree;
+
+struct merge_result {
+	/* Whether the merge is clean */
+	int clean;
+
+	/*
+	 * 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_incore_*().  Includes data needed to update the index (if
+	 * !clean) and to print "CONFLICT" messages.  Not for external use.
+	 */
+	void *priv;
+};
+
+/*
+ * 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.
+ * 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 incore merge */
+void merge_switch_to_result(struct merge_options *opt,
+			    struct tree *head,
+			    struct merge_result *result,
+			    int update_worktree_and_index,
+			    int display_update_msgs);
+
+/* Do needed cleanup when not calling merge_switch_to_result() */
+void merge_finalize(struct merge_options *opt,
+		    struct merge_result *result);
+
+#endif
-- 
gitgitgadget

[PATCH v3 2/4] merge-ort-wrappers: new convience wrappers to mimic the old merge API

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 088770c2ae..382fe73c76 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/merge-ort-wrappers.c b/merge-ort-wrappers.c
new file mode 100644
index 0000000000..7eec25f93a
--- /dev/null
+++ b/merge-ort-wrappers.c
@@ -0,0 +1,62 @@
+#include "cache.h"
+#include "merge-ort.h"
+#include "merge-ort-wrappers.h"
+
+#include "commit.h"
+
+static int unclean(struct merge_options *opt, struct tree *head)
+{
+	/* Sanity check on repo state; index must match head */
+	struct strbuf sb = STRBUF_INIT;
+
+	if (head && repo_index_has_changes(opt->repo, head, &sb)) {
+		fprintf(stderr, _("Your local changes to the following files would be overwritten by merge:\n  %s"),
+		    sb.buf);
+		strbuf_release(&sb);
+		return -1;
+	}
+
+	return 0;
+}
+
+int merge_ort_nonrecursive(struct merge_options *opt,
+			   struct tree *head,
+			   struct tree *merge,
+			   struct tree *merge_base)
+{
+	struct merge_result result;
+
+	if (unclean(opt, head))
+		return -1;
+
+	if (oideq(&merge_base->object.oid, &merge->object.oid)) {
+		printf(_("Already up to date!"));
+		return 1;
+	}
+
+	memset(&result, 0, sizeof(result));
+	merge_incore_nonrecursive(opt, merge_base, head, merge, &result);
+	merge_switch_to_result(opt, head, &result, 1, 1);
+
+	return result.clean;
+}
+
+int merge_ort_recursive(struct merge_options *opt,
+			struct commit *side1,
+			struct commit *side2,
+			struct commit_list *merge_bases,
+			struct commit **result)
+{
+	struct tree *head = repo_get_commit_tree(opt->repo, side1);
+	struct merge_result tmp;
+
+	if (unclean(opt, head))
+		return -1;
+
+	memset(&tmp, 0, sizeof(tmp));
+	merge_incore_recursive(opt, merge_bases, side1, side2, &tmp);
+	merge_switch_to_result(opt, head, &tmp, 1, 1);
+	*result = NULL;
+
+	return tmp.clean;
+}
diff --git a/merge-ort-wrappers.h b/merge-ort-wrappers.h
new file mode 100644
index 0000000000..0c4c57adbb
--- /dev/null
+++ b/merge-ort-wrappers.h
@@ -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

[PATCH v3 3/4] fast-rebase: demonstrate merge-ort's API via temporary/hidden command

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 382fe73c76..1b40d780fa 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/builtin.h b/builtin.h
index 53fb290963..75ff7dc8a9 100644
--- a/builtin.h
+++ b/builtin.h
@@ -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);
diff --git a/builtin/fast-rebase.c b/builtin/fast-rebase.c
new file mode 100644
index 0000000000..b69632054f
--- /dev/null
+++ b/builtin/fast-rebase.c
@@ -0,0 +1,210 @@
+/*
+ * "git fast-rebase" builtin command
+ *
+ * FAST: Forking Any Subprocesses (is) Taboo
+ *
+ * This is meant SOLELY as a demo of what is possible.  sequencer.c and
+ * rebase.c should be refactored to use the ideas here, rather than attempting
+ * to extend this file to replace those (unless Phillip or Dscho say that
+ * refactoring is too hard and we need a clean slate, but I'm guessing that
+ * refactoring is the better route).
+ */
+
+#define USE_THE_INDEX_COMPATIBILITY_MACROS
+#include "builtin.h"
+
+#include "cache-tree.h"
+#include "commit.h"
+#include "lockfile.h"
+#include "merge-ort.h"
+#include "refs.h"
+#include "revision.h"
+#include "sequencer.h"
+#include "strvec.h"
+#include "tree.h"
+
+static const char *short_commit_name(struct commit *commit)
+{
+	return find_unique_abbrev(&commit->object.oid, DEFAULT_ABBREV);
+}
+
+static struct commit *peel_committish(const char *name)
+{
+	struct object *obj;
+	struct object_id oid;
+
+	if (get_oid(name, &oid))
+		return NULL;
+	obj = parse_object(the_repository, &oid);
+	return (struct commit *)peel_to_type(name, 0, obj, OBJ_COMMIT);
+}
+
+static char *get_author(const char *message)
+{
+	size_t len;
+	const char *a;
+
+	a = find_commit_header(message, "author", &len);
+	if (a)
+		return xmemdupz(a, len);
+
+	return NULL;
+}
+
+static struct commit *create_commit(struct tree *tree,
+				    struct commit *based_on,
+				    struct commit *parent)
+{
+	struct object_id ret;
+	struct object *obj;
+	struct commit_list *parents = NULL;
+	char *author;
+	char *sign_commit = NULL;
+	struct commit_extra_header *extra;
+	struct strbuf msg = STRBUF_INIT;
+	const char *out_enc = get_commit_output_encoding();
+	const char *message = logmsg_reencode(based_on, NULL, out_enc);
+	const char *orig_message = NULL;
+	const char *exclude_gpgsig[] = { "gpgsig", NULL };
+
+	commit_list_insert(parent, &parents);
+	extra = read_commit_extra_headers(based_on, exclude_gpgsig);
+	find_commit_subject(message, &orig_message);
+	strbuf_addstr(&msg, orig_message);
+	author = get_author(message);
+	reset_ident_date();
+	if (commit_tree_extended(msg.buf, msg.len, &tree->object.oid, parents,
+				 &ret, author, NULL, sign_commit, extra)) {
+		error(_("failed to write commit object"));
+		return NULL;
+	}
+	free(author);
+	strbuf_release(&msg);
+
+	obj = parse_object(the_repository, &ret);
+	return (struct commit *)obj;
+}
+
+int cmd_fast_rebase(int argc, const char **argv, const char *prefix)
+{
+	struct commit *onto;
+	struct commit *last_commit = NULL, *last_picked_commit = NULL;
+	struct object_id head;
+	struct lock_file lock = LOCK_INIT;
+	int clean = 1;
+	struct strvec rev_walk_args = STRVEC_INIT;
+	struct rev_info revs;
+	struct commit *commit;
+	struct merge_options merge_opt;
+	struct tree *next_tree, *base_tree, *head_tree;
+	struct merge_result result;
+	struct strbuf reflog_msg = STRBUF_INIT;
+	struct strbuf branch_name = STRBUF_INIT;
+
+	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");
+
+	onto = peel_committish(argv[2]);
+	strbuf_addf(&branch_name, "refs/heads/%s", argv[4]);
+
+	/* Sanity check */
+	if (get_oid("HEAD", &head))
+		die(_("Cannot read HEAD"));
+	assert(oideq(&onto->object.oid, &head));
+
+	hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
+	assert(repo_read_index(the_repository) >= 0);
+
+	repo_init_revisions(the_repository, &revs, NULL);
+	revs.verbose_header = 1;
+	revs.max_parents = 1;
+	revs.cherry_mark = 1;
+	revs.limited = 1;
+	revs.reverse = 1;
+	revs.right_only = 1;
+	revs.sort_order = REV_SORT_IN_GRAPH_ORDER;
+	revs.topo_order = 1;
+	strvec_pushl(&rev_walk_args, "", argv[4], "--not", argv[3], NULL);
+
+	if (setup_revisions(rev_walk_args.nr, rev_walk_args.v, &revs, NULL) > 1)
+		return error(_("unhandled options"));
+
+	strvec_clear(&rev_walk_args);
+
+	if (prepare_revision_walk(&revs) < 0)
+		return error(_("error preparing revisions"));
+
+	init_merge_options(&merge_opt, the_repository);
+	memset(&result, 0, sizeof(result));
+	merge_opt.show_rename_progress = 1;
+	merge_opt.branch1 = "HEAD";
+	head_tree = get_commit_tree(onto);
+	result.tree = head_tree;
+	last_commit = onto;
+	while ((commit = get_revision(&revs))) {
+		struct commit *base;
+
+		fprintf(stderr, "Rebasing %s...\r",
+			oid_to_hex(&commit->object.oid));
+		assert(commit->parents && !commit->parents->next);
+		base = commit->parents->item;
+
+		next_tree = get_commit_tree(commit);
+		base_tree = get_commit_tree(base);
+
+		merge_opt.branch2 = short_commit_name(commit);
+		merge_opt.ancestor = xstrfmt("parent of %s", merge_opt.branch2);
+
+		merge_incore_nonrecursive(&merge_opt,
+					  base_tree,
+					  result.tree,
+					  next_tree,
+					  &result);
+
+		free((char*)merge_opt.ancestor);
+		merge_opt.ancestor = NULL;
+		if (!result.clean)
+			die("Aborting: Hit a conflict and restarting is not implemented.");
+		last_picked_commit = commit;
+		last_commit = create_commit(result.tree, commit, last_commit);
+	}
+	fprintf(stderr, "\nDone.\n");
+	/* TODO: There should be some kind of rev_info_free(&revs) call... */
+	memset(&revs, 0, sizeof(revs));
+
+	merge_switch_to_result(&merge_opt, head_tree, &result, 1, !result.clean);
+
+	if (result.clean < 0)
+		exit(128);
+
+	strbuf_addf(&reflog_msg, "finish rebase %s onto %s",
+		    oid_to_hex(&last_picked_commit->object.oid),
+		    oid_to_hex(&last_commit->object.oid));
+	if (update_ref(reflog_msg.buf, branch_name.buf,
+		       &last_commit->object.oid,
+		       &last_picked_commit->object.oid,
+		       REF_NO_DEREF, UPDATE_REFS_MSG_ON_ERR)) {
+		error(_("could not update %s"), argv[4]);
+		die("Failed to update %s", argv[4]);
+	}
+	if (create_symref("HEAD", branch_name.buf, reflog_msg.buf) < 0)
+		die(_("unable to update HEAD"));
+	strbuf_release(&reflog_msg);
+	strbuf_release(&branch_name);
+
+	prime_cache_tree(the_repository, the_repository->index, result.tree);
+	if (write_locked_index(&the_index, &lock,
+			       COMMIT_LOCK | SKIP_IF_UNCHANGED))
+		die(_("unable to write %s"), get_index_file());
+	return (clean == 0);
+}
diff --git a/git.c b/git.c
index 4bdcdad2cc..af84f11e69 100644
--- a/git.c
+++ b/git.c
@@ -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

[PATCH v3 4/4] merge,rebase,revert: select ort or recursive by config or environment

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 builtin/merge.c  | 26 ++++++++++++++++--
 builtin/rebase.c |  9 +++++-
 builtin/revert.c |  2 ++
 sequencer.c      | 71 ++++++++++++++++++++++++++++++++++++++++--------
 4 files changed, 93 insertions(+), 15 deletions(-)

diff --git a/builtin/merge.c b/builtin/merge.c
index 9d5359edc2..87dfc9bc06 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -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);
 
diff --git a/builtin/rebase.c b/builtin/rebase.c
index eeca53382f..9719aa25da 100644
--- a/builtin/rebase.c
+++ b/builtin/rebase.c
@@ -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:
diff --git a/builtin/revert.c b/builtin/revert.c
index f61cc5d82c..c7cb0c1a18 100644
--- a/builtin/revert.c
+++ b/builtin/revert.c
@@ -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);
diff --git a/sequencer.c b/sequencer.c
index 00acb12496..e16d85380c 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -14,7 +14,8 @@
 #include "diff.h"
 #include "revision.h"
 #include "rerere.h"
-#include "merge-recursive.h"
+#include "merge-ort.h"
+#include "merge-ort-wrappers.h"
 #include "refs.h"
 #include "strvec.h"
 #include "quote.h"
@@ -204,6 +205,20 @@ static int git_sequencer_config(const char *k, const char *v, void *cb)
 		return 0;
 	}
 
+	if (!opts->strategy && !strcmp(k, "pull.twohead")) {
+		int ret = git_config_string((const char**)&opts->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, ' ');
+			if (tmp)
+				*tmp = '\0';
+		}
+		return ret;
+	}
+
 	status = git_gpg_config(k, v, NULL);
 	if (status)
 		return status;
@@ -595,8 +610,9 @@ static int do_recursive_merge(struct repository *r,
 			      struct replay_opts *opts)
 {
 	struct merge_options o;
+	struct merge_result result;
 	struct tree *next_tree, *base_tree, *head_tree;
-	int clean;
+	int clean, show_output;
 	int i;
 	struct lock_file index_lock = LOCK_INIT;
 
@@ -620,12 +636,27 @@ static int do_recursive_merge(struct repository *r,
 	for (i = 0; i < opts->xopts_nr; i++)
 		parse_merge_opt(&o, opts->xopts[i]);
 
-	clean = merge_trees(&o,
-			    head_tree,
-			    next_tree, base_tree);
-	if (is_rebase_i(opts) && clean <= 0)
-		fputs(o.obuf.buf, stdout);
-	strbuf_release(&o.obuf);
+	if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+		memset(&result, 0, sizeof(result));
+		merge_incore_nonrecursive(&o, base_tree, head_tree, next_tree,
+					    &result);
+		show_output = !is_rebase_i(opts) || !result.clean;
+		/*
+		 * TODO: merge_switch_to_result will update index/working tree;
+		 * we only really want to do that if !result.clean || this is
+		 * the final patch to be picked.  But determining this is the
+		 * final patch would take some work, and "head_tree" would need
+		 * to be replace with the tree the index matched before we
+		 * started doing any picks.
+		 */
+		merge_switch_to_result(&o, head_tree, &result, 1, show_output);
+		clean = result.clean;
+	} else {
+		clean = merge_trees(&o, head_tree, next_tree, base_tree);
+		if (is_rebase_i(opts) && clean <= 0)
+			fputs(o.obuf.buf, stdout);
+		strbuf_release(&o.obuf);
+	}
 	if (clean < 0) {
 		rollback_lock_file(&index_lock);
 		return clean;
@@ -1991,7 +2022,10 @@ static int do_pick_commit(struct repository *r,
 
 	if (is_rebase_i(opts) && write_author_script(msg.message) < 0)
 		res = -1;
-	else if (!opts->strategy || !strcmp(opts->strategy, "recursive") || command == TODO_REVERT) {
+	else if (!opts->strategy ||
+		 !strcmp(opts->strategy, "recursive") ||
+		 !strcmp(opts->strategy, "ort") ||
+		 command == TODO_REVERT) {
 		res = do_recursive_merge(r, base, next, base_label, next_label,
 					 &head, &msgbuf, opts);
 		if (res < 0)
@@ -3485,7 +3519,9 @@ static int do_merge(struct repository *r,
 	struct commit_list *bases, *j, *reversed = NULL;
 	struct commit_list *to_merge = NULL, **tail = &to_merge;
 	const char *strategy = !opts->xopts_nr &&
-		(!opts->strategy || !strcmp(opts->strategy, "recursive")) ?
+		(!opts->strategy ||
+		 !strcmp(opts->strategy, "recursive") ||
+		 !strcmp(opts->strategy, "ort")) ?
 		NULL : opts->strategy;
 	struct merge_options o;
 	int merge_arg_len, oneline_offset, can_fast_forward, ret, k;
@@ -3722,7 +3758,20 @@ static int do_merge(struct repository *r,
 	o.branch2 = ref_name.buf;
 	o.buffer_output = 2;
 
-	ret = merge_recursive(&o, head_commit, merge_commit, reversed, &i);
+	if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+		/*
+		 * 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.
+		 */
+		ret = merge_ort_recursive(&o,
+					  head_commit, merge_commit, reversed,
+					  &i);
+	} else {
+		ret = merge_recursive(&o, head_commit, merge_commit, reversed,
+				      &i);
+	}
 	if (ret <= 0)
 		fputs(o.obuf.buf, stdout);
 	strbuf_release(&o.obuf);
-- 
gitgitgadget

Re: [PATCH v3 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Eric Sunshine]

On Mon, Oct 26, 2020 at 10:08 PM Elijah Newren via GitGitGadget
<gitgitgadget@gmail.com> wrote:
> + * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short.  Meant
> + * as a drop-in replacement for the "recursive" merge strategy, allowing one
> + * to replace
> + *
> + *   git merge [-s recursive]
> + *
> + * with
> + *
> + *   git merge -s ort
> + *
> + * Note: git's parser allows the space between '-s' and its argument to be
> + * missing.  (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
> + * "cale", "peedy", or "ins" instead of "ort"?)

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.

Re: [PATCH v3 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Elijah Newren]

On Mon, Oct 26, 2020 at 7:33 PM Eric Sunshine <sunshine@sunshineco.com> wrote:
>
> On Mon, Oct 26, 2020 at 10:08 PM Elijah Newren via GitGitGadget
> <gitgitgadget@gmail.com> wrote:
> > + * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short.  Meant
> > + * as a drop-in replacement for the "recursive" merge strategy, allowing one
> > + * to replace
> > + *
> > + *   git merge [-s recursive]
> > + *
> > + * with
> > + *
> > + *   git merge -s ort
> > + *
> > + * Note: git's parser allows the space between '-s' and its argument to be
> > + * missing.  (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
> > + * "cale", "peedy", or "ins" instead of "ort"?)
>
> 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?

Re: [PATCH v3 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Eric Sunshine]

On Tue, Oct 27, 2020 at 12:57 AM Elijah Newren <newren@gmail.com> wrote:
> On Mon, Oct 26, 2020 at 7:33 PM Eric Sunshine <sunshine@sunshineco.com> wrote:
> > 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].
> >
> > [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).

Re: [PATCH v3 3/4] fast-rebase: demonstrate merge-ort's API via temporary/hidden command

[SZEDER Gábor]

On Tue, Oct 27, 2020 at 02:08:09AM +0000, Elijah Newren via GitGitGadget wrote:
> 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.


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

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?

[PATCH v4 0/4] Beginning of new merge strategy: New API, empty implementation

[Elijah Newren via 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 <newren@gmail.com>
      
       ## 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
          Signed-off-by: Elijah Newren <newren@gmail.com>
      
       ## 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

[PATCH v4 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 95571ee3fc..088770c2ae 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/merge-ort.c b/merge-ort.c
new file mode 100644
index 0000000000..b487901d3e
--- /dev/null
+++ b/merge-ort.c
@@ -0,0 +1,52 @@
+/*
+ * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short.  Meant
+ * as a drop-in replacement for the "recursive" merge strategy, allowing one
+ * to replace
+ *
+ *   git merge [-s recursive]
+ *
+ * with
+ *
+ *   git merge -s ort
+ *
+ * Note: git's parser allows the space between '-s' and its argument to be
+ * missing.  (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
+ * "cale", "peedy", or "ins" instead of "ort"?)
+ */
+
+#include "cache.h"
+#include "merge-ort.h"
+
+void merge_switch_to_result(struct merge_options *opt,
+			    struct tree *head,
+			    struct merge_result *result,
+			    int update_worktree_and_index,
+			    int display_update_msgs)
+{
+	die("Not yet implemented");
+	merge_finalize(opt, result);
+}
+
+void merge_finalize(struct merge_options *opt,
+		    struct merge_result *result)
+{
+	die("Not yet implemented");
+}
+
+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_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");
+}
diff --git a/merge-ort.h b/merge-ort.h
new file mode 100644
index 0000000000..74adccad16
--- /dev/null
+++ b/merge-ort.h
@@ -0,0 +1,58 @@
+#ifndef MERGE_ORT_H
+#define MERGE_ORT_H
+
+#include "merge-recursive.h"
+
+struct commit;
+struct tree;
+
+struct merge_result {
+	/* Whether the merge is clean */
+	int clean;
+
+	/*
+	 * 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_incore_*().  Includes data needed to update the index (if
+	 * !clean) and to print "CONFLICT" messages.  Not for external use.
+	 */
+	void *priv;
+};
+
+/*
+ * 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.
+ * 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 incore merge */
+void merge_switch_to_result(struct merge_options *opt,
+			    struct tree *head,
+			    struct merge_result *result,
+			    int update_worktree_and_index,
+			    int display_update_msgs);
+
+/* Do needed cleanup when not calling merge_switch_to_result() */
+void merge_finalize(struct merge_options *opt,
+		    struct merge_result *result);
+
+#endif
-- 
gitgitgadget

[PATCH v4 2/4] merge-ort-wrappers: new convience wrappers to mimic the old merge API

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 088770c2ae..382fe73c76 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/merge-ort-wrappers.c b/merge-ort-wrappers.c
new file mode 100644
index 0000000000..7eec25f93a
--- /dev/null
+++ b/merge-ort-wrappers.c
@@ -0,0 +1,62 @@
+#include "cache.h"
+#include "merge-ort.h"
+#include "merge-ort-wrappers.h"
+
+#include "commit.h"
+
+static int unclean(struct merge_options *opt, struct tree *head)
+{
+	/* Sanity check on repo state; index must match head */
+	struct strbuf sb = STRBUF_INIT;
+
+	if (head && repo_index_has_changes(opt->repo, head, &sb)) {
+		fprintf(stderr, _("Your local changes to the following files would be overwritten by merge:\n  %s"),
+		    sb.buf);
+		strbuf_release(&sb);
+		return -1;
+	}
+
+	return 0;
+}
+
+int merge_ort_nonrecursive(struct merge_options *opt,
+			   struct tree *head,
+			   struct tree *merge,
+			   struct tree *merge_base)
+{
+	struct merge_result result;
+
+	if (unclean(opt, head))
+		return -1;
+
+	if (oideq(&merge_base->object.oid, &merge->object.oid)) {
+		printf(_("Already up to date!"));
+		return 1;
+	}
+
+	memset(&result, 0, sizeof(result));
+	merge_incore_nonrecursive(opt, merge_base, head, merge, &result);
+	merge_switch_to_result(opt, head, &result, 1, 1);
+
+	return result.clean;
+}
+
+int merge_ort_recursive(struct merge_options *opt,
+			struct commit *side1,
+			struct commit *side2,
+			struct commit_list *merge_bases,
+			struct commit **result)
+{
+	struct tree *head = repo_get_commit_tree(opt->repo, side1);
+	struct merge_result tmp;
+
+	if (unclean(opt, head))
+		return -1;
+
+	memset(&tmp, 0, sizeof(tmp));
+	merge_incore_recursive(opt, merge_bases, side1, side2, &tmp);
+	merge_switch_to_result(opt, head, &tmp, 1, 1);
+	*result = NULL;
+
+	return tmp.clean;
+}
diff --git a/merge-ort-wrappers.h b/merge-ort-wrappers.h
new file mode 100644
index 0000000000..0c4c57adbb
--- /dev/null
+++ b/merge-ort-wrappers.h
@@ -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

[PATCH v4 3/4] fast-rebase: demonstrate merge-ort's API via new test-tool command

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 382fe73c76..24b9fecc0f 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/t/helper/test-fast-rebase.c b/t/helper/test-fast-rebase.c
new file mode 100644
index 0000000000..373212256a
--- /dev/null
+++ b/t/helper/test-fast-rebase.c
@@ -0,0 +1,211 @@
+/*
+ * "git fast-rebase" builtin command
+ *
+ * FAST: Forking Any Subprocesses (is) Taboo
+ *
+ * This is meant SOLELY as a demo of what is possible.  sequencer.c and
+ * rebase.c should be refactored to use the ideas here, rather than attempting
+ * to extend this file to replace those (unless Phillip or Dscho say that
+ * refactoring is too hard and we need a clean slate, but I'm guessing that
+ * refactoring is the better route).
+ */
+
+#define USE_THE_INDEX_COMPATIBILITY_MACROS
+#include "test-tool.h"
+
+#include "cache-tree.h"
+#include "commit.h"
+#include "lockfile.h"
+#include "merge-ort.h"
+#include "refs.h"
+#include "revision.h"
+#include "sequencer.h"
+#include "strvec.h"
+#include "tree.h"
+
+static const char *short_commit_name(struct commit *commit)
+{
+	return find_unique_abbrev(&commit->object.oid, DEFAULT_ABBREV);
+}
+
+static struct commit *peel_committish(const char *name)
+{
+	struct object *obj;
+	struct object_id oid;
+
+	if (get_oid(name, &oid))
+		return NULL;
+	obj = parse_object(the_repository, &oid);
+	return (struct commit *)peel_to_type(name, 0, obj, OBJ_COMMIT);
+}
+
+static char *get_author(const char *message)
+{
+	size_t len;
+	const char *a;
+
+	a = find_commit_header(message, "author", &len);
+	if (a)
+		return xmemdupz(a, len);
+
+	return NULL;
+}
+
+static struct commit *create_commit(struct tree *tree,
+				    struct commit *based_on,
+				    struct commit *parent)
+{
+	struct object_id ret;
+	struct object *obj;
+	struct commit_list *parents = NULL;
+	char *author;
+	char *sign_commit = NULL;
+	struct commit_extra_header *extra;
+	struct strbuf msg = STRBUF_INIT;
+	const char *out_enc = get_commit_output_encoding();
+	const char *message = logmsg_reencode(based_on, NULL, out_enc);
+	const char *orig_message = NULL;
+	const char *exclude_gpgsig[] = { "gpgsig", NULL };
+
+	commit_list_insert(parent, &parents);
+	extra = read_commit_extra_headers(based_on, exclude_gpgsig);
+	find_commit_subject(message, &orig_message);
+	strbuf_addstr(&msg, orig_message);
+	author = get_author(message);
+	reset_ident_date();
+	if (commit_tree_extended(msg.buf, msg.len, &tree->object.oid, parents,
+				 &ret, author, NULL, sign_commit, extra)) {
+		error(_("failed to write commit object"));
+		return NULL;
+	}
+	free(author);
+	strbuf_release(&msg);
+
+	obj = parse_object(the_repository, &ret);
+	return (struct commit *)obj;
+}
+
+int cmd__fast_rebase(int argc, const char **argv)
+{
+	struct commit *onto;
+	struct commit *last_commit = NULL, *last_picked_commit = NULL;
+	struct object_id head;
+	struct lock_file lock = LOCK_INIT;
+	int clean = 1;
+	struct strvec rev_walk_args = STRVEC_INIT;
+	struct rev_info revs;
+	struct commit *commit;
+	struct merge_options merge_opt;
+	struct tree *next_tree, *base_tree, *head_tree;
+	struct merge_result result;
+	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 (argc != 5 || strcmp(argv[1], "--onto"))
+		die("usage: read the code, figure out how to use it, then do so");
+
+	onto = peel_committish(argv[2]);
+	strbuf_addf(&branch_name, "refs/heads/%s", argv[4]);
+
+	/* Sanity check */
+	if (get_oid("HEAD", &head))
+		die(_("Cannot read HEAD"));
+	assert(oideq(&onto->object.oid, &head));
+
+	hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
+	assert(repo_read_index(the_repository) >= 0);
+
+	repo_init_revisions(the_repository, &revs, NULL);
+	revs.verbose_header = 1;
+	revs.max_parents = 1;
+	revs.cherry_mark = 1;
+	revs.limited = 1;
+	revs.reverse = 1;
+	revs.right_only = 1;
+	revs.sort_order = REV_SORT_IN_GRAPH_ORDER;
+	revs.topo_order = 1;
+	strvec_pushl(&rev_walk_args, "", argv[4], "--not", argv[3], NULL);
+
+	if (setup_revisions(rev_walk_args.nr, rev_walk_args.v, &revs, NULL) > 1)
+		return error(_("unhandled options"));
+
+	strvec_clear(&rev_walk_args);
+
+	if (prepare_revision_walk(&revs) < 0)
+		return error(_("error preparing revisions"));
+
+	init_merge_options(&merge_opt, the_repository);
+	memset(&result, 0, sizeof(result));
+	merge_opt.show_rename_progress = 1;
+	merge_opt.branch1 = "HEAD";
+	head_tree = get_commit_tree(onto);
+	result.tree = head_tree;
+	last_commit = onto;
+	while ((commit = get_revision(&revs))) {
+		struct commit *base;
+
+		fprintf(stderr, "Rebasing %s...\r",
+			oid_to_hex(&commit->object.oid));
+		assert(commit->parents && !commit->parents->next);
+		base = commit->parents->item;
+
+		next_tree = get_commit_tree(commit);
+		base_tree = get_commit_tree(base);
+
+		merge_opt.branch2 = short_commit_name(commit);
+		merge_opt.ancestor = xstrfmt("parent of %s", merge_opt.branch2);
+
+		merge_incore_nonrecursive(&merge_opt,
+					  base_tree,
+					  result.tree,
+					  next_tree,
+					  &result);
+
+		free((char*)merge_opt.ancestor);
+		merge_opt.ancestor = NULL;
+		if (!result.clean)
+			die("Aborting: Hit a conflict and restarting is not implemented.");
+		last_picked_commit = commit;
+		last_commit = create_commit(result.tree, commit, last_commit);
+	}
+	fprintf(stderr, "\nDone.\n");
+	/* TODO: There should be some kind of rev_info_free(&revs) call... */
+	memset(&revs, 0, sizeof(revs));
+
+	merge_switch_to_result(&merge_opt, head_tree, &result, 1, !result.clean);
+
+	if (result.clean < 0)
+		exit(128);
+
+	strbuf_addf(&reflog_msg, "finish rebase %s onto %s",
+		    oid_to_hex(&last_picked_commit->object.oid),
+		    oid_to_hex(&last_commit->object.oid));
+	if (update_ref(reflog_msg.buf, branch_name.buf,
+		       &last_commit->object.oid,
+		       &last_picked_commit->object.oid,
+		       REF_NO_DEREF, UPDATE_REFS_MSG_ON_ERR)) {
+		error(_("could not update %s"), argv[4]);
+		die("Failed to update %s", argv[4]);
+	}
+	if (create_symref("HEAD", branch_name.buf, reflog_msg.buf) < 0)
+		die(_("unable to update HEAD"));
+	strbuf_release(&reflog_msg);
+	strbuf_release(&branch_name);
+
+	prime_cache_tree(the_repository, the_repository->index, result.tree);
+	if (write_locked_index(&the_index, &lock,
+			       COMMIT_LOCK | SKIP_IF_UNCHANGED))
+		die(_("unable to write %s"), get_index_file());
+	return (clean == 0);
+}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index a0d3966b29..8bce7db076 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -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 },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index 07034d3f38..fd0cafe5ca 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -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

[PATCH v4 4/4] merge,rebase,revert: select ort or recursive by config or environment

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 builtin/merge.c  | 26 ++++++++++++++++--
 builtin/rebase.c |  9 +++++-
 builtin/revert.c |  2 ++
 sequencer.c      | 71 ++++++++++++++++++++++++++++++++++++++++--------
 4 files changed, 93 insertions(+), 15 deletions(-)

diff --git a/builtin/merge.c b/builtin/merge.c
index 9d5359edc2..87dfc9bc06 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -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);
 
diff --git a/builtin/rebase.c b/builtin/rebase.c
index eeca53382f..9719aa25da 100644
--- a/builtin/rebase.c
+++ b/builtin/rebase.c
@@ -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:
diff --git a/builtin/revert.c b/builtin/revert.c
index f61cc5d82c..c7cb0c1a18 100644
--- a/builtin/revert.c
+++ b/builtin/revert.c
@@ -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);
diff --git a/sequencer.c b/sequencer.c
index 00acb12496..e16d85380c 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -14,7 +14,8 @@
 #include "diff.h"
 #include "revision.h"
 #include "rerere.h"
-#include "merge-recursive.h"
+#include "merge-ort.h"
+#include "merge-ort-wrappers.h"
 #include "refs.h"
 #include "strvec.h"
 #include "quote.h"
@@ -204,6 +205,20 @@ static int git_sequencer_config(const char *k, const char *v, void *cb)
 		return 0;
 	}
 
+	if (!opts->strategy && !strcmp(k, "pull.twohead")) {
+		int ret = git_config_string((const char**)&opts->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, ' ');
+			if (tmp)
+				*tmp = '\0';
+		}
+		return ret;
+	}
+
 	status = git_gpg_config(k, v, NULL);
 	if (status)
 		return status;
@@ -595,8 +610,9 @@ static int do_recursive_merge(struct repository *r,
 			      struct replay_opts *opts)
 {
 	struct merge_options o;
+	struct merge_result result;
 	struct tree *next_tree, *base_tree, *head_tree;
-	int clean;
+	int clean, show_output;
 	int i;
 	struct lock_file index_lock = LOCK_INIT;
 
@@ -620,12 +636,27 @@ static int do_recursive_merge(struct repository *r,
 	for (i = 0; i < opts->xopts_nr; i++)
 		parse_merge_opt(&o, opts->xopts[i]);
 
-	clean = merge_trees(&o,
-			    head_tree,
-			    next_tree, base_tree);
-	if (is_rebase_i(opts) && clean <= 0)
-		fputs(o.obuf.buf, stdout);
-	strbuf_release(&o.obuf);
+	if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+		memset(&result, 0, sizeof(result));
+		merge_incore_nonrecursive(&o, base_tree, head_tree, next_tree,
+					    &result);
+		show_output = !is_rebase_i(opts) || !result.clean;
+		/*
+		 * TODO: merge_switch_to_result will update index/working tree;
+		 * we only really want to do that if !result.clean || this is
+		 * the final patch to be picked.  But determining this is the
+		 * final patch would take some work, and "head_tree" would need
+		 * to be replace with the tree the index matched before we
+		 * started doing any picks.
+		 */
+		merge_switch_to_result(&o, head_tree, &result, 1, show_output);
+		clean = result.clean;
+	} else {
+		clean = merge_trees(&o, head_tree, next_tree, base_tree);
+		if (is_rebase_i(opts) && clean <= 0)
+			fputs(o.obuf.buf, stdout);
+		strbuf_release(&o.obuf);
+	}
 	if (clean < 0) {
 		rollback_lock_file(&index_lock);
 		return clean;
@@ -1991,7 +2022,10 @@ static int do_pick_commit(struct repository *r,
 
 	if (is_rebase_i(opts) && write_author_script(msg.message) < 0)
 		res = -1;
-	else if (!opts->strategy || !strcmp(opts->strategy, "recursive") || command == TODO_REVERT) {
+	else if (!opts->strategy ||
+		 !strcmp(opts->strategy, "recursive") ||
+		 !strcmp(opts->strategy, "ort") ||
+		 command == TODO_REVERT) {
 		res = do_recursive_merge(r, base, next, base_label, next_label,
 					 &head, &msgbuf, opts);
 		if (res < 0)
@@ -3485,7 +3519,9 @@ static int do_merge(struct repository *r,
 	struct commit_list *bases, *j, *reversed = NULL;
 	struct commit_list *to_merge = NULL, **tail = &to_merge;
 	const char *strategy = !opts->xopts_nr &&
-		(!opts->strategy || !strcmp(opts->strategy, "recursive")) ?
+		(!opts->strategy ||
+		 !strcmp(opts->strategy, "recursive") ||
+		 !strcmp(opts->strategy, "ort")) ?
 		NULL : opts->strategy;
 	struct merge_options o;
 	int merge_arg_len, oneline_offset, can_fast_forward, ret, k;
@@ -3722,7 +3758,20 @@ static int do_merge(struct repository *r,
 	o.branch2 = ref_name.buf;
 	o.buffer_output = 2;
 
-	ret = merge_recursive(&o, head_commit, merge_commit, reversed, &i);
+	if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+		/*
+		 * 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.
+		 */
+		ret = merge_ort_recursive(&o,
+					  head_commit, merge_commit, reversed,
+					  &i);
+	} else {
+		ret = merge_recursive(&o, head_commit, merge_commit, reversed,
+				      &i);
+	}
 	if (ret <= 0)
 		fputs(o.obuf.buf, stdout);
 	strbuf_release(&o.obuf);
-- 
gitgitgadget

Re: [PATCH v4 0/4] Beginning of new merge strategy: New API, empty implementation

[Jacob Keller]

On Thu, Oct 29, 2020 at 1:34 PM Elijah Newren via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> 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.
>

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

> 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 <newren@gmail.com>
>
>        ## 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
>           Signed-off-by: Elijah Newren <newren@gmail.com>
>
>        ## 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

Re: [PATCH v4 0/4] Beginning of new merge strategy: New API, empty implementation

[Elijah Newren]

On Mon, Nov 2, 2020 at 1:28 AM Jacob Keller <jacob.keller@gmail.com> wrote:
>
> On Thu, Oct 29, 2020 at 1:34 PM Elijah Newren via GitGitGadget
> <gitgitgadget@gmail.com> wrote:
> >
> > 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.
> >
>
> 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!

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.

[PATCH v5 0/4] Beginning of new merge strategy: New API, empty implementation

[Elijah Newren via 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 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

[PATCH v5 1/4] merge-ort: barebones API of new merge strategy with empty implementation

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 95571ee3fc..088770c2ae 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/merge-ort.c b/merge-ort.c
new file mode 100644
index 0000000000..b487901d3e
--- /dev/null
+++ b/merge-ort.c
@@ -0,0 +1,52 @@
+/*
+ * "Ostensibly Recursive's Twin" merge strategy, or "ort" for short.  Meant
+ * as a drop-in replacement for the "recursive" merge strategy, allowing one
+ * to replace
+ *
+ *   git merge [-s recursive]
+ *
+ * with
+ *
+ *   git merge -s ort
+ *
+ * Note: git's parser allows the space between '-s' and its argument to be
+ * missing.  (Should I have backronymed "ham", "alsa", "kip", "nap, "alvo",
+ * "cale", "peedy", or "ins" instead of "ort"?)
+ */
+
+#include "cache.h"
+#include "merge-ort.h"
+
+void merge_switch_to_result(struct merge_options *opt,
+			    struct tree *head,
+			    struct merge_result *result,
+			    int update_worktree_and_index,
+			    int display_update_msgs)
+{
+	die("Not yet implemented");
+	merge_finalize(opt, result);
+}
+
+void merge_finalize(struct merge_options *opt,
+		    struct merge_result *result)
+{
+	die("Not yet implemented");
+}
+
+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_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");
+}
diff --git a/merge-ort.h b/merge-ort.h
new file mode 100644
index 0000000000..74adccad16
--- /dev/null
+++ b/merge-ort.h
@@ -0,0 +1,58 @@
+#ifndef MERGE_ORT_H
+#define MERGE_ORT_H
+
+#include "merge-recursive.h"
+
+struct commit;
+struct tree;
+
+struct merge_result {
+	/* Whether the merge is clean */
+	int clean;
+
+	/*
+	 * 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_incore_*().  Includes data needed to update the index (if
+	 * !clean) and to print "CONFLICT" messages.  Not for external use.
+	 */
+	void *priv;
+};
+
+/*
+ * 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.
+ * 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 incore merge */
+void merge_switch_to_result(struct merge_options *opt,
+			    struct tree *head,
+			    struct merge_result *result,
+			    int update_worktree_and_index,
+			    int display_update_msgs);
+
+/* Do needed cleanup when not calling merge_switch_to_result() */
+void merge_finalize(struct merge_options *opt,
+		    struct merge_result *result);
+
+#endif
-- 
gitgitgadget

[PATCH v5 2/4] merge-ort-wrappers: new convience wrappers to mimic the old merge API

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 088770c2ae..382fe73c76 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/merge-ort-wrappers.c b/merge-ort-wrappers.c
new file mode 100644
index 0000000000..7eec25f93a
--- /dev/null
+++ b/merge-ort-wrappers.c
@@ -0,0 +1,62 @@
+#include "cache.h"
+#include "merge-ort.h"
+#include "merge-ort-wrappers.h"
+
+#include "commit.h"
+
+static int unclean(struct merge_options *opt, struct tree *head)
+{
+	/* Sanity check on repo state; index must match head */
+	struct strbuf sb = STRBUF_INIT;
+
+	if (head && repo_index_has_changes(opt->repo, head, &sb)) {
+		fprintf(stderr, _("Your local changes to the following files would be overwritten by merge:\n  %s"),
+		    sb.buf);
+		strbuf_release(&sb);
+		return -1;
+	}
+
+	return 0;
+}
+
+int merge_ort_nonrecursive(struct merge_options *opt,
+			   struct tree *head,
+			   struct tree *merge,
+			   struct tree *merge_base)
+{
+	struct merge_result result;
+
+	if (unclean(opt, head))
+		return -1;
+
+	if (oideq(&merge_base->object.oid, &merge->object.oid)) {
+		printf(_("Already up to date!"));
+		return 1;
+	}
+
+	memset(&result, 0, sizeof(result));
+	merge_incore_nonrecursive(opt, merge_base, head, merge, &result);
+	merge_switch_to_result(opt, head, &result, 1, 1);
+
+	return result.clean;
+}
+
+int merge_ort_recursive(struct merge_options *opt,
+			struct commit *side1,
+			struct commit *side2,
+			struct commit_list *merge_bases,
+			struct commit **result)
+{
+	struct tree *head = repo_get_commit_tree(opt->repo, side1);
+	struct merge_result tmp;
+
+	if (unclean(opt, head))
+		return -1;
+
+	memset(&tmp, 0, sizeof(tmp));
+	merge_incore_recursive(opt, merge_bases, side1, side2, &tmp);
+	merge_switch_to_result(opt, head, &tmp, 1, 1);
+	*result = NULL;
+
+	return tmp.clean;
+}
diff --git a/merge-ort-wrappers.h b/merge-ort-wrappers.h
new file mode 100644
index 0000000000..0c4c57adbb
--- /dev/null
+++ b/merge-ort-wrappers.h
@@ -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

[PATCH v5 3/4] fast-rebase: demonstrate merge-ort's API via new test-tool command

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

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

diff --git a/Makefile b/Makefile
index 382fe73c76..24b9fecc0f 100644
--- a/Makefile
+++ b/Makefile
@@ -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
diff --git a/t/helper/test-fast-rebase.c b/t/helper/test-fast-rebase.c
new file mode 100644
index 0000000000..373212256a
--- /dev/null
+++ b/t/helper/test-fast-rebase.c
@@ -0,0 +1,211 @@
+/*
+ * "git fast-rebase" builtin command
+ *
+ * FAST: Forking Any Subprocesses (is) Taboo
+ *
+ * This is meant SOLELY as a demo of what is possible.  sequencer.c and
+ * rebase.c should be refactored to use the ideas here, rather than attempting
+ * to extend this file to replace those (unless Phillip or Dscho say that
+ * refactoring is too hard and we need a clean slate, but I'm guessing that
+ * refactoring is the better route).
+ */
+
+#define USE_THE_INDEX_COMPATIBILITY_MACROS
+#include "test-tool.h"
+
+#include "cache-tree.h"
+#include "commit.h"
+#include "lockfile.h"
+#include "merge-ort.h"
+#include "refs.h"
+#include "revision.h"
+#include "sequencer.h"
+#include "strvec.h"
+#include "tree.h"
+
+static const char *short_commit_name(struct commit *commit)
+{
+	return find_unique_abbrev(&commit->object.oid, DEFAULT_ABBREV);
+}
+
+static struct commit *peel_committish(const char *name)
+{
+	struct object *obj;
+	struct object_id oid;
+
+	if (get_oid(name, &oid))
+		return NULL;
+	obj = parse_object(the_repository, &oid);
+	return (struct commit *)peel_to_type(name, 0, obj, OBJ_COMMIT);
+}
+
+static char *get_author(const char *message)
+{
+	size_t len;
+	const char *a;
+
+	a = find_commit_header(message, "author", &len);
+	if (a)
+		return xmemdupz(a, len);
+
+	return NULL;
+}
+
+static struct commit *create_commit(struct tree *tree,
+				    struct commit *based_on,
+				    struct commit *parent)
+{
+	struct object_id ret;
+	struct object *obj;
+	struct commit_list *parents = NULL;
+	char *author;
+	char *sign_commit = NULL;
+	struct commit_extra_header *extra;
+	struct strbuf msg = STRBUF_INIT;
+	const char *out_enc = get_commit_output_encoding();
+	const char *message = logmsg_reencode(based_on, NULL, out_enc);
+	const char *orig_message = NULL;
+	const char *exclude_gpgsig[] = { "gpgsig", NULL };
+
+	commit_list_insert(parent, &parents);
+	extra = read_commit_extra_headers(based_on, exclude_gpgsig);
+	find_commit_subject(message, &orig_message);
+	strbuf_addstr(&msg, orig_message);
+	author = get_author(message);
+	reset_ident_date();
+	if (commit_tree_extended(msg.buf, msg.len, &tree->object.oid, parents,
+				 &ret, author, NULL, sign_commit, extra)) {
+		error(_("failed to write commit object"));
+		return NULL;
+	}
+	free(author);
+	strbuf_release(&msg);
+
+	obj = parse_object(the_repository, &ret);
+	return (struct commit *)obj;
+}
+
+int cmd__fast_rebase(int argc, const char **argv)
+{
+	struct commit *onto;
+	struct commit *last_commit = NULL, *last_picked_commit = NULL;
+	struct object_id head;
+	struct lock_file lock = LOCK_INIT;
+	int clean = 1;
+	struct strvec rev_walk_args = STRVEC_INIT;
+	struct rev_info revs;
+	struct commit *commit;
+	struct merge_options merge_opt;
+	struct tree *next_tree, *base_tree, *head_tree;
+	struct merge_result result;
+	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 (argc != 5 || strcmp(argv[1], "--onto"))
+		die("usage: read the code, figure out how to use it, then do so");
+
+	onto = peel_committish(argv[2]);
+	strbuf_addf(&branch_name, "refs/heads/%s", argv[4]);
+
+	/* Sanity check */
+	if (get_oid("HEAD", &head))
+		die(_("Cannot read HEAD"));
+	assert(oideq(&onto->object.oid, &head));
+
+	hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
+	assert(repo_read_index(the_repository) >= 0);
+
+	repo_init_revisions(the_repository, &revs, NULL);
+	revs.verbose_header = 1;
+	revs.max_parents = 1;
+	revs.cherry_mark = 1;
+	revs.limited = 1;
+	revs.reverse = 1;
+	revs.right_only = 1;
+	revs.sort_order = REV_SORT_IN_GRAPH_ORDER;
+	revs.topo_order = 1;
+	strvec_pushl(&rev_walk_args, "", argv[4], "--not", argv[3], NULL);
+
+	if (setup_revisions(rev_walk_args.nr, rev_walk_args.v, &revs, NULL) > 1)
+		return error(_("unhandled options"));
+
+	strvec_clear(&rev_walk_args);
+
+	if (prepare_revision_walk(&revs) < 0)
+		return error(_("error preparing revisions"));
+
+	init_merge_options(&merge_opt, the_repository);
+	memset(&result, 0, sizeof(result));
+	merge_opt.show_rename_progress = 1;
+	merge_opt.branch1 = "HEAD";
+	head_tree = get_commit_tree(onto);
+	result.tree = head_tree;
+	last_commit = onto;
+	while ((commit = get_revision(&revs))) {
+		struct commit *base;
+
+		fprintf(stderr, "Rebasing %s...\r",
+			oid_to_hex(&commit->object.oid));
+		assert(commit->parents && !commit->parents->next);
+		base = commit->parents->item;
+
+		next_tree = get_commit_tree(commit);
+		base_tree = get_commit_tree(base);
+
+		merge_opt.branch2 = short_commit_name(commit);
+		merge_opt.ancestor = xstrfmt("parent of %s", merge_opt.branch2);
+
+		merge_incore_nonrecursive(&merge_opt,
+					  base_tree,
+					  result.tree,
+					  next_tree,
+					  &result);
+
+		free((char*)merge_opt.ancestor);
+		merge_opt.ancestor = NULL;
+		if (!result.clean)
+			die("Aborting: Hit a conflict and restarting is not implemented.");
+		last_picked_commit = commit;
+		last_commit = create_commit(result.tree, commit, last_commit);
+	}
+	fprintf(stderr, "\nDone.\n");
+	/* TODO: There should be some kind of rev_info_free(&revs) call... */
+	memset(&revs, 0, sizeof(revs));
+
+	merge_switch_to_result(&merge_opt, head_tree, &result, 1, !result.clean);
+
+	if (result.clean < 0)
+		exit(128);
+
+	strbuf_addf(&reflog_msg, "finish rebase %s onto %s",
+		    oid_to_hex(&last_picked_commit->object.oid),
+		    oid_to_hex(&last_commit->object.oid));
+	if (update_ref(reflog_msg.buf, branch_name.buf,
+		       &last_commit->object.oid,
+		       &last_picked_commit->object.oid,
+		       REF_NO_DEREF, UPDATE_REFS_MSG_ON_ERR)) {
+		error(_("could not update %s"), argv[4]);
+		die("Failed to update %s", argv[4]);
+	}
+	if (create_symref("HEAD", branch_name.buf, reflog_msg.buf) < 0)
+		die(_("unable to update HEAD"));
+	strbuf_release(&reflog_msg);
+	strbuf_release(&branch_name);
+
+	prime_cache_tree(the_repository, the_repository->index, result.tree);
+	if (write_locked_index(&the_index, &lock,
+			       COMMIT_LOCK | SKIP_IF_UNCHANGED))
+		die(_("unable to write %s"), get_index_file());
+	return (clean == 0);
+}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index a0d3966b29..8bce7db076 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -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 },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index 07034d3f38..fd0cafe5ca 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -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

[PATCH v5 4/4] merge,rebase,revert: select ort or recursive by config or environment

[Elijah Newren via GitGitGadget]

From: Elijah Newren <newren@gmail.com>

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.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 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(-)

diff --git a/builtin/merge.c b/builtin/merge.c
index 9d5359edc2..87dfc9bc06 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -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);
 
diff --git a/builtin/rebase.c b/builtin/rebase.c
index eeca53382f..4ba5295ddf 100644
--- a/builtin/rebase.c
+++ b/builtin/rebase.c
@@ -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:
diff --git a/builtin/revert.c b/builtin/revert.c
index f61cc5d82c..5b01a9baca 100644
--- a/builtin/revert.c
+++ b/builtin/revert.c
@@ -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);
diff --git a/sequencer.c b/sequencer.c
index 00acb12496..6b6c15c357 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -14,7 +14,8 @@
 #include "diff.h"
 #include "revision.h"
 #include "rerere.h"
-#include "merge-recursive.h"
+#include "merge-ort.h"
+#include "merge-ort-wrappers.h"
 #include "refs.h"
 #include "strvec.h"
 #include "quote.h"
@@ -204,6 +205,20 @@ static int git_sequencer_config(const char *k, const char *v, void *cb)
 		return 0;
 	}
 
+	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->default_strategy, ' ');
+			if (tmp)
+				*tmp = '\0';
+		}
+		return ret;
+	}
+
 	status = git_gpg_config(k, v, NULL);
 	if (status)
 		return status;
@@ -317,6 +332,7 @@ 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]);
@@ -595,8 +611,9 @@ static int do_recursive_merge(struct repository *r,
 			      struct replay_opts *opts)
 {
 	struct merge_options o;
+	struct merge_result result;
 	struct tree *next_tree, *base_tree, *head_tree;
-	int clean;
+	int clean, show_output;
 	int i;
 	struct lock_file index_lock = LOCK_INIT;
 
@@ -620,12 +637,27 @@ static int do_recursive_merge(struct repository *r,
 	for (i = 0; i < opts->xopts_nr; i++)
 		parse_merge_opt(&o, opts->xopts[i]);
 
-	clean = merge_trees(&o,
-			    head_tree,
-			    next_tree, base_tree);
-	if (is_rebase_i(opts) && clean <= 0)
-		fputs(o.obuf.buf, stdout);
-	strbuf_release(&o.obuf);
+	if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+		memset(&result, 0, sizeof(result));
+		merge_incore_nonrecursive(&o, base_tree, head_tree, next_tree,
+					    &result);
+		show_output = !is_rebase_i(opts) || !result.clean;
+		/*
+		 * TODO: merge_switch_to_result will update index/working tree;
+		 * we only really want to do that if !result.clean || this is
+		 * the final patch to be picked.  But determining this is the
+		 * final patch would take some work, and "head_tree" would need
+		 * to be replace with the tree the index matched before we
+		 * started doing any picks.
+		 */
+		merge_switch_to_result(&o, head_tree, &result, 1, show_output);
+		clean = result.clean;
+	} else {
+		clean = merge_trees(&o, head_tree, next_tree, base_tree);
+		if (is_rebase_i(opts) && clean <= 0)
+			fputs(o.obuf.buf, stdout);
+		strbuf_release(&o.obuf);
+	}
 	if (clean < 0) {
 		rollback_lock_file(&index_lock);
 		return clean;
@@ -1991,7 +2023,10 @@ static int do_pick_commit(struct repository *r,
 
 	if (is_rebase_i(opts) && write_author_script(msg.message) < 0)
 		res = -1;
-	else if (!opts->strategy || !strcmp(opts->strategy, "recursive") || command == TODO_REVERT) {
+	else if (!opts->strategy ||
+		 !strcmp(opts->strategy, "recursive") ||
+		 !strcmp(opts->strategy, "ort") ||
+		 command == TODO_REVERT) {
 		res = do_recursive_merge(r, base, next, base_label, next_label,
 					 &head, &msgbuf, opts);
 		if (res < 0)
@@ -3485,7 +3520,9 @@ static int do_merge(struct repository *r,
 	struct commit_list *bases, *j, *reversed = NULL;
 	struct commit_list *to_merge = NULL, **tail = &to_merge;
 	const char *strategy = !opts->xopts_nr &&
-		(!opts->strategy || !strcmp(opts->strategy, "recursive")) ?
+		(!opts->strategy ||
+		 !strcmp(opts->strategy, "recursive") ||
+		 !strcmp(opts->strategy, "ort")) ?
 		NULL : opts->strategy;
 	struct merge_options o;
 	int merge_arg_len, oneline_offset, can_fast_forward, ret, k;
@@ -3722,7 +3759,20 @@ static int do_merge(struct repository *r,
 	o.branch2 = ref_name.buf;
 	o.buffer_output = 2;
 
-	ret = merge_recursive(&o, head_commit, merge_commit, reversed, &i);
+	if (opts->strategy && !strcmp(opts->strategy, "ort")) {
+		/*
+		 * 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.
+		 */
+		ret = merge_ort_recursive(&o,
+					  head_commit, merge_commit, reversed,
+					  &i);
+	} else {
+		ret = merge_recursive(&o, head_commit, merge_commit, reversed,
+				      &i);
+	}
 	if (ret <= 0)
 		fputs(o.obuf.buf, stdout);
 	strbuf_release(&o.obuf);
diff --git a/sequencer.h b/sequencer.h
index b2a501e445..020b7fa118 100644
--- a/sequencer.h
+++ b/sequencer.h
@@ -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

Re: [PATCH v5 0/4] Beginning of new merge strategy: New API, empty implementation

[Junio C Hamano]

"Elijah Newren via GitGitGadget" <gitgitgadget@gmail.com> writes:

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

Will replace.  Thanks.

Re: [PATCH v4 0/4] Beginning of new merge strategy: New API, empty implementation

[Elijah Newren]

Hi Jake,

On Mon, Nov 2, 2020 at 10:52 AM Elijah Newren <newren@gmail.com> wrote:
>
> On Mon, Nov 2, 2020 at 1:28 AM Jacob Keller <jacob.keller@gmail.com> wrote:
> >
> > On Thu, Oct 29, 2020 at 1:34 PM Elijah Newren via GitGitGadget
> > <gitgitgadget@gmail.com> wrote:
> > >
> > > 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.
> > >
> >
> > 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!
>
> 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.

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