[PATCH 0/8] rebase -i: offer to recreate merge commits

[PATCH 0/8] rebase -i: offer to recreate merge commits

[Johannes Schindelin]

Once upon a time, I dreamt of an interactive rebase that would not
flatten branch structure, but instead recreate the commit topology
faithfully.

My original attempt was --preserve-merges, but that design was so
limited that I did not even enable it in interactive mode.

Subsequently, it *was* enabled in interactive mode, with the predictable
consequences: as the --preserve-merges design does not allow for
specifying the parents of merge commits explicitly, all the new commits'
parents are defined *implicitly* by the previous commit history, and
hence it is *not possible to even reorder commits*.

This design flaw cannot be fixed. Not without a complete re-design, at
least. This patch series offers such a re-design.

Think of --recreate-merges as "--preserve-merges done right". It
introduces new verbs for the todo list, `label`, `reset` and `merge`.
For a commit topology like this:

            A - B - C
              \   /
                D

the generated todo list would look like this:

            # branch D
            pick 0123 A
            label branch-point
            pick 1234 D
            label D

            reset branch-point
            pick 2345 B
            merge 3456 D C

There are more patches in the pipeline, based on this patch series, but
left for later in the interest of reviewable patch series: one mini
series to use the sequencer even for `git rebase -i --root`, and another
one to add support for octopus merges to --recreate-merges.


Johannes Schindelin (8):
  sequencer: introduce new commands to reset the revision
  sequencer: introduce the `merge` command
  sequencer: fast-forward merge commits, if possible
  rebase-helper --make-script: introduce a flag to recreate merges
  rebase: introduce the --recreate-merges option
  sequencer: handle autosquash and post-rewrite for merge commands
  pull: accept --rebase=recreate to recreate the branch topology
  rebase -i: introduce --recreate-merges=no-rebase-cousins

 Documentation/config.txt               |   8 +
 Documentation/git-pull.txt             |   5 +-
 Documentation/git-rebase.txt           |  13 +-
 builtin/pull.c                         |  14 +-
 builtin/rebase--helper.c               |  13 +-
 builtin/remote.c                       |   2 +
 contrib/completion/git-completion.bash |   4 +-
 git-rebase--interactive.sh             |   6 +
 git-rebase.sh                          |  16 +
 refs.c                                 |   3 +-
 sequencer.c                            | 697 ++++++++++++++++++++++++++++++++-
 sequencer.h                            |   9 +
 t/t3430-rebase-recreate-merges.sh      | 208 ++++++++++
 13 files changed, 977 insertions(+), 21 deletions(-)
 create mode 100755 t/t3430-rebase-recreate-merges.sh


base-commit: 2512f15446149235156528dafbe75930c712b29e
Published-As: https://github.com/dscho/git/releases/tag/recreate-merges-v1
Fetch-It-Via: git fetch https://github.com/dscho/git recreate-merges-v1
-- 
2.15.1.windows.2.1430.ga56c4f9e2a9

[PATCH 1/8] sequencer: introduce new commands to reset the revision

[Johannes Schindelin]

In the upcoming commits, we will teach the sequencer to recreate merges.
This will be done in a very different way from the unfortunate design of
`git rebase --preserve-merges` (which does not allow for reordering
commits, or changing the branch topology).

The main idea is to introduce new todo list commands, to support
labeling the current revision with a given name, resetting the current
revision to a previous state, merging labeled revisions.

This idea was developed in Git for Windows' Git garden shears (that are
used to maintain the "thicket of branches" on top of upstream Git), and
this patch is part of the effort to make it available to a wider
audience, as well as to make the entire process more robust (by
implementing it in a safe and portable language rather than a Unix shell
script).

This commit implements the commands to label, and to reset to, given
revisions. The syntax is:

	label <name>
	reset <name>

As a convenience shortcut, also to improve readability of the generated
todo list, a third command is introduced: bud. It simply resets to the
"onto" revision, i.e. the commit onto which we currently rebase.

Internally, the `label <name>` command creates the ref
`refs/rewritten/<name>`. This makes it possible to work with the labeled
revisions interactively, or in a scripted fashion (e.g. via the todo
list command `exec`).

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
 git-rebase--interactive.sh |   3 +
 sequencer.c                | 181 ++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 180 insertions(+), 4 deletions(-)

diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
index d47bd29593a..3d2cd19d65a 100644
--- a/git-rebase--interactive.sh
+++ b/git-rebase--interactive.sh
@@ -162,6 +162,9 @@ s, squash = use commit, but meld into previous commit
 f, fixup = like \"squash\", but discard this commit's log message
 x, exec = run command (the rest of the line) using shell
 d, drop = remove commit
+l, label = label current HEAD with a name
+t, reset = reset HEAD to a label
+b, bud = reset HEAD to the revision labeled 'onto'
 
 These lines can be re-ordered; they are executed from top to bottom.
 " | git stripspace --comment-lines >>"$todo"
