Merge branch 'pk/rebase-in-c-4-opts'
authorJunio C Hamano <gitster@pobox.com>
Fri, 2 Nov 2018 02:04:55 +0000 (11:04 +0900)
committerJunio C Hamano <gitster@pobox.com>
Fri, 2 Nov 2018 02:04:55 +0000 (11:04 +0900)
Rewrite "git rebase" in C.

* pk/rebase-in-c-4-opts:
builtin rebase: support --root
builtin rebase: add support for custom merge strategies
builtin rebase: support `fork-point` option
merge-base --fork-point: extract libified function
builtin rebase: support --rebase-merges[=[no-]rebase-cousins]
builtin rebase: support `--allow-empty-message` option
builtin rebase: support `--exec`
builtin rebase: support `--autostash` option
builtin rebase: support `-C` and `--whitespace=<type>`
builtin rebase: support `--gpg-sign` option
builtin rebase: support `--autosquash`
builtin rebase: support `keep-empty` option
builtin rebase: support `ignore-date` option
builtin rebase: support `ignore-whitespace` option
builtin rebase: support --committer-date-is-author-date
builtin rebase: support --rerere-autoupdate
builtin rebase: support --signoff
builtin rebase: allow selecting the rebase "backend"

1  2 
builtin/merge-base.c
builtin/rebase.c
commit.c
commit.h
diff --combined builtin/merge-base.c
index 1c920990701381452da910e4cee66be5e6fde5a0,790ceaeed68fae3f8696d0d59fb97aa67f88dbce..e3f8da13b69b8dbe6898bf71ee2b5df206179bd1
@@@ -7,7 -7,6 +7,7 @@@
  #include "revision.h"
  #include "parse-options.h"
  #include "repository.h"
 +#include "commit-reach.h"
  
  static int show_merge_base(struct commit **rev, int rev_nr, int show_all)
  {
@@@ -111,54 -110,12 +111,12 @@@ static int handle_is_ancestor(int argc
                return 1;
  }
  
- struct rev_collect {
-       struct commit **commit;
-       int nr;
-       int alloc;
-       unsigned int initial : 1;
- };
- static void add_one_commit(struct object_id *oid, struct rev_collect *revs)
- {
-       struct commit *commit;
-       if (is_null_oid(oid))
-               return;
-       commit = lookup_commit(the_repository, oid);
-       if (!commit ||
-           (commit->object.flags & TMP_MARK) ||
-           parse_commit(commit))
-               return;
-       ALLOC_GROW(revs->commit, revs->nr + 1, revs->alloc);
-       revs->commit[revs->nr++] = commit;
-       commit->object.flags |= TMP_MARK;
- }
- static int collect_one_reflog_ent(struct object_id *ooid, struct object_id *noid,
-                                 const char *ident, timestamp_t timestamp,
-                                 int tz, const char *message, void *cbdata)
- {
-       struct rev_collect *revs = cbdata;
-       if (revs->initial) {
-               revs->initial = 0;
-               add_one_commit(ooid, revs);
-       }
-       add_one_commit(noid, revs);
-       return 0;
- }
  static int handle_fork_point(int argc, const char **argv)
  {
        struct object_id oid;
        char *refname;
+       struct commit *derived, *fork_point;
        const char *commitname;
-       struct rev_collect revs;
-       struct commit *derived;
-       struct commit_list *bases;
-       int i, ret = 0;
  
        switch (dwim_ref(argv[0], strlen(argv[0]), &oid, &refname)) {
        case 0:
                die("Not a valid object name: '%s'", commitname);
  
        derived = lookup_commit_reference(the_repository, &oid);
-       memset(&revs, 0, sizeof(revs));
-       revs.initial = 1;
-       for_each_reflog_ent(refname, collect_one_reflog_ent, &revs);
  
-       if (!revs.nr && !get_oid(refname, &oid))
-               add_one_commit(&oid, &revs);
+       fork_point = get_fork_point(refname, derived);
  
-       for (i = 0; i < revs.nr; i++)
-               revs.commit[i]->object.flags &= ~TMP_MARK;
-       bases = get_merge_bases_many_dirty(derived, revs.nr, revs.commit);
-       /*
-        * There should be one and only one merge base, when we found
-        * a common ancestor among reflog entries.
-        */
-       if (!bases || bases->next) {
-               ret = 1;
-               goto cleanup_return;
-       }
-       /* And the found one must be one of the reflog entries */
-       for (i = 0; i < revs.nr; i++)
-               if (&bases->item->object == &revs.commit[i]->object)
-                       break; /* found */
-       if (revs.nr <= i) {
-               ret = 1; /* not found */
-               goto cleanup_return;
-       }
-       printf("%s\n", oid_to_hex(&bases->item->object.oid));
+       if (!fork_point)
+               return 1;
  
- cleanup_return:
-       free_commit_list(bases);
-       return ret;
+       printf("%s\n", oid_to_hex(&fork_point->object.oid));
+       return 0;
  }
  
  int cmd_merge_base(int argc, const char **argv, const char *prefix)
diff --combined builtin/rebase.c
index 13084082776d6a72da0d1fe44cd2ad8163e07cb4,b2cf779f1b42a5623d7d376b4fcc0e9bcea28e97..4d30ca7b878762a6675750224b9fba886bd3fd33
@@@ -21,7 -21,6 +21,7 @@@
  #include "diff.h"
  #include "wt-status.h"
  #include "revision.h"
 +#include "commit-reach.h"
  #include "rerere.h"
  
  static char const * const builtin_rebase_usage[] = {
@@@ -64,12 -63,6 +64,6 @@@ static int use_builtin_rebase(void
        return ret;
  }
  
- static int apply_autostash(void)
- {
-       warning("TODO");
-       return 0;
- }
  struct rebase_options {
        enum rebase_type type;
        const char *state_dir;
@@@ -83,6 -76,7 +77,7 @@@
        const char *revisions;
        const char *switch_to;
        int root;
+       struct object_id *squash_onto;
        struct commit *restrict_revision;
        int dont_finish_rebase;
        enum {
        } flags;
        struct strbuf git_am_opt;
        const char *action;
+       int signoff;
+       int allow_rerere_autoupdate;
+       int keep_empty;
+       int autosquash;
+       char *gpg_sign_opt;
+       int autostash;
+       char *cmd;
+       int allow_empty_message;
+       int rebase_merges, rebase_cousins;
+       char *strategy, *strategy_opts;
  };
  
  static int is_interactive(struct rebase_options *opts)
                opts->type == REBASE_PRESERVE_MERGES;
  }
  
+ static void imply_interactive(struct rebase_options *opts, const char *option)
+ {
+       switch (opts->type) {
+       case REBASE_AM:
+               die(_("%s requires an interactive rebase"), option);
+               break;
+       case REBASE_INTERACTIVE:
+       case REBASE_PRESERVE_MERGES:
+               break;
+       case REBASE_MERGE:
+               /* we silently *upgrade* --merge to --interactive if needed */
+       default:
+               opts->type = REBASE_INTERACTIVE; /* implied */
+               break;
+       }
+ }
  /* Returns the filename prefixed by the state_dir */
  static const char *state_dir_path(const char *filename, struct rebase_options *opts)
  {
@@@ -169,18 -190,106 +191,106 @@@ static int read_basic_state(struct reba
        if (file_exists(state_dir_path("verbose", opts)))
                opts->flags |= REBASE_VERBOSE;
  
+       if (file_exists(state_dir_path("signoff", opts))) {
+               opts->signoff = 1;
+               opts->flags |= REBASE_FORCE;
+       }
+       if (file_exists(state_dir_path("allow_rerere_autoupdate", opts))) {
+               strbuf_reset(&buf);
+               if (read_one(state_dir_path("allow_rerere_autoupdate", opts),
+                           &buf))
+                       return -1;
+               if (!strcmp(buf.buf, "--rerere-autoupdate"))
+                       opts->allow_rerere_autoupdate = 1;
+               else if (!strcmp(buf.buf, "--no-rerere-autoupdate"))
+                       opts->allow_rerere_autoupdate = 0;
+               else
+                       warning(_("ignoring invalid allow_rerere_autoupdate: "
+                                 "'%s'"), buf.buf);
+       } else
+               opts->allow_rerere_autoupdate = -1;
+       if (file_exists(state_dir_path("gpg_sign_opt", opts))) {
+               strbuf_reset(&buf);
+               if (read_one(state_dir_path("gpg_sign_opt", opts),
+                           &buf))
+                       return -1;
+               free(opts->gpg_sign_opt);
+               opts->gpg_sign_opt = xstrdup(buf.buf);
+       }
+       if (file_exists(state_dir_path("strategy", opts))) {
+               strbuf_reset(&buf);
+               if (read_one(state_dir_path("strategy", opts), &buf))
+                       return -1;
+               free(opts->strategy);
+               opts->strategy = xstrdup(buf.buf);
+       }
+       if (file_exists(state_dir_path("strategy_opts", opts))) {
+               strbuf_reset(&buf);
+               if (read_one(state_dir_path("strategy_opts", opts), &buf))
+                       return -1;
+               free(opts->strategy_opts);
+               opts->strategy_opts = xstrdup(buf.buf);
+       }
        strbuf_release(&buf);
  
        return 0;
  }
  
+ static int apply_autostash(struct rebase_options *opts)
+ {
+       const char *path = state_dir_path("autostash", opts);
+       struct strbuf autostash = STRBUF_INIT;
+       struct child_process stash_apply = CHILD_PROCESS_INIT;
+       if (!file_exists(path))
+               return 0;
+       if (read_one(state_dir_path("autostash", opts), &autostash))
+               return error(_("Could not read '%s'"), path);
+       argv_array_pushl(&stash_apply.args,
+                        "stash", "apply", autostash.buf, NULL);
+       stash_apply.git_cmd = 1;
+       stash_apply.no_stderr = stash_apply.no_stdout =
+               stash_apply.no_stdin = 1;
+       if (!run_command(&stash_apply))
+               printf(_("Applied autostash.\n"));
+       else {
+               struct argv_array args = ARGV_ARRAY_INIT;
+               int res = 0;
+               argv_array_pushl(&args,
+                                "stash", "store", "-m", "autostash", "-q",
+                                autostash.buf, NULL);
+               if (run_command_v_opt(args.argv, RUN_GIT_CMD))
+                       res = error(_("Cannot store %s"), autostash.buf);
+               argv_array_clear(&args);
+               strbuf_release(&autostash);
+               if (res)
+                       return res;
+               fprintf(stderr,
+                       _("Applying autostash resulted in conflicts.\n"
+                         "Your changes are safe in the stash.\n"
+                         "You can run \"git stash pop\" or \"git stash drop\" "
+                         "at any time.\n"));
+       }
+       strbuf_release(&autostash);
+       return 0;
+ }
  static int finish_rebase(struct rebase_options *opts)
  {
        struct strbuf dir = STRBUF_INIT;
        const char *argv_gc_auto[] = { "gc", "--auto", NULL };
  
        delete_ref(NULL, "REBASE_HEAD", NULL, REF_NO_DEREF);
-       apply_autostash();
+       apply_autostash(opts);
        close_all_packs(the_repository->objects);
        /*
         * We ignore errors in 'gc --auto', since the
@@@ -250,6 -359,26 +360,26 @@@ static int run_specific_rebase(struct r
        if (opts->switch_to)
                add_var(&script_snippet, "switch_to", opts->switch_to);
        add_var(&script_snippet, "action", opts->action ? opts->action : "");
+       add_var(&script_snippet, "signoff", opts->signoff ? "--signoff" : "");
+       add_var(&script_snippet, "allow_rerere_autoupdate",
+               opts->allow_rerere_autoupdate < 0 ? "" :
+               opts->allow_rerere_autoupdate ?
+               "--rerere-autoupdate" : "--no-rerere-autoupdate");
+       add_var(&script_snippet, "keep_empty", opts->keep_empty ? "yes" : "");
+       add_var(&script_snippet, "autosquash", opts->autosquash ? "t" : "");
+       add_var(&script_snippet, "gpg_sign_opt", opts->gpg_sign_opt);
+       add_var(&script_snippet, "cmd", opts->cmd);
+       add_var(&script_snippet, "allow_empty_message",
+               opts->allow_empty_message ?  "--allow-empty-message" : "");
+       add_var(&script_snippet, "rebase_merges",
+               opts->rebase_merges ? "t" : "");
+       add_var(&script_snippet, "rebase_cousins",
+               opts->rebase_cousins ? "t" : "");
+       add_var(&script_snippet, "strategy", opts->strategy);
+       add_var(&script_snippet, "strategy_opts", opts->strategy_opts);
+       add_var(&script_snippet, "rebase_root", opts->root ? "t" : "");
+       add_var(&script_snippet, "squash_onto",
+               opts->squash_onto ? oid_to_hex(opts->squash_onto) : "");
  
        switch (opts->type) {
        case REBASE_AM:
        } else if (status == 2) {
                struct strbuf dir = STRBUF_INIT;
  
-               apply_autostash();
+               apply_autostash(opts);
                strbuf_addstr(&dir, opts->state_dir);
                remove_dir_recursively(&dir, 0);
                strbuf_release(&dir);
@@@ -410,6 -539,23 +540,23 @@@ static int rebase_config(const char *va
                return 0;
        }
  
+       if (!strcmp(var, "rebase.autosquash")) {
+               opts->autosquash = git_config_bool(var, value);
+               return 0;
+       }
+       if (!strcmp(var, "commit.gpgsign")) {
+               free(opts->gpg_sign_opt);
+               opts->gpg_sign_opt = git_config_bool(var, value) ?
+                       xstrdup("-S") : NULL;
+               return 0;
+       }
+       if (!strcmp(var, "rebase.autostash")) {
+               opts->autostash = git_config_bool(var, value);
+               return 0;
+       }
        return git_default_config(var, value, data);
  }
  
@@@ -453,12 -599,37 +600,37 @@@ static int can_fast_forward(struct comm
        return res && is_linear_history(onto, head);
  }
  
+ /* -i followed by -m is still -i */
+ static int parse_opt_merge(const struct option *opt, const char *arg, int unset)
+ {
+       struct rebase_options *opts = opt->value;
+       if (!is_interactive(opts))
+               opts->type = REBASE_MERGE;
+       return 0;
+ }
+ /* -i followed by -p is still explicitly interactive, but -p alone is not */
+ static int parse_opt_interactive(const struct option *opt, const char *arg,
+                                int unset)
+ {
+       struct rebase_options *opts = opt->value;
+       opts->type = REBASE_INTERACTIVE;
+       opts->flags |= REBASE_INTERACTIVE_EXPLICIT;
+       return 0;
+ }
  int cmd_rebase(int argc, const char **argv, const char *prefix)
  {
        struct rebase_options options = {
                .type = REBASE_UNSPECIFIED,
                .flags = REBASE_NO_QUIET,
                .git_am_opt = STRBUF_INIT,
+               .allow_rerere_autoupdate  = -1,
+               .allow_empty_message = 1,
        };
        const char *branch_name;
        int ret, flags, total_argc, in_progress = 0;
                ACTION_EDIT_TODO,
                ACTION_SHOW_CURRENT_PATCH,
        } action = NO_ACTION;
+       int committer_date_is_author_date = 0;
+       int ignore_date = 0;
+       int ignore_whitespace = 0;
+       const char *gpg_sign = NULL;
+       int opt_c = -1;
+       struct string_list whitespace = STRING_LIST_INIT_NODUP;
+       struct string_list exec = STRING_LIST_INIT_NODUP;
+       const char *rebase_merges = NULL;
+       int fork_point = -1;
+       struct string_list strategy_options = STRING_LIST_INIT_NODUP;
+       struct object_id squash_onto;
+       char *squash_onto_name = NULL;
        struct option builtin_rebase_options[] = {
                OPT_STRING(0, "onto", &options.onto_name,
                           N_("revision"),
                {OPTION_NEGBIT, 'n', "no-stat", &options.flags, NULL,
                        N_("do not show diffstat of what changed upstream"),
                        PARSE_OPT_NOARG, NULL, REBASE_DIFFSTAT },
+               OPT_BOOL(0, "ignore-whitespace", &ignore_whitespace,
+                        N_("passed to 'git apply'")),
+               OPT_BOOL(0, "signoff", &options.signoff,
+                        N_("add a Signed-off-by: line to each commit")),
+               OPT_BOOL(0, "committer-date-is-author-date",
+                        &committer_date_is_author_date,
+                        N_("passed to 'git am'")),
+               OPT_BOOL(0, "ignore-date", &ignore_date,
+                        N_("passed to 'git am'")),
                OPT_BIT('f', "force-rebase", &options.flags,
                        N_("cherry-pick all commits, even if unchanged"),
                        REBASE_FORCE),
                OPT_CMDMODE(0, "show-current-patch", &action,
                            N_("show the patch file being applied or merged"),
                            ACTION_SHOW_CURRENT_PATCH),
+               { OPTION_CALLBACK, 'm', "merge", &options, NULL,
+                       N_("use merging strategies to rebase"),
+                       PARSE_OPT_NOARG | PARSE_OPT_NONEG,
+                       parse_opt_merge },
+               { OPTION_CALLBACK, 'i', "interactive", &options, NULL,
+                       N_("let the user edit the list of commits to rebase"),
+                       PARSE_OPT_NOARG | PARSE_OPT_NONEG,
+                       parse_opt_interactive },
+               OPT_SET_INT('p', "preserve-merges", &options.type,
+                           N_("try to recreate merges instead of ignoring "
+                              "them"), REBASE_PRESERVE_MERGES),
+               OPT_BOOL(0, "rerere-autoupdate",
+                        &options.allow_rerere_autoupdate,
+                        N_("allow rerere to update index  with resolved "
+                           "conflict")),
+               OPT_BOOL('k', "keep-empty", &options.keep_empty,
+                        N_("preserve empty commits during rebase")),
+               OPT_BOOL(0, "autosquash", &options.autosquash,
+                        N_("move commits that begin with "
+                           "squash!/fixup! under -i")),
+               { OPTION_STRING, 'S', "gpg-sign", &gpg_sign, N_("key-id"),
+                       N_("GPG-sign commits"),
+                       PARSE_OPT_OPTARG, NULL, (intptr_t) "" },
+               OPT_STRING_LIST(0, "whitespace", &whitespace,
+                               N_("whitespace"), N_("passed to 'git apply'")),
+               OPT_SET_INT('C', NULL, &opt_c, N_("passed to 'git apply'"),
+                           REBASE_AM),
+               OPT_BOOL(0, "autostash", &options.autostash,
+                        N_("automatically stash/stash pop before and after")),
+               OPT_STRING_LIST('x', "exec", &exec, N_("exec"),
+                               N_("add exec lines after each commit of the "
+                                  "editable list")),
+               OPT_BOOL(0, "allow-empty-message",
+                        &options.allow_empty_message,
+                        N_("allow rebasing commits with empty messages")),
+               {OPTION_STRING, 'r', "rebase-merges", &rebase_merges,
+                       N_("mode"),
+                       N_("try to rebase merges instead of skipping them"),
+                       PARSE_OPT_OPTARG, NULL, (intptr_t)""},
+               OPT_BOOL(0, "fork-point", &fork_point,
+                        N_("use 'merge-base --fork-point' to refine upstream")),
+               OPT_STRING('s', "strategy", &options.strategy,
+                          N_("strategy"), N_("use the given merge strategy")),
+               OPT_STRING_LIST('X', "strategy-option", &strategy_options,
+                               N_("option"),
+                               N_("pass the argument through to the merge "
+                                  "strategy")),
+               OPT_BOOL(0, "root", &options.root,
+                        N_("rebase all reachable commits up to the root(s)")),
                OPT_END(),
        };
  
        if (!(options.flags & REBASE_NO_QUIET))
                strbuf_addstr(&options.git_am_opt, " -q");
  
+       if (committer_date_is_author_date) {
+               strbuf_addstr(&options.git_am_opt,
+                             " --committer-date-is-author-date");
+               options.flags |= REBASE_FORCE;
+       }
+       if (ignore_whitespace)
+               strbuf_addstr(&options.git_am_opt, " --ignore-whitespace");
+       if (ignore_date) {
+               strbuf_addstr(&options.git_am_opt, " --ignore-date");
+               options.flags |= REBASE_FORCE;
+       }
+       if (options.keep_empty)
+               imply_interactive(&options, "--keep-empty");
+       if (gpg_sign) {
+               free(options.gpg_sign_opt);
+               options.gpg_sign_opt = xstrfmt("-S%s", gpg_sign);
+       }
+       if (opt_c >= 0)
+               strbuf_addf(&options.git_am_opt, " -C%d", opt_c);
+       if (whitespace.nr) {
+               int i;
+               for (i = 0; i < whitespace.nr; i++) {
+                       const char *item = whitespace.items[i].string;
+                       strbuf_addf(&options.git_am_opt, " --whitespace=%s",
+                                   item);
+                       if ((!strcmp(item, "fix")) || (!strcmp(item, "strip")))
+                               options.flags |= REBASE_FORCE;
+               }
+       }
+       if (exec.nr) {
+               int i;
+               imply_interactive(&options, "--exec");
+               strbuf_reset(&buf);
+               for (i = 0; i < exec.nr; i++)
+                       strbuf_addf(&buf, "exec %s\n", exec.items[i].string);
+               options.cmd = xstrdup(buf.buf);
+       }
+       if (rebase_merges) {
+               if (!*rebase_merges)
+                       ; /* default mode; do nothing */
+               else if (!strcmp("rebase-cousins", rebase_merges))
+                       options.rebase_cousins = 1;
+               else if (strcmp("no-rebase-cousins", rebase_merges))
+                       die(_("Unknown mode: %s"), rebase_merges);
+               options.rebase_merges = 1;
+               imply_interactive(&options, "--rebase-merges");
+       }
+       if (strategy_options.nr) {
+               int i;
+               if (!options.strategy)
+                       options.strategy = "recursive";
+               strbuf_reset(&buf);
+               for (i = 0; i < strategy_options.nr; i++)
+                       strbuf_addf(&buf, " --%s",
+                                   strategy_options.items[i].string);
+               options.strategy_opts = xstrdup(buf.buf);
+       }
+       if (options.strategy) {
+               options.strategy = xstrdup(options.strategy);
+               switch (options.type) {
+               case REBASE_AM:
+                       die(_("--strategy requires --merge or --interactive"));
+               case REBASE_MERGE:
+               case REBASE_INTERACTIVE:
+               case REBASE_PRESERVE_MERGES:
+                       /* compatible */
+                       break;
+               case REBASE_UNSPECIFIED:
+                       options.type = REBASE_MERGE;
+                       break;
+               default:
+                       BUG("unhandled rebase type (%d)", options.type);
+               }
+       }
+       if (options.root && !options.onto_name)
+               imply_interactive(&options, "--root without --onto");
        switch (options.type) {
        case REBASE_MERGE:
        case REBASE_INTERACTIVE:
                break;
        }
  
+       if (options.signoff) {
+               if (options.type == REBASE_PRESERVE_MERGES)
+                       die("cannot combine '--signoff' with "
+                           "'--preserve-merges'");
+               strbuf_addstr(&options.git_am_opt, " --signoff");
+               options.flags |= REBASE_FORCE;
+       }
        if (!options.root) {
                if (argc < 1)
                        die("TODO: handle @{upstream}");
                if (!options.upstream)
                        die(_("invalid upstream '%s'"), options.upstream_name);
                options.upstream_arg = options.upstream_name;
-       } else
-               die("TODO: upstream for --root");
+       } else {
+               if (!options.onto_name) {
+                       if (commit_tree("", 0, the_hash_algo->empty_tree, NULL,
+                                       &squash_onto, NULL, NULL) < 0)
+                               die(_("Could not create new root commit"));
+                       options.squash_onto = &squash_onto;
+                       options.onto_name = squash_onto_name =
+                               xstrdup(oid_to_hex(&squash_onto));
+               }
+               options.upstream_name = NULL;
+               options.upstream = NULL;
+               if (argc > 1)
+                       usage_with_options(builtin_rebase_usage,
+                                          builtin_rebase_options);
+               options.upstream_arg = "--root";
+       }
  
        /* Make sure the branch to rebase onto is valid. */
        if (!options.onto_name)
        } else
                BUG("unexpected number of arguments left to parse");
  
+       if (fork_point > 0) {
+               struct commit *head =
+                       lookup_commit_reference(the_repository,
+                                               &options.orig_head);
+               options.restrict_revision =
+                       get_fork_point(options.upstream_name, head);
+       }
        if (read_index(the_repository->index) < 0)
                die(_("could not read index"));
  
+       if (options.autostash) {
+               struct lock_file lock_file = LOCK_INIT;
+               int fd;
+               fd = hold_locked_index(&lock_file, 0);
+               refresh_cache(REFRESH_QUIET);
+               if (0 <= fd)
+                       update_index_if_able(&the_index, &lock_file);
+               rollback_lock_file(&lock_file);
+               if (has_unstaged_changes(0) || has_uncommitted_changes(0)) {
+                       const char *autostash =
+                               state_dir_path("autostash", &options);
+                       struct child_process stash = CHILD_PROCESS_INIT;
+                       struct object_id oid;
+                       struct commit *head =
+                               lookup_commit_reference(the_repository,
+                                                       &options.orig_head);
+                       argv_array_pushl(&stash.args,
+                                        "stash", "create", "autostash", NULL);
+                       stash.git_cmd = 1;
+                       stash.no_stdin = 1;
+                       strbuf_reset(&buf);
+                       if (capture_command(&stash, &buf, GIT_MAX_HEXSZ))
+                               die(_("Cannot autostash"));
+                       strbuf_trim_trailing_newline(&buf);
+                       if (get_oid(buf.buf, &oid))
+                               die(_("Unexpected stash response: '%s'"),
+                                   buf.buf);
+                       strbuf_reset(&buf);
+                       strbuf_add_unique_abbrev(&buf, &oid, DEFAULT_ABBREV);
+                       if (safe_create_leading_directories_const(autostash))
+                               die(_("Could not create directory for '%s'"),
+                                   options.state_dir);
+                       write_file(autostash, "%s", buf.buf);
+                       printf(_("Created autostash: %s\n"), buf.buf);
+                       if (reset_head(&head->object.oid, "reset --hard",
+                                      NULL, 0) < 0)
+                               die(_("could not reset --hard"));
+                       printf(_("HEAD is now at %s"),
+                              find_unique_abbrev(&head->object.oid,
+                                                 DEFAULT_ABBREV));
+                       strbuf_reset(&buf);
+                       pp_commit_easy(CMIT_FMT_ONELINE, head, &buf);
+                       if (buf.len > 0)
+                               printf(" %s", buf.buf);
+                       putchar('\n');
+                       if (discard_index(the_repository->index) < 0 ||
+                               read_index(the_repository->index) < 0)
+                               die(_("could not read index"));
+               }
+       }
        if (require_clean_work_tree("rebase",
                                    _("Please commit or stash them."), 1, 1)) {
                ret = 1;
         */
        if (can_fast_forward(options.onto, &options.orig_head, &merge_base) &&
            !is_interactive(&options) && !options.restrict_revision &&
+           options.upstream &&
            !oidcmp(&options.upstream->object.oid, &options.onto->object.oid)) {
                int flag;
  
                diff_flush(&opts);
        }
  
+       if (is_interactive(&options))
+               goto run_rebase;
        /* Detach HEAD and reset the tree */
        if (options.flags & REBASE_NO_QUIET)
                printf(_("First, rewinding head to replay your work on top of "
@@@ -910,5 -1336,8 +1337,8 @@@ run_rebase
  cleanup:
        strbuf_release(&revisions);
        free(options.head_name);
+       free(options.gpg_sign_opt);
+       free(options.cmd);
+       free(squash_onto_name);
        return ret;
  }
diff --combined commit.c
index dc8a39d52a1c31f979068a34bbdeeca14f3a7547,a3fc77a4eb592b64e295ffee9a904c8216415c55..d566d7e45c17cfa53493f228dbe46f2f92713ac9
+++ b/commit.c
@@@ -17,6 -17,7 +17,8 @@@
  #include "sha1-lookup.h"
  #include "wt-status.h"
  #include "advice.h"
+ #include "refs.h"
++#include "commit-reach.h"
  
  static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);
  
@@@ -46,7 -47,7 +48,7 @@@ struct commit *lookup_commit_or_die(con
        struct commit *c = lookup_commit_reference(the_repository, oid);
        if (!c)
                die(_("could not parse %s"), ref_name);
 -      if (oidcmp(oid, &c->object.oid)) {
 +      if (!oideq(oid, &c->object.oid)) {
                warning(_("%s %s is not a commit!"),
                        ref_name, oid_to_hex(oid));
        }
@@@ -209,7 -210,7 +211,7 @@@ static int read_graft_file(struct repos
        return 0;
  }
  
 -static void prepare_commit_graft(struct repository *r)
 +void prepare_commit_graft(struct repository *r)
  {
        char *graft_file;
  
@@@ -656,7 -657,7 +658,7 @@@ struct commit *pop_commit(struct commit
  define_commit_slab(indegree_slab, int);
  
  /* record author-date for each commit object */
 -define_commit_slab(author_date_slab, unsigned long);
 +define_commit_slab(author_date_slab, timestamp_t);
  
  static void record_author_date(struct author_date_slab *author_date,
                               struct commit *commit)
@@@ -843,6 -844,444 +845,86 @@@ void sort_in_topological_order(struct c
                clear_author_date_slab(&author_date);
  }
  
 -/* merge-base stuff */
 -
 -/* Remember to update object flag allocation in object.h */
 -#define PARENT1               (1u<<16)
 -#define PARENT2               (1u<<17)
 -#define STALE         (1u<<18)
 -#define RESULT                (1u<<19)
 -
 -static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
 -
 -static int queue_has_nonstale(struct prio_queue *queue)
 -{
 -      int i;
 -      for (i = 0; i < queue->nr; i++) {
 -              struct commit *commit = queue->array[i].data;
 -              if (!(commit->object.flags & STALE))
 -                      return 1;
 -      }
 -      return 0;
 -}
 -
 -/* all input commits in one and twos[] must have been parsed! */
 -static struct commit_list *paint_down_to_common(struct commit *one, int n,
 -                                              struct commit **twos,
 -                                              int min_generation)
 -{
 -      struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
 -      struct commit_list *result = NULL;
 -      int i;
 -      uint32_t last_gen = GENERATION_NUMBER_INFINITY;
 -
 -      one->object.flags |= PARENT1;
 -      if (!n) {
 -              commit_list_append(one, &result);
 -              return result;
 -      }
 -      prio_queue_put(&queue, one);
 -
 -      for (i = 0; i < n; i++) {
 -              twos[i]->object.flags |= PARENT2;
 -              prio_queue_put(&queue, twos[i]);
 -      }
 -
 -      while (queue_has_nonstale(&queue)) {
 -              struct commit *commit = prio_queue_get(&queue);
 -              struct commit_list *parents;
 -              int flags;
 -
 -              if (commit->generation > last_gen)
 -                      BUG("bad generation skip %8x > %8x at %s",
 -                          commit->generation, last_gen,
 -                          oid_to_hex(&commit->object.oid));
 -              last_gen = commit->generation;
 -
 -              if (commit->generation < min_generation)
 -                      break;
 -
 -              flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
 -              if (flags == (PARENT1 | PARENT2)) {
 -                      if (!(commit->object.flags & RESULT)) {
 -                              commit->object.flags |= RESULT;
 -                              commit_list_insert_by_date(commit, &result);
 -                      }
 -                      /* Mark parents of a found merge stale */
 -                      flags |= STALE;
 -              }
 -              parents = commit->parents;
 -              while (parents) {
 -                      struct commit *p = parents->item;
 -                      parents = parents->next;
 -                      if ((p->object.flags & flags) == flags)
 -                              continue;
 -                      if (parse_commit(p))
 -                              return NULL;
 -                      p->object.flags |= flags;
 -                      prio_queue_put(&queue, p);
 -              }
 -      }
 -
 -      clear_prio_queue(&queue);
 -      return result;
 -}
 -
 -static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
 -{
 -      struct commit_list *list = NULL;
 -      struct commit_list *result = NULL;
 -      int i;
 -
 -      for (i = 0; i < n; i++) {
 -              if (one == twos[i])
 -                      /*
 -                       * We do not mark this even with RESULT so we do not
 -                       * have to clean it up.
 -                       */
 -                      return commit_list_insert(one, &result);
 -      }
 -
 -      if (parse_commit(one))
 -              return NULL;
 -      for (i = 0; i < n; i++) {
 -              if (parse_commit(twos[i]))
 -                      return NULL;
 -      }
 -
 -      list = paint_down_to_common(one, n, twos, 0);
 -
 -      while (list) {
 -              struct commit *commit = pop_commit(&list);
 -              if (!(commit->object.flags & STALE))
 -                      commit_list_insert_by_date(commit, &result);
 -      }
 -      return result;
 -}
 -
+ struct rev_collect {
+       struct commit **commit;
+       int nr;
+       int alloc;
+       unsigned int initial : 1;
+ };
+ static void add_one_commit(struct object_id *oid, struct rev_collect *revs)
+ {
+       struct commit *commit;
+       if (is_null_oid(oid))
+               return;
+       commit = lookup_commit(the_repository, oid);
+       if (!commit ||
+           (commit->object.flags & TMP_MARK) ||
+           parse_commit(commit))
+               return;
+       ALLOC_GROW(revs->commit, revs->nr + 1, revs->alloc);
+       revs->commit[revs->nr++] = commit;
+       commit->object.flags |= TMP_MARK;
+ }
+ static int collect_one_reflog_ent(struct object_id *ooid, struct object_id *noid,
+                                 const char *ident, timestamp_t timestamp,
+                                 int tz, const char *message, void *cbdata)
+ {
+       struct rev_collect *revs = cbdata;
+       if (revs->initial) {
+               revs->initial = 0;
+               add_one_commit(ooid, revs);
+       }
+       add_one_commit(noid, revs);
+       return 0;
+ }
+ struct commit *get_fork_point(const char *refname, struct commit *commit)
+ {
+       struct object_id oid;
+       struct rev_collect revs;
+       struct commit_list *bases;
+       int i;
+       struct commit *ret = NULL;
+       memset(&revs, 0, sizeof(revs));
+       revs.initial = 1;
+       for_each_reflog_ent(refname, collect_one_reflog_ent, &revs);
+       if (!revs.nr && !get_oid(refname, &oid))
+               add_one_commit(&oid, &revs);
+       for (i = 0; i < revs.nr; i++)
+               revs.commit[i]->object.flags &= ~TMP_MARK;
+       bases = get_merge_bases_many(commit, revs.nr, revs.commit);
+       /*
+        * There should be one and only one merge base, when we found
+        * a common ancestor among reflog entries.
+        */
+       if (!bases || bases->next)
+               goto cleanup_return;
+       /* And the found one must be one of the reflog entries */
+       for (i = 0; i < revs.nr; i++)
+               if (&bases->item->object == &revs.commit[i]->object)
+                       break; /* found */
+       if (revs.nr <= i)
+               goto cleanup_return;
+       ret = bases->item;
+ cleanup_return:
+       free_commit_list(bases);
+       return ret;
+ }
 -struct commit_list *get_octopus_merge_bases(struct commit_list *in)
 -{
 -      struct commit_list *i, *j, *k, *ret = NULL;
 -
 -      if (!in)
 -              return ret;
 -
 -      commit_list_insert(in->item, &ret);
 -
 -      for (i = in->next; i; i = i->next) {
 -              struct commit_list *new_commits = NULL, *end = NULL;
 -
 -              for (j = ret; j; j = j->next) {
 -                      struct commit_list *bases;
 -                      bases = get_merge_bases(i->item, j->item);
 -                      if (!new_commits)
 -                              new_commits = bases;
 -                      else
 -                              end->next = bases;
 -                      for (k = bases; k; k = k->next)
 -                              end = k;
 -              }
 -              ret = new_commits;
 -      }
 -      return ret;
 -}
 -
 -static int remove_redundant(struct commit **array, int cnt)
 -{
 -      /*
 -       * Some commit in the array may be an ancestor of
 -       * another commit.  Move such commit to the end of
 -       * the array, and return the number of commits that
 -       * are independent from each other.
 -       */
 -      struct commit **work;
 -      unsigned char *redundant;
 -      int *filled_index;
 -      int i, j, filled;
 -
 -      work = xcalloc(cnt, sizeof(*work));
 -      redundant = xcalloc(cnt, 1);
 -      ALLOC_ARRAY(filled_index, cnt - 1);
 -
 -      for (i = 0; i < cnt; i++)
 -              parse_commit(array[i]);
 -      for (i = 0; i < cnt; i++) {
 -              struct commit_list *common;
 -              uint32_t min_generation = array[i]->generation;
 -
 -              if (redundant[i])
 -                      continue;
 -              for (j = filled = 0; j < cnt; j++) {
 -                      if (i == j || redundant[j])
 -                              continue;
 -                      filled_index[filled] = j;
 -                      work[filled++] = array[j];
 -
 -                      if (array[j]->generation < min_generation)
 -                              min_generation = array[j]->generation;
 -              }
 -              common = paint_down_to_common(array[i], filled, work,
 -                                            min_generation);
 -              if (array[i]->object.flags & PARENT2)
 -                      redundant[i] = 1;
 -              for (j = 0; j < filled; j++)
 -                      if (work[j]->object.flags & PARENT1)
 -                              redundant[filled_index[j]] = 1;
 -              clear_commit_marks(array[i], all_flags);
 -              clear_commit_marks_many(filled, work, all_flags);
 -              free_commit_list(common);
 -      }
 -
 -      /* Now collect the result */
 -      COPY_ARRAY(work, array, cnt);
 -      for (i = filled = 0; i < cnt; i++)
 -              if (!redundant[i])
 -                      array[filled++] = work[i];
 -      for (j = filled, i = 0; i < cnt; i++)
 -              if (redundant[i])
 -                      array[j++] = work[i];
 -      free(work);
 -      free(redundant);
 -      free(filled_index);
 -      return filled;
 -}
 -
 -static struct commit_list *get_merge_bases_many_0(struct commit *one,
 -                                                int n,
 -                                                struct commit **twos,
 -                                                int cleanup)
 -{
 -      struct commit_list *list;
 -      struct commit **rslt;
 -      struct commit_list *result;
 -      int cnt, i;
 -
 -      result = merge_bases_many(one, n, twos);
 -      for (i = 0; i < n; i++) {
 -              if (one == twos[i])
 -                      return result;
 -      }
 -      if (!result || !result->next) {
 -              if (cleanup) {
 -                      clear_commit_marks(one, all_flags);
 -                      clear_commit_marks_many(n, twos, all_flags);
 -              }
 -              return result;
 -      }
 -
 -      /* There are more than one */
 -      cnt = commit_list_count(result);
 -      rslt = xcalloc(cnt, sizeof(*rslt));
 -      for (list = result, i = 0; list; list = list->next)
 -              rslt[i++] = list->item;
 -      free_commit_list(result);
 -
 -      clear_commit_marks(one, all_flags);
 -      clear_commit_marks_many(n, twos, all_flags);
 -
 -      cnt = remove_redundant(rslt, cnt);
 -      result = NULL;
 -      for (i = 0; i < cnt; i++)
 -              commit_list_insert_by_date(rslt[i], &result);
 -      free(rslt);
 -      return result;
 -}
 -
 -struct commit_list *get_merge_bases_many(struct commit *one,
 -                                       int n,
 -                                       struct commit **twos)
 -{
 -      return get_merge_bases_many_0(one, n, twos, 1);
 -}
 -
 -struct commit_list *get_merge_bases_many_dirty(struct commit *one,
 -                                             int n,
 -                                             struct commit **twos)
 -{
 -      return get_merge_bases_many_0(one, n, twos, 0);
 -}
 -
 -struct commit_list *get_merge_bases(struct commit *one, struct commit *two)
 -{
 -      return get_merge_bases_many_0(one, 1, &two, 1);
 -}
 -
 -/*
 - * Is "commit" a descendant of one of the elements on the "with_commit" list?
 - */
 -int is_descendant_of(struct commit *commit, struct commit_list *with_commit)
 -{
 -      if (!with_commit)
 -              return 1;
 -      while (with_commit) {
 -              struct commit *other;
 -
 -              other = with_commit->item;
 -              with_commit = with_commit->next;
 -              if (in_merge_bases(other, commit))
 -                      return 1;
 -      }
 -      return 0;
 -}
 -
 -/*
 - * Is "commit" an ancestor of one of the "references"?
 - */
 -int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference)
 -{
 -      struct commit_list *bases;
 -      int ret = 0, i;
 -      uint32_t min_generation = GENERATION_NUMBER_INFINITY;
 -
 -      if (parse_commit(commit))
 -              return ret;
 -      for (i = 0; i < nr_reference; i++) {
 -              if (parse_commit(reference[i]))
 -                      return ret;
 -              if (reference[i]->generation < min_generation)
 -                      min_generation = reference[i]->generation;
 -      }
 -
 -      if (commit->generation > min_generation)
 -              return ret;
 -
 -      bases = paint_down_to_common(commit, nr_reference, reference, commit->generation);
 -      if (commit->object.flags & PARENT2)
 -              ret = 1;
 -      clear_commit_marks(commit, all_flags);
 -      clear_commit_marks_many(nr_reference, reference, all_flags);
 -      free_commit_list(bases);
 -      return ret;
 -}
 -
 -/*
 - * Is "commit" an ancestor of (i.e. reachable from) the "reference"?
 - */
 -int in_merge_bases(struct commit *commit, struct commit *reference)
 -{
 -      return in_merge_bases_many(commit, 1, &reference);
 -}
 -
 -struct commit_list *reduce_heads(struct commit_list *heads)
 -{
 -      struct commit_list *p;
 -      struct commit_list *result = NULL, **tail = &result;
 -      struct commit **array;
 -      int num_head, i;
 -
 -      if (!heads)
 -              return NULL;
 -
 -      /* Uniquify */
 -      for (p = heads; p; p = p->next)
 -              p->item->object.flags &= ~STALE;
 -      for (p = heads, num_head = 0; p; p = p->next) {
 -              if (p->item->object.flags & STALE)
 -                      continue;
 -              p->item->object.flags |= STALE;
 -              num_head++;
 -      }
 -      array = xcalloc(num_head, sizeof(*array));
 -      for (p = heads, i = 0; p; p = p->next) {
 -              if (p->item->object.flags & STALE) {
 -                      array[i++] = p->item;
 -                      p->item->object.flags &= ~STALE;
 -              }
 -      }
 -      num_head = remove_redundant(array, num_head);
 -      for (i = 0; i < num_head; i++)
 -              tail = &commit_list_insert(array[i], tail)->next;
 -      free(array);
 -      return result;
 -}
 -
 -void reduce_heads_replace(struct commit_list **heads)
 -{
 -      struct commit_list *result = reduce_heads(*heads);
 -      free_commit_list(*heads);
 -      *heads = result;
 -}
 -
  static const char gpg_sig_header[] = "gpgsig";
  static const int gpg_sig_header_len = sizeof(gpg_sig_header) - 1;
  
@@@ -1426,10 -1865,10 +1508,10 @@@ const char *find_commit_header(const ch
   * Returns the number of bytes from the tail to ignore, to be fed as
   * the second parameter to append_signoff().
   */
 -int ignore_non_trailer(const char *buf, size_t len)
 +size_t ignore_non_trailer(const char *buf, size_t len)
  {
 -      int boc = 0;
 -      int bol = 0;
 +      size_t boc = 0;
 +      size_t bol = 0;
        int in_old_conflicts_block = 0;
        size_t cutoff = wt_status_locate_end(buf, len);
  
diff --combined commit.h
index 1d260d62f57a24864986252892faa89c17572210,b34240017f616d765b8a2d1795e7b41ac2d05d67..6c4428c5931a9ab9d77d96a8a21aba4d75d73108
+++ b/commit.h
@@@ -202,9 -202,17 +202,11 @@@ typedef int (*each_commit_graft_fn)(con
  
  struct commit_graft *read_graft_line(struct strbuf *line);
  int register_commit_graft(struct repository *r, struct commit_graft *, int);
 +void prepare_commit_graft(struct repository *r);
  struct commit_graft *lookup_commit_graft(struct repository *r, const struct object_id *oid);
  
 -extern struct commit_list *get_merge_bases(struct commit *rev1, struct commit *rev2);
 -extern struct commit_list *get_merge_bases_many(struct commit *one, int n, struct commit **twos);
 -extern struct commit_list *get_octopus_merge_bases(struct commit_list *in);
 -
 -/* To be used only when object flags after this call no longer matter */
 -extern struct commit_list *get_merge_bases_many_dirty(struct commit *one, int n, struct commit **twos);
 -
+ struct commit *get_fork_point(const char *refname, struct commit *commit);
  /* largest positive number a signed 32-bit integer can contain */
  #define INFINITE_DEPTH 0x7fffffff
  
@@@ -252,10 -260,32 +254,10 @@@ extern int delayed_reachability_test(st
  extern void prune_shallow(int show_only);
  extern struct trace_key trace_shallow;
  
 -int is_descendant_of(struct commit *, struct commit_list *);
 -int in_merge_bases(struct commit *, struct commit *);
 -int in_merge_bases_many(struct commit *, int, struct commit **);
 -
  extern int interactive_add(int argc, const char **argv, const char *prefix, int patch);
  extern int run_add_interactive(const char *revision, const char *patch_mode,
                               const struct pathspec *pathspec);
  
 -/*
 - * Takes a list of commits and returns a new list where those
 - * have been removed that can be reached from other commits in
 - * the list. It is useful for, e.g., reducing the commits
 - * randomly thrown at the git-merge command and removing
 - * redundant commits that the user shouldn't have given to it.
 - *
 - * This function destroys the STALE bit of the commit objects'
 - * flags.
 - */
 -extern struct commit_list *reduce_heads(struct commit_list *heads);
 -
 -/*
 - * Like `reduce_heads()`, except it replaces the list. Use this
 - * instead of `foo = reduce_heads(foo);` to avoid memory leaks.
 - */
 -extern void reduce_heads_replace(struct commit_list **heads);
 -
  struct commit_extra_header {
        struct commit_extra_header *next;
        char *key;
@@@ -294,7 -324,7 +296,7 @@@ extern const char *find_commit_header(c
                                      size_t *out_len);
  
  /* Find the end of the log message, the right place for a new trailer. */
 -extern int ignore_non_trailer(const char *buf, size_t len);
 +extern size_t ignore_non_trailer(const char *buf, size_t len);
  
  typedef int (*each_mergetag_fn)(struct commit *commit, struct commit_extra_header *extra,
                                 void *cb_data);