[regexp] Experimental support for regexp named captures

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"
 #include "src/ostreams.h"
 #include "src/regexp/jsregexp.h"
 #include "src/utils.h"
 
 #ifdef V8_I18N_SUPPORT
 #include "unicode/uset.h"
 #endif  // V8_I18N_SUPPORT
 
 namespace v8 {
 namespace internal {
 
 RegExpParser::RegExpParser(FlatStringReader* in, Handle<String>* error,
                            JSRegExp::Flags flags, Isolate* isolate, Zone* zone)
     : isolate_(isolate),
       zone_(zone),
       error_(error),
       captures_(NULL),
+      named_captures_(NULL),
+      named_back_references_(NULL),
+      capture_strings_(0, zone),
       in_(in),
       current_(kEndMarker),
       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),
@@ skipping 104 matching lines @@
 
 #define CHECK_FAILED /**/); \
   if (failed_) return NULL; \
   ((void)0
 
 
 // Pattern ::
 //   Disjunction
 RegExpTree* RegExpParser::ParsePattern() {
   RegExpTree* result = ParseDisjunction(CHECK_FAILED);
+  PatchNamedBackReferences(CHECK_FAILED);
   DCHECK(!has_more());
   // If the result of parsing is a literal string atom, and it has the
   // same length as the input, then the atom is identical to the input.
   if (result->IsAtom() && result->AsAtom()->length() == in()->length()) {
     simple_ = true;
   }
   return result;
 }
 
 
@@ skipping 99 matching lines @@
             new (zone()) ZoneList<CharacterRange>(2, zone());
         CharacterRange::AddClassEscape('.', ranges, zone());
         RegExpCharacterClass* cc =
             new (zone()) RegExpCharacterClass(ranges, false);
         builder->AddCharacterClass(cc);
         break;
       }
       case '(': {
         SubexpressionType subexpr_type = CAPTURE;
         RegExpLookaround::Type lookaround_type = state->lookaround_type();
+        bool is_named_capture = false;
         Advance();
         if (current() == '?') {
           switch (Next()) {
             case ':':
               subexpr_type = GROUPING;
+              Advance(2);
               break;
             case '=':
               lookaround_type = RegExpLookaround::LOOKAHEAD;
               subexpr_type = POSITIVE_LOOKAROUND;
+              Advance(2);
               break;
             case '!':
               lookaround_type = RegExpLookaround::LOOKAHEAD;
               subexpr_type = NEGATIVE_LOOKAROUND;
+              Advance(2);
               break;
             case '<':
-              if (FLAG_harmony_regexp_lookbehind) {
+              if (FLAG_harmony_regexp_lookbehind ||
+                  FLAG_harmony_regexp_named_captures) {
                 Advance();
-                lookaround_type = RegExpLookaround::LOOKBEHIND;
-                if (Next() == '=') {
-                  subexpr_type = POSITIVE_LOOKAROUND;
-                  break;
-                } else if (Next() == '!') {
-                  subexpr_type = NEGATIVE_LOOKAROUND;
+                if (FLAG_harmony_regexp_lookbehind) {
+                  if (Next() == '=') {
+                    subexpr_type = POSITIVE_LOOKAROUND;
+                    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()) {
+                  is_named_capture = true;
+                  Advance();
                   break;
                 }
               }
             // Fall through.
             default:
               return ReportError(CStrVector("Invalid group"));
           }
-          Advance(2);
-        } else {
+        }
+
+        if (subexpr_type == CAPTURE) {
           if (captures_started_ >= kMaxCaptures) {
             return ReportError(CStrVector("Too many captures"));
           }
           captures_started_++;
+
+          if (is_named_capture) {
+            Vector<const uc16> name = ParseCaptureGroupName(CHECK_FAILED);
+            CreateNamedCaptureAtIndex(name, captures_started_ CHECK_FAILED);
+          }
         }
         // Store current state and begin new disjunction parsing.
         state = new (zone()) RegExpParserState(
             state, subexpr_type, lookaround_type, captures_started_,
             ignore_case(), unicode(), zone());
         builder = state->builder();
         continue;
       }
       case '[': {
         RegExpTree* cc = ParseCharacterClass(CHECK_FAILED);
@@ skipping 173 matching lines @@
             if (ParseUnicodeEscape(&value)) {
               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()) {
+              Advance(2);
+              ParseNamedBackReference(builder, state CHECK_FAILED);
+              break;
+            }
+          // FALLTHROUGH
           default:
             Advance();
             // With /u, no identity escapes except for syntax characters
             // are allowed. Otherwise, all identity escapes are allowed.
             if (!unicode() || IsSyntaxCharacterOrSlash(current())) {
               builder->AddCharacter(current());
               Advance();
             } else {
               return ReportError(CStrVector("Invalid escape"));
             }
@@ skipping 158 matching lines @@
     }
     if (value > capture_count_) {
       Reset(start);
       return false;
     }
   }
   *index_out = value;
   return true;
 }
 
+class CaptureNameBuffer {
+ public:
+  CaptureNameBuffer() : position_(0), backing_store_() {}
+
+  INLINE(void AddChar(uint32_t code_unit)) {
+    if (position_ >= backing_store_.length()) ExpandBuffer();
+    if (code_unit <= unibrow::Utf16::kMaxNonSurrogateCharCode) {
+      *reinterpret_cast<uint16_t*>(&backing_store_[position_]) = code_unit;
+      position_ += kUC16Size;
+    } else {
+      *reinterpret_cast<uint16_t*>(&backing_store_[position_]) =
+          unibrow::Utf16::LeadSurrogate(code_unit);
+      position_ += kUC16Size;
+      if (position_ >= backing_store_.length()) ExpandBuffer();
+      *reinterpret_cast<uint16_t*>(&backing_store_[position_]) =
+          unibrow::Utf16::TrailSurrogate(code_unit);
+      position_ += kUC16Size;
+    }
+  }
+
+  Vector<const uc16> two_byte_literal() const {
+    DCHECK((position_ & 0x1) == 0);
+    return Vector<const uc16>(reinterpret_cast<uc16*>(backing_store_.start()),
+                              position_ >> 1);
+  }
+
+  void Dispose() { backing_store_.Dispose(); }
+
+ private:
+  static const int kInitialCapacity = 16;
+  static const int kGrowthFactor = 4;
+  static const int kMaxGrowth = 1 * MB;
+
+  inline int NewCapacity(int min_capacity) {
+    int capacity = Max(min_capacity, backing_store_.length());
+    int new_capacity = Min(capacity * kGrowthFactor, capacity + kMaxGrowth);
+    return new_capacity;
+  }
+
+  void ExpandBuffer() {
+    Vector<byte> new_store = Vector<byte>::New(NewCapacity(kInitialCapacity));
+    MemCopy(new_store.start(), backing_store_.start(), position_);
+    backing_store_.Dispose();
+    backing_store_ = new_store;
+  }
+
+  int position_;
+  Vector<byte> backing_store_;

[Yang, 2016/06/10 15:43:27]

Can't we simply use a ZoneList here? It already has all the on-demand expanding,
and you can call ToConstVector to get a vector. It's zone-allocated so you won't
need to dispose it later.

[jgruber, 2016/06/13 08:26:00]

Right. I switched the CL to my ZoneVector version.

+
+  DISALLOW_COPY_AND_ASSIGN(CaptureNameBuffer);
+};
+
+Vector<const uc16> RegExpParser::ParseCaptureGroupName() {
+  DCHECK(FLAG_harmony_regexp_named_captures);
+  DCHECK(unicode());
+
+  CaptureNameBuffer buf;
+  bool at_start = true;
+  while (true) {
+    uc32 c = current();
+    Advance();
+
+    // Convert unicode escapes.
+    if (c == '\\' && current() == 'u') {
+      Advance();
+      if (!ParseUnicodeEscape(&c)) {
+        buf.Dispose();
+        ReportError(CStrVector("Invalid Unicode escape sequence"));
+        return Vector<const uc16>::empty();
+      }
+    }
+
+    if (at_start) {
+      if (!IdentifierStart::Is(c)) {
+        buf.Dispose();
+        ReportError(CStrVector("Invalid capture group name"));
+        return Vector<const uc16>::empty();
+      }
+      buf.AddChar(c);
+      at_start = false;
+    } else {
+      if (c == '>') {
+        break;
+      } else if (IdentifierPart::Is(c)) {
+        buf.AddChar(c);
+      } else {
+        buf.Dispose();
+        ReportError(CStrVector("Invalid capture group name"));
+        return Vector<const uc16>::empty();
+      }
+    }
+  }
+
+  Vector<const uc16> name = buf.two_byte_literal();
+  capture_strings_.Add(name, zone());
+  return name;
+}
+
+bool RegExpParser::CreateNamedCaptureAtIndex(Vector<const uc16> name,
+                                             int index) {
+  DCHECK(FLAG_harmony_regexp_named_captures);
+  DCHECK(unicode());
+  DCHECK(!name.is_empty());
+  DCHECK(0 < index && index <= captures_started_);
+
+  if (named_captures_ == nullptr) {
+    named_captures_ = new (zone()) ZoneList<RegExpCapture*>(1, zone());
+  } else {
+    // Check for duplicates and bail if we find any.
+    for (int i = 0; i < named_captures_->length(); i++) {
+      if (named_captures_->at(i)->name() == name) {
+        ReportError(CStrVector("Duplicate capture group name"));
+        return false;
+      }
+    }
+  }
+
+  RegExpCapture* capture = GetCapture(index);
+  DCHECK(capture->name().is_empty());
+
+  capture->set_name(name);
+  named_captures_->Add(capture, zone());
+
+  return true;
+}
+
+bool RegExpParser::ParseNamedBackReference(RegExpBuilder* builder,
+                                           RegExpParserState* state) {
+  // The parser is assumed to be on the '<' in \k<name>.
+  if (current() != '<') {
+    ReportError(CStrVector("Invalid named reference"));
+    return false;
+  }
+
+  Advance();
+  Vector<const uc16> name = ParseCaptureGroupName();
+  if (name.is_empty()) {
+    return false;
+  }
+
+  const int index = LookupCaptureGroupIndex(name);
+  if (index != -1 && state->IsInsideCaptureGroup(index)) {
+    builder->AddEmpty();
+  } else {
+    RegExpBackReference* atom = new (zone()) RegExpBackReference();
+    atom->set_name(name);
+
+    builder->AddAtom(atom);
+
+    if (named_back_references_ == nullptr) {
+      named_back_references_ =
+          new (zone()) ZoneList<RegExpBackReference*>(1, zone());
+    }
+    named_back_references_->Add(atom, zone());
+  }
+
+  return true;
+}
+
+void RegExpParser::PatchNamedBackReferences() {
+  if (named_back_references_ == nullptr) return;
+
+  if (named_captures_ == nullptr) {
+    ReportError(CStrVector("Invalid named capture referenced"));
+    return;
+  }
+
+  // Look up and patch the actual capture for each named back reference.
+  // TODO(jgruber): O(n^2), optimize if necessary.
+
+  for (int i = 0; i < named_back_references_->length(); i++) {
+    RegExpBackReference* ref = named_back_references_->at(i);
+    int index = LookupCaptureGroupIndex(ref->name());
+    if (index == -1) {
+      ReportError(CStrVector("Invalid named capture referenced"));
+      return;
+    }
+    ref->set_capture(GetCapture(index));
+  }
+}
+
+int RegExpParser::LookupCaptureGroupIndex(Vector<const uc16> name) {
+  DCHECK(FLAG_harmony_regexp_named_captures);
+  DCHECK(unicode());
+  DCHECK(!name.is_empty());
+
+  // Attempt an initial lookup.
+  if (named_captures_ == nullptr) {
+    return -1;
+  }
+
+  for (int i = 0; i < named_captures_->length(); i++) {
+    RegExpCapture* capture = named_captures_->at(i);
+    if (capture->name() == name) {
+      return capture->index();
+    }
+  }
+
+  return -1;
+}
 
 RegExpCapture* RegExpParser::GetCapture(int index) {
   // The index for the capture groups are one-based. Its index in the list is
   // zero-based.
   int know_captures =
       is_scanned_for_captures_ ? capture_count_ : captures_started_;
   DCHECK(index <= know_captures);
   if (captures_ == NULL) {
     captures_ = new (zone()) ZoneList<RegExpCapture*>(know_captures, zone());
   }
   while (captures_->length() < know_captures) {
     captures_->Add(new (zone()) RegExpCapture(captures_->length() + 1), zone());
   }
   return captures_->at(index - 1);
 }
 
+Handle<FixedArray> RegExpParser::CreateCaptureNameMap() {
+  if (named_captures_ == nullptr || named_captures_->is_empty())
+    return Handle<FixedArray>();
+
+  int len = named_captures_->length() * 2;
+  Handle<FixedArray> array = isolate()->factory()->NewFixedArray(len);
+
+  for (int i = 0; i < named_captures_->length(); i++) {
+    RegExpCapture* capture = named_captures_->at(i);
+    MaybeHandle<String> name =
+        isolate()->factory()->NewStringFromTwoByte(capture->name());
+    array->set(i * 2, *name.ToHandleChecked());
+    array->set(i * 2 + 1, Smi::FromInt(capture->index()));
+  }
+
+  return array;
+}
+
+void RegExpParser::FreeCaptureStrings() {
+  for (int i = 0; i < capture_strings_.length(); i++) {
+    capture_strings_[i].Dispose();
+  }
+  capture_strings_.Clear();
+}
 
 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 557 matching lines @@
     DCHECK(result->error.is_null());
     if (FLAG_trace_regexp_parser) {
       OFStream os(stdout);
       tree->Print(os, zone);
       os << "\n";
     }
     result->tree = tree;
     int capture_count = parser.captures_started();
     result->simple = tree->IsAtom() && parser.simple() && capture_count == 0;
     result->contains_anchor = parser.contains_anchor();
+    result->capture_name_map = parser.CreateCaptureNameMap();
     result->capture_count = capture_count;
   }
+  parser.FreeCaptureStrings();
   return !parser.failed();
 }
 
 RegExpBuilder::RegExpBuilder(Zone* zone, bool ignore_case, bool unicode)
     : zone_(zone),
       pending_empty_(false),
       ignore_case_(ignore_case),
       unicode_(unicode),
       characters_(NULL),
       pending_surrogate_(kNoPendingSurrogate),
@@ skipping 274 matching lines @@
     return false;
   }
   terms_.Add(new (zone()) RegExpQuantifier(min, max, quantifier_type, atom),
              zone());
   LAST(ADD_TERM);
   return true;
 }
 
 }  // namespace internal
 }  // namespace v8