[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 #4 from Yang Tian <nwu_ty at 163.com> ---
(In reply to Michael Saboff from comment #2)
> 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.

Can I solve this problem by modifing the loop limit myself? If so, please tell me what should i do. If not, Can i treat this as a bug of JSC Regex engine?

-- 
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/20190730/f8441c73/attachment.html>