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>

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

Later in this patch series, we will mark the `refs/rewritten/` refs as
worktree-local, to allow for interactive rebases to be run in parallel in
worktrees linked to the same repository.

Signed-off-by: Johannes Schindelin <redacted>
---
 git-rebase--interactive.sh |   2 +
 sequencer.c                | 180 ++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 179 insertions(+), 3 deletions(-)

diff --git a/git-rebase--interactive.sh b/git-rebase--interactive.sh
index fcedece1860..7e5281e74aa 100644
--- a/git-rebase--interactive.sh
+++ b/git-rebase--interactive.sh

@@ -162,6 +162,8 @@ s, squash <commit> = use commit, but meld into previous commit
 f, fixup <commit> = like \"squash\", but discard this commit's log message
 x, exec <commit> = run command (the rest of the line) using shell
 d, drop <commit> = remove commit
+l, label <label> = label current HEAD with a name
+t, reset <label> = reset HEAD to a label

 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..92ca8d2adee 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,8 @@ enum todo_command {
        TODO_SQUASH,
        /* commands that do something else than handling a single commit */
        TODO_EXEC,
+       TODO_LABEL,
+       TODO_RESET,
        /* commands that do nothing but are counted for reporting progress */
        TODO_NOOP,
        TODO_DROP,

@@ -785,6 +796,8 @@ static struct {
        { 'f', "fixup" },
        { 's', "squash" },
        { 'x', "exec" },
+       { 'l', "label" },
+       { 't', "reset" },
        { 0,   "noop" },
        { 'd', "drop" },
        { 0,   NULL }

@@ -1253,7 +1266,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;

@@ -1279,7 +1293,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 +1934,144 @@ 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, "rebase -i (label) '%.*s'", len, name);
+
+       transaction = ref_store_transaction_begin(refs, &err);
+       if (!transaction) {
+               error("%s", err.buf);
+               ret = -1;
+       } else if (get_oid("HEAD", &head_oid)) {
+               error(_("could not read HEAD"));
+               ret = -1;
+       } else if (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;
+
+       /* Determine the length of the label */
+       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();