Merge branch 'ml/filter-branch-no-op-error' into next
[gitweb.git] / sequencer.c
index 091bd6bda5c55c27e2d0688a5e12988e22e6e431..d34ffd392c07e38882dcf9145421bb0766e753cc 100644 (file)
 #include "hashmap.h"
 #include "notes-utils.h"
 #include "sigchain.h"
+#include "unpack-trees.h"
+#include "worktree.h"
+#include "oidmap.h"
+#include "oidset.h"
 
 #define GIT_REFLOG_ACTION "GIT_REFLOG_ACTION"
 
@@ -120,6 +124,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 `label` command to record the need for cleanup.
+ */
+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).
@@ -244,18 +255,33 @@ static const char *gpg_sign_opt_quoted(struct replay_opts *opts)
 
 int sequencer_remove_state(struct replay_opts *opts)
 {
-       struct strbuf dir = STRBUF_INIT;
+       struct strbuf buf = STRBUF_INIT;
        int i;
 
+       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;
+               }
+       }
+
        free(opts->gpg_sign);
        free(opts->strategy);
        for (i = 0; i < opts->xopts_nr; i++)
                free(opts->xopts[i]);
        free(opts->xopts);
 
-       strbuf_addstr(&dir, get_dir(opts));
-       remove_dir_recursively(&dir, 0);
-       strbuf_release(&dir);
+       strbuf_reset(&buf);
+       strbuf_addstr(&buf, get_dir(opts));
+       remove_dir_recursively(&buf, 0);
+       strbuf_release(&buf);
 
        return 0;
 }
@@ -345,12 +371,14 @@ static int write_message(const void *buf, size_t len, const char *filename,
        if (msg_fd < 0)
                return error_errno(_("could not lock '%s'"), filename);
        if (write_in_full(msg_fd, buf, len) < 0) {
+               error_errno(_("could not write to '%s'"), filename);
                rollback_lock_file(&msg_file);
-               return error_errno(_("could not write to '%s'"), filename);
+               return -1;
        }
        if (append_eol && write(msg_fd, "\n", 1) < 0) {
+               error_errno(_("could not write eol to '%s'"), filename);
                rollback_lock_file(&msg_file);
-               return error_errno(_("could not write eol to '%s'"), filename);
+               return -1;
        }
        if (commit_lock_file(&msg_file) < 0)
                return error(_("failed to finalize '%s'"), filename);
@@ -517,15 +545,14 @@ static int do_recursive_merge(struct commit *base, struct commit *next,
                return clean;
        }
 
-       if (active_cache_changed &&
-           write_locked_index(&the_index, &index_lock, COMMIT_LOCK))
+       if (write_locked_index(&the_index, &index_lock,
+                              COMMIT_LOCK | SKIP_IF_UNCHANGED))
                /*
                 * TRANSLATORS: %s will be "revert", "cherry-pick" or
                 * "rebase -i".
                 */
                return error(_("%s: Unable to write new index file"),
                        _(action_name(opts)));
-       rollback_lock_file(&index_lock);
 
        if (!clean)
                append_conflicts_hint(msgbuf);
@@ -1278,6 +1305,10 @@ enum todo_command {
        TODO_SQUASH,
        /* commands that do something else than handling a single commit */
        TODO_EXEC,
+       TODO_LABEL,
+       TODO_RESET,
+       TODO_MERGE,
+       TODO_MERGE_AND_EDIT,
        /* commands that do nothing but are counted for reporting progress */
        TODO_NOOP,
        TODO_DROP,
@@ -1296,6 +1327,10 @@ static struct {
        { 'f', "fixup" },
        { 's', "squash" },
        { 'x', "exec" },
+       { 'l', "label" },
+       { 't', "reset" },
+       { 'm', "merge" },
+       { 0, "merge" }, /* MERGE_AND_EDIT */
        { 0,   "noop" },
        { 'd', "drop" },
        { 0,   NULL }
@@ -1713,13 +1748,13 @@ static int read_and_refresh_cache(struct replay_opts *opts)
                        _(action_name(opts)));
        }
        refresh_index(&the_index, REFRESH_QUIET|REFRESH_UNMERGED, NULL, NULL, NULL);
-       if (the_index.cache_changed && index_fd >= 0) {
-               if (write_locked_index(&the_index, &index_lock, COMMIT_LOCK)) {
+       if (index_fd >= 0) {
+               if (write_locked_index(&the_index, &index_lock,
+                                      COMMIT_LOCK | SKIP_IF_UNCHANGED)) {
                        return error(_("git %s: failed to refresh the index"),
                                _(action_name(opts)));
                }
        }
-       rollback_lock_file(&index_lock);
        return 0;
 }
 
@@ -1801,13 +1836,29 @@ 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);
                return 0;
        }
 
