Merged r13788, r13658 into 3.16 branch.
Limit EatAtLeast recursion by a budget.
Fix NegateCompareOp and InvertCompareOp
BUG=178790,v8:2537
R=jkummerow@chromium.org
Review URL: https://chromiumcodereview.appspot.com/12746003
git-svn-id: http://v8.googlecode.com/svn/branches/3.16@13924 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
diff --git a/src/hydrogen.cc b/src/hydrogen.cc
index dd71660..bbe148f 100644
--- a/src/hydrogen.cc
+++ b/src/hydrogen.cc
@@ -1812,7 +1812,7 @@
if (test->SecondSuccessor() == dest) {
op = Token::NegateCompareOp(op);
}
- Token::Value inverted_op = Token::InvertCompareOp(op);
+ Token::Value inverted_op = Token::ReverseCompareOp(op);
UpdateControlFlowRange(op, test->left(), test->right());
UpdateControlFlowRange(inverted_op, test->right(), test->left());
}
diff --git a/src/jsregexp.cc b/src/jsregexp.cc
index 8928d4e..d66777e 100644
--- a/src/jsregexp.cc
+++ b/src/jsregexp.cc
@@ -2298,35 +2298,33 @@
int ActionNode::EatsAtLeast(int still_to_find,
- int recursion_depth,
+ int budget,
bool not_at_start) {
- if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
+ if (budget <= 0) return 0;
if (type_ == POSITIVE_SUBMATCH_SUCCESS) return 0; // Rewinds input!
return on_success()->EatsAtLeast(still_to_find,
- recursion_depth + 1,
+ budget - 1,
not_at_start);
}
void ActionNode::FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
if (type_ == BEGIN_SUBMATCH) {
bm->SetRest(offset);
} else if (type_ != POSITIVE_SUBMATCH_SUCCESS) {
- on_success()->FillInBMInfo(
- offset, recursion_depth + 1, budget - 1, bm, not_at_start);
+ on_success()->FillInBMInfo(offset, budget - 1, bm, not_at_start);
}
SaveBMInfo(bm, not_at_start, offset);
}
int AssertionNode::EatsAtLeast(int still_to_find,
- int recursion_depth,
+ int budget,
bool not_at_start) {
- if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
+ if (budget <= 0) return 0;
// If we know we are not at the start and we are asked "how many characters
// will you match if you succeed?" then we can answer anything since false
// implies false. So lets just return the max answer (still_to_find) since
@@ -2334,55 +2332,53 @@
// branches in the node graph.
if (type() == AT_START && not_at_start) return still_to_find;
return on_success()->EatsAtLeast(still_to_find,
- recursion_depth + 1,
+ budget - 1,
not_at_start);
}
void AssertionNode::FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
// Match the behaviour of EatsAtLeast on this node.
if (type() == AT_START && not_at_start) return;
- on_success()->FillInBMInfo(
- offset, recursion_depth + 1, budget - 1, bm, not_at_start);
+ on_success()->FillInBMInfo(offset, budget - 1, bm, not_at_start);
SaveBMInfo(bm, not_at_start, offset);
}
int BackReferenceNode::EatsAtLeast(int still_to_find,
- int recursion_depth,
+ int budget,
bool not_at_start) {
- if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
+ if (budget <= 0) return 0;
return on_success()->EatsAtLeast(still_to_find,
- recursion_depth + 1,
+ budget - 1,
not_at_start);
}
int TextNode::EatsAtLeast(int still_to_find,
- int recursion_depth,
+ int budget,
bool not_at_start) {
int answer = Length();
if (answer >= still_to_find) return answer;
- if (recursion_depth > RegExpCompiler::kMaxRecursion) return answer;
+ if (budget <= 0) return answer;
// We are not at start after this node so we set the last argument to 'true'.
return answer + on_success()->EatsAtLeast(still_to_find - answer,
- recursion_depth + 1,
+ budget - 1,
true);
}
int NegativeLookaheadChoiceNode::EatsAtLeast(int still_to_find,
- int recursion_depth,
+ int budget,
bool not_at_start) {
- if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
+ if (budget <= 0) return 0;
// Alternative 0 is the negative lookahead, alternative 1 is what comes
// afterwards.
RegExpNode* node = alternatives_->at(1).node();
- return node->EatsAtLeast(still_to_find, recursion_depth + 1, not_at_start);
+ return node->EatsAtLeast(still_to_find, budget - 1, not_at_start);
}
@@ -2399,39 +2395,40 @@
int ChoiceNode::EatsAtLeastHelper(int still_to_find,
- int recursion_depth,
+ int budget,
RegExpNode* ignore_this_node,
bool not_at_start) {
- if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
+ if (budget <= 0) return 0;
int min = 100;
int choice_count = alternatives_->length();
+ budget = (budget - 1) / choice_count;
for (int i = 0; i < choice_count; i++) {
RegExpNode* node = alternatives_->at(i).node();
if (node == ignore_this_node) continue;
- int node_eats_at_least = node->EatsAtLeast(still_to_find,
- recursion_depth + 1,
- not_at_start);
+ int node_eats_at_least =
+ node->EatsAtLeast(still_to_find, budget, not_at_start);
if (node_eats_at_least < min) min = node_eats_at_least;
+ if (min == 0) return 0;
}
return min;
}
int LoopChoiceNode::EatsAtLeast(int still_to_find,
- int recursion_depth,
+ int budget,
bool not_at_start) {
return EatsAtLeastHelper(still_to_find,
- recursion_depth,
+ budget - 1,
loop_node_,
not_at_start);
}
int ChoiceNode::EatsAtLeast(int still_to_find,
- int recursion_depth,
+ int budget,
bool not_at_start) {
return EatsAtLeastHelper(still_to_find,
- recursion_depth,
+ budget,
NULL,
not_at_start);
}
@@ -2987,19 +2984,15 @@
void LoopChoiceNode::FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
- if (body_can_be_zero_length_ ||
- recursion_depth > RegExpCompiler::kMaxRecursion ||
- budget <= 0) {
+ if (body_can_be_zero_length_ || budget <= 0) {
bm->SetRest(offset);
SaveBMInfo(bm, not_at_start, offset);
return;
}
- ChoiceNode::FillInBMInfo(
- offset, recursion_depth + 1, budget - 1, bm, not_at_start);
+ ChoiceNode::FillInBMInfo(offset, budget - 1, bm, not_at_start);
SaveBMInfo(bm, not_at_start, offset);
}
@@ -3096,12 +3089,13 @@
BoyerMooreLookahead* lookahead = bm_info(not_at_start);
if (lookahead == NULL) {
int eats_at_least =
- Min(kMaxLookaheadForBoyerMoore,
- EatsAtLeast(kMaxLookaheadForBoyerMoore, 0, not_at_start));
+ Min(kMaxLookaheadForBoyerMoore, EatsAtLeast(kMaxLookaheadForBoyerMoore,
+ kRecursionBudget,
+ not_at_start));
if (eats_at_least >= 1) {
BoyerMooreLookahead* bm =
new(zone()) BoyerMooreLookahead(eats_at_least, compiler, zone());
- FillInBMInfo(0, 0, kFillInBMBudget, bm, not_at_start);
+ FillInBMInfo(0, kRecursionBudget, bm, not_at_start);
if (bm->at(0)->is_non_word()) next_is_word_character = Trace::FALSE;
if (bm->at(0)->is_word()) next_is_word_character = Trace::TRUE;
}
@@ -4033,16 +4027,17 @@
ASSERT(trace->is_trivial()); // This is the case on LoopChoiceNodes.
BoyerMooreLookahead* lookahead = bm_info(not_at_start);
if (lookahead == NULL) {
- eats_at_least =
- Min(kMaxLookaheadForBoyerMoore,
- EatsAtLeast(kMaxLookaheadForBoyerMoore, 0, not_at_start));
+ eats_at_least = Min(kMaxLookaheadForBoyerMoore,
+ EatsAtLeast(kMaxLookaheadForBoyerMoore,
+ kRecursionBudget,
+ not_at_start));
if (eats_at_least >= 1) {
BoyerMooreLookahead* bm =
new(zone()) BoyerMooreLookahead(eats_at_least,
compiler,
zone());
GuardedAlternative alt0 = alternatives_->at(0);
- alt0.node()->FillInBMInfo(0, 0, kFillInBMBudget, bm, not_at_start);
+ alt0.node()->FillInBMInfo(0, kRecursionBudget, bm, not_at_start);
skip_was_emitted = bm->EmitSkipInstructions(macro_assembler);
}
} else {
@@ -4054,7 +4049,8 @@
if (eats_at_least == kEatsAtLeastNotYetInitialized) {
// Save some time by looking at most one machine word ahead.
- eats_at_least = EatsAtLeast(compiler->ascii() ? 4 : 2, 0, not_at_start);
+ eats_at_least =
+ EatsAtLeast(compiler->ascii() ? 4 : 2, kRecursionBudget, not_at_start);
}
int preload_characters = CalculatePreloadCharacters(compiler, eats_at_least);
@@ -5810,7 +5806,6 @@
void BackReferenceNode::FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
@@ -5826,7 +5821,6 @@
void ChoiceNode::FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
@@ -5839,15 +5833,13 @@
SaveBMInfo(bm, not_at_start, offset);
return;
}
- alt.node()->FillInBMInfo(
- offset, recursion_depth + 1, budget, bm, not_at_start);
+ alt.node()->FillInBMInfo(offset, budget, bm, not_at_start);
}
SaveBMInfo(bm, not_at_start, offset);
}
void TextNode::FillInBMInfo(int initial_offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
@@ -5904,7 +5896,6 @@
return;
}
on_success()->FillInBMInfo(offset,
- recursion_depth + 1,
budget - 1,
bm,
true); // Not at start after a text node.
diff --git a/src/jsregexp.h b/src/jsregexp.h
index ae0e902..625f192 100644
--- a/src/jsregexp.h
+++ b/src/jsregexp.h
@@ -582,9 +582,7 @@
// used to indicate that we know we are not at the start of the input. In
// this case anchored branches will always fail and can be ignored when
// determining how many characters are consumed on success.
- virtual int EatsAtLeast(int still_to_find,
- int recursion_depth,
- bool not_at_start) = 0;
+ virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start) = 0;
// Emits some quick code that checks whether the preloaded characters match.
// Falls through on certain failure, jumps to the label on possible success.
// If the node cannot make a quick check it does nothing and returns false.
@@ -616,9 +614,8 @@
// implementation. TODO(erikcorry): This should share more code with
// EatsAtLeast, GetQuickCheckDetails. The budget argument is used to limit
// the number of nodes we are willing to look at in order to create this data.
- static const int kFillInBMBudget = 200;
+ static const int kRecursionBudget = 200;
virtual void FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
@@ -725,12 +722,10 @@
void set_on_success(RegExpNode* node) { on_success_ = node; }
virtual RegExpNode* FilterASCII(int depth, bool ignore_case);
virtual void FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
- on_success_->FillInBMInfo(
- offset, recursion_depth + 1, budget - 1, bm, not_at_start);
+ on_success_->FillInBMInfo(offset, budget - 1, bm, not_at_start);
if (offset == 0) set_bm_info(not_at_start, bm);
}
@@ -773,9 +768,7 @@
RegExpNode* on_success);
virtual void Accept(NodeVisitor* visitor);
virtual void Emit(RegExpCompiler* compiler, Trace* trace);
- virtual int EatsAtLeast(int still_to_find,
- int recursion_depth,
- bool not_at_start);
+ virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start);
virtual void GetQuickCheckDetails(QuickCheckDetails* details,
RegExpCompiler* compiler,
int filled_in,
@@ -784,7 +777,6 @@
details, compiler, filled_in, not_at_start);
}
virtual void FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
@@ -843,9 +835,7 @@
}
virtual void Accept(NodeVisitor* visitor);
virtual void Emit(RegExpCompiler* compiler, Trace* trace);
- virtual int EatsAtLeast(int still_to_find,
- int recursion_depth,
- bool not_at_start);
+ virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start);
virtual void GetQuickCheckDetails(QuickCheckDetails* details,
RegExpCompiler* compiler,
int characters_filled_in,
@@ -856,7 +846,6 @@
virtual RegExpNode* GetSuccessorOfOmnivorousTextNode(
RegExpCompiler* compiler);
virtual void FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
@@ -911,15 +900,12 @@
}
virtual void Accept(NodeVisitor* visitor);
virtual void Emit(RegExpCompiler* compiler, Trace* trace);
- virtual int EatsAtLeast(int still_to_find,
- int recursion_depth,
- bool not_at_start);
+ virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start);
virtual void GetQuickCheckDetails(QuickCheckDetails* details,
RegExpCompiler* compiler,
int filled_in,
bool not_at_start);
virtual void FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
@@ -960,7 +946,6 @@
return;
}
virtual void FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
@@ -989,7 +974,6 @@
UNREACHABLE();
}
virtual void FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
@@ -1075,11 +1059,9 @@
ZoneList<GuardedAlternative>* alternatives() { return alternatives_; }
DispatchTable* GetTable(bool ignore_case);
virtual void Emit(RegExpCompiler* compiler, Trace* trace);
- virtual int EatsAtLeast(int still_to_find,
- int recursion_depth,
- bool not_at_start);
+ virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start);
int EatsAtLeastHelper(int still_to_find,
- int recursion_depth,
+ int budget,
RegExpNode* ignore_this_node,
bool not_at_start);
virtual void GetQuickCheckDetails(QuickCheckDetails* details,
@@ -1087,7 +1069,6 @@
int characters_filled_in,
bool not_at_start);
virtual void FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
@@ -1133,20 +1114,17 @@
AddAlternative(this_must_fail);
AddAlternative(then_do_this);
}
- virtual int EatsAtLeast(int still_to_find,
- int recursion_depth,
- bool not_at_start);
+ virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start);
virtual void GetQuickCheckDetails(QuickCheckDetails* details,
RegExpCompiler* compiler,
int characters_filled_in,
bool not_at_start);
virtual void FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
alternatives_->at(1).node()->FillInBMInfo(
- offset, recursion_depth + 1, budget - 1, bm, not_at_start);
+ offset, budget - 1, bm, not_at_start);
if (offset == 0) set_bm_info(not_at_start, bm);
}
// For a negative lookahead we don't emit the quick check for the
@@ -1169,15 +1147,12 @@
void AddLoopAlternative(GuardedAlternative alt);
void AddContinueAlternative(GuardedAlternative alt);
virtual void Emit(RegExpCompiler* compiler, Trace* trace);
- virtual int EatsAtLeast(int still_to_find,
- int recursion_depth,
- bool not_at_start);
+ virtual int EatsAtLeast(int still_to_find, int budget, bool not_at_start);
virtual void GetQuickCheckDetails(QuickCheckDetails* details,
RegExpCompiler* compiler,
int characters_filled_in,
bool not_at_start);
virtual void FillInBMInfo(int offset,
- int recursion_depth,
int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
diff --git a/src/messages.js b/src/messages.js
index 4a8143e..4ace2df 100644
--- a/src/messages.js
+++ b/src/messages.js
@@ -820,7 +820,8 @@
%_CallFunction(this.receiver,
ownName,
ObjectLookupSetter) === this.fun ||
- %GetDataProperty(this.receiver, ownName) === this.fun)) {
+ (IS_OBJECT(this.receiver) &&
+ %GetDataProperty(this.receiver, ownName) === this.fun))) {
// To handle DontEnum properties we guess that the method has
// the same name as the function.
return ownName;
@@ -829,7 +830,8 @@
for (var prop in this.receiver) {
if (%_CallFunction(this.receiver, prop, ObjectLookupGetter) === this.fun ||
%_CallFunction(this.receiver, prop, ObjectLookupSetter) === this.fun ||
- %GetDataProperty(this.receiver, prop) === this.fun) {
+ (IS_OBJECT(this.receiver) &&
+ %GetDataProperty(this.receiver, prop) === this.fun)) {
// If we find more than one match bail out to avoid confusion.
if (name) {
return null;
@@ -883,10 +885,9 @@
function CallSiteIsConstructor() {
var receiver = this.receiver;
- var constructor = receiver ? %GetDataProperty(receiver, "constructor") : null;
- if (!constructor) {
- return false;
- }
+ var constructor =
+ IS_OBJECT(receiver) ? %GetDataProperty(receiver, "constructor") : null;
+ if (!constructor) return false;
return this.fun === constructor;
}
diff --git a/src/token.h b/src/token.h
index 863ba62..4078a15 100644
--- a/src/token.h
+++ b/src/token.h
@@ -230,26 +230,30 @@
case EQ: return NE;
case NE: return EQ;
case EQ_STRICT: return NE_STRICT;
+ case NE_STRICT: return EQ_STRICT;
case LT: return GTE;
case GT: return LTE;
case LTE: return GT;
case GTE: return LT;
default:
+ UNREACHABLE();
return op;
}
}
- static Value InvertCompareOp(Value op) {
+ static Value ReverseCompareOp(Value op) {
ASSERT(IsCompareOp(op));
switch (op) {
- case EQ: return NE;
- case NE: return EQ;
- case EQ_STRICT: return NE_STRICT;
+ case EQ: return EQ;
+ case NE: return NE;
+ case EQ_STRICT: return EQ_STRICT;
+ case NE_STRICT: return NE_STRICT;
case LT: return GT;
case GT: return LT;
case LTE: return GTE;
case GTE: return LTE;
default:
+ UNREACHABLE();
return op;
}
}
diff --git a/src/version.cc b/src/version.cc
index 096d8f3..bba9f89 100644
--- a/src/version.cc
+++ b/src/version.cc
@@ -35,7 +35,7 @@
#define MAJOR_VERSION 3
#define MINOR_VERSION 16
#define BUILD_NUMBER 14
-#define PATCH_LEVEL 5
+#define PATCH_LEVEL 6
// Use 1 for candidates and 0 otherwise.
// (Boolean macro values are not supported by all preprocessors.)
#define IS_CANDIDATE_VERSION 0
diff --git a/test/mjsunit/regress/regress-2537.js b/test/mjsunit/regress/regress-2537.js
new file mode 100644
index 0000000..c6b5af94
--- /dev/null
+++ b/test/mjsunit/regress/regress-2537.js
@@ -0,0 +1,45 @@
+// Copyright 2013 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.
+
+// Flags: --allow-natives-syntax
+
+var large_int = 0x40000000;
+
+function foo(x, expected) {
+ assertEquals(expected, x); // This succeeds.
+ x += 0; // Force int32 representation so that CompareIDAndBranch is used.
+ if (3 != x) {
+ x += 0; // Poor man's "iDef".
+ // Fails due to Smi-tagging without overflow check.
+ assertEquals(expected, x);
+ }
+}
+
+foo(1, 1);
+foo(3, 3);
+%OptimizeFunctionOnNextCall(foo);
+foo(large_int, large_int);
diff --git a/test/mjsunit/regress/regress-crbug-178790.js b/test/mjsunit/regress/regress-crbug-178790.js
new file mode 100644
index 0000000..57071ea
--- /dev/null
+++ b/test/mjsunit/regress/regress-crbug-178790.js
@@ -0,0 +1,52 @@
+// Copyright 2013 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.
+
+// Create a regexp in the form of a?a?...a? so that fully
+// traversing the entire graph would be prohibitively expensive.
+// This should not cause time out.
+var r1 = "";
+for (var i = 0; i < 1000; i++) {
+ r1 += "a?";
+}
+"test".match(RegExp(r1));
+
+var r2 = "";
+for (var i = 0; i < 100; i++) {
+ r2 += "(a?|b?|c?|d?|e?|f?|g?)";
+}
+"test".match(RegExp(r2));
+
+// Create a regexp in the form of ((..(a)a..)a.
+// Compiling it causes EatsAtLeast to reach the maximum
+// recursion depth possible with a given budget.
+// This should not cause a stack overflow.
+var r3 = "a";
+for (var i = 0; i < 1000; i++) {
+ r3 = "(" + r3 + ")a";
+}
+"test".match(RegExp(r3));
+
