Why does this code cause Chrome to choke?

Question

I am trying to debug a problem in my app which I have narrowed down to a particular situation involving a regular expression which causes Chrome to choke! Trying the same code in Firefox works fine. Also if I reduce my 'sample' text to run the regex on it works too.

So what gives?

Here is the jsfiddle: http://jsfiddle.net/XWKRb/1/ (Which will fail to initialize at all because Chrome would choke if you are getting the same result as I am)

The code I have put in the jsfiddle is:

var rgx = /^(\d+([,|;]?\d*))*$/;
var sample = '40162690,40162755,40162691,40168355,40168357,40162726,40162752,40162729,40428707 ,40162740,40162546';
alert("Test is "+rgx.test(sample));

Maybe there is a better way to write my regular expression to avoid the issue? The goal is the regular expression should catch a string of numbers which are separated by comma or semi-colon.

Answer 1

You have a classic case of catastrophic backtracking:

^(\d+([,|;]?\d*))*$
    ^      ^  ^  ^
    |      |  |  ---- zero or more repetitions of the group 
    |      |  ------- zero or more digits
    |      ---------- zero or one comma, pipe or semicolon
    ----------------- one or more digits

contains a repeated group which contains optional elements, one of which is repeated itself. Ignoring the separators for now, you have essentially the regex

^(\d+\d*)*$

That leads to an exponential number of permutations your regex has to check in the worst case.

As soon as another character besides the allowed characters is found in your string (like a space in your example), the regex must fail - but it takes the engine ages to figure this out. Some browsers detect such runaway regex matches, but Chrome appears to want to ride this out.

To illustrate this, testing your regex in RegexBuddy shows the following:

Input             Steps to determine a non-match
1,1X                   23
12,21X                119
123,321X              723
1234,4321X          4,743
12345,54321X       31,991
123456,654321X    217,995
1234567,7654321X  attempt aborted after 1,000,000 steps

Answer 2

This pattern will work better:

var rgx = /^\d+(?:[,;]\s*\d+)*$/;