The time of matching those patterns wich contain empty alternatives can exponentially increase when we attempt to match the pattern in an iterative way. Eg.: /(a|b||){30}/ The fast/regex/slow.html tests this particular problem. The exponential increase of matching time can be avoided with a simple transformation: The empty alternatives should be removed from the pattern and the remaining alternatives should be grouped by a non-capturing parentheses which has a '?' quantifier. Eg.: /(a|b||)/ -> /((?:a|b)?)/ This conversion doesn't change the result of matching and the YARR generates simpler code (native or bytecode) to perform the matching.
Created attachment 77110 [details] proposed patch
Comment on attachment 77110 [details] proposed patch r=me, sorry for the delay in review. Let's see if this still merges + compiles.
Comment on attachment 77110 [details] proposed patch Rejecting attachment 77110 [details] from commit-queue. Failed to run "['./Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '--bot-id=eseidel-cq-sl', 'ap..." exit_code: 2 Last 500 characters of output: 0644 |--- Source/JavaScriptCore/yarr/RegexCompiler.cpp |+++ Source/JavaScriptCore/yarr/RegexCompiler.cpp -------------------------- No file to patch. Skipping patch. 1 out of 1 hunk ignored patching file LayoutTests/ChangeLog Hunk #1 succeeded at 1 with fuzz 3. patching file LayoutTests/fast/regex/script-tests/slow.js patching file LayoutTests/fast/regex/slow-expected.txt Failed to run "[u'/Projects/CommitQueue/Tools/Scripts/svn-apply', u'--reviewer', u'Oliver Hunt', u'--force']" exit_code: 1 Full output: http://queues.webkit.org/results/7613267
Landed in r76502.
This optimization is unsafe any will be reverted per: https://bugs.webkit.org/show_bug.cgi?id=60866