Merge branch 'ds/reachable'
authorJunio C Hamano <gitster@pobox.com>
Mon, 17 Sep 2018 20:53:52 +0000 (13:53 -0700)
committerJunio C Hamano <gitster@pobox.com>
Mon, 17 Sep 2018 20:53:52 +0000 (13:53 -0700)
The code for computing history reachability has been shuffled,
obtained a bunch of new tests to cover them, and then being
improved.

* ds/reachable:
commit-reach: correct accidental #include of C file
commit-reach: use can_all_from_reach
commit-reach: make can_all_from_reach... linear
commit-reach: replace ref_newer logic
test-reach: test commit_contains
test-reach: test can_all_from_reach_with_flags
test-reach: test reduce_heads
test-reach: test get_merge_bases_many
test-reach: test is_descendant_of
test-reach: test in_merge_bases
test-reach: create new test tool for ref_newer
commit-reach: move can_all_from_reach_with_flags
upload-pack: generalize commit date cutoff
upload-pack: refactor ok_to_give_up()
upload-pack: make reachable() more generic
commit-reach: move commit_contains from ref-filter
commit-reach: move ref_newer from remote.c
commit.h: remove method declarations
commit-reach: move walk methods from commit.c

28 files changed:
1  2 
Makefile
builtin/branch.c
builtin/commit.c
builtin/fetch.c
builtin/fmt-merge-msg.c
builtin/log.c
builtin/merge.c
builtin/pull.c
builtin/receive-pack.c
builtin/remote.c
commit-graph.c
commit-graph.h
commit-reach.c
commit.c
fast-import.c
merge-recursive.c
object.h
pack-bitmap-write.c
ref-filter.c
remote.c
remote.h
revision.c
sequencer.c
sha1-name.c
submodule.c
t/helper/test-tool.c
t/helper/test-tool.h
upload-pack.c
diff --combined Makefile
index bd83683a87aa9797d4519bf7c20591df9d5c8de8,d69f9d415d294e28d65a78140d0284e6848c3f0c..d6cd9a53552b1914de9077c8628f09fe892156de
+++ b/Makefile
@@@ -484,11 -484,6 +484,11 @@@ all:
  #        The DEVELOPER mode enables -Wextra with a few exceptions. By
  #        setting this flag the exceptions are removed, and all of
  #        -Wextra is used.
 +#
 +#    pedantic:
 +#
 +#        Enable -pedantic compilation. This also disables
 +#        USE_PARENS_AROUND_GETTEXT_N to produce only relevant warnings.
  
  GIT-VERSION-FILE: FORCE
        @$(SHELL_PATH) ./GIT-VERSION-GEN
@@@ -569,7 -564,7 +569,7 @@@ SPATCH = spatc
  export TCL_PATH TCLTK_PATH
  
  SPARSE_FLAGS =
 -SPATCH_FLAGS = --all-includes
 +SPATCH_FLAGS = --all-includes --patch .
  
  
  
@@@ -714,7 -709,6 +714,7 @@@ TEST_BUILTINS_OBJS += test-example-deco
  TEST_BUILTINS_OBJS += test-genrandom.o
  TEST_BUILTINS_OBJS += test-hashmap.o
  TEST_BUILTINS_OBJS += test-index-version.o
 +TEST_BUILTINS_OBJS += test-json-writer.o
  TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o
  TEST_BUILTINS_OBJS += test-match-trees.o
  TEST_BUILTINS_OBJS += test-mergesort.o
@@@ -722,8 -716,8 +722,9 @@@ TEST_BUILTINS_OBJS += test-mktemp.
  TEST_BUILTINS_OBJS += test-online-cpus.o
  TEST_BUILTINS_OBJS += test-path-utils.o
  TEST_BUILTINS_OBJS += test-prio-queue.o
+ TEST_BUILTINS_OBJS += test-reach.o
  TEST_BUILTINS_OBJS += test-read-cache.o
 +TEST_BUILTINS_OBJS += test-read-midx.o
  TEST_BUILTINS_OBJS += test-ref-store.o
  TEST_BUILTINS_OBJS += test-regex.o
  TEST_BUILTINS_OBJS += test-repository.o
@@@ -836,6 -830,7 +837,7 @@@ LIB_OBJS += column.
  LIB_OBJS += combine-diff.o
  LIB_OBJS += commit.o
  LIB_OBJS += commit-graph.o
+ LIB_OBJS += commit-reach.o
  LIB_OBJS += compat/obstack.o
  LIB_OBJS += compat/terminal.o
  LIB_OBJS += config.o
@@@ -867,7 -862,6 +869,7 @@@ LIB_OBJS += ewah/ewah_bitmap.
  LIB_OBJS += ewah/ewah_io.o
  LIB_OBJS += ewah/ewah_rlw.o
  LIB_OBJS += exec-cmd.o
 +LIB_OBJS += fetch-negotiator.o
  LIB_OBJS += fetch-object.o
  LIB_OBJS += fetch-pack.o
  LIB_OBJS += fsck.o
@@@ -877,11 -871,9 +879,11 @@@ LIB_OBJS += gpg-interface.
  LIB_OBJS += graph.o
  LIB_OBJS += grep.o
  LIB_OBJS += hashmap.o
 +LIB_OBJS += linear-assignment.o
  LIB_OBJS += help.o
  LIB_OBJS += hex.o
  LIB_OBJS += ident.o
 +LIB_OBJS += json-writer.o
  LIB_OBJS += kwset.o
  LIB_OBJS += levenshtein.o
  LIB_OBJS += line-log.o
@@@ -901,10 -893,7 +903,10 @@@ LIB_OBJS += merge.
  LIB_OBJS += merge-blobs.o
  LIB_OBJS += merge-recursive.o
  LIB_OBJS += mergesort.o
 +LIB_OBJS += midx.o
  LIB_OBJS += name-hash.o
 +LIB_OBJS += negotiator/default.o
 +LIB_OBJS += negotiator/skipping.o
  LIB_OBJS += notes.o
  LIB_OBJS += notes-cache.o
  LIB_OBJS += notes-merge.o
@@@ -934,7 -923,6 +936,7 @@@ LIB_OBJS += progress.
  LIB_OBJS += prompt.o
  LIB_OBJS += protocol.o
  LIB_OBJS += quote.o
 +LIB_OBJS += range-diff.o
  LIB_OBJS += reachable.o
  LIB_OBJS += read-cache.o
  LIB_OBJS += reflog-walk.o
@@@ -1062,7 -1050,6 +1064,7 @@@ BUILTIN_OBJS += builtin/merge-recursive
  BUILTIN_OBJS += builtin/merge-tree.o
  BUILTIN_OBJS += builtin/mktag.o
  BUILTIN_OBJS += builtin/mktree.o
 +BUILTIN_OBJS += builtin/multi-pack-index.o
  BUILTIN_OBJS += builtin/mv.o
  BUILTIN_OBJS += builtin/name-rev.o
  BUILTIN_OBJS += builtin/notes.o
@@@ -1074,7 -1061,6 +1076,7 @@@ BUILTIN_OBJS += builtin/prune-packed.
  BUILTIN_OBJS += builtin/prune.o
  BUILTIN_OBJS += builtin/pull.o
  BUILTIN_OBJS += builtin/push.o
 +BUILTIN_OBJS += builtin/range-diff.o
  BUILTIN_OBJS += builtin/read-tree.o
  BUILTIN_OBJS += builtin/rebase--helper.o
  BUILTIN_OBJS += builtin/receive-pack.o
@@@ -2038,9 -2024,8 +2040,9 @@@ version.sp version.s version.o: GIT-VER
  version.sp version.s version.o: EXTRA_CPPFLAGS = \
        '-DGIT_VERSION="$(GIT_VERSION)"' \
        '-DGIT_USER_AGENT=$(GIT_USER_AGENT_CQ_SQ)' \
 -      '-DGIT_BUILT_FROM_COMMIT="$(shell GIT_CEILING_DIRECTORIES=\"$(CURDIR)/..\" \
 -              git rev-parse -q --verify HEAD || :)"'
 +      '-DGIT_BUILT_FROM_COMMIT="$(shell \
 +              GIT_CEILING_DIRECTORIES="$(CURDIR)/.." \
 +              git rev-parse -q --verify HEAD 2>/dev/null)"'
  
  $(BUILT_INS): git$X
        $(QUIET_BUILT_IN)$(RM) $@ && \
  
  command-list.h: generate-cmdlist.sh command-list.txt
  
 -command-list.h: $(wildcard Documentation/git*.txt)
 +command-list.h: $(wildcard Documentation/git*.txt) Documentation/*config.txt
        $(QUIET_GEN)$(SHELL_PATH) ./generate-cmdlist.sh command-list.txt >$@+ && mv $@+ $@
  
  SCRIPT_DEFINES = $(SHELL_PATH_SQ):$(DIFF_SQ):$(GIT_VERSION):\
@@@ -2128,7 -2113,7 +2130,7 @@@ $(SCRIPT_PERL_GEN): % : %.perl GIT-PERL
        $(QUIET_GEN)$(RM) $@ $@+ && \
        sed -e '1{' \
            -e '        s|#!.*perl|#!$(PERL_PATH_SQ)|' \
 -          -e '        rGIT-PERL-HEADER' \
 +          -e '        r GIT-PERL-HEADER' \
            -e '        G' \
            -e '}' \
            -e 's/@@GIT_VERSION@@/$(GIT_VERSION)/g' \
@@@ -2686,16 -2671,10 +2688,16 @@@ check: command-list.
        fi
  
  C_SOURCES = $(patsubst %.o,%.c,$(C_OBJ))
 -%.cocci.patch: %.cocci $(C_SOURCES)
 +ifdef DC_SHA1_SUBMODULE
 +COCCI_SOURCES = $(filter-out sha1collisiondetection/%,$(C_SOURCES))
 +else
 +COCCI_SOURCES = $(filter-out sha1dc/%,$(C_SOURCES))
 +endif
 +
 +%.cocci.patch: %.cocci $(COCCI_SOURCES)
        @echo '    ' SPATCH $<; \
        ret=0; \
 -      for f in $(C_SOURCES); do \
 +      for f in $(COCCI_SOURCES); do \
                $(SPATCH) --sp-file $< $$f $(SPATCH_FLAGS) || \
                        { ret=$$?; break; }; \
        done >$@+ 2>$@.log; \
        then \
                echo '    ' SPATCH result: $@; \
        fi
 -coccicheck: $(patsubst %.cocci,%.cocci.patch,$(wildcard contrib/coccinelle/*.cocci))
 +coccicheck: $(addsuffix .patch,$(wildcard contrib/coccinelle/*.cocci))
 +
 +.PHONY: coccicheck
  
  ### Installation rules
  
@@@ -2923,10 -2900,7 +2925,10 @@@ profile-clean
        $(RM) $(addsuffix *.gcda,$(addprefix $(PROFILE_DIR)/, $(object_dirs)))
        $(RM) $(addsuffix *.gcno,$(addprefix $(PROFILE_DIR)/, $(object_dirs)))
  
 -clean: profile-clean coverage-clean
 +cocciclean:
 +      $(RM) contrib/coccinelle/*.cocci.patch*
 +
 +clean: profile-clean coverage-clean cocciclean
        $(RM) *.res
        $(RM) $(OBJECTS)
        $(RM) $(LIB_FILE) $(XDIFF_LIB) $(VCSSVN_LIB)
        $(RM) -r $(GIT_TARNAME) .doc-tmp-dir
        $(RM) $(GIT_TARNAME).tar.gz git-core_$(GIT_VERSION)-*.tar.gz
        $(RM) $(htmldocs).tar.gz $(manpages).tar.gz
 -      $(RM) contrib/coccinelle/*.cocci.patch*
        $(MAKE) -C Documentation/ clean
  ifndef NO_PERL
        $(MAKE) -C gitweb clean
@@@ -2953,7 -2928,7 +2955,7 @@@ endi
        $(RM) GIT-USER-AGENT GIT-PREFIX
        $(RM) GIT-SCRIPT-DEFINES GIT-PERL-DEFINES GIT-PERL-HEADER GIT-PYTHON-VARS
  
 -.PHONY: all install profile-clean clean strip
 +.PHONY: all install profile-clean cocciclean clean strip
  .PHONY: shell_compatibility_test please_set_SHELL_PATH_to_a_more_modern_shell
  .PHONY: FORCE cscope
  
diff --combined builtin/branch.c
index 5b4d883e1f6f432ce07aed6ac86532c6d877a969,9a787447f47bacf85ef03a765ade27f8945fd190..c396c41533c38630378db370f1db30e99aad849b
@@@ -23,6 -23,7 +23,7 @@@
  #include "ref-filter.h"
  #include "worktree.h"
  #include "help.h"
+ #include "commit-reach.h"
  
  static const char * const builtin_branch_usage[] = {
        N_("git branch [<options>] [-r | -a] [--merged | --no-merged]"),
@@@ -73,14 -74,6 +74,14 @@@ define_list_config_array(color_branch_s
  static int git_branch_config(const char *var, const char *value, void *cb)
  {
        const char *slot_name;
 +      struct ref_sorting **sorting_tail = (struct ref_sorting **)cb;
 +
 +      if (!strcmp(var, "branch.sort")) {
 +              if (!value)
 +                      return config_error_nonbool(var);
 +              parse_ref_sorting(sorting_tail, value);
 +              return 0;
 +      }
  
        if (starts_with(var, "column."))
                return git_column_config(var, value, "branch", &colopts);
@@@ -618,8 -611,8 +619,8 @@@ int cmd_branch(int argc, const char **a
                OPT_BIT('M', NULL, &rename, N_("move/rename a branch, even if target exists"), 2),
                OPT_BIT('c', "copy", &copy, N_("copy a branch and its reflog"), 1),
                OPT_BIT('C', NULL, &copy, N_("copy a branch, even if target exists"), 2),
 -              OPT_BOOL(0, "list", &list, N_("list branch names")),
 -              OPT_BOOL('l', "create-reflog", &reflog, N_("create the branch's reflog")),
 +              OPT_BOOL('l', "list", &list, N_("list branch names")),
 +              OPT_BOOL(0, "create-reflog", &reflog, N_("create the branch's reflog")),
                OPT_BOOL(0, "edit-description", &edit_description,
                         N_("edit the description for the branch")),
                OPT__FORCE(&force, N_("force creation, move/rename, deletion"), PARSE_OPT_NOCOMPLETE),
        if (argc == 2 && !strcmp(argv[1], "-h"))
                usage_with_options(builtin_branch_usage, options);
  
 -      git_config(git_branch_config, NULL);
 +      git_config(git_branch_config, sorting_tail);
  
        track = git_branch_track;
  
diff --combined builtin/commit.c
index 0d9828e29ebe89f037e68761d5cd5b407339cd48,b5c608458e8a20f3a96b7103d4437f499edb2026..fa3e53232d2d24564a2de6370b3bdef72a153735
@@@ -33,6 -33,7 +33,7 @@@
  #include "sequencer.h"
  #include "mailmap.h"
  #include "help.h"
+ #include "commit-reach.h"
  
  static const char * const builtin_commit_usage[] = {
        N_("git commit [<options>] [--] <pathspec>..."),
@@@ -251,7 -252,7 +252,7 @@@ static int list_paths(struct string_lis
  
                if (ce->ce_flags & CE_UPDATE)
                        continue;
 -              if (!ce_path_match(ce, pattern, m))
 +              if (!ce_path_match(&the_index, ce, pattern, m))
                        continue;
                item = string_list_insert(list, ce->name);
                if (ce_skip_worktree(ce))
@@@ -1647,9 -1648,9 +1648,9 @@@ int cmd_commit(int argc, const char **a
        unlink(git_path_squash_msg(the_repository));
  
        if (commit_index_files())
 -              die (_("Repository has been updated, but unable to write\n"
 -                   "new_index file. Check that disk is not full and quota is\n"
 -                   "not exceeded, and then \"git reset HEAD\" to recover."));
 +              die(_("repository has been updated, but unable to write\n"
 +                    "new_index file. Check that disk is not full and quota is\n"
 +                    "not exceeded, and then \"git reset HEAD\" to recover."));
  
        rerere(0);
        run_command_v_opt(argv_gc_auto, RUN_GIT_CMD);
diff --combined builtin/fetch.c
index 61bec5d213d47141d14162bd1a2ca88861c22ef7,7de234774be0383269f42453c09cb2c0e79095dc..eed15c78137a7e86be3ad7600b0001e33b1f7aa7
@@@ -22,6 -22,7 +22,7 @@@
  #include "utf8.h"
  #include "packfile.h"
  #include "list-objects-filter-options.h"
+ #include "commit-reach.h"
  
  static const char * const builtin_fetch_usage[] = {
        N_("git fetch [<options>] [<repository> [<refspec>...]]"),
@@@ -64,7 -65,6 +65,7 @@@ static int shown_url = 0
  static struct refspec refmap = REFSPEC_INIT_FETCH;
  static struct list_objects_filter_options filter_options;
  static struct string_list server_options = STRING_LIST_INIT_DUP;
 +static struct string_list negotiation_tip = STRING_LIST_INIT_NODUP;
  
  static int git_fetch_config(const char *k, const char *v, void *cb)
  {
        return git_default_config(k, v, cb);
  }
  
 -static int gitmodules_fetch_config(const char *var, const char *value, void *cb)
 -{
 -      if (!strcmp(var, "submodule.fetchjobs")) {
 -              max_children = parse_submodule_fetchjobs(var, value);
 -              return 0;
 -      } else if (!strcmp(var, "fetch.recursesubmodules")) {
 -              recurse_submodules = parse_fetch_recurse_submodules_arg(var, value);
 -              return 0;
 -      }
 -
 -      return 0;
 -}
 -
  static int parse_refmap_arg(const struct option *opt, const char *arg, int unset)
  {
        /*
@@@ -163,8 -176,6 +164,8 @@@ static struct option builtin_fetch_opti
                        TRANSPORT_FAMILY_IPV4),
        OPT_SET_INT('6', "ipv6", &family, N_("use IPv6 addresses only"),
                        TRANSPORT_FAMILY_IPV6),
 +      OPT_STRING_LIST(0, "negotiation-tip", &negotiation_tip, N_("revision"),
 +                      N_("report that we have only objects reachable from this object")),
        OPT_PARSE_LIST_OBJECTS_FILTER(&filter_options),
        OPT_END()
  };
@@@ -245,9 -256,9 +246,9 @@@ static int will_fetch(struct ref **head
        return 0;
  }
  
 -static void find_non_local_tags(struct transport *transport,
 -                      struct ref **head,
 -                      struct ref ***tail)
 +static void find_non_local_tags(const struct ref *refs,
 +                              struct ref **head,
 +                              struct ref ***tail)
  {
        struct string_list existing_refs = STRING_LIST_INIT_DUP;
        struct string_list remote_refs = STRING_LIST_INIT_NODUP;
        struct string_list_item *item = NULL;
  
        for_each_ref(add_existing, &existing_refs);
 -      for (ref = transport_get_remote_refs(transport, NULL); ref; ref = ref->next) {
 +      for (ref = refs; ref; ref = ref->next) {
                if (!starts_with(ref->name, "refs/tags/"))
                        continue;
  
        string_list_clear(&remote_refs, 0);
  }
  
 -static struct ref *get_ref_map(struct transport *transport,
 +static struct ref *get_ref_map(struct remote *remote,
 +                             const struct ref *remote_refs,
                               struct refspec *rs,
                               int tags, int *autotags)
  {
        struct ref *rm;
        struct ref *ref_map = NULL;
        struct ref **tail = &ref_map;
 -      struct argv_array ref_prefixes = ARGV_ARRAY_INIT;
  
        /* opportunistically-updated references: */
        struct ref *orefs = NULL, **oref_tail = &orefs;
  
 -      const struct ref *remote_refs;
 -
 -      if (rs->nr)
 -              refspec_ref_prefixes(rs, &ref_prefixes);
 -      else if (transport->remote && transport->remote->fetch.nr)
 -              refspec_ref_prefixes(&transport->remote->fetch, &ref_prefixes);
 -
 -      if (ref_prefixes.argc &&
 -          (tags == TAGS_SET || (tags == TAGS_DEFAULT && !rs->nr))) {
 -              argv_array_push(&ref_prefixes, "refs/tags/");
 -      }
 -
 -      remote_refs = transport_get_remote_refs(transport, &ref_prefixes);
 -
 -      argv_array_clear(&ref_prefixes);
 +      struct string_list existing_refs = STRING_LIST_INIT_DUP;
  
        if (rs->nr) {
                struct refspec *fetch_refspec;
                if (refmap.nr)
                        fetch_refspec = &refmap;
                else
 -                      fetch_refspec = &transport->remote->fetch;
 +                      fetch_refspec = &remote->fetch;
  
                for (i = 0; i < fetch_refspec->nr; i++)
                        get_fetch_map(ref_map, &fetch_refspec->items[i], &oref_tail, 1);
                die("--refmap option is only meaningful with command-line refspec(s).");
        } else {
                /* Use the defaults */
 -              struct remote *remote = transport->remote;
                struct branch *branch = branch_get(NULL);
                int has_merge = branch_has_merge_config(branch);
                if (remote &&
                /* also fetch all tags */
                get_fetch_map(remote_refs, tag_refspec, &tail, 0);
        else if (tags == TAGS_DEFAULT && *autotags)
 -              find_non_local_tags(transport, &ref_map, &tail);
 +              find_non_local_tags(remote_refs, &ref_map, &tail);
  
        /* Now append any refs to be updated opportunistically: */
        *tail = orefs;
                tail = &rm->next;
        }
  
 -      return ref_remove_duplicates(ref_map);
 +      ref_map = ref_remove_duplicates(ref_map);
 +
 +      for_each_ref(add_existing, &existing_refs);
 +      for (rm = ref_map; rm; rm = rm->next) {
 +              if (rm->peer_ref) {
 +                      struct string_list_item *peer_item =
 +                              string_list_lookup(&existing_refs,
 +                                                 rm->peer_ref->name);
 +                      if (peer_item) {
 +                              struct object_id *old_oid = peer_item->util;
 +                              oidcpy(&rm->peer_ref->old_oid, old_oid);
 +                      }
 +              }
 +      }
 +      string_list_clear(&existing_refs, 1);
 +
 +      return ref_map;
  }
  
  #define STORE_REF_ERROR_OTHER 1
