Fix input and output to handle UTF16 surrogate pairs.

src/objects.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 6025 matching lines @@
 
   // Negative length means the to the end of the string.
   if (length < 0) length = kMaxInt - offset;
 
   // Compute the size of the UTF-8 string. Start at the specified offset.
   Access<StringInputBuffer> buffer(
       heap->isolate()->objects_string_input_buffer());
   buffer->Reset(offset, this);
   int character_position = offset;
   int utf8_bytes = 0;
+  int last = unibrow::Utf8::kNoPreviousCharacter;
   while (buffer->has_more() && character_position++ < offset + length) {
     uint16_t character = buffer->GetNext();
-    utf8_bytes += unibrow::Utf8::Length(character);
+    utf8_bytes += unibrow::Utf8::Length(character, last);
+    last = character;
   }
 
   if (length_return) {
     *length_return = utf8_bytes;
   }
 
   char* result = NewArray<char>(utf8_bytes + 1);
 
   // Convert the UTF-16 string to a UTF-8 buffer. Start at the specified offset.
   buffer->Rewind();
   buffer->Seek(offset);
   character_position = offset;
   int utf8_byte_position = 0;
+  last = unibrow::Utf8::kNoPreviousCharacter;
   while (buffer->has_more() && character_position++ < offset + length) {
     uint16_t character = buffer->GetNext();
     if (allow_nulls == DISALLOW_NULLS && character == 0) {
       character = ' ';
     }
     utf8_byte_position +=
-        unibrow::Utf8::Encode(result + utf8_byte_position, character);
+        unibrow::Utf8::Encode(result + utf8_byte_position, character, last);
+    last = character;
   }
   result[utf8_byte_position] = 0;
   return SmartArrayPointer<char>(result);
 }
 
 
 SmartArrayPointer<char> String::ToCString(AllowNullsFlag allow_nulls,
                                           RobustnessFlag robust_flag,
                                           int* length_return) {
   return ToCString(allow_nulls, robust_flag, 0, -1, length_return);
@@ skipping 295 matching lines @@
       break;
   }
 
   UNREACHABLE();
   return 0;
 }
 
 
 // This method determines the type of string involved and then gets the UTF8
 // length of the string.  It doesn't flatten the string and has log(n) recursion
-// for a string of length n.
-int String::Utf8Length(String* input, int from, int to) {
+// for a string of length n.  If the failure flag gets set, then we have to
+// flatten the string and retry.  Failures are caused by surrogate pairs in deep

[rossberg, 2012/03/07 13:32:47]

Not sure I understand the failure mode. Why does the function need to fail on
these, and not on other recursions?

[Erik Corry, 2012/03/11 19:29:22]

The old version of this function was constructed as follows:

To get the UTF-8 length of a cons script, recurse on both the car and the cdr
and add the lengths.  But since we don't want arbitrary recursion that will
overflow the stack, we manually transform, the algorithm:
1) Introduce an accumulator for the length
2) Recurse first on the short side (the one with <= half of the characters).
3) The recursion on the other side is now a tail call, which we can manually
eliminate, turning it into an iteration.

This way, the recursion depth cannot exceed log2 of the length and all is good. 
WriteToFlat uses the same idea.

But now with UTF-16 we have a new case to consider.  The car may end in a lead
surrogate and the cdr may start with a trail surrogate.  Together they make a
surrogate pair, which is coded as 4 bytes of UTF-8, instead of two 3-byte
encodings (one for each surrogate).    This is easy to code as recursion, but if
we always recurse on the short one first, I wasn't able to see how to make it
into a tail call and transform the second one into iteration.  If we always
recurse on one (I chose the cdr) then it is still possible to do the
transformation.

So the new version always recurses on the cdr and iterates on the car.  This
works for most strings, but we can recurse too deeply, in which case we have to
bail out, flatten the string and start over.  Since these strings are often
build-then-use-once-then-discard strings that is a waste.  Currently WriteUTF
flattens them, but there are ways to avoid that in another CL (eg writing them
backwards normally works because cons strings are almost always unbalanced in
the same direction).

