Re: remotes

From: Junio C Hamano <gitster@pobox.com>
Date: May 4, 2016, 08:11 UTC
Message-ID: <xmqq1t5ijl99.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <xmqqk2jajobz.fsf@gitster.mtv.corp.google.com>

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

Show 13 quoted lines

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

Show 18 quoted lines

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