Use a Vector for the buffer in StringBuilder.

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

 /*
  * Copyright (C) 2010 Apple Inc. All rights reserved.
  * Copyright (C) 2012 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
@@ skipping 15 matching lines @@
 
 #include "wtf/text/StringBuilder.h"
 
 #include "wtf/dtoa.h"
 #include "wtf/text/IntegerToStringConversion.h"
 #include "wtf/text/WTFString.h"
 #include <algorithm>
 
 namespace WTF {
 
-static unsigned expandedCapacity(unsigned capacity, unsigned requiredLength)
+String StringBuilder::toString()
 {
-    static const unsigned minimumCapacity = 16;
-    return std::max(requiredLength, std::max(minimumCapacity, capacity * 2));
+    if (!m_length)
+        return emptyString();
+    if (m_string.isNull()) {
+        if (m_is8Bit)
+            m_string = String(characters8(), m_length);
+        else
+            m_string = String(characters16(), m_length);
+    }
+    return m_string;
 }
 
-void StringBuilder::reifyString()
+AtomicString StringBuilder::toAtomicString()
 {
-    if (!m_string.isNull()) {
-        DCHECK_EQ(m_string.length(), m_length);
-        return;
+    if (!m_length)
+        return emptyAtom;
+    if (m_string.isNull()) {
+        if (m_is8Bit)
+            m_string = AtomicString(characters8(), m_length);
+        else
+            m_string = AtomicString(characters16(), m_length);
     }
-
-    if (!m_length) {
-        m_string = StringImpl::empty();
-        return;
-    }
-
-    DCHECK(m_buffer);
-    DCHECK_LE(m_length, m_buffer->length());
-    if (m_length == m_buffer->length()) {
-        m_string = m_buffer.release();
-        return;
-    }
-
-    m_string = m_buffer->substring(0, m_length);
+    return AtomicString(m_string);
 }
 
-String StringBuilder::reifySubstring(unsigned position, unsigned length) const
+String StringBuilder::substring(unsigned start, unsigned length) const
 {
-    DCHECK(m_string.isNull());
-    DCHECK(m_buffer);
-    unsigned substringLength = std::min(length, m_length - position);
-    return m_buffer->substring(position, substringLength);
+    if (start >= m_length)
+        return emptyString();
+    if (!m_string.isNull())
+        return m_string.substring(start, length);
+    length = std::min(length, m_length - start);
+    if (m_is8Bit)
+        return String(characters8() + start, length);
+    return String(characters16() + start, length);
+}
+
+void StringBuilder::swap(StringBuilder& builder)
+{
+    std::swap(m_string, builder.m_string);
+    std::swap(m_buffer, builder.m_buffer);
+    std::swap(m_length, builder.m_length);
+    std::swap(m_is8Bit, builder.m_is8Bit);
+}
+
+void StringBuilder::clear()
+{
+    m_string = String();
+    if (m_is8Bit)
+        delete m_buffer8;

[haraken, 2016/06/27 06:36:01]

Can we use OwnPtr and avoid using manual delete?

[hajimehoshi, 2016/06/27 06:38:02]

unique_ptr I think :-)

[esprehn, 2016/06/27 23:36:40]

No, you can't store a unique_ptr in a union. So we need to do manual delete.

[hajimehoshi, 2016/06/28 05:01:35]

Out of curiosity, isn't it possible to use two unique_ptrs instead of a union? I
guess memory usage of this class is critical but not sure.

+    else
+        delete m_buffer16;
+    m_buffer = nullptr;
+    m_length = 0;
+    m_is8Bit = true;
+}
+
+unsigned StringBuilder::capacity() const
+{
+    if (!hasBuffer())
+        return 0;
+    if (m_is8Bit)
+        return m_buffer8->capacity();
+    return m_buffer16->capacity();
+}
+
+void StringBuilder::reserveCapacity(unsigned newCapacity)
+{
+    if (m_is8Bit) {
+        ensureBuffer8();
+        m_buffer8->reserveCapacity(newCapacity);
+    } else {
+        ensureBuffer16();
+        m_buffer16->reserveCapacity(newCapacity);
+    }
 }
 
 void StringBuilder::resize(unsigned newSize)
 {
-    // Check newSize < m_length, hence m_length > 0.
     DCHECK_LE(newSize, m_length);
-    if (newSize == m_length)
+    m_length = newSize;
+    m_string = String();
+    if (!hasBuffer())
         return;
-    DCHECK(m_length);
+    if (m_is8Bit)
+        m_buffer8->resize(newSize);
+    else
+        m_buffer16->resize(newSize);
+}
 
-    // If there is a buffer, we only need to duplicate it if it has more than one ref.
-    if (m_buffer) {
-        m_string = String(); // Clear the string to remove the reference to m_buffer if any before checking the reference count of m_buffer.
-        if (!m_buffer->hasOneRef()) {
-            if (m_buffer->is8Bit())
-                allocateBuffer(m_buffer->characters8(), m_buffer->length());
-            else
-                allocateBuffer(m_buffer->characters16(), m_buffer->length());
-        }
-        m_length = newSize;
+void StringBuilder::createBuffer8()
+{
+    DCHECK(!hasBuffer());
+    DCHECK(m_is8Bit);
+    m_buffer8 = new Buffer8;
+    m_length = 0;
+    // Must keep a ref to the string since append will clear it.
+    String string(m_string);
+    append(string);
+}
+
+void StringBuilder::createBuffer16()
+{
+    DCHECK(m_is8Bit || !hasBuffer());

[haraken, 2016/06/27 06:36:01]

Slightly better:

  DCHECK((m_is8Bit && m_buffer8) || !hasBuffer());

[esprehn, 2016/06/27 23:36:40]

I'm not sure what that does, if m_buffer8 is null then we'll just check
!hasBuffer() on the other side of the assert which then is !m_buffer8 so the
m_buffer8 check you added doesn't do anything, it's the same as:

DCHECK((m_is8Bit && m_buffer8) || !m_buffer8)

+    Buffer8 buffer8;
+    unsigned length = m_length;
+    if (m_buffer8) {
+        m_buffer8->swap(buffer8);
+        delete m_buffer8;
+    }
+    m_buffer16 = new Buffer16;
+    m_is8Bit = false;
+    m_length = 0;
+    if (!buffer8.isEmpty()) {
+        append(buffer8.data(), length);
         return;
     }
-
-    // Since m_length && !m_buffer, the string must be valid in m_string, and m_string.length() > 0.
-    DCHECK(!m_string.isEmpty());
-    DCHECK_EQ(m_length, m_string.length());
-    DCHECK_LT(newSize, m_string.length());
-    m_length = newSize;
-    RefPtr<StringImpl> string = m_string.releaseImpl();
-    if (string->hasOneRef()) {
-        // If we're the only ones with a reference to the string, we can
-        // re-purpose the string as m_buffer and continue mutating it.
-        m_buffer = string;
-    } else {
-        // Otherwise, we need to make a copy of the string so that we don't
-        // mutate a String that's held elsewhere.
-        m_buffer = string->substring(0, m_length);
-    }
-}
-
-// Allocate a new 8 bit buffer, copying in currentCharacters (these may come from either m_string
-// or m_buffer, neither will be reassigned until the copy has completed).
-void StringBuilder::allocateBuffer(const LChar* currentCharacters, unsigned requiredLength)
-{
-    DCHECK(m_is8Bit);
-    // Copy the existing data into a new buffer, set result to point to the end of the existing data.
-    RefPtr<StringImpl> buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters8);
-    memcpy(m_bufferCharacters8, currentCharacters, static_cast<size_t>(m_length) * sizeof(LChar)); // This can't overflow.
-
-    // Update the builder state.
-    m_buffer = buffer.release();
-    m_string = String();
-}
-
-// Allocate a new 16 bit buffer, copying in currentCharacters (these may come from either m_string
-// or m_buffer,  neither will be reassigned until the copy has completed).
-void StringBuilder::allocateBuffer(const UChar* currentCharacters, unsigned requiredLength)
-{
-    DCHECK(!m_is8Bit);
-    // Copy the existing data into a new buffer, set result to point to the end of the existing data.
-    RefPtr<StringImpl> buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters16);
-    memcpy(m_bufferCharacters16, currentCharacters, static_cast<size_t>(m_length) * sizeof(UChar)); // This can't overflow.
-
-    // Update the builder state.
-    m_buffer = buffer.release();
-    m_string = String();
-}
-
-// Allocate a new 16 bit buffer, copying in currentCharacters (which is 8 bit and may come
-// from either m_string or m_buffer, neither will be reassigned until the copy has completed).
-void StringBuilder::allocateBufferUpConvert(const LChar* currentCharacters, unsigned requiredLength)
-{
-    DCHECK(m_is8Bit);
-    // Copy the existing data into a new buffer, set result to point to the end of the existing data.
-    RefPtr<StringImpl> buffer = StringImpl::createUninitialized(requiredLength, m_bufferCharacters16);
-    for (unsigned i = 0; i < m_length; ++i)
-        m_bufferCharacters16[i] = currentCharacters[i];
-
-    m_is8Bit = false;
-
-    // Update the builder state.
-    m_buffer = buffer.release();
-    m_string = String();
-}
-
-template <>
-void StringBuilder::reallocateBuffer<LChar>(unsigned requiredLength)
-{
-    // If the buffer has only one ref (by this StringBuilder), reallocate it,
-    // otherwise fall back to "allocate and copy" method.
-    m_string = String();
-
-    DCHECK(m_is8Bit);
-    DCHECK(m_buffer->is8Bit());
-
-    allocateBuffer(m_buffer->characters8(), requiredLength);
-}
-
-template <>
-void StringBuilder::reallocateBuffer<UChar>(unsigned requiredLength)
-{
-    // If the buffer has only one ref (by this StringBuilder), reallocate it,
-    // otherwise fall back to "allocate and copy" method.
-    m_string = String();
-
-    if (m_buffer->is8Bit())
-        allocateBufferUpConvert(m_buffer->characters8(), requiredLength);
-    else
-        allocateBuffer(m_buffer->characters16(), requiredLength);
-}
-
-void StringBuilder::reserveCapacity(unsigned newCapacity)
-{
-    if (m_buffer) {
-        // If there is already a buffer, then grow if necessary.
-        if (newCapacity > m_buffer->length()) {
-            if (m_buffer->is8Bit())
-                reallocateBuffer<LChar>(newCapacity);
-            else
-                reallocateBuffer<UChar>(newCapacity);
-        }
-    } else {
-        // Grow the string, if necessary.
-        if (newCapacity > m_length) {
-            if (!m_length) {
-                LChar* nullPlaceholder = 0;
-                allocateBuffer(nullPlaceholder, newCapacity);
-            } else if (m_string.is8Bit()) {
-                allocateBuffer(m_string.characters8(), newCapacity);
-            } else {
-                allocateBuffer(m_string.characters16(), newCapacity);
-            }
-        }
-    }
-}
-
-// Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
-// return a pointer to the newly allocated storage.
-template <typename CharType>
-ALWAYS_INLINE CharType* StringBuilder::appendUninitialized(unsigned length)
-{
-    DCHECK(length);
-
-    // Calculate the new size of the builder after appending.
-    unsigned requiredLength = length + m_length;
-    CHECK_GE(requiredLength, length);
-
-    if ((m_buffer) && (requiredLength <= m_buffer->length())) {
-        // If the buffer is valid it must be at least as long as the current builder contents!
-        DCHECK_GE(m_buffer->length(), m_length);
-        unsigned currentLength = m_length;
-        m_string = String();
-        m_length = requiredLength;
-        return getBufferCharacters<CharType>() + currentLength;
-    }
-
-    return appendUninitializedSlow<CharType>(requiredLength);
-}
-
-// Make 'length' additional capacity be available in m_buffer, update m_string & m_length,
-// return a pointer to the newly allocated storage.
-template <typename CharType>
-CharType* StringBuilder::appendUninitializedSlow(unsigned requiredLength)
-{
-    DCHECK(requiredLength);
-
-    if (m_buffer) {
-        // If the buffer is valid it must be at least as long as the current builder contents!
-        DCHECK_GE(m_buffer->length(), m_length);
-
-        reallocateBuffer<CharType>(expandedCapacity(capacity(), requiredLength));
-    } else {
-        DCHECK_EQ(m_string.length(), m_length);
-        allocateBuffer(m_length ? m_string.getCharacters<CharType>() : 0, expandedCapacity(capacity(), requiredLength));
-    }
-
-    CharType* result = getBufferCharacters<CharType>() + m_length;
-    m_length = requiredLength;
-    return result;
+    // Must keep a ref to the string since append will clear it.
+    String string(m_string);
+    append(string);
 }
 
 void StringBuilder::append(const UChar* characters, unsigned length)
 {
     if (!length)
         return;
-
     DCHECK(characters);
 
-    if (m_is8Bit) {
-        if (length == 1 && !(*characters & ~0xff)) {
-            // Append as 8 bit character
-            LChar lChar = static_cast<LChar>(*characters);
-            append(&lChar, 1);
-            return;
-        }
+    // If there's only one char we use append(UChar) instead since it will
+    // check for latin1 and avoid converting to 16bit if possible.
+    if (length == 1) {
+        append(*characters);
+        return;
+    }
 
-        // Calculate the new size of the builder after appending.
-        unsigned requiredLength = length + m_length;
-        CHECK_GE(requiredLength, length);
-
-        if (m_buffer) {
-            // If the buffer is valid it must be at least as long as the current builder contents!
-            DCHECK_GE(m_buffer->length(), m_length);
-
-            allocateBufferUpConvert(m_buffer->characters8(), expandedCapacity(capacity(), requiredLength));
-        } else {
-            DCHECK_EQ(m_string.length(), m_length);
-            allocateBufferUpConvert(m_string.isNull() ? 0 : m_string.characters8(), expandedCapacity(capacity(), requiredLength));
-        }
-
-        memcpy(m_bufferCharacters16 + m_length, characters, static_cast<size_t>(length) * sizeof(UChar));
-        m_length = requiredLength;
-    } else {
-        memcpy(appendUninitialized<UChar>(length), characters, static_cast<size_t>(length) * sizeof(UChar));
-    }
+    ensureBuffer16();
+    m_string = String();
+    m_buffer16->append(characters, length);
+    m_length += length;
 }
 
 void StringBuilder::append(const LChar* characters, unsigned length)
 {
     if (!length)
         return;
     DCHECK(characters);
 
     if (m_is8Bit) {
-        LChar* dest = appendUninitialized<LChar>(length);
-        if (length > 8) {
-            memcpy(dest, characters, static_cast<size_t>(length) * sizeof(LChar));
-        } else {
-            const LChar* end = characters + length;
-            while (characters < end)
-                *(dest++) = *(characters++);
-        }
-    } else {
-        UChar* dest = appendUninitialized<UChar>(length);
-        const LChar* end = characters + length;
-        while (characters < end)
-            *(dest++) = *(characters++);
+        ensureBuffer8();
+        m_string = String();
+        m_buffer8->append(characters, length);
+        m_length += length;
+        return;
     }
+
+    ensureBuffer16();
+    m_string = String();
+    m_buffer16->reserveCapacity(m_buffer16->size() + length);
+    for (size_t i = 0; i < length; ++i)
+        m_buffer16->uncheckedAppend(characters[i]);
+    m_length += length;
 }
 
 template<typename IntegerType>
 static void appendIntegerInternal(StringBuilder& builder, IntegerType input)
 {
     IntegerToStringConverter<IntegerType> converter(input);
     builder.append(converter.characters8(), converter.length());
 }
 
 void StringBuilder::appendNumber(int number)
@@ skipping 19 matching lines @@
 void StringBuilder::appendNumber(long long number)
 {
     appendIntegerInternal(*this, number);
 }
 
 void StringBuilder::appendNumber(unsigned long long number)
 {
     appendIntegerInternal(*this, number);
 }
 
-static void expandLCharToUCharInplace(UChar* buffer, size_t length)
-{
-    const LChar* sourceEnd = reinterpret_cast<LChar*>(buffer) + length;
-    UChar* current = buffer + length;
-    while (current != buffer)
-        *--current = *--sourceEnd;
-}
-
 void StringBuilder::appendNumber(double number, unsigned precision, TrailingZerosTruncatingPolicy trailingZerosTruncatingPolicy)
 {
-    bool truncateTrailingZeros = trailingZerosTruncatingPolicy == TruncateTrailingZeros;
-    size_t numberLength;
-    if (m_is8Bit) {
-        LChar* dest = appendUninitialized<LChar>(NumberToStringBufferLength);
-        const char* result = numberToFixedPrecisionString(number, precision, reinterpret_cast<char*>(dest), truncateTrailingZeros);
-        numberLength = strlen(result);
-    } else {
-        UChar* dest = appendUninitialized<UChar>(NumberToStringBufferLength);
-        const char* result = numberToFixedPrecisionString(number, precision, reinterpret_cast<char*>(dest), truncateTrailingZeros);
-        numberLength = strlen(result);
-        expandLCharToUCharInplace(dest, numberLength);
-    }
-    DCHECK_GE(m_length, NumberToStringBufferLength);
-    // Remove what appendUninitialized added.
-    m_length -= NumberToStringBufferLength;
-    DCHECK_LE(numberLength, NumberToStringBufferLength);
-    m_length += numberLength;
-}
-
-bool StringBuilder::canShrink() const
-{
-    // Only shrink the buffer if it's less than 80% full. Need to tune this heuristic!
-    return m_buffer && m_buffer->length() > (m_length + (m_length >> 2));
-}
-
-void StringBuilder::shrinkToFit()
-{
-    if (!canShrink())
-        return;
-    if (m_is8Bit)
-        reallocateBuffer<LChar>(m_length);
-    else
-        reallocateBuffer<UChar>(m_length);
-    m_string = m_buffer.release();
+    NumberToStringBuffer buffer;
+    append(numberToFixedPrecisionString(number, precision, buffer, trailingZerosTruncatingPolicy == TruncateTrailingZeros));
 }
 
 } // namespace WTF