add `ignore_missing_links` mode to revwalk

When pack-objects is computing the reachability bitmap to
serve a fetch request, it can erroneously die() if some of
the UNINTERESTING objects are not present. Upload-pack
throws away HAVE lines from the client for objects we do not
have, but we may have a tip object without all of its
ancestors (e.g., if the tip is no longer reachable and was
new enough to survive a `git prune`, but some of its
reachable objects did get pruned).

In the non-bitmap case, we do a revision walk with the HAVE
objects marked as UNINTERESTING. The revision walker
explicitly ignores errors in accessing UNINTERESTING commits
to handle this case (and we do not bother looking at
UNINTERESTING trees or blobs at all).

When we have bitmaps, however, the process is quite
different.  The bitmap index for a pack-objects run is
calculated in two separate steps:

First, we perform an extensive walk from all the HAVEs to
find the full set of objects reachable from them. This walk
is usually optimized away because we are expected to hit an
object with a bitmap during the traversal, which allows us
to terminate early.

Secondly, we perform an extensive walk from all the WANTs,
which usually also terminates early because we hit a commit
with an existing bitmap.

Once we have the resulting bitmaps from the two walks, we
AND-NOT them together to obtain the resulting set of objects
we need to pack.

When we are walking the HAVE objects, the revision walker
does not know that we are walking it only to mark the
results as uninteresting. We strip out the UNINTERESTING flag,
because those objects _are_ interesting to us during the
first walk. We want to keep going to get a complete set of
reachable objects if we can.

We need some way to tell the revision walker that it's OK to
silently truncate the HAVE walk, just like it does for the
UNINTERESTING case. This patch introduces a new
`ignore_missing_links` flag to the `rev_info` struct, which
we set only for the HAVE walk.

It also adds tests to cover UNINTERESTING objects missing
from several positions: a missing blob, a missing tree, and
a missing parent commit. The missing blob already worked (as
we do not care about its contents at all), but the other two
cases caused us to die().

Note that there are a few cases we do not need to test:

  1. We do not need to test a missing tree, with the blob
     still present. Without the tree that refers to it, we
     would not know that the blob is relevant to our walk.

  2. We do not need to test a tip commit that is missing.
     Upload-pack omits these for us (and in fact, we
     complain even in the non-bitmap case if it fails to do
     so).

Reported-by: Siddharth Agarwal <sid0@fb.com>
Signed-off-by: Vicent Marti <tanoku@gmail.com>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'ep/shell-command-substitution'

* ep/shell-command-substitution:
  git-am.sh: use the $(...) construct for command substitution
  check-builtins.sh: use the $(...) construct for command substitution
Merge branch 'nd/log-show-linear-break'

Attempts to show where a single-strand-of-pearls break in "git log"
output.

* nd/log-show-linear-break:
  log: add --show-linear-break to help see non-linear history
  object.h: centralize object flag allocation
Merge branch 'cn/fetch-prune-overlapping-destination'

Protect refs in a hierarchy that can come from more than one remote
hierarcies from incorrect removal by "git fetch --prune".

* cn/fetch-prune-overlapping-destination:
  fetch: handle overlaping refspecs on --prune
  fetch: add a failing test for prunning with overlapping refspecs
Merge branch 'cb/aix'

* cb/aix:
  tests: don't rely on strerror text when testing rmdir failure
  dir.c: make git_fnmatch() not inline
Merge branch 'jc/fix-diff-no-index-diff-opt-parse'

"diff --no-index -Mq a b" fell into an infinite loop.

* jc/fix-diff-no-index-diff-opt-parse:
  diff-no-index: correctly diagnose error return from diff_opt_parse()
Merge branch 'nd/gc-aggressive'

Allow tweaking the maximum length of the delta-chain produced by
"gc --aggressive".

* nd/gc-aggressive:
  environment.c: fix constness for odb_pack_keep()
  gc --aggressive: make --depth configurable
Merge branch 'jn/wt-status' into maint

* jn/wt-status:
  wt-status: lift the artificual "at least 20 columns" floor
  wt-status: i18n of section labels
  wt-status: extract the code to compute width for labels
  wt-status: make full label string to be subject to l10n
Merge branch 'jc/stash-pop-not-popped' into maint

* jc/stash-pop-not-popped:
  stash pop: mention we did not drop the stash upon failing to apply
Merge branch 'jk/shallow-update-fix' into maint

* jk/shallow-update-fix:
  shallow: verify shallow file after taking lock
  shallow: automatically clean up shallow tempfiles
  shallow: use stat_validity to check for up-to-date file
Merge branch 'rr/doc-merge-strategies' into maint

* rr/doc-merge-strategies:
  Documentation/merge-strategies: avoid hyphenated commands
Merge branch 'us/printf-not-echo' into maint

* us/printf-not-echo:
  test-lib.sh: do not "echo" caller-supplied strings
  rebase -i: do not "echo" random user-supplied strings
Merge branch 'nd/index-pack-error-message' into maint

* nd/index-pack-error-message:
  index-pack: report error using the correct variable
Merge branch 'jk/lib-terminal-lazy' into maint

* jk/lib-terminal-lazy:
  t/lib-terminal: make TTY a lazy prerequisite
Merge branch 'mh/remove-subtree-long-pathname-fix' into maint

* mh/remove-subtree-long-pathname-fix:
  entry.c: fix possible buffer overflow in remove_subtree()
  checkout_entry(): use the strbuf throughout the function
Merge branch 'jk/mv-submodules-fix' into maint

* jk/mv-submodules-fix:
  mv: prevent mismatched data when ignoring errors.
  builtin/mv: fix out of bounds write

Conflicts:
	t/t7001-mv.sh
Start preparing for 1.9.1

Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'maint'

* maint:
  Start preparing for 1.9.1
Update draft release notes to 2.0

Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'ks/tree-diff-nway' (early part) into jch

* 'ks/tree-diff-nway' (early part):
  tree-diff: reuse base str(buf) memory on sub-tree recursion
  tree-diff: no need to call "full" diff_tree_sha1 from show_path()
  tree-diff: rework diff_tree interface to be sha1 based
  tree-diff: diff_tree() should now be static
  tree-diff: remove special-case diff-emitting code for empty-tree cases
  tree-diff: simplify tree_entry_pathcmp
  tree-diff: show_path prototype is not needed anymore
  tree-diff: rename compare_tree_entry -> tree_entry_pathcmp
  tree-diff: move all action-taking code out of compare_tree_entry()
  tree-diff: don't assume compare_tree_entry() returns -1,0,1
  tree-diff: consolidate code for emitting diffs and recursion in one place
  tree-diff: show_tree() is not needed
  tree-diff: no need to pass match to skip_uninteresting()
  tree-diff: no need to manually verify that there is no mode change for a path
  combine-diff: move changed-paths scanning logic into its own function
  combine-diff: move show_log_first logic/action out of paths scanning