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