remote-hg: don't decode UTF-8 paths into Unicode objects

The internal mercurial API expects ordinary 8-bit string objects, not
Unicode string objects.  With this change, the test-hg.sh unit tests
pass again.

Signed-off-by: Richard Hansen <rhansen@bbn.com>
Reviewed-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'rh/remote-hg-bzr-updates' (early part)

Unbreaks a recent breakage due to use of unquote-c-style.

This may need to be cherry-picked down to 1.8.4.x series.

* 'rh/remote-hg-bzr-updates' (early part):
  remote-hg: don't decode UTF-8 paths into Unicode objects
remote-hg: don't decode UTF-8 paths into Unicode objects

The internal mercurial API expects ordinary 8-bit string objects, not
Unicode string objects.  With this change, the test-hg.sh unit tests
pass again.

Signed-off-by: Richard Hansen <rhansen@bbn.com>
Reviewed-by: Felipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Sync with maint

* maint:
  remote-hg: don't decode UTF-8 paths into Unicode objects
Git 1.8.5

Signed-off-by: Junio C Hamano <gitster@pobox.com>
transport.h: remove send_pack prototype, already defined in send-pack.h
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 (*).

 - 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 cost at the server is (**).

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

(*) 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 to that is deepen the history
   and that operation should add missing objects to the repository
   then move the root further back as wanted.

(**) An option is to avoid this cost is delay in_merge_bases_many()
   until after the new pack is received. By then we may find out the
   common case that no shallow points are attached to any commits in
   the new pack. This means we know .git/shallow won't need updates
   and in_merge_bases_many() unnecessary.
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: stop leaking memory in mark_new_shallow_refs()
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.