[Webkit-unassigned] [Bug 200190] JavaScriptCore's Regex can't match the content.

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=200190

--- Comment #2 from Michael Saboff <msaboff at apple.com> ---
This is technically a bug in the JSC Regex engine.  The JSC regex engine is a backtracking matcher that can execute in polynomial time for certain expressions.  The engine has a loop limit that will fail if a match isn't found after 1,000,000 iterations.

The test regular expression when applied to str1 is hitting that 1,000,000 loop iteration limit due to the 2 ".*" components of the regular expression.  I increased the limit and the test case requires 1,034,633 loop iterations to match.  This high loop count is needed because the ".*" will match all non-newline characters including the 'd' you are looking for and go past them to the end of the string.  Then the matcher backtracks one character and tries matching the rest of the pattern.  It keeps on doing this until it determines there is a match or not.  The addition of the second ".*" makes this regular expression quadratic in the JSC matcher.  Matching str2, which is slightly shorter, matches in 921,193 loop iterations.

If you are looking for 5 or more 'd' characters with 0 or more non-'d' characters in between, I suggest that you change the pattern to something like /([^d]*d[^d]*){5,}/.  This pattern matches in 7 loop iterations of the matcher, thus performing 150,000x faster than the original regular expression.  This pattern will be faster on all JavaScript engines.  You could also eliminate the second ".*", /(.*d){5,}/ or move it to the end of the expression, /(.*d){5,}.*/, both of these cases will take 59 iterations through the matcher loop.

If we double the loop limit to 2,000,000 iterations, the test regex will only be able to match a string ~10 characters longer before hitting the limit.

-- 
You are receiving this mail because:
You are the assignee for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-unassigned/attachments/20190729/5ee49b94/attachment-0001.html>