Merge branch 'en/merge-ort-api-null-impl'

Preparation for a new merge strategy.

* en/merge-ort-api-null-impl:
  merge,rebase,revert: select ort or recursive by config or environment
  fast-rebase: demonstrate merge-ort's API via new test-tool command
  merge-ort-wrappers: new convience wrappers to mimic the old merge API
  merge-ort: barebones API of new merge strategy with empty implementation

13 files changed, 517 insertions, 15 deletions

diff --git a/Makefile b/Makefile
index fea5ade..dd1cf41 100644
--- a/Makefile
+++ b/Makefile
@@ -705,6 +705,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
@@ -922,6 +923,8 @@ 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-ort-wrappers.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += merge.o
 LIB_OBJS += mergesort.o
diff --git a/builtin/merge.c b/builtin/merge.c
index 4c13340..1cff730 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 4bd9f25..19c7b37 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 da8997d..314a86c 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/merge-ort-wrappers.c b/merge-ort-wrappers.c
new file mode 100644
index 0000000..7eec25f
--- /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 0000000..0c4c57a
--- /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
diff --git a/merge-ort.c b/merge-ort.c
new file mode 100644
index 0000000..b487901
--- /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 0000000..74adcca
--- /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
diff --git a/sequencer.c b/sequencer.c
index 3dce6c9..221e987 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;
@@ -315,6 +330,7 @@ int sequencer_remove_state(struct replay_opts *opts)
 	}
 
 	free(opts->gpg_sign);
+	free(opts->default_strategy);
 	free(opts->strategy);
 	for (i = 0; i < opts->xopts_nr; i++)
 		free(opts->xopts[i]);
@@ -593,8 +609,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;
 
@@ -618,12 +635,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;
@@ -1989,7 +2021,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)
@@ -3484,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 +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 ce044ae..f8b2e4a 100644
--- a/sequencer.h
+++ b/sequencer.h
@@ -55,6 +55,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;
diff --git a/t/helper/test-fast-rebase.c b/t/helper/test-fast-rebase.c
new file mode 100644
index 0000000..3732122
--- /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 cab19a9..9d6d14d 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -29,6 +29,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 1467f00..a6470ff 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -19,6 +19,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);