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
11 namespace v8 {
12 namespace internal {
13
14 template <typename sinkchar>
StringBuilderConcatHelper(String * special,sinkchar * sink,FixedArray * fixed_array,int array_length)15 void 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
48 template void StringBuilderConcatHelper<uint8_t>(String* special, uint8_t* sink,
49 FixedArray* fixed_array,
50 int array_length);
51
52 template void StringBuilderConcatHelper<uc16>(String* special, uc16* sink,
53 FixedArray* fixed_array,
54 int array_length);
55
StringBuilderConcatLength(int special_length,FixedArray * fixed_array,int array_length,bool * one_byte)56 int 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->HasOnlyOneByteChars()) {
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
FixedArrayBuilder(Isolate * isolate,int initial_capacity)105 FixedArrayBuilder::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
FixedArrayBuilder(Handle<FixedArray> backing_store)114 FixedArrayBuilder::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
HasCapacity(int elements)121 bool FixedArrayBuilder::HasCapacity(int elements) {
122 int length = array_->length();
123 int required_length = length_ + elements;
124 return (length >= required_length);
125 }
126
EnsureCapacity(Isolate * isolate,int elements)127 void 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
Add(Object * value)142 void FixedArrayBuilder::Add(Object* value) {
143 DCHECK(!value->IsSmi());
144 DCHECK(length_ < capacity());
145 array_->set(length_, value);
146 length_++;
147 has_non_smi_elements_ = true;
148 }
149
Add(Smi * value)150 void FixedArrayBuilder::Add(Smi* value) {
151 DCHECK(value->IsSmi());
152 DCHECK(length_ < capacity());
153 array_->set(length_, value);
154 length_++;
155 }
156
capacity()157 int FixedArrayBuilder::capacity() { return array_->length(); }
158
ToJSArray(Handle<JSArray> target_array)159 Handle<JSArray> FixedArrayBuilder::ToJSArray(Handle<JSArray> target_array) {
160 JSArray::SetContent(target_array, array_);
161 target_array->set_length(Smi::FromInt(length_));
162 return target_array;
163 }
164
ReplacementStringBuilder(Heap * heap,Handle<String> subject,int estimated_part_count)165 ReplacementStringBuilder::ReplacementStringBuilder(Heap* heap,
166 Handle<String> subject,
167 int estimated_part_count)
168 : heap_(heap),
169 array_builder_(heap->isolate(), estimated_part_count),
170 subject_(subject),
171 character_count_(0),
172 is_one_byte_(subject->IsOneByteRepresentation()) {
173 // Require a non-zero initial size. Ensures that doubling the size to
174 // extend the array will work.
175 DCHECK_GT(estimated_part_count, 0);
176 }
177
EnsureCapacity(int elements)178 void ReplacementStringBuilder::EnsureCapacity(int elements) {
179 array_builder_.EnsureCapacity(heap_->isolate(), elements);
180 }
181
AddString(Handle<String> string)182 void ReplacementStringBuilder::AddString(Handle<String> string) {
183 int length = string->length();
184 DCHECK_GT(length, 0);
185 AddElement(*string);
186 if (!string->IsOneByteRepresentation()) {
187 is_one_byte_ = false;
188 }
189 IncrementCharacterCount(length);
190 }
191
ToString()192 MaybeHandle<String> ReplacementStringBuilder::ToString() {
193 Isolate* isolate = heap_->isolate();
194 if (array_builder_.length() == 0) {
195 return isolate->factory()->empty_string();
196 }
197
198 Handle<String> joined_string;
199 if (is_one_byte_) {
200 Handle<SeqOneByteString> seq;
201 ASSIGN_RETURN_ON_EXCEPTION(
202 isolate, seq, isolate->factory()->NewRawOneByteString(character_count_),
203 String);
204
205 DisallowHeapAllocation no_gc;
206 uint8_t* char_buffer = seq->GetChars();
207 StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
208 array_builder_.length());
209 joined_string = Handle<String>::cast(seq);
210 } else {
211 // Two-byte.
212 Handle<SeqTwoByteString> seq;
213 ASSIGN_RETURN_ON_EXCEPTION(
214 isolate, seq, isolate->factory()->NewRawTwoByteString(character_count_),
215 String);
216
217 DisallowHeapAllocation no_gc;
218 uc16* char_buffer = seq->GetChars();
219 StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
220 array_builder_.length());
221 joined_string = Handle<String>::cast(seq);
222 }
223 return joined_string;
224 }
225
AddElement(Object * element)226 void ReplacementStringBuilder::AddElement(Object* element) {
227 DCHECK(element->IsSmi() || element->IsString());
228 DCHECK(array_builder_.capacity() > array_builder_.length());
229 array_builder_.Add(element);
230 }
231
IncrementalStringBuilder(Isolate * isolate)232 IncrementalStringBuilder::IncrementalStringBuilder(Isolate* isolate)
233 : isolate_(isolate),
234 encoding_(String::ONE_BYTE_ENCODING),
235 overflowed_(false),
236 part_length_(kInitialPartLength),
237 current_index_(0) {
238 // Create an accumulator handle starting with the empty string.
239 accumulator_ =
240 Handle<String>::New(ReadOnlyRoots(isolate).empty_string(), isolate);
241 current_part_ =
242 factory()->NewRawOneByteString(part_length_).ToHandleChecked();
243 }
244
Length() const245 int IncrementalStringBuilder::Length() const {
246 return accumulator_->length() + current_index_;
247 }
248
Accumulate(Handle<String> new_part)249 void IncrementalStringBuilder::Accumulate(Handle<String> new_part) {
250 Handle<String> new_accumulator;
251 if (accumulator()->length() + new_part->length() > String::kMaxLength) {
252 // Set the flag and carry on. Delay throwing the exception till the end.
253 new_accumulator = factory()->empty_string();
254 overflowed_ = true;
255 } else {
256 new_accumulator =
257 factory()->NewConsString(accumulator(), new_part).ToHandleChecked();
258 }
259 set_accumulator(new_accumulator);
260 }
261
262
Extend()263 void IncrementalStringBuilder::Extend() {
264 DCHECK_EQ(current_index_, current_part()->length());
265 Accumulate(current_part());
266 if (part_length_ <= kMaxPartLength / kPartLengthGrowthFactor) {
267 part_length_ *= kPartLengthGrowthFactor;
268 }
269 Handle<String> new_part;
270 if (encoding_ == String::ONE_BYTE_ENCODING) {
271 new_part = factory()->NewRawOneByteString(part_length_).ToHandleChecked();
272 } else {
273 new_part = factory()->NewRawTwoByteString(part_length_).ToHandleChecked();
274 }
275 // Reuse the same handle to avoid being invalidated when exiting handle scope.
276 set_current_part(new_part);
277 current_index_ = 0;
278 }
279
280
Finish()281 MaybeHandle<String> IncrementalStringBuilder::Finish() {
282 ShrinkCurrentPart();
283 Accumulate(current_part());
284 if (overflowed_) {
285 THROW_NEW_ERROR(isolate_, NewInvalidStringLengthError(), String);
286 }
287 return accumulator();
288 }
289
290
AppendString(Handle<String> string)291 void IncrementalStringBuilder::AppendString(Handle<String> string) {
292 ShrinkCurrentPart();
293 part_length_ = kInitialPartLength; // Allocate conservatively.
294 Extend(); // Attach current part and allocate new part.
295 Accumulate(string);
296 }
297 } // namespace internal
298 } // namespace v8
299