Reviewers: ulan,
Description:
Limit work done analyzing regexps with very large fanout.
BUG=128821
Please review this at https://chromiumcodereview.appspot.com/10448117/
SVN Base: http://v8.googlecode.com/svn/branches/bleeding_edge/
Affected files:
M src/jsregexp.h
M src/jsregexp.cc
M test/mjsunit/regexp-capture.js
Index: src/jsregexp.cc
===================================================================
--- src/jsregexp.cc (revision 11692)
+++ src/jsregexp.cc (working copy)
@@ -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, 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 /= 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);
Index: src/jsregexp.h
===================================================================
--- src/jsregexp.h (revision 11692)
+++ src/jsregexp.h (working copy)
@@ -581,8 +581,10 @@
// we look forward. This is used for a Boyer-Moore-like string searching
// implementation. TODO(erikcorry): This should share more code with
// EatsAtLeast, GetQuickCheckDetails.
+ static const int kFillInBMBudget = 200;
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
UNREACHABLE();
@@ -685,9 +687,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 +746,7 @@
}
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
Type type() { return type_; }
@@ -813,6 +818,7 @@
RegExpCompiler* compiler);
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
void CalculateOffsets();
@@ -875,6 +881,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 +922,7 @@
}
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
@@ -942,6 +950,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 +1043,7 @@
bool not_at_start);
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
@@ -1086,10 +1096,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 +1132,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_; }
Index: test/mjsunit/regexp-capture.js
===================================================================
--- test/mjsunit/regexp-capture.js (revision 11692)
+++ test/mjsunit/regexp-capture.js (working copy)
@@ -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
