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/base/strings.h"
6#include "src/execution/isolate-inl.h"
7#include "src/objects/fixed-array-inl.h"
8#include "src/objects/js-array-inl.h"
9#include "src/strings/string-builder-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  DisallowGarbageCollection 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, 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<base::uc16>(String special,
53                                                    base::uc16* sink,
54                                                    FixedArray fixed_array,
55                                                    int array_length);
56
57int StringBuilderConcatLength(int special_length, FixedArray fixed_array,
58                              int array_length, bool* one_byte) {
59  DisallowGarbageCollection no_gc;
60  int position = 0;
61  for (int i = 0; i < array_length; i++) {
62    int increment = 0;
63    Object elt = fixed_array.get(i);
64    if (elt.IsSmi()) {
65      // Smi encoding of position and length.
66      int smi_value = Smi::ToInt(elt);
67      int pos;
68      int len;
69      if (smi_value > 0) {
70        // Position and length encoded in one smi.
71        pos = StringBuilderSubstringPosition::decode(smi_value);
72        len = StringBuilderSubstringLength::decode(smi_value);
73      } else {
74        // Position and length encoded in two smis.
75        len = -smi_value;
76        // Get the position and check that it is a positive smi.
77        i++;
78        if (i >= array_length) return -1;
79        Object next_smi = fixed_array.get(i);
80        if (!next_smi.IsSmi()) return -1;
81        pos = Smi::ToInt(next_smi);
82        if (pos < 0) return -1;
83      }
84      DCHECK_GE(pos, 0);
85      DCHECK_GE(len, 0);
86      if (pos > special_length || len > special_length - pos) return -1;
87      increment = len;
88    } else if (elt.IsString()) {
89      String element = String::cast(elt);
90      int element_length = element.length();
91      increment = element_length;
92      if (*one_byte && !element.IsOneByteRepresentation()) {
93        *one_byte = false;
94      }
95    } else {
96      return -1;
97    }
98    if (increment > String::kMaxLength - position) {
99      return kMaxInt;  // Provoke throw on allocation.
100    }
101    position += increment;
102  }
103  return position;
104}
105
106FixedArrayBuilder::FixedArrayBuilder(Isolate* isolate, int initial_capacity)
107    : array_(isolate->factory()->NewFixedArrayWithHoles(initial_capacity)),
108      length_(0),
109      has_non_smi_elements_(false) {
110  // Require a non-zero initial size. Ensures that doubling the size to
111  // extend the array will work.
112  DCHECK_GT(initial_capacity, 0);
113}
114
115FixedArrayBuilder::FixedArrayBuilder(Handle<FixedArray> backing_store)
116    : array_(backing_store), length_(0), has_non_smi_elements_(false) {
117  // Require a non-zero initial size. Ensures that doubling the size to
118  // extend the array will work.
119  DCHECK_GT(backing_store->length(), 0);
120}
121
122bool FixedArrayBuilder::HasCapacity(int elements) {
123  int length = array_->length();
124  int required_length = length_ + elements;
125  return (length >= required_length);
126}
127
128void FixedArrayBuilder::EnsureCapacity(Isolate* isolate, int elements) {
129  int length = array_->length();
130  int required_length = length_ + elements;
131  if (length < required_length) {
132    int new_length = length;
133    do {
134      new_length *= 2;
135    } while (new_length < required_length);
136    Handle<FixedArray> extended_array =
137        isolate->factory()->NewFixedArrayWithHoles(new_length);
138    array_->CopyTo(0, *extended_array, 0, length_);
139    array_ = extended_array;
140  }
141}
142
143void FixedArrayBuilder::Add(Object value) {
144  DCHECK(!value.IsSmi());
145  array_->set(length_, value);
146  length_++;
147  has_non_smi_elements_ = true;
148}
149
150void FixedArrayBuilder::Add(Smi value) {
151  DCHECK(value.IsSmi());
152  array_->set(length_, value);
153  length_++;
154}
155
156int FixedArrayBuilder::capacity() { return array_->length(); }
157
158Handle<JSArray> FixedArrayBuilder::ToJSArray(Handle<JSArray> target_array) {
159  JSArray::SetContent(target_array, array_);
160  target_array->set_length(Smi::FromInt(length_));
161  return target_array;
162}
163
164ReplacementStringBuilder::ReplacementStringBuilder(Heap* heap,
165                                                   Handle<String> subject,
166                                                   int estimated_part_count)
167    : heap_(heap),
168      array_builder_(Isolate::FromHeap(heap), estimated_part_count),
169      subject_(subject),
170      character_count_(0),
171      is_one_byte_(subject->IsOneByteRepresentation()) {
172  // Require a non-zero initial size. Ensures that doubling the size to
173  // extend the array will work.
174  DCHECK_GT(estimated_part_count, 0);
175}
176
177void ReplacementStringBuilder::EnsureCapacity(int elements) {
178  array_builder_.EnsureCapacity(Isolate::FromHeap(heap_), elements);
179}
180
181void ReplacementStringBuilder::AddString(Handle<String> string) {
182  int length = string->length();
183  DCHECK_GT(length, 0);
184  AddElement(string);
185  if (!string->IsOneByteRepresentation()) {
186    is_one_byte_ = false;
187  }
188  IncrementCharacterCount(length);
189}
190
191MaybeHandle<String> ReplacementStringBuilder::ToString() {
192  Isolate* isolate = Isolate::FromHeap(heap_);
193  if (array_builder_.length() == 0) {
194    return isolate->factory()->empty_string();
195  }
196
197  Handle<String> joined_string;
198  if (is_one_byte_) {
199    Handle<SeqOneByteString> seq;
200    ASSIGN_RETURN_ON_EXCEPTION(
201        isolate, seq, isolate->factory()->NewRawOneByteString(character_count_),
202        String);
203
204    DisallowGarbageCollection no_gc;
205    uint8_t* char_buffer = seq->GetChars(no_gc);
206    StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
207                              array_builder_.length());
208    joined_string = Handle<String>::cast(seq);
209  } else {
210    // Two-byte.
211    Handle<SeqTwoByteString> seq;
212    ASSIGN_RETURN_ON_EXCEPTION(
213        isolate, seq, isolate->factory()->NewRawTwoByteString(character_count_),
214        String);
215
216    DisallowGarbageCollection no_gc;
217    base::uc16* char_buffer = seq->GetChars(no_gc);
218    StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
219                              array_builder_.length());
220    joined_string = Handle<String>::cast(seq);
221  }
222  return joined_string;
223}
224
225void ReplacementStringBuilder::AddElement(Handle<Object> element) {
226  DCHECK(element->IsSmi() || element->IsString());
227  EnsureCapacity(1);
228  DisallowGarbageCollection no_gc;
229  array_builder_.Add(*element);
230}
231
232IncrementalStringBuilder::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
245int IncrementalStringBuilder::Length() const {
246  return accumulator_->length() + current_index_;
247}
248
249bool IncrementalStringBuilder::HasValidCurrentIndex() const {
250  return current_index_ < part_length_;
251}
252
253void IncrementalStringBuilder::Accumulate(Handle<String> new_part) {
254  Handle<String> new_accumulator;
255  if (accumulator()->length() + new_part->length() > String::kMaxLength) {
256    // Set the flag and carry on. Delay throwing the exception till the end.
257    new_accumulator = factory()->empty_string();
258    overflowed_ = true;
259  } else {
260    new_accumulator =
261        factory()->NewConsString(accumulator(), new_part).ToHandleChecked();
262  }
263  set_accumulator(new_accumulator);
264}
265
266void IncrementalStringBuilder::Extend() {
267  DCHECK_EQ(current_index_, current_part()->length());
268  Accumulate(current_part());
269  if (part_length_ <= kMaxPartLength / kPartLengthGrowthFactor) {
270    part_length_ *= kPartLengthGrowthFactor;
271  }
272  Handle<String> new_part;
273  if (encoding_ == String::ONE_BYTE_ENCODING) {
274    new_part = factory()->NewRawOneByteString(part_length_).ToHandleChecked();
275  } else {
276    new_part = factory()->NewRawTwoByteString(part_length_).ToHandleChecked();
277  }
278  // Reuse the same handle to avoid being invalidated when exiting handle scope.
279  set_current_part(new_part);
280  current_index_ = 0;
281}
282
283MaybeHandle<String> IncrementalStringBuilder::Finish() {
284  ShrinkCurrentPart();
285  Accumulate(current_part());
286  if (overflowed_) {
287    THROW_NEW_ERROR(isolate_, NewInvalidStringLengthError(), String);
288  }
289  return accumulator();
290}
291
292// Short strings can be copied directly to {current_part_}.
293// Requires the IncrementalStringBuilder to either have two byte encoding or
294// the incoming string to have one byte representation "underneath" (The
295// one byte check requires the string to be flat).
296bool IncrementalStringBuilder::CanAppendByCopy(Handle<String> string) {
297  constexpr int kMaxStringLengthForCopy = 16;
298  const bool representation_ok =
299      encoding_ == String::TWO_BYTE_ENCODING ||
300      (string->IsFlat() && String::IsOneByteRepresentationUnderneath(*string));
301
302  return representation_ok && string->length() <= kMaxStringLengthForCopy &&
303         CurrentPartCanFit(string->length());
304}
305
306void IncrementalStringBuilder::AppendStringByCopy(Handle<String> string) {
307  DCHECK(CanAppendByCopy(string));
308
309  Handle<SeqOneByteString> part =
310      Handle<SeqOneByteString>::cast(current_part());
311  {
312    DisallowGarbageCollection no_gc;
313    String::WriteToFlat(*string, part->GetChars(no_gc) + current_index_, 0,
314                        string->length());
315  }
316  current_index_ += string->length();
317  DCHECK(current_index_ <= part_length_);
318  if (current_index_ == part_length_) Extend();
319}
320
321void IncrementalStringBuilder::AppendString(Handle<String> string) {
322  if (CanAppendByCopy(string)) {
323    AppendStringByCopy(string);
324    return;
325  }
326
327  ShrinkCurrentPart();
328  part_length_ = kInitialPartLength;  // Allocate conservatively.
329  Extend();  // Attach current part and allocate new part.
330  Accumulate(string);
331}
332}  // namespace internal
333}  // namespace v8
334