Changeset 91512 in webkit

Timestamp:

Jul 21, 2011, 2:58:10 PM (14 years ago)

Author:

Lucas Forschler

Message:

Merge r89614.

Location:

branches/safari-534.51-branch

Files:

• LayoutTests/ChangeLog (modified) (1 diff)
• LayoutTests/fast/regex/overflow-expected.txt (copied) (copied from trunk/LayoutTests/fast/regex/overflow-expected.txt )
• LayoutTests/fast/regex/overflow.html (copied) (copied from trunk/LayoutTests/fast/regex/overflow.html )
• LayoutTests/fast/regex/script-tests/overflow.js (copied) (copied from trunk/LayoutTests/fast/regex/script-tests/overflow.js )
• Source/JavaScriptCore/ChangeLog (modified) (1 diff)
• Source/JavaScriptCore/yarr/YarrInterpreter.cpp (modified) (2 diffs)
• Source/JavaScriptCore/yarr/YarrJIT.cpp (modified) (6 diffs)

branches/safari-534.51-branch/LayoutTests/ChangeLog

@@ +1 @@
+2011-07-21  Lucas Forschler  <lforschler@apple.com>
+
+    Merged 89614.
+
+    2011-06-23  Gavin Barraclough  <barraclough@apple.com>
+
+        Reviewed by Oliver Hunt.
+
+        https://bugs.webkit.org/show_bug.cgi?id=61585
+        Crash running regexp /(?:(?=g))|(?:m).{2147483648,}/
+
+        Add regression tests where an alterative has a size of ~2^31.
+
+        * fast/regex/overflow-expected.txt: Added.
+        * fast/regex/overflow.html: Added.
+        * fast/regex/script-tests/overflow.js: Added.
+
 2011-07-21  Lucas Forschler  <lforschler@apple.com>
 

branches/safari-534.51-branch/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2011-07-21  Lucas Forschler  <lforschler@apple.com>
+
+    Merged 89614. 
+
+    2011-06-23  Gavin Barraclough  <barraclough@apple.com>
+
+        Reviewed by Oliver Hunt.
+
+        https://bugs.webkit.org/show_bug.cgi?id=61585
+        Crash running regexp /(?:(?=g))|(?:m).{2147483648,}/
+
+        This is due to use of int instead of unsigned, bad math around
+        the 2^31 boundary.
+
+        * yarr/YarrInterpreter.cpp:
+        (JSC::Yarr::ByteCompiler::emitDisjunction):
+            - Change some uses of int to unsigned, refactor compare logic to
+              restrict to the range 0..2^32-1 (rather than -2^32-1..2^32-1).
+        * yarr/YarrJIT.cpp:
+        (JSC::Yarr::YarrGenerator::generate):
+        (JSC::Yarr::YarrGenerator::backtrack):
+            - Ditto.
+
 2011-06-20  Lucas Forschler  <lforschler@apple.com>
 

branches/safari-534.51-branch/Source/JavaScriptCore/yarr/YarrInterpreter.cpp

@@ -1752 +1752 @@
 
             unsigned minimumSize = alternative->m_minimumSize;