+       if (item->command == TODO_MERGE) {
+               if (skip_prefix(bol, "-C", &bol))
+                       bol += strspn(bol, " \t");
+               else if (skip_prefix(bol, "-c", &bol)) {
+                       bol += strspn(bol, " \t");
+                       item->command = TODO_MERGE_AND_EDIT;
+               } else {
+                       item->command = TODO_MERGE_AND_EDIT;
+                       item->commit = NULL;
+                       item->arg = bol;
+                       item->arg_len = (int)(eol - bol);
+                       return 0;
+               }
+       }
+
        end_of_object_name = (char *) bol + strcspn(bol, " \t\n");
        saved = *end_of_object_name;
        *end_of_object_name = '\0';
@@ -2120,9 +2171,9 @@ static int save_head(const char *head)
        written = write_in_full(fd, buf.buf, buf.len);
        strbuf_release(&buf);
        if (written < 0) {
+               error_errno(_("could not write to '%s'"), git_path_head_file());
                rollback_lock_file(&head_lock);
-               return error_errno(_("could not write to '%s'"),
-                                  git_path_head_file());
+               return -1;
        }
        if (commit_lock_file(&head_lock) < 0)
                return error(_("failed to finalize '%s'"), git_path_head_file());
@@ -2449,6 +2500,304 @@ 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,
+                                          LOCK_REPORT_ON_ERROR);
+       struct strbuf buf = STRBUF_INIT;
+
+       if (fd < 0)
+               return -1;
+
+       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) {
+               error_errno(_("could not write to '%s'"), filename);
+               strbuf_release(&buf);
+               rollback_lock_file(&lock);
+               return -1;
+       }
+       if (commit_lock_file(&lock) < 0) {
+               strbuf_release(&buf);
+               rollback_lock_file(&lock);
+               return error(_("failed to finalize '%s'"), filename);
+       }
+
+       strbuf_release(&buf);
+       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;
+
+       if (len == 1 && *name == '#')
+               return error("Illegal label name: '%.*s'", len, name);
+
+       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 replay_opts *opts)
+{
+       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 unpack_tree_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(&unpack_tree_opts, 0, sizeof(unpack_tree_opts));
+       unpack_tree_opts.head_idx = 1;
+       unpack_tree_opts.src_index = &the_index;
+       unpack_tree_opts.dst_index = &the_index;
+       unpack_tree_opts.fn = oneway_merge;
+       unpack_tree_opts.merge = 1;
+       unpack_tree_opts.update = 1;
+       unpack_tree_opts.reset = 1;
+
+       if (read_cache_unmerged()) {
+               rollback_lock_file(&lock);
+               strbuf_release(&ref_name);
+               return error_resolve_conflict(_(action_name(opts)));
+       }
+
+       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, &unpack_tree_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 do_merge(struct commit *commit, const char *arg, int arg_len,
+                   int run_commit_flags, 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 can_fast_forward, ret;
+       static struct lock_file lock;
+
+       for (merge_arg_len = 0; merge_arg_len < arg_len; merge_arg_len++)
+               if (isspace(arg[merge_arg_len]))
+                       break;
+
+       if (hold_locked_index(&lock, LOCK_REPORT_ON_ERROR) < 0)
+               return -1;
+
+       head_commit = lookup_commit_reference_by_name("HEAD");
+       if (!head_commit) {
+               rollback_lock_file(&lock);
+               return error(_("cannot merge without a current revision"));
+       }
+
+       if (commit) {
+               const char *message = get_commit_buffer(commit, NULL);
+               const char *body;
+               int len;
+
+               if (!message) {
+                       rollback_lock_file(&lock);
+                       return error(_("could not get commit message of '%s'"),
+                                    oid_to_hex(&commit->object.oid));
+               }
+               write_author_script(message);
+               find_commit_subject(message, &body);
+               len = strlen(body);
+               if (write_message(body, len, git_path_merge_msg(), 0) < 0) {
+                       error_errno(_("could not write '%s'"),
+                                   git_path_merge_msg());
+                       unuse_commit_buffer(commit, message);
+                       rollback_lock_file(&lock);
+                       return -1;
+               }
+               unuse_commit_buffer(commit, message);
+       } else {
+               const char *p = arg + merge_arg_len;
+               struct strbuf buf = STRBUF_INIT;
+               int len;
+
+               strbuf_addf(&buf, "author %s", git_author_info(0));
+               write_author_script(buf.buf);
+               strbuf_reset(&buf);
+
+               p += strspn(p, " \t");
+               if (*p == '#' && isspace(p[1]))
+                       p += 1 + strspn(p + 1, " \t");
+               if (*p)
+                       len = strlen(p);
+               else {
+                       strbuf_addf(&buf, "Merge branch '%.*s'",
+                                   merge_arg_len, arg);
+                       p = buf.buf;
+                       len = buf.len;
+               }
+
+               if (write_message(p, len, git_path_merge_msg(), 0) < 0) {
+                       error_errno(_("could not write '%s'"),
+                                   git_path_merge_msg());
+                       strbuf_release(&buf);
+                       rollback_lock_file(&lock);
+                       return -1;
+               }
+               strbuf_release(&buf);
+       }
+
+       /*
+        * If HEAD is not identical to the parent of the original merge commit,
+        * we cannot fast-forward.
+        */
+       can_fast_forward = opts->allow_ff && commit && commit->parents &&
+               !oidcmp(&commit->parents->item->object.oid,
+                       &head_commit->object.oid);
+
+       strbuf_addf(&ref_name, "refs/rewritten/%.*s", merge_arg_len, arg);
+       merge_commit = lookup_commit_reference_by_name(ref_name.buf);
+       if (!merge_commit) {
+               /* fall back to non-rewritten ref or commit */
+               strbuf_splice(&ref_name, 0, strlen("refs/rewritten/"), "", 0);
+               merge_commit = lookup_commit_reference_by_name(ref_name.buf);
+       }
+       if (!merge_commit) {
+               error(_("could not resolve '%s'"), ref_name.buf);
+               strbuf_release(&ref_name);
+               rollback_lock_file(&lock);
+               return -1;
+       }
+
+       if (can_fast_forward && commit->parents->next &&
+           !commit->parents->next->next &&
+           !oidcmp(&commit->parents->next->item->object.oid,
+                   &merge_commit->object.oid)) {
+               strbuf_release(&ref_name);
+               rollback_lock_file(&lock);
+               return fast_forward_to(&commit->object.oid,
+                                      &head_commit->object.oid, 0, opts);
+       }
+
+       write_message(oid_to_hex(&merge_commit->object.oid), GIT_SHA1_HEXSZ,
+                     git_path_merge_head(), 0);
+       write_message("no-ff", 5, git_path_merge_mode(), 0);
+
+       common = get_merge_bases(head_commit, merge_commit);
+       for (j = common; j; j = j->next)
+               commit_list_insert(j->item, &reversed);
+       free_commit_list(common);
+
+       read_cache();
+       init_merge_options(&o);
+       o.branch1 = "HEAD";
+       o.branch2 = ref_name.buf;
+       o.buffer_output = 2;
+
+       ret = merge_recursive(&o, head_commit, merge_commit, reversed, &i);
+       if (ret <= 0)
+               fputs(o.obuf.buf, stdout);
+       strbuf_release(&o.obuf);
+       if (ret < 0) {
+               strbuf_release(&ref_name);
+               rollback_lock_file(&lock);
+               return error(_("conflicts while merging '%.*s'"),
+                            merge_arg_len, arg);
+       }
+
+       if (active_cache_changed &&
+           write_locked_index(&the_index, &lock, COMMIT_LOCK)) {
+               strbuf_release(&ref_name);
+               return error(_("merge: Unable to write new index file"));
+       }
+       rollback_lock_file(&lock);
+
+       ret = run_git_commit(git_path_merge_msg(), opts, run_commit_flags);
+       strbuf_release(&ref_name);
+
+       return ret;
+}
+
 static int is_final_fixup(struct todo_list *todo_list)
 {
        int i = todo_list->current;
@@ -2633,6 +2982,18 @@ static int pick_commits(struct todo_list *todo_list, struct replay_opts *opts)
                                /* `current` will be incremented below */
                                todo_list->current = -1;
                        }
+               } 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, opts);
+               else if (item->command == TODO_MERGE ||
+                        item->command == TODO_MERGE_AND_EDIT) {
+                       res = do_merge(item->commit, item->arg, item->arg_len,
+                                      item->command == TODO_MERGE_AND_EDIT ?
+                                      EDIT_MSG | VERIFY_MSG : 0, opts);
+                       if (item->commit)
+                               record_in_rewritten(&item->commit->object.oid,
+                                                   peek_command(todo_list, 1));
                } else if (!is_noop(item->command))
                        return error(_("unknown command %d"), item->command);
 
