Use ICU case conversion/transliterator for case conversion behind a flag

src/runtime/runtime-strings.cc

 // Copyright 2014 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/runtime/runtime-utils.h"
 
 #include "src/arguments.h"
 #include "src/conversions-inl.h"
 #include "src/isolate-inl.h"
 #include "src/regexp/jsregexp-inl.h"
 #include "src/regexp/jsregexp.h"
 #include "src/string-builder.h"
 #include "src/string-search.h"
 
+#ifdef V8_I18N_SUPPORT
+#include "unicode/locid.h"
+#include "unicode/uchar.h"
+#include "unicode/unistr.h"
+#endif
+
 namespace v8 {
 namespace internal {
 
 
 // Perform string match of pattern on subject, starting at start index.
 // Caller must ensure that 0 <= start_index <= sub->length(),
 // and should check that pat->length() + start_index <= sub->length().
 int StringMatch(Isolate* isolate, Handle<String> sub, Handle<String> pat,
                 int start_index) {
   DCHECK(0 <= start_index);
@@ skipping 1045 matching lines @@
     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
         isolate, result, isolate->factory()->NewRawOneByteString(length));
   } else {
     if (length < 0) length = -length;
     ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
         isolate, result, isolate->factory()->NewRawTwoByteString(length));
   }
   return ConvertCaseHelper(isolate, *s, *result, length, mapping);
 }
 
