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

src/objects.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 68 matching lines @@
 //           - CompilationCacheTable
 //           - CodeCacheHashTable
 //           - MapCache
 //         - Context
 //         - JSFunctionResultCache
 //         - SerializedScopeInfo
 //       - String
 //         - SeqString
 //           - SeqAsciiString
 //           - SeqTwoByteString
+//         - SlicedString
 //         - ConsString
 //         - ExternalString
 //           - ExternalAsciiString
 //           - ExternalTwoByteString
 //       - HeapNumber
 //       - Code
 //       - Map
 //       - Oddball
 //       - Foreign
 //       - SharedFunctionInfo
@@ skipping 174 matching lines @@
   V(ASCII_SYMBOL_TYPE)                                                         \
   V(CONS_SYMBOL_TYPE)                                                          \
   V(CONS_ASCII_SYMBOL_TYPE)                                                    \
   V(EXTERNAL_SYMBOL_TYPE)                                                      \
   V(EXTERNAL_SYMBOL_WITH_ASCII_DATA_TYPE)                                      \
   V(EXTERNAL_ASCII_SYMBOL_TYPE)                                                \
   V(STRING_TYPE)                                                               \
   V(ASCII_STRING_TYPE)                                                         \
   V(CONS_STRING_TYPE)                                                          \
   V(CONS_ASCII_STRING_TYPE)                                                    \
+  V(SLICED_STRING_TYPE)                                                        \
   V(EXTERNAL_STRING_TYPE)                                                      \
   V(EXTERNAL_STRING_WITH_ASCII_DATA_TYPE)                                      \
   V(EXTERNAL_ASCII_STRING_TYPE)                                                \
   V(PRIVATE_EXTERNAL_ASCII_STRING_TYPE)                                        \
                                                                                \
   V(MAP_TYPE)                                                                  \
   V(CODE_TYPE)                                                                 \
   V(ODDBALL_TYPE)                                                              \
   V(JS_GLOBAL_PROPERTY_CELL_TYPE)                                              \
                                                                                \
@@ skipping 68 matching lines @@
     ascii_symbol,                                                              \
     AsciiSymbol)                                                               \
   V(CONS_SYMBOL_TYPE,                                                          \
     ConsString::kSize,                                                         \
     cons_symbol,                                                               \
     ConsSymbol)                                                                \
   V(CONS_ASCII_SYMBOL_TYPE,                                                    \
     ConsString::kSize,                                                         \
     cons_ascii_symbol,                                                         \
     ConsAsciiSymbol)                                                           \
+  V(SLICED_SYMBOL_TYPE,                                                        \
+    SlicedString::kSize,                                                       \
+    sliced_symbol,                                                             \
+    SlicedSymbol)                                                              \
+  V(SLICED_ASCII_SYMBOL_TYPE,                                                  \
+    SlicedString::kSize,                                                       \
+    sliced_ascii_symbol,                                                       \
+    SlicedAsciiSymbol)                                                         \
   V(EXTERNAL_SYMBOL_TYPE,                                                      \
     ExternalTwoByteString::kSize,                                              \
     external_symbol,                                                           \
     ExternalSymbol)                                                            \
   V(EXTERNAL_SYMBOL_WITH_ASCII_DATA_TYPE,                                      \
     ExternalTwoByteString::kSize,                                              \
     external_symbol_with_ascii_data,                                           \
     ExternalSymbolWithAsciiData)                                               \
   V(EXTERNAL_ASCII_SYMBOL_TYPE,                                                \
     ExternalAsciiString::kSize,                                                \
     external_ascii_symbol,                                                     \
     ExternalAsciiSymbol)                                                       \
   V(STRING_TYPE,                                                               \
     kVariableSizeSentinel,                                                     \
     string,                                                                    \
     String)                                                                    \
   V(ASCII_STRING_TYPE,                                                         \
     kVariableSizeSentinel,                                                     \
     ascii_string,                                                              \
     AsciiString)                                                               \
   V(CONS_STRING_TYPE,                                                          \
     ConsString::kSize,                                                         \
     cons_string,                                                               \
     ConsString)                                                                \
   V(CONS_ASCII_STRING_TYPE,                                                    \
     ConsString::kSize,                                                         \
     cons_ascii_string,                                                         \
     ConsAsciiString)                                                           \
