[regexp] implement case-insensitive unicode regexps.

src/regexp/jsregexp.cc

 // Copyright 2012 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/jsregexp.h"
 
 #include "src/ast/ast.h"
 #include "src/base/platform/platform.h"
 #include "src/compilation-cache.h"
 #include "src/compiler.h"
 #include "src/execution.h"
 #include "src/factory.h"
 #include "src/isolate-inl.h"
 #include "src/messages.h"
 #include "src/ostreams.h"
 #include "src/regexp/interpreter-irregexp.h"
 #include "src/regexp/jsregexp-inl.h"
 #include "src/regexp/regexp-macro-assembler.h"
 #include "src/regexp/regexp-macro-assembler-irregexp.h"
 #include "src/regexp/regexp-macro-assembler-tracer.h"
 #include "src/regexp/regexp-parser.h"
 #include "src/regexp/regexp-stack.h"
 #include "src/runtime/runtime.h"
 #include "src/splay-tree-inl.h"
 #include "src/string-search.h"
 #include "src/unicode-decoder.h"
 
+#ifdef V8_I18N_SUPPORT
+#include "unicode/uset.h"
+#include "unicode/utypes.h"
+#endif  // V8_I18N_SUPPORT
+
 #ifndef V8_INTERPRETED_REGEXP
 #if V8_TARGET_ARCH_IA32
 #include "src/regexp/ia32/regexp-macro-assembler-ia32.h"
 #elif V8_TARGET_ARCH_X64
 #include "src/regexp/x64/regexp-macro-assembler-x64.h"
 #elif V8_TARGET_ARCH_ARM64
 #include "src/regexp/arm64/regexp-macro-assembler-arm64.h"
 #elif V8_TARGET_ARCH_ARM
 #include "src/regexp/arm/regexp-macro-assembler-arm.h"
 #elif V8_TARGET_ARCH_PPC
@@ skipping 3375 matching lines @@
 void TextNode::MakeCaseIndependent(Isolate* isolate, bool is_one_byte) {
   int element_count = elements()->length();
   for (int i = 0; i < element_count; i++) {
     TextElement elm = elements()->at(i);
     if (elm.text_type() == TextElement::CHAR_CLASS) {
       RegExpCharacterClass* cc = elm.char_class();
       // None of the standard character classes is different in the case
       // independent case and it slows us down if we don't know that.
       if (cc->is_standard(zone())) continue;
       ZoneList<CharacterRange>* ranges = cc->ranges(zone());
-      int range_count = ranges->length();
-      for (int j = 0; j < range_count; j++) {
-        ranges->at(j).AddCaseEquivalents(isolate, zone(), ranges, is_one_byte);
-      }
+      CharacterRange::AddCaseEquivalents(isolate, zone(), ranges, is_one_byte);
     }
   }
 }
 
 
 int TextNode::GreedyLoopTextLength() { return Length(); }
 
 
 RegExpNode* TextNode::GetSuccessorOfOmnivorousTextNode(
     RegExpCompiler* compiler) {
@@ skipping 142 matching lines @@
   AlternativeGeneration* at(int i) {
     return alt_gens_[i];
   }
 
  private:
   static const int kAFew = 10;
   ZoneList<AlternativeGeneration*> alt_gens_;
   AlternativeGeneration a_few_alt_gens_[kAFew];
 };
 
-
-static const uc32 kLeadSurrogateStart = 0xd800;
-static const uc32 kLeadSurrogateEnd = 0xdbff;
-static const uc32 kTrailSurrogateStart = 0xdc00;
-static const uc32 kTrailSurrogateEnd = 0xdfff;
-static const uc32 kNonBmpStart = 0x10000;
-static const uc32 kNonBmpEnd = 0x10ffff;
 static const uc32 kRangeEndMarker = 0x110000;
 
 // The '2' variant is has inclusive from and exclusive to.
 // This covers \s as defined in ECMA-262 5.1, 15.10.2.12,
 // which include WhiteSpace (7.2) or LineTerminator (7.3) values.
 static const int kSpaceRanges[] = {
     '\t',   '\r' + 1, ' ',    ' ' + 1, 0x00A0, 0x00A1, 0x1680,         0x1681,
     0x180E, 0x180F,   0x2000, 0x200B,  0x2028, 0x202A, 0x202F,         0x2030,
     0x205F, 0x2060,   0x3000, 0x3001,  0xFEFF, 0xFF00, kRangeEndMarker};
 static const int kSpaceRangeCount = arraysize(kSpaceRanges);
