Comment #24 on issue 430 by e...@wix.com: Regex hardlock
http://code.google.com/p/v8/issues/detail?id=430
Hi,
I've reduced this problem to:
var regx = new RegExp('^(\\w+)*[^\\w]$');
regx.test('aaaaaaaaaaaaaaaaaaaaaaaaaa'); //chrome will crash
In other words, when you have a repeat of something 1 -> infinity times,
and this group is repeated 0->infinity times, and the next match is for
anything not in the group (obviously your next character wouldn't be one
from the previous group... but I put [^w] just to illustrate), then chrome
will keep recursion to search for a possible group of (1->n) which repeats
(0->m) times which has that letter matching.
Almost like it's checking all possible n!/((n-m)!m!) groups which can
possibly match... but obviously none can match in the above case
Therefore, internally, the regex should first be run 'greedily' to check if
there's a possible match by making sure required letters are there.
Essentially, if I were to write the implementation for a regex, when
encountering such a group, I would internally be doing this:
var regx = new RegExp('^(?=\w*[^\w])(?:\w+)*[^\w]$');
regx.test('aaaaaaaaaaaaaaaaaaaaaaaaaa'); //chrome will not crash
because first I'm doing a positive lookahead to check if this is even
possible... though the complexity for this rises as the nested groups
become more complex
To generalize, I think chrome should make a more 'general' case of each
group first, by making the smallest expanded group which includes all
possible scenarios of the inner group, meaning that (?:a+-?)*b can only
match if (?:a-?)*b can match, and then doing (?=(?:a-?)*b) first internally
on the more general group.
By the way, to fix the regexes which are crashing, currently it's enough to
rewrite as I did above, since here (a+-?)*b === (a-?)*b
Finally, another way to look at this is that it's also possible that people
are just abusing regexes, and correctly written regexes would not have
caused chrome to crash to begin with.
--
You received this message because this project is configured to send all
issue notifications to this address.
You may adjust your notification preferences at:
https://code.google.com/hosting/settings
--
--
v8-dev mailing list
v8-dev@googlegroups.com
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to v8-dev+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
