[regexp] implement character classes for unicode regexps.

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/regexp/jsregexp.h"
 #include "src/utils.h"
 
 namespace v8 {
 namespace internal {
 
 RegExpParser::RegExpParser(FlatStringReader* in, Handle<String>* error,
-                           bool multiline, bool unicode, Isolate* isolate,
-                           Zone* zone)
+                           JSRegExp::Flags flags, Isolate* isolate, Zone* zone)
     : isolate_(isolate),
       zone_(zone),
       error_(error),
       captures_(NULL),
       in_(in),
       current_(kEndMarker),
+      flags_(flags),
       next_pos_(0),
       captures_started_(0),
       capture_count_(0),
       has_more_(true),
-      multiline_(multiline),
-      unicode_(unicode),
       simple_(false),
       contains_anchor_(false),
       is_scanned_for_captures_(false),
       failed_(false) {
   Advance();
 }
 
 
+template <bool update_position>
+uc32 RegExpParser::ReadNext() {
+  int position = next_pos_;
+  uc32 c0 = in()->Get(position);
+  position++;
+  // Read the whole surrogate pair in case of unicode flag, if possible.
+  if (unicode() && position < in()->length() &&
+      unibrow::Utf16::IsLeadSurrogate(static_cast<uc16>(c0))) {
+    uc16 c1 = in()->Get(position);
+    if (unibrow::Utf16::IsTrailSurrogate(c1)) {
+      c0 = unibrow::Utf16::CombineSurrogatePair(static_cast<uc16>(c0), c1);
+      position++;
+    }
+  }
+  if (update_position) next_pos_ = position;
+  return c0;
+}
+
+
 uc32 RegExpParser::Next() {
   if (has_next()) {
-    return in()->Get(next_pos_);
+    return ReadNext<false>();
   } else {
     return kEndMarker;
   }
 }
 
 
 void RegExpParser::Advance() {
-  if (next_pos_ < in()->length()) {
+  if (has_next()) {
     StackLimitCheck check(isolate());
     if (check.HasOverflowed()) {
       ReportError(CStrVector(Isolate::kStackOverflowMessage));
     } else if (zone()->excess_allocation()) {
       ReportError(CStrVector("Regular expression too large"));
     } else {
-      current_ = in()->Get(next_pos_);
-      next_pos_++;
-      // Read the whole surrogate pair in case of unicode flag, if possible.
-      if (unicode_ && next_pos_ < in()->length() &&
-          unibrow::Utf16::IsLeadSurrogate(static_cast<uc16>(current_))) {
-        uc16 trail = in()->Get(next_pos_);
-        if (unibrow::Utf16::IsTrailSurrogate(trail)) {
-          current_ = unibrow::Utf16::CombineSurrogatePair(
-              static_cast<uc16>(current_), trail);
-          next_pos_++;
-        }
-      }
+      current_ = ReadNext<true>();
     }
   } else {
     current_ = kEndMarker;
     // Advance so that position() points to 1-after-the-last-character. This is
     // important so that Reset() to this position works correctly.
     next_pos_ = in()->length() + 1;
     has_more_ = false;
   }
 }
 
@@ skipping 56 matching lines @@
 // Alternative ::
 //   [empty]
 //   Term Alternative
 // Term ::
 //   Assertion
 //   Atom
 //   Atom Quantifier
 RegExpTree* RegExpParser::ParseDisjunction() {
   // Used to store current state while parsing subexpressions.
   RegExpParserState initial_state(NULL, INITIAL, RegExpLookaround::LOOKAHEAD, 0,
-                                  zone());
+                                  flags_, zone());
   RegExpParserState* state = &initial_state;
   // Cache the builder in a local variable for quick access.
   RegExpBuilder* builder = initial_state.builder();
   while (true) {
     switch (current()) {
       case kEndMarker:
         if (state->IsSubexpression()) {
           // Inside a parenthesized group when hitting end of input.
           ReportError(CStrVector("Unterminated group") CHECK_FAILED);
         }
@@ skipping 43 matching lines @@
         Advance();
         builder->NewAlternative();
         continue;
       }
       case '*':
       case '+':
       case '?':
         return ReportError(CStrVector("Nothing to repeat"));
       case '^': {
         Advance();
-        if (multiline_) {
+        if (multiline()) {
           builder->AddAssertion(
               new (zone()) RegExpAssertion(RegExpAssertion::START_OF_LINE));
         } else {
           builder->AddAssertion(
               new (zone()) RegExpAssertion(RegExpAssertion::START_OF_INPUT));
           set_contains_anchor();
         }
         continue;
       }
       case '$': {
         Advance();
         RegExpAssertion::AssertionType assertion_type =
-            multiline_ ? RegExpAssertion::END_OF_LINE
-                       : RegExpAssertion::END_OF_INPUT;
+            multiline() ? RegExpAssertion::END_OF_LINE
+                        : RegExpAssertion::END_OF_INPUT;
         builder->AddAssertion(new (zone()) RegExpAssertion(assertion_type));
         continue;
       }
       case '.': {
         Advance();
         // everything except \x0a, \x0d, \u2028 and \u2029
         ZoneList<CharacterRange>* ranges =
             new (zone()) ZoneList<CharacterRange>(2, zone());
         CharacterRange::AddClassEscape('.', ranges, zone());
-        RegExpTree* atom = new (zone()) RegExpCharacterClass(ranges, false);
-        builder->AddAtom(atom);
+        RegExpCharacterClass* cc =
+            new (zone()) RegExpCharacterClass(ranges, false);
+        builder->AddCharacterClass(cc);
         break;
       }
       case '(': {
         SubexpressionType subexpr_type = CAPTURE;
         RegExpLookaround::Type lookaround_type = state->lookaround_type();
         Advance();
         if (current() == '?') {
           switch (Next()) {
             case ':':
               subexpr_type = GROUPING;
@@ skipping 24 matching lines @@
               break;
           }
           Advance(2);
         } else {
           if (captures_started_ >= kMaxCaptures) {
             ReportError(CStrVector("Too many captures") CHECK_FAILED);
           }
           captures_started_++;
         }
         // Store current state and begin new disjunction parsing.
-        state = new (zone()) RegExpParserState(
-            state, subexpr_type, lookaround_type, captures_started_, zone());
+        state =
+            new (zone()) RegExpParserState(state, subexpr_type, lookaround_type,
+                                           captures_started_, flags_, zone());
         builder = state->builder();
         continue;
       }
       case '[': {
-        RegExpTree* atom = ParseCharacterClass(CHECK_FAILED);
-        builder->AddAtom(atom);
+        RegExpTree* cc = ParseCharacterClass(CHECK_FAILED);
+        builder->AddCharacterClass(cc->AsCharacterClass());
         break;
       }
       // Atom ::
       //   \ AtomEscape
       case '\\':
         switch (Next()) {
           case kEndMarker:
             return ReportError(CStrVector("\\ at end of pattern"));
           case 'b':
             Advance(2);
@@ skipping 14 matching lines @@
           case 'D':
           case 's':
           case 'S':
           case 'w':
           case 'W': {
             uc32 c = Next();
             Advance(2);
             ZoneList<CharacterRange>* ranges =
                 new (zone()) ZoneList<CharacterRange>(2, zone());
             CharacterRange::AddClassEscape(c, ranges, zone());
-            RegExpTree* atom = new (zone()) RegExpCharacterClass(ranges, false);
-            builder->AddAtom(atom);
+            RegExpCharacterClass* cc =
+                new (zone()) RegExpCharacterClass(ranges, false);
+            builder->AddCharacterClass(cc);
             break;
           }
           case '1':
           case '2':
           case '3':
           case '4':
           case '5':
           case '6':
           case '7':
           case '8':
@@ skipping 13 matching lines @@
                 builder->AddAtom(atom);
               }
               break;
             }
             uc32 first_digit = Next();
             if (first_digit == '8' || first_digit == '9') {
               // If the 'u' flag is present, only syntax characters can be
               // escaped,
               // no other identity escapes are allowed. If the 'u' flag is not
               // present, all identity escapes are allowed.
-              if (!unicode_) {
+              if (!unicode()) {
                 builder->AddCharacter(first_digit);
                 Advance(2);
               } else {
                 return ReportError(CStrVector("Invalid escape"));
               }
               break;
             }
           }
           // FALLTHROUGH
           case '0': {
@@ skipping 40 matching lines @@
               Advance(2);
               builder->AddCharacter(controlLetter & 0x1f);
             }
             break;
           }
           case 'x': {
             Advance(2);
             uc32 value;
             if (ParseHexEscape(2, &value)) {
               builder->AddCharacter(value);
-            } else if (!unicode_) {
+            } else if (!unicode()) {
               builder->AddCharacter('x');
             } else {
               // If the 'u' flag is present, invalid escapes are not treated as
               // identity escapes.
               return ReportError(CStrVector("Invalid escape"));
             }
             break;
           }
           case 'u': {
             Advance(2);
             uc32 value;
             if (ParseUnicodeEscape(&value)) {
               builder->AddUnicodeCharacter(value);
-            } else if (!unicode_) {
+            } else if (!unicode()) {
               builder->AddCharacter('u');
             } else {
               // If the 'u' flag is present, invalid escapes are not treated as
               // identity escapes.
               return ReportError(CStrVector("Invalid unicode escape"));
             }
             break;
           }
           default:
             Advance();
             // If the 'u' flag is present, only syntax characters can be
             // escaped, no
             // other identity escapes are allowed. If the 'u' flag is not
             // present,
             // all identity escapes are allowed.
-            if (!unicode_ || IsSyntaxCharacter(current())) {
+            if (!unicode() || IsSyntaxCharacter(current())) {
               builder->AddCharacter(current());
               Advance();
             } else {
               return ReportError(CStrVector("Invalid escape"));
             }
             break;
         }
         break;
       case '{': {
         int dummy;
@@ skipping 280 matching lines @@
   }
   *value = val;
   return true;
 }
 
 
 bool RegExpParser::ParseUnicodeEscape(uc32* value) {
   // Accept both \uxxxx and \u{xxxxxx} (if harmony unicode escapes are
   // allowed). In the latter case, the number of hex digits between { } is
   // arbitrary. \ and u have already been read.
-  if (current() == '{' && unicode_) {
+  if (current() == '{' && unicode()) {
     int start = position();
     Advance();
     if (ParseUnlimitedLengthHexNumber(0x10ffff, value)) {
       if (current() == '}') {
         Advance();
         return true;
       }
     }
     Reset(start);
     return false;
@@ skipping 74 matching lines @@
       // For compatibility, we interpret a decimal escape that isn't
       // a back reference (and therefore either \0 or not valid according
       // to the specification) as a 1..3 digit octal character code.
       return ParseOctalLiteral();
     case 'x': {
       Advance();
       uc32 value;
       if (ParseHexEscape(2, &value)) {
         return value;
       }
-      if (!unicode_) {
+      if (!unicode()) {
         // If \x is not followed by a two-digit hexadecimal, treat it
         // as an identity escape.
         return 'x';
       }
       // If the 'u' flag is present, invalid escapes are not treated as
       // identity escapes.
       ReportError(CStrVector("Invalid escape"));
       return 0;
     }
     case 'u': {
       Advance();
       uc32 value;
       if (ParseUnicodeEscape(&value)) {
         return value;
       }
-      if (!unicode_) {
+      if (!unicode()) {
         return 'u';
       }
       // If the 'u' flag is present, invalid escapes are not treated as
       // identity escapes.
       ReportError(CStrVector("Invalid unicode escape"));
       return 0;
     }
     default: {
       uc32 result = current();
       // If the 'u' flag is present, only syntax characters can be escaped, no
       // other identity escapes are allowed. If the 'u' flag is not present, all
       // identity escapes are allowed.
-      if (!unicode_ || IsSyntaxCharacter(result)) {
+      if (!unicode() || IsSyntaxCharacter(result)) {
         Advance();
         return result;
       }
       ReportError(CStrVector("Invalid escape"));
       return 0;
     }
   }
   return 0;
 }
 
 
 CharacterRange RegExpParser::ParseClassAtom(uc16* char_class) {
   DCHECK_EQ(0, *char_class);
   uc32 first = current();
   if (first == '\\') {
     switch (Next()) {
       case 'w':
       case 'W':
       case 'd':
       case 'D':
       case 's':
       case 'S': {
         *char_class = Next();
         Advance(2);
         return CharacterRange::Singleton(0);  // Return dummy value.
       }
       case kEndMarker:
         return ReportError(CStrVector("\\ at end of pattern"));
       default:
-        uc32 c = ParseClassCharacterEscape(CHECK_FAILED);
-        return CharacterRange::Singleton(c);
+        first = ParseClassCharacterEscape(CHECK_FAILED);
     }
   } else {
     Advance();
-    return CharacterRange::Singleton(first);
   }
+
+  if (unicode() && unibrow::Utf16::IsLeadSurrogate(first)) {
+    // Combine with possibly following trail surrogate.
+    int start = position();
+    uc32 second = current();
+    if (second == '\\') {
+      second = ParseClassCharacterEscape(CHECK_FAILED);
+    } else {
+      Advance();
+    }
+    if (unibrow::Utf16::IsTrailSurrogate(second)) {
+      first = unibrow::Utf16::CombineSurrogatePair(first, second);
+    } else {
+      Reset(start);
+    }
+  }
+
+  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,
@@ skipping 59 matching lines @@
     is_negated = !is_negated;
   }
   return new (zone()) RegExpCharacterClass(ranges, is_negated);
 }
 
 
 #undef CHECK_FAILED
 
 
 bool RegExpParser::ParseRegExp(Isolate* isolate, Zone* zone,
-                               FlatStringReader* input, bool multiline,
-                               bool unicode, RegExpCompileData* result) {
+                               FlatStringReader* input, JSRegExp::Flags flags,
+                               RegExpCompileData* result) {
   DCHECK(result != NULL);
-  RegExpParser parser(input, &result->error, multiline, unicode, isolate, zone);
+  RegExpParser parser(input, &result->error, flags, isolate, zone);
   RegExpTree* tree = parser.ParsePattern();
   if (parser.failed()) {
     DCHECK(tree == NULL);
     DCHECK(!result->error.is_null());
   } else {
     DCHECK(tree != NULL);
     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_count = capture_count;
   }
   return !parser.failed();
 }
 
 
-RegExpBuilder::RegExpBuilder(Zone* zone)
+RegExpBuilder::RegExpBuilder(Zone* zone, JSRegExp::Flags flags)
     : zone_(zone),
       pending_empty_(false),
+      flags_(flags),
       characters_(NULL),
+      pending_surrogate_(kNoPendingSurrogate),
       terms_(),
       alternatives_()
 #ifdef DEBUG
       ,
       last_added_(ADD_NONE)
 #endif
 {
 }
 
 
+void RegExpBuilder::AddLeadSurrogate(uc16 lead_surrogate) {
+  DCHECK(unibrow::Utf16::IsLeadSurrogate(lead_surrogate));
+  FlushPendingSurrogate();
+  // Hold onto the lead surrogate, waiting for a trail surrogate to follow.
+  pending_surrogate_ = lead_surrogate;
+}
+
+
+void RegExpBuilder::AddTrailSurrogate(uc16 trail_surrogate) {
+  DCHECK(unibrow::Utf16::IsTrailSurrogate(trail_surrogate));
+  if (pending_surrogate_ != kNoPendingSurrogate) {
+    uc16 lead_surrogate = pending_surrogate_;
+    DCHECK(unibrow::Utf16::IsLeadSurrogate(lead_surrogate));
+    ZoneList<uc16> surrogate_pair(2, zone());
+    surrogate_pair.Add(lead_surrogate, zone());
+    surrogate_pair.Add(trail_surrogate, zone());
+    RegExpAtom* atom = new (zone()) RegExpAtom(surrogate_pair.ToConstVector());
+    pending_surrogate_ = kNoPendingSurrogate;
+    AddAtom(atom);
+  } else {
+    pending_surrogate_ = trail_surrogate;
+    FlushPendingSurrogate();
+  }
+}
+
+
+void RegExpBuilder::FlushPendingSurrogate() {
+  if (pending_surrogate_ != kNoPendingSurrogate) {
+    // Use character class to desugar lone surrogate matching.
+    RegExpCharacterClass* cc = new (zone()) RegExpCharacterClass(
+        CharacterRange::List(zone(),
+                             CharacterRange::Singleton(pending_surrogate_)),
+        false);
+    pending_surrogate_ = kNoPendingSurrogate;
+    DCHECK(unicode());
+    AddCharacterClass(cc);
+  }
+}
+
+
 void RegExpBuilder::FlushCharacters() {
+  FlushPendingSurrogate();
   pending_empty_ = false;
   if (characters_ != NULL) {
     RegExpTree* atom = new (zone()) RegExpAtom(characters_->ToConstVector());
     characters_ = NULL;
     text_.Add(atom, zone());
     LAST(ADD_ATOM);
   }
 }
 
 
 void RegExpBuilder::FlushText() {
   FlushCharacters();
   int num_text = text_.length();
   if (num_text == 0) {
     return;
   } else if (num_text == 1) {
     terms_.Add(text_.last(), zone());
   } else {
     RegExpText* text = new (zone()) RegExpText(zone());
     for (int i = 0; i < num_text; i++) text_.Get(i)->AppendToText(text, zone());
     terms_.Add(text, zone());
   }
   text_.Clear();
 }
 
 
 void RegExpBuilder::AddCharacter(uc16 c) {
+  FlushPendingSurrogate();
   pending_empty_ = false;
   if (characters_ == NULL) {
     characters_ = new (zone()) ZoneList<uc16>(4, zone());
   }
   characters_->Add(c, zone());
   LAST(ADD_CHAR);
 }
 
 
 void RegExpBuilder::AddUnicodeCharacter(uc32 c) {
   if (c > unibrow::Utf16::kMaxNonSurrogateCharCode) {
-    ZoneList<uc16> surrogate_pair(2, zone());
-    surrogate_pair.Add(unibrow::Utf16::LeadSurrogate(c), zone());
-    surrogate_pair.Add(unibrow::Utf16::TrailSurrogate(c), zone());
-    RegExpAtom* atom = new (zone()) RegExpAtom(surrogate_pair.ToConstVector());
-    AddAtom(atom);
+    DCHECK(unicode());
+    AddLeadSurrogate(unibrow::Utf16::LeadSurrogate(c));
+    AddTrailSurrogate(unibrow::Utf16::TrailSurrogate(c));
+  } else if (unicode() && unibrow::Utf16::IsLeadSurrogate(c)) {
+    AddLeadSurrogate(c);
+  } else if (unicode() && unibrow::Utf16::IsTrailSurrogate(c)) {
+    AddTrailSurrogate(c);
   } else {
     AddCharacter(static_cast<uc16>(c));
   }
 }
 
 
 void RegExpBuilder::AddEmpty() { pending_empty_ = true; }
 
 
+void RegExpBuilder::AddCharacterClass(RegExpCharacterClass* cc) {
+  if (unicode() && cc->NeedsDesugaringForUnicode(zone())) {
+    // In unicode mode, character class needs to be desugared, so it
+    // must be a standalone term instead of being part of a RegExpText.
+    AddTerm(cc);
+  } else {
+    AddAtom(cc);
+  }
+}
+
+
 void RegExpBuilder::AddAtom(RegExpTree* term) {
   if (term->IsEmpty()) {
     AddEmpty();
     return;
   }
   if (term->IsTextElement()) {
     FlushCharacters();
     text_.Add(term, zone());
   } else {
     FlushText();
     terms_.Add(term, zone());
   }
   LAST(ADD_ATOM);
 }
 
 
+void RegExpBuilder::AddTerm(RegExpTree* term) {
+  FlushText();
+  terms_.Add(term, zone());
+  LAST(ADD_ATOM);
+}
+
+
 void RegExpBuilder::AddAssertion(RegExpTree* assert) {
   FlushText();
   terms_.Add(assert, zone());
   LAST(ADD_ASSERT);
 }
 
 
 void RegExpBuilder::NewAlternative() { FlushTerms(); }
 
 
@@ skipping 18 matching lines @@
   FlushTerms();
   int num_alternatives = alternatives_.length();
   if (num_alternatives == 0) return new (zone()) RegExpEmpty();
   if (num_alternatives == 1) return alternatives_.last();
   return new (zone()) RegExpDisjunction(alternatives_.GetList(zone()));
 }
 
 
 void RegExpBuilder::AddQuantifierToAtom(
     int min, int max, RegExpQuantifier::QuantifierType quantifier_type) {
+  FlushPendingSurrogate();
   if (pending_empty_) {
     pending_empty_ = false;
     return;
   }
   RegExpTree* atom;
   if (characters_ != NULL) {
     DCHECK(last_added_ == ADD_CHAR);
     // Last atom was character.
     Vector<const uc16> char_vector = characters_->ToConstVector();
     int num_chars = char_vector.length();
@@ skipping 26 matching lines @@
     UNREACHABLE();
     return;
   }
   terms_.Add(new (zone()) RegExpQuantifier(min, max, quantifier_type, atom),
              zone());
   LAST(ADD_TERM);
 }
 
 }  // namespace internal
 }  // namespace v8