Re: A note on merging conflicts..

On Sat, 1 Jul 2006, Linus Torvalds wrote:

On Sat, 1 Jul 2006, Daniel Barkalow wrote:

quoted

I think a...b can be computed by (in pseudocode, obviously):

Nope.

quoted

It's basically the original merge-bases code, from way back;

And it has basically the same bug.

It is possible to have

		a
	       / \
	      b   c
	      |\ /|
	      d e f
	       \|/
		g

and clearly "e" is the only valid merge-base of b and c.

HOWEVER. It's actually possible that we traverse d, f and g before we even 
look at 'e' (because somebody had a bogus date, and 'e' _looks_ old).

But that wouldn't actually affect b...c, because we don't actually care 
that 'e' is the correct merge-base and 'g' is not, because "b c ^e ^g" is 
the same as "b c ^e".

Your point is correct, though; if we look at e before c, we could think 
that it's interesting when it isn't, so we have to wait until we've 
drained the list to output anything.

So that's why git-merge-base has all that extra "unnecessary" complexity. 
You cannot output anything at all until you've guaranteed that all pending 
objects are uninteresting.

That's not all the complexity in git-merge-base, though. There's a ton 
more that's about why e is right and g is wrong in your example, and we 
don't care about *that* part in b...c.

Actually, I think that it would work to have object flags "LEFT" and 
"RIGHT", mark b with left, mark c with right, and mark anything with both 
LEFT and RIGHT as UNINTERESTING as we go through the revisions. The 
time-ordering problem with symmetric difference isn't absent with regular 
difference, and, assuming that b..c works in the tricky cases, the same 
logic should handle symmetric difference.

	-Daniel
*This .sig left intentionally blank*