Re: remotes

Junio C Hamano [off-list ref] 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.