Reviewers: Erik Corry,
Message:
In some cases the recursion to gather Boyer-Moore info can cause a stack
overflow.
PTAL.
Description:
Limit recursion depth for gathering BoyerMoore info.
BUG=126412
TEST=regress-126412
Please review this at http://codereview.chromium.org/10380028/
SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge
Affected files:
M src/jsregexp.h
M src/jsregexp.cc
A test/mjsunit/regress/regress-126412.js
Index: src/jsregexp.cc
diff --git a/src/jsregexp.cc b/src/jsregexp.cc
index
3455abce2399b3030a172e10ce1e2eb463f43647..cbfe18f4abed2d1ec310043adbd7b7e82072f2b6
100644
--- a/src/jsregexp.cc
+++ b/src/jsregexp.cc
@@ -997,7 +997,7 @@ RegExpEngine::CompilationResult
RegExpCompiler::Assemble(
bool use_slow_safe_regexp_compiler = false;
if (heap->total_regexp_code_generated() >
- RegExpImpl::kRegWxpCompiledLimit &&
+ RegExpImpl::kRegExpCompiledLimit &&
heap->isolate()->memory_allocator()->SizeExecutable() >
RegExpImpl::kRegExpExecutableMemoryLimit) {
use_slow_safe_regexp_compiler = true;
@@ -3477,7 +3477,8 @@ void BoyerMoorePositionInfo::SetAll() {
BoyerMooreLookahead::BoyerMooreLookahead(
int length, RegExpCompiler* compiler)
: length_(length),
- compiler_(compiler) {
+ compiler_(compiler),
+ depth_(0) {
if (compiler->ascii()) {
max_char_ = String::kMaxAsciiCharCode;
} else {
@@ -5588,6 +5589,11 @@ STATIC_ASSERT(BoyerMoorePositionInfo::kMapSize ==
void ChoiceNode::FillInBMInfo(
int offset, BoyerMooreLookahead* bm, bool not_at_start) {
ZoneList<GuardedAlternative>* alts = alternatives();
+ if (bm->MaxDepthExceeded()) {
+ bm->SetRest(offset); // Give up trying to fill in info.
+ SaveBMInfo(bm, not_at_start, offset);
+ return;
+ }
for (int i = 0; i < alts->length(); i++) {
GuardedAlternative& alt = alts->at(i);
if (alt.guards() != NULL && alt.guards()->length() != 0) {
Index: src/jsregexp.h
diff --git a/src/jsregexp.h b/src/jsregexp.h
index
20313ca559ff1dff6a47c4dd86879a64b6451dc5..3f7bbdf4546cba286c9daf20dd7394028b3899e2
100644
--- a/src/jsregexp.h
+++ b/src/jsregexp.h
@@ -185,7 +185,7 @@ class RegExpImpl {
// total regexp code compiled including code that has subsequently been
freed
// and the total executable memory at any point.
static const int kRegExpExecutableMemoryLimit = 16 * MB;
- static const int kRegWxpCompiledLimit = 1 * MB;
+ static const int kRegExpCompiledLimit = 1 * MB;
private:
static String* last_ascii_string_;
@@ -1236,6 +1236,12 @@ class BoyerMooreLookahead : public ZoneObject {
}
bool EmitSkipInstructions(RegExpMacroAssembler* masm);
+ bool MaxDepthExceeded() {
+ return (++depth_ > kMaxFillInDepth);
+ }
+
+ static const int kMaxFillInDepth = 1024;
+
private:
// This is the value obtained by EatsAtLeast. If we do not have at
least this
// many characters left in the sample string then the match is bound to
fail.
@@ -1243,6 +1249,7 @@ class BoyerMooreLookahead : public ZoneObject {
// point.
int length_;
RegExpCompiler* compiler_;
+ int depth_;
// 0x7f for ASCII, 0xffff for UTF-16.
int max_char_;
ZoneList<BoyerMoorePositionInfo*>* bitmaps_;
Index: test/mjsunit/regress/regress-126412.js
diff --git a/test/mjsunit/regress/regress-126412.js
b/test/mjsunit/regress/regress-126412.js
new file mode 100644
index
0000000000000000000000000000000000000000..91c6b078d8ae15c2157d8d79b730711b6f6f4842
--- /dev/null
+++ b/test/mjsunit/regress/regress-126412.js
@@ -0,0 +1,44 @@
+// Copyright 2012 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following
+// disclaimer in the documentation and/or other materials provided
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+
+function test(string, regexp) {
+ try {
+ string.match(regexp);
+ } catch (e) {
+ if (e instanceof RangeError) {
+ assertEquals("RangeError: Maximum call stack size exceeded",
e.toString());
+ }
+ }
+}
+
+test("", /(A{9999999999}B|C*)*D/);
+test("C", /(A{9999999999}B|C*)*D/);
+test("", /(A{9999999999}B|C*)*/ );
+test("C", /(A{9999999999}B|C*)*/ );
+test("", /(9u|(2\`shj{2147483649,}\r|3|f|y|3*)+8\B)\W93+/);
+test("9u8 ", /(9u|(2\`shj{2147483649,}\r|3|f|y|3*)+8\B)\W93+/);
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
