Introduce StringImpl::StaticStringImpl with constexpr constructor
authorutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 1 Dec 2016 09:24:21 +0000 (09:24 +0000)
committerutatane.tea@gmail.com <utatane.tea@gmail.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 1 Dec 2016 09:24:21 +0000 (09:24 +0000)
https://bugs.webkit.org/show_bug.cgi?id=165093

Reviewed by Darin Adler.

Source/WTF:

This patch adds new class, StringImpl::StaticStringImpl.
By using this class, we can easily create static StringImpls.
This class has constexpr constructor. You can initialize instances
of this class as global static variables without invoking global
constructors.

We already have similar system, StaticASCIILiteral. But using it
requires some special perl script since we need to calculate
hash value. On the other hand, we can use StaticStringImpl without
any script supports since we implement constexpr hash function.
In the future, we will replace all the use of StaticASCIILiteral
with this StaticStringImpl.

We define empty / null strings as StaticStringImpl. And we make
StringImpl::empty() & StringImpl::null() inline functions.

* wtf/Hasher.h:
(WTF::StringHasher::hashWithTop8BitsMasked):
(WTF::StringHasher::hash):
(WTF::StringHasher::finalize):
(WTF::StringHasher::finalizeAndMaskTop8Bits):
(WTF::StringHasher::computeLiteralHash):
(WTF::StringHasher::computeLiteralHashAndMaskTop8Bits):
(WTF::StringHasher::avalancheBits3):
(WTF::StringHasher::avalancheBits2):
(WTF::StringHasher::avalancheBits1):
(WTF::StringHasher::avalancheBits0):
(WTF::StringHasher::avalancheBits):
(WTF::StringHasher::avoidZero):
(WTF::StringHasher::processPendingCharacter):
(WTF::StringHasher::calculateWithRemainingLastCharacter1):
(WTF::StringHasher::calculateWithRemainingLastCharacter0):
(WTF::StringHasher::calculateWithRemainingLastCharacter):
(WTF::StringHasher::calculate1):
(WTF::StringHasher::calculate0):
(WTF::StringHasher::calculate):
(WTF::StringHasher::computeLiteralHashImpl):
* wtf/text/StringImpl.cpp:
* wtf/text/StringImpl.h:
(WTF::StringImpl::StaticStringImpl::StaticStringImpl):
(WTF::StringImpl::null):
(WTF::StringImpl::empty):
* wtf/text/StringStatics.cpp:
(WTF::StringImpl::null): Deleted.
(WTF::StringImpl::empty): Deleted.

Tools:

* TestWebKitAPI/Tests/WTF/StringImpl.cpp:
(TestWebKitAPI::TEST):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@209179 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WTF/ChangeLog
Source/WTF/wtf/Hasher.h
Source/WTF/wtf/text/StringImpl.cpp
Source/WTF/wtf/text/StringImpl.h
Source/WTF/wtf/text/StringStatics.cpp
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WTF/StringImpl.cpp

index 25a632e..cfca090 100644 (file)
@@ -1,3 +1,56 @@
+2016-12-01  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        Introduce StringImpl::StaticStringImpl with constexpr constructor
+        https://bugs.webkit.org/show_bug.cgi?id=165093
+
+        Reviewed by Darin Adler.
+
+        This patch adds new class, StringImpl::StaticStringImpl.
+        By using this class, we can easily create static StringImpls.
+        This class has constexpr constructor. You can initialize instances
+        of this class as global static variables without invoking global
+        constructors.
+
+        We already have similar system, StaticASCIILiteral. But using it
+        requires some special perl script since we need to calculate
+        hash value. On the other hand, we can use StaticStringImpl without
+        any script supports since we implement constexpr hash function.
+        In the future, we will replace all the use of StaticASCIILiteral
+        with this StaticStringImpl.
+
+        We define empty / null strings as StaticStringImpl. And we make
+        StringImpl::empty() & StringImpl::null() inline functions.
+
+        * wtf/Hasher.h:
+        (WTF::StringHasher::hashWithTop8BitsMasked):
+        (WTF::StringHasher::hash):
+        (WTF::StringHasher::finalize):
+        (WTF::StringHasher::finalizeAndMaskTop8Bits):
+        (WTF::StringHasher::computeLiteralHash):
+        (WTF::StringHasher::computeLiteralHashAndMaskTop8Bits):
+        (WTF::StringHasher::avalancheBits3):
+        (WTF::StringHasher::avalancheBits2):
+        (WTF::StringHasher::avalancheBits1):
+        (WTF::StringHasher::avalancheBits0):
+        (WTF::StringHasher::avalancheBits):
+        (WTF::StringHasher::avoidZero):
+        (WTF::StringHasher::processPendingCharacter):
+        (WTF::StringHasher::calculateWithRemainingLastCharacter1):
+        (WTF::StringHasher::calculateWithRemainingLastCharacter0):
+        (WTF::StringHasher::calculateWithRemainingLastCharacter):
+        (WTF::StringHasher::calculate1):
+        (WTF::StringHasher::calculate0):
+        (WTF::StringHasher::calculate):
+        (WTF::StringHasher::computeLiteralHashImpl):
+        * wtf/text/StringImpl.cpp:
+        * wtf/text/StringImpl.h:
+        (WTF::StringImpl::StaticStringImpl::StaticStringImpl):
+        (WTF::StringImpl::null):
+        (WTF::StringImpl::empty):
+        * wtf/text/StringStatics.cpp:
+        (WTF::StringImpl::null): Deleted.
+        (WTF::StringImpl::empty): Deleted.
+
 2016-11-30  Darin Adler  <darin@apple.com>
 
         Roll out StringBuilder changes from the previous patch.
index 0234bb2..c0a2e8c 100644 (file)
@@ -36,11 +36,12 @@ namespace WTF {
 // JavaScriptCore and the CodeGeneratorJS.pm script in WebCore.
 
 // Golden ratio. Arbitrary start value to avoid mapping all zeros to a hash value of zero.
-static const unsigned stringHashingStartValue = 0x9E3779B9U;
+static constexpr const unsigned stringHashingStartValue = 0x9E3779B9U;
 
 class StringHasher {
 public:
-    static const unsigned flagCount = 8; // Save 8 bits for StringImpl to use as flags.
+    static constexpr const unsigned flagCount = 8; // Save 8 bits for StringImpl to use as flags.
+    static constexpr const unsigned maskHash = (1U << (sizeof(unsigned) * 8 - flagCount)) - 1;
 
     StringHasher()
         : m_hash(stringHashingStartValue)
@@ -162,34 +163,12 @@ public:
 
     unsigned hashWithTop8BitsMasked() const
     {
-        unsigned result = avalancheBits();
-
-        // Reserving space from the high bits for flags preserves most of the hash's
-        // value, since hash lookup typically masks out the high bits anyway.
-        result &= (1U << (sizeof(result) * 8 - flagCount)) - 1;
-
-        // This avoids ever returning a hash code of 0, since that is used to
-        // signal "hash not computed yet". Setting the high bit maintains
-        // reasonable fidelity to a hash code of 0 because it is likely to yield
-        // exactly 0 when hash lookup masks out the high bits.
-        if (!result)
-            result = 0x80000000 >> flagCount;
-
-        return result;
+        return finalizeAndMaskTop8Bits(processPendingCharacter());
     }
 
     unsigned hash() const
     {
-        unsigned result = avalancheBits();
-
-        // This avoids ever returning a hash code of 0, since that is used to
-        // signal "hash not computed yet". Setting the high bit maintains
-        // reasonable fidelity to a hash code of 0 because it is likely to yield
-        // exactly 0 when hash lookup masks out the high bits.
-        if (!result)
-            result = 0x80000000;
-
-        return result;
+        return finalize(processPendingCharacter());
     }
 
     template<typename T, UChar Converter(T)> static unsigned computeHashAndMaskTop8Bits(const T* data, unsigned length)
@@ -257,6 +236,30 @@ public:
         return hashMemory(data, length);
     }
 
+    static constexpr unsigned finalize(unsigned hash)
+    {
+        return avoidZero(avalancheBits(hash));
+    }
+
+    static constexpr unsigned finalizeAndMaskTop8Bits(unsigned hash)
+    {
+        // Reserving space from the high bits for flags preserves most of the hash's
+        // value, since hash lookup typically masks out the high bits anyway.
+        return avoidZero(avalancheBits(hash) & StringHasher::maskHash);
+    }
+
+    template<typename T, unsigned charactersCount>
+    static constexpr unsigned computeLiteralHash(const T (&characters)[charactersCount])
+    {
+        return StringHasher::finalize(computeLiteralHashImpl(stringHashingStartValue, 0, characters, charactersCount - 1));
+    }
+
+    template<typename T, unsigned charactersCount>
+    static constexpr unsigned computeLiteralHashAndMaskTop8Bits(const T (&characters)[charactersCount])
+    {
+        return StringHasher::finalizeAndMaskTop8Bits(computeLiteralHashImpl(stringHashingStartValue, 0, characters, charactersCount - 1));
+    }
+
 private:
     static UChar defaultConverter(UChar character)
     {
@@ -268,7 +271,41 @@ private:
         return character;
     }
 
-    unsigned avalancheBits() const
+    ALWAYS_INLINE static constexpr unsigned avalancheBits3(unsigned hash)
+    {
+        return hash ^ (hash << 10);
+    }
+
+    ALWAYS_INLINE static constexpr unsigned avalancheBits2(unsigned hash)
+    {
+        return avalancheBits3(hash + (hash >> 15));
+    }
+
+    ALWAYS_INLINE static constexpr unsigned avalancheBits1(unsigned hash)
+    {
+        return avalancheBits2(hash ^ (hash << 2));
+    }
+
+    ALWAYS_INLINE static constexpr unsigned avalancheBits0(unsigned hash)
+    {
+        return avalancheBits1(hash + (hash >> 5));
+    }
+
+    ALWAYS_INLINE static constexpr unsigned avalancheBits(unsigned hash)
+    {
+        return avalancheBits0(hash ^ (hash << 3));
+    }
+
+    // This avoids ever returning a hash code of 0, since that is used to
+    // signal "hash not computed yet". Setting the high bit maintains
+    // reasonable fidelity to a hash code of 0 because it is likely to yield
+    // exactly 0 when hash lookup masks out the high bits.
+    ALWAYS_INLINE static constexpr unsigned avoidZero(unsigned hash)
+    {
+        return hash ? hash : (0x80000000 >> StringHasher::flagCount);
+    }
+
+    unsigned processPendingCharacter() const
     {
         unsigned result = m_hash;
 
@@ -278,15 +315,49 @@ private:
             result ^= result << 11;
             result += result >> 17;
         }
+        return result;
+    }
 
-        // Force "avalanching" of final 31 bits.
-        result ^= result << 3;
-        result += result >> 5;
-        result ^= result << 2;
-        result += result >> 15;
-        result ^= result << 10;
 
-        return result;
+    // FIXME: This code limits itself to the older, more limited C++11 constexpr capabilities, using
+    // recursion instead of looping, for example. Would be nice to rewrite this in a simpler way
+    // once we no longer need to support compilers like GCC 4.9 that do not yet support it.
+    static constexpr unsigned calculateWithRemainingLastCharacter1(unsigned hash)
+    {
+        return hash + (hash >> 17);
+    }
+
+    static constexpr unsigned calculateWithRemainingLastCharacter0(unsigned hash)
+    {
+        return calculateWithRemainingLastCharacter1((hash << 11) ^ hash);
+    }
+
+    static constexpr unsigned calculateWithRemainingLastCharacter(unsigned hash, unsigned character)
+    {
+        return calculateWithRemainingLastCharacter0(hash + character);
+    }
+
+    static constexpr unsigned calculate1(unsigned hash)
+    {
+        return hash + (hash >> 11);
+    }
+
+    static constexpr unsigned calculate0(unsigned hash, unsigned secondCharacter)
+    {
+        return calculate1((hash << 16) ^ ((secondCharacter << 11) ^ hash));
+    }
+
+    static constexpr unsigned calculate(unsigned hash, unsigned firstCharacter, unsigned secondCharacter)
+    {
+        return calculate0(hash + firstCharacter, secondCharacter);
+    }
+
+    static constexpr unsigned computeLiteralHashImpl(unsigned hash, unsigned index, const char* characters, unsigned length)
+    {
+        return (index == length)
+            ? hash : ((index + 1) == length)
+            ? calculateWithRemainingLastCharacter(hash, characters[index])
+            : computeLiteralHashImpl(calculate(hash, characters[index], characters[index + 1]), index + 2, characters, length);
     }
 
     unsigned m_hash;
index 5cd66c1..7d0a701 100644 (file)
@@ -101,6 +101,8 @@ void StringStats::printStats()
 }
 #endif
 
+StringImpl::StaticStringImpl StringImpl::s_atomicNullString("", StringImpl::StringAtomic);
+StringImpl::StaticStringImpl StringImpl::s_atomicEmptyString("", StringImpl::StringAtomic);
 
 StringImpl::~StringImpl()
 {
index 176aa59..8e0f3e7 100644 (file)
@@ -149,18 +149,18 @@ private:
 
     // The bottom 6 bits in the hash are flags.
 public:
-    static const unsigned s_flagCount = 6;
+    static constexpr const unsigned s_flagCount = 6;
 private:
-    static const unsigned s_flagMask = (1u << s_flagCount) - 1;
-    COMPILE_ASSERT(s_flagCount <= StringHasher::flagCount, StringHasher_reserves_enough_bits_for_StringImpl_flags);
-    static const unsigned s_flagStringKindCount = 4;
+    static constexpr const unsigned s_flagMask = (1u << s_flagCount) - 1;
+    static_assert(s_flagCount <= StringHasher::flagCount, "StringHasher reserves enough bits for StringImpl flags");
+    static constexpr const unsigned s_flagStringKindCount = 4;
 
-    static const unsigned s_hashFlagStringKindIsAtomic = 1u << (s_flagStringKindCount);
-    static const unsigned s_hashFlagStringKindIsSymbol = 1u << (s_flagStringKindCount + 1);
-    static const unsigned s_hashMaskStringKind = s_hashFlagStringKindIsAtomic | s_hashFlagStringKindIsSymbol;
-    static const unsigned s_hashFlag8BitBuffer = 1u << 3;
-    static const unsigned s_hashFlagDidReportCost = 1u << 2;
-    static const unsigned s_hashMaskBufferOwnership = (1u << 0) | (1u << 1);
+    static constexpr const unsigned s_hashFlagStringKindIsAtomic = 1u << (s_flagStringKindCount);
+    static constexpr const unsigned s_hashFlagStringKindIsSymbol = 1u << (s_flagStringKindCount + 1);
+    static constexpr const unsigned s_hashMaskStringKind = s_hashFlagStringKindIsAtomic | s_hashFlagStringKindIsSymbol;
+    static constexpr const unsigned s_hashFlag8BitBuffer = 1u << 3;
+    static constexpr const unsigned s_hashFlagDidReportCost = 1u << 2;
+    static constexpr const unsigned s_hashMaskBufferOwnership = (1u << 0) | (1u << 1);
 
     enum StringKind {
         StringNormal = 0u, // non-symbol, non-atomic
@@ -168,25 +168,6 @@ private:
         StringSymbol = s_hashFlagStringKindIsSymbol, // symbol, non-atomic
     };
 
-    // Used to construct static strings, which have an special refCount that can never hit zero.
-    // This means that the static string will never be destroyed, which is important because
-    // static strings will be shared across threads & ref-counted in a non-threadsafe manner.
-    friend class NeverDestroyed<StringImpl>;
-    enum ConstructEmptyStringTag { ConstructEmptyString };
-    StringImpl(ConstructEmptyStringTag)
-        : m_refCount(s_refCountFlagIsStaticString)
-        , m_length(0)
-        , m_data8(reinterpret_cast<const LChar*>(&m_length))
-        , m_hashAndFlags(s_hashFlag8BitBuffer | StringAtomic | BufferOwned)
-    {
-        // Ensure that the hash is computed so that AtomicStringHash can call existingHash()
-        // with impunity. The empty string is special because it is never entered into
-        // AtomicString's HashKey, but still needs to compare correctly.
-        STRING_STATS_ADD_8BIT_STRING(m_length);
-
-        hash();
-    }
-
     // FIXME: there has to be a less hacky way to do this.
     enum Force8Bit { Force8BitConstructor };
     // Create a normal 8-bit string with internal storage (BufferInternal)
@@ -606,7 +587,43 @@ public:
         m_refCount = tempRefCount;
     }
 
-    WTF_EXPORT_PRIVATE static StringImpl* empty();
+    class StaticStringImpl {
+    public:
+        // Used to construct static strings, which have an special refCount that can never hit zero.
+        // This means that the static string will never be destroyed, which is important because
+        // static strings will be shared across threads & ref-counted in a non-threadsafe manner.
+        template<unsigned charactersCount>
+        constexpr StaticStringImpl(const char (&characters)[charactersCount], StringKind stringKind = StringNormal)
+            : m_refCount(s_refCountFlagIsStaticString)
+            , m_length(charactersCount - 1)
+            , m_data8(characters)
+            , m_hashAndFlags(s_hashFlag8BitBuffer | stringKind | BufferInternal | (StringHasher::computeLiteralHashAndMaskTop8Bits(characters) << s_flagCount))
+        {
+        }
+
+        template<unsigned charactersCount>
+        constexpr StaticStringImpl(const char16_t (&characters)[charactersCount], StringKind stringKind = StringNormal)
+            : m_refCount(s_refCountFlagIsStaticString)
+            , m_length(charactersCount - 1)
+            , m_data16(characters)
+            , m_hashAndFlags(stringKind | BufferInternal | (StringHasher::computeLiteralHashAndMaskTop8Bits(characters) << s_flagCount))
+        {
+        }
+
+        // These member variables must match the layout of StringImpl.
+        unsigned m_refCount;
+        unsigned m_length;
+        union {
+            const char* m_data8;
+            const char16_t* m_data16;
+        };
+        unsigned m_hashAndFlags;
+    };
+
+    WTF_EXPORTDATA static StaticStringImpl s_atomicNullString;
+    WTF_EXPORTDATA static StaticStringImpl s_atomicEmptyString;
+    ALWAYS_INLINE static StringImpl* null() { return reinterpret_cast<StringImpl*>(&s_atomicNullString); }
+    ALWAYS_INLINE static StringImpl* empty() { return reinterpret_cast<StringImpl*>(&s_atomicEmptyString); }
 
     // FIXME: Does this really belong in StringImpl?
     template <typename T> static void copyChars(T* destination, const T* source, unsigned numCharacters)
@@ -866,7 +883,6 @@ private:
     template <typename CharType> static Ref<StringImpl> createInternal(const CharType*, unsigned);
     WTF_EXPORT_PRIVATE NEVER_INLINE unsigned hashSlowCase() const;
     WTF_EXPORT_PRIVATE static unsigned nextHashForSymbol();
-    WTF_EXPORT_PRIVATE static StringImpl* null();
 
     // The bottom bit in the ref count indicates a static (immortal) string.
     static const unsigned s_refCountFlagIsStaticString = 0x1;
@@ -877,6 +893,8 @@ private:
 #endif
 
 public:
+    // FIXME: It should be replaced with StaticStringImpl.
+    // https://bugs.webkit.org/show_bug.cgi?id=165134
     struct StaticASCIILiteral {
         // These member variables must match the layout of StringImpl.
         unsigned m_refCount;
@@ -899,7 +917,7 @@ public:
 #endif
 
 private:
-    // These member variables must match the layout of StaticASCIILiteral.
+    // These member variables must match the layout of StaticASCIILiteral and StaticStringImpl.
     unsigned m_refCount;
     unsigned m_length;
     union {
@@ -910,6 +928,7 @@ private:
 };
 
 static_assert(sizeof(StringImpl) == sizeof(StringImpl::StaticASCIILiteral), "");
+static_assert(sizeof(StringImpl) == sizeof(StringImpl::StaticStringImpl), "");
 
 #if !ASSERT_DISABLED
 // StringImpls created from StaticASCIILiteral will ASSERT
index ad9e6e3..0d254a5 100644 (file)
 
 namespace WTF {
 
-StringImpl* StringImpl::null()
-{
-    static NeverDestroyed<StringImpl> nullString(ConstructEmptyString);
-    return &nullString.get();
-}
-
-StringImpl* StringImpl::empty()
-{
-    static NeverDestroyed<StringImpl> emptyString(ConstructEmptyString);
-    return &emptyString.get();
-}
-
 // In addition to the normal hash value, store specialized hash value for
 // symbolized StringImpl*. And don't use the normal hash value for symbolized
 // StringImpl* when they are treated as Identifiers. Unique nature of these
index b3aff1c..add427d 100644 (file)
@@ -1,3 +1,13 @@
+2016-12-01  Yusuke Suzuki  <utatane.tea@gmail.com>
+
+        Introduce StringImpl::StaticStringImpl with constexpr constructor
+        https://bugs.webkit.org/show_bug.cgi?id=165093
+
+        Reviewed by Darin Adler.
+
+        * TestWebKitAPI/Tests/WTF/StringImpl.cpp:
+        (TestWebKitAPI::TEST):
+
 2016-11-30  Antoine Quint  <graouts@apple.com>
 
         [Modern Media Controls] Add an HTML comment flag to turn the feature on
index 9849dec..d3710fa 100644 (file)
@@ -25,6 +25,7 @@
 
 #include "config.h"
 
+#include <wtf/Hasher.h>
 #include <wtf/text/SymbolImpl.h>
 #include <wtf/text/WTFString.h>
 
@@ -574,4 +575,20 @@ TEST(WTF, StringImplNullSymbolToAtomicString)
     ASSERT_FALSE(reference->isAtomic());
 }
 
+TEST(WTF, StringImplConstexprHasher)
+{
+    ASSERT_EQ(stringFromUTF8("")->hash(), StringHasher::computeLiteralHashAndMaskTop8Bits(""));
+    ASSERT_EQ(stringFromUTF8("A")->hash(), StringHasher::computeLiteralHashAndMaskTop8Bits("A"));
+    ASSERT_EQ(stringFromUTF8("AA")->hash(), StringHasher::computeLiteralHashAndMaskTop8Bits("AA"));
+    ASSERT_EQ(stringFromUTF8("Cocoa")->hash(), StringHasher::computeLiteralHashAndMaskTop8Bits("Cocoa"));
+    ASSERT_EQ(stringFromUTF8("Cappuccino")->hash(), StringHasher::computeLiteralHashAndMaskTop8Bits("Cappuccino"));
+}
+
+TEST(WTF, StringImplEmpty)
+{
+    ASSERT_FALSE(StringImpl::empty()->length());
+    ASSERT_FALSE(StringImpl::null()->length());
+    ASSERT_NE(StringImpl::null(), StringImpl::empty());
+}
+
 } // namespace TestWebKitAPI