| Summary: | Optimize regex patterns which contain empty alternatives | ||||||
|---|---|---|---|---|---|---|---|
| Product: | WebKit | Reporter: | Peter Varga <pvarga> | ||||
| Component: | JavaScriptCore | Assignee: | Nobody <webkit-unassigned> | ||||
| Status: | RESOLVED INVALID | ||||||
| Severity: | Normal | CC: | abecsi, barraclough, commit-queue, msaboff | ||||
| Priority: | P2 | ||||||
| Version: | 528+ (Nightly build) | ||||||
| Hardware: | All | ||||||
| OS: | All | ||||||
| Attachments: |
|
||||||
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 This optimization is unsafe any will be reverted per: https://bugs.webkit.org/show_bug.cgi?id=60866 |
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.