Bug 51395 – Optimize regex patterns which contain empty alternatives

• Component: JavaScriptCore
• Status: RESOLVED INVALID

[Peter Varga]

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.

[Peter Varga]

Created attachment 77110 [details]
proposed patch

[Oliver Hunt]

Comment on attachment 77110 [details]
proposed patch

r=me, sorry for the delay in review.  Let's see if this still merges + compiles.

[WebKit Commit Bot]

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

[Peter Varga]

Landed in r76502.

[Gavin Barraclough]

This optimization is unsafe any will be reverted per: https://bugs.webkit.org/show_bug.cgi?id=60866