Reviewers: danno,
Description:
Backport to 3.10 of r11696: Limit work done analyzing regexps with very
large
fanout.
BUG=128821
Original review URL: https://chromiumcodereview.appspot.com/10448117
Please review this at https://chromiumcodereview.appspot.com/10536002/
SVN Base: http://v8.googlecode.com/svn/branches/3.10/
Affected files:
M src/jsregexp.h
M src/jsregexp.cc
M src/version.cc
M test/mjsunit/regexp-capture-3.js
M test/mjsunit/regexp-capture.js
Index: src/jsregexp.cc
===================================================================
--- src/jsregexp.cc (revision 11709)
+++ src/jsregexp.cc (working copy)
@@ -2175,12 +2175,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);
}
@@ -2204,11 +2206,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);
}
@@ -2791,15 +2795,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);
}
@@ -2901,7 +2908,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;
}
@@ -3839,7 +3846,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 {
@@ -5580,6 +5587,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
@@ -5595,9 +5603,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) {
@@ -5605,7 +5615,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);
}
@@ -5613,6 +5624,7 @@
void TextNode::FillInBMInfo(int initial_offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start) {
if (initial_offset >= bm->length()) return;
@@ -5669,6 +5681,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 11709)
+++ src/jsregexp.h (working copy)
@@ -574,9 +574,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();
@@ -679,9 +682,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);
}
@@ -736,6 +741,7 @@
}
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
Type type() { return type_; }
@@ -807,6 +813,7 @@
RegExpCompiler* compiler);
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
void CalculateOffsets();
@@ -869,6 +876,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_; }
@@ -909,6 +917,7 @@
}
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
@@ -936,6 +945,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.
@@ -1028,6 +1038,7 @@
bool not_at_start);
virtual void FillInBMInfo(int offset,
int recursion_depth,
+ int budget,
BoyerMooreLookahead* bm,
bool not_at_start);
@@ -1080,10 +1091,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
@@ -1115,6 +1127,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: src/version.cc
===================================================================
--- src/version.cc (revision 11709)
+++ src/version.cc (working copy)
@@ -35,7 +35,7 @@
#define MAJOR_VERSION 3
#define MINOR_VERSION 10
#define BUILD_NUMBER 8
-#define PATCH_LEVEL 12
+#define PATCH_LEVEL 13
// Use 1 for candidates and 0 otherwise.
// (Boolean macro values are not supported by all preprocessors.)
#define IS_CANDIDATE_VERSION 0
Index: test/mjsunit/regexp-capture-3.js
===================================================================
--- test/mjsunit/regexp-capture-3.js (revision 11709)
+++ test/mjsunit/regexp-capture-3.js (working copy)
@@ -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);
}
Index: test/mjsunit/regexp-capture.js
===================================================================
--- test/mjsunit/regexp-capture.js (revision 11709)
+++ 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