+// cons strings.
+int String::Utf8Length(String* input,
+                       int from,
+                       int to,
+                       bool followed_by_surrogate,
+                       int max_recursion,
+                       bool* failure,
+                       bool* starts_with_surrogate) {
   if (from == to) return 0;
   int total = 0;
+  bool dummy;
   while (true) {
-    if (input->IsAsciiRepresentation()) return total + to - from;
+    if (input->IsAsciiRepresentation()) {
+      *starts_with_surrogate = false;
+      return total + to - from;
+    }
     switch (StringShape(input).representation_tag()) {
       case kConsStringTag: {
         ConsString* str = ConsString::cast(input);
         String* first = str->first();
         String* second = str->second();
         int first_length = first->length();
-        if (first_length - from < to - first_length) {
-          if (first_length > from) {
-            // Left hand side is shorter.
-            total += Utf8Length(first, from, first_length);
-            input = second;
-            from = 0;
-            to -= first_length;
-          } else {
-            // We only need the right hand side.
-            input = second;
-            from -= first_length;
-            to -= first_length;
-          }
-        } else {
-          if (first_length <= to) {
+        if (first_length - from > to - first_length) {
+          if (first_length < to) {
             // Right hand side is shorter.
-            total += Utf8Length(second, 0, to - first_length);
+            bool right_starts_with_surrogate = false;
+            total += Utf8Length(second,
+                                0,
+                                to - first_length,
+                                followed_by_surrogate,
+                                max_recursion - 1,
+                                failure,
+                                &right_starts_with_surrogate);
+            if (*failure) return 0;
+            followed_by_surrogate = right_starts_with_surrogate;
             input = first;
             to = first_length;
           } else {
             // We only need the left hand side.
             input = first;
           }
+        } else {
+          if (first_length > from) {
+            // Left hand side is shorter.
+            if (first->IsAsciiRepresentation()) {
+              total += first_length - from;
+              *starts_with_surrogate = false;
+              starts_with_surrogate = &dummy;
+              input = second;
+              from = 0;
+              to -= first_length;
+            } else if (second->IsAsciiRepresentation()) {
+              followed_by_surrogate = false;
+              total += to - first_length;
+              input = first;
+              to = first_length;
+            } else if (max_recursion > 0) {

[rossberg, 2012/03/07 13:32:47]

Why is this the only recursive path actually checking max_recursion?

[Erik Corry, 2012/03/11 19:29:22]

See above.

+              bool right_starts_with_surrogate = false;
+              // Recursing on the long one.  This may fail.
+              total += Utf8Length(second,
+                                  0,
+                                  to - first_length,
+                                  followed_by_surrogate,
+                                  max_recursion - 1,
+                                  failure,
+                                  &right_starts_with_surrogate);
+              if (*failure) return 0;
+              input = first;
+              to = first_length;
+              followed_by_surrogate = right_starts_with_surrogate;
+            } else {
+              *failure = true;
+              return 0;
+            }
+          } else {
+            // We only need the right hand side.
+            input = second;
+            from = 0;
+            to -= first_length;
+          }
         }
         continue;
       }
       case kExternalStringTag:
       case kSeqStringTag: {
         Vector<const uc16> vector = input->GetFlatContent().ToUC16Vector();
         const uc16* p = vector.start();
+        int previous = unibrow::Utf8::kNoPreviousCharacter;
         for (int i = from; i < to; i++) {
-          total += unibrow::Utf8::Length(p[i]);
+          uc16 c = p[i];
+          total += unibrow::Utf8::Length(c, previous);
+          previous = c;
+        }
+        if (to - from > 0) {
+          if (unibrow::Utf16::IsLeadSurrogate(previous) &&
+              followed_by_surrogate) {
+            total -= 2;

[rossberg, 2012/03/07 13:32:47]

I wouldn't mind a comment here, why -2? Is that kSizeOfUnmatchedSurrogate-1?

[Erik Corry, 2012/03/11 19:29:22]

No, it's kBytesSavedByCombiningSurrogates.  Fixed.

+          }
+          if (unibrow::Utf16::IsTrailSurrogate(p[from])) {
+            *starts_with_surrogate = true;
+          }
         }
         return total;
       }
       case kSlicedStringTag: {
         SlicedString* str = SlicedString::cast(input);
         int offset = str->offset();
         input = str->parent();
         from += offset;
         to += offset;
         continue;
@@ skipping 394 matching lines @@
     }
   }
 }
 
 
 template <typename IteratorA, typename IteratorB>
 static inline bool CompareStringContents(IteratorA* ia, IteratorB* ib) {
   // General slow case check.  We know that the ia and ib iterators
   // have the same length.
   while (ia->has_more()) {
-    uc32 ca = ia->GetNext();
-    uc32 cb = ib->GetNext();
+    uint32_t ca = ia->GetNext();
+    uint32_t cb = ib->GetNext();
+    ASSERT(ca <= unibrow::Utf16::kMaxNonSurrogateCharCode);
+    ASSERT(cb <= unibrow::Utf16::kMaxNonSurrogateCharCode);
     if (ca != cb)
       return false;
   }
   return true;
 }
 
 
 // Compares the contents of two strings by reading and comparing
 // int-sized blocks of characters.
 template <typename Char>
@@ skipping 162 matching lines @@
 
 
 bool String::IsEqualTo(Vector<const char> str) {
   Isolate* isolate = GetIsolate();
   int slen = length();
   Access<UnicodeCache::Utf8Decoder>
       decoder(isolate->unicode_cache()->utf8_decoder());
   decoder->Reset(str.start(), str.length());
   int i;
   for (i = 0; i < slen && decoder->has_more(); i++) {
-    uc32 r = decoder->GetNext();
-    if (Get(i) != r) return false;
+    uint32_t r = decoder->GetNext();
+    if (r > unibrow::Utf16::kMaxNonSurrogateCharCode) {
+      if (i > slen - 1) return false;
+      if (Get(i++) != unibrow::Utf16::LeadSurrogate(r)) return false;
+      if (Get(i) != unibrow::Utf16::TrailSurrogate(r)) return false;
+    } else {
+      if (Get(i) != r) return false;
+    }
   }
   return i == slen && !decoder->has_more();
 }
 
 
 bool String::IsAsciiEqualTo(Vector<const char> str) {
   int slen = length();
   if (str.length() != slen) return false;
   FlatContent content = GetFlatContent();
   if (content.IsAscii()) {
@@ skipping 109 matching lines @@
   value <<= String::kHashShift;
   value |= length << String::kArrayIndexHashLengthShift;
 
   ASSERT((value & String::kIsNotArrayIndexMask) == 0);
   ASSERT((length > String::kMaxCachedArrayIndexLength) ||
          (value & String::kContainsCachedArrayIndexMask) == 0);
   return value;
 }
 
 
+void StringHasher::AddSurrogatePair(uc32 c) {
+  uint16_t lead = unibrow::Utf16::LeadSurrogate(c);
+  AddCharacter(lead);
+  uint16_t trail = unibrow::Utf16::TrailSurrogate(c);
+  AddCharacter(trail);
+}
+
+
+void StringHasher::AddSurrogatePairNoIndex(uc32 c) {
+  uint16_t lead = unibrow::Utf16::LeadSurrogate(c);
+  AddCharacterNoIndex(lead);
+  uint16_t trail = unibrow::Utf16::TrailSurrogate(c);
+  AddCharacterNoIndex(trail);
+}
+
+
 uint32_t StringHasher::GetHashField() {
   ASSERT(is_valid());
   if (length_ <= String::kMaxHashCalcLength) {
     if (is_array_index()) {
       return MakeArrayIndexHash(array_index(), length_);
     }
     return (GetHash() << String::kHashShift) | String::kIsNotArrayIndexMask;
   } else {
     return (length_ << String::kHashShift) | String::kIsNotArrayIndexMask;
   }
@@ skipping 3572 matching lines @@
       : string_(string), hash_field_(0), seed_(seed) { }
 
   bool IsMatch(Object* string) {
     return String::cast(string)->IsEqualTo(string_);
   }
 
   uint32_t Hash() {
     if (hash_field_ != 0) return hash_field_ >> String::kHashShift;
     unibrow::Utf8InputBuffer<> buffer(string_.start(),
                                       static_cast<unsigned>(string_.length()));
-    chars_ = buffer.Length();
+    chars_ = buffer.Utf16Length();
     hash_field_ = String::ComputeHashField(&buffer, chars_, seed_);
     uint32_t result = hash_field_ >> String::kHashShift;
     ASSERT(result != 0);  // Ensure that the hash value of 0 is never computed.
     return result;
   }
 
   uint32_t HashForObject(Object* other) {
     return String::cast(other)->Hash();
   }
 
@@ skipping 2197 matching lines @@
   if (break_point_objects()->IsUndefined()) return 0;
   // Single break point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif  // ENABLE_DEBUGGER_SUPPORT
 
 
 } }  // namespace v8::internal