[regexp] implement case-insensitive 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"
 
+#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),
       in_(in),
@@ skipping 1033 matching lines @@
   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_;
+    pending_surrogate_ = kNoPendingSurrogate;
     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);
+    uc32 combined =
+        unibrow::Utf16::CombineSurrogatePair(lead_surrogate, trail_surrogate);
+    if (NeedsDesugaringForIgnoreCase(combined)) {
+      AddCharacterClass(combined);
+    } else {
+      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());
+      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);
+    DCHECK(unicode());
+    uc32 c = pending_surrogate_;
     pending_surrogate_ = kNoPendingSurrogate;
-    DCHECK(unicode());
-    AddCharacterClass(cc);
+    AddCharacterClass(c);
   }
 }
 
 
 void RegExpBuilder::FlushCharacters() {
   FlushPendingSurrogate();
   pending_empty_ = false;
   if (characters_ != NULL) {
     RegExpTree* atom = new (zone()) RegExpAtom(characters_->ToConstVector());
     characters_ = NULL;
@@ skipping 15 matching lines @@
     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());
+  if (NeedsDesugaringForIgnoreCase(c)) {
+    AddCharacterClass(c);
+  } else {
+    if (characters_ == NULL) {
+      characters_ = new (zone()) ZoneList<uc16>(4, zone());
+    }
+    characters_->Add(c, zone());
+    LAST(ADD_CHAR);
   }
-  characters_->Add(c, zone());
-  LAST(ADD_CHAR);
 }
 
 
 void RegExpBuilder::AddUnicodeCharacter(uc32 c) {
   if (c > unibrow::Utf16::kMaxNonSurrogateCharCode) {
     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())) {
+  if (NeedsDesugaringForUnicode(cc->ranges(zone()))) {

[erikcorry, 2016/01/25 10:26:37]

It's a bit unfortunate, that for all the standard ranges, like \s and \d, this
will cause an allocation, just to determine that we don't need desugaring.

[Yang, 2016/01/25 11:46:37]

Fixed.

     // 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::AddCharacterClass(uc32 c) {
+  AddCharacterClass(new (zone()) RegExpCharacterClass(
+      CharacterRange::List(zone(), CharacterRange::Singleton(c)), false));
+}
+
+
 void RegExpBuilder::AddAtom(RegExpTree* term) {
   if (term->IsEmpty()) {
     AddEmpty();
     return;
   }
   if (term->IsTextElement()) {
     FlushCharacters();
     text_.Add(term, zone());
   } else {
     FlushText();
@@ skipping 30 matching lines @@
     alternative = terms_.last();
   } else {
     alternative = new (zone()) RegExpAlternative(terms_.GetList(zone()));
   }
   alternatives_.Add(alternative, zone());
   terms_.Clear();
   LAST(ADD_NONE);
 }
 
 
+bool RegExpBuilder::NeedsDesugaringForUnicode(
+    ZoneList<CharacterRange>* ranges) {
+  if (!unicode()) return false;
+  CharacterRange::Canonicalize(ranges);
+  static const uc32 kLeadSurrogateStart = 0xd800;
+  static const uc32 kTrailSurrogateEnd = 0xdfff;
+  static const uc32 kNonBmpStart = 0x10000;

[erikcorry, 2016/01/25 10:26:37]

Don't these constants already exist?

[Yang, 2016/01/25 11:46:37]

Done.

+  for (int i = ranges->length() - 1; i >= 0; i--) {
+    uc32 from = ranges->at(i).from();
+    uc32 to = ranges->at(i).to();
+    // Check for non-BMP characters.
+    if (to >= kNonBmpStart) return true;
+    // Check for lone surrogates.
+    if (from <= kTrailSurrogateEnd && to >= kLeadSurrogateStart) return true;
+  }
+  return false;
+}
+
+
+bool RegExpBuilder::NeedsDesugaringForIgnoreCase(uc32 c) {
+#ifdef V8_I18N_SUPPORT

[erikcorry, 2016/01/25 10:26:37]

Perhaps a comment explaining what happens in the non-ICU case - hopefully
something sane.

[Yang, 2016/01/25 11:46:37]

Done.

+  // Ignore-case for ASCII characters is handled at a lower layer.
+  if (c < 128) return false;

[erikcorry, 2016/01/25 10:26:37]

There's a named constant for this.

[Yang, 2016/01/25 11:46:37]

Done.

+  if (unicode() && ignore_case()) {
+    USet* set = uset_open(c, c);
+    uset_closeOver(set, USET_CASE_INSENSITIVE);
+    uset_removeAllStrings(set);
+    bool result = uset_size(set) > 1;
+    uset_close(set);
+    return result;
+  }
+#endif  // V8_I18N_SUPPORT
+  return false;
+}
+
+
 RegExpTree* RegExpBuilder::ToRegExp() {
   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(
@@ skipping 38 matching lines @@
     UNREACHABLE();
     return;
   }
   terms_.Add(new (zone()) RegExpQuantifier(min, max, quantifier_type, atom),
              zone());
   LAST(ADD_TERM);
 }
 
 }  // namespace internal
 }  // namespace v8