src/string-builder.h

   1 // Copyright 2014 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef V8_STRING_BUILDER_H_
   6 #define V8_STRING_BUILDER_H_
   7
   8 #include "src/objects-inl.h"
   9 #include "src/utils.h"
  10
  11 namespace v8 {
  12 namespace internal {
  13
  14 const int kStringBuilderConcatHelperLengthBits = 11;
  15 const int kStringBuilderConcatHelperPositionBits = 19;
  16
  17 typedef BitField<int, 0, kStringBuilderConcatHelperLengthBits>
  18     StringBuilderSubstringLength;
  19 typedef BitField<int, kStringBuilderConcatHelperLengthBits,
  20                  kStringBuilderConcatHelperPositionBits>
  21     StringBuilderSubstringPosition;
  22
  23
  24 template <typename sinkchar>
  25 static inline void StringBuilderConcatHelper(String* special, sinkchar* sink,
  26                                              FixedArray* fixed_array,
  27                                              int array_length) {
  28   DisallowHeapAllocation no_gc;
  29   int position = 0;
  30   for (int i = 0; i < array_length; i++) {
  31     Object* element = fixed_array->get(i);
  32     if (element->IsSmi()) {
  33       // Smi encoding of position and length.
  34       int encoded_slice = Smi::cast(element)->value();
  35       int pos;
  36       int len;
  37       if (encoded_slice > 0) {
  38         // Position and length encoded in one smi.
  39         pos = StringBuilderSubstringPosition::decode(encoded_slice);
  40         len = StringBuilderSubstringLength::decode(encoded_slice);
  41       } else {
  42         // Position and length encoded in two smis.
  43         Object* obj = fixed_array->get(++i);
  44         DCHECK(obj->IsSmi());
  45         pos = Smi::cast(obj)->value();
  46         len = -encoded_slice;
  47       }
  48       String::WriteToFlat(special, sink + position, pos, pos + len);
  49       position += len;
  50     } else {
  51       String* string = String::cast(element);
  52       int element_length = string->length();
  53       String::WriteToFlat(string, sink + position, 0, element_length);
  54       position += element_length;
  55     }
  56   }
  57 }
  58
  59
  60 // Returns the result length of the concatenation.
  61 // On illegal argument, -1 is returned.
  62 static inline int StringBuilderConcatLength(int special_length,
  63                                             FixedArray* fixed_array,
  64                                             int array_length, bool* one_byte) {
  65   DisallowHeapAllocation no_gc;
  66   int position = 0;
  67   for (int i = 0; i < array_length; i++) {
  68     int increment = 0;
  69     Object* elt = fixed_array->get(i);
  70     if (elt->IsSmi()) {
  71       // Smi encoding of position and length.
  72       int smi_value = Smi::cast(elt)->value();
  73       int pos;
  74       int len;
  75       if (smi_value > 0) {
  76         // Position and length encoded in one smi.
  77         pos = StringBuilderSubstringPosition::decode(smi_value);
  78         len = StringBuilderSubstringLength::decode(smi_value);
  79       } else {
  80         // Position and length encoded in two smis.
  81         len = -smi_value;
  82         // Get the position and check that it is a positive smi.
  83         i++;
  84         if (i >= array_length) return -1;
  85         Object* next_smi = fixed_array->get(i);
  86         if (!next_smi->IsSmi()) return -1;
  87         pos = Smi::cast(next_smi)->value();
  88         if (pos < 0) return -1;
  89       }
  90       DCHECK(pos >= 0);
  91       DCHECK(len >= 0);
  92       if (pos > special_length || len > special_length - pos) return -1;
  93       increment = len;
  94     } else if (elt->IsString()) {
  95       String* element = String::cast(elt);
  96       int element_length = element->length();
  97       increment = element_length;
  98       if (*one_byte && !element->HasOnlyOneByteChars()) {
  99         *one_byte = false;
 100       }
 101     } else {
 102       return -1;
 103     }
 104     if (increment > String::kMaxLength - position) {
 105       return kMaxInt;  // Provoke throw on allocation.
 106     }
 107     position += increment;
 108   }
 109   return position;
 110 }
 111
 112
 113 class FixedArrayBuilder {
 114  public:
 115   explicit FixedArrayBuilder(Isolate* isolate, int initial_capacity)
 116       : array_(isolate->factory()->NewFixedArrayWithHoles(initial_capacity)),
 117         length_(0),
 118         has_non_smi_elements_(false) {
 119     // Require a non-zero initial size. Ensures that doubling the size to
 120     // extend the array will work.
 121     DCHECK(initial_capacity > 0);
 122   }
 123
 124   explicit FixedArrayBuilder(Handle<FixedArray> backing_store)
 125       : array_(backing_store), length_(0), has_non_smi_elements_(false) {
 126     // Require a non-zero initial size. Ensures that doubling the size to
 127     // extend the array will work.
 128     DCHECK(backing_store->length() > 0);
 129   }
 130
 131   bool HasCapacity(int elements) {
 132     int length = array_->length();
 133     int required_length = length_ + elements;
 134     return (length >= required_length);
 135   }
 136
 137   void EnsureCapacity(int elements) {
 138     int length = array_->length();
 139     int required_length = length_ + elements;
 140     if (length < required_length) {
 141       int new_length = length;
 142       do {
 143         new_length *= 2;
 144       } while (new_length < required_length);
 145       Handle<FixedArray> extended_array =
 146           array_->GetIsolate()->factory()->NewFixedArrayWithHoles(new_length);
 147       array_->CopyTo(0, *extended_array, 0, length_);
 148       array_ = extended_array;
 149     }
 150   }
 151
 152   void Add(Object* value) {
 153     DCHECK(!value->IsSmi());
 154     DCHECK(length_ < capacity());
 155     array_->set(length_, value);
 156     length_++;
 157     has_non_smi_elements_ = true;
 158   }
 159
 160   void Add(Smi* value) {
 161     DCHECK(value->IsSmi());
 162     DCHECK(length_ < capacity());
 163     array_->set(length_, value);
 164     length_++;
 165   }
 166
 167   Handle<FixedArray> array() { return array_; }
 168
 169   int length() { return length_; }
 170
 171   int capacity() { return array_->length(); }
 172
 173   Handle<JSArray> ToJSArray(Handle<JSArray> target_array) {
 174     JSArray::SetContent(target_array, array_);
 175     target_array->set_length(Smi::FromInt(length_));
 176     return target_array;
 177   }
 178
 179
 180  private:
 181   Handle<FixedArray> array_;
 182   int length_;
 183   bool has_non_smi_elements_;
 184 };
 185
 186
 187 class ReplacementStringBuilder {
 188  public:
 189   ReplacementStringBuilder(Heap* heap, Handle<String> subject,
 190                            int estimated_part_count)
 191       : heap_(heap),
 192         array_builder_(heap->isolate(), estimated_part_count),
 193         subject_(subject),
 194         character_count_(0),
 195         is_one_byte_(subject->IsOneByteRepresentation()) {
 196     // Require a non-zero initial size. Ensures that doubling the size to
 197     // extend the array will work.
 198     DCHECK(estimated_part_count > 0);
 199   }
 200
 201   static inline void AddSubjectSlice(FixedArrayBuilder* builder, int from,
 202                                      int to) {
 203     DCHECK(from >= 0);
 204     int length = to - from;
 205     DCHECK(length > 0);
 206     if (StringBuilderSubstringLength::is_valid(length) &&
 207         StringBuilderSubstringPosition::is_valid(from)) {
 208       int encoded_slice = StringBuilderSubstringLength::encode(length) |
 209                           StringBuilderSubstringPosition::encode(from);
 210       builder->Add(Smi::FromInt(encoded_slice));
 211     } else {
 212       // Otherwise encode as two smis.
 213       builder->Add(Smi::FromInt(-length));
 214       builder->Add(Smi::FromInt(from));
 215     }
 216   }
 217
 218
 219   void EnsureCapacity(int elements) { array_builder_.EnsureCapacity(elements); }
 220
 221
 222   void AddSubjectSlice(int from, int to) {
 223     AddSubjectSlice(&array_builder_, from, to);
 224     IncrementCharacterCount(to - from);
 225   }
 226
 227
 228   void AddString(Handle<String> string) {
 229     int length = string->length();
 230     DCHECK(length > 0);
 231     AddElement(*string);
 232     if (!string->IsOneByteRepresentation()) {
 233       is_one_byte_ = false;
 234     }
 235     IncrementCharacterCount(length);
 236   }
 237
 238
 239   MaybeHandle<String> ToString();
 240
 241
 242   void IncrementCharacterCount(int by) {
 243     if (character_count_ > String::kMaxLength - by) {
 244       STATIC_ASSERT(String::kMaxLength < kMaxInt);
 245       character_count_ = kMaxInt;
 246     } else {
 247       character_count_ += by;
 248     }
 249   }
 250
 251  private:
 252   void AddElement(Object* element) {
 253     DCHECK(element->IsSmi() || element->IsString());
 254     DCHECK(array_builder_.capacity() > array_builder_.length());
 255     array_builder_.Add(element);
 256   }
 257
 258   Heap* heap_;
 259   FixedArrayBuilder array_builder_;
 260   Handle<String> subject_;
 261   int character_count_;
 262   bool is_one_byte_;
 263 };
 264
 265
 266 class IncrementalStringBuilder {
 267  public:
 268   explicit IncrementalStringBuilder(Isolate* isolate);
 269
 270   INLINE(String::Encoding CurrentEncoding()) { return encoding_; }
 271
 272   template <typename SrcChar, typename DestChar>
 273   INLINE(void Append(SrcChar c));
 274
 275   INLINE(void AppendCharacter(uint8_t c)) {
 276     if (encoding_ == String::ONE_BYTE_ENCODING) {
 277       Append<uint8_t, uint8_t>(c);
 278     } else {
 279       Append<uint8_t, uc16>(c);
 280     }
 281   }
 282
 283   INLINE(void AppendCString(const char* s)) {
 284     const uint8_t* u = reinterpret_cast<const uint8_t*>(s);
 285     if (encoding_ == String::ONE_BYTE_ENCODING) {
 286       while (*u != '\0') Append<uint8_t, uint8_t>(*(u++));
 287     } else {
 288       while (*u != '\0') Append<uint8_t, uc16>(*(u++));
 289     }
 290   }
 291
 292   INLINE(bool CurrentPartCanFit(int length)) {
 293     return part_length_ - current_index_ > length;
 294   }
 295
 296   void AppendString(Handle<String> string);
 297
 298   MaybeHandle<String> Finish();
 299
 300   // Change encoding to two-byte.
 301   void ChangeEncoding() {
 302     DCHECK_EQ(String::ONE_BYTE_ENCODING, encoding_);
 303     ShrinkCurrentPart();
 304     encoding_ = String::TWO_BYTE_ENCODING;
 305     Extend();
 306   }
 307
 308   template <typename DestChar>
 309   class NoExtend {
 310    public:
 311     explicit NoExtend(Handle<String> string, int offset) {
 312       DCHECK(string->IsSeqOneByteString() || string->IsSeqTwoByteString());
 313       if (sizeof(DestChar) == 1) {
 314         start_ = reinterpret_cast<DestChar*>(
 315             Handle<SeqOneByteString>::cast(string)->GetChars() + offset);
 316       } else {
 317         start_ = reinterpret_cast<DestChar*>(
 318             Handle<SeqTwoByteString>::cast(string)->GetChars() + offset);
 319       }
 320       cursor_ = start_;
 321     }
 322
 323     INLINE(void Append(DestChar c)) { *(cursor_++) = c; }
 324     INLINE(void AppendCString(const char* s)) {
 325       const uint8_t* u = reinterpret_cast<const uint8_t*>(s);
 326       while (*u != '\0') Append(*(u++));
 327     }
 328
 329     int written() { return static_cast<int>(cursor_ - start_); }
 330
 331    private:
 332     DestChar* start_;
 333     DestChar* cursor_;
 334     DisallowHeapAllocation no_gc_;
 335   };
 336
 337   template <typename DestChar>
 338   class NoExtendString : public NoExtend<DestChar> {
 339    public:
 340     NoExtendString(Handle<String> string, int required_length)
 341         : NoExtend<DestChar>(string, 0), string_(string) {
 342       DCHECK(string->length() >= required_length);
 343     }
 344
 345     ~NoExtendString() {
 346       Handle<SeqString> string = Handle<SeqString>::cast(string_);
 347       int length = NoExtend<DestChar>::written();
 348       *string_.location() = *SeqString::Truncate(string, length);
 349     }
 350
 351    private:
 352     Handle<String> string_;
 353   };
 354
 355   template <typename DestChar>
 356   class NoExtendBuilder : public NoExtend<DestChar> {
 357    public:
 358     NoExtendBuilder(IncrementalStringBuilder* builder, int required_length)
 359         : NoExtend<DestChar>(builder->current_part(), builder->current_index_),
 360           builder_(builder) {
 361       DCHECK(builder->CurrentPartCanFit(required_length));
 362     }
 363
 364     ~NoExtendBuilder() {
 365       builder_->current_index_ += NoExtend<DestChar>::written();
 366     }
 367
 368    private:
 369     IncrementalStringBuilder* builder_;
 370   };
 371
 372  private:
 373   Factory* factory() { return isolate_->factory(); }
 374
 375   INLINE(Handle<String> accumulator()) { return accumulator_; }
 376
 377   INLINE(void set_accumulator(Handle<String> string)) {
 378     *accumulator_.location() = *string;
 379   }
 380
 381   INLINE(Handle<String> current_part()) { return current_part_; }
 382
 383   INLINE(void set_current_part(Handle<String> string)) {
 384     *current_part_.location() = *string;
 385   }
 386
 387   // Add the current part to the accumulator.
 388   void Accumulate(Handle<String> new_part);
 389
 390   // Finish the current part and allocate a new part.
 391   void Extend();
 392
 393   // Shrink current part to the right size.
 394   void ShrinkCurrentPart() {
 395     DCHECK(current_index_ < part_length_);
 396     set_current_part(SeqString::Truncate(
 397         Handle<SeqString>::cast(current_part()), current_index_));
 398   }
 399
 400   static const int kInitialPartLength = 32;
 401   static const int kMaxPartLength = 16 * 1024;
 402   static const int kPartLengthGrowthFactor = 2;
 403
 404   Isolate* isolate_;
 405   String::Encoding encoding_;
 406   bool overflowed_;
 407   int part_length_;
 408   int current_index_;
 409   Handle<String> accumulator_;
 410   Handle<String> current_part_;
 411 };
 412
 413
 414 template <typename SrcChar, typename DestChar>
 415 void IncrementalStringBuilder::Append(SrcChar c) {
 416   DCHECK_EQ(encoding_ == String::ONE_BYTE_ENCODING, sizeof(DestChar) == 1);
 417   if (sizeof(DestChar) == 1) {
 418     DCHECK_EQ(String::ONE_BYTE_ENCODING, encoding_);
 419     SeqOneByteString::cast(*current_part_)
 420         ->SeqOneByteStringSet(current_index_++, c);
 421   } else {
 422     DCHECK_EQ(String::TWO_BYTE_ENCODING, encoding_);
 423     SeqTwoByteString::cast(*current_part_)
 424         ->SeqTwoByteStringSet(current_index_++, c);
 425   }
 426   if (current_index_ == part_length_) Extend();
 427 }
 428 }
 429 }  // namespace v8::internal
 430
 431 #endif  // V8_STRING_BUILDER_H_