Changeset 76502 in webkit

Timestamp:

Jan 24, 2011 3:52:43 AM (13 years ago)

Author:

pvarga@webkit.org

Message:

2011-01-24 Peter Varga <​pvarga@inf.u-szeged.hu>

Reviewed by Oliver Hunt.

Optimize regex patterns which contain empty alternatives
​https://bugs.webkit.org/show_bug.cgi?id=51395

Eliminate the empty alternatives from the regex pattern and convert it to do
the matching in an easier way.

• fast/regex/script-tests/slow.js:
• fast/regex/slow-expected.txt:

2011-01-24 Peter Varga <​pvarga@webkit.org>

Reviewed by Oliver Hunt.

Optimize regex patterns which contain empty alternatives
​https://bugs.webkit.org/show_bug.cgi?id=51395

Eliminate the empty alternatives from the regex pattern and convert it to do
the matching in an easier way.

• yarr/YarrPattern.cpp: (JSC::Yarr::YarrPatternConstructor::atomParenthesesEnd):

Location:

trunk

Files:

• LayoutTests/ChangeLog (modified) (1 diff)
• LayoutTests/fast/regex/script-tests/slow.js (modified) (1 diff)
• LayoutTests/fast/regex/slow-expected.txt (modified) (1 diff)
• Source/JavaScriptCore/ChangeLog (modified) (1 diff)
• Source/JavaScriptCore/yarr/YarrPattern.cpp (modified) (2 diffs)

trunk/LayoutTests/ChangeLog

@@ +1 @@
+2011-01-24  Peter Varga  <pvarga@inf.u-szeged.hu>
+
+        Reviewed by Oliver Hunt.
+
+        Optimize regex patterns which contain empty alternatives
+        https://bugs.webkit.org/show_bug.cgi?id=51395
+
+        Eliminate the empty alternatives from the regex pattern and convert it to do
+        the matching in an easier way.
+
+        * fast/regex/script-tests/slow.js:
+        * fast/regex/slow-expected.txt:
+
 2011-01-24  Pavel Podivilov  <podivilov@chromium.org>
 

trunk/LayoutTests/fast/regex/script-tests/slow.js

@@ -3 +3 @@
 );
 
-shouldBe('/(?:[^(?!)]||){23}z/.test("/(?:[^(?!)]||){23}z/")', 'false');
+shouldBe('/(?:[^(?!)]||){23}z/.test("/(?:[^(?!)]||){23}z/")', 'true');
 
 var successfullyParsed = true;

trunk/LayoutTests/fast/regex/slow-expected.txt

@@ -4 +4 @@
 
 
-PASS /(?:[^(?!)]||){23}z/.test("/(?:[^(?!)]||){23}z/") is false
+PASS /(?:[^(?!)]||){23}z/.test("/(?:[^(?!)]||){23}z/") is true
 PASS successfullyParsed is true
 

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2011-01-24  Peter Varga  <pvarga@webkit.org>
+
+        Reviewed by Oliver Hunt.
+
+        Optimize regex patterns which contain empty alternatives
+        https://bugs.webkit.org/show_bug.cgi?id=51395
+
+        Eliminate the empty alternatives from the regex pattern and convert it to do
+        the matching in an easier way.
+
+        * yarr/YarrPattern.cpp:
+        (JSC::Yarr::YarrPatternConstructor::atomParenthesesEnd):
+
 2011-01-24  Andras Becsi  <abecsi@webkit.org>
 

trunk/Source/JavaScriptCore/yarr/YarrPattern.cpp

@@ -489 +489 @@
 
         PatternTerm& lastTerm = m_alternative->lastTerm();
-        
+
         unsigned numParenAlternatives = parenthesesDisjunction->m_alternatives.size();
         unsigned numBOLAnchoredAlts = 0;
-        // Bubble up BOL flags
+        bool containsEmptyAlternative = false;
+
         for (unsigned i = 0; i < numParenAlternatives; i++) {
+            if (!parenthesesDisjunction->m_alternatives[i]->m_terms.size() && numParenAlternatives > 1) {
+                parenthesesDisjunction->m_alternatives.remove(i);
+                --numParenAlternatives;
+
+                containsEmptyAlternative = true;
+                continue;
+            }
+
+            // Bubble up BOL flags
             if (parenthesesDisjunction->m_alternatives[i]->m_startsWithBOL)
                 numBOLAnchoredAlts++;
         }
-        
+
         if (numBOLAnchoredAlts) {
             m_alternative->m_containsBOL = true;
@@ -504 +514 @@
                 m_alternative->m_startsWithBOL = true;
         }
-        
+
         lastTerm.parentheses.lastSubpatternId = m_pattern.m_numSubpatterns;
         m_invertParentheticalAssertion = false;
+
+        if (containsEmptyAlternative) {
+            // Backup and remove the current disjunction's alternatives.
+            Vector<PatternAlternative*> alternatives;
+            alternatives.append(parenthesesDisjunction->m_alternatives);
+            parenthesesDisjunction->m_alternatives.clear();
+            PatternAlternative* alternative = parenthesesDisjunction->addNewAlternative();
+
+            // Insert a new non-capturing parentheses.
+            unsigned subpatternId = m_pattern.m_numSubpatterns + 1;
+            PatternDisjunction* newDisjunction = new PatternDisjunction(alternative);
+            m_pattern.m_disjunctions.append(newDisjunction);
+            alternative->m_terms.append(PatternTerm(PatternTerm::TypeParenthesesSubpattern, subpatternId, newDisjunction, false, false));
+            newDisjunction->m_alternatives.append(alternatives);
+
+            // Set the quantifier of the new parentheses to '?' and set the inherited properties.
+            PatternTerm& disjunctionTerm = alternative->lastTerm();
+            disjunctionTerm.quantify(1, QuantifierGreedy);
+            disjunctionTerm.parentheses.lastSubpatternId = m_pattern.m_numSubpatterns;
+            alternative->m_containsBOL = m_alternative->m_containsBOL;
+            alternative->m_startsWithBOL = m_alternative->m_startsWithBOL;
+        }
     }