Re: [RFH] revision limiting sometimes ignored

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 5, 2008, 07:14 UTC
Message-ID: <7vir13g9hx.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <alpine.LFD.1.00.0802041223080.3034@hp.linux-foundation.org>

Linus Torvalds <torvalds@linux-foundation.org> writes:

Show 17 quoted lines

> On Mon, 4 Feb 2008, Linus Torvalds wrote:
>> 
>> Gaah. This is that stupid apporach.
>
> .. and it won't actually solve the problem you pointed to. It's not enough 
> that the positive commits should be connected to the negative ones, the 
> problem is that no negative ones could possibly connect to the positives. 
>
> So scratch that patch as broken too. 
>
> Really annoying. It does look like we really want to check the *totally* 
> connected case, and we simply cannot do the "two unconnected trees" 
> decision case without traversing both trees fully (since we won't know 
> that they are *really* unconnected until we do).
>
> And that seems really quite expensive. I wonder if I've missed something 
> again.

I tend to agree. In a totally connected history, the upper bound we would need to traverse is down to the merge base of still positive commits in the "newlist" and negative ones still on the "list" when everybody on list becomes uninteresting. And if there are two unrelated histories, that traversal will need to traverse down to respective roots.

Which sucks.