@@@ -762,7 -772,7 +763,7 @@@ static int iterate_ref_map(void *cb_dat
  }
  
  static int store_updated_refs(const char *raw_url, const char *remote_name,
 -              struct ref *ref_map)
 +                            int connectivity_checked, struct ref *ref_map)
  {
        FILE *fp;
        struct commit *commit;
        else
                url = xstrdup("foreign");
  
 -      rm = ref_map;
 -      if (check_connected(iterate_ref_map, &rm, NULL)) {
 -              rc = error(_("%s did not send all necessary objects\n"), url);
 -              goto abort;
 +      if (!connectivity_checked) {
 +              rm = ref_map;
 +              if (check_connected(iterate_ref_map, &rm, NULL)) {
 +                      rc = error(_("%s did not send all necessary objects\n"), url);
 +                      goto abort;
 +              }
        }
  
        prepare_format_display(ref_map);
@@@ -948,24 -956,9 +949,24 @@@ static int fetch_refs(struct transport 
        if (ret)
                ret = transport_fetch_refs(transport, ref_map);
        if (!ret)
 -              ret |= store_updated_refs(transport->url,
 -                              transport->remote->name,
 -                              ref_map);
 +              /*
 +               * Keep the new pack's ".keep" file around to allow the caller
 +               * time to update refs to reference the new objects.
 +               */
 +              return 0;
 +      transport_unlock_pack(transport);
 +      return ret;
 +}
 +
 +/* Update local refs based on the ref values fetched from a remote */
 +static int consume_refs(struct transport *transport, struct ref *ref_map)
 +{
 +      int connectivity_checked = transport->smart_options
 +              ? transport->smart_options->connectivity_checked : 0;
 +      int ret = store_updated_refs(transport->url,
 +                                   transport->remote->name,
 +                                   connectivity_checked,
 +                                   ref_map);
        transport_unlock_pack(transport);
        return ret;
  }
@@@ -1061,40 -1054,6 +1062,40 @@@ static void set_option(struct transpor
                        name, transport->url);
  }
  
 +
 +static int add_oid(const char *refname, const struct object_id *oid, int flags,
 +                 void *cb_data)
 +{
 +      struct oid_array *oids = cb_data;
 +
 +      oid_array_append(oids, oid);
 +      return 0;
 +}
 +
 +static void add_negotiation_tips(struct git_transport_options *smart_options)
 +{
 +      struct oid_array *oids = xcalloc(1, sizeof(*oids));
 +      int i;
 +
 +      for (i = 0; i < negotiation_tip.nr; i++) {
 +              const char *s = negotiation_tip.items[i].string;
 +              int old_nr;
 +              if (!has_glob_specials(s)) {
 +                      struct object_id oid;
 +                      if (get_oid(s, &oid))
 +                              die("%s is not a valid object", s);
 +                      oid_array_append(oids, &oid);
 +                      continue;
 +              }
 +              old_nr = oids->nr;
 +              for_each_glob_ref(add_oid, s, oids);
 +              if (old_nr == oids->nr)
 +                      warning("Ignoring --negotiation-tip=%s because it does not match any refs",
 +                              s);
 +      }
 +      smart_options->negotiation_tips = oids;
 +}
 +
  static struct transport *prepare_transport(struct remote *remote, int deepen)
  {
        struct transport *transport;
                           filter_options.filter_spec);
                set_option(transport, TRANS_OPT_FROM_PROMISOR, "1");
        }
 +      if (negotiation_tip.nr) {
 +              if (transport->smart_options)
 +                      add_negotiation_tips(transport->smart_options);
 +              else
 +                      warning("Ignoring --negotiation-tip because the protocol does not support it.");
 +      }
        return transport;
  }
  
