Call out to ICU for case conversion

src/runtime/runtime-strings.cc

Index: src/runtime/runtime-strings.cc
diff --git a/src/runtime/runtime-strings.cc b/src/runtime/runtime-strings.cc
index bd4dd699b4576363f7232380b75653e20863fce1..09f9cafb59f0df3299020d29020ea4643dbeccb8 100644
--- a/src/runtime/runtime-strings.cc
+++ b/src/runtime/runtime-strings.cc
@@ -12,6 +12,11 @@
 #include "src/string-builder.h"
 #include "src/string-search.h"
 
+#ifdef V8_I18N_SUPPORT
+#include "unicode/uchar.h"
+#include "unicode/ustring.h"
+#endif
+
 namespace v8 {
 namespace internal {
 
@@ -1069,19 +1074,242 @@ MUST_USE_RESULT static Object* ConvertCase(
 }
 
 
+#ifdef V8_I18N_SUPPORT
+namespace {

[Yang, 2016/01/07 09:47:38]

Can we move all of that into its own file?

+
+typedef int32_t (*case_conversion_fn)(UChar* dest, int32_t destCapacity,
+                                      const UChar* src, int32_t srcLength,
+                                      const char* locale,
+                                      UErrorCode* pErrorCode);
+
+MUST_USE_RESULT static Handle<String> ConvertCaseICU(Handle<String> s,
+                                                     Isolate* isolate,
+                                                     case_conversion_fn fn) {
+  int32_t length = s->length();
+  Handle<SeqTwoByteString> result =
+      isolate->factory()->NewRawTwoByteString(length).ToHandleChecked();
+
+  // If we already have a UTF-16 string, use that, otherwise build it
+  base::SmartArrayPointer<uc16> sap;
+  const UChar* src;
+  if (StringShape(*s).IsSequentialTwoByte()) {
+    src =
+        reinterpret_cast<const UChar*>(SeqTwoByteString::cast(*s)->GetChars());

[Yang, 2016/01/07 09:47:38]

Please use String::FlatContent to access the flat content.

+  } else {
+    sap = s->ToWideCString(ROBUST_STRING_TRAVERSAL);
+    src = reinterpret_cast<const UChar*>(sap.get());
+  }
+
+  UErrorCode error = U_ZERO_ERROR;
+  int32_t real_length = fn(reinterpret_cast<UChar*>(result->GetChars()), length,
+                           src, length, "", &error);
+  // If the lengths are equal, ICU will be unable to put the terminating \0
+  // but that's to be expected, as V8 strings are not null-terminated.
+  if (error == U_STRING_NOT_TERMINATED_WARNING) {
+    DCHECK_EQ(real_length, length);
+    return Handle<String>(*result);
+  }
+  // These are the two expected error types from an oversized converted string
+  // "buffer overflow" when needs more space; "success" when too long
+  DCHECK(error == U_BUFFER_OVERFLOW_ERROR || error == U_ZERO_ERROR);
+
+  error = U_ZERO_ERROR;
+  result =
+      isolate->factory()->NewRawTwoByteString(real_length).ToHandleChecked();
+  int32_t real_length_again = fn(reinterpret_cast<UChar*>(result->GetChars()),

[Yang, 2016/01/07 09:47:38]

Instead of running the whole thing again, you could simply create a new string
with the excess length, convert the remaining characters, and create a cons
string for both parts.

+                                 real_length, src, length, "", &error);

[Yang, 2016/01/07 09:47:38]

src can have moved already after the allocation of the two byte string. Please
use a new instance of String::FlatContent to refetch the source.

+  USE(real_length_again);  // Shouldn't that be part of DCHECK_EQ?
+  DCHECK_EQ(real_length, real_length_again);
+  DCHECK_EQ(error, U_STRING_NOT_TERMINATED_WARNING);
+  if (error != U_STRING_NOT_TERMINATED_WARNING) return s;
+  return Handle<String>(*result);
+}
+
+
+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();
+  // 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);

[Yang, 2016/01/07 09:47:38]

This can get pretty expensive if the string is a deeply nested ConsString.
Please flatten it and use String::FlatContent instead.

+      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();
+    // In Blink, this is a simple memcpy, but in V8, the path applies in
+    // more cases. The optimization here is conditional on whether the
+    // source is actually a simple 8-bit string (always true in Blink).
+    // The broader condition lets us eliminate a bunch of duplicate code
+    // which Blink had in a separate section below.
+    if (StringShape(*s).IsSequentialOneByte()) {

[Yang, 2016/01/07 09:47:38]

Let's not use StringShape. Just check for s->IsSeqOneByteString().

+      // In this path, we can use the one-byte-specific Get, and
+      // memcpy until the first_index_to_lower.
+      SeqOneByteString* source = SeqOneByteString::cast(*s);
+      memcpy(result->GetChars(), source->GetChars(), first_index_to_lower);

[Yang, 2016/01/07 09:47:38]

We should just use CopyChars for uniformity here. See below.

+      for (int index = first_index_to_lower; index < length; ++index) {
+        uint16_t ch = source->SeqOneByteStringGet(index);
+        result->SeqOneByteStringSet(index,
+                                    V8_UNLIKELY(ch & ~0x7F)
+                                        ? static_cast<uint16_t>(u_tolower(ch))
+                                        : ToASCIILower(ch));
+      }
+    } else {
+      // In this path, we start from the beginning of the string,
+      // since there is nothing to memcpy from, and we have to
+      // use the generic Get. Another  option here would be to create
+      // a two-byte string as output, and do a memcpy from that,
+      // as Blink does, but there's also the ConsString case.

[Yang, 2016/01/07 09:47:38]

As explained above, we should flatten upfront, so no ConsStrings here. We could
then do CopyChars up to first_index_to_lower, which handles the two-byte to
one-byte copying.

+      for (int index = 0; 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, u_strToLower);
+}
+
+
+const uint16_t sharp_s = L'\u00DF';

[Yang, 2016/01/07 09:47:38]

0xDF should do the trick to, right?

+
+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();
+
+  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);

[Yang, 2016/01/07 09:47:38]

Again, please flatten upfront and use String::FlatContent.

+      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;
+      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.
+        goto upconvert;

[Yang, 2016/01/07 09:47:38]

Can't we simply "return ConvertCaseICU(s, isolate, u_strToUpper);"? I'd prefer
this small code duplication way more than goto.

+      }
+      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);
+  }
+
+upconvert:
+  return ConvertCaseICU(s, isolate, u_strToUpper);
+}
+
+}  // 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)

[Yang, 2016/01/07 09:47:38]

the convention with multiline conditionals is to use brackets.

+    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());
 }