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,
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.

 - 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.
shallow.c: add mark_new_shallow_refs()

When we receive a pack and the shallow points from another repository,
we may need to add more shallow points to current repo to make sure no
commits point to nowhere. But usually we don't want to do so because
(in future) new shallow points invalidate pack bitmaps and we need to
rebuild them again, which is not cheap.

So the default way is we allow ref updates that do not introduce new
shallow points and mark the others. If the user is fine with new
shallow point addition, we accept the marked refs.

But even so we do not blindly accept all shallow points provided. Some
of them might not point to any commits in the new pack. Some might
even do, but those might be unreachable object islands. Only shallow
points that are reachable from old and new refs can stay.

The way it's implemented is paint down from each ref, attach a bitmap
to each commit where one bit represents one ref. In order to avoid
allocating new bitmap for every commit, we try to reuse the same
bitmap for parent commits if possible. This reduces allocation and
leaks deliberately because it's hard to keep/time consuming track how
many pointers to the same buffer.

In a typical push or fetch, the new pack should not carry new shallow
roots. If the current repo does not have any commit islands refered by
the sender's shallow roots either, this function is just a few
has_sha1_file(). So quite cheap.

Once the sender diverts from that path (or the receiver detects
shallow roots attached to commit islands from remove_reachable_shallow_points),
it'll be a lot more expensive. Pack bitmaps won't help this kind of
commit traversal, but commit cache might.
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
remote-curl: pass ref SHA-1 to fetch-pack as well
Support fetch/clone over http
receive-pack: support pushing to a shallow clone via http