diffcore-order: export generic ordering interface

diffcore_order() interface only accepts a queue of `struct
diff_filepair`.

In the next patches, we'll want to order `struct combine_diff_path`
by path, so let's first rework diffcore-order to also provide
generic low-level interface for ordering arbitrary objects, provided
they have path accessors.

The new interface is:

    - `struct obj_order`    for describing objects to ordering routine, and
    - order_objects()       for actually doing the ordering work.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
diff test: add tests for combine-diff with orderfile

In the next patch combine-diff will have special code-path for taking
orderfile into account. Prepare for making changes by introducing
coverage tests for that case.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
combine-diff: optimize combine_diff_path sets intersection

When generating combined diff, for each commit, we intersect diff
paths from diff(parent_0,commit) to diff(parent_i,commit) comparing
all paths pairs, i.e. doing it the quadratic way. That is correct,
but could be optimized.

Paths come from trees in sorted (= tree) order, and so does diff_tree()
emits resulting paths in that order too. Now if we look at diffcore
transformations, all of them, except diffcore_order, preserve resulting
path ordering:

    - skip_stat_unmatch, grep, pickaxe, filter
                            -- just skip elements -> order stays preserved

    - break                 -- just breaks diff for a path, adding path
                               dup after the path -> order stays preserved

    - detect rename/copy    -- resulting paths are emitted sorted
                               (verified empirically)

So only diffcore_order changes diff paths ordering.

But diffcore_order meaning affects only presentation - i.e. only how to
show the diff, so we could do all the internal computations without
paths reordering, and order only resultant paths set. This is faster,
since, if we know two paths sets are all ordered, their intersection
could be done in linear time.

This patch does just that.

Timings for `git log --raw --no-abbrev --no-renames` without `-c` ("git log")
and with `-c` ("git log -c") before and after the patch are as follows:

                linux.git v3.10..v3.11

            log     log -c

    before  1.9s    20.4s
    after   1.9s    16.6s

                navy.git    (private repo)

            log     log -c

    before  0.83s   15.6s
    after   0.83s    2.1s

P.S.

I think linux.git case is sped up not so much as the second one, since
in navy.git, there are more exotic (subtree, etc) merges.

P.P.S.

My tracing showed that the rest of the time (16.6s vs 1.9s) is usually
spent in computing huge diffs from commit to second parent. Will try to
deal with it, if I'll have time.

P.P.P.S.

For combine_diff_path, ->len is not needed anymore - will remove it in
the next noisy cleanup path, to maintain good signal/noise ratio here.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
combine-diff: combine_diff_path.len is not needed anymore

The field was used in order to speed-up name comparison and also to
mark removed paths by setting it to 0.

Because the updated code does significantly less strcmp and also
just removes paths from the list and free right after we know a path
will not be needed, it is not needed anymore.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
expand_user_path: do not look at NULL path

We explicitly check for and handle the case that the
incoming "path" variable is NULL, but before doing so we
call strchrnul on it, leading to a potential segfault.

We can fix this simply by moving the strchrnul call down; as
a bonus, we can tighten the scope on the associated
variable.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
handle_path_include: don't look at NULL value

When we see config like:

  [include]
  path

the expand_user_path helper notices that the config value is
empty, but we then dereference NULL while printing the error
message (glibc will helpfully print "(null)" for us here,
but we cannot rely on that).

  $ git -c include.path rev-parse
  error: Could not expand include path '(null)'
  fatal: unable to parse command-line config

Instead of tweaking our message, let's actually use
config_error_nonbool to match other config variables that
expect a value:

  $ git -c include.path rev-parse
  error: Missing value for 'include.path'
  fatal: unable to parse command-line config

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
repack: add `repack.honorpackkeep` config var

The git-repack command always passes `--honor-pack-keep`
to pack-objects. This has traditionally been a good thing,
as we do not want to duplicate those objects in a new pack,
and we are not going to delete the old pack.

However, when bitmaps are in use, it is important for a full
repack to include all reachable objects, even if they may be
duplicated in a .keep pack. Otherwise, we cannot generate
the bitmaps, as the on-disk format requires the set of
objects in the pack to be fully closed.

Even if the repository does not generally have .keep files,
a simultaneous push could cause a race condition in which a
.keep file exists at the moment of a repack. The repack may
try to include those objects in one of two situations:

  1. The pushed .keep pack contains objects that were
     already in the repository (e.g., blobs due to a revert of
     an old commit).

  2. Receive-pack updates the refs, making the objects
     reachable, but before it removes the .keep file, the
     repack runs.

In either case, we may prefer to duplicate some objects in
the new, full pack, and let the next repack (after the .keep
file is cleaned up) take care of removing them.

