Replace struct extra_have_objects with struct sha1_array

The latter can do everything the former can and is used in many more
places.
send-pack: forbid pushing from a shallow repository

send-pack can send a pack with loose ends to the server.  receive-pack
before 6d4bb38 (fetch: verify we have everything we need before
updating our ref - 2011-09-01) does not detect this and keeps the pack
anyway, which corrupts the repository, at least from fsck point of
view.

send-pack will learn to safely push from a shallow repository later.
clone: prevent --reference to a shallow repository

If we borrow objects from another repository, we should also pay
attention to their $GIT_DIR/shallow (and even info/grafts). But
current alternates code does not.

Reject alternate repos that are shallow because we do not do it
right. In future the alternate code may be updated to check
$GIT_DIR/shallow properly so that this restriction could be lifted.
Advertise shallow graft information on the server end

If either receive-pack or upload-pack is called on a shallow
repository, shallow graft points will be sent after the ref
advertisement (but before the packet flush), so that the client has
the full "shape" of the server's commit graph.

This breaks the protocol for all clients trying to push to a shallow
repo, or fetch from one. Which is basically the same end result as
today's "is_repository_shallow() && die()" in receive-pack and
upload-pack. New clients will be made aware of shallow upstream and
can make use of this information.

Smart HTTP is not affected by this patch. Shallow support on
smart-http comes later separately.
connect.c: teach get_remote_heads to parse "shallow" lines

No callers pass a non-empty pointer as shallow_points at this
stage. As a result, all clients still refuse to talk to shallow
repository on the other end.
shallow.c: add remove_reachable_shallow_points()

When we receive a pack and the shallow points from another repository
with no history deepen/shorten request, we may want to add more
shallow points to current repo to make sure no commits point to
nowhere. However we do not want to add unnecessary shallow points and
cut our history short because the other end is a shallow version of
this repo. The output shallow points may or may not be added to
.git/shallow, depending on whether they are actually reachable in the
new pack.

This function filters such shallow points out, leaving ones that might
potentially be added. A simple has_sha1_file won't do because we may
have incomplete object islands (i.e. not connected to any refs) and
the shallow points are on these islands. In that case we want to keep
the shallow points as candidates until we figure out if the new pack
connects to such object islands.

Typical cases that use remove_reachable_shallow_points() are:

 - fetch from a repo that has longer history: in this case all remote
   shallow roots do not exist in the client repo, this function will
   be cheap as it just does a few lookup_commit_graft and
   has_sha1_file.

 - fetch from a repo that has exactly the same shallow root set
   (e.g. a clone from a shallow repo): this case may trigger
   in_merge_bases_many all the way to roots. An exception is made to
   avoid such costly path with a faith that .git/shallow does not
   usually points to unreachable commit islands.

   Even if .git/shallow does, the worst thing that can happen is the
   user may not see some part of the history that they expect to see
   because of these commits. There are no loose ends that may lead to
   missing objects. A natural reaction what that happens is deepen (*)
   the history and that operation should add missing objects to the
   repository then move the root further back as wanted.

 - push from a shallow repo that has shorter history than the
   server's: in_merge_bases_many() is unavoidable, so the longer
   history the client has the higher the server cost is. The cost may
   be reduced with the help of pack bitmaps, or commit cache, though.

 - push from a shallow clone that has exactly the same shallow root
   set: the same as the second fetch case above, .i.e. cheap by
   exception.

The function must be called before the new pack is installed, or we
won't know which objects are ours, which theirs.

(*) It's easier than it sounds. With current deepen mechanism, the
user has to do some calculation to determine what number to pass to
--depth. Not pleasant, but currently out of scope.
shallow.c: add mark_new_shallow_refs()

Context is needed to understand this function. Suppose a fetch or push
is requested between two shallow repositories (with no history
deepening or shortening). A pack that contains necessary objects is
transferred over. The receiver has to determine whether it needs to
update .git/shallow in order to update refs that reference to objects
from that pack.

