https://bugs.webkit.org/show_bug.cgi?id=61585
authorbarraclough@apple.com <barraclough@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 23 Jun 2011 21:35:50 +0000 (21:35 +0000)
committerbarraclough@apple.com <barraclough@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 23 Jun 2011 21:35:50 +0000 (21:35 +0000)
Crash running regexp /(?:(?=g))|(?:m).{2147483648,}/

Reviewed by Oliver Hunt.

Source/JavaScriptCore:

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.

LayoutTests:

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.

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

LayoutTests/ChangeLog
LayoutTests/fast/regex/overflow-expected.txt [new file with mode: 0644]
LayoutTests/fast/regex/overflow.html [new file with mode: 0644]
LayoutTests/fast/regex/script-tests/overflow.js [new file with mode: 0644]
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/yarr/YarrInterpreter.cpp
Source/JavaScriptCore/yarr/YarrJIT.cpp

index 545dd54..693cffa 100644 (file)
@@ -1,3 +1,16 @@
+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-06-23  Jessie Berlin  <jberlin@apple.com>
 
         [Snow Leopard WebKit2 Tests]  http/tests/appcache/interrupted-update.html failing, probably
diff --git a/LayoutTests/fast/regex/overflow-expected.txt b/LayoutTests/fast/regex/overflow-expected.txt
new file mode 100644 (file)
index 0000000..e02faa3
--- /dev/null
@@ -0,0 +1,11 @@
+This test checks expressions with alternative lengths of appox. 2^31.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS regexp1.exec('') is null
+PASS regexp2.exec('') is null
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/regex/overflow.html b/LayoutTests/fast/regex/overflow.html
new file mode 100644 (file)
index 0000000..32e9945
--- /dev/null
@@ -0,0 +1,13 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="../js/resources/js-test-style.css">
+<script src="../js/resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="script-tests/overflow.js"></script>
+<script src="../js/resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/fast/regex/script-tests/overflow.js b/LayoutTests/fast/regex/script-tests/overflow.js
new file mode 100644 (file)
index 0000000..cced651
--- /dev/null
@@ -0,0 +1,10 @@
+description("This test checks expressions with alternative lengths of appox. 2^31.");
+
+var regexp1 = /(?:(?=g))|(?:m).{2147483648,}/;
+shouldBe("regexp1.exec('')", 'null');
+
+var regexp2 = /(?:(?=g)).{2147483648,}/;
+shouldBe("regexp2.exec('')", 'null');
+
+var successfullyParsed = true;
+
index 5770728..9abd3c7 100644 (file)
@@ -1,3 +1,22 @@
+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-22  Gavin Barraclough  <barraclough@apple.com>
 
         Reviewed by Sam Weinig.
index 9e404dd..fcab836 100644 (file)
@@ -1751,9 +1751,9 @@ public:
             }
 
             unsigned minimumSize = alternative->m_minimumSize;
-            int countToCheck = minimumSize - parenthesesInputCountAlreadyChecked;
+            ASSERT(minimumSize >= parenthesesInputCountAlreadyChecked);
+            unsigned countToCheck = minimumSize - parenthesesInputCountAlreadyChecked;
 
-            ASSERT(countToCheck >= 0);
             if (countToCheck) {
                 checkInput(countToCheck);
                 currentCountAlreadyChecked += countToCheck;
@@ -1821,14 +1821,13 @@ public:
                     unsigned alternativeFrameLocation = term.frameLocation + YarrStackSpaceForBackTrackInfoParentheticalAssertion;
 
                     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);
                     emitDisjunction(term.parentheses.disjunction, currentCountAlreadyChecked, positiveInputOffset - uncheckAmount);
index a824c6f..f1b69d7 100644 (file)
@@ -1208,11 +1208,11 @@ class YarrGenerator : private MacroAssembler {
                     // PRIOR alteranative, and we will only check input availability if we
                     // 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,
                     // jumped to when the las alternative fails to match.
@@ -1571,19 +1571,13 @@ class YarrGenerator : private MacroAssembler {
                 if (onceThrough)
                     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 {
                         // We need to generate a trampoline of code to execute before looping back
@@ -1604,19 +1598,26 @@ class YarrGenerator : private MacroAssembler {
                             }
                         }
 
-                        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);
+                            }
+                        }
                     }
                 }
 
@@ -1640,21 +1641,20 @@ class YarrGenerator : private MacroAssembler {
                 while (nextOp->m_op != OpBodyAlternativeEnd) {
                     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.
-                        Jump fail = jumpIfNoAvailableInput();
+                        unsigned delta = prevOp->m_alternative->m_minimumSize - nextOp->m_alternative->m_minimumSize;
                         sub32(Imm32(delta), index);
+                        Jump fail = jumpIfNoAvailableInput();
+                        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];
                 }
@@ -1688,9 +1688,18 @@ class YarrGenerator : private MacroAssembler {
                 // one, and check. Also add in the minimum disjunction size before checking - there
                 // 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();
 
                 if (needsToUpdateMatchStart) {
@@ -1706,11 +1715,13 @@ class YarrGenerator : private MacroAssembler {
                 // Calculate how much more input the first alternative requires than the minimum
                 // 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);
                 }