[regexp] Allow named captures and back-references in non-unicode patterns

src/regexp/regexp-parser.cc

 // Copyright 2016 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/regexp/regexp-parser.h"
 
 #include "src/char-predicates-inl.h"
 #include "src/factory.h"
 #include "src/isolate.h"
 #include "src/objects-inl.h"
@@ skipping 22 matching lines @@
       ignore_case_(flags & JSRegExp::kIgnoreCase),
       multiline_(flags & JSRegExp::kMultiline),
       unicode_(flags & JSRegExp::kUnicode),
       next_pos_(0),
       captures_started_(0),
       capture_count_(0),
       has_more_(true),
       simple_(false),
       contains_anchor_(false),
       is_scanned_for_captures_(false),
+      has_named_captures_(false),
       failed_(false) {
   DCHECK_IMPLIES(dotall(), FLAG_harmony_regexp_dotall);
   Advance();
 }
 
 template <bool update_position>
 inline uc32 RegExpParser::ReadNext() {
   int position = next_pos_;
   uc32 c0 = in()->Get(position);
   position++;
@@ skipping 265 matching lines @@
                   lookaround_type = RegExpLookaround::LOOKBEHIND;
                   Advance(2);
                   break;
                 } else if (Next() == '!') {
                   subexpr_type = NEGATIVE_LOOKAROUND;
                   lookaround_type = RegExpLookaround::LOOKBEHIND;
                   Advance(2);
                   break;
                 }
               }
-              if (FLAG_harmony_regexp_named_captures && unicode()) {
+              if (FLAG_harmony_regexp_named_captures) {
+                has_named_captures_ = true;
                 is_named_capture = true;
                 Advance();
                 break;
               }
             // Fall through.
             default:
               return ReportError(CStrVector("Invalid group"));
           }
         }
 
@@ skipping 195 matching lines @@
               builder->AddEscapedUnicodeCharacter(value);
             } else if (!unicode()) {
               builder->AddCharacter('u');
             } else {
               // With /u, invalid escapes are not treated as identity escapes.
               return ReportError(CStrVector("Invalid unicode escape"));
             }
             break;
           }
           case 'k':
