Re: Comments on recursive merge..

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

Linus Torvalds [off-list ref] writes:

quoted

quoted

                 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