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

src/objects-inl.h

 // 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 159 matching lines @@
   // Because the symbol tag is non-zero and no non-string types have the
   // symbol bit set we can test for symbols with a very simple test
   // operation.
   ASSERT(kSymbolTag != 0);
   ASSERT(kNotStringTag + kIsSymbolMask > LAST_TYPE);
   return (type & kIsSymbolMask) != 0;
 }
 
 
 bool Object::IsConsString() {
-  if (!this->IsHeapObject()) return false;
-  uint32_t type = HeapObject::cast(this)->map()->instance_type();
-  return (type & (kIsNotStringMask | kStringRepresentationMask)) ==
-         (kStringTag | kConsStringTag);
+  if (!IsString()) return false;
+  return StringShape(String::cast(this)).IsCons();
 }
 
 
+bool Object::IsSlicedString() {
+  if (!IsString()) return false;
+  return StringShape(String::cast(this)).IsSliced();
+}
+
+
 bool Object::IsSeqString() {
   if (!IsString()) return false;
   return StringShape(String::cast(this)).IsSequential();
 }
 
 
 bool Object::IsSeqAsciiString() {
   if (!IsString()) return false;
   return StringShape(String::cast(this)).IsSequential() &&
          String::cast(this)->IsAsciiRepresentation();
@@ skipping 76 matching lines @@
   return (type & kStringEncodingMask) == kAsciiStringTag ||
          (type & kAsciiDataHintMask) == kAsciiDataHintTag;
 }
 
 
 bool StringShape::IsCons() {
   return (type_ & kStringRepresentationMask) == kConsStringTag;
 }
 
 
+bool StringShape::IsSliced() {
+  return (type_ & kStringRepresentationMask) == kSlicedStringTag;
+}
+
+
+bool StringShape::IsIndirect() {
+  ASSERT(((type_ & kIsIndirectStringMask) == kIsIndirectStringTag)
+      == (((type_ & kStringRepresentationMask) == kConsStringTag)
+      || ((type_ & kStringRepresentationMask) == kSlicedStringTag)));

[antonm, 2011/08/04 12:18:48]

Isn't it similar to change to Heap::TargetSpaceId?

+  return (type_ & kIsIndirectStringMask) == kIsIndirectStringTag;
+}

[Yang, 2011/08/04 09:19:53]

Being 'indirect' means either cons or slice. Accessing the first part of a
flattened cons or the parent of a truncated slice goes to the same offset, so
there is no point making a distinction here.

+
+
 bool StringShape::IsExternal() {
   return (type_ & kStringRepresentationMask) == kExternalStringTag;
 }
 
 
 bool StringShape::IsSequential() {
   return (type_ & kStringRepresentationMask) == kSeqStringTag;
 }
 
 
@@ skipping 1741 matching lines @@
 CAST_ACCESSOR(JSFunctionResultCache)
 CAST_ACCESSOR(NormalizedMapCache)
 CAST_ACCESSOR(CompilationCacheTable)
 CAST_ACCESSOR(CodeCacheHashTable)
 CAST_ACCESSOR(PolymorphicCodeCacheHashTable)
 CAST_ACCESSOR(MapCache)
 CAST_ACCESSOR(String)
 CAST_ACCESSOR(SeqString)
 CAST_ACCESSOR(SeqAsciiString)
 CAST_ACCESSOR(SeqTwoByteString)
+CAST_ACCESSOR(SlicedString)
 CAST_ACCESSOR(ConsString)
 CAST_ACCESSOR(ExternalString)
 CAST_ACCESSOR(ExternalAsciiString)
 CAST_ACCESSOR(ExternalTwoByteString)
 CAST_ACCESSOR(JSReceiver)
 CAST_ACCESSOR(JSObject)
 CAST_ACCESSOR(Smi)
 CAST_ACCESSOR(HeapObject)
 CAST_ACCESSOR(HeapNumber)
 CAST_ACCESSOR(Oddball)
@@ skipping 66 matching lines @@
   if (StringShape(this).IsSymbol() && StringShape(other).IsSymbol()) {
     return false;
   }
   return SlowEquals(other);
 }
 
 
 MaybeObject* String::TryFlatten(PretenureFlag pretenure) {
   if (!StringShape(this).IsCons()) return this;
   ConsString* cons = ConsString::cast(this);
-  if (cons->second()->length() == 0) return cons->first();
+  if (cons->IsFlat()) return cons->first();
   return SlowTryFlatten(pretenure);
 }
 
 
 String* String::TryFlattenGetString(PretenureFlag pretenure) {
   MaybeObject* flat = TryFlatten(pretenure);
   Object* successfully_flattened;
-  if (flat->ToObject(&successfully_flattened)) {
-    return String::cast(successfully_flattened);
-  }
-  return this;
+  if (!flat->ToObject(&successfully_flattened)) return this;
+  return String::cast(successfully_flattened);
 }
 
 
