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.
5 #ifndef V8_STRING_BUILDER_H_
6 #define V8_STRING_BUILDER_H_
8 #include "src/assert-scope.h"
9 #include "src/factory.h"
10 #include "src/handles.h"
11 #include "src/isolate.h"
12 #include "src/objects.h"
13 #include "src/utils.h"
18 const int kStringBuilderConcatHelperLengthBits = 11;
19 const int kStringBuilderConcatHelperPositionBits = 19;
21 typedef BitField<int, 0, kStringBuilderConcatHelperLengthBits>
22 StringBuilderSubstringLength;
23 typedef BitField<int, kStringBuilderConcatHelperLengthBits,
24 kStringBuilderConcatHelperPositionBits>
25 StringBuilderSubstringPosition;
28 template <typename sinkchar>
29 static inline void StringBuilderConcatHelper(String* special, sinkchar* sink,
30 FixedArray* fixed_array,
32 DisallowHeapAllocation no_gc;
34 for (int i = 0; i < array_length; i++) {
35 Object* element = fixed_array->get(i);
36 if (element->IsSmi()) {
37 // Smi encoding of position and length.
38 int encoded_slice = Smi::cast(element)->value();
41 if (encoded_slice > 0) {
42 // Position and length encoded in one smi.
43 pos = StringBuilderSubstringPosition::decode(encoded_slice);
44 len = StringBuilderSubstringLength::decode(encoded_slice);
46 // Position and length encoded in two smis.
47 Object* obj = fixed_array->get(++i);
49 pos = Smi::cast(obj)->value();
52 String::WriteToFlat(special, sink + position, pos, pos + len);
55 String* string = String::cast(element);
56 int element_length = string->length();
57 String::WriteToFlat(string, sink + position, 0, element_length);
58 position += element_length;
64 // Returns the result length of the concatenation.
65 // On illegal argument, -1 is returned.
66 static inline int StringBuilderConcatLength(int special_length,
67 FixedArray* fixed_array,
68 int array_length, bool* one_byte) {
69 DisallowHeapAllocation no_gc;
71 for (int i = 0; i < array_length; i++) {
73 Object* elt = fixed_array->get(i);
75 // Smi encoding of position and length.
76 int smi_value = Smi::cast(elt)->value();
80 // Position and length encoded in one smi.
81 pos = StringBuilderSubstringPosition::decode(smi_value);
82 len = StringBuilderSubstringLength::decode(smi_value);
84 // Position and length encoded in two smis.
86 // Get the position and check that it is a positive smi.
88 if (i >= array_length) return -1;
89 Object* next_smi = fixed_array->get(i);
90 if (!next_smi->IsSmi()) return -1;
91 pos = Smi::cast(next_smi)->value();
92 if (pos < 0) return -1;
96 if (pos > special_length || len > special_length - pos) return -1;
98 } else if (elt->IsString()) {
99 String* element = String::cast(elt);
100 int element_length = element->length();
101 increment = element_length;
102 if (*one_byte && !element->HasOnlyOneByteChars()) {
108 if (increment > String::kMaxLength - position) {
109 return kMaxInt; // Provoke throw on allocation.
111 position += increment;
117 class FixedArrayBuilder {
119 explicit FixedArrayBuilder(Isolate* isolate, int initial_capacity)
120 : array_(isolate->factory()->NewFixedArrayWithHoles(initial_capacity)),
122 has_non_smi_elements_(false) {
123 // Require a non-zero initial size. Ensures that doubling the size to
124 // extend the array will work.
125 DCHECK(initial_capacity > 0);
128 explicit FixedArrayBuilder(Handle<FixedArray> backing_store)
129 : array_(backing_store), length_(0), has_non_smi_elements_(false) {
130 // Require a non-zero initial size. Ensures that doubling the size to
131 // extend the array will work.
132 DCHECK(backing_store->length() > 0);
135 bool HasCapacity(int elements) {
136 int length = array_->length();
137 int required_length = length_ + elements;
138 return (length >= required_length);
141 void EnsureCapacity(int elements) {
142 int length = array_->length();
143 int required_length = length_ + elements;
144 if (length < required_length) {
145 int new_length = length;
148 } while (new_length < required_length);
149 Handle<FixedArray> extended_array =
150 array_->GetIsolate()->factory()->NewFixedArrayWithHoles(new_length);
151 array_->CopyTo(0, *extended_array, 0, length_);
152 array_ = extended_array;
156 void Add(Object* value) {
157 DCHECK(!value->IsSmi());
158 DCHECK(length_ < capacity());
159 array_->set(length_, value);
161 has_non_smi_elements_ = true;
164 void Add(Smi* value) {
165 DCHECK(value->IsSmi());
166 DCHECK(length_ < capacity());
167 array_->set(length_, value);
171 Handle<FixedArray> array() { return array_; }
173 int length() { return length_; }
175 int capacity() { return array_->length(); }
177 Handle<JSArray> ToJSArray(Handle<JSArray> target_array) {
178 JSArray::SetContent(target_array, array_);
179 target_array->set_length(Smi::FromInt(length_));
185 Handle<FixedArray> array_;
187 bool has_non_smi_elements_;
191 class ReplacementStringBuilder {
193 ReplacementStringBuilder(Heap* heap, Handle<String> subject,
194 int estimated_part_count)
196 array_builder_(heap->isolate(), estimated_part_count),
199 is_one_byte_(subject->IsOneByteRepresentation()) {
200 // Require a non-zero initial size. Ensures that doubling the size to
201 // extend the array will work.
202 DCHECK(estimated_part_count > 0);
205 static inline void AddSubjectSlice(FixedArrayBuilder* builder, int from,
208 int length = to - from;
210 if (StringBuilderSubstringLength::is_valid(length) &&
211 StringBuilderSubstringPosition::is_valid(from)) {
212 int encoded_slice = StringBuilderSubstringLength::encode(length) |
213 StringBuilderSubstringPosition::encode(from);
214 builder->Add(Smi::FromInt(encoded_slice));
216 // Otherwise encode as two smis.
217 builder->Add(Smi::FromInt(-length));
218 builder->Add(Smi::FromInt(from));
223 void EnsureCapacity(int elements) { array_builder_.EnsureCapacity(elements); }
226 void AddSubjectSlice(int from, int to) {
227 AddSubjectSlice(&array_builder_, from, to);
228 IncrementCharacterCount(to - from);
232 void AddString(Handle<String> string) {
233 int length = string->length();
236 if (!string->IsOneByteRepresentation()) {
237 is_one_byte_ = false;
239 IncrementCharacterCount(length);
243 MaybeHandle<String> ToString();
246 void IncrementCharacterCount(int by) {
247 if (character_count_ > String::kMaxLength - by) {
248 STATIC_ASSERT(String::kMaxLength < kMaxInt);
249 character_count_ = kMaxInt;
251 character_count_ += by;
256 void AddElement(Object* element) {
257 DCHECK(element->IsSmi() || element->IsString());
258 DCHECK(array_builder_.capacity() > array_builder_.length());
259 array_builder_.Add(element);
263 FixedArrayBuilder array_builder_;
264 Handle<String> subject_;
265 int character_count_;
270 class IncrementalStringBuilder {
272 explicit IncrementalStringBuilder(Isolate* isolate);
274 INLINE(String::Encoding CurrentEncoding()) { return encoding_; }
276 template <typename SrcChar, typename DestChar>
277 INLINE(void Append(SrcChar c));
279 INLINE(void AppendCharacter(uint8_t c)) {
280 if (encoding_ == String::ONE_BYTE_ENCODING) {
281 Append<uint8_t, uint8_t>(c);
283 Append<uint8_t, uc16>(c);
287 INLINE(void AppendCString(const char* s)) {
288 const uint8_t* u = reinterpret_cast<const uint8_t*>(s);
289 if (encoding_ == String::ONE_BYTE_ENCODING) {
290 while (*u != '\0') Append<uint8_t, uint8_t>(*(u++));
292 while (*u != '\0') Append<uint8_t, uc16>(*(u++));
296 INLINE(bool CurrentPartCanFit(int length)) {
297 return part_length_ - current_index_ > length;
300 void AppendString(Handle<String> string);
302 MaybeHandle<String> Finish();
304 // Change encoding to two-byte.
305 void ChangeEncoding() {
306 DCHECK_EQ(String::ONE_BYTE_ENCODING, encoding_);
308 encoding_ = String::TWO_BYTE_ENCODING;
312 template <typename DestChar>
315 explicit NoExtend(Handle<String> string, int offset) {
316 DCHECK(string->IsSeqOneByteString() || string->IsSeqTwoByteString());
317 if (sizeof(DestChar) == 1) {
318 start_ = reinterpret_cast<DestChar*>(
319 Handle<SeqOneByteString>::cast(string)->GetChars() + offset);
321 start_ = reinterpret_cast<DestChar*>(
322 Handle<SeqTwoByteString>::cast(string)->GetChars() + offset);
327 INLINE(void Append(DestChar c)) { *(cursor_++) = c; }
328 INLINE(void AppendCString(const char* s)) {
329 const uint8_t* u = reinterpret_cast<const uint8_t*>(s);
330 while (*u != '\0') Append(*(u++));
333 int written() { return static_cast<int>(cursor_ - start_); }
338 DisallowHeapAllocation no_gc_;
341 template <typename DestChar>
342 class NoExtendString : public NoExtend<DestChar> {
344 NoExtendString(Handle<String> string, int required_length)
345 : NoExtend<DestChar>(string, 0), string_(string) {
346 DCHECK(string->length() >= required_length);
350 Handle<SeqString> string = Handle<SeqString>::cast(string_);
351 int length = NoExtend<DestChar>::written();
352 *string_.location() = *SeqString::Truncate(string, length);
356 Handle<String> string_;
359 template <typename DestChar>
360 class NoExtendBuilder : public NoExtend<DestChar> {
362 NoExtendBuilder(IncrementalStringBuilder* builder, int required_length)
363 : NoExtend<DestChar>(builder->current_part(), builder->current_index_),
365 DCHECK(builder->CurrentPartCanFit(required_length));
369 builder_->current_index_ += NoExtend<DestChar>::written();
373 IncrementalStringBuilder* builder_;
377 Factory* factory() { return isolate_->factory(); }
379 INLINE(Handle<String> accumulator()) { return accumulator_; }
381 INLINE(void set_accumulator(Handle<String> string)) {
382 *accumulator_.location() = *string;
385 INLINE(Handle<String> current_part()) { return current_part_; }
387 INLINE(void set_current_part(Handle<String> string)) {
388 *current_part_.location() = *string;
391 // Add the current part to the accumulator.
392 void Accumulate(Handle<String> new_part);
394 // Finish the current part and allocate a new part.
397 // Shrink current part to the right size.
398 void ShrinkCurrentPart() {
399 DCHECK(current_index_ < part_length_);
400 set_current_part(SeqString::Truncate(
401 Handle<SeqString>::cast(current_part()), current_index_));
404 static const int kInitialPartLength = 32;
405 static const int kMaxPartLength = 16 * 1024;
406 static const int kPartLengthGrowthFactor = 2;
409 String::Encoding encoding_;
413 Handle<String> accumulator_;
414 Handle<String> current_part_;
418 template <typename SrcChar, typename DestChar>
419 void IncrementalStringBuilder::Append(SrcChar c) {
420 DCHECK_EQ(encoding_ == String::ONE_BYTE_ENCODING, sizeof(DestChar) == 1);
421 if (sizeof(DestChar) == 1) {
422 DCHECK_EQ(String::ONE_BYTE_ENCODING, encoding_);
423 SeqOneByteString::cast(*current_part_)
424 ->SeqOneByteStringSet(current_index_++, c);
426 DCHECK_EQ(String::TWO_BYTE_ENCODING, encoding_);
427 SeqTwoByteString::cast(*current_part_)
428 ->SeqTwoByteStringSet(current_index_++, c);
430 if (current_index_ == part_length_) Extend();
432 } // namespace internal
435 #endif // V8_STRING_BUILDER_H_