Tentative implementation of string slices (hidden under the flag --string-slices).

src/objects.cc

 // Copyright 2011 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 715 matching lines @@
     return true;    // An MP3File, an M.
   }
   return false;
 }
 
 
 MaybeObject* String::SlowTryFlatten(PretenureFlag pretenure) {
 #ifdef DEBUG
   // Do not attempt to flatten in debug mode when allocation is not
   // allowed.  This is to avoid an assertion failure when allocating.
-  // Flattening strings is the only case where we always allow
-  // allocation because no GC is performed if the allocation fails.
+  // Flattening and truncating strings are the only cases where we always
+  // allow allocation because no GC is performed if the allocation fails.
   if (!HEAP->IsAllocationAllowed()) return this;
 #endif
 
+  ASSERT(StringShape(this).representation_tag() == kConsStringTag);
+
   Heap* heap = GetHeap();
-  switch (StringShape(this).representation_tag()) {
-    case kConsStringTag: {
-      ConsString* cs = ConsString::cast(this);
-      if (cs->second()->length() == 0) {
-        return cs->first();
-      }
-      // There's little point in putting the flat string in new space if the
-      // cons string is in old space.  It can never get GCed until there is
-      // an old space GC.
-      PretenureFlag tenure = heap->InNewSpace(this) ? pretenure : TENURED;
-      int len = length();
-      Object* object;
-      String* result;
-      if (IsAsciiRepresentation()) {
-        { MaybeObject* maybe_object = heap->AllocateRawAsciiString(len, tenure);
-          if (!maybe_object->ToObject(&object)) return maybe_object;
-        }
-        result = String::cast(object);
-        String* first = cs->first();
-        int first_length = first->length();
-        char* dest = SeqAsciiString::cast(result)->GetChars();
-        WriteToFlat(first, dest, 0, first_length);
-        String* second = cs->second();
-        WriteToFlat(second,
-                    dest + first_length,
-                    0,
-                    len - first_length);
-      } else {
-        { MaybeObject* maybe_object =
-              heap->AllocateRawTwoByteString(len, tenure);
-          if (!maybe_object->ToObject(&object)) return maybe_object;
-        }
-        result = String::cast(object);
-        uc16* dest = SeqTwoByteString::cast(result)->GetChars();
-        String* first = cs->first();
-        int first_length = first->length();
-        WriteToFlat(first, dest, 0, first_length);
-        String* second = cs->second();
-        WriteToFlat(second,
-                    dest + first_length,
-                    0,
-                    len - first_length);
-      }
-      cs->set_first(result);
-      cs->set_second(heap->empty_string());
-      return result;
+  ConsString* cs = ConsString::cast(this);
+  // There's little point in putting the flat string in new space if the
+  // cons string is in old space.  It can never get GCed until there is
+  // an old space GC.
+  PretenureFlag tenure = heap->InNewSpace(this) ? pretenure : TENURED;
+  int len = length();
+  Object* object;
+  String* result;
+  if (IsAsciiRepresentation()) {
+    { MaybeObject* maybe_object = heap->AllocateRawAsciiString(len, tenure);
+      if (!maybe_object->ToObject(&object)) return maybe_object;
     }
-    default:
-      return this;
+    result = String::cast(object);
+    String* first = cs->first();
+    int first_length = first->length();
+    char* dest = SeqAsciiString::cast(result)->GetChars();
+    WriteToFlat(first, dest, 0, first_length);
+    String* second = cs->second();
+    WriteToFlat(second,
+                dest + first_length,
+                0,
+                len - first_length);
+  } else {
+    { MaybeObject* maybe_object =
+          heap->AllocateRawTwoByteString(len, tenure);
+      if (!maybe_object->ToObject(&object)) return maybe_object;
+    }
+    result = String::cast(object);
+    uc16* dest = SeqTwoByteString::cast(result)->GetChars();
+    String* first = cs->first();
+    int first_length = first->length();
+    WriteToFlat(first, dest, 0, first_length);
+    String* second = cs->second();
+    WriteToFlat(second,
+                dest + first_length,
+                0,
+                len - first_length);
   }
+  cs->set_first(result);
+  cs->set_second(heap->empty_string());
+  ASSERT(this->IsFlat());
+  return result;
 }
 
 
+MaybeObject* String::SlowTryTruncate(PretenureFlag pretenure) {
+#ifdef DEBUG
+  // Do not attempt to truncate in debug mode when allocation is not
+  // allowed.  This is to avoid an assertion failure when allocating.
+  // Flattening and truncating strings are the only cases where we always
+  // allow allocation because no GC is performed if the allocation fails.
+  if (!HEAP->IsAllocationAllowed()) return this;
+#endif
+  ASSERT(StringShape(this).representation_tag() == kSlicedStringTag);
+
+  Heap* heap = GetHeap();
+  SlicedString* slice = SlicedString::cast(this);
+  // There's little point in putting the truncated string in new space if the
+  // sliced string is in old space.  It can never get GCed until there is
+  // an old space GC.
+  PretenureFlag tenure = heap->InNewSpace(this) ? pretenure : TENURED;
+  int len = length();
+  int offset = slice->offset();
+  Object* object;
+  String* result;
+  if (IsAsciiRepresentation()) {
+    { MaybeObject* maybe_object = heap->AllocateRawAsciiString(len, tenure);
+      if (!maybe_object->ToObject(&object)) return maybe_object;
+    }
+    result = String::cast(object);
+    String* parent = slice->parent();
+    ASSERT(StringShape(parent).IsSequentialAscii());
+    WriteToFlat(parent, SeqAsciiString::cast(result)->GetChars(),
+                offset, offset + len);
+  } else {
+    { MaybeObject* maybe_object =
+          heap->AllocateRawTwoByteString(len, tenure);
+      if (!maybe_object->ToObject(&object)) return maybe_object;
+    }
+    result = String::cast(object);
+    String* parent = slice->parent();
+    ASSERT(StringShape(parent).IsSequentialTwoByte());
+    WriteToFlat(parent, SeqTwoByteString::cast(result)->GetChars(),
+                offset, offset + len);
+  }
+  slice->set_parent(result);
+  slice->set_offset(0);
+  return result;
+}
+
+
 bool String::MakeExternal(v8::String::ExternalStringResource* resource) {
   // Externalizing twice leaks the external resource, so it's
   // prohibited by the API.
   ASSERT(!this->IsExternalString());
 #ifdef DEBUG
   if (FLAG_enable_slow_asserts) {
     // Assert that the resource and the string are equivalent.
     ASSERT(static_cast<size_t>(this->length()) == resource->length());
     ScopedVector<uc16> smart_chars(this->length());
     String::WriteToFlat(this, smart_chars.start(), 0, this->length());
@@ skipping 357 matching lines @@
                              ObjectVisitor* v) {
   // Avoiding <Type>::cast(this) because it accesses the map pointer field.
   // During GC, the map pointer field is encoded.
   if (type < FIRST_NONSTRING_TYPE) {
     switch (type & kStringRepresentationMask) {
       case kSeqStringTag:
         break;
       case kConsStringTag:
         ConsString::BodyDescriptor::IterateBody(this, v);
         break;
+      case kSlicedStringTag:
+        SlicedString::BodyDescriptor::IterateBody(this, v);
+        break;
       case kExternalStringTag:
         if ((type & kStringEncodingMask) == kAsciiStringTag) {
           reinterpret_cast<ExternalAsciiString*>(this)->
               ExternalAsciiStringIterateBody(v);
         } else {
           reinterpret_cast<ExternalTwoByteString*>(this)->
               ExternalTwoByteStringIterateBody(v);
         }
         break;
     }
@@ skipping 4056 matching lines @@
 
   int offset = 0;
   int length = this->length();
   StringRepresentationTag string_tag = StringShape(this).representation_tag();
   String* string = this;
   if (string_tag == kConsStringTag) {
     ConsString* cons = ConsString::cast(string);
     ASSERT(cons->second()->length() == 0);
     string = cons->first();
     string_tag = StringShape(string).representation_tag();
+    ASSERT(string_tag != kConsStringTag);
   }
-  if (string_tag == kSeqStringTag) {
-    SeqAsciiString* seq = SeqAsciiString::cast(string);
-    char* start = seq->GetChars();
+  if (string_tag == kSlicedStringTag) {
+    // Note that the parent of a slice cannot be a cons.
+    SlicedString* slice = SlicedString::cast(string);
+    offset = slice->offset();
+    string = slice->parent();
+  }
+  if (string_tag == kExternalStringTag) {
+    ExternalAsciiString* ext = ExternalAsciiString::cast(string);
+    const char* start = ext->resource()->data();
     return Vector<const char>(start + offset, length);
   }
-  ASSERT(string_tag == kExternalStringTag);
-  ExternalAsciiString* ext = ExternalAsciiString::cast(string);
-  const char* start = ext->resource()->data();
+  ASSERT(StringShape(string).representation_tag() == kSeqStringTag);
+  SeqAsciiString* seq = SeqAsciiString::cast(string);
+  char* start = seq->GetChars();
   return Vector<const char>(start + offset, length);
 }
 
 
 Vector<const uc16> String::ToUC16Vector() {
   ASSERT(IsTwoByteRepresentation());
   ASSERT(IsFlat());
 
   int offset = 0;
   int length = this->length();
   StringRepresentationTag string_tag = StringShape(this).representation_tag();
   String* string = this;
   if (string_tag == kConsStringTag) {
     ConsString* cons = ConsString::cast(string);
     ASSERT(cons->second()->length() == 0);
     string = cons->first();
     string_tag = StringShape(string).representation_tag();
+    ASSERT(string_tag != kConsStringTag);
   }
-  if (string_tag == kSeqStringTag) {
-    SeqTwoByteString* seq = SeqTwoByteString::cast(string);
-    return Vector<const uc16>(seq->GetChars() + offset, length);
+  if (string_tag == kSlicedStringTag) {
+    // Note that the parent of a slice cannot be a cons.
+    SlicedString* slice = SlicedString::cast(string);
+    offset = slice->offset();
+    string = slice->parent();
   }
-  ASSERT(string_tag == kExternalStringTag);
-  ExternalTwoByteString* ext = ExternalTwoByteString::cast(string);
-  const uc16* start =
-      reinterpret_cast<const uc16*>(ext->resource()->data());
-  return Vector<const uc16>(start + offset, length);
+  if (string_tag == kExternalStringTag) {
+    ExternalTwoByteString* ext = ExternalTwoByteString::cast(string);
+    const uc16* start =
+        reinterpret_cast<const uc16*>(ext->resource()->data());
+    return Vector<const uc16>(start + offset, length);
+  }
+  ASSERT(StringShape(string).representation_tag() == kSeqStringTag);
+  SeqTwoByteString* seq = SeqTwoByteString::cast(string);
+  return Vector<const uc16>(seq->GetChars() + offset, length);
 }
 
 
 SmartPointer<char> String::ToCString(AllowNullsFlag allow_nulls,
                                      RobustnessFlag robust_flag,
                                      int offset,
                                      int length,
                                      int* length_return) {
   if (robust_flag == ROBUST_STRING_TRAVERSAL && !LooksValid()) {
     return SmartPointer<char>(NULL);
@@ skipping 57 matching lines @@
 
 
 const uc16* String::GetTwoByteData(unsigned start) {
   ASSERT(!IsAsciiRepresentation());
   switch (StringShape(this).representation_tag()) {
     case kSeqStringTag:
       return SeqTwoByteString::cast(this)->SeqTwoByteStringGetData(start);
     case kExternalStringTag:
       return ExternalTwoByteString::cast(this)->
         ExternalTwoByteStringGetData(start);
+    case kSlicedStringTag: {
+      SlicedString* slice = SlicedString::cast(this);
+      return slice->parent()->GetTwoByteData(start + slice->offset());
+    }
     case kConsStringTag:
       UNREACHABLE();
       return NULL;
   }
   UNREACHABLE();
   return NULL;
 }
 
 
 SmartPointer<uc16> String::ToWideCString(RobustnessFlag robust_flag) {
@@ skipping 270 matching lines @@
             &rbb->remaining,
             offset_ptr,
             max_chars);
       } else {
         ExternalTwoByteString::cast(input)->
             ExternalTwoByteStringReadBlockIntoBuffer(rbb,
                                                      offset_ptr,
                                                      max_chars);
         return rbb->util_buffer;
       }
+    case kSlicedStringTag:
+      return SlicedString::cast(input)->SlicedStringReadBlock(rbb,
+                                                              offset_ptr,
+                                                              max_chars);
     default:
       break;
   }
 
   UNREACHABLE();
   return 0;
 }
 
 
 void Relocatable::PostGarbageCollectionProcessing() {
@@ skipping 121 matching lines @@
       if (input->IsAsciiRepresentation()) {
         ExternalAsciiString::cast(input)->
             ExternalAsciiStringReadBlockIntoBuffer(rbb, offset_ptr, max_chars);
       } else {
         ExternalTwoByteString::cast(input)->
             ExternalTwoByteStringReadBlockIntoBuffer(rbb,
                                                      offset_ptr,
                                                      max_chars);
        }
        return;
+    case kSlicedStringTag:
+      SlicedString::cast(input)->SlicedStringReadBlockIntoBuffer(rbb,
+                                                                 offset_ptr,
+                                                                 max_chars);
+      return;
     default:
       break;
   }
 
   UNREACHABLE();
   return;
 }
 
 
 const unibrow::byte* String::ReadBlock(String* input,
@@ skipping 114 matching lines @@
     } else {
       return string->Get(index);
     }
   }
 
   UNREACHABLE();
   return 0;
 }
 
 
+uint16_t SlicedString::SlicedStringGet(int index) {
+  return parent()->Get(offset() + index);
+}
+
+
+const unibrow::byte* SlicedString::SlicedStringReadBlock(
+    ReadBlockBuffer* buffer, unsigned* offset_ptr, unsigned chars) {
+  unsigned offset = this->offset();
+  *offset_ptr += offset;
+  const unibrow::byte* answer = String::ReadBlock(String::cast(parent()),
+                                                  buffer, offset_ptr, chars);
+  *offset_ptr -= offset;
+  return answer;
+}
+
+
+void SlicedString::SlicedStringReadBlockIntoBuffer(
+    ReadBlockBuffer* buffer, unsigned* offset_ptr, unsigned chars) {
+  unsigned offset = this->offset();
+  *offset_ptr += offset;
+  String::ReadBlockIntoBuffer(String::cast(parent()),
+                              buffer, offset_ptr, chars);
+  *offset_ptr -= offset;
+}
+
 template <typename sinkchar>
 void String::WriteToFlat(String* src,
                          sinkchar* sink,
                          int f,
                          int t) {
   String* source = src;
   int from = f;
   int to = t;
   while (true) {
     ASSERT(0 <= from && from <= to && to <= source->length());
@@ skipping 47 matching lines @@
             WriteToFlat(second,
                         sink + boundary - from,
                         0,
                         to - boundary);
             to = boundary;
           }
           source = first;
         }
         break;
       }
+      case kAsciiStringTag | kSlicedStringTag:
+      case kTwoByteStringTag | kSlicedStringTag: {
+        SlicedString* slice = SlicedString::cast(source);
+        unsigned offset = slice->offset();
+        WriteToFlat(slice->parent(), sink, from + offset, to + offset);
+        return;
+      }
     }
   }
 }
 
 
 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()) {
@@ skipping 5935 matching lines @@
   if (break_point_objects()->IsUndefined()) return 0;
   // Single beak point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif
 
 
 } }  // namespace v8::internal