@@@ -1151,8 -1104,7 +1152,8 @@@ static void backfill_tags(struct transp
        transport_set_option(transport, TRANS_OPT_FOLLOWTAGS, NULL);
        transport_set_option(transport, TRANS_OPT_DEPTH, "0");
        transport_set_option(transport, TRANS_OPT_DEEPEN_RELATIVE, NULL);
 -      fetch_refs(transport, ref_map);
 +      if (!fetch_refs(transport, ref_map))
 +              consume_refs(transport, ref_map);
  
        if (gsecondary) {
                transport_disconnect(gsecondary);
  static int do_fetch(struct transport *transport,
                    struct refspec *rs)
  {
 -      struct string_list existing_refs = STRING_LIST_INIT_DUP;
        struct ref *ref_map;
 -      struct ref *rm;
        int autotags = (transport->remote->fetch_tags == 1);
        int retcode = 0;
 -
 -      for_each_ref(add_existing, &existing_refs);
 +      const struct ref *remote_refs;
 +      struct argv_array ref_prefixes = ARGV_ARRAY_INIT;
  
        if (tags == TAGS_DEFAULT) {
                if (transport->remote->fetch_tags == 2)
                        goto cleanup;
        }
  
 -      ref_map = get_ref_map(transport, rs, tags, &autotags);
 -      if (!update_head_ok)
 -              check_not_current_branch(ref_map);
 +      if (rs->nr)
 +              refspec_ref_prefixes(rs, &ref_prefixes);
 +      else if (transport->remote && transport->remote->fetch.nr)
 +              refspec_ref_prefixes(&transport->remote->fetch, &ref_prefixes);
  
 -      for (rm = ref_map; rm; rm = rm->next) {
 -              if (rm->peer_ref) {
 -                      struct string_list_item *peer_item =
 -                              string_list_lookup(&existing_refs,
 -                                                 rm->peer_ref->name);
 -                      if (peer_item) {
 -                              struct object_id *old_oid = peer_item->util;
 -                              oidcpy(&rm->peer_ref->old_oid, old_oid);
 -                      }
 -              }
 +      if (ref_prefixes.argc &&
 +          (tags == TAGS_SET || (tags == TAGS_DEFAULT))) {
 +              argv_array_push(&ref_prefixes, "refs/tags/");
        }
  
 +      remote_refs = transport_get_remote_refs(transport, &ref_prefixes);
 +      argv_array_clear(&ref_prefixes);
 +
 +      ref_map = get_ref_map(transport->remote, remote_refs, rs,
 +                            tags, &autotags);
 +      if (!update_head_ok)
 +              check_not_current_branch(ref_map);
 +
        if (tags == TAGS_DEFAULT && autotags)
                transport_set_option(transport, TRANS_OPT_FOLLOWTAGS, "1");
        if (prune) {
                                   transport->url);
                }
        }
 -      if (fetch_refs(transport, ref_map)) {
 +      if (fetch_refs(transport, ref_map) || consume_refs(transport, ref_map)) {
                free_refs(ref_map);
                retcode = 1;
                goto cleanup;
        if (tags == TAGS_DEFAULT && autotags) {
                struct ref **tail = &ref_map;
                ref_map = NULL;
 -              find_non_local_tags(transport, &ref_map, &tail);
 +              find_non_local_tags(remote_refs, &ref_map, &tail);
                if (ref_map)
                        backfill_tags(transport, ref_map);
                free_refs(ref_map);
        }
  
   cleanup:
 -      string_list_clear(&existing_refs, 1);
        return retcode;
  }
  
@@@ -1485,7 -1438,7 +1486,7 @@@ int cmd_fetch(int argc, const char **ar
        for (i = 1; i < argc; i++)
                strbuf_addf(&default_rla, " %s", argv[i]);
  
 -      config_from_gitmodules(gitmodules_fetch_config, NULL);
 +      fetch_config_from_gitmodules(&max_children, &recurse_submodules);
        git_config(git_fetch_config, NULL);
  
        argc = parse_options(argc, argv, prefix,
diff --combined builtin/fmt-merge-msg.c
index f35ff1612bb563c819b611e82f8e3a7730d32461,7277d557b2d1972250e5b8b4117bc3be23964b6f..e5668f27d8df7deee8705587e3c9eddb0be61818
@@@ -12,6 -12,7 +12,7 @@@
  #include "fmt-merge-msg.h"
  #include "gpg-interface.h"
  #include "repository.h"
+ #include "commit-reach.h"
  
  static const char * const fmt_merge_msg_usage[] = {
        N_("git fmt-merge-msg [-m <message>] [--log[=<n>] | --no-log] [--file <file>]"),
@@@ -110,15 -111,14 +111,15 @@@ static int handle_line(char *line, stru
        struct string_list_item *item;
        int pulling_head = 0;
        struct object_id oid;
 +      const unsigned hexsz = the_hash_algo->hexsz;
  
 -      if (len < GIT_SHA1_HEXSZ + 3 || line[GIT_SHA1_HEXSZ] != '\t')
 +      if (len < hexsz + 3 || line[hexsz] != '\t')
                return 1;
  
 -      if (starts_with(line + GIT_SHA1_HEXSZ + 1, "not-for-merge"))
 +      if (starts_with(line + hexsz + 1, "not-for-merge"))
                return 0;
  
 -      if (line[GIT_SHA1_HEXSZ + 1] != '\t')
 +      if (line[hexsz + 1] != '\t')
                return 2;
  
        i = get_oid_hex(line, &oid);
  
        if (line[len - 1] == '\n')
                line[len - 1] = 0;
 -      line += GIT_SHA1_HEXSZ + 2;
 +      line += hexsz + 2;
  
        /*
         * At this point, line points at the beginning of comment e.g.
@@@ -347,7 -347,7 +348,7 @@@ static void shortlog(const char *name
  
        branch = deref_tag(the_repository, parse_object(the_repository, oid),
                           oid_to_hex(oid),
 -                         GIT_SHA1_HEXSZ);
 +                         the_hash_algo->hexsz);
        if (!branch || branch->type != OBJ_COMMIT)
                return;
  
@@@ -550,7 -550,6 +551,7 @@@ static void find_merge_parents(struct m
                int len;
                char *p = in->buf + pos;
                char *newline = strchr(p, '\n');
 +              const char *q;
                struct object_id oid;
                struct commit *parent;
                struct object *obj;
                len = newline ? newline - p : strlen(p);
                pos += len + !!newline;
  
 -              if (len < GIT_SHA1_HEXSZ + 3 ||
 -                  get_oid_hex(p, &oid) ||
 -                  p[GIT_SHA1_HEXSZ] != '\t' ||
 -                  p[GIT_SHA1_HEXSZ + 1] != '\t')
 +              if (parse_oid_hex(p, &oid, &q) ||
 +                  q[0] != '\t' ||
 +                  q[1] != '\t')
                        continue; /* skip not-for-merge */
                /*
                 * Do not use get_merge_parent() here; we do not have
@@@ -628,7 -628,7 +629,7 @@@ int fmt_merge_msg(struct strbuf *in, st
                i++;
                p[len] = 0;
                if (handle_line(p, &merge_parents))
 -                      die ("Error in line %d: %.*s", i, len, p);
 +                      die("error in line %d: %.*s", i, len, p);
        }
  
        if (opts->add_title && srcs.nr)
diff --combined builtin/log.c
index e094560d9abca6e819c24b845dc7c04d384850c3,333d97c69288ac2ded86ed38431e94660b372cdd..517c5e67890d421fd1f15fb454221eb1fa0634f4
@@@ -31,6 -31,7 +31,7 @@@
  #include "progress.h"
  #include "commit-slab.h"
  #include "repository.h"
+ #include "commit-reach.h"
  
  #define MAIL_DEFAULT_WRAP 72
  
@@@ -1608,14 -1609,14 +1609,14 @@@ int cmd_format_patch(int argc, const ch
                numbered = 0;
  
        if (numbered && keep_subject)
 -              die (_("-n and -k are mutually exclusive."));
 +              die(_("-n and -k are mutually exclusive"));
        if (keep_subject && subject_prefix)
 -              die (_("--subject-prefix/--rfc and -k are mutually exclusive."));
 +              die(_("--subject-prefix/--rfc and -k are mutually exclusive"));
        rev.preserve_subject = keep_subject;
  
        argc = setup_revisions(argc, argv, &rev, &s_r_opt);
        if (argc > 1)
 -              die (_("unrecognized argument: %s"), argv[1]);
 +              die(_("unrecognized argument: %s"), argv[1]);
  
        if (rev.diffopt.output_format & DIFF_FORMAT_NAME)
                die(_("--name-only does not make sense"));
        if (base_commit || base_auto) {
                struct commit *base = get_base_commit(base_commit, list, nr);
                reset_revision_walk();
 +              clear_object_flags(UNINTERESTING);
                prepare_bases(&bases, base, list, nr);
        }
  
diff --combined builtin/merge.c
index 8f4a5065c209b5b50e02271b48277fff90306338,4c601c40a2efbb459325a3c6f62a1863172d1e75..7a8e3e274f43c6b184defe24d9d4c09a76d63a3e
@@@ -36,6 -36,7 +36,7 @@@
  #include "packfile.h"
  #include "tag.h"
  #include "alias.h"
+ #include "commit-reach.h"
  
  #define DEFAULT_TWOHEAD (1<<0)
  #define DEFAULT_OCTOPUS (1<<1)
@@@ -111,35 -112,6 +112,35 @@@ static int option_parse_message(const s
        return 0;
  }
  
 +static int option_read_message(struct parse_opt_ctx_t *ctx,
 +                             const struct option *opt, int unset)
 +{
 +      struct strbuf *buf = opt->value;
 +      const char *arg;
 +
 +      if (unset)
 +              BUG("-F cannot be negated");
 +
 +      if (ctx->opt) {
 +              arg = ctx->opt;
 +              ctx->opt = NULL;
 +      } else if (ctx->argc > 1) {
 +              ctx->argc--;
 +              arg = *++ctx->argv;
 +      } else
 +              return opterror(opt, "requires a value", 0);
 +
 +      if (buf->len)
 +              strbuf_addch(buf, '\n');
 +      if (ctx->prefix && !is_absolute_path(arg))
 +              arg = prefix_filename(ctx->prefix, arg);
 +      if (strbuf_read_file(buf, arg, 0) < 0)
 +              return error(_("could not read file '%s'"), arg);
 +      have_message = 1;
 +
 +      return 0;
 +}
 +
  static struct strategy *get_strategy(const char *name)
  {
        int i;
@@@ -257,9 -229,6 +258,9 @@@ static struct option builtin_merge_opti
        OPT_CALLBACK('m', "message", &merge_msg, N_("message"),
                N_("merge commit message (for a non-fast-forward merge)"),
                option_parse_message),
 +      { OPTION_LOWLEVEL_CALLBACK, 'F', "file", &merge_msg, N_("path"),
 +              N_("read message from file"), PARSE_OPT_NONEG,
 +              (parse_opt_cb *) option_read_message },
        OPT__VERBOSITY(&verbosity),
        OPT_BOOL(0, "abort", &abort_current_merge,
                N_("abort the current in-progress merge")),
@@@ -725,7 -694,7 +726,7 @@@ static int try_merge_strategy(const cha
                        exit(128);
                if (write_locked_index(&the_index, &lock,
                                       COMMIT_LOCK | SKIP_IF_UNCHANGED))
 -                      die (_("unable to write %s"), get_index_file());
 +                      die(_("unable to write %s"), get_index_file());
                return clean ? 0 : 1;
        } else {
                return try_merge_command(strategy, xopts_nr, xopts,
@@@ -1067,7 -1036,6 +1068,7 @@@ static void handle_fetch_head(struct co
        const char *filename;
        int fd, pos, npos;
        struct strbuf fetch_head_file = STRBUF_INIT;
 +      const unsigned hexsz = the_hash_algo->hexsz;
  
        if (!merge_names)
                merge_names = &fetch_head_file;
                else
                        npos = merge_names->len;
  
 -              if (npos - pos < GIT_SHA1_HEXSZ + 2 ||
 +              if (npos - pos < hexsz + 2 ||
                    get_oid_hex(merge_names->buf + pos, &oid))
                        commit = NULL; /* bad */
 -              else if (memcmp(merge_names->buf + pos + GIT_SHA1_HEXSZ, "\t\t", 2))
 +              else if (memcmp(merge_names->buf + pos + hexsz, "\t\t", 2))
                        continue; /* not-for-merge */
                else {
 -                      char saved = merge_names->buf[pos + GIT_SHA1_HEXSZ];
 -                      merge_names->buf[pos + GIT_SHA1_HEXSZ] = '\0';
 +                      char saved = merge_names->buf[pos + hexsz];
 +                      merge_names->buf[pos + hexsz] = '\0';
                        commit = get_merge_parent(merge_names->buf + pos);
 -                      merge_names->buf[pos + GIT_SHA1_HEXSZ] = saved;
 +                      merge_names->buf[pos + hexsz] = saved;
                }
                if (!commit) {
                        if (ptr)
diff --combined builtin/pull.c
index 681c127a07071c98641972227a28dbe7f77eaf70,15ad01096817c9108e56647c4d52051968979a99..2514bfb9cd6b4288bcda5e1676e3d4e20f10f281
@@@ -22,6 -22,7 +22,7 @@@
  #include "tempfile.h"
  #include "lockfile.h"
  #include "wt-status.h"
+ #include "commit-reach.h"
  
  enum rebase_type {
        REBASE_INVALID = -1,
@@@ -48,11 -49,11 +49,11 @@@ static enum rebase_type parse_config_re
                return REBASE_FALSE;
        else if (v > 0)
                return REBASE_TRUE;
 -      else if (!strcmp(value, "preserve"))
 +      else if (!strcmp(value, "preserve") || !strcmp(value, "p"))
                return REBASE_PRESERVE;
 -      else if (!strcmp(value, "merges"))
 +      else if (!strcmp(value, "merges") || !strcmp(value, "m"))
                return REBASE_MERGES;
 -      else if (!strcmp(value, "interactive"))
 +      else if (!strcmp(value, "interactive") || !strcmp(value, "i"))
                return REBASE_INTERACTIVE;
  
        if (fatal)
@@@ -135,7 -136,7 +136,7 @@@ static struct option pull_options[] = 
        /* Options passed to git-merge or git-rebase */
        OPT_GROUP(N_("Options related to merging")),
        { OPTION_CALLBACK, 'r', "rebase", &opt_rebase,
 -        "false|true|merges|preserve|interactive",
 +        "(false|true|merges|preserve|interactive)",
          N_("incorporate changes by rebasing rather than merging"),
          PARSE_OPT_OPTARG, parse_opt_rebase },
        OPT_PASSTHRU('n', NULL, &opt_diffstat, NULL,
diff --combined builtin/receive-pack.c
index c17ce94e12ee34c5b822b0e09fcd6d7264e759ad,d8467f97343438e10badd28e34ab3e5dc310a028..35a3fcfbd96bbc18a777be5a70e21edb35decffb
@@@ -27,6 -27,7 +27,7 @@@
  #include "packfile.h"
  #include "object-store.h"
  #include "protocol.h"
+ #include "commit-reach.h"
  
  static const char * const receive_pack_usage[] = {
        N_("git receive-pack <git-dir>"),
@@@ -630,6 -631,8 +631,6 @@@ static void prepare_push_cert_sha1(stru
                return;
  
        if (!already_done) {
 -              struct strbuf gpg_output = STRBUF_INIT;
 -              struct strbuf gpg_status = STRBUF_INIT;
                int bogs /* beginning_of_gpg_sig */;
  
                already_done = 1;
                        oidclr(&push_cert_oid);
  
                memset(&sigcheck, '\0', sizeof(sigcheck));
 -              sigcheck.result = 'N';
  
                bogs = parse_signature(push_cert.buf, push_cert.len);
 -              if (verify_signed_buffer(push_cert.buf, bogs,
 -                                       push_cert.buf + bogs, push_cert.len - bogs,
 -                                       &gpg_output, &gpg_status) < 0) {
 -                      ; /* error running gpg */
 -              } else {
 -                      sigcheck.payload = push_cert.buf;
 -                      sigcheck.gpg_output = gpg_output.buf;
 -                      sigcheck.gpg_status = gpg_status.buf;
 -                      parse_gpg_output(&sigcheck);
 -              }
 +              check_signature(push_cert.buf, bogs, push_cert.buf + bogs,
 +                              push_cert.len - bogs, &sigcheck);
  
 -              strbuf_release(&gpg_output);
 -              strbuf_release(&gpg_status);
                nonce_status = check_nonce(push_cert.buf, bogs);
        }
        if (!is_null_oid(&push_cert_oid)) {
diff --combined builtin/remote.c
index 7876db1c20d317e28e4a84880197c6a690bf9ef6,79b032644637956a41ef7c97dc953f4101ff351b..61479bc428c80ef0b976cd46aa8cb60c1d1550f8
@@@ -10,6 -10,7 +10,7 @@@
  #include "refspec.h"
  #include "object-store.h"
  #include "argv-array.h"
+ #include "commit-reach.h"
  
  static const char * const builtin_remote_usage[] = {
        N_("git remote [-v | --verbose]"),
@@@ -168,7 -169,7 +169,7 @@@ static int add(int argc, const char **a
                OPT_STRING_LIST('t', "track", &track, N_("branch"),
                                N_("branch(es) to track")),
                OPT_STRING('m', "master", &master, N_("branch"), N_("master branch")),
 -              { OPTION_CALLBACK, 0, "mirror", &mirror, N_("push|fetch"),
 +              { OPTION_CALLBACK, 0, "mirror", &mirror, "(push|fetch)",
                        N_("set up remote as a mirror to push to or fetch from"),
                        PARSE_OPT_OPTARG | PARSE_OPT_COMP_ARG, parse_mirror_opt },
                OPT_END()
@@@ -566,7 -567,7 +567,7 @@@ static int read_remote_branches(const c
  
        strbuf_addf(&buf, "refs/remotes/%s/", rename->old_name);
        if (starts_with(refname, buf.buf)) {
 -              item = string_list_append(rename->remote_branches, xstrdup(refname));
 +              item = string_list_append(rename->remote_branches, refname);
                symref = resolve_ref_unsafe(refname, RESOLVE_REF_READING,
                                            NULL, &flag);
                if (symref && (flag & REF_ISSYMREF))
@@@ -612,7 -613,7 +613,7 @@@ static int mv(int argc, const char **ar
        struct remote *oldremote, *newremote;
        struct strbuf buf = STRBUF_INIT, buf2 = STRBUF_INIT, buf3 = STRBUF_INIT,
                old_remote_context = STRBUF_INIT;
 -      struct string_list remote_branches = STRING_LIST_INIT_NODUP;
 +      struct string_list remote_branches = STRING_LIST_INIT_DUP;
        struct rename_info rename;
        int i, refspec_updated = 0;
  
                if (create_symref(buf.buf, buf2.buf, buf3.buf))
                        die(_("creating '%s' failed"), buf.buf);
        }
 +      string_list_clear(&remote_branches, 1);
        return 0;
  }
  
diff --combined commit-graph.c
index 8a1bec7b8aa420dd3d4ecadc95dee31029533c07,e9786fa8640ec4ccab570b4f902d1f039ceb08d7..0cad55eec2d5603ccd375e093206f0c971c3524a
@@@ -80,28 -80,28 +80,28 @@@ struct commit_graph *load_commit_graph_
  
        if (graph_size < GRAPH_MIN_SIZE) {
                close(fd);
 -              die("graph file %s is too small", graph_file);
 +              die(_("graph file %s is too small"), graph_file);
        }
        graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
        data = (const unsigned char *)graph_map;
  
        graph_signature = get_be32(data);
        if (graph_signature != GRAPH_SIGNATURE) {
 -              error("graph signature %X does not match signature %X",
 +              error(_("graph signature %X does not match signature %X"),
                      graph_signature, GRAPH_SIGNATURE);
                goto cleanup_fail;
        }
  
        graph_version = *(unsigned char*)(data + 4);
        if (graph_version != GRAPH_VERSION) {
 -              error("graph version %X does not match version %X",
 +              error(_("graph version %X does not match version %X"),
                      graph_version, GRAPH_VERSION);
                goto cleanup_fail;
        }
  
        hash_version = *(unsigned char*)(data + 5);
        if (hash_version != GRAPH_OID_VERSION) {
 -              error("hash version %X does not match version %X",
 +              error(_("hash version %X does not match version %X"),
                      hash_version, GRAPH_OID_VERSION);
                goto cleanup_fail;
        }
                chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
  
                if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
 -                      error("improper chunk offset %08x%08x", (uint32_t)(chunk_offset >> 32),
 +                      error(_("improper chunk offset %08x%08x"), (uint32_t)(chunk_offset >> 32),
                              (uint32_t)chunk_offset);
                        goto cleanup_fail;
                }
                }
  
                if (chunk_repeated) {
 -                      error("chunk id %08x appears multiple times", chunk_id);
 +                      error(_("chunk id %08x appears multiple times"), chunk_id);
                        goto cleanup_fail;
                }
  
@@@ -233,6 -233,24 +233,24 @@@ static int prepare_commit_graph(struct 
        return !!r->objects->commit_graph;
  }
  
+ int generation_numbers_enabled(struct repository *r)
+ {
+       uint32_t first_generation;
+       struct commit_graph *g;
+       if (!prepare_commit_graph(r))
+              return 0;
+       g = r->objects->commit_graph;
+       if (!g->num_commits)
+               return 0;
+       first_generation = get_be32(g->chunk_commit_data +
+                                   g->hash_len + 8) >> 2;
+       return !!first_generation;
+ }
  static void close_commit_graph(void)
  {
        free_commit_graph(the_repository->objects->commit_graph);
@@@ -258,7 -276,7 +276,7 @@@ static struct commit_list **insert_pare
        hashcpy(oid.hash, g->chunk_oid_lookup + g->hash_len * pos);
        c = lookup_commit(the_repository, &oid);
        if (!c)
 -              die("could not find commit %s", oid_to_hex(&oid));
 +              die(_("could not find commit %s"), oid_to_hex(&oid));
        c->graph_pos = pos;
        return &commit_list_insert(c, pptr)->next;
  }
@@@ -562,7 -580,7 +580,7 @@@ static int add_packed_commits(const str
  
        oi.typep = &type;
        if (packed_object_info(the_repository, pack, offset, &oi) < 0)
 -              die("unable to get type of object %s", oid_to_hex(oid));
 +              die(_("unable to get type of object %s"), oid_to_hex(oid));
  
        if (type != OBJ_COMMIT)
                return 0;
@@@ -727,10 -745,10 +745,10 @@@ void write_commit_graph(const char *obj
                        strbuf_addstr(&packname, pack_indexes->items[i].string);
                        p = add_packed_git(packname.buf, packname.len, 1);
                        if (!p)
 -                              die("error adding pack %s", packname.buf);
 +                              die(_("error adding pack %s"), packname.buf);
                        if (open_pack_index(p))
 -                              die("error opening index for %s", packname.buf);
 -                      for_each_object_in_pack(p, add_packed_commits, &oids);
 +                              die(_("error opening index for %s"), packname.buf);
 +                      for_each_object_in_pack(p, add_packed_commits, &oids, 0);
                        close_pack(p);
                }
                strbuf_release(&packname);
diff --combined commit-graph.h
index eea62f8c0ee53b56630a1a2b0c2c716b4cd63670,0de8f88316fd465b4bb08bfb4ac40559d615c161..698f09e2bc876cf9ccfed04022827dc1fdd9bfbd
@@@ -4,7 -4,6 +4,7 @@@
  #include "git-compat-util.h"
  #include "repository.h"
  #include "string-list.h"
 +#include "cache.h"
  
  struct commit;
  
@@@ -52,6 -51,12 +52,12 @@@ struct commit_graph 
  
  struct commit_graph *load_commit_graph_one(const char *graph_file);
  
+ /*
+  * Return 1 if and only if the repository has a commit-graph
+  * file and generation numbers are computed in that file.
+  */
+ int generation_numbers_enabled(struct repository *r);
  void write_commit_graph_reachable(const char *obj_dir, int append);
  void write_commit_graph(const char *obj_dir,
                        struct string_list *pack_indexes,
diff --combined commit-reach.c
index 0000000000000000000000000000000000000000,86715c103c48b2a81e6f5ee2885af399dcf65abb..622eeb313de0e1ce5525054373468823fdeedf58
mode 000000,100644..100644
--- /dev/null
@@@ -1,0 -1,662 +1,665 @@@
 -              if (commit->generation > last_gen)
+ #include "cache.h"
+ #include "commit.h"
+ #include "commit-graph.h"
+ #include "decorate.h"
+ #include "prio-queue.h"
+ #include "tree.h"
+ #include "ref-filter.h"
+ #include "revision.h"
+ #include "tag.h"
+ #include "commit-reach.h"
+ /* Remember to update object flag allocation in object.h */
+ #define REACHABLE       (1u<<15)
+ #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;
++      if (!min_generation)
++              queue.compare = compare_commits_by_commit_date;
++
+       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 (min_generation && 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 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;
+       if (generation_numbers_enabled(the_repository)) {
+               struct commit_list *from_list = NULL;
+               int result;
+               commit_list_insert(commit, &from_list);
+               result = can_all_from_reach(from_list, with_commit, 0);
+               free_commit_list(from_list);
+               return result;
+       } else {
+               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;
+ }
+ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
+ {
+       struct object *o;
+       struct commit *old_commit, *new_commit;
+       struct commit_list *old_commit_list = NULL;
+       /*
+        * Both new_commit and old_commit must be commit-ish and new_commit is descendant of
+        * old_commit.  Otherwise we require --force.
+        */
+       o = deref_tag(the_repository, parse_object(the_repository, old_oid),
+                     NULL, 0);
+       if (!o || o->type != OBJ_COMMIT)
+               return 0;
+       old_commit = (struct commit *) o;
+       o = deref_tag(the_repository, parse_object(the_repository, new_oid),
+                     NULL, 0);
+       if (!o || o->type != OBJ_COMMIT)
+               return 0;
+       new_commit = (struct commit *) o;
+       if (parse_commit(new_commit) < 0)
+               return 0;
+       commit_list_insert(old_commit, &old_commit_list);
+       return is_descendant_of(new_commit, old_commit_list);
+ }
+ /*
+  * Mimicking the real stack, this stack lives on the heap, avoiding stack
+  * overflows.
+  *
+  * At each recursion step, the stack items points to the commits whose
+  * ancestors are to be inspected.
+  */
+ struct contains_stack {
+       int nr, alloc;
+       struct contains_stack_entry {
+               struct commit *commit;
+               struct commit_list *parents;
+       } *contains_stack;
+ };
+ static int in_commit_list(const struct commit_list *want, struct commit *c)
+ {
+       for (; want; want = want->next)
+               if (!oidcmp(&want->item->object.oid, &c->object.oid))
+                       return 1;
+       return 0;
+ }
+ /*
+  * Test whether the candidate is contained in the list.
+  * Do not recurse to find out, though, but return -1 if inconclusive.
+  */
+ static enum contains_result contains_test(struct commit *candidate,
+                                         const struct commit_list *want,
+                                         struct contains_cache *cache,
+                                         uint32_t cutoff)
+ {
+       enum contains_result *cached = contains_cache_at(cache, candidate);
+       /* If we already have the answer cached, return that. */
+       if (*cached)
+               return *cached;
+       /* or are we it? */
+       if (in_commit_list(want, candidate)) {
+               *cached = CONTAINS_YES;
+               return CONTAINS_YES;
+       }
+       /* Otherwise, we don't know; prepare to recurse */
+       parse_commit_or_die(candidate);
+       if (candidate->generation < cutoff)
+               return CONTAINS_NO;
+       return CONTAINS_UNKNOWN;
+ }
+ static void push_to_contains_stack(struct commit *candidate, struct contains_stack *contains_stack)
+ {
+       ALLOC_GROW(contains_stack->contains_stack, contains_stack->nr + 1, contains_stack->alloc);
+       contains_stack->contains_stack[contains_stack->nr].commit = candidate;
+       contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;
+ }
+ static enum contains_result contains_tag_algo(struct commit *candidate,
+                                             const struct commit_list *want,
+                                             struct contains_cache *cache)
+ {
+       struct contains_stack contains_stack = { 0, 0, NULL };
+       enum contains_result result;
+       uint32_t cutoff = GENERATION_NUMBER_INFINITY;
+       const struct commit_list *p;
+       for (p = want; p; p = p->next) {
+               struct commit *c = p->item;
+               load_commit_graph_info(the_repository, c);
+               if (c->generation < cutoff)
+                       cutoff = c->generation;
+       }
+       result = contains_test(candidate, want, cache, cutoff);
+       if (result != CONTAINS_UNKNOWN)
+               return result;
+       push_to_contains_stack(candidate, &contains_stack);
+       while (contains_stack.nr) {
+               struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];
+               struct commit *commit = entry->commit;
+               struct commit_list *parents = entry->parents;
+               if (!parents) {
+                       *contains_cache_at(cache, commit) = CONTAINS_NO;
+                       contains_stack.nr--;
+               }
+               /*
+                * If we just popped the stack, parents->item has been marked,
+                * therefore contains_test will return a meaningful yes/no.
+                */
+               else switch (contains_test(parents->item, want, cache, cutoff)) {
+               case CONTAINS_YES:
+                       *contains_cache_at(cache, commit) = CONTAINS_YES;
+                       contains_stack.nr--;
+                       break;
+               case CONTAINS_NO:
+                       entry->parents = parents->next;
+                       break;
+               case CONTAINS_UNKNOWN:
+                       push_to_contains_stack(parents->item, &contains_stack);
+                       break;
+               }
+       }
+       free(contains_stack.contains_stack);
+       return contains_test(candidate, want, cache, cutoff);
+ }
+ int commit_contains(struct ref_filter *filter, struct commit *commit,
+                   struct commit_list *list, struct contains_cache *cache)
+ {
+       if (filter->with_commit_tag_algo)
+               return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
+       return is_descendant_of(commit, list);
+ }
+ static int compare_commits_by_gen(const void *_a, const void *_b)
+ {
+       const struct commit *a = (const struct commit *)_a;
+       const struct commit *b = (const struct commit *)_b;
+       if (a->generation < b->generation)
+               return -1;
+       if (a->generation > b->generation)
+               return 1;
+       return 0;
+ }
+ int can_all_from_reach_with_flag(struct object_array *from,
+                                unsigned int with_flag,
+                                unsigned int assign_flag,
+                                time_t min_commit_date,
+                                uint32_t min_generation)
+ {
+       struct commit **list = NULL;
+       int i;
+       int result = 1;
+       ALLOC_ARRAY(list, from->nr);
+       for (i = 0; i < from->nr; i++) {
+               list[i] = (struct commit *)from->objects[i].item;
+               if (parse_commit(list[i]) ||
+                   list[i]->generation < min_generation)
+                       return 0;
+       }
+       QSORT(list, from->nr, compare_commits_by_gen);
+       for (i = 0; i < from->nr; i++) {
+               /* DFS from list[i] */
+               struct commit_list *stack = NULL;
+               list[i]->object.flags |= assign_flag;
+               commit_list_insert(list[i], &stack);
+               while (stack) {
+                       struct commit_list *parent;
+                       if (stack->item->object.flags & with_flag) {
+                               pop_commit(&stack);
+                               continue;
+                       }
+                       for (parent = stack->item->parents; parent; parent = parent->next) {
+                               if (parent->item->object.flags & (with_flag | RESULT))
+                                       stack->item->object.flags |= RESULT;
+                               if (!(parent->item->object.flags & assign_flag)) {
+                                       parent->item->object.flags |= assign_flag;
+                                       if (parse_commit(parent->item) ||
+                                           parent->item->date < min_commit_date ||
+                                           parent->item->generation < min_generation)
+                                               continue;
+                                       commit_list_insert(parent->item, &stack);
+                                       break;
+                               }
+                       }
+                       if (!parent)
+                               pop_commit(&stack);
+               }
+               if (!(list[i]->object.flags & (with_flag | RESULT))) {
+                       result = 0;
+                       goto cleanup;
+               }
+       }
+ cleanup:
+       for (i = 0; i < from->nr; i++) {
+               clear_commit_marks(list[i], RESULT);
+               clear_commit_marks(list[i], assign_flag);
+       }
+       return result;
+ }
+ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
+                      int cutoff_by_min_date)
+ {
+       struct object_array from_objs = OBJECT_ARRAY_INIT;
+       time_t min_commit_date = cutoff_by_min_date ? from->item->date : 0;
+       struct commit_list *from_iter = from, *to_iter = to;
+       int result;
+       uint32_t min_generation = GENERATION_NUMBER_INFINITY;
+       while (from_iter) {
+               add_object_array(&from_iter->item->object, NULL, &from_objs);
+               if (!parse_commit(from_iter->item)) {
+                       if (from_iter->item->date < min_commit_date)
+                               min_commit_date = from_iter->item->date;
+                       if (from_iter->item->generation < min_generation)
+                               min_generation = from_iter->item->generation;
+               }
+               from_iter = from_iter->next;
+       }
+       while (to_iter) {
+               if (!parse_commit(to_iter->item)) {
+                       if (to_iter->item->date < min_commit_date)
+                               min_commit_date = to_iter->item->date;
+                       if (to_iter->item->generation < min_generation)
+                               min_generation = to_iter->item->generation;
+               }
+               to_iter->item->object.flags |= PARENT2;
+               to_iter = to_iter->next;
+       }
+       result = can_all_from_reach_with_flag(&from_objs, PARENT2, PARENT1,
+                                             min_commit_date, min_generation);
+       while (from) {
+               clear_commit_marks(from->item, PARENT1);
+               from = from->next;
+       }
+       while (to) {
+               clear_commit_marks(to->item, PARENT2);
+               to = to->next;
+       }
+       object_array_clear(&from_objs);
+       return result;
+ }
diff --combined commit.c
index 449c1f4920cff631f5cf2479772c350c9b8b7325,32d1234bd745faa64a969e73bb2c24d3527211f6..5781f9bc675722041b9ffb0471f4c959fba48924
+++ b/commit.c
@@@ -388,8 -388,8 +388,8 @@@ int parse_commit_buffer(struct reposito
        struct object_id parent;
        struct commit_list **pptr;
        struct commit_graft *graft;
 -      const int tree_entry_len = GIT_SHA1_HEXSZ + 5;
 -      const int parent_entry_len = GIT_SHA1_HEXSZ + 7;
 +      const int tree_entry_len = the_hash_algo->hexsz + 5;
 +      const int parent_entry_len = the_hash_algo->hexsz + 7;
  
        if (item->object.parsed)
                return 0;
@@@ -656,7 -656,7 +656,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,367 -843,6 +843,6 @@@ 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;
-       if (!min_generation)
-               queue.compare = compare_commits_by_commit_date;
-       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 (min_generation && 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 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;
  
diff --combined fast-import.c
index f8c3acd3b5577caa24c13402ea2b6f733e41aec5,4a93df3839dcb4565810538d5a3a48f74eb51f14..af6514fdea9959b26355b328221ceb67eaf1432f
@@@ -171,6 -171,7 +171,7 @@@ Format of STDIN stream
  #include "packfile.h"
  #include "object-store.h"
  #include "mem-pool.h"
+ #include "commit-reach.h"
  
  #define PACK_ID_BITS 16
  #define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)
@@@ -1068,7 -1069,7 +1069,7 @@@ static int store_object
                duplicate_count_by_type[type]++;
                return 1;
        } else if (find_sha1_pack(oid.hash,
 -                                get_packed_git(the_repository))) {
 +                                get_all_packs(the_repository))) {
                e->type = type;
                e->pack_id = MAX_PACK_ID;
                e->idx.offset = 1; /* just not zero! */
                return 1;
        }
  
 -      if (last && last->data.buf && last->depth < max_depth
 +      if (last && last->data.len && last->data.buf && last->depth < max_depth
                && dat->len > the_hash_algo->rawsz) {
  
                delta_count_attempts_by_type[type]++;
@@@ -1266,7 -1267,7 +1267,7 @@@ static void stream_blob(uintmax_t len, 
                truncate_pack(&checkpoint);
  
        } else if (find_sha1_pack(oid.hash,
 -                                get_packed_git(the_repository))) {
 +                                get_all_packs(the_repository))) {
                e->type = OBJ_BLOB;
                e->pack_id = MAX_PACK_ID;
                e->idx.offset = 1; /* just not zero! */
diff --combined merge-recursive.c
index e5243dbc542d786a645a9c038c855a6ca30acaba,8155dee9a98cbea8b1045d0436e0a170b0757555..d9d78ec3832c54cae373e9fb688d5153e66830e2
@@@ -27,6 -27,7 +27,7 @@@
  #include "dir.h"
  #include "submodule.h"
  #include "revision.h"
+ #include "commit-reach.h"
  
  struct path_hashmap_entry {
        struct hashmap_entry e;
@@@ -184,7 -185,7 +185,7 @@@ static int oid_eq(const struct object_i
  
  enum rename_type {
        RENAME_NORMAL = 0,
 -      RENAME_DIR,
 +      RENAME_VIA_DIR,
        RENAME_DELETE,
        RENAME_ONE_FILE_TO_ONE,
        RENAME_ONE_FILE_TO_TWO,
@@@ -314,13 -315,13 +315,13 @@@ static void output_commit_title(struct 
  }
  
  static int add_cacheinfo(struct merge_options *o,
 -              unsigned int mode, const struct object_id *oid,
 -              const char *path, int stage, int refresh, int options)
 +                       unsigned int mode, const struct object_id *oid,
 +                       const char *path, int stage, int refresh, int options)
  {
        struct cache_entry *ce;
        int ret;
  
 -      ce = make_cache_entry(mode, oid ? oid->hash : null_sha1, path, stage, 0);
 +      ce = make_cache_entry(&the_index, mode, oid ? oid : &null_oid, path, stage, 0);
        if (!ce)
                return err(o, _("add_cacheinfo failed for path '%s'; merge aborting."), path);
  
        if (refresh) {
                struct cache_entry *nce;
  
 -              nce = refresh_cache_entry(ce, CE_MATCH_REFRESH | CE_MATCH_IGNORE_MISSING);
 +              nce = refresh_cache_entry(&the_index, ce, CE_MATCH_REFRESH | CE_MATCH_IGNORE_MISSING);
                if (!nce)
                        return err(o, _("add_cacheinfo failed to refresh for path '%s'; merge aborting."), path);
                if (nce != ce)
@@@ -422,8 -423,8 +423,8 @@@ struct tree *write_tree_from_memory(str
  }
  
  static int save_files_dirs(const struct object_id *oid,
 -              struct strbuf *base, const char *path,
 -              unsigned int mode, int stage, void *context)
 +                         struct strbuf *base, const char *path,
 +                         unsigned int mode, int stage, void *context)
  {
        struct path_hashmap_entry *entry;
        int baselen = base->len;
@@@ -544,7 -545,7 +545,7 @@@ static void record_df_conflict_files(st
                                     struct string_list *entries)
  {
        /* If there is a D/F conflict and the file for such a conflict
 -       * currently exist in the working tree, we want to allow it to be
 +       * currently exists in the working tree, we want to allow it to be
         * removed to make room for the corresponding directory if needed.
         * The files underneath the directories of such D/F conflicts will
         * be processed before the corresponding file involved in the D/F
@@@ -918,7 -919,7 +919,7 @@@ static int make_room_for_path(struct me
         */
        if (would_lose_untracked(path))
                return err(o, _("refusing to lose untracked file at '%s'"),
 -                           path);
 +                         path);
  
        /* Successful unlink is good.. */
        if (!unlink(path))
@@@ -966,7 -967,7 +967,7 @@@ static int update_file_flags(struct mer
                }
                if (S_ISREG(mode)) {
                        struct strbuf strbuf = STRBUF_INIT;
 -                      if (convert_to_working_tree(path, buf, size, &strbuf)) {
 +                      if (convert_to_working_tree(&the_index, path, buf, size, &strbuf)) {
                                free(buf);
                                size = strbuf.len;
                                buf = strbuf_detach(&strbuf, NULL);
                        unlink(path);
                        if (symlink(lnk, path))
                                ret = err(o, _("failed to symlink '%s': %s"),
 -                                      path, strerror(errno));
 +                                        path, strerror(errno));
                        free(lnk);
                } else
                        ret = err(o,
                                  _("do not know what to do with %06o %s '%s'"),
                                  mode, oid_to_hex(oid), path);
 - free_buf:
 +      free_buf:
                free(buf);
        }
 - update_index:
 +update_index:
        if (!ret && update_cache)
                if (add_cacheinfo(o, mode, oid, path, 0, update_wd,
                                  ADD_CACHE_OK_TO_ADD))
@@@ -1095,7 -1096,7 +1096,7 @@@ static int merge_3way(struct merge_opti
  }
  
  static int find_first_merges(struct object_array *result, const char *path,
 -              struct commit *a, struct commit *b)
 +                           struct commit *a, struct commit *b)
  {
        int i, j;
        struct object_array merges = OBJECT_ARRAY_INIT;
  
        /* get all revisions that merge commit a */
        xsnprintf(merged_revision, sizeof(merged_revision), "^%s",
 -                      oid_to_hex(&a->object.oid));
 +                oid_to_hex(&a->object.oid));
        init_revisions(&revs, NULL);
        rev_opts.submodule = path;
        /* FIXME: can't handle linked worktrees in submodules yet */
@@@ -1255,12 -1256,12 +1256,12 @@@ static int merge_submodule(struct merge
                output(o, 2, _("Found a possible merge resolution for the submodule:\n"));
                print_commit((struct commit *) merges.objects[0].item);
                output(o, 2, _(
 -                      "If this is correct simply add it to the index "
 -                      "for example\n"
 -                      "by using:\n\n"
 -                      "  git update-index --cacheinfo 160000 %s \"%s\"\n\n"
 -                      "which will accept this suggestion.\n"),
 -                      oid_to_hex(&merges.objects[0].item->oid), path);
 +                     "If this is correct simply add it to the index "
 +                     "for example\n"
 +                     "by using:\n\n"
 +                     "  git update-index --cacheinfo 160000 %s \"%s\"\n\n"
 +                     "which will accept this suggestion.\n"),
 +                     oid_to_hex(&merges.objects[0].item->oid), path);
                break;
  
        default:
@@@ -1337,10 -1338,10 +1338,10 @@@ static int merge_file_1(struct merge_op
                        result->clean = (merge_status == 0);
                } else if (S_ISGITLINK(a->mode)) {
                        result->clean = merge_submodule(o, &result->oid,
 -                                                     one->path,
 -                                                     &one->oid,
 -                                                     &a->oid,
 -                                                     &b->oid);
 +                                                      one->path,
 +                                                      &one->oid,
 +                                                      &a->oid,
 +                                                      &b->oid);
                } else if (S_ISLNK(a->mode)) {
                        switch (o->recursive_variant) {
                        case MERGE_RECURSIVE_NORMAL:
@@@ -1415,17 -1416,11 +1416,17 @@@ static int merge_file_one(struct merge_
        return merge_file_1(o, &one, &a, &b, path, branch1, branch2, mfi);
  }
  
 -static int conflict_rename_dir(struct merge_options *o,
 -                             struct diff_filepair *pair,
 -                             const char *rename_branch,
 -                             const char *other_branch)
 +static int handle_rename_via_dir(struct merge_options *o,
 +                               struct diff_filepair *pair,
 +                               const char *rename_branch,
 +                               const char *other_branch)
  {
 +      /*
 +       * Handle file adds that need to be renamed due to directory rename
 +       * detection.  This differs from handle_rename_normal, because
 +       * there is no content merge to do; just move the file into the
 +       * desired final location.
 +       */
        const struct diff_filespec *dest = pair->two;
  
        if (!o->call_depth && would_lose_untracked(dest->path)) {
  }
  
  static int handle_change_delete(struct merge_options *o,
 -                               const char *path, const char *old_path,
 -                               const struct object_id *o_oid, int o_mode,
 -                               const struct object_id *changed_oid,
 -                               int changed_mode,
 -                               const char *change_branch,
 -                               const char *delete_branch,
 -                               const char *change, const char *change_past)
 +                              const char *path, const char *old_path,
 +                              const struct object_id *o_oid, int o_mode,
 +                              const struct object_id *changed_oid,
 +                              int changed_mode,
 +                              const char *change_branch,
 +                              const char *delete_branch,
 +                              const char *change, const char *change_past)
  {
        char *alt_path = NULL;
        const char *update_path = path;
                if (!ret)
                        ret = update_file(o, 0, o_oid, o_mode, update_path);
        } else {
 +              /*
 +               * Despite the four nearly duplicate messages and argument
 +               * lists below and the ugliness of the nested if-statements,
 +               * having complete messages makes the job easier for
 +               * translators.
 +               *
 +               * The slight variance among the cases is due to the fact
 +               * that:
 +               *   1) directory/file conflicts (in effect if
 +               *      !alt_path) could cause us to need to write the
 +               *      file to a different path.
 +               *   2) renames (in effect if !old_path) could mean that
 +               *      there are two names for the path that the user
 +               *      may know the file by.
 +               */
                if (!alt_path) {
                        if (!old_path) {
                                output(o, 1, _("CONFLICT (%s/delete): %s deleted in %s "
        return ret;
  }
  
 -static int conflict_rename_delete(struct merge_options *o,
 -                                 struct diff_filepair *pair,
 -                                 const char *rename_branch,
 -                                 const char *delete_branch)
 +static int handle_rename_delete(struct merge_options *o,
 +                              struct diff_filepair *pair,
 +                              const char *rename_branch,
 +                              const char *delete_branch)
  {
        const struct diff_filespec *orig = pair->one;
        const struct diff_filespec *dest = pair->two;
@@@ -1640,8 -1620,8 +1641,8 @@@ static int handle_file(struct merge_opt
        return ret;
  }
  
 -static int conflict_rename_rename_1to2(struct merge_options *o,
 -                                      struct rename_conflict_info *ci)
 +static int handle_rename_rename_1to2(struct merge_options *o,
 +                                   struct rename_conflict_info *ci)
  {
        /* One file was renamed in both branches, but to different names. */
        struct diff_filespec *one = ci->pair1->one;
        return 0;
  }
  
 -static int conflict_rename_rename_2to1(struct merge_options *o,
 -                                      struct rename_conflict_info *ci)
 +static int handle_rename_rename_2to1(struct merge_options *o,
 +                                   struct rename_conflict_info *ci)
  {
        /* Two files, a & b, were renamed to the same thing, c. */
        struct diff_filespec *a = ci->pair1->one;
@@@ -2445,7 -2425,7 +2446,7 @@@ static void apply_directory_rename_modi
         * "NOTE" in update_stages(), doing so will modify the current
         * in-memory index which will break calls to would_lose_untracked()
         * that we need to make.  Instead, we need to just make sure that
 -       * the various conflict_rename_*() functions update the index
 +       * the various handle_rename_*() functions update the index
         * explicitly rather than relying on unpack_trees() to have done it.
         */
        get_tree_entry(&tree->object.oid,
@@@ -2718,7 -2698,7 +2719,7 @@@ static int process_renames(struct merge
  
                        if (oid_eq(&src_other.oid, &null_oid) &&
                            ren1->add_turned_into_rename) {
 -                              setup_rename_conflict_info(RENAME_DIR,
 +                              setup_rename_conflict_info(RENAME_VIA_DIR,
                                                           ren1->pair,
                                                           NULL,
                                                           branch1,
@@@ -2849,12 -2829,12 +2850,12 @@@ static void initial_cleanup_rename(stru
        free(pairs);
  }
  
 -static int handle_renames(struct merge_options *o,
 -                        struct tree *common,
 -                        struct tree *head,
 -                        struct tree *merge,
 -                        struct string_list *entries,
 -                        struct rename_info *ri)
 +static int detect_and_process_renames(struct merge_options *o,
 +                                    struct tree *common,
 +                                    struct tree *head,
 +                                    struct tree *merge,
 +                                    struct string_list *entries,
 +                                    struct rename_info *ri)
  {
        struct diff_queue_struct *head_pairs, *merge_pairs;
        struct hashmap *dir_re_head, *dir_re_merge;
        head_pairs = get_diffpairs(o, common, head);
        merge_pairs = get_diffpairs(o, common, merge);
  
 -      dir_re_head = get_directory_renames(head_pairs, head);
 -      dir_re_merge = get_directory_renames(merge_pairs, merge);
 +      if (o->detect_directory_renames) {
 +              dir_re_head = get_directory_renames(head_pairs, head);
 +              dir_re_merge = get_directory_renames(merge_pairs, merge);
  
 -      handle_directory_level_conflicts(o,
 -                                       dir_re_head, head,
 -                                       dir_re_merge, merge);
 +              handle_directory_level_conflicts(o,
 +                                               dir_re_head, head,
 +                                               dir_re_merge, merge);
 +      } else {
 +              dir_re_head  = xmalloc(sizeof(*dir_re_head));
 +              dir_re_merge = xmalloc(sizeof(*dir_re_merge));
 +              dir_rename_init(dir_re_head);
 +              dir_rename_init(dir_re_merge);
 +      }
  
        ri->head_renames  = get_renames(o, head_pairs,
                                        dir_re_merge, dir_re_head, head,
@@@ -2937,8 -2910,7 +2938,8 @@@ static struct object_id *stage_oid(cons
  }
  
  static int read_oid_strbuf(struct merge_options *o,
 -      const struct object_id *oid, struct strbuf *dst)
 +                         const struct object_id *oid,
 +                         struct strbuf *dst)
  {
        void *buf;
        enum object_type type;
@@@ -2991,10 -2963,10 +2992,10 @@@ error_return
  }
  
  static int handle_modify_delete(struct merge_options *o,
 -                               const char *path,
 -                               struct object_id *o_oid, int o_mode,
 -                               struct object_id *a_oid, int a_mode,
 -                               struct object_id *b_oid, int b_mode)
 +                              const char *path,
 +                              struct object_id *o_oid, int o_mode,
 +                              struct object_id *a_oid, int a_mode,
 +                              struct object_id *b_oid, int b_mode)
  {
        const char *modify_branch, *delete_branch;
        struct object_id *changed_oid;
@@@ -3077,26 -3049,10 +3078,26 @@@ static int merge_content(struct merge_o
        if (mfi.clean &&
            was_tracked_and_matches(o, path, &mfi.oid, mfi.mode) &&
            !df_conflict_remains) {
 +              int pos;
 +              struct cache_entry *ce;
 +
                output(o, 3, _("Skipped %s (merged same as existing)"), path);
                if (add_cacheinfo(o, mfi.mode, &mfi.oid, path,
                                  0, (!o->call_depth && !is_dirty), 0))
                        return -1;
 +              /*
 +               * However, add_cacheinfo() will delete the old cache entry
 +               * and add a new one.  We need to copy over any skip_worktree
 +               * flag to avoid making the file appear as if it were
 +               * deleted by the user.
 +               */
 +              pos = index_name_pos(&o->orig_index, path, strlen(path));
 +              ce = o->orig_index.cache[pos];
 +              if (ce_skip_worktree(ce)) {
 +                      pos = index_name_pos(&the_index, path, strlen(path));
 +                      ce = the_index.cache[pos];
 +                      ce->ce_flags |= CE_SKIP_WORKTREE;
 +              }
                return mfi.clean;
        }
  
        return !is_dirty && mfi.clean;
  }
  
 -static int conflict_rename_normal(struct merge_options *o,
 -                                const char *path,
 -                                struct object_id *o_oid, unsigned int o_mode,
 -                                struct object_id *a_oid, unsigned int a_mode,
 -                                struct object_id *b_oid, unsigned int b_mode,
 -                                struct rename_conflict_info *ci)
 +static int handle_rename_normal(struct merge_options *o,
 +                              const char *path,
 +                              struct object_id *o_oid, unsigned int o_mode,
 +                              struct object_id *a_oid, unsigned int a_mode,
 +                              struct object_id *b_oid, unsigned int b_mode,
 +                              struct rename_conflict_info *ci)
  {
        /* Merge the content and write it out */
        return merge_content(o, path, was_dirty(o, path),
@@@ -3180,37 -3136,37 +3181,37 @@@ static int process_entry(struct merge_o
                switch (conflict_info->rename_type) {
                case RENAME_NORMAL:
                case RENAME_ONE_FILE_TO_ONE:
 -                      clean_merge = conflict_rename_normal(o,
 -                                                           path,
 -                                                           o_oid, o_mode,
 -                                                           a_oid, a_mode,
 -                                                           b_oid, b_mode,
 -                                                           conflict_info);
 +                      clean_merge = handle_rename_normal(o,
 +                                                         path,
 +                                                         o_oid, o_mode,
 +                                                         a_oid, a_mode,
 +                                                         b_oid, b_mode,
 +                                                         conflict_info);
                        break;
 -              case RENAME_DIR:
 +              case RENAME_VIA_DIR:
                        clean_merge = 1;
 -                      if (conflict_rename_dir(o,
 -                                              conflict_info->pair1,
 -                                              conflict_info->branch1,
 -                                              conflict_info->branch2))
 +                      if (handle_rename_via_dir(o,
 +                                                conflict_info->pair1,
 +                                                conflict_info->branch1,
 +                                                conflict_info->branch2))
                                clean_merge = -1;
                        break;
                case RENAME_DELETE:
                        clean_merge = 0;
 -                      if (conflict_rename_delete(o,
 -                                                 conflict_info->pair1,
 -                                                 conflict_info->branch1,
 -                                                 conflict_info->branch2))
 +                      if (handle_rename_delete(o,
 +                                               conflict_info->pair1,
 +                                               conflict_info->branch1,
 +                                               conflict_info->branch2))
                                clean_merge = -1;
                        break;
                case RENAME_ONE_FILE_TO_TWO:
                        clean_merge = 0;
 -                      if (conflict_rename_rename_1to2(o, conflict_info))
 +                      if (handle_rename_rename_1to2(o, conflict_info))
                                clean_merge = -1;
                        break;
                case RENAME_TWO_FILES_TO_ONE:
                        clean_merge = 0;
 -                      if (conflict_rename_rename_2to1(o, conflict_info))
 +                      if (handle_rename_rename_2to1(o, conflict_info))
                                clean_merge = -1;
                        break;
                default:
@@@ -3304,13 -3260,6 +3305,13 @@@ int merge_trees(struct merge_options *o
                struct tree **result)
  {
        int code, clean;
 +      struct strbuf sb = STRBUF_INIT;
 +
 +      if (!o->call_depth && index_has_changes(&the_index, head, &sb)) {
 +              err(o, _("Your local changes to the following files would be overwritten by merge:\n  %s"),
 +                  sb.buf);
 +              return -1;
 +      }
  
        if (o->subtree_shift) {
                merge = shift_tree_object(head, merge, o->subtree_shift);
        }
  
        if (oid_eq(&common->object.oid, &merge->object.oid)) {
 -              struct strbuf sb = STRBUF_INIT;
 -
 -              if (!o->call_depth && index_has_changes(&sb)) {
 -                      err(o, _("Dirty index: cannot merge (dirty: %s)"),
 -                          sb.buf);
 -                      return 0;
 -              }
                output(o, 0, _("Already up to date!"));
                *result = head;
                return 1;
                get_files_dirs(o, merge);
  
                entries = get_unmerged();
 -              clean = handle_renames(o, common, head, merge, entries,
 -                                     &re_info);
 +              clean = detect_and_process_renames(o, common, head, merge,
 +                                                 entries, &re_info);
                record_df_conflict_files(o, entries);
                if (clean < 0)
                        goto cleanup;
                                    entries->items[i].string);
                }
  
 -cleanup:
 +      cleanup:
                final_cleanup_renames(&re_info);
  
                string_list_clear(entries, 1);
@@@ -3545,14 -3501,14 +3546,14 @@@ int merge_recursive_generic(struct merg
                        struct commit *base;
                        if (!(base = get_ref(base_list[i], oid_to_hex(base_list[i]))))
                                return err(o, _("Could not parse object '%s'"),
 -                                      oid_to_hex(base_list[i]));
 +                                         oid_to_hex(base_list[i]));
                        commit_list_insert(base, &ca);
                }
        }
  
        hold_locked_index(&lock, LOCK_DIE_ON_ERROR);
        clean = merge_recursive(o, head_commit, next_commit, ca,
 -                      result);
 +                              result);
        if (clean < 0) {
                rollback_lock_file(&lock);
                return clean;
@@@ -3593,7 -3549,6 +3594,7 @@@ void init_merge_options(struct merge_op
        o->renormalize = 0;
        o->diff_detect_rename = -1;
        o->merge_detect_rename = -1;
 +      o->detect_directory_renames = 1;
        merge_recursive_config(o);
        merge_verbosity = getenv("GIT_MERGE_VERBOSITY");
        if (merge_verbosity)
diff --combined object.h
index 6e28fdd0b426a3e276001e674675cf386f7d86c1,b132944c51d968a2f18562c0b676424eddeec6cc..0feb90ae613be04d56ac091307c9b2be88724e42
+++ b/object.h
@@@ -1,8 -1,6 +1,8 @@@
  #ifndef OBJECT_H
  #define OBJECT_H
  
 +#include "cache.h"
 +
  struct buffer_slab;
  
  struct parsed_object_pool {
@@@ -59,16 -57,15 +59,16 @@@ struct object_array 
  
  /*
   * object flag allocation:
 - * revision.h:               0---------10                                26
 - * fetch-pack.c:             0----5
 + * revision.h:               0---------10                              2526
 + * fetch-pack.c:             01
 + * negotiator/default.c:       2--5
   * walker.c:                 0-2
-  * upload-pack.c:                4       11----------------19
+  * upload-pack.c:                4       11-----14  16-----19
   * builtin/blame.c:                        12-13
   * bisect.c:                                        16
   * bundle.c:                                        16
   * http-push.c:                                     16-----19
-  * commit.c:                                        16-----19
+  * commit-reach.c:                                15-------19
   * sha1-name.c:                                              20
   * list-objects-filter.c:                                      21
   * builtin/fsck.c:           0--3
diff --combined pack-bitmap-write.c
index d977e9bacb19ed766dd0a501b6fbcae800bb4ae0,55bcab907c0ecf22d38ba512fe793c3d7f373ced..fc82f37a02772244ee93aee41bef9238075c07ba
@@@ -11,6 -11,7 +11,7 @@@
  #include "pack-bitmap.h"
  #include "sha1-lookup.h"
  #include "pack-objects.h"
+ #include "commit-reach.h"
  
  struct bitmapped_commit {
        struct commit *commit;
@@@ -361,17 -362,11 +362,17 @@@ static int date_compare(const void *_a
  
  void bitmap_writer_reuse_bitmaps(struct packing_data *to_pack)
  {
 -      if (prepare_bitmap_git() < 0)
 +      struct bitmap_index *bitmap_git;
 +      if (!(bitmap_git = prepare_bitmap_git()))
                return;
  
        writer.reused = kh_init_sha1();
 -      rebuild_existing_bitmaps(to_pack, writer.reused, writer.show_progress);
 +      rebuild_existing_bitmaps(bitmap_git, to_pack, writer.reused,
 +                               writer.show_progress);
 +      /*
 +       * NEEDSWORK: rebuild_existing_bitmaps() makes writer.reused reference
 +       * some bitmaps in bitmap_git, so we can't free the latter.
 +       */
  }
  
  static struct ewah_bitmap *find_reused_bitmap(const unsigned char *sha1)
diff --combined ref-filter.c
index 0bccfceff2ae31200019838d9f2b67e13e32ef6f,495e830fa58d268beae449843799235b2cc21d66..9bacd32f0a0a72854c81d0d114520efb554c04a8
@@@ -19,6 -19,7 +19,7 @@@
  #include "wt-status.h"
  #include "commit-slab.h"
  #include "commit-graph.h"
+ #include "commit-reach.h"
  
  static struct ref_msg {
        const char *gone;
@@@ -43,7 -44,6 +44,7 @@@ void setup_ref_filter_porcelain_msg(voi
  
  typedef enum { FIELD_STR, FIELD_ULONG, FIELD_TIME } cmp_type;
  typedef enum { COMPARE_EQUAL, COMPARE_UNEQUAL, COMPARE_NONE } cmp_status;
 +typedef enum { SOURCE_NONE = 0, SOURCE_OBJ, SOURCE_OTHER } info_source;
  
  struct align {
        align_type position;
@@@ -63,17 -63,6 +64,17 @@@ struct refname_atom 
        int lstrip, rstrip;
  };
  
 +static struct expand_data {
 +      struct object_id oid;
 +      enum object_type type;
 +      unsigned long size;
 +      off_t disk_size;
 +      struct object_id delta_base_oid;
 +      void *content;
 +
 +      struct object_info info;
 +} oi, oi_deref;
 +
  /*
   * An atom is a valid field atom listed below, possibly prefixed with
   * a "*" to denote deref_tag().
@@@ -87,7 -76,6 +88,7 @@@
  static struct used_atom {
        const char *name;
        cmp_type type;
 +      info_source source;
        union {
                char color[COLOR_MAXLEN];
                struct align align;
@@@ -215,30 -203,6 +216,30 @@@ static int remote_ref_atom_parser(cons
        return 0;
  }
  
 +static int objecttype_atom_parser(const struct ref_format *format, struct used_atom *atom,
 +                                const char *arg, struct strbuf *err)
 +{
 +      if (arg)
 +              return strbuf_addf_ret(err, -1, _("%%(objecttype) does not take arguments"));
 +      if (*atom->name == '*')
 +              oi_deref.info.typep = &oi_deref.type;
 +      else
 +              oi.info.typep = &oi.type;
 +      return 0;
 +}
 +
 +static int objectsize_atom_parser(const struct ref_format *format, struct used_atom *atom,
 +                                const char *arg, struct strbuf *err)
 +{
 +      if (arg)
 +              return strbuf_addf_ret(err, -1, _("%%(objectsize) does not take arguments"));
 +      if (*atom->name == '*')
 +              oi_deref.info.sizep = &oi_deref.size;
 +      else
 +              oi.info.sizep = &oi.size;
 +      return 0;
 +}
 +
  static int body_atom_parser(const struct ref_format *format, struct used_atom *atom,
                            const char *arg, struct strbuf *err)
  {
@@@ -419,50 -383,49 +420,50 @@@ static int head_atom_parser(const struc
  
  static struct {
        const char *name;
 +      info_source source;
        cmp_type cmp_type;
        int (*parser)(const struct ref_format *format, struct used_atom *atom,
                      const char *arg, struct strbuf *err);
  } valid_atom[] = {
 -      { "refname" , FIELD_STR, refname_atom_parser },
 -      { "objecttype" },
 -      { "objectsize", FIELD_ULONG },
 -      { "objectname", FIELD_STR, objectname_atom_parser },
 -      { "tree" },
 -      { "parent" },
 -      { "numparent", FIELD_ULONG },
 -      { "object" },
 -      { "type" },
 -      { "tag" },
 -      { "author" },
 -      { "authorname" },
 -      { "authoremail" },
 -      { "authordate", FIELD_TIME },
 -      { "committer" },
 -      { "committername" },
 -      { "committeremail" },
 -      { "committerdate", FIELD_TIME },
 -      { "tagger" },
 -      { "taggername" },
 -      { "taggeremail" },
 -      { "taggerdate", FIELD_TIME },
 -      { "creator" },
 -      { "creatordate", FIELD_TIME },
 -      { "subject", FIELD_STR, subject_atom_parser },
 -      { "body", FIELD_STR, body_atom_parser },
 -      { "trailers", FIELD_STR, trailers_atom_parser },
 -      { "contents", FIELD_STR, contents_atom_parser },
 -      { "upstream", FIELD_STR, remote_ref_atom_parser },
 -      { "push", FIELD_STR, remote_ref_atom_parser },
 -      { "symref", FIELD_STR, refname_atom_parser },
 -      { "flag" },
 -      { "HEAD", FIELD_STR, head_atom_parser },
 -      { "color", FIELD_STR, color_atom_parser },
 -      { "align", FIELD_STR, align_atom_parser },
 -      { "end" },
 -      { "if", FIELD_STR, if_atom_parser },
 -      { "then" },
 -      { "else" },
 +      { "refname", SOURCE_NONE, FIELD_STR, refname_atom_parser },
 +      { "objecttype", SOURCE_OTHER, FIELD_STR, objecttype_atom_parser },
 +      { "objectsize", SOURCE_OTHER, FIELD_ULONG, objectsize_atom_parser },
 +      { "objectname", SOURCE_OTHER, FIELD_STR, objectname_atom_parser },
 +      { "tree", SOURCE_OBJ },
 +      { "parent", SOURCE_OBJ },
 +      { "numparent", SOURCE_OBJ, FIELD_ULONG },
 +      { "object", SOURCE_OBJ },
 +      { "type", SOURCE_OBJ },
 +      { "tag", SOURCE_OBJ },
 +      { "author", SOURCE_OBJ },
 +      { "authorname", SOURCE_OBJ },
 +      { "authoremail", SOURCE_OBJ },
 +      { "authordate", SOURCE_OBJ, FIELD_TIME },
 +      { "committer", SOURCE_OBJ },
 +      { "committername", SOURCE_OBJ },
 +      { "committeremail", SOURCE_OBJ },
 +      { "committerdate", SOURCE_OBJ, FIELD_TIME },
 +      { "tagger", SOURCE_OBJ },
 +      { "taggername", SOURCE_OBJ },
 +      { "taggeremail", SOURCE_OBJ },
 +      { "taggerdate", SOURCE_OBJ, FIELD_TIME },
 +      { "creator", SOURCE_OBJ },
 +      { "creatordate", SOURCE_OBJ, FIELD_TIME },
 +      { "subject", SOURCE_OBJ, FIELD_STR, subject_atom_parser },
 +      { "body", SOURCE_OBJ, FIELD_STR, body_atom_parser },
 +      { "trailers", SOURCE_OBJ, FIELD_STR, trailers_atom_parser },
 +      { "contents", SOURCE_OBJ, FIELD_STR, contents_atom_parser },
 +      { "upstream", SOURCE_NONE, FIELD_STR, remote_ref_atom_parser },
 +      { "push", SOURCE_NONE, FIELD_STR, remote_ref_atom_parser },
 +      { "symref", SOURCE_NONE, FIELD_STR, refname_atom_parser },
 +      { "flag", SOURCE_NONE },
 +      { "HEAD", SOURCE_NONE, FIELD_STR, head_atom_parser },
 +      { "color", SOURCE_NONE, FIELD_STR, color_atom_parser },
 +      { "align", SOURCE_NONE, FIELD_STR, align_atom_parser },
 +      { "end", SOURCE_NONE },
 +      { "if", SOURCE_NONE, FIELD_STR, if_atom_parser },
 +      { "then", SOURCE_NONE },
 +      { "else", SOURCE_NONE },
  };
  
  #define REF_FORMATTING_STATE_INIT  { 0, NULL }
@@@ -538,13 -501,6 +539,13 @@@ static int parse_ref_filter_atom(const 
        REALLOC_ARRAY(used_atom, used_atom_cnt);
        used_atom[at].name = xmemdupz(atom, ep - atom);
        used_atom[at].type = valid_atom[i].cmp_type;
 +      used_atom[at].source = valid_atom[i].source;
 +      if (used_atom[at].source == SOURCE_OBJ) {
 +              if (*atom == '*')
 +                      oi_deref.info.contentp = &oi_deref.content;
 +              else
 +                      oi.info.contentp = &oi.content;
 +      }
        if (arg) {
                arg = used_atom[at].name + (arg - atom) + 1;
                if (!*arg) {
@@@ -840,6 -796,25 +841,6 @@@ int verify_ref_format(struct ref_forma
        return 0;
  }
  
 -/*
 - * Given an object name, read the object data and size, and return a
 - * "struct object".  If the object data we are returning is also borrowed
 - * by the "struct object" representation, set *eaten as well---it is a
 - * signal from parse_object_buffer to us not to free the buffer.
 - */
 -static void *get_obj(const struct object_id *oid, struct object **obj, unsigned long *sz, int *eaten)
 -{
 -      enum object_type type;
 -      void *buf = read_object_file(oid, &type, sz);
 -
 -      if (buf)
 -              *obj = parse_object_buffer(the_repository, oid, type, *sz,
 -                                         buf, eaten);
 -      else
 -              *obj = NULL;
 -      return buf;
 -}
 -
  static int grab_objectname(const char *name, const struct object_id *oid,
                           struct atom_value *v, struct used_atom *atom)
  {
  }
  
  /* See grab_values */
 -static void grab_common_values(struct atom_value *val, int deref, struct object *obj, void *buf, unsigned long sz)
 +static void grab_common_values(struct atom_value *val, int deref, struct expand_data *oi)
  {
        int i;
  
                if (deref)
                        name++;
                if (!strcmp(name, "objecttype"))
 -                      v->s = type_name(obj->type);
 +                      v->s = type_name(oi->type);
                else if (!strcmp(name, "objectsize")) {
 -                      v->value = sz;
 -                      v->s = xstrfmt("%lu", sz);
 +                      v->value = oi->size;
 +                      v->s = xstrfmt("%lu", oi->size);
                }
                else if (deref)
 -                      grab_objectname(name, &obj->oid, v, &used_atom[i]);
 +                      grab_objectname(name, &oi->oid, v, &used_atom[i]);
        }
  }
  
@@@ -1237,6 -1212,7 +1238,6 @@@ static void fill_missing_values(struct 
   */
  static void grab_values(struct atom_value *val, int deref, struct object *obj, void *buf, unsigned long sz)
  {
 -      grab_common_values(val, deref, obj, buf, sz);
        switch (obj->type) {
        case OBJ_TAG:
                grab_tag_values(val, deref, obj, buf, sz);
@@@ -1460,36 -1436,24 +1461,36 @@@ static const char *get_refname(struct u
        return show_ref(&atom->u.refname, ref->refname);
  }
  
 -static int get_object(struct ref_array_item *ref, const struct object_id *oid,
 -                     int deref, struct object **obj, struct strbuf *err)
 +static int get_object(struct ref_array_item *ref, int deref, struct object **obj,
 +                    struct expand_data *oi, struct strbuf *err)
  {
 -      int eaten;
 -      int ret = 0;
 -      unsigned long size;
 -      void *buf = get_obj(oid, obj, &size, &eaten);
 -      if (!buf)
 -              ret = strbuf_addf_ret(err, -1, _("missing object %s for %s"),
 -                                    oid_to_hex(oid), ref->refname);
 -      else if (!*obj)
 -              ret = strbuf_addf_ret(err, -1, _("parse_object_buffer failed on %s for %s"),
 -                                    oid_to_hex(oid), ref->refname);
 -      else
 -              grab_values(ref->value, deref, *obj, buf, size);
 +      /* parse_object_buffer() will set eaten to 0 if free() will be needed */
 +      int eaten = 1;
 +      if (oi->info.contentp) {
 +              /* We need to know that to use parse_object_buffer properly */
 +              oi->info.sizep = &oi->size;
 +              oi->info.typep = &oi->type;
 +      }
 +      if (oid_object_info_extended(the_repository, &oi->oid, &oi->info,
 +                                   OBJECT_INFO_LOOKUP_REPLACE))
 +              return strbuf_addf_ret(err, -1, _("missing object %s for %s"),
 +                                     oid_to_hex(&oi->oid), ref->refname);
 +
 +      if (oi->info.contentp) {
 +              *obj = parse_object_buffer(the_repository, &oi->oid, oi->type, oi->size, oi->content, &eaten);
 +              if (!obj) {
 +                      if (!eaten)
 +                              free(oi->content);
 +                      return strbuf_addf_ret(err, -1, _("parse_object_buffer failed on %s for %s"),
 +                                             oid_to_hex(&oi->oid), ref->refname);
 +              }
 +              grab_values(ref->value, deref, *obj, oi->content, oi->size);
 +      }
 +
 +      grab_common_values(ref->value, deref, oi);
        if (!eaten)
 -              free(buf);
 -      return ret;
 +              free(oi->content);
 +      return 0;
  }
  
  /*
@@@ -1499,7 -1463,7 +1500,7 @@@ static int populate_value(struct ref_ar
  {
        struct object *obj;
        int i;
 -      const struct object_id *tagged;
 +      struct object_info empty = OBJECT_INFO_INIT;
  
        ref->value = xcalloc(used_atom_cnt, sizeof(struct atom_value));
  
                        refname = get_symref(atom, ref);
                else if (starts_with(name, "upstream")) {
                        const char *branch_name;
 +                      v->s = "";
                        /* only local branches may have an upstream */
                        if (!skip_prefix(ref->refname, "refs/heads/",
                                         &branch_name))
                        continue;
                } else if (atom->u.remote_ref.push) {
                        const char *branch_name;
 +                      v->s = "";
                        if (!skip_prefix(ref->refname, "refs/heads/",
                                         &branch_name))
                                continue;
                        continue;
                } else if (starts_with(name, "align")) {
                        v->handler = align_atom_handler;
 +                      v->s = "";
                        continue;
                } else if (!strcmp(name, "end")) {
                        v->handler = end_atom_handler;
 +                      v->s = "";
                        continue;
                } else if (starts_with(name, "if")) {
                        const char *s;
 -
 +                      v->s = "";
                        if (skip_prefix(name, "if:", &s))
                                v->s = xstrdup(s);
                        v->handler = if_atom_handler;
                        continue;
                } else if (!strcmp(name, "then")) {
                        v->handler = then_atom_handler;
 +                      v->s = "";
                        continue;
                } else if (!strcmp(name, "else")) {
                        v->handler = else_atom_handler;
 +                      v->s = "";
                        continue;
                } else
                        continue;
  
        for (i = 0; i < used_atom_cnt; i++) {
                struct atom_value *v = &ref->value[i];
 -              if (v->s == NULL)
 -                      break;
 +              if (v->s == NULL && used_atom[i].source == SOURCE_NONE)
 +                      return strbuf_addf_ret(err, -1, _("missing object %s for %s"),
 +                                             oid_to_hex(&ref->objectname), ref->refname);
        }
 -      if (used_atom_cnt <= i)
 +
 +      if (need_tagged)
 +              oi.info.contentp = &oi.content;
 +      if (!memcmp(&oi.info, &empty, sizeof(empty)) &&
 +          !memcmp(&oi_deref.info, &empty, sizeof(empty)))
                return 0;
  
 -      if (get_object(ref, &ref->objectname, 0, &obj, err))
 +
 +      oi.oid = ref->objectname;
 +      if (get_object(ref, 0, &obj, &oi, err))
                return -1;
  
        /*
         * If it is a tag object, see if we use a value that derefs
         * the object, and if we do grab the object it refers to.
         */
 -      tagged = &((struct tag *)obj)->tagged->oid;
 +      oi_deref.oid = ((struct tag *)obj)->tagged->oid;
  
        /*
         * NEEDSWORK: This derefs tag only once, which
         * is not consistent with what deref_tag() does
         * which peels the onion to the core.
         */
 -      return get_object(ref, tagged, 1, &obj, err);
 +      return get_object(ref, 1, &obj, &oi_deref, err);
  }
  
  /*
@@@ -1673,144 -1624,6 +1674,6 @@@ static int get_ref_atom_value(struct re
        return 0;
  }
  
- /*
-  * Unknown has to be "0" here, because that's the default value for
-  * contains_cache slab entries that have not yet been assigned.
-  */
- enum contains_result {
-       CONTAINS_UNKNOWN = 0,
-       CONTAINS_NO,
-       CONTAINS_YES
- };
- define_commit_slab(contains_cache, enum contains_result);
- struct ref_filter_cbdata {
-       struct ref_array *array;
-       struct ref_filter *filter;
-       struct contains_cache contains_cache;
-       struct contains_cache no_contains_cache;
- };
- /*
-  * Mimicking the real stack, this stack lives on the heap, avoiding stack
-  * overflows.
-  *
-  * At each recursion step, the stack items points to the commits whose
-  * ancestors are to be inspected.
-  */
- struct contains_stack {
-       int nr, alloc;
-       struct contains_stack_entry {
-               struct commit *commit;
-               struct commit_list *parents;
-       } *contains_stack;
- };
- static int in_commit_list(const struct commit_list *want, struct commit *c)
- {
-       for (; want; want = want->next)
-               if (!oidcmp(&want->item->object.oid, &c->object.oid))
-                       return 1;
-       return 0;
- }
- /*
-  * Test whether the candidate is contained in the list.
-  * Do not recurse to find out, though, but return -1 if inconclusive.
-  */
- static enum contains_result contains_test(struct commit *candidate,
-                                         const struct commit_list *want,
-                                         struct contains_cache *cache,
-                                         uint32_t cutoff)
- {
-       enum contains_result *cached = contains_cache_at(cache, candidate);
-       /* If we already have the answer cached, return that. */
-       if (*cached)
-               return *cached;
-       /* or are we it? */
-       if (in_commit_list(want, candidate)) {
-               *cached = CONTAINS_YES;
-               return CONTAINS_YES;
-       }
-       /* Otherwise, we don't know; prepare to recurse */
-       parse_commit_or_die(candidate);
-       if (candidate->generation < cutoff)
-               return CONTAINS_NO;
-       return CONTAINS_UNKNOWN;
- }
- static void push_to_contains_stack(struct commit *candidate, struct contains_stack *contains_stack)
- {
-       ALLOC_GROW(contains_stack->contains_stack, contains_stack->nr + 1, contains_stack->alloc);
-       contains_stack->contains_stack[contains_stack->nr].commit = candidate;
-       contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;
- }
- static enum contains_result contains_tag_algo(struct commit *candidate,
-                                             const struct commit_list *want,
-                                             struct contains_cache *cache)
- {
-       struct contains_stack contains_stack = { 0, 0, NULL };
-       enum contains_result result;
-       uint32_t cutoff = GENERATION_NUMBER_INFINITY;
-       const struct commit_list *p;
-       for (p = want; p; p = p->next) {
-               struct commit *c = p->item;
-               load_commit_graph_info(the_repository, c);
-               if (c->generation < cutoff)
-                       cutoff = c->generation;
-       }
-       result = contains_test(candidate, want, cache, cutoff);
-       if (result != CONTAINS_UNKNOWN)
-               return result;
-       push_to_contains_stack(candidate, &contains_stack);
-       while (contains_stack.nr) {
-               struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];
-               struct commit *commit = entry->commit;
-               struct commit_list *parents = entry->parents;
-               if (!parents) {
-                       *contains_cache_at(cache, commit) = CONTAINS_NO;
-                       contains_stack.nr--;
-               }
-               /*
-                * If we just popped the stack, parents->item has been marked,
-                * therefore contains_test will return a meaningful yes/no.
-                */
-               else switch (contains_test(parents->item, want, cache, cutoff)) {
-               case CONTAINS_YES:
-                       *contains_cache_at(cache, commit) = CONTAINS_YES;
-                       contains_stack.nr--;
-                       break;
-               case CONTAINS_NO:
-                       entry->parents = parents->next;
-                       break;
-               case CONTAINS_UNKNOWN:
-                       push_to_contains_stack(parents->item, &contains_stack);
-                       break;
-               }
-       }
-       free(contains_stack.contains_stack);
-       return contains_test(candidate, want, cache, cutoff);
- }
- static int commit_contains(struct ref_filter *filter, struct commit *commit,
-                          struct commit_list *list, struct contains_cache *cache)
- {
-       if (filter->with_commit_tag_algo)
-               return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
-       return is_descendant_of(commit, list);
- }
  /*
   * Return 1 if the refname matches one of the patterns, otherwise 0.
   * A pattern can be a literal prefix (e.g. a refname "refs/heads/master"
@@@ -1866,7 -1679,7 +1729,7 @@@ static int match_name_as_path(const str
                     refname[plen] == '/' ||
                     p[plen-1] == '/'))
                        return 1;
 -              if (!wildmatch(p, refname, WM_PATHNAME))
 +              if (!wildmatch(p, refname, flags))
                        return 1;
        }
        return 0;
@@@ -1921,15 -1734,6 +1784,15 @@@ static int for_each_fullref_in_pattern(
                return for_each_fullref_in("", cb, cb_data, broken);
        }
  
 +      if (filter->ignore_case) {
 +              /*
 +               * we can't handle case-insensitive comparisons,
 +               * so just return everything and let the caller
 +               * sort it out.
 +               */
 +              return for_each_fullref_in("", cb, cb_data, broken);
 +      }
 +
        if (!filter->name_patterns[0]) {
                /* no patterns; we have to look at everything */
                return for_each_fullref_in("", cb, cb_data, broken);
@@@ -2046,6 -1850,13 +1909,13 @@@ static int filter_ref_kind(struct ref_f
        return ref_kind_from_refname(refname);
  }
  
+ struct ref_filter_cbdata {
+       struct ref_array *array;
+       struct ref_filter *filter;
+       struct contains_cache contains_cache;
+       struct contains_cache no_contains_cache;
+ };
  /*
   * A call-back given to for_each_ref().  Filter refs and keep them for
   * later object processing.
diff --combined remote.c
index 7f6277a1451d147fc5af4ae2910e7c40dd330aec,f0c23bae48795482dae4eed2bce8d25ec78efd56..9a079517691331fae9cfc46d796c2d296081a7cc
+++ b/remote.c
@@@ -12,6 -12,7 +12,7 @@@
  #include "string-list.h"
  #include "mergesort.h"
  #include "argv-array.h"
+ #include "commit-reach.h"
  
  enum map_direction { FROM_SRC, FROM_DST };
  
@@@ -1689,18 -1690,11 +1690,18 @@@ static struct ref *get_expanded_map(con
  static const struct ref *find_ref_by_name_abbrev(const struct ref *refs, const char *name)
  {
        const struct ref *ref;
 +      const struct ref *best_match = NULL;
 +      int best_score = 0;
 +
        for (ref = refs; ref; ref = ref->next) {
 -              if (refname_match(name, ref->name))
 -                      return ref;
 +              int score = refname_match(name, ref->name);
 +
 +              if (best_score < score) {
 +                      best_match = ref;
 +                      best_score = score;
 +              }
        }
 -      return NULL;
 +      return best_match;
  }
  
  struct ref *get_remote_ref(const struct ref *remote_refs, const char *name)
@@@ -1744,7 -1738,6 +1745,7 @@@ int get_fetch_map(const struct ref *rem
                if (refspec->exact_sha1) {
                        ref_map = alloc_ref(name);
                        get_oid_hex(name, &ref_map->old_oid);
 +                      ref_map->exact_oid = 1;
                } else {
                        ref_map = get_remote_ref(remote_refs, name);
                }
@@@ -1791,55 -1784,6 +1792,6 @@@ int resolve_remote_symref(struct ref *r
        return 1;
  }
  
- static void unmark_and_free(struct commit_list *list, unsigned int mark)
- {
-       while (list) {
-               struct commit *commit = pop_commit(&list);
-               commit->object.flags &= ~mark;
-       }
- }
- int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
- {
-       struct object *o;
-       struct commit *old_commit, *new_commit;
-       struct commit_list *list, *used;
-       int found = 0;
-       /*
-        * Both new_commit and old_commit must be commit-ish and new_commit is descendant of
-        * old_commit.  Otherwise we require --force.
-        */
-       o = deref_tag(the_repository, parse_object(the_repository, old_oid),
-                     NULL, 0);
-       if (!o || o->type != OBJ_COMMIT)
-               return 0;
-       old_commit = (struct commit *) o;
-       o = deref_tag(the_repository, parse_object(the_repository, new_oid),
-                     NULL, 0);
-       if (!o || o->type != OBJ_COMMIT)
-               return 0;
-       new_commit = (struct commit *) o;
-       if (parse_commit(new_commit) < 0)
-               return 0;
-       used = list = NULL;
-       commit_list_insert(new_commit, &list);
-       while (list) {
-               new_commit = pop_most_recent_commit(&list, TMP_MARK);
-               commit_list_insert(new_commit, &used);
-               if (new_commit == old_commit) {
-                       found = 1;
-                       break;
-               }
-       }
-       unmark_and_free(list, TMP_MARK);
-       unmark_and_free(used, TMP_MARK);
-       return found;
- }
  /*
   * Lookup the upstream branch for the given branch and if present, optionally
   * compute the commit ahead/behind values for the pair.
diff --combined remote.h
index 88f8480c71a2e5ac494ef65532619a4322c1d32a,56fb9cbb27258be9eeae50a9c99fc8bb1d6a5f5c..da53ad570b91dbd4a820ffc79541fb0a4915ff6b
+++ b/remote.h
@@@ -1,7 -1,6 +1,7 @@@
  #ifndef REMOTE_H
  #define REMOTE_H
  
 +#include "cache.h"
  #include "parse-options.h"
  #include "hashmap.h"
  #include "refspec.h"
@@@ -74,7 -73,6 +74,7 @@@ struct ref 
                force:1,
                forced_update:1,
                expect_old_sha1:1,
 +              exact_oid:1,
                deletion:1;
  
        enum {
@@@ -151,7 -149,6 +151,6 @@@ extern struct ref **get_remote_refs(in
                                    const struct string_list *server_options);
  
  int resolve_remote_symref(struct ref *ref, struct ref *list);
- int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);
  
  /*
   * Remove and free all but the first of any entries in the input list
diff --combined revision.c
index 46228f82ee50166fb135d457f808b52629f48394,3205a3947ad122aa9c5d2f7bce5e85bd0a690c65..494cc041faba7921781cfa7b35c3bd56e877ec6f
@@@ -24,6 -24,7 +24,7 @@@
  #include "packfile.h"
  #include "worktree.h"
  #include "argv-array.h"
+ #include "commit-reach.h"
  
  volatile show_early_output_fn_t show_early_output;
  
@@@ -175,7 -176,6 +176,7 @@@ static void add_pending_object_with_pat
                strbuf_release(&buf);
                return; /* do not add the commit itself */
        }
 +      obj->flags |= USER_GIVEN;
        add_object_array_with_path(obj, name, &revs->pending, mode, path);
  }
  
@@@ -251,9 -251,6 +252,9 @@@ static struct commit *handle_commit(str
                if (!object) {
                        if (revs->ignore_missing_links || (flags & UNINTERESTING))
                                return NULL;
 +                      if (revs->exclude_promisor_objects &&
 +                          is_promisor_object(&tag->tagged->oid))
 +                              return NULL;
                        die("bad object %s", oid_to_hex(&tag->tagged->oid));
                }
                object->flags |= flags;
@@@ -1517,7 -1514,7 +1518,7 @@@ static void prepare_show_merge(struct r
                const struct cache_entry *ce = active_cache[i];
                if (!ce_stage(ce))
                        continue;
 -              if (ce_path_match(ce, &revs->prune_data, NULL)) {
 +              if (ce_path_match(&the_index, ce, &revs->prune_data, NULL)) {
                        prune_num++;
                        REALLOC_ARRAY(prune, prune_num);
                        prune[prune_num-2] = ce->name;
@@@ -2318,7 -2315,7 +2319,7 @@@ static void NORETURN diagnose_missing_d
   */
  int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct setup_revision_opt *opt)
  {
 -      int i, flags, left, seen_dashdash, read_from_stdin, got_rev_arg = 0, revarg_opt;
 +      int i, flags, left, seen_dashdash, got_rev_arg = 0, revarg_opt;
        struct argv_array prune_data = ARGV_ARRAY_INIT;
        const char *submodule = NULL;
  
        revarg_opt = opt ? opt->revarg_opt : 0;
        if (seen_dashdash)
                revarg_opt |= REVARG_CANNOT_BE_FILENAME;
 -      read_from_stdin = 0;
        for (left = i = 1; i < argc; i++) {
                const char *arg = argv[i];
                if (*arg == '-') {
                                        argv[left++] = arg;
                                        continue;
                                }
 -                              if (read_from_stdin++)
 +                              if (revs->read_from_stdin++)
                                        die("--stdin given twice?");
                                read_revisions_from_stdin(revs, &prune_data);
                                continue;
diff --combined sequencer.c
index dc2c58d464c14be033f4bcba2ab4332886ead327,97bdfd48b42c14911b8f87975be88ebd853f5374..bd159991e9ca1ad85fe831d84031f6d889e3c090
@@@ -30,6 -30,7 +30,7 @@@
  #include "oidset.h"
  #include "commit-slab.h"
  #include "alias.h"
+ #include "commit-reach.h"
  
  #define GIT_REFLOG_ACTION "GIT_REFLOG_ACTION"
  
@@@ -63,12 -64,12 +64,12 @@@ static GIT_PATH_FUNC(rebase_path_done, 
   * The file to keep track of how many commands were already processed (e.g.
   * for the prompt).
   */
 -static GIT_PATH_FUNC(rebase_path_msgnum, "rebase-merge/msgnum");
 +static GIT_PATH_FUNC(rebase_path_msgnum, "rebase-merge/msgnum")
  /*
   * The file to keep track of how many commands are to be processed in total
   * (e.g. for the prompt).
   */
 -static GIT_PATH_FUNC(rebase_path_msgtotal, "rebase-merge/end");
 +static GIT_PATH_FUNC(rebase_path_msgtotal, "rebase-merge/end")
  /*
   * The commit message that is planned to be used for any changes that
   * need to be committed following a user interaction.
@@@ -307,7 -308,7 +308,7 @@@ static const char *action_name(const st
        case REPLAY_INTERACTIVE_REBASE:
                return N_("rebase -i");
        }
 -      die(_("Unknown action: %d"), opts->action);
 +      die(_("unknown action: %d"), opts->action);
  }
  
  struct commit_message {
@@@ -639,7 -640,7 +640,7 @@@ missing_author
                else if (*message != '\'')
                        strbuf_addch(&buf, *(message++));
                else
 -                      strbuf_addf(&buf, "'\\\\%c'", *(message++));
 +                      strbuf_addf(&buf, "'\\%c'", *(message++));
        strbuf_addstr(&buf, "'\nGIT_AUTHOR_EMAIL='");
        while (*message && *message != '\n' && *message != '\r')
                if (skip_prefix(message, "> ", &message))
                else if (*message != '\'')
                        strbuf_addch(&buf, *(message++));
                else
 -                      strbuf_addf(&buf, "'\\\\%c'", *(message++));
 +                      strbuf_addf(&buf, "'\\%c'", *(message++));
        strbuf_addstr(&buf, "'\nGIT_AUTHOR_DATE='@");
        while (*message && *message != '\n' && *message != '\r')
                if (*message != '\'')
                        strbuf_addch(&buf, *(message++));
                else
 -                      strbuf_addf(&buf, "'\\\\%c'", *(message++));
 +                      strbuf_addf(&buf, "'\\%c'", *(message++));
 +      strbuf_addch(&buf, '\'');
        res = write_message(buf.buf, buf.len, rebase_path_author_script(), 1);
        strbuf_release(&buf);
        return res;
  }
  
 +
 +/*
 + * write_author_script() used to fail to terminate the last line with a "'" and
 + * also escaped "'" incorrectly as "'\\\\''" rather than "'\\''". We check for
 + * the terminating "'" on the last line to see how "'" has been escaped in case
 + * git was upgraded while rebase was stopped.
 + */
 +static int quoting_is_broken(const char *s, size_t n)
 +{
 +      /* Skip any empty lines in case the file was hand edited */
 +      while (n > 0 && s[--n] == '\n')
 +              ; /* empty */
 +      if (n > 0 && s[n] != '\'')
 +              return 1;
 +
 +      return 0;
 +}
 +
  /*
   * Read a list of environment variable assignments (such as the author-script
   * file) into an environment block. Returns -1 on error, 0 otherwise.
  static int read_env_script(struct argv_array *env)
  {
        struct strbuf script = STRBUF_INIT;
 -      int i, count = 0;
 -      char *p, *p2;
 +      int i, count = 0, sq_bug;
 +      const char *p2;
 +      char *p;
  
        if (strbuf_read_file(&script, rebase_path_author_script(), 256) <= 0)
                return -1;
 -
 +      /* write_author_script() used to quote incorrectly */
 +      sq_bug = quoting_is_broken(script.buf, script.len);
        for (p = script.buf; *p; p++)
 -              if (skip_prefix(p, "'\\\\''", (const char **)&p2))
 +              if (sq_bug && skip_prefix(p, "'\\\\''", &p2))
 +                      strbuf_splice(&script, p - script.buf, p2 - p, "'", 1);
 +              else if (skip_prefix(p, "'\\''", &p2))
                        strbuf_splice(&script, p - script.buf, p2 - p, "'", 1);
                else if (*p == '\'')
                        strbuf_splice(&script, p-- - script.buf, 1, "", 0);
@@@ -731,51 -709,43 +732,51 @@@ static const char *read_author_ident(st
        const char *keys[] = {
                "GIT_AUTHOR_NAME=", "GIT_AUTHOR_EMAIL=", "GIT_AUTHOR_DATE="
        };
 -      char *in, *out, *eol;
 -      int i = 0, len;
 +      struct strbuf out = STRBUF_INIT;
 +      char *in, *eol;
 +      const char *val[3];
 +      int i = 0;
  
        if (strbuf_read_file(buf, rebase_path_author_script(), 256) <= 0)
                return NULL;
  
        /* dequote values and construct ident line in-place */
 -      for (in = out = buf->buf; i < 3 && in - buf->buf < buf->len; i++) {
 +      for (in = buf->buf; i < 3 && in - buf->buf < buf->len; i++) {
                if (!skip_prefix(in, keys[i], (const char **)&in)) {
 -                      warning("could not parse '%s' (looking for '%s'",
 +                      warning(_("could not parse '%s' (looking for '%s')"),
                                rebase_path_author_script(), keys[i]);
                        return NULL;
                }
  
                eol = strchrnul(in, '\n');
                *eol = '\0';
 -              sq_dequote(in);
 -              len = strlen(in);
 -
 -              if (i > 0) /* separate values by spaces */
 -                      *(out++) = ' ';
 -              if (i == 1) /* email needs to be surrounded by <...> */
 -                      *(out++) = '<';
 -              memmove(out, in, len);
 -              out += len;
 -              if (i == 1) /* email needs to be surrounded by <...> */
 -                      *(out++) = '>';
 +              if (!sq_dequote(in)) {
 +                      warning(_("bad quoting on %s value in '%s'"),
 +                              keys[i], rebase_path_author_script());
 +                      return NULL;
 +              }
 +              val[i] = in;
                in = eol + 1;
        }
  
        if (i < 3) {
 -              warning("could not parse '%s' (looking for '%s')",
 +              warning(_("could not parse '%s' (looking for '%s')"),
                        rebase_path_author_script(), keys[i]);
                return NULL;
        }
  
 -      buf->len = out - buf->buf;
 +      /* validate date since fmt_ident() will die() on bad value */
 +      if (parse_date(val[2], &out)){
 +              warning(_("invalid date format '%s' in '%s'"),
 +                      val[2], rebase_path_author_script());
 +              strbuf_release(&out);
 +              return NULL;
 +      }
 +
 +      strbuf_reset(&out);
 +      strbuf_addstr(&out, fmt_ident(val[0], val[1], val[2], 0));
 +      strbuf_swap(buf, &out);
 +      strbuf_release(&out);
        return buf->buf;
  }
  
@@@ -820,18 -790,11 +821,18 @@@ static int run_git_commit(const char *d
  
        if ((flags & CREATE_ROOT_COMMIT) && !(flags & AMEND_MSG)) {
                struct strbuf msg = STRBUF_INIT, script = STRBUF_INIT;
 -              const char *author = is_rebase_i(opts) ?
 -                      read_author_ident(&script) : NULL;
 +              const char *author = NULL;
                struct object_id root_commit, *cache_tree_oid;
                int res = 0;
  
 +              if (is_rebase_i(opts)) {
 +                      author = read_author_ident(&script);
 +                      if (!author) {
 +                              strbuf_release(&script);
 +                              return -1;
 +                      }
 +              }
 +
                if (!defmsg)
                        BUG("root commit without message");
  
@@@ -1282,7 -1245,7 +1283,7 @@@ static int try_to_commit(struct strbuf 
                commit_list_insert(current_head, &parents);
        }
  
 -      if (write_cache_as_tree(&tree, 0, NULL)) {
 +      if (write_index_as_tree(&tree, &the_index, get_index_file(), 0, NULL)) {
                res = error(_("git write-tree failed to write a tree"));
                goto out;
        }
@@@ -1483,7 -1446,7 +1484,7 @@@ static const char *command_to_string(co
  {
        if (command < TODO_COMMENT)
                return todo_command_info[command].str;
 -      die("Unknown command: %d", command);
 +      die(_("unknown command: %d"), command);
  }
  
  static char command_to_char(const enum todo_command command)
@@@ -1581,13 -1544,13 +1582,13 @@@ static int update_squash_messages(enum 
                unlink(rebase_path_fixup_msg());
                strbuf_addf(&buf, "\n%c ", comment_line_char);
                strbuf_addf(&buf, _("This is the commit message #%d:"),
 -                          ++opts->current_fixup_count);
 +                          ++opts->current_fixup_count + 1);
                strbuf_addstr(&buf, "\n\n");
                strbuf_addstr(&buf, body);
        } else if (command == TODO_FIXUP) {
                strbuf_addf(&buf, "\n%c ", comment_line_char);
                strbuf_addf(&buf, _("The commit message #%d will be skipped:"),
 -                          ++opts->current_fixup_count);
 +                          ++opts->current_fixup_count + 1);
                strbuf_addstr(&buf, "\n\n");
                strbuf_add_commented_lines(&buf, body, strlen(body));
        } else
@@@ -1668,7 -1631,7 +1669,7 @@@ static int do_pick_commit(enum todo_com
                 * that represents the "current" state for merge-recursive
                 * to work on.
                 */
 -              if (write_cache_as_tree(&head, 0, NULL))
 +              if (write_index_as_tree(&head, &the_index, get_index_file(), 0, NULL))
                        return error(_("your index file is unmerged."));
        } else {
                unborn = get_oid("HEAD", &head);
@@@ -1902,6 -1865,8 +1903,6 @@@ static int prepare_revs(struct replay_o
        if (prepare_revision_walk(opts->revs))
                return error(_("revision walk setup failed"));
  
 -      if (!opts->revs->commits)
 -              return error(_("empty commit set passed"));
        return 0;
  }
  
@@@ -2243,7 -2208,6 +2244,7 @@@ static int populate_opts_cb(const char 
  static void read_strategy_opts(struct replay_opts *opts, struct strbuf *buf)
  {
        int i;
 +      char *strategy_opts_string;
  
        strbuf_reset(buf);
        if (!read_oneliner(buf, rebase_path_strategy(), 0))
        if (!read_oneliner(buf, rebase_path_strategy_opts(), 0))
                return;
  
 -      opts->xopts_nr = split_cmdline(buf->buf, (const char ***)&opts->xopts);
 +      strategy_opts_string = buf->buf;
 +      if (*strategy_opts_string == ' ')
 +              strategy_opts_string++;
 +      opts->xopts_nr = split_cmdline(strategy_opts_string,
 +                                     (const char ***)&opts->xopts);
        for (i = 0; i < opts->xopts_nr; i++) {
                const char *arg = opts->xopts[i];
  
@@@ -2359,10 -2319,6 +2360,10 @@@ static int walk_revs_populate_todo(stru
                        short_commit_name(commit), subject_len, subject);
                unuse_commit_buffer(commit, commit_buffer);
        }
 +
 +      if (!todo_list->nr)
 +              return error(_("empty commit set passed"));
 +
        return 0;
  }
  
@@@ -2639,39 -2595,23 +2640,39 @@@ static int error_with_patch(struct comm
        const char *subject, int subject_len,
        struct replay_opts *opts, int exit_code, int to_amend)
  {
 -      if (make_patch(commit, opts))
 -              return -1;
 +      if (commit) {
 +              if (make_patch(commit, opts))
 +                      return -1;
 +      } else if (copy_file(rebase_path_message(),
 +                           git_path_merge_msg(the_repository), 0666))
 +              return error(_("unable to copy '%s' to '%s'"),
 +                           git_path_merge_msg(the_repository), rebase_path_message());
  
        if (to_amend) {
                if (intend_to_amend())
                        return -1;
  
 -              fprintf(stderr, "You can amend the commit now, with\n"
 -                      "\n"
 -                      "  git commit --amend %s\n"
 -                      "\n"
 -                      "Once you are satisfied with your changes, run\n"
 -                      "\n"
 -                      "  git rebase --continue\n", gpg_sign_opt_quoted(opts));
 -      } else if (exit_code)
 -              fprintf(stderr, "Could not apply %s... %.*s\n",
 -                      short_commit_name(commit), subject_len, subject);
 +              fprintf(stderr,
 +                      _("You can amend the commit now, with\n"
 +                        "\n"
 +                        "  git commit --amend %s\n"
 +                        "\n"
 +                        "Once you are satisfied with your changes, run\n"
 +                        "\n"
 +                        "  git rebase --continue\n"),
 +                      gpg_sign_opt_quoted(opts));
 +      } else if (exit_code) {
 +              if (commit)
 +                      fprintf_ln(stderr, _("Could not apply %s... %.*s"),
 +                                 short_commit_name(commit), subject_len, subject);
 +              else
 +                      /*
 +                       * We don't have the hash of the parent so
 +                       * just print the line from the todo file.
 +                       */
 +                      fprintf_ln(stderr, _("Could not merge %.*s"),
 +                                 subject_len, subject);
 +      }
  
        return exit_code;
  }
@@@ -2699,8 -2639,6 +2700,8 @@@ static int do_exec(const char *command_
        fprintf(stderr, "Executing: %s\n", command_line);
        child_argv[0] = command_line;
        argv_array_pushf(&child_env, "GIT_DIR=%s", absolute_path(get_git_dir()));
 +      argv_array_pushf(&child_env, "GIT_WORK_TREE=%s",
 +                       absolute_path(get_git_work_tree()));
        status = run_command_v_opt_cd_env(child_argv, RUN_USING_SHELL, NULL,
                                          child_env.argv);
  
@@@ -2784,7 -2722,7 +2785,7 @@@ static int do_label(const char *name, i
        struct object_id head_oid;
  
        if (len == 1 && *name == '#')
 -              return error("Illegal label name: '%.*s'", len, 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);
@@@ -2906,26 -2844,6 +2907,26 @@@ static int do_reset(const char *name, i
        return ret;
  }
  
 +static struct commit *lookup_label(const char *label, int len,
 +                                 struct strbuf *buf)
 +{
 +      struct commit *commit;
 +
 +      strbuf_reset(buf);
 +      strbuf_addf(buf, "refs/rewritten/%.*s", len, label);
 +      commit = lookup_commit_reference_by_name(buf->buf);
 +      if (!commit) {
 +              /* fall back to non-rewritten ref or commit */
 +              strbuf_splice(buf, 0, strlen("refs/rewritten/"), "", 0);
 +              commit = lookup_commit_reference_by_name(buf->buf);
 +      }
 +
 +      if (!commit)
 +              error(_("could not resolve '%s'"), buf->buf);
 +
 +      return commit;
 +}
 +
  static int do_merge(struct commit *commit, const char *arg, int arg_len,
                    int flags, struct replay_opts *opts)
  {
        struct strbuf ref_name = STRBUF_INIT;
        struct commit *head_commit, *merge_commit, *i;
        struct commit_list *bases, *j, *reversed = NULL;
 +      struct commit_list *to_merge = NULL, **tail = &to_merge;
        struct merge_options o;
 -      int merge_arg_len, oneline_offset, can_fast_forward, ret;
 +      int merge_arg_len, oneline_offset, can_fast_forward, ret, k;
        static struct lock_file lock;
        const char *p;
  
                goto leave_merge;
        }
  
 -      oneline_offset = arg_len;
 -      merge_arg_len = strcspn(arg, " \t\n");
 -      p = arg + merge_arg_len;
 -      p += strspn(p, " \t\n");
 -      if (*p == '#' && (!p[1] || isspace(p[1]))) {
 -              p += 1 + strspn(p + 1, " \t\n");
 -              oneline_offset = p - arg;
 -      } else if (p - arg < arg_len)
 -              BUG("octopus merges are not supported yet: '%s'", p);
 -
 -      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);
 +      /*
 +       * For octopus merges, the arg starts with the list of revisions to be
 +       * merged. The list is optionally followed by '#' and the oneline.
 +       */
 +      merge_arg_len = oneline_offset = arg_len;
 +      for (p = arg; p - arg < arg_len; p += strspn(p, " \t\n")) {
 +              if (!*p)
 +                      break;
 +              if (*p == '#' && (!p[1] || isspace(p[1]))) {
 +                      p += 1 + strspn(p + 1, " \t\n");
 +                      oneline_offset = p - arg;
 +                      break;
 +              }
 +              k = strcspn(p, " \t\n");
 +              if (!k)
 +                      continue;
 +              merge_commit = lookup_label(p, k, &ref_name);
 +              if (!merge_commit) {
 +                      ret = error(_("unable to parse '%.*s'"), k, p);
 +                      goto leave_merge;
 +              }
 +              tail = &commit_list_insert(merge_commit, tail)->next;
 +              p += k;
 +              merge_arg_len = p - arg;
        }
  
 -      if (!merge_commit) {
 -              ret = error(_("could not resolve '%s'"), ref_name.buf);
 +      if (!to_merge) {
 +              ret = error(_("nothing to merge: '%.*s'"), arg_len, arg);
                goto leave_merge;
        }
  
                 * "[new root]", let's simply fast-forward to the merge head.
                 */
                rollback_lock_file(&lock);
 -              ret = fast_forward_to(&merge_commit->object.oid,
 -                                     &head_commit->object.oid, 0, opts);
 +              if (to_merge->next)
 +                      ret = error(_("octopus merge cannot be executed on "
 +                                    "top of a [new root]"));
 +              else
 +                      ret = fast_forward_to(&to_merge->item->object.oid,
 +                                            &head_commit->object.oid, 0,
 +                                            opts);
                goto leave_merge;
        }
  
                        p = arg + oneline_offset;
                        len = arg_len - oneline_offset;
                } else {
 -                      strbuf_addf(&buf, "Merge branch '%.*s'",
 +                      strbuf_addf(&buf, "Merge %s '%.*s'",
 +                                  to_merge->next ? "branches" : "branch",
                                    merge_arg_len, arg);
                        p = buf.buf;
                        len = buf.len;
                        &head_commit->object.oid);
  
        /*
 -       * If the merge head is different from the original one, we cannot
 +       * If any merge head is different from the original one, we cannot
         * fast-forward.
         */
        if (can_fast_forward) {
 -              struct commit_list *second_parent = commit->parents->next;
 +              struct commit_list *p = commit->parents->next;
  
 -              if (second_parent && !second_parent->next &&
 -                  oidcmp(&merge_commit->object.oid,
 -                         &second_parent->item->object.oid))
 +              for (j = to_merge; j && p; j = j->next, p = p->next)
 +                      if (oidcmp(&j->item->object.oid,
 +                                 &p->item->object.oid)) {
 +                              can_fast_forward = 0;
 +                              break;
 +                      }
 +              /*
 +               * If the number of merge heads differs from the original merge
 +               * commit, we cannot fast-forward.
 +               */
 +              if (j || p)
                        can_fast_forward = 0;
        }
  
 -      if (can_fast_forward && commit->parents->next &&
 -          !commit->parents->next->next &&
 -          !oidcmp(&commit->parents->next->item->object.oid,
 -                  &merge_commit->object.oid)) {
 +      if (can_fast_forward) {
                rollback_lock_file(&lock);
                ret = fast_forward_to(&commit->object.oid,
                                      &head_commit->object.oid, 0, opts);
                goto leave_merge;
        }
  
 +      if (to_merge->next) {
 +              /* Octopus merge */
 +              struct child_process cmd = CHILD_PROCESS_INIT;
 +
 +              if (read_env_script(&cmd.env_array)) {
 +                      const char *gpg_opt = gpg_sign_opt_quoted(opts);
 +
 +                      ret = error(_(staged_changes_advice), gpg_opt, gpg_opt);
 +                      goto leave_merge;
 +              }
 +
 +              cmd.git_cmd = 1;
 +              argv_array_push(&cmd.args, "merge");
 +              argv_array_push(&cmd.args, "-s");
 +              argv_array_push(&cmd.args, "octopus");
 +              argv_array_push(&cmd.args, "--no-edit");
 +              argv_array_push(&cmd.args, "--no-ff");
 +              argv_array_push(&cmd.args, "--no-log");
 +              argv_array_push(&cmd.args, "--no-stat");
 +              argv_array_push(&cmd.args, "-F");
 +              argv_array_push(&cmd.args, git_path_merge_msg(the_repository));
 +              if (opts->gpg_sign)
 +                      argv_array_push(&cmd.args, opts->gpg_sign);
 +
 +              /* Add the tips to be merged */
 +              for (j = to_merge; j; j = j->next)
 +                      argv_array_push(&cmd.args,
 +                                      oid_to_hex(&j->item->object.oid));
 +
 +              strbuf_release(&ref_name);
 +              unlink(git_path_cherry_pick_head(the_repository));
 +              rollback_lock_file(&lock);
 +
 +              rollback_lock_file(&lock);
 +              ret = run_command(&cmd);
 +
 +              /* force re-reading of the cache */
 +              if (!ret && (discard_cache() < 0 || read_cache() < 0))
 +                      ret = error(_("could not read index"));
 +              goto leave_merge;
 +      }
 +
 +      merge_commit = to_merge->item;
        write_message(oid_to_hex(&merge_commit->object.oid), GIT_SHA1_HEXSZ,
                      git_path_merge_head(the_repository), 0);
        write_message("no-ff", 5, git_path_merge_mode(the_repository), 0);
  leave_merge:
        strbuf_release(&ref_name);
        rollback_lock_file(&lock);
 +      free_commit_list(to_merge);
        return ret;
  }
  
@@@ -3366,27 -3220,10 +3367,27 @@@ static int pick_commits(struct todo_lis
                                        intend_to_amend();
                                return error_failed_squash(item->commit, opts,
                                        item->arg_len, item->arg);
 -                      } else if (res && is_rebase_i(opts) && item->commit)
 +                      } else if (res && is_rebase_i(opts) && item->commit) {
 +                              int to_amend = 0;
 +                              struct object_id oid;
 +
 +                              /*
 +                               * If we are rewording and have either
 +                               * fast-forwarded already, or are about to
 +                               * create a new root commit, we want to amend,
 +                               * otherwise we do not.
 +                               */
 +                              if (item->command == TODO_REWORD &&
 +                                  !get_oid("HEAD", &oid) &&
 +                                  (!oidcmp(&item->commit->object.oid, &oid) ||
 +                                   (opts->have_squash_onto &&
 +                                    !oidcmp(&opts->squash_onto, &oid))))
 +                                      to_amend = 1;
 +
                                return res | error_with_patch(item->commit,
 -                                      item->arg, item->arg_len, opts, res,
 -                                      item->command == TODO_REWORD);
 +                                              item->arg, item->arg_len, opts,
 +                                              res, to_amend);
 +                      }
                } else if (item->command == TODO_EXEC) {
                        char *end_of_arg = (char *)(item->arg + item->arg_len);
                        int saved = *end_of_arg;
@@@ -3800,10 -3637,8 +3801,10 @@@ int sequencer_pick_revisions(struct rep
                if (prepare_revision_walk(opts->revs))
                        return error(_("revision walk setup failed"));
                cmit = get_revision(opts->revs);
 -              if (!cmit || get_revision(opts->revs))
 -                      return error("BUG: expected exactly one commit from walk");
 +              if (!cmit)
 +                      return error(_("empty commit set passed"));
 +              if (get_revision(opts->revs))
 +                      BUG("unexpected extra commit from walk");
                return single_pick(cmit, opts);
        }
  
@@@ -4045,6 -3880,7 +4046,6 @@@ static int make_script_with_merges(stru
         */
        while ((commit = get_revision(revs))) {
                struct commit_list *to_merge;
 -              int is_octopus;
                const char *p1, *p2;
                struct object_id *oid;
                int is_empty;
                        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) &&
                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, ' ');
 +              /* label the tips of merged branches */
 +              for (; to_merge; to_merge = to_merge->next) {
 +                      oid = &to_merge->item->object.oid;
 +                      strbuf_addch(&buf, ' ');
 +
 +                      if (!oidset_contains(&interesting, oid)) {
 +                              strbuf_addstr(&buf, label_oid(oid, NULL,
 +                                                            &state));
 +                              continue;
 +                      }
  
 -              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;
  
                entry = oidmap_get(&state.commit2label, &commit->object.oid);
  
                if (entry)
 -                      fprintf(out, "\n# Branch %s\n", entry->string);
 +                      fprintf(out, "\n%c Branch %s\n", comment_line_char, entry->string);
                else
                        fprintf(out, "\n");
  
@@@ -4298,9 -4135,10 +4299,9 @@@ int sequencer_add_exec_commands(const c
  {
        const char *todo_file = rebase_path_todo();
        struct todo_list todo_list = TODO_LIST_INIT;
 -      struct todo_item *item;
        struct strbuf *buf = &todo_list.buf;
        size_t offset = 0, commands_len = strlen(commands);
 -      int i, first;
 +      int i, insert;
  
        if (strbuf_read_file(&todo_list.buf, todo_file, 0) < 0)
                return error(_("could not read '%s'."), todo_file);
                return error(_("unusable todo list: '%s'"), todo_file);
        }
  
 -      first = 1;
 -      /* insert <commands> before every pick except the first one */
 -      for (item = todo_list.items, i = 0; i < todo_list.nr; i++, item++) {
 -              if (item->command == TODO_PICK && !first) {
 -                      strbuf_insert(buf, item->offset_in_buf + offset,
 -                                    commands, commands_len);
 +      /*
 +       * Insert <commands> after every pick. Here, fixup/squash chains
 +       * are considered part of the pick, so we insert the commands *after*
 +       * those chains if there are any.
 +       */
 +      insert = -1;
 +      for (i = 0; i < todo_list.nr; i++) {
 +              enum todo_command command = todo_list.items[i].command;
 +
 +              if (insert >= 0) {
 +                      /* skip fixup/squash chains */
 +                      if (command == TODO_COMMENT)
 +                              continue;
 +                      else if (is_fixup(command)) {
 +                              insert = i + 1;
 +                              continue;
 +                      }
 +                      strbuf_insert(buf,
 +                                    todo_list.items[insert].offset_in_buf +
 +                                    offset, commands, commands_len);
                        offset += commands_len;
 +                      insert = -1;
                }
 -              first = 0;
 +
 +              if (command == TODO_PICK || command == TODO_MERGE)
 +                      insert = i + 1;
        }
  
 -      /* append final <commands> */
 -      strbuf_add(buf, commands, commands_len);
 +      /* insert or append final <commands> */
 +      if (insert >= 0 && insert < todo_list.nr)
 +              strbuf_insert(buf, todo_list.items[insert].offset_in_buf +
 +                            offset, commands, commands_len);
 +      else if (insert >= 0 || !offset)
 +              strbuf_add(buf, commands, commands_len);
  
        i = write_message(buf->buf, buf->len, todo_file, 0);
        todo_list_release(&todo_list);
diff --combined sha1-name.c
index 6cccfbbfbff396fb17ac9f3f357dcead802ecf94,7215b30b8861aaada90f578ef598e2a43793250b..fbcd2f78eb3fafc84748063d46e14f5153ffe4bc
@@@ -12,7 -12,7 +12,8 @@@
  #include "packfile.h"
  #include "object-store.h"
  #include "repository.h"
 +#include "midx.h"
+ #include "commit-reach.h"
  
  static int get_oid_oneline(const char *, struct object_id *, struct commit_list *);
  
@@@ -150,32 -150,6 +151,32 @@@ static int match_sha(unsigned len, cons
        return 1;
  }
  
 +static void unique_in_midx(struct multi_pack_index *m,
 +                         struct disambiguate_state *ds)
 +{
 +      uint32_t num, i, first = 0;
 +      const struct object_id *current = NULL;
 +      num = m->num_objects;
 +
 +      if (!num)
 +              return;
 +
 +      bsearch_midx(&ds->bin_pfx, m, &first);
 +
 +      /*
 +       * At this point, "first" is the location of the lowest object
 +       * with an object name that could match "bin_pfx".  See if we have
 +       * 0, 1 or more objects that actually match(es).
 +       */
 +      for (i = first; i < num && !ds->ambiguous; i++) {
 +              struct object_id oid;
 +              current = nth_midxed_object_oid(&oid, m, i);
 +              if (!match_sha(ds->len, ds->bin_pfx.hash, current->hash))
 +                      break;
 +              update_candidates(ds, current);
 +      }
 +}
 +
  static void unique_in_pack(struct packed_git *p,
                           struct disambiguate_state *ds)
  {
  
  static void find_short_packed_object(struct disambiguate_state *ds)
  {
 +      struct multi_pack_index *m;
        struct packed_git *p;
  
 +      for (m = get_multi_pack_index(the_repository); m && !ds->ambiguous;
 +           m = m->next)
 +              unique_in_midx(m, ds);
        for (p = get_packed_git(the_repository); p && !ds->ambiguous;
             p = p->next)
                unique_in_pack(p, ds);
@@@ -343,7 -313,7 +344,7 @@@ static int init_object_disambiguation(c
  {
        int i;
  
 -      if (len < MINIMUM_ABBREV || len > GIT_SHA1_HEXSZ)
 +      if (len < MINIMUM_ABBREV || len > the_hash_algo->hexsz)
                return -1;
  
        memset(ds, 0, sizeof(*ds));
@@@ -560,42 -530,6 +561,42 @@@ static int extend_abbrev_len(const stru
        return 0;
  }
  
 +static void find_abbrev_len_for_midx(struct multi_pack_index *m,
 +                                   struct min_abbrev_data *mad)
 +{
 +      int match = 0;
 +      uint32_t num, first = 0;
 +      struct object_id oid;
 +      const struct object_id *mad_oid;
 +
 +      if (!m->num_objects)
 +              return;
 +
 +      num = m->num_objects;
 +      mad_oid = mad->oid;
 +      match = bsearch_midx(mad_oid, m, &first);
 +
 +      /*
 +       * first is now the position in the packfile where we would insert
 +       * mad->hash if it does not exist (or the position of mad->hash if
 +       * it does exist). Hence, we consider a maximum of two objects
 +       * nearby for the abbreviation length.
 +       */
 +      mad->init_len = 0;
 +      if (!match) {
 +              if (nth_midxed_object_oid(&oid, m, first))
 +                      extend_abbrev_len(&oid, mad);
 +      } else if (first < num - 1) {
 +              if (nth_midxed_object_oid(&oid, m, first + 1))
 +                      extend_abbrev_len(&oid, mad);
 +      }
 +      if (first > 0) {
 +              if (nth_midxed_object_oid(&oid, m, first - 1))
 +                      extend_abbrev_len(&oid, mad);
 +      }
 +      mad->init_len = mad->cur_len;
 +}
 +
  static void find_abbrev_len_for_pack(struct packed_git *p,
                                     struct min_abbrev_data *mad)
  {
  
  static void find_abbrev_len_packed(struct min_abbrev_data *mad)
  {
 +      struct multi_pack_index *m;
        struct packed_git *p;
  
 +      for (m = get_multi_pack_index(the_repository); m; m = m->next)
 +              find_abbrev_len_for_midx(m, mad);
        for (p = get_packed_git(the_repository); p; p = p->next)
                find_abbrev_len_for_pack(p, mad);
  }
@@@ -648,8 -579,6 +649,8 @@@ int find_unique_abbrev_r(char *hex, con
        struct disambiguate_state ds;
        struct min_abbrev_data mad;
        struct object_id oid_ret;
 +      const unsigned hexsz = the_hash_algo->hexsz;
 +
        if (len < 0) {
                unsigned long count = approximate_object_count();
                /*
        }
  
        oid_to_hex_r(hex, oid);
 -      if (len == GIT_SHA1_HEXSZ || !len)
 -              return GIT_SHA1_HEXSZ;
 +      if (len == hexsz || !len)
 +              return hexsz;
  
        mad.init_len = len;
        mad.cur_len = len;
@@@ -780,7 -709,7 +781,7 @@@ static int get_oid_basic(const char *st
        int refs_found = 0;
        int at, reflog_len, nth_prior = 0;
  
 -      if (len == GIT_SHA1_HEXSZ && !get_oid_hex(str, oid)) {
 +      if (len == the_hash_algo->hexsz && !get_oid_hex(str, oid)) {
                if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
                        refs_found = dwim_ref(str, len, &tmp_oid, &real_ref);
                        if (refs_found > 0) {
                int detached;
  
                if (interpret_nth_prior_checkout(str, len, &buf) > 0) {
 -                      detached = (buf.len == GIT_SHA1_HEXSZ && !get_oid_hex(buf.buf, oid));
 +                      detached = (buf.len == the_hash_algo->hexsz && !get_oid_hex(buf.buf, oid));
                        strbuf_release(&buf);
                        if (detached)
                                return 0;
@@@ -1725,7 -1654,6 +1726,7 @@@ static int get_oid_with_context_1(cons
                        struct commit_list *list = NULL;
  
                        for_each_ref(handle_one_ref, &list);
 +                      head_ref(handle_one_ref, &list);
                        commit_list_sort_by_date(&list);
                        return get_oid_oneline(name + 2, oid, list);
                }
diff --combined submodule.c
index a2b266fbfae2cd89b00a11008fbcd28bf09777e2,6650ed7aa02b2b657929c8868d05b83583c0093a..058fc9f8855d7719cbc9bb17d646b63d99772c87
@@@ -22,6 -22,7 +22,7 @@@
  #include "worktree.h"
  #include "parse-options.h"
  #include "object-store.h"
+ #include "commit-reach.h"
  
  static int config_update_recurse_submodules = RECURSE_SUBMODULES_OFF;
  static struct string_list changed_submodule_names = STRING_LIST_INIT_DUP;
@@@ -93,7 -94,7 +94,7 @@@ int update_path_in_gitmodules(const cha
        if (!file_exists(GITMODULES_FILE)) /* Do nothing without .gitmodules */
                return -1;
  
 -      if (is_gitmodules_unmerged(&the_index))
 +      if (is_gitmodules_unmerged(the_repository->index))
                die(_("Cannot change unmerged .gitmodules, resolve merge conflicts first"));
  
        submodule = submodule_from_path(the_repository, &null_oid, oldpath);
@@@ -127,7 -128,7 +128,7 @@@ int remove_path_from_gitmodules(const c
        if (!file_exists(GITMODULES_FILE)) /* Do nothing without .gitmodules */
                return -1;
  
 -      if (is_gitmodules_unmerged(&the_index))
 +      if (is_gitmodules_unmerged(the_repository->index))
                die(_("Cannot change unmerged .gitmodules, resolve merge conflicts first"));
  
        submodule = submodule_from_path(the_repository, &null_oid, path);
@@@ -188,7 -189,7 +189,7 @@@ void set_diffopt_flags_from_submodule_c
  
                if (ignore)
                        handle_ignore_submodules_arg(diffopt, ignore);
 -              else if (is_gitmodules_unmerged(&the_index))
 +              else if (is_gitmodules_unmerged(the_repository->index))
                        diffopt->flags.ignore_submodules = 1;
        }
  }
@@@ -258,7 -259,7 +259,7 @@@ int is_submodule_active(struct reposito
                }
  
                parse_pathspec(&ps, 0, 0, NULL, args.argv);
 -              ret = match_pathspec(&ps, path, strlen(path), 0, NULL, 1);
 +              ret = match_pathspec(repo->index, &ps, path, strlen(path), 0, NULL, 1);
  
                argv_array_clear(&args);
                clear_pathspec(&ps);
@@@ -1670,7 -1671,7 +1671,7 @@@ int submodule_move_head(const char *pat
        argv_array_push(&cp.args, new_head ? new_head : empty_tree_oid_hex());
  
        if (run_command(&cp)) {
 -              ret = -1;
 +              ret = error(_("Submodule '%s' could not be updated."), path);
                goto out;
        }
  
diff --combined t/helper/test-tool.c
index 32767017102650db48115ffa69aea5c6b5636a4c,582d02adfd93ef5e72ec835b80fd218a3f2afb51..bef50c4dcc7c595c22074b3f5ceb62cf260a6393
@@@ -19,7 -19,6 +19,7 @@@ static struct test_cmd cmds[] = 
        { "genrandom", cmd__genrandom },
        { "hashmap", cmd__hashmap },
        { "index-version", cmd__index_version },
 +      { "json-writer", cmd__json_writer },
        { "lazy-init-name-hash", cmd__lazy_init_name_hash },
        { "match-trees", cmd__match_trees },
        { "mergesort", cmd__mergesort },
@@@ -27,8 -26,8 +27,9 @@@
        { "online-cpus", cmd__online_cpus },
        { "path-utils", cmd__path_utils },
        { "prio-queue", cmd__prio_queue },
+       { "reach", cmd__reach },
        { "read-cache", cmd__read_cache },
 +      { "read-midx", cmd__read_midx },
        { "ref-store", cmd__ref_store },
        { "regex", cmd__regex },
        { "repository", cmd__repository },
diff --combined t/helper/test-tool.h
index 710fb1b28625d26555f809844955b8785f5e2a4c,a7e53c420e1f44d376623c7d289a5ad1968df92e..321982e4bc0366281af400f67ebd2ca3e68fffe7
@@@ -1,8 -1,6 +1,8 @@@
  #ifndef __TEST_TOOL_H__
  #define __TEST_TOOL_H__
  
 +#include "git-compat-util.h"
 +
  int cmd__chmtime(int argc, const char **argv);
  int cmd__config(int argc, const char **argv);
  int cmd__ctype(int argc, const char **argv);
@@@ -15,7 -13,6 +15,7 @@@ int cmd__example_decorate(int argc, con
  int cmd__genrandom(int argc, const char **argv);
  int cmd__hashmap(int argc, const char **argv);
  int cmd__index_version(int argc, const char **argv);
 +int cmd__json_writer(int argc, const char **argv);
  int cmd__lazy_init_name_hash(int argc, const char **argv);
  int cmd__match_trees(int argc, const char **argv);
  int cmd__mergesort(int argc, const char **argv);
@@@ -23,8 -20,8 +23,9 @@@ int cmd__mktemp(int argc, const char **
  int cmd__online_cpus(int argc, const char **argv);
  int cmd__path_utils(int argc, const char **argv);
  int cmd__prio_queue(int argc, const char **argv);
+ int cmd__reach(int argc, const char **argv);
  int cmd__read_cache(int argc, const char **argv);
 +int cmd__read_midx(int argc, const char **argv);
  int cmd__ref_store(int argc, const char **argv);
  int cmd__regex(int argc, const char **argv);
  int cmd__repository(int argc, const char **argv);
diff --combined upload-pack.c
index 82b393ec31917c0c2bcd904668a60b5aaef00633,1e498f1188c90e4998bb06e17f99c4780592a553..62a1000f4401f4314f072b61046d7a19d9d04bae
  #include "quote.h"
  #include "upload-pack.h"
  #include "serve.h"
+ #include "commit-reach.h"
  
  /* Remember to update object flag allocation in object.h */
  #define THEY_HAVE     (1u << 11)
  #define OUR_REF               (1u << 12)
  #define WANTED                (1u << 13)
  #define COMMON_KNOWN  (1u << 14)
- #define REACHABLE     (1u << 15)
  
  #define SHALLOW               (1u << 16)
  #define NOT_SHALLOW   (1u << 17)
@@@ -66,7 -66,6 +66,7 @@@ static const char *pack_objects_hook
  
  static int filter_capability_requested;
  static int allow_filter;
 +static int allow_ref_in_want;
  static struct list_objects_filter_options filter_options;
  
  static void reset_timeout(void)
@@@ -337,64 -336,16 +337,16 @@@ static int got_oid(const char *hex, str
        return 0;
  }
  
- static int reachable(struct commit *want)
- {
-       struct prio_queue work = { compare_commits_by_commit_date };
-       prio_queue_put(&work, want);
-       while (work.nr) {
-               struct commit_list *list;
-               struct commit *commit = prio_queue_get(&work);
-               if (commit->object.flags & THEY_HAVE) {
-                       want->object.flags |= COMMON_KNOWN;
-                       break;
-               }
-               if (!commit->object.parsed)
-                       parse_object(the_repository, &commit->object.oid);
-               if (commit->object.flags & REACHABLE)
-                       continue;
-               commit->object.flags |= REACHABLE;
-               if (commit->date < oldest_have)
-                       continue;
-               for (list = commit->parents; list; list = list->next) {
-                       struct commit *parent = list->item;
-                       if (!(parent->object.flags & REACHABLE))
-                               prio_queue_put(&work, parent);
-               }
-       }
-       want->object.flags |= REACHABLE;
-       clear_commit_marks(want, REACHABLE);
-       clear_prio_queue(&work);
-       return (want->object.flags & COMMON_KNOWN);
- }
  static int ok_to_give_up(void)
  {
-       int i;
+       uint32_t min_generation = GENERATION_NUMBER_ZERO;
  
        if (!have_obj.nr)
                return 0;
  
-       for (i = 0; i < want_obj.nr; i++) {
-               struct object *want = want_obj.objects[i].item;
-               if (want->flags & COMMON_KNOWN)
-                       continue;
-               want = deref_tag(the_repository, want, "a want line", 0);
-               if (!want || want->type != OBJ_COMMIT) {
-                       /* no way to tell if this is reachable by
-                        * looking at the ancestry chain alone, so
-                        * leave a note to ourselves not to worry about
-                        * this object anymore.
-                        */
-                       want_obj.objects[i].item->flags |= COMMON_KNOWN;
-                       continue;
-               }
-               if (!reachable((struct commit *)want))
-                       return 0;
-       }
-       return 1;
+       return can_all_from_reach_with_flag(&want_obj, THEY_HAVE,
+                                           COMMON_KNOWN, oldest_have,
+                                           min_generation);
  }
  
  static int get_common_commits(void)
@@@ -1079,8 -1030,6 +1031,8 @@@ static int upload_pack_config(const cha
                        return git_config_string(&pack_objects_hook, var, value);
        } else if (!strcmp("uploadpack.allowfilter", var)) {
                allow_filter = git_config_bool(var, value);
 +      } else if (!strcmp("uploadpack.allowrefinwant", var)) {
 +              allow_ref_in_want = git_config_bool(var, value);
        }
        return parse_hide_refs_config(var, value, "uploadpack");
  }
@@@ -1120,7 -1069,6 +1072,7 @@@ void upload_pack(struct upload_pack_opt
  
  struct upload_pack_data {
        struct object_array wants;
 +      struct string_list wanted_refs;
        struct oid_array haves;
  
        struct object_array shallows;
  static void upload_pack_data_init(struct upload_pack_data *data)
  {
        struct object_array wants = OBJECT_ARRAY_INIT;
 +      struct string_list wanted_refs = STRING_LIST_INIT_DUP;
        struct oid_array haves = OID_ARRAY_INIT;
        struct object_array shallows = OBJECT_ARRAY_INIT;
        struct string_list deepen_not = STRING_LIST_INIT_DUP;
  
        memset(data, 0, sizeof(*data));
        data->wants = wants;
 +      data->wanted_refs = wanted_refs;
        data->haves = haves;
        data->shallows = shallows;
        data->deepen_not = deepen_not;
  static void upload_pack_data_clear(struct upload_pack_data *data)
  {
        object_array_clear(&data->wants);
 +      string_list_clear(&data->wanted_refs, 1);
        oid_array_clear(&data->haves);
        object_array_clear(&data->shallows);
        string_list_clear(&data->deepen_not, 0);
@@@ -1195,34 -1140,6 +1147,34 @@@ static int parse_want(const char *line
        return 0;
  }
  
 +static int parse_want_ref(const char *line, struct string_list *wanted_refs)
 +{
 +      const char *arg;
 +      if (skip_prefix(line, "want-ref ", &arg)) {
 +              struct object_id oid;
 +              struct string_list_item *item;
 +              struct object *o;
 +
 +              if (read_ref(arg, &oid)) {
 +                      packet_write_fmt(1, "ERR unknown ref %s", arg);
 +                      die("unknown ref %s", arg);
 +              }
 +
 +              item = string_list_append(wanted_refs, arg);
 +              item->util = oiddup(&oid);
 +
 +              o = parse_object_or_die(&oid, arg);
 +              if (!(o->flags & WANTED)) {
 +                      o->flags |= WANTED;
 +                      add_object_array(o, NULL, &want_obj);
 +              }
 +
 +              return 1;
 +      }
 +
 +      return 0;
 +}
 +
  static int parse_have(const char *line, struct oid_array *haves)
  {
        const char *arg;
@@@ -1248,8 -1165,6 +1200,8 @@@ static void process_args(struct packet_
                /* process want */
                if (parse_want(arg))
                        continue;
 +              if (allow_ref_in_want && parse_want_ref(arg, &data->wanted_refs))
 +                      continue;
                /* process have line */
                if (parse_have(arg, &data->haves))
                        continue;
@@@ -1392,24 -1307,6 +1344,24 @@@ static int process_haves_and_send_acks(
        return ret;
  }
  
 +static void send_wanted_ref_info(struct upload_pack_data *data)
 +{
 +      const struct string_list_item *item;
 +
 +      if (!data->wanted_refs.nr)
 +              return;
 +
 +      packet_write_fmt(1, "wanted-refs\n");
 +
 +      for_each_string_list_item(item, &data->wanted_refs) {
 +              packet_write_fmt(1, "%s %s\n",
 +                               oid_to_hex(item->util),
 +                               item->string);
 +      }
 +
 +      packet_delim(1);
 +}
 +
  static void send_shallow_info(struct upload_pack_data *data)
  {
        /* No shallow info needs to be sent */
@@@ -1477,7 -1374,6 +1429,7 @@@ int upload_pack_v2(struct repository *r
                                state = FETCH_DONE;
                        break;
                case FETCH_SEND_PACK:
 +                      send_wanted_ref_info(&data);
                        send_shallow_info(&data);
  
                        packet_write_fmt(1, "packfile\n");
@@@ -1498,22 -1394,12 +1450,22 @@@ int upload_pack_advertise(struct reposi
  {
        if (value) {
                int allow_filter_value;
 +              int allow_ref_in_want;
 +
                strbuf_addstr(value, "shallow");
 +
                if (!repo_config_get_bool(the_repository,
                                         "uploadpack.allowfilter",
                                         &allow_filter_value) &&
                    allow_filter_value)
                        strbuf_addstr(value, " filter");
 +
 +              if (!repo_config_get_bool(the_repository,
 +                                       "uploadpack.allowrefinwant",
 +                                       &allow_ref_in_want) &&
 +                  allow_ref_in_want)
 +                      strbuf_addstr(value, " ref-in-want");
        }
 +
        return 1;
  }