Multi-head fetch proposal

Hi,

I reported a while ago that a fetch downloaded objects which were already in the repository. While that was true, it was not the whole truth: This only happened with multi-head fetch.

As far as I can tell, what happened was this:

- fetch-pack connected to the server
- it asked correctly for the remote refs
- it then opened a (local) pipe to git-rev-list
- it sent quite a few refs from that pipe over the wire
- on the other side, upload-pack marked these refs as "fetcher got those"
- since upload-pack has a limit on that list (only 16) it soon said STFU 
- it turned out that quite a few common refs were not yet marked
- so upload-pack would upload these

The reason is that git-rev-list would happily output parents of refs which were already acknowledged by upload-pack to be common refs.

I just sent out a patch which makes this irrelevant for the case that most or all of these heads are already fetched.

Now, to really solve the multi-head problem, which really is the problem "how to find the edges of the common commits", I propose the following:

For each remote ref known to be not in the local repository, find the 1st, 2nd, 4th, 8th, ... parents. Send these to upload-pack to be marked. For each ack'ed ref (i.e. remote side also has it), do a binary search to find the edge (i.e. the youngest common ref) on that DAG branch.

(To ease the burden on the server side, one coul mark only the edges as stop gaps for upload-pack. However, it might make things too complicated.)

Of course, the trick is to do that asynchronously, so that the network bandwidth is used optimally. This means that not each ack'ed ref leads to a binary search, but only those refs where no descendant was ack'ed.

BTW this does not need any change of the protocol. In fact, it only needs a change to fetch-pack.

I'd also increase MAX_HAS in upload-pack.

Ciao, Dscho