Re: [RFH] revision limiting sometimes ignored

[Junio C Hamano <gitster@pobox.com>]

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

> 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.