On Sat, 1 Jul 2006, Daniel Barkalow wrote:
quoted text
> 
> I think a...b can be computed by (in pseudocode, obviously):

Nope.

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

Remember: in a distributed system we have no global clock, so any graph 
traversal ordering we choose is by definition always arbitrary, even 
though we can obviously _try_ to choose one that is efficient in practice 
(ie the "sort the heap by date).

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.

				Linus
-
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