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

src/runtime/runtime-i18n.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.
 
 
 #ifdef V8_I18N_SUPPORT
 #include "src/runtime/runtime-utils.h"
 
 #include "src/api.h"
 #include "src/api-natives.h"
@@ skipping 11 matching lines @@
 #include "unicode/dcfmtsym.h"
 #include "unicode/decimfmt.h"
 #include "unicode/dtfmtsym.h"
 #include "unicode/dtptngen.h"
 #include "unicode/locid.h"
 #include "unicode/numfmt.h"
 #include "unicode/numsys.h"
 #include "unicode/rbbi.h"
 #include "unicode/smpdtfmt.h"
 #include "unicode/timezone.h"
+#include "unicode/translit.h"
 #include "unicode/uchar.h"
 #include "unicode/ucol.h"
 #include "unicode/ucurr.h"
 #include "unicode/uloc.h"
+#include "unicode/unistr.h"
 #include "unicode/unum.h"
 #include "unicode/uversion.h"
 
 
 namespace v8 {
 namespace internal {
 
 RUNTIME_FUNCTION(Runtime_CanonicalizeLanguageTag) {
   HandleScope scope(isolate);
   Factory* factory = isolate->factory();
@@ skipping 696 matching lines @@
   } else if (status >= UBRK_WORD_LETTER && status < UBRK_WORD_LETTER_LIMIT) {
     return *isolate->factory()->NewStringFromStaticChars("letter");
   } else if (status >= UBRK_WORD_KANA && status < UBRK_WORD_KANA_LIMIT) {
     return *isolate->factory()->NewStringFromStaticChars("kana");
   } else if (status >= UBRK_WORD_IDEO && status < UBRK_WORD_IDEO_LIMIT) {
     return *isolate->factory()->NewStringFromStaticChars("ideo");
   } else {
     return *isolate->factory()->NewStringFromStaticChars("unknown");
   }
 }
+
+namespace {
+void ConvertCaseWithTransliterator(icu::UnicodeString* input,
+                                   const char* transliterator_id) {
+  UErrorCode status = U_ZERO_ERROR;
+  base::SmartPointer<icu::Transliterator> translit(
+      icu::Transliterator::createInstance(
+          icu::UnicodeString(transliterator_id, -1, US_INV), UTRANS_FORWARD,
+          status));
+  if (U_FAILURE(status)) return;
+  translit->transliterate(*input);
+}
+
+const UChar* GetUCharBufferFromFlat(const String::FlatContent& flat, uc16* dest,
+                                    int32_t length) {
+  DCHECK(flat.IsFlat());
+  if (flat.IsOneByte()) {
+    CopyChars(dest, flat.ToOneByteVector().start(), length);
+    return reinterpret_cast<const UChar*>(dest);
+  } else {
+    return reinterpret_cast<const UChar*>(flat.ToUC16Vector().start());
+  }
+}
+
+MUST_USE_RESULT Object* LocaleConvertCase(Handle<String> s, Isolate* isolate,
+                                          bool is_to_upper, const char* lang) {
+  int32_t src_length = s->length();
+
+  // Greek uppercasing has to be done via transliteration.
+  // TODO(jshin): Drop this special-casing once ICU's regular case conversion
+  // API supports Greek uppercasing. See
+  // http://bugs.icu-project.org/trac/ticket/10582 .
+  // In the meantime, if there's no Greek character in |s|, call this
+  // function again with the root locale (lang="").
+  // ICU's C API for transliteration is nasty and we just use C++ API.
+  if (V8_UNLIKELY(is_to_upper && lang[0] == 'e' && lang[1] == 'l')) {
+    icu::UnicodeString converted;
+    base::SmartArrayPointer<uc16> sap(NewArray<uc16>(src_length));
+    {
+      DisallowHeapAllocation no_gc;
+      String::FlatContent flat = s->GetFlatContent();
+      const UChar* src = GetUCharBufferFromFlat(flat, sap.get(), src_length);
+      // Starts with the source string (read-only alias with copy-on-write
+      // semantics) and will be modified to contain the converted result.
+      // Using read-only alias at first saves one copy operation if
+      // transliteration does not change the input, which is rather rare.
+      // Moreover, transliteration takes rather long so that saving one copy
+      // helps only a little bit.
+      converted.setTo(false, src, src_length);

[jungshik at Google, 2016/04/29 23:41:43]

Yang, 

https://docs.google.com/spreadsheets/d/19FCu-uk48FT7NCvMxRWgsnrCc06iON79Uni4a...
compares various combinations of aliasing and copying when obtaining |src|
(GetUCharBufferFromFlat) and setting up the input UnicodeString with setTo(). 

Using read-alias for two-byte string when obtaining |src| and read-alias for
setTo minimizes # of copy operations. 

One outstanding question is whether the buffer pointed to by
|flat.ToUC16Vector()| will continue to be reliably available after |flat| goes
out of scope even though a flattened string (from which |flat| was obtained)
remains in the scope (and not gc'd away).

Adam thinks that it can still cause a problem (I asked him that question a week
or so ago) and I want to play safe. Therefore, I changed the CL to avoid that. 
I have since discovered that the implementation and usage pattern of
GetCharVector() ( https://goo.gl/EsgZXq ) kinda indicates otherwise. The way the
return value of GetCharVector() is used is almost identical to this one except
that in my case, I need to access the buffer even after DisallowHeapAllocation
is NOT in force any more. 

Anyway, if the way I use the buffer obtained via GetFlatContent() is safe [1],
the current way (using read-alias for both steps) is the best (although the
difference would be rather small relatively because Transltierator takes so
long). 

If not, either '1. alias 2. upfront copy' or '1. copy 2. alias' should be used.
'1. copy 2. alias' is what you suggested.  I prefer to use '1. alias 2. upfront
copy' (PS #47 ~ #49) because I'm using GetUCharBufferFromFlat() in non-Greek
code-path below (which is much more common) where '1. copy' is wasteful.

Well, I shouldn't tinker with this too much because 1) ICU 58 in 5 months  will
support el-Upper with a regular case conversion API (no more need for
special-casing) 2) the cost of transliteration is so expensive that saving one
copy does not help much. 

[1] I have yet to find a test that will break for TwoByteString path. When |sap|
is inside DisallowHeapAllocation block, accessing |converted| with an unmodified
buffer, I definitely get a crash for a OneByte input in a debug build. 

+      ConvertCaseWithTransliterator(&converted, "el-Upper");
+    }
+    Handle<String> result;
+    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
+        isolate, result,
+        isolate->factory()->NewStringFromTwoByte(Vector<const uint16_t>(
+            reinterpret_cast<const uint16_t*>(converted.getBuffer()),
+            converted.length())));
+    return *result;
+  }
+
+  auto case_converter = is_to_upper ? u_strToUpper : u_strToLower;
+
+  int32_t dest_length = src_length;
+  UErrorCode status;
+  Handle<SeqTwoByteString> result;
+  base::SmartArrayPointer<uc16> sap(NewArray<uc16>(src_length));
+
+  // This is not a real loop. It'll be executed only once (no overflow) or
+  // twice (overflow).
+  for (int i = 0; i < 2; ++i) {
+    result =
+        isolate->factory()->NewRawTwoByteString(dest_length).ToHandleChecked();
+    DisallowHeapAllocation no_gc;
+    String::FlatContent flat = s->GetFlatContent();
+    const UChar* src = GetUCharBufferFromFlat(flat, sap.get(), src_length);
+    status = U_ZERO_ERROR;
+    dest_length = case_converter(reinterpret_cast<UChar*>(result->GetChars()),
+                                 dest_length, src, src_length, lang, &status);
+    if (status != U_BUFFER_OVERFLOW_ERROR) break;
+  }
+
+  // In most cases, the output will fill the destination buffer completely
+  // leading to an unterminated string (U_STRING_NOT_TERMINATED_WARNING).
+  // Only in rare cases, it'll be shorter than the destination buffer and
+  // |result| has to be truncated.
+  DCHECK(U_SUCCESS(status));
+  if (V8_LIKELY(status == U_STRING_NOT_TERMINATED_WARNING)) {
+    DCHECK(dest_length == result->length());
+    return *result;
+  }
+  if (U_SUCCESS(status)) {
+    DCHECK(dest_length < result->length());
+    return *Handle<SeqTwoByteString>::cast(
+        SeqString::Truncate(result, dest_length));
+  }
+  return *s;
+}
+
+inline bool IsASCIIUpper(uint16_t ch) { return ch >= 'A' && ch <= 'Z'; }
+
+const uint8_t kToLower[256] = {
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B,
+    0x0C, 0x0D, 0x0E, 0x0F, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
+    0x18, 0x19, 0x1A, 0x1B, 0x1C, 0x1D, 0x1E, 0x1F, 0x20, 0x21, 0x22, 0x23,
+    0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E, 0x2F,
+    0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3A, 0x3B,
+    0x3C, 0x3D, 0x3E, 0x3F, 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
+    0x68, 0x69, 0x6A, 0x6B, 0x6C, 0x6D, 0x6E, 0x6F, 0x70, 0x71, 0x72, 0x73,
+    0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7A, 0x5B, 0x5C, 0x5D, 0x5E, 0x5F,
+    0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6A, 0x6B,
+    0x6C, 0x6D, 0x6E, 0x6F, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
+    0x78, 0x79, 0x7A, 0x7B, 0x7C, 0x7D, 0x7E, 0x7F, 0x80, 0x81, 0x82, 0x83,
+    0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8A, 0x8B, 0x8C, 0x8D, 0x8E, 0x8F,
+    0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9A, 0x9B,
+    0x9C, 0x9D, 0x9E, 0x9F, 0xA0, 0xA1, 0xA2, 0xA3, 0xA4, 0xA5, 0xA6, 0xA7,
+    0xA8, 0xA9, 0xAA, 0xAB, 0xAC, 0xAD, 0xAE, 0xAF, 0xB0, 0xB1, 0xB2, 0xB3,
+    0xB4, 0xB5, 0xB6, 0xB7, 0xB8, 0xB9, 0xBA, 0xBB, 0xBC, 0xBD, 0xBE, 0xBF,
+    0xE0, 0xE1, 0xE2, 0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9, 0xEA, 0xEB,
+    0xEC, 0xED, 0xEE, 0xEF, 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xD7,
+    0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xDF, 0xE0, 0xE1, 0xE2, 0xE3,
+    0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9, 0xEA, 0xEB, 0xEC, 0xED, 0xEE, 0xEF,
+    0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, 0xF8, 0xF9, 0xFA, 0xFB,
+    0xFC, 0xFD, 0xFE, 0xFF,
+};
+
+inline uint16_t ToLatin1Lower(uint16_t ch) {
+  return static_cast<uint16_t>(kToLower[ch]);
+}
+
+inline uint16_t ToASCIIUpper(uint16_t ch) {
+  return ch & ~((ch >= 'a' && ch <= 'z') << 5);
+}
+
+// Does not work for U+00DF (sharp-s), U+00B5 (micron), U+00FF.
+inline uint16_t ToLatin1Upper(uint16_t ch) {
+  DCHECK(ch != 0xDF && ch != 0xB5 && ch != 0xFF);
+  return ch &
+         ~(((ch >= 'a' && ch <= 'z') || (((ch & 0xE0) == 0xE0) && ch != 0xE7))
+           << 5);
+}
+
+template <typename Char>
+bool ToUpperFastASCII(const Vector<const Char>& src,
+                      Handle<SeqOneByteString> result) {
+  // Do a faster loop for the case where all the characters are ASCII.
+  uint16_t ored = 0;
+  int32_t index = 0;
+  for (auto it = src.begin(); it != src.end(); ++it) {
+    uint16_t ch = static_cast<uint16_t>(*it);
+    ored |= ch;
+    result->SeqOneByteStringSet(index++, ToASCIIUpper(ch));
+  }
+  return !(ored & ~0x7F);
+}
+
+const uint16_t sharp_s = 0xDF;
+
+template <typename Char>
+bool ToUpperOneByte(const Vector<const Char>& src,
+                    Handle<SeqOneByteString> result, int* sharp_s_count) {
+  // Still pretty-fast path for the input with non-ASCII Latin-1 characters.
+
+  // There are two special cases.
+  //  1. U+00B5 and U+00FF are mapped to a character beyond U+00FF.
+  //  2. Lower case sharp-S converts to "SS" (two characters)
+  *sharp_s_count = 0;
+  int32_t index = 0;
+  for (auto it = src.begin(); it != src.end(); ++it) {
+    uint16_t ch = static_cast<uint16_t>(*it);
+    if (V8_UNLIKELY(ch == sharp_s)) {
+      ++(*sharp_s_count);
+      continue;
+    }
+    if (V8_UNLIKELY(ch == 0xB5 || ch == 0xFF)) {
+      // Since this upper-cased character does not fit in an 8-bit string, we
+      // need to take the 16-bit path.
+      return false;
+    }
+    result->SeqOneByteStringSet(index++, ToLatin1Upper(ch));
+  }
+
+  return true;
+}
+
+template <typename Char>
+void ToUpperWithSharpS(const Vector<const Char>& src,
+                       Handle<SeqOneByteString> result) {
+  int32_t dest_index = 0;
+  for (auto it = src.begin(); it != src.end(); ++it) {
+    uint16_t ch = static_cast<uint16_t>(*it);
+    if (ch == sharp_s) {
+      result->SeqOneByteStringSet(dest_index++, 'S');
+      result->SeqOneByteStringSet(dest_index++, 'S');
+    } else {
+      result->SeqOneByteStringSet(dest_index++, ToLatin1Upper(ch));
+    }
+  }
+}
+
+}  // namespace
+
+RUNTIME_FUNCTION(Runtime_StringToLowerCaseI18N) {
+  HandleScope scope(isolate);
+  DCHECK_EQ(args.length(), 1);
+  CONVERT_ARG_HANDLE_CHECKED(String, s, 0);
+
+  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 in the *root locale*. It does not hold
+    // for ToUpperCase even in the root locale.
+    Handle<SeqOneByteString> result;
+    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
+        isolate, result, isolate->factory()->NewRawOneByteString(length));
+
+    DisallowHeapAllocation no_gc;
+    String::FlatContent flat = s->GetFlatContent();
+    if (flat.IsOneByte()) {
+      const uint8_t* src = flat.ToOneByteVector().start();
+      CopyChars(result->GetChars(), src, first_index_to_lower);
+      for (int index = first_index_to_lower; index < length; ++index) {
+        uint16_t ch = static_cast<uint16_t>(src[index]);
+        result->SeqOneByteStringSet(index, ToLatin1Lower(ch));
+      }
+    } else {
+      const uint16_t* src = flat.ToUC16Vector().start();
+      CopyChars(result->GetChars(), src, first_index_to_lower);
+      for (int index = first_index_to_lower; index < length; ++index) {
+        uint16_t ch = src[index];
+        result->SeqOneByteStringSet(index, ToLatin1Lower(ch));
+      }
+    }
+
+    return *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 LocaleConvertCase(s, isolate, false, "");
+}
+
+RUNTIME_FUNCTION(Runtime_StringToUpperCaseI18N) {
+  HandleScope scope(isolate);
+  DCHECK_EQ(args.length(), 1);
+  CONVERT_ARG_HANDLE_CHECKED(String, s, 0);
+
+  // This function could be optimized for no-op cases the way lowercase
+  // counterpart 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;
+    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
+        isolate, result, isolate->factory()->NewRawOneByteString(length));
+
+    int sharp_s_count;
+    bool is_result_single_byte;
+    {
+      DisallowHeapAllocation no_gc;
+      String::FlatContent flat = s->GetFlatContent();
+      // If it was ok to slow down ASCII-only input slightly, ToUpperFastASCII
+      // could be removed  because ToUpperOneByte is pretty fast now (it
+      // does not call ICU API any more.).
+      if (flat.IsOneByte()) {
+        Vector<const uint8_t> src = flat.ToOneByteVector();
+        if (ToUpperFastASCII(src, result)) return *result;
+        is_result_single_byte = ToUpperOneByte(src, result, &sharp_s_count);
+      } else {
+        DCHECK(flat.IsTwoByte());
+        Vector<const uint16_t> src = flat.ToUC16Vector();
+        if (ToUpperFastASCII(src, result)) return *result;
+        is_result_single_byte = ToUpperOneByte(src, result, &sharp_s_count);
+      }
+    }
+
+    // Go to the full Unicode path if there are characters whose uppercase
+    // is beyond the Latin-1 range (cannot be represented in OneByteString).
+    if (V8_UNLIKELY(!is_result_single_byte)) {
+      return LocaleConvertCase(s, isolate, true, "");
+    }
+
+    if (sharp_s_count == 0) return *result;
+
+    // We have sharp_s_count sharp-s characters, but the result is still
+    // in the Latin-1 range.
+    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
+        isolate, result,
+        isolate->factory()->NewRawOneByteString(length + sharp_s_count));
+    DisallowHeapAllocation no_gc;
+    String::FlatContent flat = s->GetFlatContent();
+    if (flat.IsOneByte()) {
+      ToUpperWithSharpS(flat.ToOneByteVector(), result);
+    } else {
+      ToUpperWithSharpS(flat.ToUC16Vector(), result);
+    }
+
+    return *result;
+  }
+
+  return LocaleConvertCase(s, isolate, true, "");
+}
+
+RUNTIME_FUNCTION(Runtime_StringLocaleConvertCase) {
+  HandleScope scope(isolate);
+  DCHECK_EQ(args.length(), 3);
+  CONVERT_ARG_HANDLE_CHECKED(String, s, 0);
+  CONVERT_BOOLEAN_ARG_CHECKED(is_upper, 1);
+  CONVERT_ARG_HANDLE_CHECKED(SeqOneByteString, lang, 2);
+
+  // All the languages requiring special handling ("az", "el", "lt", "tr")
+  // have a 2-letter language code.
+  DCHECK(lang->length() == 2);
+  uint8_t lang_str[3];
+  memcpy(lang_str, lang->GetChars(), 2);
+  lang_str[2] = 0;
+  s = String::Flatten(s);
+  // TODO(jshin): Consider adding a fast path for ASCII or Latin-1. The fastpath
+  // in the root locale needs to be adjusted for az, lt and tr because even case
+  // mapping of ASCII range characters are different in those locales.
+  // Greek (el) does not require any adjustment, though.
+  return LocaleConvertCase(s, isolate, is_upper,
+                           reinterpret_cast<const char*>(lang_str));
+}
+
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_I18N_SUPPORT