Re: A note on merging conflicts..

From: Linus Torvalds <torvalds@osdl.org>
Date: 2006-07-02 08:57:42
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).

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
Received on Sun Jul 02 08:58:31 2006

This archive was generated by hypermail 2.1.8 : 2006-07-02 08:58:59 EST