-            if (FLAG_harmony_regexp_named_captures && unicode()) {
+            // Either an identity escape or a named back-reference.  The two
+            // interpretations are mutually exclusive: '\k' is interpreted as
+            // an identity escape for non-unicode patterns without named
+            // capture groups, and as the beginning of a named back-reference
+            // in all other cases.
+            if (FLAG_harmony_regexp_named_captures &&
+                (unicode() || HasNamedCaptures())) {
               Advance(2);
               ParseNamedBackReference(builder, state CHECK_FAILED);
               break;
             }
           // Fall through.
           default:
             Advance();
             // With /u, no identity escapes except for syntax characters
             // are allowed. Otherwise, all identity escapes are allowed.
             if (!unicode() || IsSyntaxCharacterOrSlash(current())) {
@@ skipping 95 matching lines @@
 #endif
 
 
 // In order to know whether an escape is a backreference or not we have to scan
 // the entire regexp and find the number of capturing parentheses.  However we
 // don't want to scan the regexp twice unless it is necessary.  This mini-parser
 // is called when needed.  It can see the difference between capturing and
 // noncapturing parentheses and can skip character classes and backslash-escaped
 // characters.
 void RegExpParser::ScanForCaptures() {
+  DCHECK(!is_scanned_for_captures_);
+  const int saved_position = position();
   // Start with captures started previous to current position
   int capture_count = captures_started();
   // Add count of captures after this position.
   int n;
   while ((n = current()) != kEndMarker) {
     Advance();
     switch (n) {
       case '\\':
         Advance();
         break;
@@ skipping 15 matching lines @@
           // * a non-capturing group '(:',
           // * a lookbehind assertion '(?<=' '(?<!'
           // * or a named capture '(?<'.
           //
           // Of these, only named captures are capturing groups.
           if (!FLAG_harmony_regexp_named_captures) break;
 
           Advance();
           if (current() != '<') break;
 
-          // TODO(jgruber): To be more future-proof we could test for
-          // IdentifierStart here once it becomes clear whether group names
-          // allow unicode escapes.
-          Advance();
-          if (current() == '=' || current() == '!') break;
+          if (FLAG_harmony_regexp_lookbehind) {
+            // TODO(jgruber): To be more future-proof we could test for
+            // IdentifierStart here once it becomes clear whether group names
+            // allow unicode escapes.
+            // https://github.com/tc39/proposal-regexp-named-groups/issues/23
+            Advance();
+            if (current() == '=' || current() == '!') break;
+          }
+
+          // Found a possible named capture. It could turn out to be a syntax
+          // error (e.g. an unterminated or invalid name), but that distinction
+          // does not matter for our purposes.
+          has_named_captures_ = true;
         }
         capture_count++;
         break;
     }
   }
   capture_count_ = capture_count;
   is_scanned_for_captures_ = true;
+  Reset(saved_position);
 }
 
 
 bool RegExpParser::ParseBackReferenceIndex(int* index_out) {
   DCHECK_EQ('\\', current());
   DCHECK('1' <= Next() && Next() <= '9');
   // Try to parse a decimal literal that is no greater than the total number
   // of left capturing parentheses in the input.
   int start = position();
   int value = Next() - '0';
   Advance(2);
   while (true) {
     uc32 c = current();
     if (IsDecimalDigit(c)) {
       value = 10 * value + (c - '0');
       if (value > kMaxCaptures) {
         Reset(start);
         return false;
       }
       Advance();
     } else {
       break;
     }
   }
   if (value > captures_started()) {
-    if (!is_scanned_for_captures_) {
-      int saved_position = position();
-      ScanForCaptures();
-      Reset(saved_position);
-    }
+    if (!is_scanned_for_captures_) ScanForCaptures();
     if (value > capture_count_) {
       Reset(start);
       return false;
     }
   }
   *index_out = value;
   return true;
 }
 
 static void push_code_unit(ZoneVector<uc16>* v, uint32_t code_unit) {
   if (code_unit <= unibrow::Utf16::kMaxNonSurrogateCharCode) {
     v->push_back(code_unit);
   } else {
     v->push_back(unibrow::Utf16::LeadSurrogate(code_unit));
     v->push_back(unibrow::Utf16::TrailSurrogate(code_unit));
   }
 }
 
 const ZoneVector<uc16>* RegExpParser::ParseCaptureGroupName() {
   DCHECK(FLAG_harmony_regexp_named_captures);
-  DCHECK(unicode());
 
   ZoneVector<uc16>* name =
       new (zone()->New(sizeof(ZoneVector<uc16>))) ZoneVector<uc16>(zone());
 
   bool at_start = true;
   while (true) {
     uc32 c = current();
     Advance();
 
     // Convert unicode escapes.
     if (c == '\\' && current() == 'u') {
+      // TODO(jgruber): Reconsider this once the spec has settled.
+      // https://github.com/tc39/proposal-regexp-named-groups/issues/23
       Advance();
       if (!ParseUnicodeEscape(&c)) {
         ReportError(CStrVector("Invalid Unicode escape sequence"));
         return nullptr;
       }
     }
 
     if (at_start) {
       if (!IdentifierStart::Is(c)) {
         ReportError(CStrVector("Invalid capture group name"));
@@ skipping 12 matching lines @@
       }
     }
   }
 
   return name;
 }
 
 bool RegExpParser::CreateNamedCaptureAtIndex(const ZoneVector<uc16>* name,
                                              int index) {
   DCHECK(FLAG_harmony_regexp_named_captures);
-  DCHECK(unicode());
   DCHECK(0 < index && index <= captures_started_);
   DCHECK_NOT_NULL(name);
 
   if (named_captures_ == nullptr) {
     named_captures_ = new (zone()) ZoneList<RegExpCapture*>(1, zone());
   } else {
     // Check for duplicates and bail if we find any.
+    // TODO(jgruber): O(n^2).
     for (const auto& named_capture : *named_captures_) {
       if (*named_capture->name() == *name) {
         ReportError(CStrVector("Duplicate capture group name"));
         return false;
       }
     }
   }
 
   RegExpCapture* capture = GetCapture(index);
   DCHECK(capture->name() == nullptr);
@@ skipping 94 matching lines @@
   for (int i = 0; i < named_captures_->length(); i++) {
     RegExpCapture* capture = named_captures_->at(i);
     MaybeHandle<String> name = factory->NewStringFromTwoByte(capture->name());
     array->set(i * 2, *name.ToHandleChecked());
     array->set(i * 2 + 1, Smi::FromInt(capture->index()));
   }
 
   return array;
 }
 
+bool RegExpParser::HasNamedCaptures() {
+  if (has_named_captures_ || is_scanned_for_captures_) {
+    return has_named_captures_;
+  }
+
+  ScanForCaptures();
+  DCHECK(is_scanned_for_captures_);
+  return has_named_captures_;
+}
+
 bool RegExpParser::RegExpParserState::IsInsideCaptureGroup(int index) {
   for (RegExpParserState* s = this; s != NULL; s = s->previous_state()) {
     if (s->group_type() != CAPTURE) continue;
     // Return true if we found the matching capture index.
     if (index == s->capture_index()) return true;
     // Abort if index is larger than what has been parsed up till this state.
     if (index > s->capture_index()) return false;
   }
   return false;
 }
@@ skipping 905 matching lines @@
     return false;
   }
   terms_.Add(new (zone()) RegExpQuantifier(min, max, quantifier_type, atom),
              zone());
   LAST(ADD_TERM);
   return true;
 }
 
 }  // namespace internal
 }  // namespace v8