Bug 691299: Lower maximum quantifier. (r=dmandelin, a=akeybl)
authorChris Leary <cdleary@mozilla.com>
Tue, 29 Nov 2011 15:24:44 -0800
changeset 79265 7709a40b7919b19d2e2620b9c1075ef060227d95
parent 79264 a2aab866a09b7c92a43a72b7a6e59b9c54ad506d
child 79266 92f39c8a9cf399c4e10e32665a1cdc8600a452d9
push id78
push userclegnitto@mozilla.com
push dateFri, 16 Dec 2011 17:32:24 +0000
treeherdermozilla-release@79d24e644fdd [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdmandelin, akeybl
bugs691299
milestone9.0
Bug 691299: Lower maximum quantifier. (r=dmandelin, a=akeybl)
js/src/jit-test/tests/basic/bug691299-regexp.js
js/src/yarr/YarrParser.h
js/src/yarr/YarrPattern.cpp
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/basic/bug691299-regexp.js
@@ -0,0 +1,3 @@
+// |jit-test| error: SyntaxError: invalid quantifier
+
+String.fromCharCode(256).replace(/[^a$]{4294967295}/,"aaaa");
--- a/js/src/yarr/YarrParser.h
+++ b/js/src/yarr/YarrParser.h
@@ -517,16 +517,21 @@ private:
      *
      * Helper for parseTokens(); checks for parse errors and non-greedy quantifiers.
      */
     void parseQuantifier(bool lastTokenWasAnAtom, unsigned min, unsigned max)
     {
         ASSERT(!m_err);
         ASSERT(min <= max);
 
+        if (min == unsigned(-1)) {
+            m_err = QuantifierTooLarge;
+            return;
+        }
+
         if (lastTokenWasAnAtom)
             m_delegate.quantifyAtom(min, max, !tryConsume('?'));
         else
             m_err = QuantifierWithoutAtom;
     }
 
     /*
      * parseTokens():
--- a/js/src/yarr/YarrPattern.cpp
+++ b/js/src/yarr/YarrPattern.cpp
@@ -617,17 +617,17 @@ public:
         }
     }
 
     void disjunction()
     {
         m_alternative = m_alternative->m_parent->addNewAlternative();
     }
 
-    unsigned setupAlternativeOffsets(PatternAlternative* alternative, unsigned currentCallFrameSize, unsigned initialInputPosition)
+    ErrorCode setupAlternativeOffsets(PatternAlternative* alternative, unsigned currentCallFrameSize, unsigned initialInputPosition, unsigned *callFrameSizeOut)
     {
         alternative->m_hasFixedSize = true;
         unsigned currentInputPosition = initialInputPosition;
 
         for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
             PatternTerm& term = alternative->m_terms[i];
 
             switch (term.type) {
@@ -668,75 +668,87 @@ public:
                 break;
 
             case PatternTerm::TypeParenthesesSubpattern:
                 // Note: for fixed once parentheses we will ensure at least the minimum is available; others are on their own.
                 term.frameLocation = currentCallFrameSize;
                 if (term.quantityCount == 1 && !term.parentheses.isCopy) {
                     if (term.quantityType != QuantifierFixedCount)
                         currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesOnce;
-                    currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition);
+                    if (ErrorCode error = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition, &currentCallFrameSize))
+                        return error;
                     // If quantity is fixed, then pre-check its minimum size.
                     if (term.quantityType == QuantifierFixedCount)
                         currentInputPosition += term.parentheses.disjunction->m_minimumSize;
                     term.inputPosition = currentInputPosition;
                 } else if (term.parentheses.isTerminal) {
                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesTerminal;
-                    currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition);
+                    if (ErrorCode error = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition, &currentCallFrameSize))
+                        return error;
                     term.inputPosition = currentInputPosition;
                 } else {
                     term.inputPosition = currentInputPosition;
-                    setupDisjunctionOffsets(term.parentheses.disjunction, BASE_FRAME_SIZE, currentInputPosition);
+                    unsigned dummy;
+                    if (ErrorCode error = setupDisjunctionOffsets(term.parentheses.disjunction, BASE_FRAME_SIZE, currentInputPosition, &dummy))
+                        return error;
                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoParentheses;
                 }
                 // Fixed count of 1 could be accepted, if they have a fixed size *AND* if all alternatives are of the same length.
                 alternative->m_hasFixedSize = false;
                 break;
 
             case PatternTerm::TypeParentheticalAssertion:
                 term.inputPosition = currentInputPosition;
                 term.frameLocation = currentCallFrameSize;
-                currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize + YarrStackSpaceForBackTrackInfoParentheticalAssertion, currentInputPosition);
+                if (ErrorCode error = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize + YarrStackSpaceForBackTrackInfoParentheticalAssertion, currentInputPosition, &currentCallFrameSize))
+                    return error;
                 break;
             }
         }
 
         alternative->m_minimumSize = currentInputPosition - initialInputPosition;
-        return currentCallFrameSize;
+        *callFrameSizeOut = currentCallFrameSize;
+        return NoError;
     }
 
-    unsigned setupDisjunctionOffsets(PatternDisjunction* disjunction, unsigned initialCallFrameSize, unsigned initialInputPosition)
+    ErrorCode setupDisjunctionOffsets(PatternDisjunction* disjunction, unsigned initialCallFrameSize, unsigned initialInputPosition, unsigned *maximumCallFrameSizeOut)
     {
         if ((disjunction != m_pattern.m_body) && (disjunction->m_alternatives.size() > 1))
             initialCallFrameSize += YarrStackSpaceForBackTrackInfoAlternative;
 
         unsigned minimumInputSize = UINT_MAX;
         unsigned maximumCallFrameSize = 0;
         bool hasFixedSize = true;
 
         for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
             PatternAlternative* alternative = disjunction->m_alternatives[alt];
-            unsigned currentAlternativeCallFrameSize = setupAlternativeOffsets(alternative, initialCallFrameSize, initialInputPosition);
+            unsigned currentAlternativeCallFrameSize;
+            if (ErrorCode error = setupAlternativeOffsets(alternative, initialCallFrameSize, initialInputPosition, &currentAlternativeCallFrameSize))
+                return error;
             minimumInputSize = std::min(minimumInputSize, alternative->m_minimumSize);
             maximumCallFrameSize = std::max(maximumCallFrameSize, currentAlternativeCallFrameSize);
             hasFixedSize &= alternative->m_hasFixedSize;
         }
         
-        ASSERT(minimumInputSize != UINT_MAX);
+        if (minimumInputSize == UINT_MAX)
+            return PatternTooLarge;
+
         ASSERT(maximumCallFrameSize >= initialCallFrameSize);
 
         disjunction->m_hasFixedSize = hasFixedSize;
         disjunction->m_minimumSize = minimumInputSize;
         disjunction->m_callFrameSize = maximumCallFrameSize;
-        return maximumCallFrameSize;
+        *maximumCallFrameSizeOut = maximumCallFrameSize;
+        return NoError;
     }
 
-    void setupOffsets()
+    ErrorCode setupOffsets()
     {
-        setupDisjunctionOffsets(m_pattern.m_body, BASE_FRAME_SIZE, 0);
+        unsigned dummy;
+        return setupDisjunctionOffsets(m_pattern.m_body, BASE_FRAME_SIZE, 0, &dummy);
     }
 
     // This optimization identifies sets of parentheses that we will never need to backtrack.
     // In these cases we do not need to store state from prior iterations.
     // We can presently avoid backtracking for:
     //   * where the parens are at the end of the regular expression (last term in any of the
     //     alternatives of the main body disjunction).
     //   * where the parens are non-capturing, and quantified unbounded greedy (*).
@@ -953,17 +965,19 @@ ErrorCode YarrPattern::compile(const USt
 
         ASSERT(!error);
         ASSERT(numSubpatterns == m_numSubpatterns);
     }
 
     constructor.checkForTerminalParentheses();
     constructor.optimizeBOL();
         
-    constructor.setupOffsets();
+    if (ErrorCode error = constructor.setupOffsets())
+        return error;
+
     constructor.setupBeginChars();
 
     return NoError;
 }
 
 YarrPattern::YarrPattern(const UString& pattern, bool ignoreCase, bool multiline, ErrorCode* error)
     : m_ignoreCase(ignoreCase)
     , m_multiline(multiline)