Re: A note on merging conflicts..

From: Linus Torvalds <torvalds@osdl.org>
Date: Jul 1, 2006, 22:57 UTC
Message-ID: <Pine.LNX.4.64.0607011552170.12404@g5.osdl.org>
In-Reply-To: <Pine.LNX.4.64.0607011754370.9789@iabervon.org>

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