Re: remotes

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

Stefan Beller <sbeller@google.com> writes:

> A recent addition is the check for unrelated histories via
> checking for added root commits (i.e. commits with no parent) and
> refusing to merge them by default.  you need to pass
> --allow-unrelated-histories to merge.
>
> see
> https://kernel.googlesource.com/pub/scm/git/git/+/e379fdf34fee96cd205be83ff4e71699bdc32b18

That commit however is not about "checking for added root commits",
which would be way more expensive to compute.  That commit is merely
about detecting that the other history does not have _any_ relation
to ours.

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

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