Subj : ?Javascript's regex engine and exponential matches with quantifiers
To   : netscape.public.mozilla.jseng
From : mszlazak@aol.com (Mszlazak)
Date : Thu Apr 17 2003 08:29 pm

When doing matchings with regular expression patterns that use two unlimited
quantifiers, one can run into problems like exponential (aka., eternal,
superlinear) matches. If a pattern contains an unlimited repeat inside a
subpattern that can itself be repeated an unlimited number of times can cause
failed matches to take a very long time. When this pattern

(?:\D+|<\d+>)*[!?]

matches, it runs quickly. However, if it's applied to

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

it theoretically should take a long time before reporting failure.

I've tried this in IE5.5 and it reports failure quickly. Also, I don't see a
rapid exponential increase in the time to report failure as I increase the size
of the string.

Is there some built in feature of Javascript regex engines that limits
"iterations of backtracking" in these kind of searches (eg. no more
"iterations" than characters in the target string).

.