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

src/ast/ast.h

Index: src/ast/ast.h
diff --git a/src/ast/ast.h b/src/ast/ast.h
index b4f2992e047215ac95d2c61b96a98d64afbfb5a1..ea81eba4caf9c1c39abf664890178ae84148ae76 100644
--- a/src/ast/ast.h
+++ b/src/ast/ast.h
@@ -2874,6 +2874,7 @@ class RegExpVisitor BASE_EMBEDDED {
 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,
@@ -2898,7 +2899,12 @@ class RegExpTree : public ZoneObject {
 
 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;
@@ -2906,10 +2912,18 @@ class RegExpDisjunction final : public RegExpTree {
   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);
@@ -2921,7 +2935,10 @@ class RegExpDisjunction final : public RegExpTree {
 
 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;
@@ -2929,10 +2946,18 @@ class RegExpAlternative final : public RegExpTree {
   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_;
@@ -3075,14 +3100,9 @@ class RegExpQuantifier final : public RegExpTree {
       : 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,
@@ -3095,8 +3115,14 @@ class RegExpQuantifier final : public RegExpTree {
   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; }
@@ -3105,6 +3131,7 @@ class RegExpQuantifier final : public RegExpTree {
   RegExpTree* body() { return body_; }
 
  private:
+  void LazilyComputeMatchLengths();
   RegExpTree* body_;
   int min_;
   int max_;
@@ -3180,24 +3207,21 @@ class RegExpLookaround final : public RegExpTree {
 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_;
 };