-            int countToCheck = minimumSize - parenthesesInputCountAlreadyChecked;
-
-            ASSERT(countToCheck >= 0);
+            ASSERT(minimumSize >= parenthesesInputCountAlreadyChecked);
+            unsigned countToCheck = minimumSize - parenthesesInputCountAlreadyChecked;
+
             if (countToCheck) {
                 checkInput(countToCheck);
@@ -1822 +1822 @@
 
                     ASSERT(currentCountAlreadyChecked >= static_cast<unsigned>(term.inputPosition));
-                    int positiveInputOffset = currentCountAlreadyChecked - term.inputPosition;
-                    int uncheckAmount = positiveInputOffset - term.parentheses.disjunction->m_minimumSize;
-
-                    if (uncheckAmount > 0) {
+                    unsigned positiveInputOffset = currentCountAlreadyChecked - static_cast<unsigned>(term.inputPosition);
+                    unsigned uncheckAmount = 0;
+                    if (positiveInputOffset > term.parentheses.disjunction->m_minimumSize) {
+                        uncheckAmount = positiveInputOffset - term.parentheses.disjunction->m_minimumSize;
                         uncheckInput(uncheckAmount);
                         currentCountAlreadyChecked -= uncheckAmount;
-                    } else
-                        uncheckAmount = 0;
+                    }
 
                     atomParentheticalAssertionBegin(term.parentheses.subpatternId, term.invert(), term.frameLocation, alternativeFrameLocation);

branches/safari-534.51-branch/Source/JavaScriptCore/yarr/YarrJIT.cpp

@@ -1209 +1209 @@
                     // need to progress it forwards.
                     op.m_reentry = label();
-                    if (int delta = alternative->m_minimumSize - priorAlternative->m_minimumSize) {
-                        add32(Imm32(delta), index);
-                        if (delta > 0)
-                            op.m_jumps.append(jumpIfNoAvailableInput());
-                    }
+                    if (alternative->m_minimumSize > priorAlternative->m_minimumSize) {
+                        add32(Imm32(alternative->m_minimumSize - priorAlternative->m_minimumSize), index);
+                        op.m_jumps.append(jumpIfNoAvailableInput());
+                    } else if (priorAlternative->m_minimumSize > alternative->m_minimumSize)
+                        sub32(Imm32(priorAlternative->m_minimumSize - alternative->m_minimumSize), index);
                 } else if (op.m_nextOp == notFound) {
                     // This is the reentry point for the End of 'once through' alternatives,
@@ -1572 +1572 @@
                     m_backtrackingState.linkTo(endOp.m_reentry, this);
                 else {
-                    // Okay, we're going to need to loop. Calculate the delta between where the input
-                    // position was, and where we want it to be allowing for the fact that we need to
-                    // increment by 1. E.g. for the regexp /a|x/ we need to increment the position by
-                    // 1 between loop iterations, but for /abcd|xyz/ we need to increment by two when
-                    // looping from the last alternative to the first, for /a|xyz/ we need to decrement
-                    // by 1, and for /a|xy/ we don't need to move the input position at all.
-                    int deltaLastAlternativeToFirstAlternativePlusOne = (beginOp->m_alternative->m_minimumSize - alternative->m_minimumSize) + 1;
-
                     // If we don't need to move the input poistion, and the pattern has a fixed size
                     // (in which case we omit the store of the start index until the pattern has matched)
                     // then we can just link the backtrack out of the last alternative straight to the
                     // head of the first alternative.
-                    if (!deltaLastAlternativeToFirstAlternativePlusOne && m_pattern.m_body->m_hasFixedSize)
+                    if (m_pattern.m_body->m_hasFixedSize
+                        && (alternative->m_minimumSize > beginOp->m_alternative->m_minimumSize)
+                        && (alternative->m_minimumSize - beginOp->m_alternative->m_minimumSize == 1))
                         m_backtrackingState.linkTo(beginOp->m_reentry, this);
                     else {
@@ -1605 +1599 @@
                         }
 
-                        if (deltaLastAlternativeToFirstAlternativePlusOne)
-                            add32(Imm32(deltaLastAlternativeToFirstAlternativePlusOne), index);
-
-                        // Loop. Since this code is only reached when we backtrack out of the last
-                        // alternative (and NOT linked to from the input check upon entry to the
-                        // last alternative) we know that there must be at least enough input as
-                        // required by the last alternative. As such, we only need to check if the
-                        // first will require more to run - if the same or less is required we can
-                        // unconditionally jump.
-                        if (deltaLastAlternativeToFirstAlternativePlusOne > 0)
-                            checkInput().linkTo(beginOp->m_reentry, this);
-                        else
+                        // Generate code to loop. Check whether the last alternative is longer than the
+                        // first (e.g. /a|xy/ or /a|xyz/).
+                        if (alternative->m_minimumSize > beginOp->m_alternative->m_minimumSize) {
+                            // We want to loop, and increment input position. If the delta is 1, it is
+                            // already correctly incremented, if more than one then decrement as appropriate.
+                            unsigned delta = alternative->m_minimumSize - beginOp->m_alternative->m_minimumSize;
+                            ASSERT(delta);
+                            if (delta != 1)
+                                sub32(Imm32(delta - 1), index);
                             jump(beginOp->m_reentry);
+                        } else {
+                            // If the first alternative has minimum size 0xFFFFFFFFu, then there cannot
+                            // be sufficent input available to handle this, so just fall through.
+                            unsigned delta = beginOp->m_alternative->m_minimumSize - alternative->m_minimumSize;
+                            if (delta != 0xFFFFFFFFu) {
+                                // We need to check input because we are incrementing the input.
+                                add32(Imm32(delta + 1), index);
+                                checkInput().linkTo(beginOp->m_reentry, this);
+                            }
+                        }
                     }
                 }
