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