1/*
2 * Copyright (C) 2010-2018 Apple Inc. All rights reserved.
3 * Copyright (C) 2012 Google Inc. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
18 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include "config.h"
28#include <wtf/text/StringBuilder.h>
29
30#include <wtf/dtoa.h>
31#include <wtf/MathExtras.h>
32#include <wtf/text/WTFString.h>
33#include <wtf/text/IntegerToStringConversion.h>
34
35namespace WTF {
36
37static constexpr unsigned maxCapacity = String::MaxLength;
38
39static unsigned expandedCapacity(unsigned capacity, unsigned requiredLength)
40{
41 static const unsigned minimumCapacity = 16;
42 return std::max(requiredLength, std::max(minimumCapacity, std::min(capacity * 2, maxCapacity)));
43}
44
45void StringBuilder::reifyString() const
46{
47 ASSERT(!hasOverflowed());
48 // Check if the string already exists.
49 if (!m_string.isNull()) {
50 ASSERT(m_string.length() == m_length.unsafeGet<unsigned>());
51 return;
52 }
53
54#if !ASSERT_DISABLED
55 m_isReified = true;
56#endif
57
58 // Check for empty.
59 if (!m_length) {
60 m_string = StringImpl::empty();
61 return;
62 }
63
64 // Must be valid in the buffer, take a substring (unless string fills the buffer).
65 ASSERT(m_buffer && m_length.unsafeGet<unsigned>() <= m_buffer->length());
66 if (m_length.unsafeGet<unsigned>() == m_buffer->length())
67 m_string = m_buffer.get();
68 else
69 m_string = StringImpl::createSubstringSharingImpl(*m_buffer, 0, m_length.unsafeGet());
70}
71
72void StringBuilder::resize(unsigned newSize)
73{
74 if (hasOverflowed())
75 return;
76
77 // Check newSize < m_length, hence m_length > 0.
78 unsigned oldLength = m_length.unsafeGet();
79 ASSERT(newSize <= oldLength);
80 if (newSize == oldLength)
81 return;
82 ASSERT(oldLength);
83
84 m_length = newSize;
85 ASSERT(!hasOverflowed());
86
87 // If there is a buffer, we only need to duplicate it if it has more than one ref.
88 if (m_buffer) {
89 m_string = String(); // Clear the string to remove the reference to m_buffer if any before checking the reference count of m_buffer.
90 if (!m_buffer->hasOneRef()) {
91 if (m_buffer->is8Bit())
92 allocateBuffer(m_buffer->characters8(), m_buffer->length());
93 else
94 allocateBuffer(m_buffer->characters16(), m_buffer->length());
95 }
96 ASSERT(hasOverflowed() || m_buffer->length() >= m_length.unsafeGet<unsigned>());
97 return;
98 }
99
100 // Since m_length && !m_buffer, the string must be valid in m_string, and m_string.length() > 0.
101 ASSERT(!m_string.isEmpty());
102 ASSERT(oldLength == m_string.length());
103 ASSERT(newSize < m_string.length());
104 m_string = StringImpl::createSubstringSharingImpl(*m_string.impl(), 0, newSize);
105}
106
107// Allocate a new 8 bit buffer, copying in currentCharacters (these may come from either m_string
108// or m_buffer, neither will be reassigned until the copy has completed).
109void StringBuilder::allocateBuffer(const LChar* currentCharacters, unsigned requiredLength)
110{
111 ASSERT(!hasOverflowed());
112 ASSERT(m_is8Bit);
113 // Copy the existing data into a new buffer, set result to point to the end of the existing data.
114 auto buffer = StringImpl::tryCreateUninitialized(requiredLength, m_bufferCharacters8);
115 if (UNLIKELY(!buffer))
116 return didOverflow();
117 memcpy(m_bufferCharacters8, currentCharacters, static_cast<size_t>(m_length.unsafeGet()) * sizeof(LChar)); // This can't overflow.
118
119 // Update the builder state.
120 m_buffer = WTFMove(buffer);
121 m_string = String();
122 ASSERT(m_buffer->length() == requiredLength);
123}
124
125// Allocate a new 16 bit buffer, copying in currentCharacters (these may come from either m_string
126// or m_buffer, neither will be reassigned until the copy has completed).
127void StringBuilder::allocateBuffer(const UChar* currentCharacters, unsigned requiredLength)
128{
129 ASSERT(!hasOverflowed());
130 ASSERT(!m_is8Bit);
131 // Copy the existing data into a new buffer, set result to point to the end of the existing data.
132 auto buffer = StringImpl::tryCreateUninitialized(requiredLength, m_bufferCharacters16);
133 if (UNLIKELY(!buffer))
134 return didOverflow();
135 memcpy(m_bufferCharacters16, currentCharacters, static_cast<size_t>(m_length.unsafeGet()) * sizeof(UChar)); // This can't overflow.
136
137 // Update the builder state.
138 m_buffer = WTFMove(buffer);
139 m_string = String();
140 ASSERT(m_buffer->length() == requiredLength);
141}
142
143// Allocate a new 16 bit buffer, copying in currentCharacters (which is 8 bit and may come
144// from either m_string or m_buffer, neither will be reassigned until the copy has completed).
145void StringBuilder::allocateBufferUpConvert(const LChar* currentCharacters, unsigned requiredLength)
146{
147 ASSERT(!hasOverflowed());
148 ASSERT(m_is8Bit);
149 unsigned length = m_length.unsafeGet();
150 ASSERT(requiredLength <= maxCapacity && requiredLength >= length);
151 // Copy the existing data into a new buffer, set result to point to the end of the existing data.
152 auto buffer = StringImpl::tryCreateUninitialized(requiredLength, m_bufferCharacters16);
153 if (UNLIKELY(!buffer))
154 return didOverflow(); // Treat a failure to allcoate as an overflow.
155 for (unsigned i = 0; i < length; ++i)
156 m_bufferCharacters16[i] = currentCharacters[i];
157
158 m_is8Bit = false;
159
160 // Update the builder state.
161 m_buffer = WTFMove(buffer);
162 m_string = String();
163 ASSERT(m_buffer->length() == requiredLength);
164}
165
166template <>
167void StringBuilder::reallocateBuffer<LChar>(unsigned requiredLength)
168{
169 // If the buffer has only one ref (by this StringBuilder), reallocate it,
170 // otherwise fall back to "allocate and copy" method.
171 m_string = String();
172
173 ASSERT(m_is8Bit);
174 ASSERT(m_buffer->is8Bit());
175
176 if (m_buffer->hasOneRef()) {
177 auto expectedStringImpl = StringImpl::tryReallocate(m_buffer.releaseNonNull(), requiredLength, m_bufferCharacters8);
178 if (UNLIKELY(!expectedStringImpl))
179 return didOverflow();
180 m_buffer = WTFMove(expectedStringImpl.value());
181 } else
182 allocateBuffer(m_buffer->characters8(), requiredLength);
183 ASSERT(hasOverflowed() || m_buffer->length() == requiredLength);
184}
185
186template <>
187void StringBuilder::reallocateBuffer<UChar>(unsigned requiredLength)
188{
189 // If the buffer has only one ref (by this StringBuilder), reallocate it,
190 // otherwise fall back to "allocate and copy" method.
191 m_string = String();
192
193 if (m_buffer->is8Bit())
194 allocateBufferUpConvert(m_buffer->characters8(), requiredLength);
195 else if (m_buffer->hasOneRef()) {
196 auto expectedStringImpl = StringImpl::tryReallocate(m_buffer.releaseNonNull(), requiredLength, m_bufferCharacters16);
197 if (UNLIKELY(!expectedStringImpl))
198 return didOverflow();
199 m_buffer = WTFMove(expectedStringImpl.value());
200 } else
201 allocateBuffer(m_buffer->characters16(), requiredLength);
202 ASSERT(hasOverflowed() || m_buffer->length() == requiredLength);
203}
204
205void StringBuilder::reserveCapacity(unsigned newCapacity)
206{
207 if (hasOverflowed())
208 return;
209 ASSERT(newCapacity <= String::MaxLength);
210 if (m_buffer) {
211 // If there is already a buffer, then grow if necessary.
212 if (newCapacity > m_buffer->length()) {
213 if (m_buffer->is8Bit())
214 reallocateBuffer<LChar>(newCapacity);
215 else
216 reallocateBuffer<UChar>(newCapacity);
217 }
218 } else {
219 // Grow the string, if necessary.
220 unsigned length = m_length.unsafeGet();
221 if (newCapacity > length) {
222 if (!length) {
223 LChar* nullPlaceholder = nullptr;
224 allocateBuffer(nullPlaceholder, newCapacity);
225 } else if (m_string.is8Bit())
226 allocateBuffer(m_string.characters8(), newCapacity);
227 else
228 allocateBuffer(m_string.characters16(), newCapacity);
229 }
230 }
231 ASSERT(hasOverflowed() || !newCapacity || m_buffer->length() >= newCapacity);
232}
233
234// Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
235// return a pointer to the newly allocated storage.
236// Returns nullptr if the size of the new builder would have overflowed
237template <typename CharType>
238ALWAYS_INLINE CharType* StringBuilder::appendUninitialized(unsigned length)
239{
240 ASSERT(length);
241
242 // Calculate the new size of the builder after appending.
243 CheckedInt32 requiredLength = m_length + length;
244 if (requiredLength.hasOverflowed()) {
245 didOverflow();
246 return nullptr;
247 }
248
249 if (m_buffer && (requiredLength.unsafeGet<unsigned>() <= m_buffer->length())) {
250 // If the buffer is valid it must be at least as long as the current builder contents!
251 ASSERT(m_buffer->length() >= m_length.unsafeGet<unsigned>());
252 unsigned currentLength = m_length.unsafeGet();
253 m_string = String();
254 m_length = requiredLength;
255 return getBufferCharacters<CharType>() + currentLength;
256 }
257
258 return appendUninitializedSlow<CharType>(requiredLength.unsafeGet());
259}
260
261// Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
262// return a pointer to the newly allocated storage.
263template <typename CharType>
264CharType* StringBuilder::appendUninitializedSlow(unsigned requiredLength)
265{
266 ASSERT(!hasOverflowed());
267 ASSERT(requiredLength);
268
269 if (m_buffer) {
270 // If the buffer is valid it must be at least as long as the current builder contents!
271 ASSERT(m_buffer->length() >= m_length.unsafeGet<unsigned>());
272
273 reallocateBuffer<CharType>(expandedCapacity(capacity(), requiredLength));
274 } else {
275 ASSERT(m_string.length() == m_length.unsafeGet<unsigned>());
276 allocateBuffer(m_length ? m_string.characters<CharType>() : nullptr, expandedCapacity(capacity(), requiredLength));
277 }
278 if (UNLIKELY(hasOverflowed()))
279 return nullptr;
280
281 CharType* result = getBufferCharacters<CharType>() + m_length.unsafeGet();
282 m_length = requiredLength;
283 ASSERT(!hasOverflowed());
284 ASSERT(m_buffer->length() >= m_length.unsafeGet<unsigned>());
285 return result;
286}
287
288void StringBuilder::append(const UChar* characters, unsigned length)
289{
290 if (!length || hasOverflowed())
291 return;
292
293 ASSERT(characters);
294
295 if (m_is8Bit) {
296 if (length == 1 && !(*characters & ~0xff)) {
297 // Append as 8 bit character
298 LChar lChar = static_cast<LChar>(*characters);
299 return append(&lChar, 1);
300 }
301
302 // Calculate the new size of the builder after appending.
303 CheckedInt32 requiredLength = m_length + length;
304 if (requiredLength.hasOverflowed())
305 return didOverflow();
306
307 if (m_buffer) {
308 // If the buffer is valid it must be at least as long as the current builder contents!
309 ASSERT(m_buffer->length() >= m_length.unsafeGet<unsigned>());
310 allocateBufferUpConvert(m_buffer->characters8(), expandedCapacity(capacity(), requiredLength.unsafeGet()));
311 } else {
312 ASSERT(m_string.length() == m_length.unsafeGet<unsigned>());
313 allocateBufferUpConvert(m_string.isNull() ? nullptr : m_string.characters8(), expandedCapacity(capacity(), requiredLength.unsafeGet()));
314 }
315 if (UNLIKELY(hasOverflowed()))
316 return;
317
318 memcpy(m_bufferCharacters16 + m_length.unsafeGet<unsigned>(), characters, static_cast<size_t>(length) * sizeof(UChar));
319 m_length = requiredLength;
320 } else {
321 UChar* dest = appendUninitialized<UChar>(length);
322 if (!dest)
323 return;
324 memcpy(dest, characters, static_cast<size_t>(length) * sizeof(UChar));
325 }
326 ASSERT(!hasOverflowed());
327 ASSERT(m_buffer->length() >= m_length.unsafeGet<unsigned>());
328}
329
330void StringBuilder::append(const LChar* characters, unsigned length)
331{
332 if (!length || hasOverflowed())
333 return;
334
335 ASSERT(characters);
336
337 if (m_is8Bit) {
338 LChar* dest = appendUninitialized<LChar>(length);
339 if (!dest) {
340 ASSERT(hasOverflowed());
341 return;
342 }
343 if (length > 8)
344 memcpy(dest, characters, static_cast<size_t>(length) * sizeof(LChar));
345 else {
346 const LChar* end = characters + length;
347 while (characters < end)
348 *(dest++) = *(characters++);
349 }
350 } else {
351 UChar* dest = appendUninitialized<UChar>(length);
352 if (!dest) {
353 ASSERT(hasOverflowed());
354 return;
355 }
356 const LChar* end = characters + length;
357 while (characters < end)
358 *(dest++) = *(characters++);
359 }
360}
361
362#if USE(CF)
363
364void StringBuilder::append(CFStringRef string)
365{
366 // Fast path: avoid constructing a temporary String when possible.
367 if (auto* characters = CFStringGetCStringPtr(string, kCFStringEncodingISOLatin1)) {
368 append(reinterpret_cast<const LChar*>(characters), CFStringGetLength(string));
369 return;
370 }
371 append(String(string));
372}
373
374#endif
375
376void StringBuilder::appendNumber(int number)
377{
378 numberToStringSigned<StringBuilder>(number, this);
379}
380
381void StringBuilder::appendNumber(unsigned number)
382{
383 numberToStringUnsigned<StringBuilder>(number, this);
384}
385
386void StringBuilder::appendNumber(long number)
387{
388 numberToStringSigned<StringBuilder>(number, this);
389}
390
391void StringBuilder::appendNumber(unsigned long number)
392{
393 numberToStringUnsigned<StringBuilder>(number, this);
394}
395
396void StringBuilder::appendNumber(long long number)
397{
398 numberToStringSigned<StringBuilder>(number, this);
399}
400
401void StringBuilder::appendNumber(unsigned long long number)
402{
403 numberToStringUnsigned<StringBuilder>(number, this);
404}
405
406void StringBuilder::appendFixedPrecisionNumber(float number, unsigned precision, TrailingZerosTruncatingPolicy policy)
407{
408 NumberToStringBuffer buffer;
409 append(numberToFixedPrecisionString(number, precision, buffer, policy == TruncateTrailingZeros));
410}
411
412void StringBuilder::appendFixedPrecisionNumber(double number, unsigned precision, TrailingZerosTruncatingPolicy policy)
413{
414 NumberToStringBuffer buffer;
415 append(numberToFixedPrecisionString(number, precision, buffer, policy == TruncateTrailingZeros));
416}
417
418void StringBuilder::appendNumber(float number)
419{
420 NumberToStringBuffer buffer;
421 append(numberToString(number, buffer));
422}
423
424void StringBuilder::appendNumber(double number)
425{
426 NumberToStringBuffer buffer;
427 append(numberToString(number, buffer));
428}
429
430void StringBuilder::appendFixedWidthNumber(float number, unsigned decimalPlaces)
431{
432 NumberToStringBuffer buffer;
433 append(numberToFixedWidthString(number, decimalPlaces, buffer));
434}
435
436void StringBuilder::appendFixedWidthNumber(double number, unsigned decimalPlaces)
437{
438 NumberToStringBuffer buffer;
439 append(numberToFixedWidthString(number, decimalPlaces, buffer));
440}
441
442bool StringBuilder::canShrink() const
443{
444 if (hasOverflowed())
445 return false;
446 // Only shrink the buffer if it's less than 80% full. Need to tune this heuristic!
447 unsigned length = m_length.unsafeGet();
448 return m_buffer && m_buffer->length() > (length + (length >> 2));
449}
450
451void StringBuilder::shrinkToFit()
452{
453 if (canShrink()) {
454 if (m_is8Bit)
455 reallocateBuffer<LChar>(m_length.unsafeGet());
456 else
457 reallocateBuffer<UChar>(m_length.unsafeGet());
458 ASSERT(!hasOverflowed());
459 m_string = WTFMove(m_buffer);
460 }
461}
462
463} // namespace WTF
464