@@ skipping 782 matching lines @@
   }
 
   LimitResult limit_result = LimitVersions(compiler, trace);
   if (limit_result == DONE) return;
   DCHECK(limit_result == CONTINUE);
 
   RecursionCheck rc(compiler);
 
   DCHECK_EQ(start_reg_ + 1, end_reg_);
   if (compiler->ignore_case()) {
-    assembler->CheckNotBackReferenceIgnoreCase(start_reg_, read_backward(),
-                                               trace->backtrack());
+    assembler->CheckNotBackReferenceIgnoreCase(
+        start_reg_, read_backward(), compiler->unicode(), trace->backtrack());
   } else {
     assembler->CheckNotBackReference(start_reg_, read_backward(),
                                      trace->backtrack());
   }
   // We are going to advance backward, so we may end up at the start.
   if (read_backward()) trace->set_at_start(Trace::UNKNOWN);
   on_success()->Emit(compiler, trace);
 }
 
 
@@ skipping 449 matching lines @@
     return true;
   }
   if (CompareInverseRanges(set_.ranges(zone), kWordRanges, kWordRangeCount)) {
     set_.set_standard_set_type('W');
     return true;
   }
   return false;
 }
 
 
-bool RegExpCharacterClass::NeedsDesugaringForUnicode(Zone* zone) {
-  ZoneList<CharacterRange>* ranges = this->ranges(zone);
-  CharacterRange::Canonicalize(ranges);
-  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;
-}
-
-
 UnicodeRangeSplitter::UnicodeRangeSplitter(Zone* zone,
                                            ZoneList<CharacterRange>* base)
     : zone_(zone),
       table_(zone),
       bmp_(nullptr),
       lead_surrogates_(nullptr),
       trail_surrogates_(nullptr),
       non_bmp_(nullptr) {
   // The unicode range splitter categorizes given character ranges into:
   // - Code points from the BMP representable by one code unit.
@@ skipping 219 matching lines @@
   optional_trail->AddAlternative(
       GuardedAlternative(TextNode::CreateForCharacterRanges(
           zone, trail_surrogates, false, on_success)));
   optional_trail->AddAlternative(GuardedAlternative(on_success));
   RegExpNode* optional_pair = TextNode::CreateForCharacterRanges(
       zone, lead_surrogates, false, optional_trail);
   result->AddAlternative(GuardedAlternative(optional_pair));
 }
 
 
