Avoid OOM on regexps with nested quantifiers.

src/ast.h

 // Copyright 2011 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 1745 matching lines @@
 #define MAKE_CASE(Name)                                              \
   virtual void* Visit##Name(RegExp##Name*, void* data) = 0;
   FOR_EACH_REG_EXP_TREE_TYPE(MAKE_CASE)
 #undef MAKE_CASE
 };
 
 
 class RegExpTree: public ZoneObject {
  public:
   static const int kInfinity = kMaxInt;
+  RegExpTree() : contains_expanded_quantifier_(false) { }
   virtual ~RegExpTree() { }
   virtual void* Accept(RegExpVisitor* visitor, void* data) = 0;
   virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                              RegExpNode* on_success) = 0;
   virtual bool IsTextElement() { return false; }
   virtual bool IsAnchoredAtStart() { return false; }
   virtual bool IsAnchoredAtEnd() { return false; }
   virtual int min_match() = 0;
   virtual int max_match() = 0;
+  virtual bool ContainsExpandedQuantifier() {
+    return contains_expanded_quantifier_;
+  }
+  void set_contains_expanded_quantifier(bool value) {
+    contains_expanded_quantifier_ = value;
+  }
   // Returns the interval of registers used for captures within this
   // expression.
   virtual Interval CaptureRegisters() { return Interval::Empty(); }
   virtual void AppendToText(RegExpText* text);
   SmartPointer<const char> ToString();
 #define MAKE_ASTYPE(Name)                                                  \
   virtual RegExp##Name* As##Name();                                        \
   virtual bool Is##Name();
   FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ASTYPE)
 #undef MAKE_ASTYPE
+
+ protected:
+  bool contains_expanded_quantifier_;
 };
 
 
 class RegExpDisjunction: public RegExpTree {
  public:
   explicit RegExpDisjunction(ZoneList<RegExpTree*>* alternatives);
   virtual void* Accept(RegExpVisitor* visitor, void* data);
   virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                              RegExpNode* on_success);
   virtual RegExpDisjunction* AsDisjunction();
   virtual Interval CaptureRegisters();
   virtual bool IsDisjunction();
   virtual bool IsAnchoredAtStart();
   virtual bool IsAnchoredAtEnd();
   virtual int min_match() { return min_match_; }
   virtual int max_match() { return max_match_; }
+  virtual bool ContainsExpandedQuantifier();
   ZoneList<RegExpTree*>* alternatives() { return alternatives_; }
  private:
   ZoneList<RegExpTree*>* alternatives_;
   int min_match_;
   int max_match_;
 };
 
 
 class RegExpAlternative: public RegExpTree {
  public:
   explicit RegExpAlternative(ZoneList<RegExpTree*>* nodes);
   virtual void* Accept(RegExpVisitor* visitor, void* data);
   virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                              RegExpNode* on_success);
   virtual RegExpAlternative* AsAlternative();
   virtual Interval CaptureRegisters();
   virtual bool IsAlternative();
   virtual bool IsAnchoredAtStart();
   virtual bool IsAnchoredAtEnd();
   virtual int min_match() { return min_match_; }
   virtual int max_match() { return max_match_; }
+  virtual bool ContainsExpandedQuantifier();
   ZoneList<RegExpTree*>* nodes() { return nodes_; }
  private:
   ZoneList<RegExpTree*>* nodes_;
   int min_match_;
   int max_match_;
 };
 
 
 class RegExpAssertion: public RegExpTree {
  public:
@@ skipping 129 matching lines @@
 
 
 class RegExpQuantifier: public RegExpTree {
  public:
   enum Type { GREEDY, NON_GREEDY, POSSESSIVE };
   RegExpQuantifier(int min, int max, Type type, RegExpTree* body)
       : body_(body),
         min_(min),
         max_(max),
         min_match_(min * body->min_match()),
-        type_(type) {
+        type_(type),
+        contains_expanded_quantifier_(false) {
     if (max > 0 && body->max_match() > kInfinity / max) {
       max_match_ = kInfinity;
     } else {
       max_match_ = max * body->max_match();
     }
   }
   virtual void* Accept(RegExpVisitor* visitor, void* data);
   virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                              RegExpNode* on_success);
   static RegExpNode* ToNode(int min,
                             int max,
                             bool is_greedy,
                             RegExpTree* body,
                             RegExpCompiler* compiler,
                             RegExpNode* on_success,
                             bool not_at_start = false);
   virtual RegExpQuantifier* AsQuantifier();
   virtual Interval CaptureRegisters();
   virtual bool IsQuantifier();
   virtual int min_match() { return min_match_; }
   virtual int max_match() { return max_match_; }
+  virtual bool ContainsExpandedQuantifier() {
+    return contains_expanded_quantifier_ || body_->ContainsExpandedQuantifier();
+  }
   int min() { return min_; }
   int max() { return max_; }
   bool is_possessive() { return type_ == POSSESSIVE; }
   bool is_non_greedy() { return type_ == NON_GREEDY; }
   bool is_greedy() { return type_ == GREEDY; }
   RegExpTree* body() { return body_; }
 
  private:
   RegExpTree* body_;
   int min_;
   int max_;
   int min_match_;
   int max_match_;
   Type type_;
+  bool contains_expanded_quantifier_;
 };
 
 
 class RegExpCapture: public RegExpTree {
  public:
   explicit RegExpCapture(RegExpTree* body, int index)
       : body_(body), index_(index) { }
   virtual void* Accept(RegExpVisitor* visitor, void* data);
   virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                              RegExpNode* on_success);
   static RegExpNode* ToNode(RegExpTree* body,
                             int index,
                             RegExpCompiler* compiler,
                             RegExpNode* on_success);
   virtual RegExpCapture* AsCapture();
   virtual bool IsAnchoredAtStart();
   virtual bool IsAnchoredAtEnd();
   virtual Interval CaptureRegisters();
   virtual bool IsCapture();
   virtual int min_match() { return body_->min_match(); }
   virtual int max_match() { return body_->max_match(); }
+  virtual bool ContainsExpandedQuantifier() {
+    return contains_expanded_quantifier_ || body_->ContainsExpandedQuantifier();
+  }
   RegExpTree* body() { return body_; }
   int index() { return index_; }
   static int StartRegister(int index) { return index * 2; }
   static int EndRegister(int index) { return index * 2 + 1; }
 
  private:
   RegExpTree* body_;
   int index_;
 };
 
@@ skipping 11 matching lines @@
 
   virtual void* Accept(RegExpVisitor* visitor, void* data);
   virtual RegExpNode* ToNode(RegExpCompiler* compiler,
                              RegExpNode* on_success);
   virtual RegExpLookahead* AsLookahead();
   virtual Interval CaptureRegisters();
   virtual bool IsLookahead();
   virtual bool IsAnchoredAtStart();
   virtual int min_match() { return 0; }
   virtual int max_match() { return 0; }
+  virtual bool ContainsExpandedQuantifier() {
+    return contains_expanded_quantifier_ || body_->ContainsExpandedQuantifier();
+  }
   RegExpTree* body() { return body_; }
   bool is_positive() { return is_positive_; }
   int capture_count() { return capture_count_; }
   int capture_from() { return capture_from_; }
 
  private:
   RegExpTree* body_;
   bool is_positive_;
   int capture_count_;
   int capture_from_;
@@ skipping 75 matching lines @@
 
  private:
   Isolate* isolate_;
   bool stack_overflow_;
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_AST_H_