Revision: 11696
Author: [email protected]
Date: Fri Jun 1 04:28:52 2012
Log: Limit work done analyzing regexps with very large fanout.
BUG=128821
Review URL: https://chromiumcodereview.appspot.com/10448117
http://code.google.com/p/v8/source/detail?r=11696
Modified:
/branches/bleeding_edge/src/jsregexp.cc
/branches/bleeding_edge/src/jsregexp.h
/branches/bleeding_edge/test/mjsunit/regexp-capture-3.js
/branches/bleeding_edge/test/mjsunit/regexp-capture.js
=======================================
--- /branches/bleeding_edge/src/jsregexp.cc Thu May 31 04:59:04 2012
+++ /branches/bleeding_edge/src/jsregexp.cc Fri Jun 1 04:28:52 2012
@@ -2192,12 +2192,14 @@
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, bm,
not_at_start);
+ on_success()->FillInBMInfo(
+ offset, recursion_depth + 1, budget - 1, bm, not_at_start);
}
SaveBMInfo(bm, not_at_start, offset);
}
@@ -2221,11 +2223,13 @@
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, bm,
not_at_start);
+ on_success()->FillInBMInfo(
+ offset, recursion_depth + 1, budget - 1, bm, not_at_start);
SaveBMInfo(bm, not_at_start, offset);
}
@@ -2808,15 +2812,18 @@
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) {
+ recursion_depth > RegExpCompiler::kMaxRecursion ||
+ budget <= 0) {
bm->SetRest(offset);
SaveBMInfo(bm, not_at_start, offset);
return;
}
- ChoiceNode::FillInBMInfo(offset, recursion_depth + 1, bm, not_at_start);
+ ChoiceNode::FillInBMInfo(
+ offset, recursion_depth + 1, budget - 1, bm, not_at_start);
SaveBMInfo(bm, not_at_start, offset);
}
@@ -2918,7 +2925,7 @@
if (eats_at_least >= 1) {
BoyerMooreLookahead* bm =
new BoyerMooreLookahead(eats_at_least, compiler);
- FillInBMInfo(0, 0, bm, not_at_start);
+ FillInBMInfo(0, 0, kFillInBMBudget, 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;
}
@@ -3856,7 +3863,7 @@
BoyerMooreLookahead* bm =
new BoyerMooreLookahead(eats_at_least, compiler);
GuardedAlternative alt0 = alternatives_->at(0);
- alt0.node()->FillInBMInfo(0, 0, bm, not_at_start);
+ alt0.node()->FillInBMInfo(0, 0, kFillInBMBudget, bm,
not_at_start);
skip_was_emitted = bm->EmitSkipInstructions(macro_assembler);
}
} else {
@@ -5597,6 +5604,7 @@
void BackReferenceNode::FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
// Working out the set of characters that a backreference can match is
too
@@ -5612,9 +5620,11 @@
void ChoiceNode::FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
ZoneList<GuardedAlternative>* alts = alternatives();
+ budget = (budget - 1) / alts->length();
for (int i = 0; i < alts->length(); i++) {
GuardedAlternative& alt = alts->at(i);
if (alt.guards() != NULL && alt.guards()->length() != 0) {
@@ -5622,7 +5632,8 @@
SaveBMInfo(bm, not_at_start, offset);
return;
}
- alt.node()->FillInBMInfo(offset, recursion_depth + 1, bm,
not_at_start);
+ alt.node()->FillInBMInfo(
+ offset, recursion_depth + 1, budget, bm, not_at_start);
}
SaveBMInfo(bm, not_at_start, offset);
}
@@ -5630,6 +5641,7 @@
void TextNode::FillInBMInfo(int initial_offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
if (initial_offset >= bm->length()) return;
@@ -5686,6 +5698,7 @@
}
on_success()->FillInBMInfo(offset,
recursion_depth + 1,
+ budget - 1,
bm,
true); // Not at start after a text node.
if (initial_offset == 0) set_bm_info(not_at_start, bm);
=======================================
--- /branches/bleeding_edge/src/jsregexp.h Thu May 31 04:59:04 2012
+++ /branches/bleeding_edge/src/jsregexp.h Fri Jun 1 04:28:52 2012
@@ -580,9 +580,12 @@
// Collects information on the possible code units (mod 128) that can
match if
// we look forward. This is used for a Boyer-Moore-like string searching
// implementation. TODO(erikcorry): This should share more code with
- // EatsAtLeast, GetQuickCheckDetails.
+ // 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;
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
UNREACHABLE();
@@ -685,9 +688,11 @@
virtual RegExpNode* FilterASCII(int depth);
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
- on_success_->FillInBMInfo(offset, recursion_depth + 1, bm,
not_at_start);
+ on_success_->FillInBMInfo(
+ offset, recursion_depth + 1, budget - 1, bm, not_at_start);
if (offset == 0) set_bm_info(not_at_start, bm);
}
@@ -742,6 +747,7 @@
}
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
Type type() { return type_; }
@@ -813,6 +819,7 @@
RegExpCompiler* compiler);
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
void CalculateOffsets();
@@ -875,6 +882,7 @@
bool not_at_start);
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
AssertionNodeType type() { return type_; }
@@ -915,6 +923,7 @@
}
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
@@ -942,6 +951,7 @@
}
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
// Returning 0 from EatsAtLeast should ensure we never get here.
@@ -1034,6 +1044,7 @@
bool not_at_start);
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
@@ -1086,10 +1097,11 @@
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, bm, not_at_start);
+ offset, recursion_depth + 1, 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
@@ -1121,6 +1133,7 @@
bool not_at_start);
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
RegExpNode* loop_node() { return loop_node_; }
=======================================
--- /branches/bleeding_edge/test/mjsunit/regexp-capture-3.js Thu May 31
04:59:04 2012
+++ /branches/bleeding_edge/test/mjsunit/regexp-capture-3.js Fri Jun 1
04:28:52 2012
@@ -162,7 +162,6 @@
// string we can test that the relevant node is removed by verifying that
// there is no hang.
function NoHang(re) {
- print(re);
"This is an ASCII string that could take forever".match(re);
}
=======================================
--- /branches/bleeding_edge/test/mjsunit/regexp-capture.js Fri Apr 15
04:35:36 2011
+++ /branches/bleeding_edge/test/mjsunit/regexp-capture.js Fri Jun 1
04:28:52 2012
@@ -56,3 +56,5 @@
assertEquals(["bbaa", "a", "", "a"],
/((\3|b)\2(a)){2,}/.exec("bbaababbabaaaaabbaaaabba"));
+// From crbug.com/128821 - don't hang:
+"".match(/((a|i|A|I|u|o|U|O)(s|c|b|c|d|f|g|h|j|k|l|m|n|p|q|r|s|t|v|w|x|y|z|
B|C|D|F|G|H|J|K|L|M|N|P|Q|R|S|T|V|W|X|Y|Z)*) de\/da([.,!?\s]|$)/);
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
