696723 - Exponential regular expressions no longer throw an exception

Status: RESOLVED DUPLICATE of bug 1391654

(Core :: JavaScript Engine, defect)

Description

[Wladimir Palant]

It seems that the regexp engine no longer recognizes exponential regular expressions. Bug 330569 introduced javascript.options.relimit preference but searching the current source code I only see code that translates that preference into a JS environment option, nothing that would actually use that option afterwards. I suspect that it is unused ever since SpiderMonkey switched to the YARR engine.

Consider the following code:

/a*a*a*a*a*a*a*b/.test("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");

In Firefox 3.6 it throws "regular expression too complex" exception. In Firefox 7.0.1 and 10.0a1 (both on Windows 7 x64) it simply hangs for a while and will hang much longer as the tested string gets longer.

Comment 1

[Jason Orendorff [:jorendorff]]

Slow regexp searches should time out just as ordinary JS code times out.

The old "regular expression too complex" exception was a neat trick, but that's not how we want it to work.

The relimit pref is obsolete and should be removed.

Comment 2

[Wladimir Palant]

(In reply to Jason Orendorff [:jorendorff] from comment #1)
> Slow regexp searches should time out just as ordinary JS code times out.

Would be nice but doesn't seem to happen here...

Comment 3

[:Benjamin Peterson]

Safari also hangs on this regular expression.

Comment 5

[Andrei Purice]

Hey Wladimir,
Does this issue still occur for you or can it be closed?

Comment 6

[Wladimir Palant]

Yes, this is still problematic. The delay isn’t noticeable with the short string I posted in comment 0 but a test string twice as long hangs up the content process for around 20 seconds:

/a*a*a*a*a*a*a*b/.test("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");

Comment 7

[Iain Ireland [:iain]]

Bug 1391654 tracks potential solutions for exponential blowup of regexp execution.