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