Line data Source code
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>
15 2234 : void StringBuilderConcatHelper(String special, sinkchar* sink,
16 : FixedArray fixed_array, int array_length) {
17 : DisallowHeapAllocation no_gc;
18 : int position = 0;
19 335499 : for (int i = 0; i < array_length; i++) {
20 333265 : Object element = fixed_array->get(i);
21 333265 : if (element->IsSmi()) {
22 : // Smi encoding of position and length.
23 61320 : int encoded_slice = Smi::ToInt(element);
24 : int pos;
25 : int len;
26 61320 : if (encoded_slice > 0) {
27 : // Position and length encoded in one smi.
28 61302 : pos = StringBuilderSubstringPosition::decode(encoded_slice);
29 : len = StringBuilderSubstringLength::decode(encoded_slice);
30 : } else {
31 : // Position and length encoded in two smis.
32 36 : Object obj = fixed_array->get(++i);
33 : DCHECK(obj->IsSmi());
34 18 : pos = Smi::ToInt(obj);
35 18 : len = -encoded_slice;
36 : }
37 61320 : String::WriteToFlat(special, sink + position, pos, pos + len);
38 61320 : position += len;
39 : } else {
40 : String string = String::cast(element);
41 : int element_length = string->length();
42 271945 : String::WriteToFlat(string, sink + position, 0, element_length);
43 271945 : position += element_length;
44 : }
45 : }
46 2234 : }
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 :
56 659 : int StringBuilderConcatLength(int special_length, FixedArray fixed_array,
57 : int array_length, bool* one_byte) {
58 : DisallowHeapAllocation no_gc;
59 : int position = 0;
60 330459 : for (int i = 0; i < array_length; i++) {
61 : int increment = 0;
62 329809 : Object elt = fixed_array->get(i);
63 329809 : if (elt->IsSmi()) {
64 : // Smi encoding of position and length.
65 58737 : int smi_value = Smi::ToInt(elt);
66 : int pos;
67 : int len;
68 58737 : if (smi_value > 0) {
69 : // Position and length encoded in one smi.
70 58737 : pos = StringBuilderSubstringPosition::decode(smi_value);
71 : len = StringBuilderSubstringLength::decode(smi_value);
72 : } else {
73 : // Position and length encoded in two smis.
74 0 : len = -smi_value;
75 : // Get the position and check that it is a positive smi.
76 0 : i++;
77 0 : if (i >= array_length) return -1;
78 0 : Object next_smi = fixed_array->get(i);
79 0 : if (!next_smi->IsSmi()) return -1;
80 0 : pos = Smi::ToInt(next_smi);
81 0 : if (pos < 0) return -1;
82 : }
83 : DCHECK_GE(pos, 0);
84 : DCHECK_GE(len, 0);
85 58737 : if (pos > special_length || len > special_length - pos) return -1;
86 : increment = len;
87 271072 : } else if (elt->IsString()) {
88 271072 : String element = String::cast(elt);
89 : int element_length = element->length();
90 : increment = element_length;
91 271072 : if (*one_byte && !element->HasOnlyOneByteChars()) {
92 0 : *one_byte = false;
93 : }
94 : } else {
95 : return -1;
96 : }
97 329809 : if (increment > String::kMaxLength - position) {
98 : return kMaxInt; // Provoke throw on allocation.
99 : }
100 329800 : position += increment;
101 : }
102 : return position;
103 : }
104 :
105 0 : FixedArrayBuilder::FixedArrayBuilder(Isolate* isolate, int initial_capacity)
106 : : array_(isolate->factory()->NewFixedArrayWithHoles(initial_capacity)),
107 : length_(0),
108 1620 : 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 0 : }
113 :
114 93121 : FixedArrayBuilder::FixedArrayBuilder(Handle<FixedArray> backing_store)
115 93121 : : 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 93121 : }
120 :
121 0 : bool FixedArrayBuilder::HasCapacity(int elements) {
122 : int length = array_->length();
123 0 : int required_length = length_ + elements;
124 0 : return (length >= required_length);
125 : }
126 :
127 365893 : void FixedArrayBuilder::EnsureCapacity(Isolate* isolate, int elements) {
128 : int length = array_->length();
129 365893 : int required_length = length_ + elements;
130 365893 : if (length < required_length) {
131 : int new_length = length;
132 1451 : do {
133 1451 : new_length *= 2;
134 : } while (new_length < required_length);
135 : Handle<FixedArray> extended_array =
136 1451 : isolate->factory()->NewFixedArrayWithHoles(new_length);
137 2902 : array_->CopyTo(0, *extended_array, 0, length_);
138 1451 : array_ = extended_array;
139 : }
140 365893 : }
141 :
142 364633 : void FixedArrayBuilder::Add(Object value) {
143 : DCHECK(!value->IsSmi());
144 : DCHECK(length_ < capacity());
145 729266 : array_->set(length_, value);
146 364633 : length_++;
147 364633 : has_non_smi_elements_ = true;
148 364633 : }
149 :
150 61338 : void FixedArrayBuilder::Add(Smi value) {
151 : DCHECK(value->IsSmi());
152 : DCHECK(length_ < capacity());
153 61338 : array_->set(length_, value);
154 61338 : length_++;
155 61338 : }
156 :
157 0 : int FixedArrayBuilder::capacity() { return array_->length(); }
158 :
159 93059 : Handle<JSArray> FixedArrayBuilder::ToJSArray(Handle<JSArray> target_array) {
160 93059 : JSArray::SetContent(target_array, array_);
161 279177 : target_array->set_length(Smi::FromInt(length_));
162 93059 : return target_array;
163 : }
164 :
165 1620 : 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 6480 : 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 1620 : }
177 :
178 2421 : void ReplacementStringBuilder::EnsureCapacity(int elements) {
179 4842 : array_builder_.EnsureCapacity(heap_->isolate(), elements);
180 2421 : }
181 :
182 1161 : void ReplacementStringBuilder::AddString(Handle<String> string) {
183 : int length = string->length();
184 : DCHECK_GT(length, 0);
185 : AddElement(*string);
186 1161 : if (!string->IsOneByteRepresentation()) {
187 0 : is_one_byte_ = false;
188 : }
189 : IncrementCharacterCount(length);
190 1161 : }
191 :
192 1620 : MaybeHandle<String> ReplacementStringBuilder::ToString() {
193 1620 : Isolate* isolate = heap_->isolate();
194 3204 : if (array_builder_.length() == 0) {
195 36 : return isolate->factory()->empty_string();
196 : }
197 :
198 : Handle<String> joined_string;
199 1584 : if (is_one_byte_) {
200 : Handle<SeqOneByteString> seq;
201 3168 : 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(no_gc);
207 : StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
208 1584 : array_builder_.length());
209 1584 : joined_string = Handle<String>::cast(seq);
210 : } else {
211 : // Two-byte.
212 : Handle<SeqTwoByteString> seq;
213 0 : 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(no_gc);
219 : StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
220 0 : array_builder_.length());
221 0 : joined_string = Handle<String>::cast(seq);
222 : }
223 1584 : return joined_string;
224 : }
225 :
226 0 : void ReplacementStringBuilder::AddElement(Object element) {
227 : DCHECK(element->IsSmi() || element->IsString());
228 : DCHECK(array_builder_.capacity() > array_builder_.length());
229 1161 : array_builder_.Add(element);
230 0 : }
231 :
232 10932951 : IncrementalStringBuilder::IncrementalStringBuilder(Isolate* isolate)
233 : : isolate_(isolate),
234 : encoding_(String::ONE_BYTE_ENCODING),
235 : overflowed_(false),
236 : part_length_(kInitialPartLength),
237 5466475 : current_index_(0) {
238 : // Create an accumulator handle starting with the empty string.
239 : accumulator_ =
240 5466476 : Handle<String>::New(ReadOnlyRoots(isolate).empty_string(), isolate);
241 : current_part_ =
242 16399428 : factory()->NewRawOneByteString(part_length_).ToHandleChecked();
243 5466476 : }
244 :
245 1088888 : int IncrementalStringBuilder::Length() const {
246 1088888 : return accumulator_->length() + current_index_;
247 : }
248 :
249 38174510 : void IncrementalStringBuilder::Accumulate(Handle<String> new_part) {
250 : Handle<String> new_accumulator;
251 19087254 : 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 45 : overflowed_ = true;
255 : } else {
256 : new_accumulator =
257 38174419 : factory()->NewConsString(accumulator(), new_part).ToHandleChecked();
258 : }
259 : set_accumulator(new_accumulator);
260 19087255 : }
261 :
262 :
263 15135440 : void IncrementalStringBuilder::Extend() {
264 : DCHECK_EQ(current_index_, current_part()->length());
265 7567719 : Accumulate(current_part());
266 7567721 : if (part_length_ <= kMaxPartLength / kPartLengthGrowthFactor) {
267 7413460 : part_length_ *= kPartLengthGrowthFactor;
268 : }
269 : Handle<String> new_part;
270 7567721 : if (encoding_ == String::ONE_BYTE_ENCODING) {
271 20545777 : new_part = factory()->NewRawOneByteString(part_length_).ToHandleChecked();
272 : } else {
273 2157384 : 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 7567720 : current_index_ = 0;
278 7567720 : }
279 :
280 :
281 5465841 : MaybeHandle<String> IncrementalStringBuilder::Finish() {
282 5465841 : ShrinkCurrentPart();
283 5465841 : Accumulate(current_part());
284 5465840 : if (overflowed_) {
285 45 : THROW_NEW_ERROR(isolate_, NewInvalidStringLengthError(), String);
286 : }
287 5465795 : return accumulator();
288 : }
289 :
290 :
291 6053695 : void IncrementalStringBuilder::AppendString(Handle<String> string) {
292 6053695 : ShrinkCurrentPart();
293 6053693 : part_length_ = kInitialPartLength; // Allocate conservatively.
294 6053693 : Extend(); // Attach current part and allocate new part.
295 6053694 : Accumulate(string);
296 6053696 : }
297 : } // namespace internal
298 183867 : } // namespace v8
|
