afe1341928a70aff8b8c0170c246aa155862eba8
[WebKit-https.git] / Source / WTF / wtf / text / StringBuilder.cpp
1 /*
2  * Copyright (C) 2010, 2013, 2016 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 "StringBuilder.h"
29
30 #include "IntegerToStringConversion.h"
31 #include "MathExtras.h"
32 #include "WTFString.h"
33 #include <wtf/dtoa.h>
34
35 namespace WTF {
36
37 static unsigned expandedCapacity(unsigned capacity, unsigned requiredLength)
38 {
39     static const unsigned minimumCapacity = 16;
40     return std::max(requiredLength, std::max(minimumCapacity, capacity * 2));
41 }
42
43 void StringBuilder::reifyString() const
44 {
45     // Check if the string already exists.
46     if (!m_string.isNull()) {
47         ASSERT(m_string.length() == m_length);
48         return;
49     }
50
51     // Check for empty.
52     if (!m_length) {
53         m_string = StringImpl::empty();
54         return;
55     }
56
57     // Must be valid in the buffer, take a substring (unless string fills the buffer).
58     ASSERT(m_buffer && m_length <= m_buffer->length());
59     if (m_length == m_buffer->length())
60         m_string = m_buffer.get();
61     else
62         m_string = StringImpl::createSubstringSharingImpl(*m_buffer, 0, m_length);
63 }
64
65 void StringBuilder::resize(unsigned newSize)
66 {
67     // Check newSize < m_length, hence m_length > 0.
68     ASSERT(newSize <= m_length);
69     if (newSize == m_length)
70         return;
71     ASSERT(m_length);
72
73     // If there is a buffer, we only need to duplicate it if it has more than one ref.
74     if (m_buffer) {
75         m_string = String(); // Clear the string to remove the reference to m_buffer if any before checking the reference count of m_buffer.
76         if (!m_buffer->hasOneRef()) {
77             if (m_buffer->is8Bit())
78                 allocateBuffer(m_buffer->characters8(), m_buffer->length());
79             else
80                 allocateBuffer(m_buffer->characters16(), m_buffer->length());
81         }
82         m_length = newSize;
83         ASSERT(m_buffer->length() >= m_length);
84         return;
85     }
86
87     // Since m_length && !m_buffer, the string must be valid in m_string, and m_string.length() > 0.
88     ASSERT(!m_string.isEmpty());
89     ASSERT(m_length == m_string.length());
90     ASSERT(newSize < m_string.length());
91     m_length = newSize;
92     m_string = StringImpl::createSubstringSharingImpl(*m_string.impl(), 0, newSize);
93 }
94
95 // Allocate a new 8 bit buffer, copying in currentCharacters (these may come from either m_string
96 // or m_buffer, neither will be reassigned until the copy has completed).
97 void StringBuilder::allocateBuffer(const LChar* currentCharacters, unsigned requiredLength)
98 {
99     ASSERT(m_is8Bit);
100     // Copy the existing data into a new buffer, set result to point to the end of the existing data.
101     auto buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters8);
102     memcpy(m_bufferCharacters8, currentCharacters, static_cast<size_t>(m_length) * sizeof(LChar)); // This can't overflow.
103     
104     // Update the builder state.
105     m_buffer = WTFMove(buffer);
106     m_string = String();
107     ASSERT(m_buffer->length() == requiredLength);
108 }
109
110 // Allocate a new 16 bit buffer, copying in currentCharacters (these may come from either m_string
111 // or m_buffer,  neither will be reassigned until the copy has completed).
112 void StringBuilder::allocateBuffer(const UChar* currentCharacters, unsigned requiredLength)
113 {
114     ASSERT(!m_is8Bit);
115     // Copy the existing data into a new buffer, set result to point to the end of the existing data.
116     auto buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters16);
117     memcpy(m_bufferCharacters16, currentCharacters, static_cast<size_t>(m_length) * sizeof(UChar)); // 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 (which is 8 bit and may come
126 // from either m_string or m_buffer, neither will be reassigned until the copy has completed).
127 void StringBuilder::allocateBufferUpConvert(const LChar* currentCharacters, unsigned requiredLength)
128 {
129     ASSERT(m_is8Bit);
130     ASSERT(requiredLength >= m_length);
131     // Copy the existing data into a new buffer, set result to point to the end of the existing data.
132     auto buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters16);
133     for (unsigned i = 0; i < m_length; ++i)
134         m_bufferCharacters16[i] = currentCharacters[i];
135     
136     m_is8Bit = false;
137     
138     // Update the builder state.
139     m_buffer = WTFMove(buffer);
140     m_string = String();
141     ASSERT(m_buffer->length() == requiredLength);
142 }
143
144 template <>
145 void StringBuilder::reallocateBuffer<LChar>(unsigned requiredLength)
146 {
147     // If the buffer has only one ref (by this StringBuilder), reallocate it,
148     // otherwise fall back to "allocate and copy" method.
149     m_string = String();
150     
151     ASSERT(m_is8Bit);
152     ASSERT(m_buffer->is8Bit());
153     
154     if (m_buffer->hasOneRef())
155         m_buffer = StringImpl::reallocate(m_buffer.releaseNonNull(), requiredLength, m_bufferCharacters8);
156     else
157         allocateBuffer(m_buffer->characters8(), requiredLength);
158     ASSERT(m_buffer->length() == requiredLength);
159 }
160
161 template <>
162 void StringBuilder::reallocateBuffer<UChar>(unsigned requiredLength)
163 {
164     // If the buffer has only one ref (by this StringBuilder), reallocate it,
165     // otherwise fall back to "allocate and copy" method.
166     m_string = String();
167     
168     if (m_buffer->is8Bit())
169         allocateBufferUpConvert(m_buffer->characters8(), requiredLength);
170     else if (m_buffer->hasOneRef())
171         m_buffer = StringImpl::reallocate(m_buffer.releaseNonNull(), requiredLength, m_bufferCharacters16);
172     else
173         allocateBuffer(m_buffer->characters16(), requiredLength);
174     ASSERT(m_buffer->length() == requiredLength);
175 }
176
177 void StringBuilder::reserveCapacity(unsigned newCapacity)
178 {
179     if (m_buffer) {
180         // If there is already a buffer, then grow if necessary.
181         if (newCapacity > m_buffer->length()) {
182             if (m_buffer->is8Bit())
183                 reallocateBuffer<LChar>(newCapacity);
184             else
185                 reallocateBuffer<UChar>(newCapacity);
186         }
187     } else {
188         // Grow the string, if necessary.
189         if (newCapacity > m_length) {
190             if (!m_length) {
191                 LChar* nullPlaceholder = 0;
192                 allocateBuffer(nullPlaceholder, newCapacity);
193             } else if (m_string.is8Bit())
194                 allocateBuffer(m_string.characters8(), newCapacity);
195             else
196                 allocateBuffer(m_string.characters16(), newCapacity);
197         }
198     }
199     ASSERT(!newCapacity || m_buffer->length() >= newCapacity);
200 }
201
202 // Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
203 // return a pointer to the newly allocated storage.
204 template <typename CharType>
205 ALWAYS_INLINE CharType* StringBuilder::appendUninitialized(unsigned length)
206 {
207     ASSERT(length);
208
209     // Calculate the new size of the builder after appending.
210     unsigned requiredLength = length + m_length;
211     if (requiredLength < length)
212         CRASH();
213
214     if ((m_buffer) && (requiredLength <= m_buffer->length())) {
215         // If the buffer is valid it must be at least as long as the current builder contents!
216         ASSERT(m_buffer->length() >= m_length);
217         unsigned currentLength = m_length;
218         m_string = String();
219         m_length = requiredLength;
220         return getBufferCharacters<CharType>() + currentLength;
221     }
222     
223     return appendUninitializedSlow<CharType>(requiredLength);
224 }
225
226 // Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
227 // return a pointer to the newly allocated storage.
228 template <typename CharType>
229 CharType* StringBuilder::appendUninitializedSlow(unsigned requiredLength)
230 {
231     ASSERT(requiredLength);
232
233     if (m_buffer) {
234         // If the buffer is valid it must be at least as long as the current builder contents!
235         ASSERT(m_buffer->length() >= m_length);
236         
237         reallocateBuffer<CharType>(expandedCapacity(capacity(), requiredLength));
238     } else {
239         ASSERT(m_string.length() == m_length);
240         allocateBuffer(m_length ? m_string.characters<CharType>() : 0, expandedCapacity(capacity(), requiredLength));
241     }
242     
243     CharType* result = getBufferCharacters<CharType>() + m_length;
244     m_length = requiredLength;
245     ASSERT(m_buffer->length() >= m_length);
246     return result;
247 }
248
249 void StringBuilder::append(const UChar* characters, unsigned length)
250 {
251     if (!length)
252         return;
253
254     ASSERT(characters);
255
256     if (m_is8Bit) {
257         if (length == 1 && !(*characters & ~0xff)) {
258             // Append as 8 bit character
259             LChar lChar = static_cast<LChar>(*characters);
260             append(&lChar, 1);
261             return;
262         }
263
264         // Calculate the new size of the builder after appending.
265         unsigned requiredLength = length + m_length;
266         if (requiredLength < length)
267             CRASH();
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);
272             
273             allocateBufferUpConvert(m_buffer->characters8(), expandedCapacity(capacity(), requiredLength));
274         } else {
275             ASSERT(m_string.length() == m_length);
276             allocateBufferUpConvert(m_string.isNull() ? 0 : m_string.characters8(), expandedCapacity(capacity(), requiredLength));
277         }
278
279         memcpy(m_bufferCharacters16 + m_length, characters, static_cast<size_t>(length) * sizeof(UChar));
280         m_length = requiredLength;
281     } else
282         memcpy(appendUninitialized<UChar>(length), characters, static_cast<size_t>(length) * sizeof(UChar));
283     ASSERT(m_buffer->length() >= m_length);
284 }
285
286 void StringBuilder::append(const LChar* characters, unsigned length)
287 {
288     if (!length)
289         return;
290     ASSERT(characters);
291
292     if (m_is8Bit) {
293         LChar* dest = appendUninitialized<LChar>(length);
294         if (length > 8)
295             memcpy(dest, characters, static_cast<size_t>(length) * sizeof(LChar));
296         else {
297             const LChar* end = characters + length;
298             while (characters < end)
299                 *(dest++) = *(characters++);
300         }
301     } else {
302         UChar* dest = appendUninitialized<UChar>(length);
303         const LChar* end = characters + length;
304         while (characters < end)
305             *(dest++) = *(characters++);
306     }
307 }
308
309 #if USE(CF)
310
311 void StringBuilder::append(CFStringRef string)
312 {
313     // Fast path: avoid constructing a temporary String when possible.
314     if (auto* characters = CFStringGetCStringPtr(string, kCFStringEncodingISOLatin1)) {
315         append(reinterpret_cast<const LChar*>(characters), CFStringGetLength(string));
316         return;
317     }
318     append(String(string));
319 }
320
321 #endif
322
323 void StringBuilder::appendNumber(int number)
324 {
325     numberToStringSigned<StringBuilder>(number, this);
326 }
327
328 void StringBuilder::appendNumber(unsigned int number)
329 {
330     numberToStringUnsigned<StringBuilder>(number, this);
331 }
332
333 void StringBuilder::appendNumber(long number)
334 {
335     numberToStringSigned<StringBuilder>(number, this);
336 }
337
338 void StringBuilder::appendNumber(unsigned long number)
339 {
340     numberToStringUnsigned<StringBuilder>(number, this);
341 }
342
343 void StringBuilder::appendNumber(long long number)
344 {
345     numberToStringSigned<StringBuilder>(number, this);
346 }
347
348 void StringBuilder::appendNumber(unsigned long long number)
349 {
350     numberToStringUnsigned<StringBuilder>(number, this);
351 }
352
353 void StringBuilder::appendNumber(double number, unsigned precision, TrailingZerosTruncatingPolicy trailingZerosTruncatingPolicy)
354 {
355     NumberToStringBuffer buffer;
356     append(numberToFixedPrecisionString(number, precision, buffer, trailingZerosTruncatingPolicy == TruncateTrailingZeros));
357 }
358
359 void StringBuilder::appendECMAScriptNumber(double number)
360 {
361     NumberToStringBuffer buffer;
362     append(numberToString(number, buffer));
363 }
364
365 void StringBuilder::appendFixedWidthNumber(double number, unsigned decimalPlaces)
366 {
367     NumberToStringBuffer buffer;
368     append(numberToFixedWidthString(number, decimalPlaces, buffer));
369 }
370
371 bool StringBuilder::canShrink() const
372 {
373     // Only shrink the buffer if it's less than 80% full. Need to tune this heuristic!
374     return m_buffer && m_buffer->length() > (m_length + (m_length >> 2));
375 }
376
377 void StringBuilder::shrinkToFit()
378 {
379     if (canShrink()) {
380         if (m_is8Bit)
381             reallocateBuffer<LChar>(m_length);
382         else
383             reallocateBuffer<UChar>(m_length);
384         m_string = WTFMove(m_buffer);
385     }
386 }
387
388 template <typename OutputCharacterType, typename InputCharacterType>
389 static void appendQuotedJSONStringInternal(OutputCharacterType*& output, const InputCharacterType* input, unsigned length)
390 {
391     for (const InputCharacterType* end = input + length; input != end; ++input) {
392         if (LIKELY(*input > 0x1F)) {
393             if (*input == '"' || *input == '\\')
394                 *output++ = '\\';
395             *output++ = *input;
396             continue;
397         }
398         switch (*input) {
399         case '\t':
400             *output++ = '\\';
401             *output++ = 't';
402             break;
403         case '\r':
404             *output++ = '\\';
405             *output++ = 'r';
406             break;
407         case '\n':
408             *output++ = '\\';
409             *output++ = 'n';
410             break;
411         case '\f':
412             *output++ = '\\';
413             *output++ = 'f';
414             break;
415         case '\b':
416             *output++ = '\\';
417             *output++ = 'b';
418             break;
419         default:
420             ASSERT((*input & 0xFF00) == 0);
421             static const char hexDigits[] = "0123456789abcdef";
422             *output++ = '\\';
423             *output++ = 'u';
424             *output++ = '0';
425             *output++ = '0';
426             *output++ = static_cast<LChar>(hexDigits[(*input >> 4) & 0xF]);
427             *output++ = static_cast<LChar>(hexDigits[*input & 0xF]);
428             break;
429         }
430     }
431 }
432
433 void StringBuilder::appendQuotedJSONString(const String& string)
434 {
435     // Make sure we have enough buffer space to append this string without having
436     // to worry about reallocating in the middle.
437     // The 2 is for the '"' quotes on each end.
438     // The 6 is for characters that need to be \uNNNN encoded.
439     Checked<unsigned> stringLength = string.length();
440     Checked<unsigned> maximumCapacityRequired = length();
441     maximumCapacityRequired += 2 + stringLength * 6;
442     unsigned allocationSize = maximumCapacityRequired.unsafeGet();
443     // This max() is here to allow us to allocate sizes between the range [2^31, 2^32 - 2] because roundUpToPowerOfTwo(1<<31 + some int smaller than 1<<31) == 0.
444     allocationSize = std::max(allocationSize, roundUpToPowerOfTwo(allocationSize));
445
446     if (is8Bit() && !string.is8Bit())
447         allocateBufferUpConvert(m_bufferCharacters8, allocationSize);
448     else
449         reserveCapacity(allocationSize);
450     ASSERT(m_buffer->length() >= allocationSize);
451
452     if (is8Bit()) {
453         ASSERT(string.is8Bit());
454         LChar* output = m_bufferCharacters8 + m_length;
455         *output++ = '"';
456         appendQuotedJSONStringInternal(output, string.characters8(), string.length());
457         *output++ = '"';
458         m_length = output - m_bufferCharacters8;
459     } else {
460         UChar* output = m_bufferCharacters16 + m_length;
461         *output++ = '"';
462         if (string.is8Bit())
463             appendQuotedJSONStringInternal(output, string.characters8(), string.length());
464         else
465             appendQuotedJSONStringInternal(output, string.characters16(), string.length());
466         *output++ = '"';
467         m_length = output - m_bufferCharacters16;
468     }
469     ASSERT(m_buffer->length() >= m_length);
470 }
471
472 } // namespace WTF