This patch introduces an option to disable the
`--honor-pack-keep` option.  It is not triggered by default,
even when pack.writeBitmaps is turned on, because its use
depends on your overall packing strategy and use of .keep
files.

Note that this option just disables the pack-objects
behavior. We still leave packs with a .keep in place, as we
do not necessarily know that we have duplicated all of their
objects.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
FIXUP: understand pointers ;-)
rev-parse: check i before using argv[i] against argc

The --prefix, --default, and --resolve-git-dir options to
git-rev-parse require an argument, but when given no argument,
the code uses the NULL read from argv[argc] without checking,
leading to a segfault.

Instead, check first and die() with an error message.

Signed-off-by: David Sharp <dhsharp@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'nd/diff-quiet-stat-dirty' into jch

* nd/diff-quiet-stat-dirty:
  diff: do not quit early on stat-dirty files
  Move diffcore_skip_stat_unmatch core logic out for reuse later
Merge branch 'jk/branch-at-publish-rebased' into jch

Give an easier access to the tracking branches from "other" side in
a triangular workflow by introducing B@{publish} that works in a
similar way to how B@{upstream} does.

Will hold.

* jk/branch-at-publish-rebased:
  t1507 (rev-parse-upstream): fix typo in test title
  implement @{publish} shorthand
  branch_get: provide per-branch pushremote pointers
  branch_get: return early on error
  sha1_name: refactor upstream_mark
Merge branch 'rb/merge-prepare-commit-msg-hook' into jch

Expose more merge states (e.g. $GIT_DIR/MERGE_MODE) to hooks that
run during "git merge".  The log message stresses too much on one
hook, prepare-commit-msg, but it would equally apply to other hooks
like post-merge, I think.

Waiting to give a chance to reroll.

* rb/merge-prepare-commit-msg-hook:
  merge: drop unused arg from abort_commit method signature
  merge: make prepare_to_commit responsible for write_merge_state
  t7505: ensure cleanup after hook blocks merge
  t7505: add missing &&
Merge branch 'po/everyday-doc' into jch

This may make the said command to emit something, but the source is
not meant to be formatted into a manual pages to begin with, and
also its contents are a bit stale.  It may be a good first step in
the right direction, but needs more work to at least get the
mark-up right before public consumption.

* po/everyday-doc:
  Make 'git help everyday' work

# Conflicts:
# 	Documentation/Makefile
Merge branch 'jk/warn-on-object-refname-ambiguity' into jch

* jk/warn-on-object-refname-ambiguity:
  get_sha1: drop object/refname ambiguity flag
  get_sha1: speed up ambiguous 40-hex test
  FIXUP: teach DO_FOR_EACH_NO_RECURSE to prime_ref_dir()
  refs: teach for_each_ref a flag to avoid recursion
  cat-file: fix a minor memory leak in batch_objects
  cat-file: refactor error handling of batch_objects

# Conflicts:
# 	builtin/cat-file.c
Merge branch 'ks/diff-c-with-diff-order' into jch

Teach combine-diff to honour the path-output-order imposed by
diffcore-order.

* ks/diff-c-with-diff-order:
  FIXUP: understand pointers ;-)
  combine-diff: combine_diff_path.len is not needed anymore
  combine-diff: optimize combine_diff_path sets intersection
  diff test: add tests for combine-diff with orderfile
  diffcore-order: export generic ordering interface
Merge branch 'lt/request-pull' into jch

* lt/request-pull:
  pull-request: test updates
  Make request-pull able to take a refspec of form local:remote
  Make 'git request-pull' more strict about matching
Merge branch 'nd/submodule-pathspec-ending-with-slash' into jch

* nd/submodule-pathspec-ending-with-slash:
  clean: use cache_name_is_other()
  clean: replace match_pathspec() with dir_path_match()
  Pass directory indicator to match_pathspec_item()
  match_pathspec: match pathspec "foo/" against directory "foo"
  dir.c: prepare match_pathspec_item for taking more flags
  Rename match_pathspec_depth() to match_pathspec()
  Convert some match_pathspec_depth() to dir_path_match()
  Convert some match_pathspec_depth() to ce_path_match()

Conflicts:
	t/t4010-diff-pathspec.sh
Merge branch 'ds/rev-parse-required-args' into jch

* ds/rev-parse-required-args:
  rev-parse: check i before using argv[i] against argc
Merge branch 'jk/config-path-include-fix' into jch

* jk/config-path-include-fix:
  handle_path_include: don't look at NULL value
  expand_user_path: do not look at NULL path
Merge branch 'jk/repack-honor-pack-keep' into jch

* jk/repack-honor-pack-keep:
  repack: add `repack.honorpackkeep` config var