[Users] [PATCH 2/3] Do not allow search cost to explode in case of bad message parsing in textview_make_clickable_parts_later();

Igor Mammedov imammedo at redhat.com
Thu Oct 25 16:42:30 CEST 2012

On Thu, 25 Oct 2012 12:24:20 +0200
Colin Leroy <colin at colino.net> wrote:

> Hi,
> > Searching all patterns inside for(walk) loop in worst case could lead
> > to an expontential like search cost if 'walk' is incremented by a
> > character on each iteration. Rewriting pattern loop from inner to
> > outer loop will fix issue and yeld only O(n) complexity.
> Just FYI, this one caused issues with http://www.example.com links,
> because two parsers match this (http:// and www.). That made two URIs.
> I've fixed it by testing than the current match is not a sub-match of
> the previous (prev->bp < cur->bp && prev->ep == cur->ep), see cvs107.

I've doubts about this patch written in cover letter, that seems haven't made
to list:
>> I'm not sure if [2/3] patch is totally correct, because of I've dropped
>> "tmp < scanpos" so changing ordering from sorted by position to sorted by pattern.
>> Hope someone knows better how it should work and can fix next block if necessary.
So there might be another issues caused by change.


More information about the Users mailing list