Backport to 3.10 of r11696: Limit work done analyzing regexps with very large fanout.

src/jsregexp.h

 // 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 556 matching lines @@
   // Only returns the successor for a text node of length 1 that matches any
   // character and that has no guards on it.
   virtual RegExpNode* GetSuccessorOfOmnivorousTextNode(
       RegExpCompiler* compiler) {
     return NULL;
   }
 
   // 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();
   }
 
   // If we know that the input is ASCII then there are some nodes that can
   // never match.  This method returns a node that can be substituted for
   // itself, or NULL if the node can never match.
   virtual RegExpNode* FilterASCII(int depth) { return this; }
   // Helper for FilterASCII.
@@ skipping 82 matching lines @@
 
 class SeqRegExpNode: public RegExpNode {
  public:
   explicit SeqRegExpNode(RegExpNode* on_success)
       : on_success_(on_success) { }
   RegExpNode* on_success() { return on_success_; }
   void set_on_success(RegExpNode* node) { on_success_ = node; }
   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);
   }
 
  protected:
   RegExpNode* FilterSuccessor(int depth);
 
  private:
   RegExpNode* on_success_;
 };
 
@@ skipping 34 matching lines @@
                           bool not_at_start);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int filled_in,
                                     bool not_at_start) {
     return on_success()->GetQuickCheckDetails(
         details, compiler, filled_in, not_at_start);
   }
   virtual void FillInBMInfo(int offset,
                             int recursion_depth,
+                            int budget,
                             BoyerMooreLookahead* bm,
                             bool not_at_start);
   Type type() { return type_; }
   // TODO(erikcorry): We should allow some action nodes in greedy loops.
   virtual int GreedyLoopTextLength() { return kNodeIsTooComplexForGreedyLoops; }
 
  private:
   union {
     struct {
       int reg;
@@ skipping 51 matching lines @@
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start);
   ZoneList<TextElement>* elements() { return elms_; }
   void MakeCaseIndependent(bool is_ascii);
   virtual int GreedyLoopTextLength();
   virtual RegExpNode* GetSuccessorOfOmnivorousTextNode(
       RegExpCompiler* compiler);
   virtual void FillInBMInfo(int offset,
                             int recursion_depth,
+                            int budget,
                             BoyerMooreLookahead* bm,
                             bool not_at_start);
   void CalculateOffsets();
   virtual RegExpNode* FilterASCII(int depth);
 
  private:
   enum TextEmitPassType {
     NON_ASCII_MATCH,             // Check for characters that can't match.
     SIMPLE_CHARACTER_MATCH,      // Case-dependent single character check.
     NON_LETTER_CHARACTER_MATCH,  // Check characters that have no case equivs.
@@ skipping 42 matching lines @@
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find,
                           int recursion_depth,
                           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);
   AssertionNodeType type() { return type_; }
   void set_type(AssertionNodeType type) { type_ = type; }
 
  private:
   void EmitBoundaryCheck(RegExpCompiler* compiler, Trace* trace);
   enum IfPrevious { kIsNonWord, kIsWord };
   void BacktrackIfPrevious(RegExpCompiler* compiler,
                            Trace* trace,
@@ skipping 20 matching lines @@
                           int recursion_depth,
                           bool not_at_start);
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start) {
     return;
   }
   virtual void FillInBMInfo(int offset,
                             int recursion_depth,
+                            int budget,
                             BoyerMooreLookahead* bm,
                             bool not_at_start);
 
  private:
   int start_reg_;
   int end_reg_;
 };
 
 
 class EndNode: public RegExpNode {
  public:
   enum Action { ACCEPT, BACKTRACK, NEGATIVE_SUBMATCH_SUCCESS };
   explicit EndNode(Action action) : action_(action) { }
   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) { return 0; }
   virtual void GetQuickCheckDetails(QuickCheckDetails* details,
                                     RegExpCompiler* compiler,
                                     int characters_filled_in,
                                     bool not_at_start) {
     // Returning 0 from EatsAtLeast should ensure we never get here.
     UNREACHABLE();
   }
   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.
     UNREACHABLE();
   }
 
  private:
   Action action_;
 };
 
@@ skipping 72 matching lines @@
   int EatsAtLeastHelper(int still_to_find,
                         int recursion_depth,
                         RegExpNode* ignore_this_node,
                         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);
 
   bool being_calculated() { return being_calculated_; }
   bool not_at_start() { return not_at_start_; }
   void set_not_at_start() { not_at_start_ = true; }
   void set_being_calculated(bool b) { being_calculated_ = b; }
   virtual bool try_to_emit_quick_check_for_alternative(int i) { return true; }
   virtual RegExpNode* FilterASCII(int depth);
 
@@ skipping 32 matching lines @@
   }
   virtual int EatsAtLeast(int still_to_find,
                           int recursion_depth,
                           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, 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
   // alternative that is expected to fail.  This is because quick check code
   // starts by loading enough characters for the alternative that takes fewest
   // characters, but on a negative lookahead the negative branch did not take
   // part in that calculation (EatsAtLeast) so the assumptions don't hold.
   virtual bool try_to_emit_quick_check_for_alternative(int i) { return i != 0; }
   virtual RegExpNode* FilterASCII(int depth);
 };
@@ skipping 11 matching lines @@
   virtual void Emit(RegExpCompiler* compiler, Trace* trace);
   virtual int EatsAtLeast(int still_to_find,
                           int recursion_depth,
                           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);
   RegExpNode* loop_node() { return loop_node_; }
   RegExpNode* continue_node() { return continue_node_; }
   bool body_can_be_zero_length() { return body_can_be_zero_length_; }
   virtual void Accept(NodeVisitor* visitor);
   virtual RegExpNode* FilterASCII(int depth);
 
  private:
   // AddAlternative is made private for loop nodes because alternatives
@@ skipping 476 matching lines @@
   int* vector_;
   int offsets_vector_length_;
 
   friend class ExternalReference;
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_JSREGEXP_H_