Avoid overdeep recursion in regexp where a guarded expression with a

src/jsregexp.cc

 // 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
@@ skipping 2173 matching lines @@
                             bool not_at_start) {
   if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
   if (type_ == POSITIVE_SUBMATCH_SUCCESS) return 0;  // Rewinds input!
   return on_success()->EatsAtLeast(still_to_find,
                                    recursion_depth + 1,
                                    not_at_start);
 }
 
 
 void ActionNode::FillInBMInfo(int offset,
+                              int recursion_depth,
                               BoyerMooreLookahead* bm,
                               bool not_at_start) {
   if (type_ == BEGIN_SUBMATCH) {
     bm->SetRest(offset);
   } else if (type_ != POSITIVE_SUBMATCH_SUCCESS) {
-    on_success()->FillInBMInfo(offset, bm, not_at_start);
+    on_success()->FillInBMInfo(offset, recursion_depth + 1, bm, not_at_start);
   }
   SaveBMInfo(bm, not_at_start, offset);
 }
 
 
 int AssertionNode::EatsAtLeast(int still_to_find,
                                int recursion_depth,
                                bool not_at_start) {
   if (recursion_depth > RegExpCompiler::kMaxRecursion) 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
   // that won't prevent us from preloading a lot of characters for the other
   // 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,
                                    not_at_start);
 }
 
 
