[Webkit-unassigned] [Bug 51395] New: Optimize regex patterns which contain empty alternatives

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=51395

           Summary: Optimize regex patterns which contain empty
                    alternatives
           Product: WebKit
           Version: 528+ (Nightly build)
          Platform: All
        OS/Version: All
            Status: UNCONFIRMED
          Severity: Normal
          Priority: P2
         Component: JavaScriptCore
        AssignedTo: webkit-unassigned at lists.webkit.org
        ReportedBy: pvarga at inf.u-szeged.hu
                CC: barraclough at apple.com, abecsi at webkit.org,
                    msaboff at apple.com


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.

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.