508542 - Extremely slow processing of a particular regular expression

Status: RESOLVED INVALID

(Core :: JavaScript Engine, defect)

Description

[Wladimir Palant]

An Adblock Plus user was complaining about his browser hanging. When I investigated this issue I discovered that he added a regular expression to his filter list that took extremely long to process. With everything unnecessary removed I got /(\D+)*\d+/ (note that "(\D+)*" was a more complicated expression originally and couldn't be optimized away). To reproduce this issue copy the following into the location bar of the browser:

javascript:/(\D+)*\d+/.test("foobarfoobarfoobarfoobar")

In my case this hangs Firefox for 10 seconds. Making the tested string longer causes the processing time to increase considerably, seems to be an exponential dependency. Reproduced with current Minefield nightly, Firefox 3.5.2 and Firefox 3.0.13 - not a regression.

Comment 1

[Bob Clary [:bc] (inactive)]

looks like an exponential regular expression to me. bug 452451 would help.

setting javascript.options.relimit to true causes the test to throw:

Error: regular expression too complex
Source File: javascript:/(\D+)*\d+/.test("foobarfoobarfoobarfoobar")
Line: 1

invalid?

Comment 2

[Wladimir Palant]

Yes, the original regular expression throws as well - but for some reason not when a content policy is using it. Well, invalid is fair enough I guess.

Comment 3

[Wladimir Palant]

Apparently, this pref only sets the relimit flag on JS environments belonging to a window. So setting the relimit flag on BackstagePass seems impossible - neither via the preference nor with something like window._options.relimit.

Comment 4

[Wladimir Palant]

Filed an enhancement request: bug 508553