Re: merge-base: fully contaminate the well.

From: Junio C Hamano <junkio@cox.net>
Date: Nov 11, 2005, 08:28 UTC
Message-ID: <7v8xvvr3jr.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <Pine.LNX.4.64.0511102125510.4627@g5.osdl.org>

Linus Torvalds <torvalds@osdl.org> writes:

> Btw, I don't think your contamination logic is necessarily complete. We 
> may not even have parsed some of the commits that end up being on that 
> strange corner case....

You are right.  And the situation seems really bad.

The full-contaminator is not full at all, and fails miserably in not so pathlogical case. If we have something like this:

	1	2	List		A B C D E F G
	F	E	F1 E2		- - - - 2 1 -
        |\     /|	G1 E2 D1 C1	- - 1 1 2 1 1
        \ \   / |	E2 D1 C1	- - 1 1 2 1 1
        |\  D  /|	G3 D3 C3	- - 3 3 2 1 3
        | \ | / |	D3 C3		- - 3 3 2 1 3
        |   C   |	C7		- - 7 3 2 1 3
        |   |   |
        |   B   |
        |   |   /
         \  A  /
          \ | /
            G

we would end up finding D and G and stop there, without ever seeing A or B. B _might_ be touched when we look at C at the last round, but there is no way for us to find G is reachable from D (or C) without parsing more than what we parsed in the main loop.

The worst part of this is that you can indefinitely extend C-B-A chain trivially, and all it takes is the one, initial commit G, that has a screwed-up timestamp. All the other commits in this example are in the right time order. Very sad.