+  V(SLICED_STRING_TYPE,                                                        \
+    SlicedString::kSize,                                                       \
+    sliced_string,                                                             \
+    SlicedString)                                                              \
+  V(SLICED_ASCII_STRING_TYPE,                                                  \
+    SlicedString::kSize,                                                       \
+    sliced_ascii_string,                                                       \
+    SlicedAsciiString)                                                         \
   V(EXTERNAL_STRING_TYPE,                                                      \
     ExternalTwoByteString::kSize,                                              \
     external_string,                                                           \
     ExternalString)                                                            \
   V(EXTERNAL_STRING_WITH_ASCII_DATA_TYPE,                                      \
     ExternalTwoByteString::kSize,                                              \
     external_string_with_ascii_data,                                           \
     ExternalStringWithAsciiData)                                               \
   V(EXTERNAL_ASCII_STRING_TYPE,                                                \
     ExternalAsciiString::kSize,                                                \
@@ skipping 53 matching lines @@
 const uint32_t kStringEncodingMask = 0x4;
 const uint32_t kTwoByteStringTag = 0x0;
 const uint32_t kAsciiStringTag = 0x4;
 
 // If bit 7 is clear, the low-order 2 bits indicate the representation
 // of the string.
 const uint32_t kStringRepresentationMask = 0x03;
 enum StringRepresentationTag {
   kSeqStringTag = 0x0,
   kConsStringTag = 0x1,
-  kExternalStringTag = 0x2
+  kExternalStringTag = 0x2,
+  kSlicedStringTag = 0x3
 };
-const uint32_t kIsConsStringMask = 0x1;
+const uint32_t kIsIndirectStringMask = 0x1;
+const uint32_t kIsIndirectStringTag = 0x1;
+STATIC_ASSERT(
+    (kConsStringTag & kIsIndirectStringMask) == kIsIndirectStringTag);
+STATIC_ASSERT(
+    (kSlicedStringTag & kIsIndirectStringMask) == kIsIndirectStringTag);

[antonm, 2011/07/27 14:04:49]

sorry, up to you, but I would code it like:

bool is_indirect_string(SRT tag) {
  ASSERT((tag & kIISM == kIIST) == ((tag == kConstString) || (tag ==
kSlicedString));
  return tag & kIISM == kIIST;
}

And reuse it in heap.h

[Yang, 2011/07/28 15:43:06]

There is only one place where this tag is actually used. I put the assertion
there.

On 2011/07/27 14:04:49, antonm wrote:

 
 // If bit 7 is clear, then bit 3 indicates whether this two-byte
 // string actually contains ascii data.
 const uint32_t kAsciiDataHintMask = 0x08;
 const uint32_t kAsciiDataHintTag = 0x08;
 
 
 // A ConsString with an empty string as the right side is a candidate
 // for being shortcut by the garbage collector unless it is a
 // symbol. It's not common to have non-flat symbols, so we do not
 // shortcut them thereby avoiding turning symbols into strings. See
 // heap.cc and mark-compact.cc.
 const uint32_t kShortcutTypeMask =
     kIsNotStringMask |
     kIsSymbolMask |
     kStringRepresentationMask;
 const uint32_t kShortcutTypeTag = kConsStringTag;
 
 
 enum InstanceType {
   // String types.
   SYMBOL_TYPE = kTwoByteStringTag | kSymbolTag | kSeqStringTag,
   ASCII_SYMBOL_TYPE = kAsciiStringTag | kSymbolTag | kSeqStringTag,
   CONS_SYMBOL_TYPE = kTwoByteStringTag | kSymbolTag | kConsStringTag,
   CONS_ASCII_SYMBOL_TYPE = kAsciiStringTag | kSymbolTag | kConsStringTag,
+  SLICED_SYMBOL_TYPE = kTwoByteStringTag | kSymbolTag | kSlicedStringTag,

[antonm, 2011/07/27 14:04:49]

Do we want sliced symbols?

[Rico, 2011/07/28 06:49:50]

I am a little concerned about this as well, this could potentially keep strings
alive for a lot longer since these are often identifier names, e.g., if json (or
eval for that sake) is used for loading dynamic content we will keep the string
alive where the identifiers are first described potentially long after the
original objects died.

+  SLICED_ASCII_SYMBOL_TYPE = kAsciiStringTag | kSymbolTag | kSlicedStringTag,
   EXTERNAL_SYMBOL_TYPE = kTwoByteStringTag | kSymbolTag | kExternalStringTag,
   EXTERNAL_SYMBOL_WITH_ASCII_DATA_TYPE =
       kTwoByteStringTag | kSymbolTag | kExternalStringTag | kAsciiDataHintTag,
   EXTERNAL_ASCII_SYMBOL_TYPE =
       kAsciiStringTag | kSymbolTag | kExternalStringTag,
   STRING_TYPE = kTwoByteStringTag | kSeqStringTag,
   ASCII_STRING_TYPE = kAsciiStringTag | kSeqStringTag,
   CONS_STRING_TYPE = kTwoByteStringTag | kConsStringTag,
   CONS_ASCII_STRING_TYPE = kAsciiStringTag | kConsStringTag,
+  SLICED_STRING_TYPE = kTwoByteStringTag | kSlicedStringTag,
+  SLICED_ASCII_STRING_TYPE = kAsciiStringTag | kSlicedStringTag,
   EXTERNAL_STRING_TYPE = kTwoByteStringTag | kExternalStringTag,
   EXTERNAL_STRING_WITH_ASCII_DATA_TYPE =
       kTwoByteStringTag | kExternalStringTag | kAsciiDataHintTag,
   // LAST_STRING_TYPE
   EXTERNAL_ASCII_STRING_TYPE = kAsciiStringTag | kExternalStringTag,
   PRIVATE_EXTERNAL_ASCII_STRING_TYPE = EXTERNAL_ASCII_STRING_TYPE,
 
   // Objects allocated in their own spaces (never in new space).
   MAP_TYPE = kNotStringTag,  // FIRST_NONSTRING_TYPE
   CODE_TYPE,
@@ skipping 183 matching lines @@
   V(HeapObject)                                \
   V(Number)                                    \
 
 #define HEAP_OBJECT_TYPE_LIST(V)               \
   V(HeapNumber)                                \
   V(String)                                    \
   V(Symbol)                                    \
   V(SeqString)                                 \
   V(ExternalString)                            \
   V(ConsString)                                \
+  V(SlicedString)                              \
   V(ExternalTwoByteString)                     \
   V(ExternalAsciiString)                       \
   V(SeqTwoByteString)                          \
   V(SeqAsciiString)                            \
                                                \
   V(ExternalArray)                             \
   V(ExternalByteArray)                         \
   V(ExternalUnsignedByteArray)                 \
   V(ExternalShortArray)                        \
   V(ExternalUnsignedShortArray)                \
@@ skipping 4980 matching lines @@
 // prone and so we no longer put StringShapes in variables unless there is a
 // concrete performance benefit at that particular point in the code.
 class StringShape BASE_EMBEDDED {
  public:
   inline explicit StringShape(String* s);
   inline explicit StringShape(Map* s);
   inline explicit StringShape(InstanceType t);
   inline bool IsSequential();
   inline bool IsExternal();
   inline bool IsCons();
+  inline bool IsSliced();
   inline bool IsExternalAscii();
   inline bool IsExternalTwoByte();
   inline bool IsSequentialAscii();
   inline bool IsSequentialTwoByte();
   inline bool IsSymbol();
   inline StringRepresentationTag representation_tag();
   inline uint32_t full_representation_tag();
   inline uint32_t size_tag();
 #ifdef DEBUG
   inline uint32_t type() { return type_; }
@@ skipping 152 matching lines @@
 #ifdef OBJECT_PRINT
   inline void StringPrint() {
     StringPrint(stdout);
   }
   void StringPrint(FILE* out);
 #endif
 #ifdef DEBUG
   void StringVerify();
 #endif
   inline bool IsFlat();
+  inline bool IsIndirect();
 
   // Layout description.
   static const int kLengthOffset = HeapObject::kHeaderSize;
   static const int kHashFieldOffset = kLengthOffset + kPointerSize;
   static const int kSize = kHashFieldOffset + kPointerSize;
 
   // Maximum number of characters to consider when trying to convert a string
   // value into an array index.
   static const int kMaxArrayIndexSize = 10;
 
@@ skipping 327 matching lines @@
   static const int kMinLength = 13;
 
   typedef FixedBodyDescriptor<kFirstOffset, kSecondOffset + kPointerSize, kSize>
           BodyDescriptor;
 
  private:
   DISALLOW_IMPLICIT_CONSTRUCTORS(ConsString);
 };
 
 
+class SlicedString: public String {
+ public:
+
+  inline String* parent();
+  inline void set_parent(String* parent);
+  inline int offset();
+  inline void set_offset(int offset);
+
+  // Dispatched behavior.
+  uint16_t SlicedStringGet(int index);
+
+  // Casting.
+  static inline SlicedString* cast(Object* obj);
+
+  // Layout description.
+  static const int kParentOffset = POINTER_SIZE_ALIGN(String::kSize);
+  static const int kOffsetOffset = kParentOffset + kPointerSize;
+  static const int kSize = kOffsetOffset + kPointerSize;
+
+  // Support for StringInputBuffer
+  inline const unibrow::byte* SlicedStringReadBlock(ReadBlockBuffer* buffer,
+                                                    unsigned* offset_ptr,
+                                                    unsigned chars);
+  inline void SlicedStringReadBlockIntoBuffer(ReadBlockBuffer* buffer,
+                                              unsigned* offset_ptr,
+                                              unsigned chars);
+  // Minimum length for a sliced string.
+  static const int kMinLength = 13;
+
+  typedef FixedBodyDescriptor<kParentOffset,
+                              kOffsetOffset + kPointerSize, kSize>
+          BodyDescriptor;
+
+ private:
+  DISALLOW_IMPLICIT_CONSTRUCTORS(SlicedString);
+};
+
+
 // The ExternalString class describes string values that are backed by
 // a string resource that lies outside the V8 heap.  ExternalStrings
 // consist of the length field common to all strings, a pointer to the
 // external resource.  It is important to ensure (externally) that the
 // resource is not deallocated while the ExternalString is live in the
 // V8 heap.
 //
 // The API expects that all ExternalStrings are created through the
 // API.  Therefore, ExternalStrings should not be used internally.
 class ExternalString: public String {
@@ skipping 962 matching lines @@
     } else {
       value &= ~(1 << bit_position);
     }
     return value;
   }
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_H_