[regexp] break recursion in mutually recursive capture/back references.

src/ast/ast.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_AST_AST_H_
 #define V8_AST_AST_H_
 
 #include "src/assembler.h"
 #include "src/ast/ast-value-factory.h"
 #include "src/ast/modules.h"
@@ skipping 2856 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;
+  static const int kUninitialized = -1;
   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;
   // Returns the interval of registers used for captures within this
   // expression.
   virtual Interval CaptureRegisters() { return Interval::Empty(); }
   virtual void AppendToText(RegExpText* text, Zone* zone);
   std::ostream& Print(std::ostream& os, Zone* zone);  // NOLINT
 #define MAKE_ASTYPE(Name)                                                  \
   virtual RegExp##Name* As##Name();                                        \
   virtual bool Is##Name();
   FOR_EACH_REG_EXP_TREE_TYPE(MAKE_ASTYPE)
 #undef MAKE_ASTYPE
 };
 
 
 class RegExpDisjunction final : public RegExpTree {
  public:
-  explicit RegExpDisjunction(ZoneList<RegExpTree*>* alternatives);
+  explicit RegExpDisjunction(ZoneList<RegExpTree*>* alternatives)
+      : alternatives_(alternatives),
+        min_match_(kUninitialized),
+        max_match_(kUninitialized) {
+    DCHECK(alternatives->length() > 1);
+  }
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   RegExpDisjunction* AsDisjunction() override;
   Interval CaptureRegisters() override;
   bool IsDisjunction() override;
   bool IsAnchoredAtStart() override;
   bool IsAnchoredAtEnd() override;
-  int min_match() override { return min_match_; }
-  int max_match() override { return max_match_; }
+  int min_match() override {
+    if (min_match_ == kUninitialized) LazilyComputeMatchLengths();
+    return min_match_;
+  }
+  int max_match() override {
+    if (max_match_ == kUninitialized) LazilyComputeMatchLengths();
+    return max_match_;
+  }
   ZoneList<RegExpTree*>* alternatives() { return alternatives_; }
+
  private:
+  void LazilyComputeMatchLengths();
   bool SortConsecutiveAtoms(RegExpCompiler* compiler);
   void RationalizeConsecutiveAtoms(RegExpCompiler* compiler);
   void FixSingleCharacterDisjunctions(RegExpCompiler* compiler);
   ZoneList<RegExpTree*>* alternatives_;
   int min_match_;
   int max_match_;
 };
 
 
 class RegExpAlternative final : public RegExpTree {
  public:
-  explicit RegExpAlternative(ZoneList<RegExpTree*>* nodes);
+  explicit RegExpAlternative(ZoneList<RegExpTree*>* nodes)
+      : nodes_(nodes), min_match_(kUninitialized), max_match_(kUninitialized) {
+    DCHECK(nodes->length() > 1);
+  }
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   RegExpAlternative* AsAlternative() override;
   Interval CaptureRegisters() override;
   bool IsAlternative() override;
   bool IsAnchoredAtStart() override;
   bool IsAnchoredAtEnd() override;
-  int min_match() override { return min_match_; }
-  int max_match() override { return max_match_; }
+  int min_match() override {
+    if (min_match_ == kUninitialized) LazilyComputeMatchLengths();
+    return min_match_;
+  }
+  int max_match() override {
+    if (max_match_ == kUninitialized) LazilyComputeMatchLengths();
+    return max_match_;
+  }
   ZoneList<RegExpTree*>* nodes() { return nodes_; }
+
  private:
+  void LazilyComputeMatchLengths();
   ZoneList<RegExpTree*>* nodes_;
   int min_match_;
   int max_match_;
 };
 
 
 class RegExpAssertion final : public RegExpTree {
  public:
   enum AssertionType {
     START_OF_LINE,
@@ skipping 122 matching lines @@
 };
 
 
 class RegExpQuantifier final : public RegExpTree {
  public:
   enum QuantifierType { GREEDY, NON_GREEDY, POSSESSIVE };
   RegExpQuantifier(int min, int max, QuantifierType type, RegExpTree* body)
       : body_(body),
         min_(min),
         max_(max),
-        min_match_(min * body->min_match()),
-        quantifier_type_(type) {
-    if (max > 0 && body->max_match() > kInfinity / max) {
-      max_match_ = kInfinity;
-    } else {
-      max_match_ = max * body->max_match();
-    }
-  }
+        min_match_(kUninitialized),
+        max_match_(kUninitialized),
+        quantifier_type_(type) {}
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   static RegExpNode* ToNode(int min,
                             int max,
                             bool is_greedy,
                             RegExpTree* body,
                             RegExpCompiler* compiler,
                             RegExpNode* on_success,
                             bool not_at_start = false);
   RegExpQuantifier* AsQuantifier() override;
   Interval CaptureRegisters() override;
   bool IsQuantifier() override;
-  int min_match() override { return min_match_; }
-  int max_match() override { return max_match_; }
+  int min_match() override {
+    if (min_match_ == kUninitialized) LazilyComputeMatchLengths();
+    return min_match_;
+  }
+  int max_match() override {
+    if (max_match_ == kUninitialized) LazilyComputeMatchLengths();
+    return max_match_;
+  }
   int min() { return min_; }
   int max() { return max_; }
   bool is_possessive() { return quantifier_type_ == POSSESSIVE; }
   bool is_non_greedy() { return quantifier_type_ == NON_GREEDY; }
   bool is_greedy() { return quantifier_type_ == GREEDY; }
   RegExpTree* body() { return body_; }
 
  private:
+  void LazilyComputeMatchLengths();
   RegExpTree* body_;
   int min_;
   int max_;
   int min_match_;
   int max_match_;
   QuantifierType quantifier_type_;
 };
 
 
 class RegExpCapture final : public RegExpTree {
@@ skipping 55 matching lines @@
   bool is_positive_;
   int capture_count_;
   int capture_from_;
   Type type_;
 };
 
 
 class RegExpBackReference final : public RegExpTree {
  public:
   explicit RegExpBackReference(RegExpCapture* capture)
-      : capture_(capture) { }
+      : capture_(capture), max_match_(kUninitialized) {}
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   RegExpBackReference* AsBackReference() override;
   bool IsBackReference() override;
   int min_match() override { return 0; }
-  // The capture may not be completely parsed yet, if the reference occurs
-  // before the capture. In the ordinary case, nothing has been captured yet,
-  // so the back reference must have the length 0. If the back reference is
-  // inside a lookbehind, effectively making it a forward reference, we return
-  // 0 since lookbehinds have a length of 0.
-  int max_match() override {
-    return capture_->body() ? capture_->max_match() : 0;
-  }
+  int max_match() override;
   int index() { return capture_->index(); }
   RegExpCapture* capture() { return capture_; }
  private:
+  static const int kRecursionMarker = -2;
+  STATIC_ASSERT(kRecursionMarker != kUninitialized);
+
   RegExpCapture* capture_;
+  int max_match_;
 };
 
 
 class RegExpEmpty final : public RegExpTree {
  public:
   RegExpEmpty() { }
   void* Accept(RegExpVisitor* visitor, void* data) override;
   RegExpNode* ToNode(RegExpCompiler* compiler, RegExpNode* on_success) override;
   RegExpEmpty* AsEmpty() override;
   bool IsEmpty() override;
@@ skipping 504 matching lines @@
   // the parser-level zone.
   Zone* parser_zone_;
   AstValueFactory* ast_value_factory_;
 };
 
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_AST_AST_H_