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>
t1400: fix name and expected result of one test

The test

    stdin -z create ref fails with zero new value

actually passes an empty new value, not a zero new value.  So rename
the test s/zero/empty/, and change the expected error from

    fatal: create $c given zero new value

to

    fatal: create $c missing <newvalue>

Of course, this makes the test fail now, because although "git
update-ref" tries to distinguish between these two errors, it does not
succeed in this situation.  Fixing it is more than a one-liner, so
mark the test test_expect_failure for now.  The failure will be fixed
later in this patch series.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
t1400: provide more usual input to the command

The old version was passing (among other things)

    update SP refs/heads/c NUL NUL 0{40} NUL

to "git update-ref -z --stdin" to test whether the old-value check for
c is working.  But the <newvalue> is empty, which is a bit off the
beaten track.

So, to be sure that we are testing what we want to test, provide an
actual <newvalue> on the "update" line.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
parse_arg(): really test that argument is properly terminated

The old parse_arg(), when fed an argument

    "refs/heads/a"master

parsed 'refs/heads/a' off of the front of the argument and considered
itself successful.  It was only when parse_next_arg() tried to parse
the *next* argument that a problem was noticed.  But in fact, the
definition of the input format requires arguments to be terminated by
SP or NUL, so *this* argument is already erroneous and parse_arg()
should diagnose the problem.

So teach parse_arg() to verify that C-quoted arguments are terminated
correctly.  If not, emit a more specific error message.

There is no corresponding error case of a non-C-quoted argument that
is not terminated correctly, because the end of a non-quoted argument
is *by definition* a space or NUL, so there is no way to insert other
junk between the "end" of the argument and the argument terminator.

Adjust the tests to expect the new error message.  Add a docstring to
the function, incorporating the comments that were formerly within the
function plus some added information.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
t1400: add some more tests involving quoted arguments

Previously there were no good tests of C-quoted arguments.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
refs.h: rename the action_on_err constants

Given that these constants are only being used when updating
references, it is inappropriate to give them such generic names as
"DIE_ON_ERR".  So prefix their names with "UPDATE_REFS_".

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
update_refs(): fix constness

The old signature of update_refs() required a
(const struct ref_update **) for its updates_orig argument.  The
"const" is presumably there to promise that the function will not
modify the contents of the structures.

But this declaration does not permit the function to be called with a
(struct ref_update **), which is perfectly legitimate.  C's type
system is not powerful enough to express what we'd like.  So remove
the first "const" from the declaration.

On the other hand, the function *can* promise not to modify the
pointers within the array that is passed to it without inconveniencing
its callers.  So add a "const" that has that effect, making the final
declaration
(struct ref_update * const *).

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
update-ref --stdin: read the whole input at once

Read the whole input into a strbuf at once, and then parse it from
there.  This might also be a tad faster, but that is not the point.
The point is to decouple the parsing code from the input source (the
old parsing code had to read new data even in the middle of commands).
Add docstrings for the parsing functions.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
parse_cmd_verify(): copy old_sha1 instead of evaluating <oldvalue> twice

Aside from avoiding a tiny bit of work, this makes it transparently
obvious that old_sha1 and new_sha1 are identical.  It is arguably a
bit silly to have to set new_sha1 in order to verify old_sha1, but
that is a problem for another day.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
update-ref.c: extract a new function, parse_refname()

There is no reason to obscure the fact that parse_first_arg() always
parses refnames.  Form the new function by combining parse_first_arg()
and update_store_ref_name().

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
update-ref --stdin: improve error messages for invalid values

If an invalid value is passed to "update-ref --stdin" as <oldvalue> or
<newvalue>, include the command and the name of the reference at the
beginning of the error message.  Update the tests accordingly.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
update-ref --stdin: make error messages more consistent

The old error messages emitted for invalid input sometimes said
"<oldvalue>"/"<newvalue>" and sometimes said "old value"/"new value".
Convert them all to the former.  Update the tests accordingly.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
update-ref --stdin: simplify error messages for missing oldvalues

Instead of, for example,

    fatal: update refs/heads/master missing [<oldvalue>] NUL

emit

    fatal: update refs/heads/master missing <oldvalue>

Update the tests accordingly.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
t1400: test that stdin -z update treats empty <newvalue> as zeros

This is the (slightly inconsistent) status quo; make sure it doesn't
change by accident.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
update-ref.c: extract a new function, parse_next_sha1()

Replace three functions, update_store_new_sha1(),
update_store_old_sha1(), and parse_next_arg(), with a single function,
parse_next_sha1().  The new function takes care of a whole argument,
including checking whether it is there, converting it to an SHA-1, and
emitting errors on EOF or for invalid values.  The return value
indicates whether the argument was present or absent, which requires
a bit of intelligence because absent values are represented
differently depending on whether "-z" was used.

The new interface means that the calling functions, parse_cmd_*(),
don't have to interpret the result differently based on the
line_termination mode that is in effect.  It also means that
parse_cmd_create() can distinguish unambiguously between an empty new
value and a zeros new value, which fixes a failure in t1400.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
update-ref --stdin -z: deprecate interpreting the empty string as zeros

In the original version of this command, for the single case of the
"update" command's <newvalue>, the empty string was interpreted as
being equivalent to 40 "0"s.  This shorthand is unnecessary (binary
input will usually be generated programmatically anyway), and it
complicates the parser and the documentation.

So gently deprecate this usage: remove its description from the
documentation and emit a warning if it is found.  But for reasons of
backwards compatibility, continue to accept it.

Helped-by: Brad King <brad.king@kitware.com>
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
t1400: test one mistake at a time

This case wants to test passing a bad refname to the "update" command.
But it also passes too few arguments to "update", which muddles the
situation: which error should be diagnosed?  So split this test into
two:

* One that passes too few arguments to update

* One that passes all three arguments to "update", but with a bad
  refname.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
update-ref --stdin: improve the error message for unexpected EOF

Distinguish this error from the error that an argument is missing for
another reason.  Update the tests accordingly.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
update-ref --stdin: harmonize error messages

Make (most of) the error messages for invalid input have the same
format [1]:

    $COMMAND [SP $REFNAME]: $MESSAGE

Update the tests accordingly.

[1] A few error messages are left with their old form, because
    $COMMAND and $REFNAME aren't passed all the way down the call
    stack.  Maybe those sites should be changed some day, too.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
refs: add a concept of a reference transaction

Build out the API for dealing with a bunch of reference checks and
changes within a transaction.  Define an opaque ref_transaction type
that is managed entirely within refs.c.  Introduce functions for
beginning a transaction, adding updates to a transaction, and
committing/rolling back a transaction.

This API will soon replace update_refs().

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>