@@ -2987,6 +3348,345 @@ void append_signoff(struct strbuf *msgbuf, int ignore_footer, unsigned flag)
        strbuf_release(&sob);
 }
 
+struct labels_entry {
+       struct hashmap_entry entry;
+       char label[FLEX_ARRAY];
+};
+
+static int labels_cmp(const void *fndata, const struct labels_entry *a,
+                     const struct labels_entry *b, const void *key)
+{
+       return key ? strcmp(a->label, key) : strcmp(a->label, b->label);
+}
+
+struct string_entry {
+       struct oidmap_entry entry;
+       char string[FLEX_ARRAY];
+};
+
+struct label_state {
+       struct oidmap commit2label;
+       struct hashmap labels;
+       struct strbuf buf;
+};
+
+static const char *label_oid(struct object_id *oid, const char *label,
+                            struct label_state *state)
+{
+       struct labels_entry *labels_entry;
+       struct string_entry *string_entry;
+       struct object_id dummy;
+       size_t len;
+       int i;
+
+       string_entry = oidmap_get(&state->commit2label, oid);
+       if (string_entry)
+               return string_entry->string;
+
+       /*
+        * For "uninteresting" commits, i.e. commits that are not to be
+        * rebased, and which can therefore not be labeled, we use a unique
+        * abbreviation of the commit name. This is slightly more complicated
+        * than calling find_unique_abbrev() because we also need to make
+        * sure that the abbreviation does not conflict with any other
+        * label.
+        *
+        * We disallow "interesting" commits to be labeled by a string that
+        * is a valid full-length hash, to ensure that we always can find an
+        * abbreviation for any uninteresting commit's names that does not
+        * clash with any other label.
+        */
+       if (!label) {
+               char *p;
+
+               strbuf_reset(&state->buf);
+               strbuf_grow(&state->buf, GIT_SHA1_HEXSZ);
+               label = p = state->buf.buf;
+
+               find_unique_abbrev_r(p, oid->hash, default_abbrev);
+
+               /*
+                * We may need to extend the abbreviated hash so that there is
+                * no conflicting label.
+                */
+               if (hashmap_get_from_hash(&state->labels, strihash(p), p)) {
+                       size_t i = strlen(p) + 1;
+
+                       oid_to_hex_r(p, oid);
+                       for (; i < GIT_SHA1_HEXSZ; i++) {
+                               char save = p[i];
+                               p[i] = '\0';
+                               if (!hashmap_get_from_hash(&state->labels,
+                                                          strihash(p), p))
+                                       break;
+                               p[i] = save;
+                       }
+               }
+       } else if (((len = strlen(label)) == GIT_SHA1_RAWSZ &&
+                   !get_oid_hex(label, &dummy)) ||
+                  (len == 1 && *label == '#') ||
+                  hashmap_get_from_hash(&state->labels,
+                                        strihash(label), label)) {
+               /*
+                * If the label already exists, or if the label is a valid full
+                * OID, or the label is a '#' (which we use as a separator
+                * between merge heads and oneline), we append a dash and a
+                * number to make it unique.
+                */
+               struct strbuf *buf = &state->buf;
+
+               strbuf_reset(buf);
+               strbuf_add(buf, label, len);
+
+               for (i = 2; ; i++) {
+                       strbuf_setlen(buf, len);
+                       strbuf_addf(buf, "-%d", i);
+                       if (!hashmap_get_from_hash(&state->labels,
+                                                  strihash(buf->buf),
+                                                  buf->buf))
+                               break;
+               }
+
+               label = buf->buf;
+       }
+
+       FLEX_ALLOC_STR(labels_entry, label, label);
+       hashmap_entry_init(labels_entry, strihash(label));
+       hashmap_add(&state->labels, labels_entry);
+
+       FLEX_ALLOC_STR(string_entry, string, label);
+       oidcpy(&string_entry->entry.oid, oid);
+       oidmap_put(&state->commit2label, string_entry);
+
+       return string_entry->string;
+}
+
+static int make_script_with_merges(struct pretty_print_context *pp,
+                                  struct rev_info *revs, FILE *out,
+                                  unsigned flags)
+{
+       int keep_empty = flags & TODO_LIST_KEEP_EMPTY;
+       int rebase_cousins = flags & TODO_LIST_REBASE_COUSINS;
+       struct strbuf buf = STRBUF_INIT, oneline = STRBUF_INIT;
+       struct strbuf label = STRBUF_INIT;
+       struct commit_list *commits = NULL, **tail = &commits, *iter;
+       struct commit_list *tips = NULL, **tips_tail = &tips;
+       struct commit *commit;
+       struct oidmap commit2todo = OIDMAP_INIT;
+       struct string_entry *entry;
+       struct oidset interesting = OIDSET_INIT, child_seen = OIDSET_INIT,
+               shown = OIDSET_INIT;
+       struct label_state state = { OIDMAP_INIT, { NULL }, STRBUF_INIT };
+
+       int abbr = flags & TODO_LIST_ABBREVIATE_CMDS;
+       const char *cmd_pick = abbr ? "p" : "pick",
+               *cmd_label = abbr ? "l" : "label",
+               *cmd_reset = abbr ? "t" : "reset",
+               *cmd_merge = abbr ? "m" : "merge";
+
+       oidmap_init(&commit2todo, 0);
+       oidmap_init(&state.commit2label, 0);
+       hashmap_init(&state.labels, (hashmap_cmp_fn) labels_cmp, NULL, 0);
+       strbuf_init(&state.buf, 32);
+
+       if (revs->cmdline.nr && (revs->cmdline.rev[0].flags & BOTTOM)) {
+               struct object_id *oid = &revs->cmdline.rev[0].item->oid;
+               FLEX_ALLOC_STR(entry, string, "onto");
+               oidcpy(&entry->entry.oid, oid);
+               oidmap_put(&state.commit2label, entry);
+       }
+
+       /*
+        * First phase:
+        * - get onelines for all commits
+        * - gather all branch tips (i.e. 2nd or later parents of merges)
+        * - label all branch tips
+        */
+       while ((commit = get_revision(revs))) {
+               struct commit_list *to_merge;
+               int is_octopus;
+               const char *p1, *p2;
+               struct object_id *oid;
+
+               tail = &commit_list_insert(commit, tail)->next;
+               oidset_insert(&interesting, &commit->object.oid);
+
+               if ((commit->object.flags & PATCHSAME))
+                       continue;
+
+               strbuf_reset(&oneline);
+               pretty_print_commit(pp, commit, &oneline);
+
+               to_merge = commit->parents ? commit->parents->next : NULL;
+               if (!to_merge) {
+                       /* non-merge commit: easy case */
+                       strbuf_reset(&buf);
+                       if (!keep_empty && is_original_commit_empty(commit))
+                               strbuf_addf(&buf, "%c ", comment_line_char);
+                       strbuf_addf(&buf, "%s %s %s", cmd_pick,
+                                   oid_to_hex(&commit->object.oid),
+                                   oneline.buf);
+
+                       FLEX_ALLOC_STR(entry, string, buf.buf);
+                       oidcpy(&entry->entry.oid, &commit->object.oid);
+                       oidmap_put(&commit2todo, entry);
+
+                       continue;
+               }
+
+               is_octopus = to_merge && to_merge->next;
+
+               if (is_octopus)
+                       BUG("Octopus merges not yet supported");
+
+               /* Create a label */
+               strbuf_reset(&label);
+               if (skip_prefix(oneline.buf, "Merge ", &p1) &&
+                   (p1 = strchr(p1, '\'')) &&
+                   (p2 = strchr(++p1, '\'')))
+                       strbuf_add(&label, p1, p2 - p1);
+               else if (skip_prefix(oneline.buf, "Merge pull request ",
+                                    &p1) &&
+                        (p1 = strstr(p1, " from ")))
+                       strbuf_addstr(&label, p1 + strlen(" from "));
+               else
+                       strbuf_addbuf(&label, &oneline);
+
+               for (p1 = label.buf; *p1; p1++)
+                       if (isspace(*p1))
+                               *(char *)p1 = '-';
+
+               strbuf_reset(&buf);
+               strbuf_addf(&buf, "%s -C %s",
+                           cmd_merge, oid_to_hex(&commit->object.oid));
+
+               /* label the tip of merged branch */
+               oid = &to_merge->item->object.oid;
+               strbuf_addch(&buf, ' ');
+
+               if (!oidset_contains(&interesting, oid))
+                       strbuf_addstr(&buf, label_oid(oid, NULL, &state));
+               else {
+                       tips_tail = &commit_list_insert(to_merge->item,
+                                                       tips_tail)->next;
+
+                       strbuf_addstr(&buf, label_oid(oid, label.buf, &state));
+               }
+               strbuf_addf(&buf, " # %s", oneline.buf);
+
+               FLEX_ALLOC_STR(entry, string, buf.buf);
+               oidcpy(&entry->entry.oid, &commit->object.oid);
+               oidmap_put(&commit2todo, entry);
+       }
+
+       /*
+        * Second phase:
+        * - label branch points
+        * - add HEAD to the branch tips
+        */
+       for (iter = commits; iter; iter = iter->next) {
+               struct commit_list *parent = iter->item->parents;
+               for (; parent; parent = parent->next) {
+                       struct object_id *oid = &parent->item->object.oid;
+                       if (!oidset_contains(&interesting, oid))
+                               continue;
+                       if (!oidset_contains(&child_seen, oid))
+                               oidset_insert(&child_seen, oid);
+                       else
+                               label_oid(oid, "branch-point", &state);
+               }
+
+               /* Add HEAD as implict "tip of branch" */
+               if (!iter->next)
+                       tips_tail = &commit_list_insert(iter->item,
+                                                       tips_tail)->next;
+       }
+
+       /*
+        * Third phase: output the todo list. This is a bit tricky, as we
+        * want to avoid jumping back and forth between revisions. To
+        * accomplish that goal, we walk backwards from the branch tips,
+        * gathering commits not yet shown, reversing the list on the fly,
+        * then outputting that list (labeling revisions as needed).
+        */
+       fprintf(out, "%s onto\n", cmd_label);
+       for (iter = tips; iter; iter = iter->next) {
+               struct commit_list *list = NULL, *iter2;
+
+               commit = iter->item;
+               if (oidset_contains(&shown, &commit->object.oid))
+                       continue;
+               entry = oidmap_get(&state.commit2label, &commit->object.oid);
+
+               if (entry)
+                       fprintf(out, "\n# Branch %s\n", entry->string);
+               else
+                       fprintf(out, "\n");
+
+               while (oidset_contains(&interesting, &commit->object.oid) &&
+                      !oidset_contains(&shown, &commit->object.oid)) {
+                       commit_list_insert(commit, &list);
+                       if (!commit->parents) {
+                               commit = NULL;
+                               break;
+                       }
+                       commit = commit->parents->item;
+               }
+
+               if (!commit)
+                       fprintf(out, "%s onto\n", cmd_reset);
+               else {
+                       const char *to = NULL;
+
+                       entry = oidmap_get(&state.commit2label,
+                                          &commit->object.oid);
+                       if (entry)
+                               to = entry->string;
+                       else if (!rebase_cousins)
+                               to = label_oid(&commit->object.oid, NULL,
+                                              &state);
+
+                       if (!to || !strcmp(to, "onto"))
+                               fprintf(out, "%s onto\n", cmd_reset);
+                       else {
+                               strbuf_reset(&oneline);
+                               pretty_print_commit(pp, commit, &oneline);
+                               fprintf(out, "%s %s # %s\n",
+                                       cmd_reset, to, oneline.buf);
+                       }
+               }
+
+               for (iter2 = list; iter2; iter2 = iter2->next) {
+                       struct object_id *oid = &iter2->item->object.oid;
+                       entry = oidmap_get(&commit2todo, oid);
+                       /* only show if not already upstream */
+                       if (entry)
+                               fprintf(out, "%s\n", entry->string);
+                       entry = oidmap_get(&state.commit2label, oid);
+                       if (entry)
+                               fprintf(out, "%s %s\n",
+                                       cmd_label, entry->string);
+                       oidset_insert(&shown, oid);
+               }
+
+               free_commit_list(list);
+       }
+
+       free_commit_list(commits);
+       free_commit_list(tips);
+
+       strbuf_release(&label);
+       strbuf_release(&oneline);
+       strbuf_release(&buf);
+
+       oidmap_free(&commit2todo, 1);
+       oidmap_free(&state.commit2label, 1);
+       hashmap_free(&state.labels, 1);
+       strbuf_release(&state.buf);
+
+       return 0;
+}
+
 int sequencer_make_script(FILE *out, int argc, const char **argv,
                          unsigned flags)
 {
@@ -2997,11 +3697,16 @@ int sequencer_make_script(FILE *out, int argc, const char **argv,
        struct commit *commit;
        int keep_empty = flags & TODO_LIST_KEEP_EMPTY;
        const char *insn = flags & TODO_LIST_ABBREVIATE_CMDS ? "p" : "pick";
+       int recreate_merges = flags & TODO_LIST_RECREATE_MERGES;
 
        init_revisions(&revs, NULL);
        revs.verbose_header = 1;
-       revs.max_parents = 1;
-       revs.cherry_pick = 1;
+       if (recreate_merges)
+               revs.cherry_mark = 1;
+       else {
+               revs.max_parents = 1;
+               revs.cherry_pick = 1;
+       }
        revs.limited = 1;
        revs.reverse = 1;
        revs.right_only = 1;
@@ -3025,6 +3730,9 @@ int sequencer_make_script(FILE *out, int argc, const char **argv,
        if (prepare_revision_walk(&revs) < 0)
                return error(_("make_script: error preparing revisions"));
 
+       if (recreate_merges)
+               return make_script_with_merges(&pp, &revs, out, flags);
+
        while ((commit = get_revision(&revs))) {
                strbuf_reset(&buf);
                if (!keep_empty && is_original_commit_empty(commit))
@@ -3114,8 +3822,14 @@ int transform_todos(unsigned flags)
                                          short_commit_name(item->commit) :
                                          oid_to_hex(&item->commit->object.oid);
 
+                       if (item->command == TODO_MERGE)
+                               strbuf_addstr(&buf, " -C");
+                       else if (item->command == TODO_MERGE_AND_EDIT)
+                               strbuf_addstr(&buf, " -c");
+
                        strbuf_addf(&buf, " %s", oid);
                }
+
                /* add all the rest */
                if (!item->arg_len)
                        strbuf_addch(&buf, '\n');
@@ -3391,7 +4105,7 @@ int rearrange_squash(void)
                struct subject2item_entry *entry;
 
                next[i] = tail[i] = -1;
-               if (item->command >= TODO_EXEC) {
+               if (!item->commit || item->command == TODO_DROP) {
                        subjects[i] = NULL;
                        continue;
                }