-void AssertionNode::FillInBMInfo(
-    int offset, BoyerMooreLookahead* bm, bool not_at_start) {
+void AssertionNode::FillInBMInfo(int offset,
+                                 int recursion_depth,
+                                 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, bm, not_at_start);
+  on_success()->FillInBMInfo(offset, recursion_depth + 1, bm, not_at_start);
   SaveBMInfo(bm, not_at_start, offset);
 }
 
 
 int BackReferenceNode::EatsAtLeast(int still_to_find,
                                    int recursion_depth,
                                    bool not_at_start) {
   if (recursion_depth > RegExpCompiler::kMaxRecursion) return 0;
   return on_success()->EatsAtLeast(still_to_find,
                                    recursion_depth + 1,
@@ skipping 560 matching lines @@
                                           bool not_at_start) {
   if (body_can_be_zero_length_ || info()->visited) return;
   VisitMarker marker(info());
   return ChoiceNode::GetQuickCheckDetails(details,
                                           compiler,
                                           characters_filled_in,
                                           not_at_start);
 }
 
 
-void LoopChoiceNode::FillInBMInfo(
-    int offset, BoyerMooreLookahead* bm, bool not_at_start) {
-  if (body_can_be_zero_length_) {
+void LoopChoiceNode::FillInBMInfo(int offset,
+                                  int recursion_depth,
+                                  BoyerMooreLookahead* bm,
+                                  bool not_at_start) {
+  if (body_can_be_zero_length_ ||
+      recursion_depth > RegExpCompiler::kMaxRecursion) {
     bm->SetRest(offset);
     SaveBMInfo(bm, not_at_start, offset);
     return;
   }
-  ChoiceNode::FillInBMInfo(offset, bm, not_at_start);
+  ChoiceNode::FillInBMInfo(offset, recursion_depth + 1, bm, not_at_start);
   SaveBMInfo(bm, not_at_start, offset);
 }
 
 
 void ChoiceNode::GetQuickCheckDetails(QuickCheckDetails* details,
                                       RegExpCompiler* compiler,
                                       int characters_filled_in,
                                       bool not_at_start) {
   not_at_start = (not_at_start || not_at_start_);
   int choice_count = alternatives_->length();
@@ skipping 81 matching lines @@
   Trace::TriBool next_is_word_character = Trace::UNKNOWN;
   bool not_at_start = (trace->at_start() == Trace::FALSE);
   BoyerMooreLookahead* lookahead = bm_info(not_at_start);
   if (lookahead == NULL) {
     int eats_at_least =
         Min(kMaxLookaheadForBoyerMoore,
             EatsAtLeast(kMaxLookaheadForBoyerMoore, 0, not_at_start));
     if (eats_at_least >= 1) {
       BoyerMooreLookahead* bm =
           new BoyerMooreLookahead(eats_at_least, compiler);
-      FillInBMInfo(0, bm, not_at_start);
+      FillInBMInfo(0, 0, 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;
     }
   } else {
     if (lookahead->at(0)->is_non_word()) next_is_word_character = Trace::FALSE;
     if (lookahead->at(0)->is_word()) next_is_word_character = Trace::TRUE;
   }
   bool at_boundary = (type_ == AssertionNode::AT_BOUNDARY);
   if (next_is_word_character == Trace::UNKNOWN) {
     Label before_non_word;
@@ skipping 917 matching lines @@
         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));
           if (eats_at_least >= 1) {
             BoyerMooreLookahead* bm =
                 new BoyerMooreLookahead(eats_at_least, compiler);
             GuardedAlternative alt0 = alternatives_->at(0);
-            alt0.node()->FillInBMInfo(0, bm, not_at_start);
+            alt0.node()->FillInBMInfo(0, 0, bm, not_at_start);
             skip_was_emitted = bm->EmitSkipInstructions(macro_assembler);
           }
         } else {
           skip_was_emitted = lookahead->EmitSkipInstructions(macro_assembler);
         }
       }
     }
   }
 
   if (eats_at_least == kEatsAtLeastNotYetInitialized) {
@@ skipping 1718 matching lines @@
 void Analysis::VisitBackReference(BackReferenceNode* that) {
   EnsureAnalyzed(that->on_success());
 }
 
 
 void Analysis::VisitAssertion(AssertionNode* that) {
   EnsureAnalyzed(that->on_success());
 }
 
 
-void BackReferenceNode::FillInBMInfo(
-    int offset, BoyerMooreLookahead* bm, bool not_at_start) {
+void BackReferenceNode::FillInBMInfo(int offset,
+                                     int recursion_depth,
+                                     BoyerMooreLookahead* bm,
+                                     bool not_at_start) {
   // Working out the set of characters that a backreference can match is too
   // hard, so we just say that any character can match.
   bm->SetRest(offset);
   SaveBMInfo(bm, not_at_start, offset);
 }
 
 
 STATIC_ASSERT(BoyerMoorePositionInfo::kMapSize ==
               RegExpMacroAssembler::kTableSize);
 
 
-void ChoiceNode::FillInBMInfo(
-    int offset, BoyerMooreLookahead* bm, bool not_at_start) {
+void ChoiceNode::FillInBMInfo(int offset,
+                              int recursion_depth,
+                              BoyerMooreLookahead* bm,
+                              bool not_at_start) {
   ZoneList<GuardedAlternative>* alts = alternatives();

[ulan, 2012/05/31 11:56:23]

We don't check recursion_depth here, because nesting of choice nodes is limited
somewhere else?

[Erik Corry, 2012/05/31 13:51:43]

Yes, it's only LoopChoiceNodes that can lead to unrestricted recursion.

   for (int i = 0; i < alts->length(); i++) {
     GuardedAlternative& alt = alts->at(i);
     if (alt.guards() != NULL && alt.guards()->length() != 0) {
       bm->SetRest(offset);  // Give up trying to fill in info.
       SaveBMInfo(bm, not_at_start, offset);
       return;
     }
-    alt.node()->FillInBMInfo(offset, bm, not_at_start);
+    alt.node()->FillInBMInfo(offset, recursion_depth + 1, bm, not_at_start);
   }
   SaveBMInfo(bm, not_at_start, offset);
 }
 
 
-void TextNode::FillInBMInfo(
-    int initial_offset, BoyerMooreLookahead* bm, bool not_at_start) {
+void TextNode::FillInBMInfo(int initial_offset,
+                            int recursion_depth,
+                            BoyerMooreLookahead* bm,
+                            bool not_at_start) {
   if (initial_offset >= bm->length()) return;
   int offset = initial_offset;
   int max_char = bm->max_char();
   for (int i = 0; i < elements()->length(); i++) {
     if (offset >= bm->length()) {
       if (initial_offset == 0) set_bm_info(not_at_start, bm);
       return;
     }
     TextElement text = elements()->at(i);
     if (text.type == TextElement::ATOM) {
@@ skipping 33 matching lines @@
         }
       }
       offset++;
     }
   }
   if (offset >= bm->length()) {
     if (initial_offset == 0) set_bm_info(not_at_start, bm);
     return;
   }
   on_success()->FillInBMInfo(offset,
+                             recursion_depth + 1,
                              bm,
                              true);  // Not at start after a text node.
   if (initial_offset == 0) set_bm_info(not_at_start, bm);
 }
 
 
 // -------------------------------------------------------------------
 // Dispatch table construction
 
 
@@ skipping 218 matching lines @@
   macro_assembler.set_global(is_global);
 
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal