Massively simplify WTF's StringConcatenate

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

Index: third_party/WebKit/Source/wtf/text/StringConcatenate.h
diff --git a/third_party/WebKit/Source/wtf/text/StringConcatenate.h b/third_party/WebKit/Source/wtf/text/StringConcatenate.h
index b9c6d948a08e6e23d2ef7e9f5f4fb1e90adab565..a6d5e408a6f770eb834cd00caf2886269bb9a7e3 100644
--- a/third_party/WebKit/Source/wtf/text/StringConcatenate.h
+++ b/third_party/WebKit/Source/wtf/text/StringConcatenate.h
@@ -27,331 +27,251 @@
 #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();
+    STACK_ALLOCATED();
 };
 
 template<>
-class StringTypeAdapter<char> {
-    DISALLOW_NEW();
+class StringTypeAdapter<LChar> {
+    STACK_ALLOCATED();
 public:
-    StringTypeAdapter<char>(char buffer)
-        : m_buffer(buffer)
-    {
-    }
-
-    unsigned length() { return 1; }
+    explicit StringTypeAdapter<LChar>(LChar buffer)
+        : m_buffer(buffer) {}
 
-    bool is8Bit() { return true; }
+    unsigned length() const { return 1; }
+    bool is8Bit() const { return true; }
 
-    void writeTo(LChar* destination)
-    {
-        *destination = m_buffer;
-    }
-
-    void writeTo(UChar* destination) { *destination = m_buffer; }
+    void writeTo(LChar* destination) const { *destination = m_buffer; }
+    void writeTo(UChar* destination) const { *destination = m_buffer; }
 
 private:
-    unsigned char m_buffer;
+    const LChar m_buffer;
 };
 
 template<>
-class StringTypeAdapter<LChar> {
-    DISALLOW_NEW();
+class StringTypeAdapter<char> : public StringTypeAdapter<LChar> {
+    STACK_ALLOCATED();
 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;
+    explicit StringTypeAdapter<char>(char buffer)
+        : StringTypeAdapter<LChar>(buffer) {}
 };
 
 template<>
 class StringTypeAdapter<UChar> {
-    DISALLOW_NEW();
+    STACK_ALLOCATED();
 public:
-    StringTypeAdapter<UChar>(UChar buffer)
-        : m_buffer(buffer)
-    {
-    }
-
-    unsigned length() { return 1; }
+    explicit StringTypeAdapter<UChar>(UChar buffer)
+        : m_buffer(buffer) {}
 
-    bool is8Bit() { return m_buffer <= 0xff; }
+    unsigned length() const { return 1; }
+    bool is8Bit() const { return m_buffer <= 0xff; }
 
-    void writeTo(LChar* destination)
+    void writeTo(LChar* destination) const
     {
-        ASSERT(is8Bit());
+        DCHECK(is8Bit());
         *destination = static_cast<LChar>(m_buffer);
     }
 
-    void writeTo(UChar* destination) { *destination = m_buffer; }
+    void writeTo(UChar* destination) const { *destination = m_buffer; }
 
 private:
-    UChar m_buffer;
+    const UChar m_buffer;
 };
 
 template<>
-class WTF_EXPORT StringTypeAdapter<char*> {
-    DISALLOW_NEW();
+class WTF_EXPORT StringTypeAdapter<const UChar*> {
+    STACK_ALLOCATED();
 public:
-    StringTypeAdapter<char*>(char* buffer)
-        : m_buffer(buffer)
-        , m_length(strlen(buffer))
-    {
-    }
-
-    unsigned length() { return m_length; }
+    explicit StringTypeAdapter(const UChar* buffer);
 
-    bool is8Bit() { return true; }
+    unsigned length() const { return m_length; }
 
-    void writeTo(LChar* destination);
+    bool is8Bit() const { return false; }
 
-    void writeTo(UChar* destination);
+    void writeTo(LChar*) const { RELEASE_NOTREACHED(); }
+    void writeTo(UChar* destination) const;
 
 private:
-    const char* m_buffer;
-    unsigned m_length;
+    const UChar* m_buffer;
+    const unsigned m_length;
 };
 
 template<>
-class WTF_EXPORT StringTypeAdapter<LChar*> {
-    DISALLOW_NEW();
+class WTF_EXPORT StringTypeAdapter<const LChar*> {
+    STACK_ALLOCATED();
 public:
-    StringTypeAdapter<LChar*>(LChar* buffer);
-
-    unsigned length() { return m_length; }
+    explicit StringTypeAdapter(const LChar* buffer)
+        : m_buffer(buffer)
+        , m_length(strlen(reinterpret_cast<const char*>(buffer))) {}
 
-    bool is8Bit() { return true; }
+    explicit StringTypeAdapter(const char* buffer)
+        : StringTypeAdapter(reinterpret_cast<const LChar*>(buffer)) {}
 
-    void writeTo(LChar* destination);
+    unsigned length() const { return m_length; }
+    bool is8Bit() const { return true; }
 
-    void writeTo(UChar* destination);
+    void writeTo(LChar* destination) const;
+    void writeTo(UChar* destination) const;
 
 private:
     const LChar* m_buffer;
-    unsigned m_length;
+    const unsigned m_length;
 };
 
 template<>
-class WTF_EXPORT StringTypeAdapter<const UChar*> {
-    DISALLOW_NEW();
+class WTF_EXPORT StringTypeAdapter<String> {
+    STACK_ALLOCATED();
 public:
-    StringTypeAdapter(const UChar* buffer);
-
-    unsigned length() { return m_length; }
+    explicit StringTypeAdapter(const String& string)
+        : m_buffer(string) {}
 
-    bool is8Bit() { return false; }
-
-    void writeTo(LChar*)
-    {
-        RELEASE_ASSERT(false);
-    }
+    unsigned length() const { return m_buffer.length(); }
+    bool is8Bit() const { return m_buffer.isNull() || m_buffer.is8Bit(); }
 
-    void writeTo(UChar* destination);
+    void writeTo(LChar* destination) const;
+    void writeTo(UChar* destination) const;
 
 private:
-    const UChar* m_buffer;
-    unsigned m_length;
+    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 WTF_EXPORT StringTypeAdapter<const char*> {
-    DISALLOW_NEW();
+class StringTypeAdapter<AtomicString> : public StringTypeAdapter<String> {
+    STACK_ALLOCATED();
 public:
-    StringTypeAdapter<const char*>(const char* buffer);
-
-    unsigned length() { return m_length; }
-
-    bool is8Bit() { return true; }
-
-    void writeTo(LChar* destination);
-
-    void writeTo(UChar* destination);
+    explicit StringTypeAdapter(const AtomicString& string)
+        : StringTypeAdapter<String>(string) {}
+};
 
-private:
-    const char* m_buffer;
-    unsigned m_length;
+namespace internal {
+WTF_EXPORT unsigned checkedAddLength(unsigned length1, unsigned length2);
 };
 
-template<>
-class WTF_EXPORT StringTypeAdapter<const LChar*> {
-    DISALLOW_NEW();
+template<typename StringType1, typename StringType2>
+class StringAppend final {
+    STACK_ALLOCATED();
 public:
-    StringTypeAdapter<const LChar*>(const LChar* buffer);
+    StringAppend(StringType1 string1, StringType2 string2)
+        : m_adapter1(string1)
+        , m_adapter2(string2) {}
 
-    unsigned length() { return m_length; }
+    operator String() const { return toString(); }
+    operator AtomicString() const { return AtomicString(toString()); }
 
-    bool is8Bit() { return true; }
+    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);
-
-    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)
+    void writeTo(LChar* destination) const
     {
+        DCHECK(is8Bit());
+        m_adapter1.writeTo(destination);
+        m_adapter2.writeTo(destination + m_adapter1.length());
     }
 
-    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)
+    void writeTo(UChar* destination) const
     {
+        m_adapter1.writeTo(destination);
+        m_adapter2.writeTo(destination + m_adapter1.length());
     }
 
-    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;
-};
-
-template<>
-class WTF_EXPORT StringTypeAdapter<String> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter<String>(const String& string)
-        : m_buffer(string)
+    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();
     }
 
-    unsigned length() { return m_buffer.length(); }
+    StringTypeAdapter<StringType1> m_adapter1;
+    StringTypeAdapter<StringType2> m_adapter2;
+};
 
-    bool is8Bit() { return m_buffer.isNull() || m_buffer.is8Bit(); }
+template<typename StringType1, typename StringType2>
+class StringTypeAdapter<StringAppend<StringType1, StringType2>> {
+    STACK_ALLOCATED();
+public:
+    explicit StringTypeAdapter(const StringAppend<StringType1, StringType2>& buffer)
+        : m_buffer(buffer) {}
 
-    void writeTo(LChar* destination);
+    unsigned length() const { return m_buffer.length(); }
+    bool is8Bit() const { return m_buffer.is8Bit(); }
 
-    void writeTo(UChar* destination);
+    void writeTo(LChar* destination) const { m_buffer.writeTo(destination); }
+    void writeTo(UChar* destination) const { m_buffer.writeTo(destination); }
 
 private:
-    const String& m_buffer;
+    const StringAppend<StringType1, StringType2> m_buffer;
 };
 
-template<>
-class StringTypeAdapter<AtomicString> {
-    DISALLOW_NEW();
-public:
-    StringTypeAdapter<AtomicString>(const AtomicString& string)
-        : m_adapter(string.getString())
-    {
-    }
+inline StringAppend<const LChar*, String> operator+(const char* string1, const String& string2)
+{
+    return StringAppend<const LChar*, String>(reinterpret_cast<const LChar*>(string1), string2);
+}
 
-    unsigned length() { return m_adapter.length(); }
+inline StringAppend<const LChar*, AtomicString> operator+(const char* string1, const AtomicString& string2)
+{
+    return StringAppend<const LChar*, AtomicString>(reinterpret_cast<const LChar*>(string1), string2);
+}
 
-    bool is8Bit() { return m_adapter.is8Bit(); }
+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);
+}
 
-    void writeTo(LChar* destination) { m_adapter.writeTo(destination); }
-    void writeTo(UChar* destination) { m_adapter.writeTo(destination); }
+inline StringAppend<const UChar*, String> operator+(const UChar* string1, const String& string2)
+{
+    return StringAppend<const UChar*, String>(string1, string2);
+}
 
-private:
-    StringTypeAdapter<String> m_adapter;
-};
+inline StringAppend<const UChar*, AtomicString> operator+(const UChar* string1, const AtomicString& string2)
+{
+    return StringAppend<const UChar*, AtomicString>(string1, string2);
+}
 
-inline void sumWithOverflow(unsigned& total, unsigned addend, bool& overflow)
+template<typename U, typename V>
+inline StringAppend<const UChar*, StringAppend<U, V>> operator+(const UChar* string1, const StringAppend<U, V>& string2)
 {
-    unsigned oldTotal = total;
-    total = oldTotal + addend;
-    if (total < oldTotal)
-        overflow = true;
+    return StringAppend<const UChar*, StringAppend<U, V>>(string1, string2);
 }
 
-template<typename StringType1, typename StringType2>
-PassRefPtr<StringImpl> makeString(StringType1 string1, StringType2 string2)
+inline StringAppend<String, const LChar*> operator+(const String& string1, const char* 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();
-    }
+    return StringAppend<String, const LChar*>(string1, reinterpret_cast<const LChar*>(string2));
+}
 
-    UChar* buffer;
-    RefPtr<StringImpl> resultImpl = StringImpl::createUninitialized(length, buffer);
-    if (!resultImpl)
-        return nullptr;
+template<typename T>
+inline StringAppend<String, T> operator+(const String& string1, T string2)
+{
+    return StringAppend<String, T>(string1, string2);
+}
 
-    UChar* result = buffer;
-    adapter1.writeTo(result);
-    result += adapter1.length();
-    adapter2.writeTo(result);
+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));
+}
 
-    return resultImpl.release();
+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