+MaybeObject* String::TryTruncate(PretenureFlag pretenure) {
+  if (!StringShape(this).IsSliced()) return this;
+  SlicedString* slice = SlicedString::cast(this);
+  if (slice->IsTruncated()) return slice->parent();
+  return SlowTryTruncate(pretenure);
+}
+
+
+String* String::TryTruncateGetString(PretenureFlag pretenure) {
+  MaybeObject* truncate = TryTruncate(pretenure);
+  Object* successfully_truncated;
+  if (!truncate->ToObject(&successfully_truncated)) return this;
+  return String::cast(successfully_truncated);
+}
+
+
+MaybeObject* String::TryFlattenOrTruncate(PretenureFlag pretenure) {
+  switch (StringShape(this).representation_tag()) {
+    case kSlicedStringTag: {
+      SlicedString* slice = SlicedString::cast(this);
+      if (slice->IsTruncated()) return slice->parent();
+      return SlowTryTruncate(pretenure);
+    }
+    case kConsStringTag: {
+      ConsString* cons = ConsString::cast(this);
+      if (cons->IsFlat()) return cons->first();
+      return SlowTryFlatten(pretenure);
+    }
+    default:
+      return this;
+  }
+}
+
+
 uint16_t String::Get(int index) {
   ASSERT(index >= 0 && index < length());
   switch (StringShape(this).full_representation_tag()) {
     case kSeqStringTag | kAsciiStringTag:
       return SeqAsciiString::cast(this)->SeqAsciiStringGet(index);
     case kSeqStringTag | kTwoByteStringTag:
       return SeqTwoByteString::cast(this)->SeqTwoByteStringGet(index);
     case kConsStringTag | kAsciiStringTag:
     case kConsStringTag | kTwoByteStringTag:
       return ConsString::cast(this)->ConsStringGet(index);
     case kExternalStringTag | kAsciiStringTag:
       return ExternalAsciiString::cast(this)->ExternalAsciiStringGet(index);
     case kExternalStringTag | kTwoByteStringTag:
       return ExternalTwoByteString::cast(this)->ExternalTwoByteStringGet(index);
+    case kSlicedStringTag | kAsciiStringTag:
+    case kSlicedStringTag | kTwoByteStringTag:
+      return SlicedString::cast(this)->SlicedStringGet(index);
     default:
       break;
   }
 
   UNREACHABLE();
   return 0;
 }
 
 
 void String::Set(int index, uint16_t value) {
   ASSERT(index >= 0 && index < length());
   ASSERT(StringShape(this).IsSequential());
 
   return this->IsAsciiRepresentation()
       ? SeqAsciiString::cast(this)->SeqAsciiStringSet(index, value)
       : SeqTwoByteString::cast(this)->SeqTwoByteStringSet(index, value);
 }
 
 
 bool String::IsFlat() {
+  if (!StringShape(this).IsCons()) return true;
+  return ConsString::cast(this)->second() == GetHeap()->empty_string();
+}
+
+
+bool String::IsTruncated() {
+  if (!StringShape(this).IsSliced()) return true;
+  SlicedString* slice = SlicedString::cast(this);
+  return slice->parent()->length() == slice->length();
+}
+
+
+bool String::IsFlatAndTruncated() {
   switch (StringShape(this).representation_tag()) {
-    case kConsStringTag: {
-      String* second = ConsString::cast(this)->second();
-      // Only flattened strings have second part empty.
-      return second->length() == 0;
+    case kSlicedStringTag: {
+      SlicedString* slice = SlicedString::cast(this);
+      return slice->parent()->length() == slice->length();
     }
+    case kConsStringTag:
+      return ConsString::cast(this)->second() == GetHeap()->empty_string();
     default:
       return true;
   }
 }
 
 
+String* String::GetIndirect() {
+  STATIC_ASSERT(ConsString::kFirstOffset == SlicedString::kParentOffset);
+  ASSERT(this->IsFlat());
+  ASSERT(this->IsTruncated());
+  ASSERT(StringShape(this).IsIndirect());
+  return String::cast(reinterpret_cast<ConsString*>(this)->first());
+}
+
+
 uint16_t SeqAsciiString::SeqAsciiStringGet(int index) {
   ASSERT(index >= 0 && index < length());
   return READ_BYTE_FIELD(this, kHeaderSize + index * kCharSize);
 }
 
 
 void SeqAsciiString::SeqAsciiStringSet(int index, uint16_t value) {
   ASSERT(index >= 0 && index < length() && value <= kMaxAsciiCharCode);
   WRITE_BYTE_FIELD(this, kHeaderSize + index * kCharSize,
                    static_cast<byte>(value));
@@ skipping 35 matching lines @@
 int SeqTwoByteString::SeqTwoByteStringSize(InstanceType instance_type) {
   return SizeFor(length());
 }
 
 
 int SeqAsciiString::SeqAsciiStringSize(InstanceType instance_type) {
   return SizeFor(length());
 }
 
 
+String* SlicedString::parent() {
+  return String::cast(READ_FIELD(this, kParentOffset));
+}
+
+
+void SlicedString::set_parent(String* parent) {
+  ASSERT(parent->IsSeqString());
+  WRITE_FIELD(this, kParentOffset, parent);
+}
+
+
+SMI_ACCESSORS(SlicedString, offset, kOffsetOffset)
+
+
 String* ConsString::first() {
   return String::cast(READ_FIELD(this, kFirstOffset));
 }
 
 
 Object* ConsString::unchecked_first() {
   return READ_FIELD(this, kFirstOffset);
 }
 
 
@@ skipping 2255 matching lines @@
 #undef WRITE_INT_FIELD
 #undef READ_SHORT_FIELD
 #undef WRITE_SHORT_FIELD
 #undef READ_BYTE_FIELD
 #undef WRITE_BYTE_FIELD
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_INL_H_