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