From: Justin Collins <justincollins@...>
Date: 2013-02-23T03:41:12+09:00
Subject: Re: Questionable regex performance when using lazy matching and inverted character classes

On 02/22/2013 07:24 AM, Tikhon B. wrote:
> Robert Klemme wrote in post #1098439:
>> So, yes, there is a cost for backtracking involved, but it only shows
>> only in particular situations:
>> - large inputs
>> - specific expressions (absence of anchoring, using unlimited
>> repetition operators vs. limited (e.g. /a{0,10}/).
>>
>> The phenomenon is well known with regular expression engines I
>> believe.  The cases you mention seem to be rather the exception than
>> the common state of affairs.  Which doesn't mean that Ruby's engine
>> cannot be improved.  I just don't think it's not that dramatic an
>> issue.
>>
>> Kind regards
>>
>> robert
>
> I took another look at the anchors ruby provides, and I found that the
> \G anchor actually solves the issue outlined in this particular example
> as it applies in my real use case to my satisfaction.
>
> I'm still a bit unsettled that there is such a caveat to consider when
> writing a relatively benign expression. However, given what the symptoms
> of the problem imply about the engine design, I suspect fixing the issue
> would take quite a bit of either hackery, or a fair amount of re-design.
>
> I'll chalk it up to yet another one of those strange landmines you
> encounter in ruby every once in a while.
>
> Thanks,
>
> Tikhon
>

You might be interested in the following pages:

https://en.wikipedia.org/wiki/ReDoS
http://www.regular-expressions.info/catastrophic.html


-Justin