@@ -1641 +1642 @@
                     prevOp->m_jumps.link(this);
 
-                    int delta = nextOp->m_alternative->m_minimumSize - prevOp->m_alternative->m_minimumSize;
-                    if (delta)
-                        add32(Imm32(delta), index);
-
                     // We only get here if an input check fails, it is only worth checking again
                     // if the next alternative has a minimum size less than the last.
-                    if (delta < 0) {
+                    if (prevOp->m_alternative->m_minimumSize > nextOp->m_alternative->m_minimumSize) {
                         // FIXME: if we added an extra label to YarrOp, we could avoid needing to
                         // subtract delta back out, and reduce this code. Should performance test
                         // the benefit of this.
+                        unsigned delta = prevOp->m_alternative->m_minimumSize - nextOp->m_alternative->m_minimumSize;
+                        sub32(Imm32(delta), index);
                         Jump fail = jumpIfNoAvailableInput();
-                        sub32(Imm32(delta), index);
+                        add32(Imm32(delta), index);
                         jump(nextOp->m_reentry);
                         fail.link(this);
-                    }
+                    } else if (prevOp->m_alternative->m_minimumSize < nextOp->m_alternative->m_minimumSize)
+                        add32(Imm32(nextOp->m_alternative->m_minimumSize - prevOp->m_alternative->m_minimumSize), index);
                     prevOp = nextOp;
                     nextOp = &m_ops[nextOp->m_nextOp];
@@ -1689 +1689 @@
                 // is no point in looping if we're just going to fail all the input checks around
                 // the next iteration.
-                int deltaLastAlternativeToBodyMinimumPlusOne = (m_pattern.m_body->m_minimumSize + 1) - alternative->m_minimumSize;
-                if (deltaLastAlternativeToBodyMinimumPlusOne)
-                    add32(Imm32(deltaLastAlternativeToBodyMinimumPlusOne), index);
+                ASSERT(alternative->m_minimumSize >= m_pattern.m_body->m_minimumSize);
+                if (alternative->m_minimumSize == m_pattern.m_body->m_minimumSize) {
+                    // If the last alternative had the same minimum size as the disjunction,
+                    // just simply increment input pos by 1, no adjustment based on minimum size.
+                    add32(Imm32(1), index);
+                } else {
+                    // If the minumum for the last alternative was one greater than than that
+                    // for the disjunction, we're already progressed by 1, nothing to do!
+                    unsigned delta = (alternative->m_minimumSize - m_pattern.m_body->m_minimumSize) - 1;
+                    if (delta)
+                        sub32(Imm32(delta), index);
+                }
                 Jump matchFailed = jumpIfNoAvailableInput();
 
@@ -1707 +1716 @@
                 // for the body as a whole. If no more is needed then we dont need an additional
                 // input check here - jump straight back up to the start of the first alternative.
-                int deltaBodyMinimumToFirstAlternative = beginOp->m_alternative->m_minimumSize - m_pattern.m_body->m_minimumSize;
-                if (!deltaBodyMinimumToFirstAlternative)
+                if (beginOp->m_alternative->m_minimumSize == m_pattern.m_body->m_minimumSize)
                     jump(beginOp->m_reentry);
                 else {
-                    add32(Imm32(deltaBodyMinimumToFirstAlternative), index);
+                    if (beginOp->m_alternative->m_minimumSize > m_pattern.m_body->m_minimumSize)
+                        add32(Imm32(beginOp->m_alternative->m_minimumSize - m_pattern.m_body->m_minimumSize), index);
+                    else
+                        sub32(Imm32(m_pattern.m_body->m_minimumSize - beginOp->m_alternative->m_minimumSize), index);
                     checkInput().linkTo(beginOp->m_reentry, this);
                     jump(firstInputCheckFailed);