[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) {

[Yang, 2016/06/13 10:54:52]

I don't think this check is still necessary. We can just always Advance. If none
of the flags below are set, we can just fall through and fail parsing.

[jgruber, 2016/06/13 13:10:00]

Done.

                 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) {
+            const ZoneVector<uc16>* name = ParseCaptureGroupName(CHECK_FAILED);
+            CreateNamedCaptureAtIndex(name, captures_started_ CHECK_FAILED);

[Yang, 2016/06/13 10:54:52]

Can we simply attach the name to the parser state here and create the capture
group later with the name at the place where we call GetCapture? That way we
don't add another place where we create capture groups.

[jgruber, 2016/06/13 13:10:00]

Done.

+          }
         }
         // 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

[Yang, 2016/06/13 10:54:53]

I don't think we need all caps here :)
Above we have "Fall through." as comment.

[jgruber, 2016/06/13 13:10:00]

Looking at the rest of the file, I think we have every variation of
capitalization and white space possible. There actually is a second instance of
FALLTHROUGH right above this, which is what I tried to stay consistent with
(didn't notice the others).

I can go through in a follow-up commit and make sure we use a single style :)

           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:
+  explicit CaptureNameBuffer(Zone* zone)
+      : backing_store_(nullptr), zone_(zone) {}
+
+  INLINE(void AddChar(uint32_t code_unit)) {
+    if (backing_store_ == nullptr) {
+      backing_store_ =
+          new (zone_->New(sizeof(ZoneVector<uc16>))) ZoneVector<uc16>(zone_);
+    }
+    if (code_unit <= unibrow::Utf16::kMaxNonSurrogateCharCode) {
+      backing_store_->push_back(code_unit);
+    } else {
+      backing_store_->push_back(unibrow::Utf16::LeadSurrogate(code_unit));
+      backing_store_->push_back(unibrow::Utf16::TrailSurrogate(code_unit));
+    }
+  }
+
+  const ZoneVector<uc16>* two_byte_literal() { return backing_store_; }
+
+ private:
+  ZoneVector<uc16>* backing_store_;

[Yang, 2016/06/13 10:54:52]

Let's make this a non-dynamic member, like BytecodeArrayWriter::bytecodes_, and
initialize it eagerly in the constructor's initializer list.

In fact, we probably can avoid this whole class and just inline the surrogate
encoding into ParseCaptureGroupName and define the ZoneVector there.

[jgruber, 2016/06/13 13:10:00]

Done.

+  Zone* zone_;
+
+  DISALLOW_COPY_AND_ASSIGN(CaptureNameBuffer);
+};
+
+const ZoneVector<uc16>* RegExpParser::ParseCaptureGroupName() {
+  DCHECK(FLAG_harmony_regexp_named_captures);
+  DCHECK(unicode());
+
+  CaptureNameBuffer buf(zone());
+  bool at_start = true;
+  while (true) {
+    uc32 c = current();
+    Advance();
+
+    // Convert unicode escapes.
+    if (c == '\\' && current() == 'u') {
+      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"));
+        return nullptr;
+      }
+      buf.AddChar(c);
+      at_start = false;
+    } else {
+      if (c == '>') {
+        break;
+      } else if (IdentifierPart::Is(c)) {
+        buf.AddChar(c);
+      } else {
+        ReportError(CStrVector("Invalid capture group name"));
+        return nullptr;
+      }
+    }
+  }
+
+  return buf.two_byte_literal();
+}
+
+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());

[Yang, 2016/06/13 10:54:52]

Let's make named_captures_ a non-dynamic member of RegExpParser.

[jgruber, 2016/06/13 13:10:00]

Do you have an intuition about how much overhead initialization of
named_captures_ and named_back_references_ adds to the case of regexps without
named captures? 

The captures_ list itself is also dynamic, and I assumed it was due to
performance reasons.

[Yang, 2016/06/13 13:38:00]

Not a lot. List takes 3 pointers, so dynamic allocation would take 1 or 4
depending on whether its initialized. If we don't allocate dynamically, we also
save some code.

