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#ifndef V8_STRING_BUILDER_INL_H_
6#define V8_STRING_BUILDER_INL_H_
7
8#include "src/assert-scope.h"
9#include "src/handles-inl.h"
10#include "src/heap/factory.h"
11#include "src/isolate.h"
12#include "src/objects.h"
13#include "src/objects/fixed-array.h"
14#include "src/objects/string-inl.h"
15#include "src/utils.h"
16
17namespace v8 {
18namespace internal {
19
20const int kStringBuilderConcatHelperLengthBits = 11;
21const int kStringBuilderConcatHelperPositionBits = 19;
22
23typedef BitField<int, 0, kStringBuilderConcatHelperLengthBits>
24 StringBuilderSubstringLength;
25typedef BitField<int, kStringBuilderConcatHelperLengthBits,
26 kStringBuilderConcatHelperPositionBits>
27 StringBuilderSubstringPosition;
28
29template <typename sinkchar>
30void StringBuilderConcatHelper(String special, sinkchar* sink,
31 FixedArray fixed_array, int array_length);
32
33// Returns the result length of the concatenation.
34// On illegal argument, -1 is returned.
35int StringBuilderConcatLength(int special_length, FixedArray fixed_array,
36 int array_length, bool* one_byte);
37
38class FixedArrayBuilder {
39 public:
40 explicit FixedArrayBuilder(Isolate* isolate, int initial_capacity);
41 explicit FixedArrayBuilder(Handle<FixedArray> backing_store);
42
43 bool HasCapacity(int elements);
44 void EnsureCapacity(Isolate* isolate, int elements);
45
46 void Add(Object value);
47 void Add(Smi value);
48
49 Handle<FixedArray> array() { return array_; }
50
51 int length() { return length_; }
52
53 int capacity();
54
55 Handle<JSArray> ToJSArray(Handle<JSArray> target_array);
56
57 private:
58 Handle<FixedArray> array_;
59 int length_;
60 bool has_non_smi_elements_;
61};
62
63class ReplacementStringBuilder {
64 public:
65 ReplacementStringBuilder(Heap* heap, Handle<String> subject,
66 int estimated_part_count);
67
68 // Caution: Callers must ensure the builder has enough capacity.
69 static inline void AddSubjectSlice(FixedArrayBuilder* builder, int from,
70 int to) {
71 DCHECK_GE(from, 0);
72 int length = to - from;
73 DCHECK_GT(length, 0);
74 if (StringBuilderSubstringLength::is_valid(length) &&
75 StringBuilderSubstringPosition::is_valid(from)) {
76 int encoded_slice = StringBuilderSubstringLength::encode(length) |
77 StringBuilderSubstringPosition::encode(from);
78 builder->Add(Smi::FromInt(encoded_slice));
79 } else {
80 // Otherwise encode as two smis.
81 builder->Add(Smi::FromInt(-length));
82 builder->Add(Smi::FromInt(from));
83 }
84 }
85
86 void AddSubjectSlice(int from, int to) {
87 EnsureCapacity(2); // Subject slices are encoded with up to two smis.
88 AddSubjectSlice(&array_builder_, from, to);
89 IncrementCharacterCount(to - from);
90 }
91
92 void AddString(Handle<String> string);
93
94 MaybeHandle<String> ToString();
95
96 void IncrementCharacterCount(int by) {
97 if (character_count_ > String::kMaxLength - by) {
98 STATIC_ASSERT(String::kMaxLength < kMaxInt);
99 character_count_ = kMaxInt;
100 } else {
101 character_count_ += by;
102 }
103 }
104
105 private:
106 void AddElement(Handle<Object> element);
107 void EnsureCapacity(int elements);
108
109 Heap* heap_;
110 FixedArrayBuilder array_builder_;
111 Handle<String> subject_;
112 int character_count_;
113 bool is_one_byte_;
114};
115
116class IncrementalStringBuilder {
117 public:
118 explicit IncrementalStringBuilder(Isolate* isolate);
119
120 V8_INLINE String::Encoding CurrentEncoding() { return encoding_; }
121
122 template <typename SrcChar, typename DestChar>
123 V8_INLINE void Append(SrcChar c);
124
125 V8_INLINE void AppendCharacter(uint8_t c) {
126 if (encoding_ == String::ONE_BYTE_ENCODING) {
127 Append<uint8_t, uint8_t>(c);
128 } else {
129 Append<uint8_t, uc16>(c);
130 }
131 }
132
133 V8_INLINE void AppendCString(const char* s) {
134 const uint8_t* u = reinterpret_cast<const uint8_t*>(s);
135 if (encoding_ == String::ONE_BYTE_ENCODING) {
136 while (*u != '\0') Append<uint8_t, uint8_t>(*(u++));
137 } else {
138 while (*u != '\0') Append<uint8_t, uc16>(*(u++));
139 }
140 }
141
142 V8_INLINE void AppendCString(const uc16* s) {
143 if (encoding_ == String::ONE_BYTE_ENCODING) {
144 while (*s != '\0') Append<uc16, uint8_t>(*(s++));
145 } else {
146 while (*s != '\0') Append<uc16, uc16>(*(s++));
147 }
148 }
149
150 V8_INLINE bool CurrentPartCanFit(int length) {
151 return part_length_ - current_index_ > length;
152 }
153
154 // We make a rough estimate to find out if the current string can be
155 // serialized without allocating a new string part. The worst case length of
156 // an escaped character is 6. Shifting the remaining string length right by 3
157 // is a more pessimistic estimate, but faster to calculate.
158 V8_INLINE int EscapedLengthIfCurrentPartFits(int length) {
159 if (length > kMaxPartLength) return 0;
160 STATIC_ASSERT((kMaxPartLength << 3) <= String::kMaxLength);
161 // This shift will not overflow because length is already less than the
162 // maximum part length.
163 int worst_case_length = length << 3;
164 return CurrentPartCanFit(worst_case_length) ? worst_case_length : 0;
165 }
166
167 void AppendString(Handle<String> string);
168
169 MaybeHandle<String> Finish();
170
171 V8_INLINE bool HasOverflowed() const { return overflowed_; }
172
173 int Length() const;
174
175 // Change encoding to two-byte.
176 void ChangeEncoding() {
177 DCHECK_EQ(String::ONE_BYTE_ENCODING, encoding_);
178 ShrinkCurrentPart();
179 encoding_ = String::TWO_BYTE_ENCODING;
180 Extend();
181 }
182
183 template <typename DestChar>
184 class NoExtend {
185 public:
186 NoExtend(Handle<String> string, int offset,
187 const DisallowHeapAllocation& no_gc) {
188 DCHECK(string->IsSeqOneByteString() || string->IsSeqTwoByteString());
189 if (sizeof(DestChar) == 1) {
190 start_ = reinterpret_cast<DestChar*>(
191 Handle<SeqOneByteString>::cast(string)->GetChars(no_gc) + offset);
192 } else {
193 start_ = reinterpret_cast<DestChar*>(
194 Handle<SeqTwoByteString>::cast(string)->GetChars(no_gc) + offset);
195 }
196 cursor_ = start_;
197 }
198
199 V8_INLINE void Append(DestChar c) { *(cursor_++) = c; }
200 V8_INLINE void AppendCString(const char* s) {
201 const uint8_t* u = reinterpret_cast<const uint8_t*>(s);
202 while (*u != '\0') Append(*(u++));
203 }
204
205 int written() { return static_cast<int>(cursor_ - start_); }
206
207 private:
208 DestChar* start_;
209 DestChar* cursor_;
210 DISALLOW_HEAP_ALLOCATION(no_gc_)
211 };
212
213 template <typename DestChar>
214 class NoExtendString : public NoExtend<DestChar> {
215 public:
216 NoExtendString(Handle<String> string, int required_length)
217 : NoExtend<DestChar>(string, 0), string_(string) {
218 DCHECK(string->length() >= required_length);
219 }
220
221 Handle<String> Finalize() {
222 Handle<SeqString> string = Handle<SeqString>::cast(string_);
223 int length = NoExtend<DestChar>::written();
224 Handle<String> result = SeqString::Truncate(string, length);
225 string_ = Handle<String>();
226 return result;
227 }
228
229 private:
230 Handle<String> string_;
231 };
232
233 template <typename DestChar>
234 class NoExtendBuilder : public NoExtend<DestChar> {
235 public:
236 NoExtendBuilder(IncrementalStringBuilder* builder, int required_length,
237 const DisallowHeapAllocation& no_gc)
238 : NoExtend<DestChar>(builder->current_part(), builder->current_index_,
239 no_gc),
240 builder_(builder) {
241 DCHECK(builder->CurrentPartCanFit(required_length));
242 }
243
244 ~NoExtendBuilder() {
245 builder_->current_index_ += NoExtend<DestChar>::written();
246 }
247
248 private:
249 IncrementalStringBuilder* builder_;
250 };
251
252 private:
253 Factory* factory() { return isolate_->factory(); }
254
255 V8_INLINE Handle<String> accumulator() { return accumulator_; }
256
257 V8_INLINE void set_accumulator(Handle<String> string) {
258 *accumulator_.location() = string->ptr();
259 }
260
261 V8_INLINE Handle<String> current_part() { return current_part_; }
262
263 V8_INLINE void set_current_part(Handle<String> string) {
264 *current_part_.location() = string->ptr();
265 }
266
267 // Add the current part to the accumulator.
268 void Accumulate(Handle<String> new_part);
269
270 // Finish the current part and allocate a new part.
271 void Extend();
272
273 // Shrink current part to the right size.
274 void ShrinkCurrentPart() {
275 DCHECK(current_index_ < part_length_);
276 set_current_part(SeqString::Truncate(
277 Handle<SeqString>::cast(current_part()), current_index_));
278 }
279
280 static const int kInitialPartLength = 32;
281 static const int kMaxPartLength = 16 * 1024;
282 static const int kPartLengthGrowthFactor = 2;
283
284 Isolate* isolate_;
285 String::Encoding encoding_;
286 bool overflowed_;
287 int part_length_;
288 int current_index_;
289 Handle<String> accumulator_;
290 Handle<String> current_part_;
291};
292
293template <typename SrcChar, typename DestChar>
294void IncrementalStringBuilder::Append(SrcChar c) {
295 DCHECK_EQ(encoding_ == String::ONE_BYTE_ENCODING, sizeof(DestChar) == 1);
296 if (sizeof(DestChar) == 1) {
297 DCHECK_EQ(String::ONE_BYTE_ENCODING, encoding_);
298 SeqOneByteString::cast(*current_part_)
299 ->SeqOneByteStringSet(current_index_++, c);
300 } else {
301 DCHECK_EQ(String::TWO_BYTE_ENCODING, encoding_);
302 SeqTwoByteString::cast(*current_part_)
303 ->SeqTwoByteStringSet(current_index_++, c);
304 }
305 if (current_index_ == part_length_) Extend();
306}
307} // namespace internal
308} // namespace v8
309
310#endif // V8_STRING_BUILDER_INL_H_
311