Modified: trunk/LayoutTests/ChangeLog (89613 => 89614)
--- trunk/LayoutTests/ChangeLog 2011-06-23 21:30:15 UTC (rev 89613)
+++ trunk/LayoutTests/ChangeLog 2011-06-23 21:35:50 UTC (rev 89614)
@@ -1,3 +1,16 @@
+2011-06-23 Gavin Barraclough <barraclo...@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 <jber...@apple.com>
[Snow Leopard WebKit2 Tests] http/tests/appcache/interrupted-update.html failing, probably
Added: trunk/LayoutTests/fast/regex/overflow-expected.txt (0 => 89614)
--- trunk/LayoutTests/fast/regex/overflow-expected.txt (rev 0)
+++ trunk/LayoutTests/fast/regex/overflow-expected.txt 2011-06-23 21:35:50 UTC (rev 89614)
@@ -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
+
Added: trunk/LayoutTests/fast/regex/script-tests/overflow.js (0 => 89614)
--- trunk/LayoutTests/fast/regex/script-tests/overflow.js (rev 0)
+++ trunk/LayoutTests/fast/regex/script-tests/overflow.js 2011-06-23 21:35:50 UTC (rev 89614)
@@ -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;
+
Modified: trunk/Source/_javascript_Core/ChangeLog (89613 => 89614)
--- trunk/Source/_javascript_Core/ChangeLog 2011-06-23 21:30:15 UTC (rev 89613)
+++ trunk/Source/_javascript_Core/ChangeLog 2011-06-23 21:35:50 UTC (rev 89614)
@@ -1,3 +1,22 @@
+2011-06-23 Gavin Barraclough <barraclo...@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 <barraclo...@apple.com>
Reviewed by Sam Weinig.
Modified: trunk/Source/_javascript_Core/yarr/YarrInterpreter.cpp (89613 => 89614)
--- trunk/Source/_javascript_Core/yarr/YarrInterpreter.cpp 2011-06-23 21:30:15 UTC (rev 89613)
+++ trunk/Source/_javascript_Core/yarr/YarrInterpreter.cpp 2011-06-23 21:35:50 UTC (rev 89614)
@@ -1751,9 +1751,9 @@
}
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 @@
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);
Modified: trunk/Source/_javascript_Core/yarr/YarrJIT.cpp (89613 => 89614)
--- trunk/Source/_javascript_Core/yarr/YarrJIT.cpp 2011-06-23 21:30:15 UTC (rev 89613)
+++ trunk/Source/_javascript_Core/yarr/YarrJIT.cpp 2011-06-23 21:35:50 UTC (rev 89614)
@@ -1208,11 +1208,11 @@
// 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 @@
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 @@
}
}
- 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 @@
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.
+ 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];
}
@@ -1688,9 +1688,18 @@
// 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 @@
// 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);
}
