Re: Comments on recursive merge..

From: Linus Torvalds <torvalds@osdl.org>
Date: Nov 9, 2005, 23:34 UTC
Message-ID: <Pine.LNX.4.64.0511091518370.4627@g5.osdl.org>
In-Reply-To: <7virv1a0ro.fsf@assigned-by-dhcp.cox.net>

On Wed, 9 Nov 2005, Junio C Hamano wrote:

Show 23 quoted lines

> Linus Torvalds <torvalds@osdl.org> writes:
> 
> >> 
> >>                  H
> >>                 / \
> >>            G   A   \
> >>            |\ /     \ 
> >>            | B       \
> >>            |  \       \
> >>             \  C       F
> >>              \  \     / 
> >>               \  D   /   
> >>                \ |  /
> >>                 \| /
> >> 		   E
> >> 
> > So I think from a correctness standpoint, the only thing that matters is 
> > "git-merge-base --all", and anything that doesn't know to return both E 
> > and B looks potentially buggy.
> 
> But the point of well-poisoning you did in merge-base was to
> detect that E is an ancestor of B and exclude it in the first
> place.

Ahh, you're right, and I'm wrong. That "E" is not a real merge-base, since there _is_ a valid merge-base that is a direct descendant of it and thus objectively better.

And as to why git-merge-base returns E in the first place: it really shouldn't, but when it sees B, it can decide that C is uninteresting, and so there are no interesting commits left. So it never continues to walk D and thus never notices that D covers E and E is _also_ uninteresting.

So it thinks both E and B are interesting, and since E has a more recent date, it will select that one when only showing one (and then show both when asked to).

> I however do not see merge-base trying to take that into account
> and treat E differently from C and D in any way.

It doesn't. git-merge-base simply walks the chain in as close to date order as it can, and when it decides that the rest of the chain is provably uninteresting, it stops.

Which means that sometimes it can stop with too _many_ merge heads, just because it hasn't realized that they are reachable through a chain that is otherwise provably uninteresting.

This is because we define "uninteresting" as meaning "cannot reach any more _new_ merge-heads". Which is true. The fact that such a chain could reach some heads we found earlier and mark them as being pointless never enters the picture ;)

> I agree we should try to stay away from "heuristic" and make
> things safer, but after seeing the above, I'd need a bit more
> time to convince myself that what 'git-merge-base --all' does is
> *the* safe approach.

Well, "git-merge-base --all" will be "safer" in the sense that it's guaranteed to give a superset of the merge-heads (which itself is "safe" in that it flags potentially interesting cases early).

Then, the recursive merge strategy could notice (in fact, _will_ notice, if it tries to merge the merge-heads) that the merge of such a pair of merge-heads is one of the heads itself (just a fast-forward), and thus the recursive strategy should correctly have chosen "B" as the merge-head.

So yes, "git-merge-base --all" really is safe. Sometimes (under fairly odd circumstances) a bit unnecessarily conservative, but always safe.

> Right now, it looks to me that both are heuristic that work most of the 
> time (merge-base --all 99.99999% of the time, show-branch 99% of the 
> time, or something like that).

The thing is, I don't see what guarantees that the show-branch brhaviour is safe or conservative. It happened to pick B in this case, which was the right choice, but I don't see how that was anything but just luck and happenstance.

IOW, I can see that "git-merge-base --all" can return some unnecessary heads, but I can also argue for how that becomes safe and fixes itself. With git-show-branch --merge-base, I don't know what that argument is, because I can't see how it _guarantees_ that it would always pick B over E.

			Linus