Massively simplify WTF's StringConcatenate

third_party/WebKit/Source/wtf/text/StringConcatenate.h

 /*
  * Copyright (C) 2010 Apple 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
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
 #ifndef StringConcatenate_h
 #define StringConcatenate_h
 
 #include "wtf/Allocator.h"
+#include "wtf/text/StringBuffer.h"
 #include <string.h>
 
 #ifndef WTFString_h
 #include "wtf/text/AtomicString.h"
 #endif
 
-// This macro is helpful for testing how many intermediate Strings are created while evaluating an
-// expression containing operator+.
-#ifndef WTF_STRINGTYPEADAPTER_COPIED_WTF_STRING
-#define WTF_STRINGTYPEADAPTER_COPIED_WTF_STRING() ((void)0)
-#endif
-
 namespace WTF {
 
 template<typename StringType>
 class StringTypeAdapter {
-    DISALLOW_NEW();
-};
-
-template<>
-class StringTypeAdapter<char> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter<char>(char buffer)
+    STACK_ALLOCATED();
+};
+
+template<>
+class StringTypeAdapter<LChar> {
+    STACK_ALLOCATED();
+public:
+    explicit StringTypeAdapter<LChar>(LChar buffer)
+        : m_buffer(buffer) {}
+
+    unsigned length() const { return 1; }
+    bool is8Bit() const { return true; }
+
+    void writeTo(LChar* destination) const { *destination = m_buffer; }
+    void writeTo(UChar* destination) const { *destination = m_buffer; }
+
+private:
+    const LChar m_buffer;
+};
+
+template<>
+class StringTypeAdapter<char> : public StringTypeAdapter<LChar> {
+    STACK_ALLOCATED();
+public:
+    explicit StringTypeAdapter<char>(char buffer)
+        : StringTypeAdapter<LChar>(buffer) {}
+};
+
+template<>
+class StringTypeAdapter<UChar> {
+    STACK_ALLOCATED();
+public:
+    explicit StringTypeAdapter<UChar>(UChar buffer)
+        : m_buffer(buffer) {}
+
+    unsigned length() const { return 1; }
+    bool is8Bit() const { return m_buffer <= 0xff; }
+
+    void writeTo(LChar* destination) const
+    {
+        DCHECK(is8Bit());
+        *destination = static_cast<LChar>(m_buffer);
+    }
+
+    void writeTo(UChar* destination) const { *destination = m_buffer; }
+
+private:
+    const UChar m_buffer;
+};
+
+template<>
+class WTF_EXPORT StringTypeAdapter<const UChar*> {
+    STACK_ALLOCATED();
+public:
+    explicit StringTypeAdapter(const UChar* buffer);
+
+    unsigned length() const { return m_length; }
+
+    bool is8Bit() const { return false; }
+
+    void writeTo(LChar*) const { RELEASE_NOTREACHED(); }
+    void writeTo(UChar* destination) const;
+
+private:
+    const UChar* m_buffer;
+    const unsigned m_length;
+};
+
+template<>
+class WTF_EXPORT StringTypeAdapter<const LChar*> {
+    STACK_ALLOCATED();
+public:
+    explicit StringTypeAdapter(const LChar* buffer)
         : m_buffer(buffer)
-    {
-    }
-
-    unsigned length() { return 1; }
-
-    bool is8Bit() { return true; }
-
-    void writeTo(LChar* destination)
-    {
-        *destination = m_buffer;
-    }
-
-    void writeTo(UChar* destination) { *destination = m_buffer; }
-
-private:
-    unsigned char m_buffer;
-};
-
-template<>
-class StringTypeAdapter<LChar> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter<LChar>(LChar buffer)
-        : m_buffer(buffer)
-    {
-    }
-
-    unsigned length() { return 1; }
-
-    bool is8Bit() { return true; }
-
-    void writeTo(LChar* destination)
-    {
-        *destination = m_buffer;
-    }
-
-    void writeTo(UChar* destination) { *destination = m_buffer; }
-
-private:
-    LChar m_buffer;
-};
-
-template<>
-class StringTypeAdapter<UChar> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter<UChar>(UChar buffer)
-        : m_buffer(buffer)
-    {
-    }
-
-    unsigned length() { return 1; }
-
-    bool is8Bit() { return m_buffer <= 0xff; }
-
-    void writeTo(LChar* destination)
-    {
-        ASSERT(is8Bit());
-        *destination = static_cast<LChar>(m_buffer);
-    }
-
-    void writeTo(UChar* destination) { *destination = m_buffer; }
-
-private:
-    UChar m_buffer;
-};
-
-template<>
-class WTF_EXPORT StringTypeAdapter<char*> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter<char*>(char* buffer)
-        : m_buffer(buffer)
-        , m_length(strlen(buffer))
-    {
-    }
-
-    unsigned length() { return m_length; }
-
-    bool is8Bit() { return true; }
-
-    void writeTo(LChar* destination);
-
-    void writeTo(UChar* destination);
-
-private:
-    const char* m_buffer;
-    unsigned m_length;
-};
-
-template<>
-class WTF_EXPORT StringTypeAdapter<LChar*> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter<LChar*>(LChar* buffer);
-
-    unsigned length() { return m_length; }
-
-    bool is8Bit() { return true; }
-
-    void writeTo(LChar* destination);
-
-    void writeTo(UChar* destination);
+        , m_length(strlen(reinterpret_cast<const char*>(buffer))) {}
+
+    explicit StringTypeAdapter(const char* buffer)
+        : StringTypeAdapter(reinterpret_cast<const LChar*>(buffer)) {}
+
+    unsigned length() const { return m_length; }
+    bool is8Bit() const { return true; }
+
+    void writeTo(LChar* destination) const;
+    void writeTo(UChar* destination) const;
 
 private:
     const LChar* m_buffer;
-    unsigned m_length;
-};
-
-template<>
-class WTF_EXPORT StringTypeAdapter<const UChar*> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter(const UChar* buffer);
-
-    unsigned length() { return m_length; }
-
-    bool is8Bit() { return false; }
-
-    void writeTo(LChar*)
-    {
-        RELEASE_ASSERT(false);
-    }
-
-    void writeTo(UChar* destination);
-
-private:
-    const UChar* m_buffer;
-    unsigned m_length;
-};
-
-template<>
-class WTF_EXPORT StringTypeAdapter<const char*> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter<const char*>(const char* buffer);
-
-    unsigned length() { return m_length; }
-
-    bool is8Bit() { return true; }
-
-    void writeTo(LChar* destination);
-
-    void writeTo(UChar* destination);
-
-private:
-    const char* m_buffer;
-    unsigned m_length;
-};
-
-template<>
-class WTF_EXPORT StringTypeAdapter<const LChar*> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter<const LChar*>(const LChar* buffer);
-
-    unsigned length() { return m_length; }
-
-    bool is8Bit() { return true; }
-
-    void writeTo(LChar* destination);
-
-    void writeTo(UChar* destination);
-
-private:
-    const LChar* m_buffer;
-    unsigned m_length;
-};
-
-template<>
-class WTF_EXPORT StringTypeAdapter<Vector<char>> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter<Vector<char>>(const Vector<char>& buffer)
-        : m_buffer(buffer)
-    {
-    }
-
-    size_t length() { return m_buffer.size(); }
-
-    bool is8Bit() { return true; }
-
-    void writeTo(LChar* destination);
-
-    void writeTo(UChar* destination);
-
-private:
-    const Vector<char>& m_buffer;
-};
-
-template<>
-class StringTypeAdapter<Vector<LChar>> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter<Vector<LChar>>(const Vector<LChar>& buffer)
-        : m_buffer(buffer)
-    {
-    }
-
-    size_t length() { return m_buffer.size(); }
-
-    bool is8Bit() { return true; }
-
-    void writeTo(LChar* destination);
-
-    void writeTo(UChar* destination);
-
-private:
-    const Vector<LChar>& m_buffer;
+    const unsigned m_length;
 };
 
 template<>
 class WTF_EXPORT StringTypeAdapter<String> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter<String>(const String& string)
-        : m_buffer(string)
-    {
-    }
-
-    unsigned length() { return m_buffer.length(); }
-
-    bool is8Bit() { return m_buffer.isNull() || m_buffer.is8Bit(); }
-
-    void writeTo(LChar* destination);
-
-    void writeTo(UChar* destination);
-
-private:
-    const String& m_buffer;
-};
-
-template<>
-class StringTypeAdapter<AtomicString> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter<AtomicString>(const AtomicString& string)
-        : m_adapter(string.getString())
-    {
-    }
-
-    unsigned length() { return m_adapter.length(); }
-
-    bool is8Bit() { return m_adapter.is8Bit(); }
-
-    void writeTo(LChar* destination) { m_adapter.writeTo(destination); }
-    void writeTo(UChar* destination) { m_adapter.writeTo(destination); }
-
-private:
-    StringTypeAdapter<String> m_adapter;
-};
-
-inline void sumWithOverflow(unsigned& total, unsigned addend, bool& overflow)
-{
-    unsigned oldTotal = total;
-    total = oldTotal + addend;
-    if (total < oldTotal)
-        overflow = true;
-}
+    STACK_ALLOCATED();
+public:
+    explicit StringTypeAdapter(const String& string)
+        : m_buffer(string) {}
+
+    unsigned length() const { return m_buffer.length(); }
+    bool is8Bit() const { return m_buffer.isNull() || m_buffer.is8Bit(); }
+
+    void writeTo(LChar* destination) const;
+    void writeTo(UChar* destination) const;
+
+private:
+    const String m_buffer;

[Yuta Kitamura, 2016/09/07 10:25:39]

I don't think store-as-value is an improvement, unless the original
code was doing something bad. The new code costs an unnecessary ref
churn, which should be avoided in the common code like this.

Your change also invalidates an existing test with no good reason.

What do you mean by "any issues with temporary strings" in your
change description?

[esprehn, 2016/09/07 16:21:26]

Note that the StringAppend class has always stored the strings by value with:
  StringType1 m_string1;
  StringType2 m_string2;

which was ref churn. I made the adapters store by value, and now store the
adapters inside StringAppend directly so that's the same number of refs. The
extra refs come from making the combining
StringTypeAdapter<StringAppend<StringType1, StringType2>> store the StringAppend
by value which has to copy the tree. That was a const ref before, but I keep
hitting use after frees from it.

Note that previously we were creating the StringTypeAdapters repeatedly inside
the process, each instance over a const char* would then invoke strlen again in
the out of line constructor, which was many branches to count the length of the
string. We were also manually copying the bytes inside
StringTypeAdapter<String>::writeTo instead of using memcpy which this patches
does by way of copyChars. That also saves lots of branches.

So overall I think this patch is probably reducing the number of branches.
What test? Do you mean the StringOperators one? That test has been disabled for
several years apparently, I just renamed and moved it.
That might be wrong, it might just be the StringAppend instances. I've been
trying to get this patch or some variant working for several weeks, and I keep
hitting various use after frees because the temporaries inside operator+ chains
have been problematic. ex.
https://codereview.chromium.org/2245773002

There I almost got it right, but MSVC disagrees. I can try again, it's been
rather frustrating though. :)

[Jeffrey Yasskin, 2016/09/07 18:53:01]

LLVM has a type called "Twine" that stores references to its arguments in order
to facilitate concatenation:
http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/ADT/Twine.h?revis...

It probably is slightly faster than storing the tree by value, but it's also
more fiddly and increases the risk of use-after-frees. The refcount churn is
much less significant for WTF::Strings than it would be for a thread-safe
string.

[Yuta Kitamura, 2016/09/08 05:09:31]

Ah sorry, I wasn't aware the tests were disabled already.

+};
+
+template<>
+class StringTypeAdapter<AtomicString> : public StringTypeAdapter<String> {
+    STACK_ALLOCATED();
+public:
+    explicit StringTypeAdapter(const AtomicString& string)
+        : StringTypeAdapter<String>(string) {}
+};
+
+namespace internal {
+WTF_EXPORT unsigned checkedAddLength(unsigned length1, unsigned length2);
+};
 
 template<typename StringType1, typename StringType2>
-PassRefPtr<StringImpl> makeString(StringType1 string1, StringType2 string2)
-{
-    StringTypeAdapter<StringType1> adapter1(string1);
-    StringTypeAdapter<StringType2> adapter2(string2);
-
-    bool overflow = false;
-    unsigned length = adapter1.length();
-    sumWithOverflow(length, adapter2.length(), overflow);
-    if (overflow)
-        return nullptr;
-
-    if (adapter1.is8Bit() && adapter2.is8Bit()) {
-        LChar* buffer;
-        RefPtr<StringImpl> resultImpl = StringImpl::createUninitialized(length, buffer);
-        if (!resultImpl)
-            return nullptr;
-
-        LChar* result = buffer;
-        adapter1.writeTo(result);
-        result += adapter1.length();
-        adapter2.writeTo(result);
-
-        return resultImpl.release();
-    }
-
-    UChar* buffer;
-    RefPtr<StringImpl> resultImpl = StringImpl::createUninitialized(length, buffer);
-    if (!resultImpl)
-        return nullptr;
-
-    UChar* result = buffer;
-    adapter1.writeTo(result);
-    result += adapter1.length();
-    adapter2.writeTo(result);
-
-    return resultImpl.release();
+class StringAppend final {
+    STACK_ALLOCATED();
+public:
+    StringAppend(StringType1 string1, StringType2 string2)
+        : m_adapter1(string1)
+        , m_adapter2(string2) {}
+
+    operator String() const { return toString(); }
+    operator AtomicString() const { return AtomicString(toString()); }
+
+    unsigned length() const { return internal::checkedAddLength(m_adapter1.length(), m_adapter2.length()); }
+    bool is8Bit() const { return m_adapter1.is8Bit() && m_adapter2.is8Bit(); }
+
+    void writeTo(LChar* destination) const
+    {
+        DCHECK(is8Bit());
+        m_adapter1.writeTo(destination);
+        m_adapter2.writeTo(destination + m_adapter1.length());
+    }
+
+    void writeTo(UChar* destination) const
+    {
+        m_adapter1.writeTo(destination);
+        m_adapter2.writeTo(destination + m_adapter1.length());
+    }
+
+private:
+    PassRefPtr<StringImpl> toString() const
+    {
+        if (is8Bit()) {
+            StringBuffer<LChar> buffer(length());
+            writeTo(buffer.characters());
+            return buffer.release();
+        }
+        StringBuffer<UChar> buffer(length());
+        writeTo(buffer.characters());
+        return buffer.release();
+    }
+
+    StringTypeAdapter<StringType1> m_adapter1;
+    StringTypeAdapter<StringType2> m_adapter2;
+};
+
+template<typename StringType1, typename StringType2>
+class StringTypeAdapter<StringAppend<StringType1, StringType2>> {
+    STACK_ALLOCATED();
+public:
+    explicit StringTypeAdapter(const StringAppend<StringType1, StringType2>& buffer)
+        : m_buffer(buffer) {}
+
+    unsigned length() const { return m_buffer.length(); }
+    bool is8Bit() const { return m_buffer.is8Bit(); }
+
+    void writeTo(LChar* destination) const { m_buffer.writeTo(destination); }
+    void writeTo(UChar* destination) const { m_buffer.writeTo(destination); }
+
+private:
+    const StringAppend<StringType1, StringType2> m_buffer;
+};
+
+inline StringAppend<const LChar*, String> operator+(const char* string1, const String& string2)
+{
+    return StringAppend<const LChar*, String>(reinterpret_cast<const LChar*>(string1), string2);
+}
+
+inline StringAppend<const LChar*, AtomicString> operator+(const char* string1, const AtomicString& string2)
+{
+    return StringAppend<const LChar*, AtomicString>(reinterpret_cast<const LChar*>(string1), string2);
+}
+
+template<typename U, typename V>
+inline StringAppend<const LChar*, StringAppend<U, V>> operator+(const char* string1, const StringAppend<U, V>& string2)
+{
+    return StringAppend<const LChar*, StringAppend<U, V>>(reinterpret_cast<const LChar*>(string1), string2);
+}
+
+inline StringAppend<const UChar*, String> operator+(const UChar* string1, const String& string2)
+{
+    return StringAppend<const UChar*, String>(string1, string2);
+}
+
+inline StringAppend<const UChar*, AtomicString> operator+(const UChar* string1, const AtomicString& string2)
+{
+    return StringAppend<const UChar*, AtomicString>(string1, string2);
+}
+
+template<typename U, typename V>
+inline StringAppend<const UChar*, StringAppend<U, V>> operator+(const UChar* string1, const StringAppend<U, V>& string2)
+{
+    return StringAppend<const UChar*, StringAppend<U, V>>(string1, string2);
+}
+
+inline StringAppend<String, const LChar*> operator+(const String& string1, const char* string2)
+{
+    return StringAppend<String, const LChar*>(string1, reinterpret_cast<const LChar*>(string2));
+}
+
+template<typename T>
+inline StringAppend<String, T> operator+(const String& string1, T string2)
+{
+    return StringAppend<String, T>(string1, string2);
+}
+
+template<typename U, typename V>
+inline StringAppend<StringAppend<U, V>, const LChar*> operator+(const StringAppend<U, V>& string1, const char* string2)
+{
+    return StringAppend<StringAppend<U, V>, const LChar*>(string1, reinterpret_cast<const LChar*>(string2));
+}
+
+template<typename U, typename V, typename W>
+inline StringAppend<StringAppend<U, V>, W> operator+(const StringAppend<U, V>& string1, W string2)
+{
+    return StringAppend<StringAppend<U, V>, W>(string1, string2);
 }
 
 } // namespace WTF
-
-#include "wtf/text/StringOperators.h"
 #endif