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