Re: A note on merging conflicts..

From: Daniel Barkalow <barkalow@iabervon.org>
Date: Jul 1, 2006, 23:25 UTC
Message-ID: <Pine.LNX.4.64.0607011905030.9789@iabervon.org>
In-Reply-To: <Pine.LNX.4.64.0607011552170.12404@g5.osdl.org>

On Sat, 1 Jul 2006, Linus Torvalds wrote:

Show 24 quoted lines

> On Sat, 1 Jul 2006, Daniel Barkalow wrote:
> > 
> > I think a...b can be computed by (in pseudocode, obviously):
> 
> Nope.
> 
> > 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*