Bug 51395 - Optimize regex patterns which contain empty alternatives
Summary: Optimize regex patterns which contain empty alternatives
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Nobody
Depends on:
Reported: 2010-12-21 07:07 PST by Peter Varga
Modified: 2011-05-15 19:29 PDT (History)
4 users (show)

See Also:

proposed patch (6.06 KB, patch)
2010-12-21 07:11 PST, Peter Varga
oliver: review+
commit-queue: commit-queue-
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
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