Before the pack is transferred, the sender should have sent its
.git/shallow to the receiver. In order to avoid cutting its history
short by accident (e.g. the sender's history is shorter than the
receiver's), the receiver must remove all commits in the sender's
.git/shallow that are reachable in the current repository. This is
accomplished with remove_reachable_shallow_points(). The remaining
commits may be required for some refs in the new pack, or may be not.

After the pack is received and installed, the receiver can now answer
that question. For each new ref, it can walk through the commit chains
until it hits the (even shallow) bottom of the current repository, or
it hits some of the remaining commits from the sender's .git/shallow.
In the latter case, those commits are obviously needed in the
receiver's .git/shallow for the ref in question. The ref is marked.
All the shallow roots it need are also recorded. This is what
mark_new_shallow_refs() does.

One can see this is not a cheap operation. The code tries to stop the
walker from going down the the repo's current bottom if the walker
goes past any of existing refs, so that only new commits are walked
through. But that's not always the case.

Luckily, a normal push or fetch does not require any new shallow
roots. If none of potential shallow exists in the new pack (*) they
obviously can't be reachable from any new refs, the new pack can be
used without any addition to .git/shallow and the whole commit walking
can be skipped.

Once the sender diverts from that path, it may be a lot more
expensive. Pack bitmaps won't help this kind of commit traversal, but
commit cache or pack v4 might.

(*) The real check is a bit different, if none of potential shallow
    exists (in either new or old packs), we're good. The reason is we
    already ruled out the sender roots that are reachable from current
    refs. So checking the commit existence of the remaining shallow
    roots on current packs must be false.

    Well, and that is true if the repository does not have object
    islands. If the repo does, and the sender's .git/shallow does
    reference to any of them. The real check is fooled and we'll fall
    into the expensive code path.

    One way to avoid this (if it turns out to happen often enough) is
    avoid unpack-objects and always keep the new pack for this
    verification. But that loses the advatanges of unpack-objects. A
    trade-off option is do the strict "new pack only" check when
    index-pack is used, else "all pack" check. But let's see.
shallow.c: extend setup_*_shallow() to accept extra shallow points
fetch-pack.c: move shallow update code out of fetch_pack()
fetch-pack.h: one statement per bitfield declaration
clone: support remote shallow repository

The gist of cloning a remote shallow repository is simple. The remote
gives you a pack and all its shallow roots. All you need to do is set
your .git/shallow correctly.

The rule to create this .git/shallow is simple and more importantly,
cheap: if a shallow root is found in the pack, it's probably used
(i.e. reachable from some refs), so we add it. Others are dropped.

One may notice this method seems flawed by the word "probably". A
shallow point may not be reachable from any refs at all if it's
attached to an object island (a group of objects that are not
reachable by any refs).

If that object island is not complete, a new fetch request may send
more objects to connect it to some ref. At that time, because we
incorrectly installed the shallow root in this island, the user will
not see anything after that root. This is not desired.

There is a stricter method to rule out unwanted shallow roots above:
mark_new_shallow_refs(). But it's expensive and even more so for a
clone because it's proportional to the (potentially huge) number of
commits.

Given that object islands are rare (C Git never sends such islands), a
tradeoff is made to surprise the user occasionally but work faster
everyday. --strict option could be added later to enforce
mark_new_shallow_refs().
fetch: support fetching from a shallow repository

This patch just put together pieces from the previous patches:

 - Before getting the new pack, we need to remove all new reachable
   shallow roots. The remaining roots may or may not be added to
   .git/shallow.

 - After getting the pack, walk all new refs until they connect to
   current refs, or hit the bottom of current repo, or hit new
   shallow roots.

Those refs that hit new shallow roots are rejected because by default
we do not allow to update .git/shallow (the only exception so far is
cloning from a shallow repo, which is more like creating .git/shallow
than updating it)
upload-pack: make sure deepening preserves shallow roots

When "fetch --depth=N" where N exceeds the longest chain of history in
the source repo, usually we just send an "unshallow" line to the
client so full history is obtained.

When the source repo is shallow we need to make sure to "unshallow"
the current shallow point _and_ "shallow" again when the commit
reaches its shallow bottom in the source repo.

This should fix both cases: large <N> and --unshallow.
fetch: add --update-shallow to get refs that require updating .git/shallow
receive-pack: reorder some code in unpack()

This is the preparation for adding --shallow-file to both
unpack-objects and index-pack. To sum up:

 - status/code, ip/child, unpacker/keeper and i (now ac) are moved out
   to function top level

 - successful flow now ends at the end of the function
Support pushing from a shallow clone

Pushing from a shallow clone using today's send-pack and receive-pack
may work, if the transferred pack does not end up at any graft
points. If it does, recent receive-pack that does connectivity check
will reject the push. If receive-pack is old and does not have the
connectivity check, the upstream repo becomes corrupt.

The pack protocol is updated and send-pack now sends all shallow
grafts before it sends the commands, if the repo is shallow. This
protocol extension will break current receive-pack, which is intended,
mostly to stop corrupting the upstream repo.

Changes on the receiver are similar to what has been done in
fetch-pack, i.e. filter out refs that require new shallow roots then
go along as usual.
New var GIT_SHALLOW_FILE to propagate --shallow-file to subprocesses

This may be needed when a hook is run after a new shallow pack is
received, but .git/shallow is not settled yet. A temporary shallow
file to plug all loose ends should be used instead. GIT_SHALLOW_FILE
is overriden by --shallow-file.

--shallow-file does not work in this case because the hook may spawn
many git subprocesses and the launch commands do not have
--shallow-file as it's a recent addition.
connected.c: add new variant that runs with --shallow-file
receive-pack: allow pushing with new shallow roots

This is more expensive than the current mode and potentially
invalidates caches like pack bitmaps. It's only enabled if
receive.shallowupdate is on.
send-pack: support pushing to a shallow clone