Bug 51395

Summary: Optimize regex patterns which contain empty alternatives
Product: WebKit Reporter: Peter Varga <pvarga>
Component: JavaScriptCoreAssignee: Nobody <webkit-unassigned>
Severity: Normal CC: abecsi, barraclough, commit-queue, msaboff
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: All   
OS: All   
Description Flags
proposed patch oliver: review+, commit-queue: commit-queue-

Description Peter Varga 2010-12-21 07:07:23 PST
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.
Comment 1 Peter Varga 2010-12-21 07:11:05 PST
Created attachment 77110 [details]
proposed patch
Comment 2 Oliver Hunt 2011-01-20 17:06:02 PST
Comment on attachment 77110 [details]
proposed patch

r=me, sorry for the delay in review.  Let's see if this still merges + compiles.
Comment 3 WebKit Commit Bot 2011-01-20 17:23:43 PST
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:
|--- 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
Comment 4 Peter Varga 2011-01-24 04:16:47 PST
Landed in r76502.
Comment 5 Gavin Barraclough 2011-05-15 19:29:51 PDT
This optimization is unsafe any will be reverted per: https://bugs.webkit.org/show_bug.cgi?id=60866