I don't have strong opinion on this, and can be convinced either way.

[jgruber, 2016/06/14 07:53:12]

Ok. I'll stick with dynamic lists for now, just to stay consistent to captures_
and to avoid object creation for patterns without named captures.

+  } else {
+    // Check for duplicates and bail if we find any.
+    for (int i = 0; i < named_captures_->length(); i++) {

[Yang, 2016/06/13 10:54:52]

You can use C++11 syntax here.

for (const auto& named_capture : *named_captures_)

[jgruber, 2016/06/13 13:10:00]

Done.

+      if (*named_captures_->at(i)->name() == *name) {
+        ReportError(CStrVector("Duplicate capture group name"));
+        return false;
+      }
+    }
+  }
+
+  RegExpCapture* capture = GetCapture(index);
+  DCHECK(capture->name() == nullptr);
+
+  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();
+  const ZoneVector<uc16>* name = ParseCaptureGroupName();
+  if (name == nullptr) {
+    return false;
+  }
+
+  const int index = LookupCaptureGroupIndex(name);

[Yang, 2016/06/13 10:54:53]

Let's not do this twice, here and in PatchNamedBackReferences. Let's always do
this in the latter.

[jgruber, 2016/06/13 13:10:00]

We needed the index here to determine whether to call AddEmpty() or add a back
reference node. But since we now store the name in state, we can skip this
lookup. 

+  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_ =

[Yang, 2016/06/13 10:54:53]

Same here, let's make named_back_references_ a non-dynamic member.

[jgruber, 2016/06/13 13:10:00]

See above.

This change is trivial, just want to make sure it's the right way to go :)

+          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(const ZoneVector<uc16>* name) {

[Yang, 2016/06/13 10:54:52]

This can be inlined into PatchNamedBackReferences if this is only called from
there.

[jgruber, 2016/06/13 13:10:00]

Done.

+  DCHECK(FLAG_harmony_regexp_named_captures);
+  DCHECK(unicode());
+  DCHECK_NOT_NULL(name);
+
+  // 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);
+    Vector<const uc16> vector(&(*capture->name())[0],

[Yang, 2016/06/13 10:54:53]

Could we use a ZoneList for capture->name() instead of ZoneVector? They
essentially do the same anyways. With ZoneList, you can simply use
ToConstVector.

[jgruber, 2016/06/13 13:10:00]

I used ZoneVector because of mstarzinger's comment '[...] once we got rid of our
own home-grown ZoneList [...]' in zone-containers.

I'm fine with either container type, but is there a real benefit to switching to
ZoneVector? What about adding ToConstVector to ZoneVector? 

[Yang, 2016/06/13 13:38:00]

I guess adding ToConstVector to ZoneVector also works.

[jgruber, 2016/06/14 07:53:12]

Done.

+                              static_cast<int>(capture->name()->size()));
+    MaybeHandle<String> name =
+        isolate()->factory()->NewStringFromTwoByte(vector);
+    array->set(i * 2, *name.ToHandleChecked());
+    array->set(i * 2 + 1, Smi::FromInt(capture->index()));
+  }
+
+  return array;
+}
+
+void RegExpParser::FreeCaptureStrings() {

[Yang, 2016/06/13 10:54:52]

Do we still need this and capture_strings_?

[jgruber, 2016/06/13 13:10:00]

No. Thanks, good catch.

+  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 424 matching lines @@
       default:
         first = ParseClassCharacterEscape(CHECK_FAILED);
     }
   } else {
     Advance();
   }
 
   return CharacterRange::Singleton(first);
 }
 
-
 static const uc16 kNoCharClass = 0;
 
 // Adds range or pre-defined character class to character ranges.
 // If char_class is not kInvalidClass, it's interpreted as a class
 // escape (i.e., 's' means whitespace, from '\s').
 static inline void AddRangeOrEscape(ZoneList<CharacterRange>* ranges,
                                     uc16 char_class, CharacterRange range,
                                     Zone* zone) {
   if (char_class != kNoCharClass) {
     CharacterRange::AddClassEscape(char_class, ranges, zone);
@@ skipping 112 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