375642 - Another regexp that makes JS allocate >1GB and hang

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jesse Ruderman]

This makes the JavaScript engine allocate gobs of memory and hang for a while:

/(?:a??)+?/.exec("")

options("relimit") does not help.

Comment 1

[Joachim Rousseau]

With the following regexp :
var regexp= /^(?:[\w!#$%&'*+/=?^_`{|}~-]+\.?)*[\w!#$%&'*+/=?^_`{|}~]+@(?:(?:[a-z\d]+-?)*[a-z\d]+\.)+[a-z]{2,5}$/;

regexp.test("[e-mail]") returns true as expected, but regexp.test("test60%OffOnPanties.yeah-baby@yop.%reduction.com") hangs the javascript instead of returning false. The alert asking if you want to continue/debug/stop the script shows up.

(the used regexp is trying to validate email adress as specified in RFC3696 with a restrcition : "abc def@ghi"@example.com is not supported)

Is this the same bug ?

Comment 2

[Joachim Rousseau]

Please notice I have the bug on W2k/Firefox 2.0.0.3

Comment 3

[Brian Crowder]

Joachim:  Your bug is a different one, which has been resolved on the trunk.  Your regular expression is exponentially complex; on the trunk this issue is helped by a JavaScript option to throw an exception on expressions that are performing badly.

If your expression contains a structure like this:  (.*)*, then you probably have this problem.  Looking at your expression, it is possible you have used "*" characters in places where you meant to use "\*", and you are definitely doing this:  ([...]+)*, which is has the same non-linear performance characteristics as (.*)*.  You can and should refactor your expression to operate in linear time.  I was able to get better results with this:

js> "[e-mail]".match(/^(?:[\w!#$%&'\*+/=?^_`{|}~-\.]+)[\w!#$%&'*+/=?^_`{|}~]+@(?:(?:[a-z\d]+-?)*[a-z\d]+\.)+[a-z]{2,5}$/) 
[e-mail]

(essentially, I made the first parenthesized expression not have a "*" after it, and moved the \. inside the [] group).

Let me know if that works better for you.

Comment 4

[Brian Crowder]

The new expression does reject "test60%OffOnPanties.yeah-baby@yop.%reduction.com" and I think you intended, also.

Comment 5

[Brian Crowder]

Attachment: Yet another empty result, infinite loop

mrbkap:  Let me know when the running them on these gets boring.  Also added some assertions for fruity goodness.

Comment 6

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 260769 [details] [diff] [review]
Yet another empty result, infinite loop

Maybe it might be worth to investigate making REOP_EMPTY work after all?

Comment 7

[Brian Crowder]

No, I think the removal of REOP_EMPTY is a good optimization, and going back now is more pain than fixing the one or two more (if any?) endpoints like this that don't do the proper checking.

Comment 8

[Brian Crowder]

jsregexp.c: 3.145

Comment 9

[Bob Clary [:bc] (inactive)]

/cvsroot/mozilla/js/tests/ecma_3/RegExp/regress-375642.js,v  <--  regress-375642.js
initial revision: 1.1

Comment 10

[Bob Clary [:bc] (inactive)]

verified fixed 1.9.0 linux/mac* 2007-05-05