1/*
2 * Copyright (C) 2010 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 "WTFString.h"
32#include "wtf/dtoa.h"
33
34namespace WTF {
35
36static 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
42void StringBuilder::reifyString()
43{
44    if (!m_string.isNull()) {
45        ASSERT(m_string.length() == m_length);
46        return;
47    }
48
49    if (!m_length) {
50        m_string = StringImpl::empty();
51        return;
52    }
53
54    ASSERT(m_buffer && m_length <= m_buffer->length());
55    if (m_length == m_buffer->length()) {
56        m_string = m_buffer.release();
57        return;
58    }
59
60    if (m_buffer->hasOneRef()) {
61        m_buffer->truncateAssumingIsolated(m_length);
62        m_string = m_buffer.release();
63        return;
64    }
65
66    m_string = m_buffer->substring(0, m_length);
67}
68
69String StringBuilder::reifySubstring(unsigned position, unsigned length) const
70{
71    ASSERT(m_string.isNull());
72    ASSERT(m_buffer);
73    unsigned substringLength = std::min(length, m_length - position);
74    return m_buffer->substring(position, substringLength);
75}
76
77void StringBuilder::resize(unsigned newSize)
78{
79    // Check newSize < m_length, hence m_length > 0.
80    ASSERT(newSize <= m_length);
81    if (newSize == m_length)
82        return;
83    ASSERT(m_length);
84
85    // If there is a buffer, we only need to duplicate it if it has more than one ref.
86    if (m_buffer) {
87        m_string = String(); // Clear the string to remove the reference to m_buffer if any before checking the reference count of m_buffer.
88        if (!m_buffer->hasOneRef()) {
89            if (m_buffer->is8Bit())
90                allocateBuffer(m_buffer->characters8(), m_buffer->length());
91            else
92                allocateBuffer(m_buffer->characters16(), m_buffer->length());
93        }
94        m_length = newSize;
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    RefPtr<StringImpl> string = m_string.releaseImpl();
104    if (string->hasOneRef()) {
105        // If we're the only ones with a reference to the string, we can
106        // re-purpose the string as m_buffer and continue mutating it.
107        m_buffer = string;
108    } else {
109        // Otherwise, we need to make a copy of the string so that we don't
110        // mutate a String that's held elsewhere.
111        m_buffer = string->substring(0, m_length);
112    }
113}
114
115// Allocate a new 8 bit buffer, copying in currentCharacters (these may come from either m_string
116// or m_buffer, neither will be reassigned until the copy has completed).
117void StringBuilder::allocateBuffer(const LChar* currentCharacters, unsigned requiredLength)
118{
119    ASSERT(m_is8Bit);
120    // Copy the existing data into a new buffer, set result to point to the end of the existing data.
121    RefPtr<StringImpl> buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters8);
122    memcpy(m_bufferCharacters8, currentCharacters, static_cast<size_t>(m_length) * sizeof(LChar)); // This can't overflow.
123
124    // Update the builder state.
125    m_buffer = buffer.release();
126    m_string = String();
127}
128
129// Allocate a new 16 bit buffer, copying in currentCharacters (these may come from either m_string
130// or m_buffer,  neither will be reassigned until the copy has completed).
131void StringBuilder::allocateBuffer(const UChar* currentCharacters, unsigned requiredLength)
132{
133    ASSERT(!m_is8Bit);
134    // Copy the existing data into a new buffer, set result to point to the end of the existing data.
135    RefPtr<StringImpl> buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters16);
136    memcpy(m_bufferCharacters16, currentCharacters, static_cast<size_t>(m_length) * sizeof(UChar)); // This can't overflow.
137
138    // Update the builder state.
139    m_buffer = buffer.release();
140    m_string = String();
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(m_is8Bit);
148    // Copy the existing data into a new buffer, set result to point to the end of the existing data.
149    RefPtr<StringImpl> buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters16);
150    for (unsigned i = 0; i < m_length; ++i)
151        m_bufferCharacters16[i] = currentCharacters[i];
152
153    m_is8Bit = false;
154
155    // Update the builder state.
156    m_buffer = buffer.release();
157    m_string = String();
158}
159
160template <>
161void StringBuilder::reallocateBuffer<LChar>(unsigned requiredLength)
162{
163    // If the buffer has only one ref (by this StringBuilder), reallocate it,
164    // otherwise fall back to "allocate and copy" method.
165    m_string = String();
166
167    ASSERT(m_is8Bit);
168    ASSERT(m_buffer->is8Bit());
169
170    if (m_buffer->hasOneRef()) {
171        m_buffer = StringImpl::reallocate(m_buffer.release(), requiredLength);
172        m_bufferCharacters8 = const_cast<LChar*>(m_buffer->characters8());
173    } else
174        allocateBuffer(m_buffer->characters8(), requiredLength);
175}
176
177template <>
178void StringBuilder::reallocateBuffer<UChar>(unsigned requiredLength)
179{
180    // If the buffer has only one ref (by this StringBuilder), reallocate it,
181    // otherwise fall back to "allocate and copy" method.
182    m_string = String();
183
184    if (m_buffer->is8Bit()) {
185        allocateBufferUpConvert(m_buffer->characters8(), requiredLength);
186    } else if (m_buffer->hasOneRef()) {
187        m_buffer = StringImpl::reallocate(m_buffer.release(), requiredLength);
188        m_bufferCharacters16 = const_cast<UChar*>(m_buffer->characters16());
189    } else
190        allocateBuffer(m_buffer->characters16(), requiredLength);
191}
192
193void StringBuilder::reserveCapacity(unsigned newCapacity)
194{
195    if (m_buffer) {
196        // If there is already a buffer, then grow if necessary.
197        if (newCapacity > m_buffer->length()) {
198            if (m_buffer->is8Bit())
199                reallocateBuffer<LChar>(newCapacity);
200            else
201                reallocateBuffer<UChar>(newCapacity);
202        }
203    } else {
204        // Grow the string, if necessary.
205        if (newCapacity > m_length) {
206            if (!m_length) {
207                LChar* nullPlaceholder = 0;
208                allocateBuffer(nullPlaceholder, newCapacity);
209            } else if (m_string.is8Bit())
210                allocateBuffer(m_string.characters8(), newCapacity);
211            else
212                allocateBuffer(m_string.characters16(), newCapacity);
213        }
214    }
215}
216
217// Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
218// return a pointer to the newly allocated storage.
219template <typename CharType>
220ALWAYS_INLINE CharType* StringBuilder::appendUninitialized(unsigned length)
221{
222    ASSERT(length);
223
224    // Calculate the new size of the builder after appending.
225    unsigned requiredLength = length + m_length;
226    RELEASE_ASSERT(requiredLength >= length);
227
228    if ((m_buffer) && (requiredLength <= m_buffer->length())) {
229        // If the buffer is valid it must be at least as long as the current builder contents!
230        ASSERT(m_buffer->length() >= m_length);
231        unsigned currentLength = m_length;
232        m_string = String();
233        m_length = requiredLength;
234        return getBufferCharacters<CharType>() + currentLength;
235    }
236
237    return appendUninitializedSlow<CharType>(requiredLength);
238}
239
240// Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
241// return a pointer to the newly allocated storage.
242template <typename CharType>
243CharType* StringBuilder::appendUninitializedSlow(unsigned requiredLength)
244{
245    ASSERT(requiredLength);
246
247    if (m_buffer) {
248        // If the buffer is valid it must be at least as long as the current builder contents!
249        ASSERT(m_buffer->length() >= m_length);
250
251        reallocateBuffer<CharType>(expandedCapacity(capacity(), requiredLength));
252    } else {
253        ASSERT(m_string.length() == m_length);
254        allocateBuffer(m_length ? m_string.getCharacters<CharType>() : 0, expandedCapacity(capacity(), requiredLength));
255    }
256
257    CharType* result = getBufferCharacters<CharType>() + m_length;
258    m_length = requiredLength;
259    return result;
260}
261
262void StringBuilder::append(const UChar* characters, unsigned length)
263{
264    if (!length)
265        return;
266
267    ASSERT(characters);
268
269    if (m_is8Bit) {
270        if (length == 1 && !(*characters & ~0xff)) {
271            // Append as 8 bit character
272            LChar lChar = static_cast<LChar>(*characters);
273            append(&lChar, 1);
274            return;
275        }
276
277        // Calculate the new size of the builder after appending.
278        unsigned requiredLength = length + m_length;
279        RELEASE_ASSERT(requiredLength >= length);
280
281        if (m_buffer) {
282            // If the buffer is valid it must be at least as long as the current builder contents!
283            ASSERT(m_buffer->length() >= m_length);
284
285            allocateBufferUpConvert(m_buffer->characters8(), expandedCapacity(capacity(), requiredLength));
286        } else {
287            ASSERT(m_string.length() == m_length);
288            allocateBufferUpConvert(m_string.isNull() ? 0 : m_string.characters8(), expandedCapacity(capacity(), requiredLength));
289        }
290
291        memcpy(m_bufferCharacters16 + m_length, characters, static_cast<size_t>(length) * sizeof(UChar));
292        m_length = requiredLength;
293    } else
294        memcpy(appendUninitialized<UChar>(length), characters, static_cast<size_t>(length) * sizeof(UChar));
295}
296
297void StringBuilder::append(const LChar* characters, unsigned length)
298{
299    if (!length)
300        return;
301    ASSERT(characters);
302
303    if (m_is8Bit) {
304        LChar* dest = appendUninitialized<LChar>(length);
305        if (length > 8)
306            memcpy(dest, characters, static_cast<size_t>(length) * sizeof(LChar));
307        else {
308            const LChar* end = characters + length;
309            while (characters < end)
310                *(dest++) = *(characters++);
311        }
312    } else {
313        UChar* dest = appendUninitialized<UChar>(length);
314        const LChar* end = characters + length;
315        while (characters < end)
316            *(dest++) = *(characters++);
317    }
318}
319
320void StringBuilder::appendNumber(int number)
321{
322    numberToStringSigned<StringBuilder>(number, this);
323}
324
325void StringBuilder::appendNumber(unsigned number)
326{
327    numberToStringUnsigned<StringBuilder>(number, this);
328}
329
330void StringBuilder::appendNumber(long number)
331{
332    numberToStringSigned<StringBuilder>(number, this);
333}
334
335void StringBuilder::appendNumber(unsigned long number)
336{
337    numberToStringUnsigned<StringBuilder>(number, this);
338}
339
340void StringBuilder::appendNumber(long long number)
341{
342    numberToStringSigned<StringBuilder>(number, this);
343}
344
345void StringBuilder::appendNumber(unsigned long long number)
346{
347    numberToStringUnsigned<StringBuilder>(number, this);
348}
349
350static void expandLCharToUCharInplace(UChar* buffer, size_t length)
351{
352    const LChar* sourceEnd = reinterpret_cast<LChar*>(buffer) + length;
353    UChar* current = buffer + length;
354    while (current != buffer)
355        *--current = *--sourceEnd;
356}
357
358void StringBuilder::appendNumber(double number, unsigned precision, TrailingZerosTruncatingPolicy trailingZerosTruncatingPolicy)
359{
360    bool truncateTrailingZeros = trailingZerosTruncatingPolicy == TruncateTrailingZeros;
361    size_t numberLength;
362    if (m_is8Bit) {
363        LChar* dest = appendUninitialized<LChar>(NumberToStringBufferLength);
364        const char* result = numberToFixedPrecisionString(number, precision, reinterpret_cast<char*>(dest), truncateTrailingZeros);
365        numberLength = strlen(result);
366    } else {
367        UChar* dest = appendUninitialized<UChar>(NumberToStringBufferLength);
368        const char* result = numberToFixedPrecisionString(number, precision, reinterpret_cast<char*>(dest), truncateTrailingZeros);
369        numberLength = strlen(result);
370        expandLCharToUCharInplace(dest, numberLength);
371    }
372    ASSERT(m_length >= NumberToStringBufferLength);
373    // Remove what appendUninitialized added.
374    m_length -= NumberToStringBufferLength;
375    ASSERT(numberLength <= NumberToStringBufferLength);
376    m_length += numberLength;
377}
378
379bool StringBuilder::canShrink() const
380{
381    // Only shrink the buffer if it's less than 80% full. Need to tune this heuristic!
382    return m_buffer && m_buffer->length() > (m_length + (m_length >> 2));
383}
384
385void StringBuilder::shrinkToFit()
386{
387    if (!canShrink())
388        return;
389    if (m_is8Bit)
390        reallocateBuffer<LChar>(m_length);
391    else
392        reallocateBuffer<UChar>(m_length);
393    m_string = m_buffer.release();
394}
395
396} // namespace WTF
397