diff --git a/sequencer.c b/sequencer.c
index 4d3f60594cb..91cc55a002f 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -21,6 +21,8 @@
 #include "log-tree.h"
 #include "wt-status.h"
 #include "hashmap.h"
+#include "unpack-trees.h"
+#include "worktree.h"
 
 #define GIT_REFLOG_ACTION "GIT_REFLOG_ACTION"
 
@@ -116,6 +118,13 @@ static GIT_PATH_FUNC(rebase_path_stopped_sha, "rebase-merge/stopped-sha")
 static GIT_PATH_FUNC(rebase_path_rewritten_list, "rebase-merge/rewritten-list")
 static GIT_PATH_FUNC(rebase_path_rewritten_pending,
 	"rebase-merge/rewritten-pending")
+
+/*
+ * The path of the file listing refs that need to be deleted after the rebase
+ * finishes. This is used by the `merge` command.
+ */
+static GIT_PATH_FUNC(rebase_path_refs_to_delete, "rebase-merge/refs-to-delete")
+
 /*
  * The following files are written by git-rebase just after parsing the
  * command-line (and are only consumed, not modified, by the sequencer).
@@ -767,6 +776,9 @@ enum todo_command {
 	TODO_SQUASH,
 	/* commands that do something else than handling a single commit */
 	TODO_EXEC,
+	TODO_LABEL,
+	TODO_RESET,
+	TODO_BUD,
 	/* commands that do nothing but are counted for reporting progress */
 	TODO_NOOP,
 	TODO_DROP,
