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

src/ast/ast.cc

 // 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.
 
 #include "src/ast/ast.h"
 
 #include <cmath>  // For isfinite.
 #include "src/ast/scopes.h"
 #include "src/builtins.h"
 #include "src/code-stubs.h"
@@ skipping 908 matching lines @@
 bool RegExpCapture::IsAnchoredAtStart() {
   return body()->IsAnchoredAtStart();
 }
 
 
 bool RegExpCapture::IsAnchoredAtEnd() {
   return body()->IsAnchoredAtEnd();
 }
 
 
+int RegExpBackReference::max_match() {

[erikcorry, 2015/12/15 08:09:19]

Alternative simpler implementation is to return kInfinity here.

+  switch (max_match_) {
+    case kRecursionMarker:
+      // The back reference references a capture that references this back
+      // reference, leading to a recursion, e.g. /(\2)(\1)/.
+      // Such captures cannot be satisfied and have the length 0.
+      max_match_ = 0;
+      break;
+    case kUninitialized:
+      // The max match length of a back reference is the length of the capture.
+      if (capture_->body()) {
+        // Mark this back reference to break possible recursion before
+        // descending into the capture.
+        max_match_ = kRecursionMarker;
+        max_match_ = capture_->max_match();
+      } else {
+        // If the capture has no body, it has not been parsed and does not
+        // exist. Hence the length is 0.
+        max_match_ = 0;
+      }
+      break;
+    default:
+      // max_match_ has already been found.
+      break;
+  }
+  return max_match_;
+}
+
+
 // Convert regular expression trees to a simple sexp representation.
 // This representation should be different from the input grammar
 // in as many cases as possible, to make it more difficult for incorrect
 // parses to look as correct ones which is likely if the input and
 // output formats are alike.
 class RegExpUnparser final : public RegExpVisitor {
  public:
   RegExpUnparser(std::ostream& os, Zone* zone) : os_(os), zone_(zone) {}
   void VisitCharacterRange(CharacterRange that);
 #define MAKE_CASE(Name) void* Visit##Name(RegExp##Name*, void* data) override;
@@ skipping 208 matching lines @@
 bool Literal::Match(void* literal1, void* literal2) {
   const AstValue* x = static_cast<Literal*>(literal1)->raw_value();
   const AstValue* y = static_cast<Literal*>(literal2)->raw_value();
   return (x->IsString() && y->IsString() && x->AsString() == y->AsString()) ||
          (x->IsNumber() && y->IsNumber() && x->AsNumber() == y->AsNumber());
 }
 
 
 }  // namespace internal
 }  // namespace v8