https://bugs.webkit.org/show_bug.cgi?id=60866
authorbarraclough@apple.com <barraclough@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 16 May 2011 09:08:07 +0000 (09:08 +0000)
committerbarraclough@apple.com <barraclough@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 16 May 2011 09:08:07 +0000 (09:08 +0000)
Evaluation order broken for empty alternatives in subpatterns

Rubber stamped by Geoff Garen.

Source/JavaScriptCore:

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

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

LayoutTests:

Reverted https://bugs.webkit.org/show_bug.cgi?id=51395, and added
test cases for /(|a)/ and /(a|)/, to test the evaluation order of
subpattern matches with empty alternatives.

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

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@86547 268f45cc-cd09-0410-ab3c-d52691b4dbfc

LayoutTests/ChangeLog
LayoutTests/fast/regex/parentheses-expected.txt
LayoutTests/fast/regex/script-tests/parentheses.js
LayoutTests/fast/regex/script-tests/slow.js
LayoutTests/fast/regex/slow-expected.txt
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/yarr/YarrPattern.cpp

index cff8bd2..cf58f9c 100644 (file)
@@ -1,3 +1,19 @@
+2011-05-16  Gavin Barraclough  <barraclough@apple.com>
+
+        Rubber stamped by Geoff Garen.
+
+        https://bugs.webkit.org/show_bug.cgi?id=60866
+        Evaluation order broken for empty alternatives in subpatterns
+
+        Reverted https://bugs.webkit.org/show_bug.cgi?id=51395, and added
+        test cases for /(|a)/ and /(a|)/, to test the evaluation order of
+        subpattern matches with empty alternatives.
+
+        * fast/regex/parentheses-expected.txt:
+        * fast/regex/script-tests/parentheses.js:
+        * fast/regex/script-tests/slow.js:
+        * fast/regex/slow-expected.txt:
+
 2011-05-16  Alejandro G. Castro  <alex@igalia.com>
 
         Skipped failing test, the fail already has a bug:
index 6f665c1..739f9b3 100644 (file)
@@ -91,6 +91,8 @@ PASS 'Hi Bob'.match(regexp52) is ['Bob',undefined,'Bob',undefined,undefined]
 PASS regexp53.exec('#') is ['',undefined,'']
 PASS regexp54.exec('#') is ['','',undefined,undefined,'']
 PASS regexp55.exec('#') is ['','']
+PASS regexp56.exec('a') is ['','']
+PASS regexp57.exec('a') is ['a','a']
 PASS successfullyParsed is true
 
 TEST COMPLETE
index 5ed9fc5..6a4c3e7 100644 (file)
@@ -240,5 +240,11 @@ shouldBe("regexp54.exec('#')", "['','',undefined,undefined,'']");
 var regexp55 = /(?:(?:(?:a?|(?:))((?:)))|a?)/m;
 shouldBe("regexp55.exec('#')", "['','']");
 
+// Test evaluation order of empty subpattern alternatives.
+var regexp56 = /(|a)/;
+shouldBe("regexp56.exec('a')", "['','']");
+var regexp57 = /(a|)/;
+shouldBe("regexp57.exec('a')", "['a','a']");
+
 var successfullyParsed = true;
 
index 83ccb91..54b6b81 100644 (file)
@@ -2,6 +2,6 @@ description(
 'Test for expressions that would hang when evaluated due to exponential matching behavior. If the test does not hang it is a success.'
 );
 
-shouldBe('/(?:[^(?!)]||){23}z/.test("/(?:[^(?!)]||){23}z/")', 'true');
+shouldBe('/(?:[^(?!)]||){23}z/.test("/(?:[^(?!)]||){23}z/")', 'false');
 
 var successfullyParsed = true;
index d238a83..105f24f 100644 (file)
@@ -3,7 +3,7 @@ Test for expressions that would hang when evaluated due to exponential matching
 On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
 
 
-PASS /(?:[^(?!)]||){23}z/.test("/(?:[^(?!)]||){23}z/") is true
+PASS /(?:[^(?!)]||){23}z/.test("/(?:[^(?!)]||){23}z/") is false
 PASS successfullyParsed is true
 
 TEST COMPLETE
index 9d3fc98..ef13bfc 100644 (file)
@@ -1,3 +1,15 @@
+2011-05-16  Gavin Barraclough  <barraclough@apple.com>
+
+        Rubber stamped by Geoff Garen.
+
+        https://bugs.webkit.org/show_bug.cgi?id=60866
+        Evaluation order broken for empty alternatives in subpatterns
+
+        Reverting https://bugs.webkit.org/show_bug.cgi?id=51395
+
+        * yarr/YarrPattern.cpp:
+        (JSC::Yarr::YarrPatternConstructor::atomParenthesesEnd):
+
 2011-05-15  Gavin Barraclough  <barraclough@apple.com>
 
         Reviewed by Geoff Garen & Michael Saboff.
index 5913f7e..8436712 100644 (file)
@@ -491,19 +491,8 @@ public:
 
         unsigned numParenAlternatives = parenthesesDisjunction->m_alternatives.size();
         unsigned numBOLAnchoredAlts = 0;
-        bool containsEmptyAlternative = false;
 
         for (unsigned i = 0; i < numParenAlternatives; i++) {
-            if (!parenthesesDisjunction->m_alternatives[i]->m_terms.size() && numParenAlternatives > 1) {
-                PatternAlternative* altToRemove = parenthesesDisjunction->m_alternatives[i];
-                parenthesesDisjunction->m_alternatives.remove(i);
-                delete altToRemove;
-                --numParenAlternatives;
-
-                containsEmptyAlternative = true;
-                continue;
-            }
-
             // Bubble up BOL flags
             if (parenthesesDisjunction->m_alternatives[i]->m_startsWithBOL)
                 numBOLAnchoredAlts++;
@@ -518,28 +507,6 @@ public:
 
         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;
-        }
     }
 
     void atomBackReference(unsigned subpatternId)