+void AddUnicodeCaseEquivalents(RegExpCompiler* compiler,
+                               ZoneList<CharacterRange>* ranges) {
+#ifdef V8_I18N_SUPPORT
+  // Use ICU to compute the case fold closure over the ranges.
+  DCHECK(compiler->unicode());
+  DCHECK(compiler->ignore_case());
+  USet* set = uset_openEmpty();
+  for (int i = 0; i < ranges->length(); i++) {
+    uset_addRange(set, ranges->at(i).from(), ranges->at(i).to());
+  }
+  ranges->Clear();
+  uset_closeOver(set, USET_CASE_INSENSITIVE);
+  // Full case mapping map single characters to multiple characters.
+  // Those are represented as strings in the set. Remove them so that
+  // we end up with only simple and common case mappings.
+  uset_removeAllStrings(set);
+  int item_count = uset_getItemCount(set);
+  int item_result = 0;
+  UErrorCode ec = U_ZERO_ERROR;
+  Zone* zone = compiler->zone();
+  for (int i = 0; i < item_count; i++) {
+    uc32 start = 0;
+    uc32 end = 0;
+    item_result += uset_getItem(set, i, &start, &end, nullptr, 0, &ec);
+    ranges->Add(CharacterRange::Range(start, end), zone);
+  }
+  // No errors and everything we collected have been ranges.
+  DCHECK_EQ(U_ZERO_ERROR, ec);
+  DCHECK_EQ(0, item_result);
+  uset_close(set);
+#else
+  // Fallback if ICU is not included.
+  CharacterRange::AddCaseEquivalents(compiler->isolate(), compiler->zone(),
+                                     ranges, compiler->one_byte());
+#endif  // V8_I18N_SUPPORT
+  CharacterRange::Canonicalize(ranges);
+}
+
+
 RegExpNode* RegExpCharacterClass::ToNode(RegExpCompiler* compiler,
                                          RegExpNode* on_success) {
   set_.Canonicalize();
   Zone* zone = compiler->zone();
   ZoneList<CharacterRange>* ranges = this->ranges(zone);
+  if (compiler->unicode() && compiler->ignore_case()) {
+    AddUnicodeCaseEquivalents(compiler, ranges);
+  }
   if (compiler->unicode() && !compiler->one_byte()) {
     if (is_negated()) {
       ZoneList<CharacterRange>* negated =
           new (zone) ZoneList<CharacterRange>(2, zone);
       CharacterRange::Negate(ranges, negated, zone);
       ranges = negated;
     }
     if (ranges->length() == 0) {
       // No matches possible.
       return new (zone) EndNode(EndNode::BACKTRACK, zone);
@@ skipping 708 matching lines @@
 
 
 Vector<const int> CharacterRange::GetWordBounds() {
   return Vector<const int>(kWordRanges, kWordRangeCount - 1);
 }
 
 
 void CharacterRange::AddCaseEquivalents(Isolate* isolate, Zone* zone,
                                         ZoneList<CharacterRange>* ranges,
                                         bool is_one_byte) {
-  uc32 bottom = from();
-  uc32 top = to();
-  // Nothing to be done for surrogates.
-  if (bottom >= kLeadSurrogateStart && top <= kTrailSurrogateEnd) return;
-  if (is_one_byte && !RangeContainsLatin1Equivalents(*this)) {
-    if (bottom > String::kMaxOneByteCharCode) return;
-    if (top > String::kMaxOneByteCharCode) top = String::kMaxOneByteCharCode;
-  }
-  unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
-  if (top == bottom) {
+  int range_count = ranges->length();
+  for (int i = 0; i < range_count; i++) {
+    CharacterRange range = ranges->at(i);
+    uc32 bottom = range.from();
+    uc32 top = range.to();
+    // Nothing to be done for surrogates.
+    if (bottom >= kLeadSurrogateStart && top <= kTrailSurrogateEnd) return;
+    if (is_one_byte && !RangeContainsLatin1Equivalents(range)) {
+      if (bottom > String::kMaxOneByteCharCode) return;
+      if (top > String::kMaxOneByteCharCode) top = String::kMaxOneByteCharCode;
+    }
+    unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
+    if (top == bottom) {
     // If this is a singleton we just expand the one character.

[brucedawson, 2016/01/29 18:49:15]

The indenting of this line - and the rest of the function - is now incorrect
because the entire function was wrapped in a for loop. This makes the code very
misleading to read.

I noticed this because a subsequent change added another 'range' variable which
shadows the existing one but the indenting makes this shadowing almost
invisible.

     int length = isolate->jsregexp_uncanonicalize()->get(bottom, '\0', chars);
     for (int i = 0; i < length; i++) {
       uc32 chr = chars[i];
       if (chr != bottom) {
         ranges->Add(CharacterRange::Singleton(chars[i]), zone);
       }
     }
   } else {
     // If this is a range we expand the characters block by block,
     // expanding contiguous subranges (blocks) one at a time.
@@ skipping 30 matching lines @@
         uc32 c = range[i];
         uc32 range_from = c - (block_end - pos);
         uc32 range_to = c - (block_end - end);
         if (!(bottom <= range_from && range_to <= top)) {
           ranges->Add(CharacterRange(range_from, range_to), zone);
         }
       }
       pos = end + 1;
     }
   }
+  }
 }
 
 
 bool CharacterRange::IsCanonical(ZoneList<CharacterRange>* ranges) {
   DCHECK_NOT_NULL(ranges);
   int n = ranges->length();
   if (n <= 1) return true;
   int max = ranges->at(0).to();
   for (int i = 1; i < n; i++) {
     CharacterRange next_range = ranges->at(i);
@@ skipping 350 matching lines @@
   int cp_offset = 0;
   for (int i = 0; i < element_count; i++) {
     TextElement& elm = elements()->at(i);
     elm.set_cp_offset(cp_offset);
     cp_offset += elm.length();
   }
 }
 
 
 void Analysis::VisitText(TextNode* that) {
-  if (ignore_case_) {
+  if (ignore_case()) {
     that->MakeCaseIndependent(isolate(), is_one_byte_);
   }
   EnsureAnalyzed(that->on_success());
   if (!has_failed()) {
     that->CalculateOffsets();
   }
 }
 
 
 void Analysis::VisitAction(ActionNode* that) {
@@ skipping 344 matching lines @@
     // put because they had not been calculated yet.
     if (node != NULL) {
       node = node->FilterOneByte(RegExpCompiler::kMaxRecursion, ignore_case);
     }
   } else if (compiler.unicode() && (is_global || is_sticky)) {
     node = OptionallyStepBackToLeadSurrogate(&compiler, node);
   }
 
   if (node == NULL) node = new(zone) EndNode(EndNode::BACKTRACK, zone);
   data->node = node;
-  Analysis analysis(isolate, ignore_case, is_one_byte);
+  Analysis analysis(isolate, flags, is_one_byte);
   analysis.EnsureAnalyzed(node);
   if (analysis.has_failed()) {
     const char* error_message = analysis.error_message();
     return CompilationResult(isolate, error_message);
   }
 
   // Create the correct assembler for the architecture.
 #ifndef V8_INTERPRETED_REGEXP
   // Native regexp implementation.
 
@@ skipping 166 matching lines @@
 
 
 void RegExpResultsCache::Clear(FixedArray* cache) {
   for (int i = 0; i < kRegExpResultsCacheSize; i++) {
     cache->set(i, Smi::FromInt(0));
   }
 }
 
 }  // namespace internal
 }  // namespace v8