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#include "src/string-builder-inl.h"
6
7#include "src/isolate-inl.h"
8#include "src/objects/fixed-array-inl.h"
9#include "src/objects/js-array-inl.h"
10
11namespace v8 {
12namespace internal {
13
14template <typename sinkchar>
15void StringBuilderConcatHelper(String special, sinkchar* sink,
16 FixedArray fixed_array, int array_length) {
17 DisallowHeapAllocation no_gc;
18 int position = 0;
19 for (int i = 0; i < array_length; i++) {
20 Object element = fixed_array->get(i);
21 if (element->IsSmi()) {
22 // Smi encoding of position and length.
23 int encoded_slice = Smi::ToInt(element);
24 int pos;
25 int len;
26 if (encoded_slice > 0) {
27 // Position and length encoded in one smi.
28 pos = StringBuilderSubstringPosition::decode(encoded_slice);
29 len = StringBuilderSubstringLength::decode(encoded_slice);
30 } else {
31 // Position and length encoded in two smis.
32 Object obj = fixed_array->get(++i);
33 DCHECK(obj->IsSmi());
34 pos = Smi::ToInt(obj);
35 len = -encoded_slice;
36 }
37 String::WriteToFlat(special, sink + position, pos, pos + len);
38 position += len;
39 } else {
40 String string = String::cast(element);
41 int element_length = string->length();
42 String::WriteToFlat(string, sink + position, 0, element_length);
43 position += element_length;
44 }
45 }
46}
47
48template void StringBuilderConcatHelper<uint8_t>(String special, uint8_t* sink,
49 FixedArray fixed_array,
50 int array_length);
51
52template void StringBuilderConcatHelper<uc16>(String special, uc16* sink,
53 FixedArray fixed_array,
54 int array_length);
55
56int StringBuilderConcatLength(int special_length, FixedArray fixed_array,
57 int array_length, bool* one_byte) {
58 DisallowHeapAllocation no_gc;
59 int position = 0;
60 for (int i = 0; i < array_length; i++) {
61 int increment = 0;
62 Object elt = fixed_array->get(i);
63 if (elt->IsSmi()) {
64 // Smi encoding of position and length.
65 int smi_value = Smi::ToInt(elt);
66 int pos;
67 int len;
68 if (smi_value > 0) {
69 // Position and length encoded in one smi.
70 pos = StringBuilderSubstringPosition::decode(smi_value);
71 len = StringBuilderSubstringLength::decode(smi_value);
72 } else {
73 // Position and length encoded in two smis.
74 len = -smi_value;
75 // Get the position and check that it is a positive smi.
76 i++;
77 if (i >= array_length) return -1;
78 Object next_smi = fixed_array->get(i);
79 if (!next_smi->IsSmi()) return -1;
80 pos = Smi::ToInt(next_smi);
81 if (pos < 0) return -1;
82 }
83 DCHECK_GE(pos, 0);
84 DCHECK_GE(len, 0);
85 if (pos > special_length || len > special_length - pos) return -1;
86 increment = len;
87 } else if (elt->IsString()) {
88 String element = String::cast(elt);
89 int element_length = element->length();
90 increment = element_length;
91 if (*one_byte && !element->IsOneByteRepresentation()) {
92 *one_byte = false;
93 }
94 } else {
95 return -1;
96 }
97 if (increment > String::kMaxLength - position) {
98 return kMaxInt; // Provoke throw on allocation.
99 }
100 position += increment;
101 }
102 return position;
103}
104
105FixedArrayBuilder::FixedArrayBuilder(Isolate* isolate, int initial_capacity)
106 : array_(isolate->factory()->NewFixedArrayWithHoles(initial_capacity)),
107 length_(0),
108 has_non_smi_elements_(false) {
109 // Require a non-zero initial size. Ensures that doubling the size to
110 // extend the array will work.
111 DCHECK_GT(initial_capacity, 0);
112}
113
114FixedArrayBuilder::FixedArrayBuilder(Handle<FixedArray> backing_store)
115 : array_(backing_store), length_(0), has_non_smi_elements_(false) {
116 // Require a non-zero initial size. Ensures that doubling the size to
117 // extend the array will work.
118 DCHECK_GT(backing_store->length(), 0);
119}
120
121bool FixedArrayBuilder::HasCapacity(int elements) {
122 int length = array_->length();
123 int required_length = length_ + elements;
124 return (length >= required_length);
125}
126
127void FixedArrayBuilder::EnsureCapacity(Isolate* isolate, int elements) {
128 int length = array_->length();
129 int required_length = length_ + elements;
130 if (length < required_length) {
131 int new_length = length;
132 do {
133 new_length *= 2;
134 } while (new_length < required_length);
135 Handle<FixedArray> extended_array =
136 isolate->factory()->NewFixedArrayWithHoles(new_length);
137 array_->CopyTo(0, *extended_array, 0, length_);
138 array_ = extended_array;
139 }
140}
141
142void FixedArrayBuilder::Add(Object value) {
143 DCHECK(!value->IsSmi());
144 array_->set(length_, value);
145 length_++;
146 has_non_smi_elements_ = true;
147}
148
149void FixedArrayBuilder::Add(Smi value) {
150 DCHECK(value->IsSmi());
151 array_->set(length_, value);
152 length_++;
153}
154
155int FixedArrayBuilder::capacity() { return array_->length(); }
156
157Handle<JSArray> FixedArrayBuilder::ToJSArray(Handle<JSArray> target_array) {
158 JSArray::SetContent(target_array, array_);
159 target_array->set_length(Smi::FromInt(length_));
160 return target_array;
161}
162
163ReplacementStringBuilder::ReplacementStringBuilder(Heap* heap,
164 Handle<String> subject,
165 int estimated_part_count)
166 : heap_(heap),
167 array_builder_(Isolate::FromHeap(heap), estimated_part_count),
168 subject_(subject),
169 character_count_(0),
170 is_one_byte_(subject->IsOneByteRepresentation()) {
171 // Require a non-zero initial size. Ensures that doubling the size to
172 // extend the array will work.
173 DCHECK_GT(estimated_part_count, 0);
174}
175
176void ReplacementStringBuilder::EnsureCapacity(int elements) {
177 array_builder_.EnsureCapacity(Isolate::FromHeap(heap_), elements);
178}
179
180void ReplacementStringBuilder::AddString(Handle<String> string) {
181 int length = string->length();
182 DCHECK_GT(length, 0);
183 AddElement(string);
184 if (!string->IsOneByteRepresentation()) {
185 is_one_byte_ = false;
186 }
187 IncrementCharacterCount(length);
188}
189
190MaybeHandle<String> ReplacementStringBuilder::ToString() {
191 Isolate* isolate = Isolate::FromHeap(heap_);
192 if (array_builder_.length() == 0) {
193 return isolate->factory()->empty_string();
194 }
195
196 Handle<String> joined_string;
197 if (is_one_byte_) {
198 Handle<SeqOneByteString> seq;
199 ASSIGN_RETURN_ON_EXCEPTION(
200 isolate, seq, isolate->factory()->NewRawOneByteString(character_count_),
201 String);
202
203 DisallowHeapAllocation no_gc;
204 uint8_t* char_buffer = seq->GetChars(no_gc);
205 StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
206 array_builder_.length());
207 joined_string = Handle<String>::cast(seq);
208 } else {
209 // Two-byte.
210 Handle<SeqTwoByteString> seq;
211 ASSIGN_RETURN_ON_EXCEPTION(
212 isolate, seq, isolate->factory()->NewRawTwoByteString(character_count_),
213 String);
214
215 DisallowHeapAllocation no_gc;
216 uc16* char_buffer = seq->GetChars(no_gc);
217 StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
218 array_builder_.length());
219 joined_string = Handle<String>::cast(seq);
220 }
221 return joined_string;
222}
223
224void ReplacementStringBuilder::AddElement(Handle<Object> element) {
225 DCHECK(element->IsSmi() || element->IsString());
226 EnsureCapacity(1);
227 DisallowHeapAllocation no_gc;
228 array_builder_.Add(*element);
229}
230
231IncrementalStringBuilder::IncrementalStringBuilder(Isolate* isolate)
232 : isolate_(isolate),
233 encoding_(String::ONE_BYTE_ENCODING),
234 overflowed_(false),
235 part_length_(kInitialPartLength),
236 current_index_(0) {
237 // Create an accumulator handle starting with the empty string.
238 accumulator_ =
239 Handle<String>::New(ReadOnlyRoots(isolate).empty_string(), isolate);
240 current_part_ =
241 factory()->NewRawOneByteString(part_length_).ToHandleChecked();
242}
243
244int IncrementalStringBuilder::Length() const {
245 return accumulator_->length() + current_index_;
246}
247
248void IncrementalStringBuilder::Accumulate(Handle<String> new_part) {
249 Handle<String> new_accumulator;
250 if (accumulator()->length() + new_part->length() > String::kMaxLength) {
251 // Set the flag and carry on. Delay throwing the exception till the end.
252 new_accumulator = factory()->empty_string();
253 overflowed_ = true;
254 } else {
255 new_accumulator =
256 factory()->NewConsString(accumulator(), new_part).ToHandleChecked();
257 }
258 set_accumulator(new_accumulator);
259}
260
261
262void IncrementalStringBuilder::Extend() {
263 DCHECK_EQ(current_index_, current_part()->length());
264 Accumulate(current_part());
265 if (part_length_ <= kMaxPartLength / kPartLengthGrowthFactor) {
266 part_length_ *= kPartLengthGrowthFactor;
267 }
268 Handle<String> new_part;
269 if (encoding_ == String::ONE_BYTE_ENCODING) {
270 new_part = factory()->NewRawOneByteString(part_length_).ToHandleChecked();
271 } else {
272 new_part = factory()->NewRawTwoByteString(part_length_).ToHandleChecked();
273 }
274 // Reuse the same handle to avoid being invalidated when exiting handle scope.
275 set_current_part(new_part);
276 current_index_ = 0;
277}
278
279
280MaybeHandle<String> IncrementalStringBuilder::Finish() {
281 ShrinkCurrentPart();
282 Accumulate(current_part());
283 if (overflowed_) {
284 THROW_NEW_ERROR(isolate_, NewInvalidStringLengthError(), String);
285 }
286 return accumulator();
287}
288
289
290void IncrementalStringBuilder::AppendString(Handle<String> string) {
291 ShrinkCurrentPart();
292 part_length_ = kInitialPartLength; // Allocate conservatively.
293 Extend(); // Attach current part and allocate new part.
294 Accumulate(string);
295}
296} // namespace internal
297} // namespace v8
298