src/third_party/WebKit/Source/wtf/text/StringBuilder.cpp

   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
  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 void 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
  69 String 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
  77 void 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).
 117 void 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).
 131 void 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).
 145 void 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
 160 template <>
 161 void 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
 177 template <>
 178 void 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
 193 void 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.
 219 template <typename CharType>
 220 ALWAYS_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.
 242 template <typename CharType>
 243 CharType* 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
 262 void 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
 297 void 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
 320 void StringBuilder::appendNumber(int number)
 321 {
 322     numberToStringSigned<StringBuilder>(number, this);
 323 }
 324
 325 void StringBuilder::appendNumber(unsigned number)
 326 {
 327     numberToStringUnsigned<StringBuilder>(number, this);
 328 }
 329
 330 void StringBuilder::appendNumber(long number)
 331 {
 332     numberToStringSigned<StringBuilder>(number, this);
 333 }
 334
 335 void StringBuilder::appendNumber(unsigned long number)
 336 {
 337     numberToStringUnsigned<StringBuilder>(number, this);
 338 }
 339
 340 void StringBuilder::appendNumber(long long number)
 341 {
 342     numberToStringSigned<StringBuilder>(number, this);
 343 }
 344
 345 void StringBuilder::appendNumber(unsigned long long number)
 346 {
 347     numberToStringUnsigned<StringBuilder>(number, this);
 348 }
 349
 350 static 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
 358 void 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
 379 bool 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
 385 void 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