On Sat, 1 Jul 2006, Linus Torvalds wrote:

quoted text
> 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.

quoted text
> 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*
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html