@@ -785,6 +797,9 @@ static struct {
 	{ 'f', "fixup" },
 	{ 's', "squash" },
 	{ 'x', "exec" },
+	{ 'l', "label" },
+	{ 't', "reset" },
+	{ 'b', "bud" },
 	{ 0,   "noop" },
 	{ 'd', "drop" },
 	{ 0,   NULL }
@@ -1253,7 +1268,8 @@ static int parse_insn_line(struct todo_item *item, const char *bol, char *eol)
 		if (skip_prefix(bol, todo_command_info[i].str, &bol)) {
 			item->command = i;
 			break;
-		} else if (bol[1] == ' ' && *bol == todo_command_info[i].c) {
+		} else if ((bol + 1 == eol || bol[1] == ' ') &&
+			   *bol == todo_command_info[i].c) {
 			bol++;
 			item->command = i;
 			break;
@@ -1265,7 +1281,7 @@ static int parse_insn_line(struct todo_item *item, const char *bol, char *eol)
 	padding = strspn(bol, " \t");
 	bol += padding;
 
-	if (item->command == TODO_NOOP) {
+	if (item->command == TODO_NOOP || item->command == TODO_BUD) {
 		if (bol != eol)
 			return error(_("%s does not accept arguments: '%s'"),
 				     command_to_string(item->command), bol);
@@ -1279,7 +1295,8 @@ static int parse_insn_line(struct todo_item *item, const char *bol, char *eol)
 		return error(_("missing arguments for %s"),
 			     command_to_string(item->command));
 
-	if (item->command == TODO_EXEC) {
+	if (item->command == TODO_EXEC || item->command == TODO_LABEL ||
+	    item->command == TODO_RESET) {
 		item->commit = NULL;
 		item->arg = bol;
 		item->arg_len = (int)(eol - bol);
@@ -1919,6 +1936,139 @@ static int do_exec(const char *command_line)
 	return status;
 }
 
+static int safe_append(const char *filename, const char *fmt, ...)
+{
+	va_list ap;
+	struct lock_file lock = LOCK_INIT;
+	int fd = hold_lock_file_for_update(&lock, filename, 0);
+	struct strbuf buf = STRBUF_INIT;
+
+	if (fd < 0)
+		return error_errno(_("could not lock '%s'"), filename);
+
+	if (strbuf_read_file(&buf, filename, 0) < 0 && errno != ENOENT)
+		return error_errno(_("could not read '%s'"), filename);
+	strbuf_complete(&buf, '\n');
+	va_start(ap, fmt);
+	strbuf_vaddf(&buf, fmt, ap);
+	va_end(ap);
+
+	if (write_in_full(fd, buf.buf, buf.len) < 0) {
+		rollback_lock_file(&lock);
+		return error_errno(_("could not write to '%s'"), filename);
+	}
+	if (commit_lock_file(&lock) < 0) {
+		rollback_lock_file(&lock);
+		return error(_("failed to finalize '%s'."), filename);
+	}
+
+	return 0;
+}
+
+static int do_label(const char *name, int len)
+{
+	struct ref_store *refs = get_main_ref_store();
+	struct ref_transaction *transaction;
+	struct strbuf ref_name = STRBUF_INIT, err = STRBUF_INIT;
+	struct strbuf msg = STRBUF_INIT;
+	int ret = 0;
+	struct object_id head_oid;
+
+	strbuf_addf(&ref_name, "refs/rewritten/%.*s", len, name);
+	strbuf_addf(&msg, "label '%.*s'", len, name);
+
+	transaction = ref_store_transaction_begin(refs, &err);
+	if (!transaction ||
+	    get_oid("HEAD", &head_oid) ||
+	    ref_transaction_update(transaction, ref_name.buf, &head_oid, NULL,
+				   0, msg.buf, &err) < 0 ||
+	    ref_transaction_commit(transaction, &err)) {
+		error("%s", err.buf);
+		ret = -1;
+	}
+	ref_transaction_free(transaction);
+	strbuf_release(&err);
+	strbuf_release(&msg);
+
+	if (!ret)
+		ret = safe_append(rebase_path_refs_to_delete(),
+				  "%s\n", ref_name.buf);
+	strbuf_release(&ref_name);
+
+	return ret;
+}
+
+static int do_reset(const char *name, int len)
+{
+	struct strbuf ref_name = STRBUF_INIT;
+	struct object_id oid;
+	struct lock_file lock = LOCK_INIT;
+	struct tree_desc desc;
+	struct tree *tree;
+	struct unpack_trees_options opts;
+	int ret = 0, i;
+
+	if (hold_locked_index(&lock, LOCK_REPORT_ON_ERROR) < 0)
+		return -1;
+
+	for (i = 0; i < len; i++)
+		if (isspace(name[i]))
+			len = i;
+
+	strbuf_addf(&ref_name, "refs/rewritten/%.*s", len, name);
+	if (get_oid(ref_name.buf, &oid) &&
+	    get_oid(ref_name.buf + strlen("refs/rewritten/"), &oid)) {
+		error(_("could not read '%s'"), ref_name.buf);
+		rollback_lock_file(&lock);
+		strbuf_release(&ref_name);
+		return -1;
+	}
+
+	memset(&opts, 0, sizeof(opts));
+	opts.head_idx = 1;
+	opts.src_index = &the_index;
+	opts.dst_index = &the_index;
+	opts.fn = oneway_merge;
+	opts.merge = 1;
+	opts.update = 1;
+	opts.reset = 1;
+
+	read_cache_unmerged();
+	if (!fill_tree_descriptor(&desc, &oid)) {
+		error(_("Failed to find tree of %s."), oid_to_hex(&oid));
+		rollback_lock_file(&lock);
+		free((void *)desc.buffer);
+		strbuf_release(&ref_name);
+		return -1;
+	}
+
+	if (unpack_trees(1, &desc, &opts)) {
+		rollback_lock_file(&lock);
+		free((void *)desc.buffer);
+		strbuf_release(&ref_name);
+		return -1;
+	}
+
+	tree = parse_tree_indirect(&oid);
+	prime_cache_tree(&the_index, tree);
+
+	if (write_locked_index(&the_index, &lock, COMMIT_LOCK) < 0)
+		ret = error(_("could not write index"));
+	free((void *)desc.buffer);
+
+	if (!ret) {
+		struct strbuf msg = STRBUF_INIT;
+
+		strbuf_addf(&msg, "(rebase -i) reset '%.*s'", len, name);
+		ret = update_ref(msg.buf, "HEAD", &oid, NULL, 0,
+				 UPDATE_REFS_MSG_ON_ERR);
+		strbuf_release(&msg);
+	}
+
+	strbuf_release(&ref_name);
+	return ret;
+}
+
 static int is_final_fixup(struct todo_list *todo_list)
 {
 	int i = todo_list->current;
@@ -2102,7 +2252,13 @@ static int pick_commits(struct todo_list *todo_list, struct replay_opts *opts)
 				/* `current` will be incremented below */
 				todo_list->current = -1;
 			}
-		} else if (!is_noop(item->command))
+		} else if (item->command == TODO_LABEL)
+			res = do_label(item->arg, item->arg_len);
+		else if (item->command == TODO_RESET)
+			res = do_reset(item->arg, item->arg_len);
+		else if (item->command == TODO_BUD)
+			res = do_reset("onto", 4);
+		else if (!is_noop(item->command))
 			return error(_("unknown command %d"), item->command);
 
 		todo_list->current++;
@@ -2207,6 +2363,23 @@ static int pick_commits(struct todo_list *todo_list, struct replay_opts *opts)
 		}
 		apply_autostash(opts);
 
+		strbuf_reset(&buf);
+		if (strbuf_read_file(&buf, rebase_path_refs_to_delete(), 0)
+		    > 0) {
+			char *p = buf.buf;
+			while (*p) {
+				char *eol = strchr(p, '\n');
+				if (eol)
+					*eol = '\0';
+				if (delete_ref("(rebase -i) cleanup",
+					       p, NULL, 0) < 0)
+					warning(_("could not delete '%s'"), p);
+				if (!eol)
+					break;
+				p = eol + 1;
+			}
+		}
+
 		fprintf(stderr, "Successfully rebased and updated %s.\n",
 			head_ref.buf);
 
-- 
2.15.1.windows.2.1430.ga56c4f9e2a9

[PATCH 2/8] sequencer: introduce the `merge` command

[Johannes Schindelin]

This patch is part of the effort to reimplement `--preserve-merges` with
a substantially improved design, a design that has been developed in the
Git for Windows project to maintain the dozens of Windows-specific patch
series on top of upstream Git.

The previous patch implemented the `label`, `bud` and `reset` commands
to label commits and to reset to a labeled commits. This patch adds the
`merge` command, with the following syntax:

	merge <commit> <rev> <oneline>

The <commit> parameter in this instance is the *original* merge commit,
whose author and message will be used for the to-be-created merge
commit.

The <rev> parameter refers to the (possibly rewritten) revision to
merge. Let's see an example of a todo list:

	label onto

	# Branch abc
	bud
	pick deadbeef Hello, world!
	label abc

	bud
	pick cafecafe And now for something completely different
	merge baaabaaa abc Merge the branch 'abc' into master

To support creating *new* merges, i.e. without copying the commit
message from an existing commit, use the special value `-` as <commit>
parameter (in which case the text after the <rev> parameter is used as
commit message):

	merge - abc This will be the actual commit message of the merge

This comes in handy when splitting a branch into two or more branches.

Note: this patch only adds support for recursive merges, to keep things
simple. Support for octopus merges will be added later in this patch
series, support for merges using strategies other than the recursive
merge is left for future contributions.

The design of the `merge` command as introduced by this patch only
supports creating new merge commits with exactly two parents, i.e. it
adds no support for octopus merges.

We will introduce support for octopus merges in a later commit.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
 git-rebase--interactive.sh |   1 +
 sequencer.c                | 146 +++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 143 insertions(+), 4 deletions(-)

diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
index 3d2cd19d65a..5bf1ea3781f 100644
--- a/git-rebase--interactive.sh
+++ b/git-rebase--interactive.sh
@@ -165,6 +165,7 @@ d, drop = remove commit
 l, label = label current HEAD with a name
 t, reset = reset HEAD to a label
 b, bud = reset HEAD to the revision labeled 'onto'
+m, merge = create a merge commit using a given commit's message
 
 These lines can be re-ordered; they are executed from top to bottom.
 " | git stripspace --comment-lines >>"$todo"
diff --git a/sequencer.c b/sequencer.c
index 91cc55a002f..567cfcbbe8b 100644
--- a/sequencer.c
+++ b/sequencer.c
@@ -779,6 +779,7 @@ enum todo_command {
 	TODO_LABEL,
 	TODO_RESET,
 	TODO_BUD,
+	TODO_MERGE,
 	/* commands that do nothing but are counted for reporting progress */
 	TODO_NOOP,
 	TODO_DROP,
@@ -800,6 +801,7 @@ static struct {
 	{ 'l', "label" },
 	{ 't', "reset" },
 	{ 'b', "bud" },
+	{ 'm', "merge" },
 	{ 0,   "noop" },
 	{ 'd', "drop" },
 	{ 0,   NULL }
@@ -1304,14 +1306,20 @@ static int parse_insn_line(struct todo_item *item, const char *bol, char *eol)
 	}
 
 	end_of_object_name = (char *) bol + strcspn(bol, " \t\n");
+	item->arg = end_of_object_name + strspn(end_of_object_name, " \t");
+	item->arg_len = (int)(eol - item->arg);
+
 	saved = *end_of_object_name;
+	if (item->command == TODO_MERGE && *bol == '-' &&
+	    bol + 1 == end_of_object_name) {
+		item->commit = NULL;
+		return 0;
+	}
+
 	*end_of_object_name = '\0';
 	status = get_oid(bol, &commit_oid);
 	*end_of_object_name = saved;
 
-	item->arg = end_of_object_name + strspn(end_of_object_name, " \t");
-	item->arg_len = (int)(eol - item->arg);
-
 	if (status < 0)
 		return -1;
 
@@ -2069,6 +2077,132 @@ static int do_reset(const char *name, int len)
 	return ret;
 }
 
+static int do_merge(struct commit *commit, const char *arg, int arg_len,
+		    struct replay_opts *opts)
+{
+	int merge_arg_len;
+	struct strbuf ref_name = STRBUF_INIT;
+	struct commit *head_commit, *merge_commit, *i;
+	struct commit_list *common, *j, *reversed = NULL;
+	struct merge_options o;
+	int ret;
+	st