Remove all uses of PassRefPtr in WTF
[WebKit-https.git] / Source / WTF / wtf / text / StringBuilder.cpp
1 /*
2  * Copyright (C) 2010, 2013 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         return;
84     }
85
86     // Since m_length && !m_buffer, the string must be valid in m_string, and m_string.length() > 0.
87     ASSERT(!m_string.isEmpty());
88     ASSERT(m_length == m_string.length());
89     ASSERT(newSize < m_string.length());
90     m_length = newSize;
91     m_string = StringImpl::createSubstringSharingImpl(*m_string.impl(), 0, newSize);
92 }
93
94 // Allocate a new 8 bit buffer, copying in currentCharacters (these may come from either m_string
95 // or m_buffer, neither will be reassigned until the copy has completed).
96 void StringBuilder::allocateBuffer(const LChar* currentCharacters, unsigned requiredLength)
97 {
98     ASSERT(m_is8Bit);
99     // Copy the existing data into a new buffer, set result to point to the end of the existing data.
100     auto buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters8);
101     memcpy(m_bufferCharacters8, currentCharacters, static_cast<size_t>(m_length) * sizeof(LChar)); // This can't overflow.
102     
103     // Update the builder state.
104     m_buffer = WTFMove(buffer);
105     m_string = String();
106 }
107
108 // Allocate a new 16 bit buffer, copying in currentCharacters (these may come from either m_string
109 // or m_buffer,  neither will be reassigned until the copy has completed).
110 void StringBuilder::allocateBuffer(const UChar* currentCharacters, unsigned requiredLength)
111 {
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::createUninitialized(requiredLength, m_bufferCharacters16);
115     memcpy(m_bufferCharacters16, currentCharacters, static_cast<size_t>(m_length) * sizeof(UChar)); // This can't overflow.
116     
117     // Update the builder state.
118     m_buffer = WTFMove(buffer);
119     m_string = String();
120 }
121
122 // Allocate a new 16 bit buffer, copying in currentCharacters (which is 8 bit and may come
123 // from either m_string or m_buffer, neither will be reassigned until the copy has completed).
124 void StringBuilder::allocateBufferUpConvert(const LChar* currentCharacters, unsigned requiredLength)
125 {
126     ASSERT(m_is8Bit);
127     // Copy the existing data into a new buffer, set result to point to the end of the existing data.
128     auto buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters16);
129     for (unsigned i = 0; i < m_length; ++i)
130         m_bufferCharacters16[i] = currentCharacters[i];
131     
132     m_is8Bit = false;
133     
134     // Update the builder state.
135     m_buffer = WTFMove(buffer);
136     m_string = String();
137 }
138
139 template <>
140 void StringBuilder::reallocateBuffer<LChar>(unsigned requiredLength)
141 {
142     // If the buffer has only one ref (by this StringBuilder), reallocate it,
143     // otherwise fall back to "allocate and copy" method.
144     m_string = String();
145     
146     ASSERT(m_is8Bit);
147     ASSERT(m_buffer->is8Bit());
148     
149     if (m_buffer->hasOneRef())
150         m_buffer = StringImpl::reallocate(m_buffer.releaseNonNull(), requiredLength, m_bufferCharacters8);
151     else
152         allocateBuffer(m_buffer->characters8(), requiredLength);
153 }
154
155 template <>
156 void StringBuilder::reallocateBuffer<UChar>(unsigned requiredLength)
157 {
158     // If the buffer has only one ref (by this StringBuilder), reallocate it,
159     // otherwise fall back to "allocate and copy" method.
160     m_string = String();
161     
162     if (m_buffer->is8Bit())
163         allocateBufferUpConvert(m_buffer->characters8(), requiredLength);
164     else if (m_buffer->hasOneRef())
165         m_buffer = StringImpl::reallocate(m_buffer.releaseNonNull(), requiredLength, m_bufferCharacters16);
166     else
167         allocateBuffer(m_buffer->characters16(), requiredLength);
168 }
169
170 void StringBuilder::reserveCapacity(unsigned newCapacity)
171 {
172     if (m_buffer) {
173         // If there is already a buffer, then grow if necessary.
174         if (newCapacity > m_buffer->length()) {
175             if (m_buffer->is8Bit())
176                 reallocateBuffer<LChar>(newCapacity);
177             else
178                 reallocateBuffer<UChar>(newCapacity);
179         }
180     } else {
181         // Grow the string, if necessary.
182         if (newCapacity > m_length) {
183             if (!m_length) {
184                 LChar* nullPlaceholder = 0;
185                 allocateBuffer(nullPlaceholder, newCapacity);
186             } else if (m_string.is8Bit())
187                 allocateBuffer(m_string.characters8(), newCapacity);
188             else
189                 allocateBuffer(m_string.characters16(), newCapacity);
190         }
191     }
192 }
193
194 // Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
195 // return a pointer to the newly allocated storage.
196 template <typename CharType>
197 ALWAYS_INLINE CharType* StringBuilder::appendUninitialized(unsigned length)
198 {
199     ASSERT(length);
200
201     // Calculate the new size of the builder after appending.
202     unsigned requiredLength = length + m_length;
203     if (requiredLength < length)
204         CRASH();
205
206     if ((m_buffer) && (requiredLength <= m_buffer->length())) {
207         // If the buffer is valid it must be at least as long as the current builder contents!
208         ASSERT(m_buffer->length() >= m_length);
209         unsigned currentLength = m_length;
210         m_string = String();
211         m_length = requiredLength;
212         return getBufferCharacters<CharType>() + currentLength;
213     }
214     
215     return appendUninitializedSlow<CharType>(requiredLength);
216 }
217
218 // Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
219 // return a pointer to the newly allocated storage.
220 template <typename CharType>
221 CharType* StringBuilder::appendUninitializedSlow(unsigned requiredLength)
222 {
223     ASSERT(requiredLength);
224
225     if (m_buffer) {
226         // If the buffer is valid it must be at least as long as the current builder contents!
227         ASSERT(m_buffer->length() >= m_length);
228         
229         reallocateBuffer<CharType>(expandedCapacity(capacity(), requiredLength));
230     } else {
231         ASSERT(m_string.length() == m_length);
232         allocateBuffer(m_length ? m_string.characters<CharType>() : 0, expandedCapacity(capacity(), requiredLength));
233     }
234     
235     CharType* result = getBufferCharacters<CharType>() + m_length;
236     m_length = requiredLength;
237     return result;
238 }
239
240 void StringBuilder::append(const UChar* characters, unsigned length)
241 {
242     if (!length)
243         return;
244
245     ASSERT(characters);
246
247     if (m_is8Bit) {
248         if (length == 1 && !(*characters & ~0xff)) {
249             // Append as 8 bit character
250             LChar lChar = static_cast<LChar>(*characters);
251             append(&lChar, 1);
252             return;
253         }
254
255         // Calculate the new size of the builder after appending.
256         unsigned requiredLength = length + m_length;
257         if (requiredLength < length)
258             CRASH();
259         
260         if (m_buffer) {
261             // If the buffer is valid it must be at least as long as the current builder contents!
262             ASSERT(m_buffer->length() >= m_length);
263             
264             allocateBufferUpConvert(m_buffer->characters8(), expandedCapacity(capacity(), requiredLength));
265         } else {
266             ASSERT(m_string.length() == m_length);
267             allocateBufferUpConvert(m_string.isNull() ? 0 : m_string.characters8(), expandedCapacity(capacity(), requiredLength));
268         }
269
270         memcpy(m_bufferCharacters16 + m_length, characters, static_cast<size_t>(length) * sizeof(UChar));        
271         m_length = requiredLength;
272     } else
273         memcpy(appendUninitialized<UChar>(length), characters, static_cast<size_t>(length) * sizeof(UChar));
274 }
275
276 void StringBuilder::append(const LChar* characters, unsigned length)
277 {
278     if (!length)
279         return;
280     ASSERT(characters);
281
282     if (m_is8Bit) {
283         LChar* dest = appendUninitialized<LChar>(length);
284         if (length > 8)
285             memcpy(dest, characters, static_cast<size_t>(length) * sizeof(LChar));
286         else {
287             const LChar* end = characters + length;
288             while (characters < end)
289                 *(dest++) = *(characters++);
290         }
291     } else {
292         UChar* dest = appendUninitialized<UChar>(length);
293         const LChar* end = characters + length;
294         while (characters < end)
295             *(dest++) = *(characters++);
296     }
297 }
298
299 void StringBuilder::appendNumber(int number)
300 {
301     numberToStringSigned<StringBuilder>(number, this);
302 }
303
304 void StringBuilder::appendNumber(unsigned int number)
305 {
306     numberToStringUnsigned<StringBuilder>(number, this);
307 }
308
309 void StringBuilder::appendNumber(long number)
310 {
311     numberToStringSigned<StringBuilder>(number, this);
312 }
313
314 void StringBuilder::appendNumber(unsigned long number)
315 {
316     numberToStringUnsigned<StringBuilder>(number, this);
317 }
318
319 void StringBuilder::appendNumber(long long number)
320 {
321     numberToStringSigned<StringBuilder>(number, this);
322 }
323
324 void StringBuilder::appendNumber(unsigned long long number)
325 {
326     numberToStringUnsigned<StringBuilder>(number, this);
327 }
328
329 void StringBuilder::appendNumber(double number, unsigned precision, TrailingZerosTruncatingPolicy trailingZerosTruncatingPolicy)
330 {
331     NumberToStringBuffer buffer;
332     append(numberToFixedPrecisionString(number, precision, buffer, trailingZerosTruncatingPolicy == TruncateTrailingZeros));
333 }
334
335 void StringBuilder::appendECMAScriptNumber(double number)
336 {
337     NumberToStringBuffer buffer;
338     append(numberToString(number, buffer));
339 }
340
341 void StringBuilder::appendFixedWidthNumber(double number, unsigned decimalPlaces)
342 {
343     NumberToStringBuffer buffer;
344     append(numberToFixedWidthString(number, decimalPlaces, buffer));
345 }
346
347 bool StringBuilder::canShrink() const
348 {
349     // Only shrink the buffer if it's less than 80% full. Need to tune this heuristic!
350     return m_buffer && m_buffer->length() > (m_length + (m_length >> 2));
351 }
352
353 void StringBuilder::shrinkToFit()
354 {
355     if (canShrink()) {
356         if (m_is8Bit)
357             reallocateBuffer<LChar>(m_length);
358         else
359             reallocateBuffer<UChar>(m_length);
360         m_string = WTFMove(m_buffer);
361     }
362 }
363
364 template <typename OutputCharacterType, typename InputCharacterType>
365 static void appendQuotedJSONStringInternal(OutputCharacterType*& output, const InputCharacterType* input, unsigned length)
366 {
367     for (const InputCharacterType* end = input + length; input != end; ++input) {
368         if (LIKELY(*input > 0x1F)) {
369             if (*input == '"' || *input == '\\')
370                 *output++ = '\\';
371             *output++ = *input;
372             continue;
373         }
374         switch (*input) {
375         case '\t':
376             *output++ = '\\';
377             *output++ = 't';
378             break;
379         case '\r':
380             *output++ = '\\';
381             *output++ = 'r';
382             break;
383         case '\n':
384             *output++ = '\\';
385             *output++ = 'n';
386             break;
387         case '\f':
388             *output++ = '\\';
389             *output++ = 'f';
390             break;
391         case '\b':
392             *output++ = '\\';
393             *output++ = 'b';
394             break;
395         default:
396             ASSERT((*input & 0xFF00) == 0);
397             static const char hexDigits[] = "0123456789abcdef";
398             *output++ = '\\';
399             *output++ = 'u';
400             *output++ = '0';
401             *output++ = '0';
402             *output++ = static_cast<LChar>(hexDigits[(*input >> 4) & 0xF]);
403             *output++ = static_cast<LChar>(hexDigits[*input & 0xF]);
404             break;
405         }
406     }
407 }
408
409 void StringBuilder::appendQuotedJSONString(const String& string)
410 {
411     // Make sure we have enough buffer space to append this string without having
412     // to worry about reallocating in the middle.
413     // The 2 is for the '"' quotes on each end.
414     // The 6 is for characters that need to be \uNNNN encoded.
415     size_t maximumCapacityRequired = length() + 2 + string.length() * 6;
416     RELEASE_ASSERT(maximumCapacityRequired < std::numeric_limits<unsigned>::max());
417     unsigned allocationSize = maximumCapacityRequired;
418     // 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.
419     allocationSize = std::max(allocationSize, roundUpToPowerOfTwo(allocationSize));
420
421     if (is8Bit() && !string.is8Bit())
422         allocateBufferUpConvert(m_bufferCharacters8, allocationSize);
423     else
424         reserveCapacity(allocationSize);
425
426     if (is8Bit()) {
427         ASSERT(string.is8Bit());
428         LChar* output = m_bufferCharacters8 + m_length;
429         *output++ = '"';
430         appendQuotedJSONStringInternal(output, string.characters8(), string.length());
431         *output++ = '"';
432         m_length = output - m_bufferCharacters8;
433     } else {
434         UChar* output = m_bufferCharacters16 + m_length;
435         *output++ = '"';
436         if (string.is8Bit())
437             appendQuotedJSONStringInternal(output, string.characters8(), string.length());
438         else
439             appendQuotedJSONStringInternal(output, string.characters16(), string.length());
440         *output++ = '"';
441         m_length = output - m_bufferCharacters16;
442     }
443 }
444
445 } // namespace WTF