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 2378 : void StringBuilderConcatHelper(String special, sinkchar* sink,
16 : FixedArray fixed_array, int array_length) {
17 : DisallowHeapAllocation no_gc;
18 : int position = 0;
19 669646 : for (int i = 0; i < array_length; i++) {
20 : Object element = fixed_array->get(i);
21 333634 : if (element->IsSmi()) {
22 : // Smi encoding of position and length.
23 : int encoded_slice = Smi::ToInt(element);
24 : int pos;
25 : int len;
26 61437 : if (encoded_slice > 0) {
27 : // Position and length encoded in one smi.
28 61419 : pos = StringBuilderSubstringPosition::decode(encoded_slice);
29 : len = StringBuilderSubstringLength::decode(encoded_slice);
30 : } else {
31 : // Position and length encoded in two smis.
32 18 : Object obj = fixed_array->get(++i);
33 : DCHECK(obj->IsSmi());
34 : pos = Smi::ToInt(obj);
35 18 : len = -encoded_slice;
36 : }
37 61437 : String::WriteToFlat(special, sink + position, pos, pos + len);
38 61437 : position += len;
39 : } else {
40 : String string = String::cast(element);
41 : int element_length = string->length();
42 272197 : String::WriteToFlat(string, sink + position, 0, element_length);
43 272197 : position += element_length;
44 : }
45 : }
46 2378 : }
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 660259 : for (int i = 0; i < array_length; i++) {
61 : int increment = 0;
62 : Object elt = fixed_array->get(i);
63 329809 : if (elt->IsSmi()) {
64 : // Smi encoding of position and length.
65 : 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 : Object next_smi = fixed_array->get(i);
79 0 : if (!next_smi->IsSmi()) return -1;
80 : 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 : String element = String::cast(elt);
89 : int element_length = element->length();
90 : increment = element_length;
91 542122 : if (*one_byte && !element->IsOneByteRepresentation()) {
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 1764 : 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 93153 : FixedArrayBuilder::FixedArrayBuilder(Handle<FixedArray> backing_store)
115 93153 : : 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 93153 : }
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 367621 : void FixedArrayBuilder::EnsureCapacity(Isolate* isolate, int elements) {
128 : int length = array_->length();
129 367621 : int required_length = length_ + elements;
130 367621 : if (length < required_length) {
131 : int new_length = length;
132 : do {
133 1424 : new_length *= 2;
134 1424 : } while (new_length < required_length);
135 : Handle<FixedArray> extended_array =
136 1424 : isolate->factory()->NewFixedArrayWithHoles(new_length);
137 2848 : array_->CopyTo(0, *extended_array, 0, length_);
138 1424 : array_ = extended_array;
139 : }
140 367621 : }
141 :
142 363508 : void FixedArrayBuilder::Add(Object value) {
143 : DCHECK(!value->IsSmi());
144 729842 : array_->set(length_, value);
145 364921 : length_++;
146 364921 : has_non_smi_elements_ = true;
147 363508 : }
148 :
149 61455 : void FixedArrayBuilder::Add(Smi value) {
150 : DCHECK(value->IsSmi());
151 61455 : array_->set(length_, value);
152 61455 : length_++;
153 61455 : }
154 :
155 0 : int FixedArrayBuilder::capacity() { return array_->length(); }
156 :
157 93095 : Handle<JSArray> FixedArrayBuilder::ToJSArray(Handle<JSArray> target_array) {
158 93095 : JSArray::SetContent(target_array, array_);
159 93095 : target_array->set_length(Smi::FromInt(length_));
160 93095 : return target_array;
161 : }
162 :
163 1764 : ReplacementStringBuilder::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 7056 : 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 1764 : }
175 :
176 2700 : void ReplacementStringBuilder::EnsureCapacity(int elements) {
177 8226 : array_builder_.EnsureCapacity(Isolate::FromHeap(heap_), elements);
178 2700 : }
179 :
180 1413 : void ReplacementStringBuilder::AddString(Handle<String> string) {
181 : int length = string->length();
182 : DCHECK_GT(length, 0);
183 1413 : AddElement(string);
184 1413 : if (!string->IsOneByteRepresentation()) {
185 0 : is_one_byte_ = false;
186 : }
187 : IncrementCharacterCount(length);
188 1413 : }
189 :
190 1764 : MaybeHandle<String> ReplacementStringBuilder::ToString() {
191 1764 : Isolate* isolate = Isolate::FromHeap(heap_);
192 1764 : if (array_builder_.length() == 0) {
193 36 : return isolate->factory()->empty_string();
194 : }
195 :
196 : Handle<String> joined_string;
197 1728 : if (is_one_byte_) {
198 : Handle<SeqOneByteString> seq;
199 3456 : 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 1728 : array_builder_.length());
207 : joined_string = Handle<String>::cast(seq);
208 : } else {
209 : // Two-byte.
210 : Handle<SeqTwoByteString> seq;
211 0 : 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 0 : array_builder_.length());
219 : joined_string = Handle<String>::cast(seq);
220 : }
221 1728 : return joined_string;
222 : }
223 :
224 1413 : void ReplacementStringBuilder::AddElement(Handle<Object> element) {
225 : DCHECK(element->IsSmi() || element->IsString());
226 : EnsureCapacity(1);
227 : DisallowHeapAllocation no_gc;
228 : array_builder_.Add(*element);
229 1413 : }
230 :
231 6168430 : IncrementalStringBuilder::IncrementalStringBuilder(Isolate* isolate)
232 : : isolate_(isolate),
233 : encoding_(String::ONE_BYTE_ENCODING),
234 : overflowed_(false),
235 : part_length_(kInitialPartLength),
236 6168430 : current_index_(0) {
237 : // Create an accumulator handle starting with the empty string.
238 : accumulator_ =
239 6168430 : Handle<String>::New(ReadOnlyRoots(isolate).empty_string(), isolate);
240 : current_part_ =
241 12336859 : factory()->NewRawOneByteString(part_length_).ToHandleChecked();
242 6168429 : }
243 :
244 1088896 : int IncrementalStringBuilder::Length() const {
245 1088896 : return accumulator_->length() + current_index_;
246 : }
247 :
248 22761094 : void IncrementalStringBuilder::Accumulate(Handle<String> new_part) {
249 : Handle<String> new_accumulator;
250 22761094 : 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 45 : overflowed_ = true;
254 : } else {
255 : new_accumulator =
256 45522090 : factory()->NewConsString(accumulator(), new_part).ToHandleChecked();
257 : }
258 : set_accumulator(new_accumulator);
259 22761086 : }
260 :
261 :
262 9049441 : void IncrementalStringBuilder::Extend() {
263 : DCHECK_EQ(current_index_, current_part()->length());
264 9049441 : Accumulate(current_part());
265 9049441 : if (part_length_ <= kMaxPartLength / kPartLengthGrowthFactor) {
266 8895181 : part_length_ *= kPartLengthGrowthFactor;
267 : }
268 : Handle<String> new_part;
269 9049441 : if (encoding_ == String::ONE_BYTE_ENCODING) {
270 16660610 : new_part = factory()->NewRawOneByteString(part_length_).ToHandleChecked();
271 : } else {
272 1438272 : 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 9049441 : current_index_ = 0;
277 9049441 : }
278 :
279 :
280 6167786 : MaybeHandle<String> IncrementalStringBuilder::Finish() {
281 6167786 : ShrinkCurrentPart();
282 6167785 : Accumulate(current_part());
283 6167786 : if (overflowed_) {
284 45 : THROW_NEW_ERROR(isolate_, NewInvalidStringLengthError(), String);
285 : }
286 6167741 : return accumulator();
287 : }
288 :
289 :
290 7543874 : void IncrementalStringBuilder::AppendString(Handle<String> string) {
291 7543874 : ShrinkCurrentPart();
292 7543874 : part_length_ = kInitialPartLength; // Allocate conservatively.
293 7543874 : Extend(); // Attach current part and allocate new part.
294 7543872 : Accumulate(string);
295 7543872 : }
296 : } // namespace internal
297 121996 : } // namespace v8
|
