Re: remotes

[Junio C Hamano <gitster@pobox.com>]

Junio C Hamano <gitster@pobox.com> writes:

> The difference is in this sequence.
>
>  (1) Alice owns the canonical history.
>  (2) Bob copies Alice's tip tree without history, starts a
>      different root, and builds some history.
>  (3) Alice builds some more history.
>  (4) Bob pulls from Alice.  The check in e379fdf3 triggers here, but
>      Bob can override it.
>  (5) Alice builds even more history.
>  (6) Bob also builds even more history.
>  (7) Bob asks Alice to pull from him.
>  (8) Alice pulls from Bob.  The common ancestor discovery finds the
>      merge base between (4) and (5), which is (3).

Correction.  That merge-base is between (6) and (5); I renumbered
the steps while writing the document and failed to update the
reference.

>     ---(1)---(3)---(5)---(8)
>                 \        /
>           (2)---(4)---(6)
>
> The history traversal is done at (8) to find merge-base for two
> purposes.  One is to find the common ancestor to use in 3-way merge,
> and the other is for the check introduced by e379fdf3.  It stops at
> finding (3), and does not traverse the history all the way down to
> (2).  But in order for Alice to notice that the merge would pull a
> new root Alice never has seen, i.e. (2), a traversal needs to
> continue down to the root of other's history.
>
> Naively, it would be running
>
> 	rev-list --max-parents=0 ^HEAD MERGE_HEAD
>
> and see if the result is not empty, in which case you found (2).
> But that is way too expensive unless (2) is relatively shallow.

A not-so-naive optimization Linus alluded to in the discussion that
was a tangent of e379fdf3 was to teach unpack-objects and index-pack
to report when they see any root commits in the payload.  When Alice
pulls from Bob at (8), one of these two programs would already be
examining every object received from Bob's history, and they can
notice the presense of (2), a new root commit, and report it to the
caller with minimum additional cost.

Unfortunately that approach will not work in the general case of
"fetch to examine first and then decide to merge" workflow, as there
is no medium the first step, i.e. "fetch", can use to convey the
fact that it saw a new root to the later step, i.e. "merge".  Doubly
unfortunate is that "git pull" is in fact implemented in terms of
handling that general case.  We _might_ be able to futz with the
file format used in FETCH_HEAD to help "git pull", but that would
not help a true user-space "git fetch $there master:there/master"
followed by "git merge there/master" workflow.