+#ifdef V8_I18N_SUPPORT
+namespace {
+
+MUST_USE_RESULT static Handle<String> ConvertCaseICU(Handle<String> s,
+                                                     Isolate* isolate,
+                                                     bool is_to_upper) {
+  int32_t length = s->length();
+  icu::UnicodeString converted;
+  {
+    DisallowHeapAllocation no_gc;
+    DCHECK(s->IsFlat());
+    String::FlatContent flat = s->GetFlatContent();
+
+    const UChar* src;
+    if (flat.IsOneByte()) {
+      base::SmartArrayPointer<uc16> sap = s->ToWideCString();
+      src = reinterpret_cast<const UChar*>(sap.get());
+      converted = icu::UnicodeString(src, length);
+    } else {
+      src = reinterpret_cast<const UChar*>(flat.ToUC16Vector().start());
+      converted = icu::UnicodeString(src, length);
+    }
+  }
+
+  const icu::Locale& root_locale = icu::Locale::getRoot();
+  if (is_to_upper)
+    converted.toUpper(root_locale);
+  else
+    converted.toLower(root_locale);
+
+  return isolate->factory()
+      ->NewStringFromTwoByte(Vector<const uint16_t>(
+          reinterpret_cast<const uint16_t*>(converted.getBuffer()),
+          converted.length()))
+      .ToHandleChecked();
+}
+
+inline bool IsASCIIUpper(uint16_t ch) { return ch >= 'A' && ch <= 'Z'; }
+
+inline uint16_t ToASCIILower(uint16_t ch) {
+  return ch | ((ch >= 'A' && ch <= 'Z') << 5);
+}
+
+inline uint16_t ToASCIIUpper(uint16_t ch) {
+  return ch & ~((ch >= 'a' && ch <= 'z') << 5);
+}
+
+MUST_USE_RESULT Handle<String> StringToLowerCase(Handle<String> s,
+                                                 Isolate* isolate) {
+  // Note: This is a hot function in the Dromaeo benchmark, specifically the
+  // no-op code path up through the first 'return' statement.
+
+  int length = s->length();
+  s = String::Flatten(s);
+  // First scan the string for uppercase and non-ASCII characters:
+  if (s->HasOnlyOneByteChars()) {
+    unsigned first_index_to_lower = length;
+    for (int index = 0; index < length; ++index) {
+      // Blink specializes this path for one-byte strings, so it
+      // does not need to do a generic get, but can do the equivalent
+      // of SeqOneByteStringGet.
+      uint16_t ch = s->Get(index);
+      if (V8_UNLIKELY(IsASCIIUpper(ch) || ch & ~0x7F)) {
+        first_index_to_lower = index;
+        break;
+      }
+    }
+
+    // Nothing to do if the string is all ASCII with no uppercase.
+    if (first_index_to_lower == length) return s;
+
+    // We depend here on the invariant that the length of a Latin1
+    // string is invariant under ToLowerCase, and the result always
+    // fits in the Latin1 range (untrue for ToUpperCase, and might
+    // be untrue in some locales, but this is the root locale)
+    Handle<SeqOneByteString> result =
+        isolate->factory()->NewRawOneByteString(length).ToHandleChecked();
+    if (s->IsSeqOneByteString()) {
+      SeqOneByteString* source = SeqOneByteString::cast(*s);
+      CopyChars(result->GetChars(), source->GetChars(), first_index_to_lower);
+    } else {
+      // Do we have to worry about External{One,Two}ByteString?
+      DCHECK(s->IsSeqTwoByteString());
+      SeqTwoByteString* source = SeqTwoByteString::cast(*s);
+      CopyChars(result->GetChars(), source->GetChars(), first_index_to_lower);
+    }
+
+    for (int index = first_index_to_lower; index < length; ++index) {
+      uint16_t ch = s->Get(index);
+      result->SeqOneByteStringSet(
+          index, V8_UNLIKELY(ch & ~0x7F) ? static_cast<uint16_t>(u_tolower(ch))
+                                         : ToASCIILower(ch));
+    }
+
+    return Handle<String>(*result);
+  }
+
+  // Blink had an additional case here for ASCII 2-byte strings, but
+  // that is subsumed by the above code (assuming there isn't a false
+  // negative for HasOnlyOneByteChars).
+
+  // Do a slower implementation for cases that include non-ASCII characters.
+  return ConvertCaseICU(s, isolate, false);
+}
+
+const uint16_t sharp_s = 0x00DFu;
+
+MUST_USE_RESULT Handle<String> StringToUpperCase(Handle<String> s,
+                                                 Isolate* isolate) {
+  // This function could be optimized for no-op cases the way lower() is,
+  // but in empirical testing, few actual calls to upper() are no-ops, so
+  // it wouldn't be worth the extra time for pre-scanning.
+
+  int32_t length = s->length();
+  s = String::Flatten(s);
+
+  if (s->HasOnlyOneByteChars()) {
+    Handle<SeqOneByteString> result =
+        isolate->factory()->NewRawOneByteString(length).ToHandleChecked();
+
+    // Do a faster loop for the case where all the characters are ASCII.
+    uint16_t ored = 0;
+    for (int index = 0; index < length; ++index) {
+      uint16_t ch = s->Get(index);
+      ored |= ch;
+      result->SeqOneByteStringSet(index, ToASCIIUpper(ch));
+    }
+    if (!(ored & ~0x7F)) return Handle<String>(*result);
+
+    // Do a slower implementation for cases that include non-ASCII Latin-1
+    // characters.
+    int sharp_s_count = 0;
+
+    // There are two special cases.
+    //  1. latin-1 characters when converted to upper case are 16 bit
+    //  characters.
+    //  2. Lower case sharp-S converts to "SS" (two characters)
+    for (int32_t index = 0; index < length; ++index) {
+      uint16_t ch = s->Get(index);
+      if (V8_UNLIKELY(ch == sharp_s)) {
+        ++sharp_s_count;
+        continue;
+      }
+      uint16_t upper = static_cast<uint16_t>(u_toupper(static_cast<UChar>(ch)));
+      if (V8_UNLIKELY(upper > 0xff)) {
+        // Since this upper-cased character does not fit in an 8-bit string, we
+        // need to take the 16-bit path.
+        return ConvertCaseICU(s, isolate, true);
+      }
+      result->SeqOneByteStringSet(index, upper);
+    }
+
+    if (sharp_s_count == 0) return Handle<String>(*result);
+
+    // We have sharp_s_count sharp-s characters, but none of the other special
+    // characters.
+    result = isolate->factory()
+                 ->NewRawOneByteString(length + sharp_s_count)
+                 .ToHandleChecked();
+    for (int32_t index = 0, dest_index = 0; index < length; ++index) {
+      uint16_t ch = s->Get(index);
+      if (ch == sharp_s) {
+        result->SeqOneByteStringSet(dest_index++, 'S');
+        result->SeqOneByteStringSet(dest_index++, 'S');
+      } else {
+        uint16_t upper =
+            static_cast<uint16_t>(u_toupper(static_cast<UChar>(ch)));
+        result->SeqOneByteStringSet(dest_index++, upper);
+      }
+    }
+
+    return Handle<String>(*result);
+  }
+
+  return ConvertCaseICU(s, isolate, true);
+}
+
+}  // namespace
+#endif
 
 RUNTIME_FUNCTION(Runtime_StringToLowerCase) {
   HandleScope scope(isolate);
-  DCHECK(args.length() == 1);
+  DCHECK_EQ(args.length(), 1);
   CONVERT_ARG_HANDLE_CHECKED(String, s, 0);
-  return ConvertCase(s, isolate, isolate->runtime_state()->to_lower_mapping());
+#ifdef V8_I18N_SUPPORT
+  if (FLAG_icu_case_mapping)

[jungshik at Google, 2016/04/08 19:44:42]

Do we need this flag once we're satisfied with perf etc?  
Dan, what kind of micro benchmark test did you run?  

[Dan Ehrenberg, 2016/04/08 21:13:46]

Microbenchmarks and results here:

https://docs.google.com/spreadsheets/d/1xDpYTaFVE97rtqQ5KyZCk4T_QJsKp-S_lRhQZ...

Agreed that we won't need this flag long-term, but it's good to develop new
features under a flag.

+    return *StringToLowerCase(s, isolate);
+  else
+#endif
+    return ConvertCase(s, isolate,
+                       isolate->runtime_state()->to_lower_mapping());
 }
 
 
 RUNTIME_FUNCTION(Runtime_StringToUpperCase) {
   HandleScope scope(isolate);
-  DCHECK(args.length() == 1);
+  DCHECK_EQ(args.length(), 1);
   CONVERT_ARG_HANDLE_CHECKED(String, s, 0);
-  return ConvertCase(s, isolate, isolate->runtime_state()->to_upper_mapping());
-}
-
-
+#ifdef V8_I18N_SUPPORT
+  if (FLAG_icu_case_mapping)
+    return *StringToUpperCase(s, isolate);
+  else
+#endif
+    return ConvertCase(s, isolate,
+                       isolate->runtime_state()->to_upper_mapping());
+}
+
+
 RUNTIME_FUNCTION(Runtime_StringTrim) {
   HandleScope scope(isolate);
   DCHECK(args.length() == 3);
 
   CONVERT_ARG_HANDLE_CHECKED(String, string, 0);
   CONVERT_BOOLEAN_ARG_CHECKED(trimLeft, 1);
   CONVERT_BOOLEAN_ARG_CHECKED(trimRight, 2);
 
   string = String::Flatten(string);
   int length = string->length();
@@ skipping 211 matching lines @@
   SealHandleScope shs(isolate);
   DCHECK(args.length() == 2);
   if (!args[0]->IsString()) return isolate->heap()->undefined_value();
   if (!args[1]->IsNumber()) return isolate->heap()->undefined_value();
   if (std::isinf(args.number_at(1))) return isolate->heap()->nan_value();
   return __RT_impl_Runtime_StringCharCodeAtRT(args, isolate);
 }
 
 }  // namespace internal
 }  // namespace v8