From: Junio C Hamano Date: Fri, 11 Nov 2005 08:28:56 GMT Subject: Re: merge-base: fully contaminate the well. Message-ID: <7v8xvvr3jr.fsf@assigned-by-dhcp.cox.net> In-Reply-To: Linus Torvalds 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.