[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() {
+  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.

[erikcorry, 2015/12/15 09:45:43]

This may well just be a bug in a comment, but here's a recursion that can be
satisfied and has a length not == 0.

/(x\2)(y\1)$/.test("...xyx")   // True

[Yang, 2015/12/15 09:52:18]

You are right. It should be "Such back references must have the length 0".

[erikcorry, 2015/12/15 10:18:18]

My example regexp seems to contradict the revised version of the comment still.

+      max_match_ = 0;
+      break;
+    case kUninitialized:
+      // The max match length of a back reference is the length of the capture.
+      // Mark this back reference to break possible recursion before
+      // descending into the capture.
+      max_match_ = kRecursionMarker;
+      // The capture has been parsed.
+      DCHECK_NOT_NULL(capture_->body());
+      max_match_ = capture_->max_match();
+      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 145 matching lines @@
 }
 
 
 std::ostream& RegExpTree::Print(std::ostream& os, Zone* zone) {  // NOLINT
   RegExpUnparser unparser(os, zone);
   Accept(&unparser, NULL);
   return os;
 }
 
 
-RegExpDisjunction::RegExpDisjunction(ZoneList<RegExpTree*>* alternatives)
-    : alternatives_(alternatives) {
-  DCHECK(alternatives->length() > 1);
-  RegExpTree* first_alternative = alternatives->at(0);
+void RegExpDisjunction::LazilyComputeMatchLengths() {
+  // We cannot compute this in the constructor because at the time of parsing
+  // back referenced captures have not yet been parsed yet.
+  RegExpTree* first_alternative = alternatives_->at(0);
   min_match_ = first_alternative->min_match();

[erikcorry, 2015/12/15 09:45:43]

This looks a bit dodgy.  We are not done calculating it, but we overwrite the
kUninitialized already here?  I think we should write kRecursionMarker here,
then accumulate it in a temporary variable and overwrite the recursion marker at
the end.

Think about:

(foo|bar|baz|(\1)|\2)

or maybe don't.  It made my head hurt and didn't bring enlightenment.

[Yang, 2015/12/15 09:52:18]

I think this is fine. We can only have a recursion if both capture and back
references are involved. In that case however we would already catch the
recursion inside the call.

   max_match_ = first_alternative->max_match();
-  for (int i = 1; i < alternatives->length(); i++) {
-    RegExpTree* alternative = alternatives->at(i);
+  for (int i = 1; i < alternatives_->length(); i++) {
+    RegExpTree* alternative = alternatives_->at(i);
     min_match_ = Min(min_match_, alternative->min_match());
     max_match_ = Max(max_match_, alternative->max_match());
   }
 }
 
 
 static int IncreaseBy(int previous, int increase) {
   if (RegExpTree::kInfinity - previous < increase) {
     return RegExpTree::kInfinity;
   } else {
     return previous + increase;
   }
 }
 
-RegExpAlternative::RegExpAlternative(ZoneList<RegExpTree*>* nodes)
-    : nodes_(nodes) {
-  DCHECK(nodes->length() > 1);
+
+void RegExpAlternative::LazilyComputeMatchLengths() {
+  // We cannot compute this in the constructor because at the time of parsing
+  // back referenced captures have not yet been parsed yet.
   min_match_ = 0;
   max_match_ = 0;
-  for (int i = 0; i < nodes->length(); i++) {
-    RegExpTree* node = nodes->at(i);
+  for (int i = 0; i < nodes_->length(); i++) {
+    RegExpTree* node = nodes_->at(i);
     int node_min_match = node->min_match();
     min_match_ = IncreaseBy(min_match_, node_min_match);
     int node_max_match = node->max_match();
     max_match_ = IncreaseBy(max_match_, node_max_match);
   }
 }
 
 
+void RegExpQuantifier::LazilyComputeMatchLengths() {
+  // We cannot compute this in the constructor because at the time of parsing
+  // back referenced captures have not yet been parsed yet.
+  min_match_ = min_ * body_->min_match();
+  if (max_ > 0 && body_->max_match() > kInfinity / max_) {
+    max_match_ = kInfinity;
+  } else {
+    max_match_ = max_ * body_->max_match();
+  }
+}
+
+
 CaseClause::CaseClause(Zone* zone, Expression* label,
                        ZoneList<Statement*>* statements, int pos)
     : Expression(zone, pos),
       label_(label),
       statements_(statements),
       compare_type_(Type::None(zone)) {}
 
 
 uint32_t Literal::Hash() {
   return raw_value()->IsString()
              ? raw_value()->AsString()->hash()
              : ComputeLongHash(double_to_uint64(raw_value()->AsNumber()));
 }
 
 
 // static
 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