1 files changed, 122 insertions, 21 deletions

diff --git a/Source/WTF/wtf/HashTraits.h b/Source/WTF/wtf/HashTraits.h
index f14810021..542e7ad2c 100644
--- a/Source/WTF/wtf/HashTraits.h
+++ b/Source/WTF/wtf/HashTraits.h
@@ -21,18 +21,16 @@
 #ifndef WTF_HashTraits_h
 #define WTF_HashTraits_h
 
+#include <limits>
+#include <utility>
 #include <wtf/HashFunctions.h>
+#include <wtf/Optional.h>
 #include <wtf/StdLibExtras.h>
-#include <utility>
-#include <limits>
 
 namespace WTF {
 
 class String;
 
-template<typename T> class OwnPtr;
-template<typename T> class PassOwnPtr;
-
 template<typename T> struct HashTraits;
 
 template<bool isInteger, typename T> struct GenericHashTraitsBase;
@@ -48,7 +46,7 @@ template<typename T> struct GenericHashTraitsBase<false, T> {
 
     // The starting table size. Can be overridden when we know beforehand that
     // a hash table will have at least N entries.
-    static const int minimumTableSize = 8;
+    static const unsigned minimumTableSize = 8;
 };
 
 // Default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned).
@@ -64,10 +62,18 @@ template<typename T> struct GenericHashTraits : GenericHashTraitsBase<std::is_in
 
     static T emptyValue() { return T(); }
 
+    template<typename U, typename V> 
+    static void assignToEmpty(U& emptyValue, V&& value)
+    { 
+        emptyValue = std::forward<V>(value);
+    }
+
     // Type for return value of functions that do not transfer ownership, such as get.
     typedef T PeekType;
-    static PeekType peek(const T& value) { return value; }
-    static T& peek(T& value) { return value; } // Overloaded to avoid copying of non-temporary values.
+    template<typename U> static U&& peek(U&& value) { return std::forward<U>(value); }
+
+    typedef T TakeType;
+    template<typename U> static TakeType take(U&& value) { return std::forward<U>(value); }
 };
 
 template<typename T> struct HashTraits : GenericHashTraits<T> { };
@@ -89,6 +95,22 @@ template<typename T> struct UnsignedWithZeroKeyHashTraits : GenericHashTraits<T>
     static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max() - 1; }
 };
 
+template<typename T> struct SignedWithZeroKeyHashTraits : GenericHashTraits<T> {
+    static const bool emptyValueIsZero = false;
+    static T emptyValue() { return std::numeric_limits<T>::min(); }
+    static void constructDeletedValue(T& slot) { slot = std::numeric_limits<T>::max(); }
+    static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max(); }
+};
+
+// Can be used with strong enums, allows zero as key.
+template<typename T> struct StrongEnumHashTraits : GenericHashTraits<T> {
+    using UnderlyingType = typename std::underlying_type<T>::type;
+    static const bool emptyValueIsZero = false;
+    static T emptyValue() { return static_cast<T>(std::numeric_limits<UnderlyingType>::max()); }
+    static void constructDeletedValue(T& slot) { slot = static_cast<T>(std::numeric_limits<UnderlyingType>::max() - 1); }
+    static bool isDeletedValue(T value) { return value == static_cast<T>(std::numeric_limits<UnderlyingType>::max() - 1); }
+};
+
 template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
     static const bool emptyValueIsZero = true;
     static void constructDeletedValue(P*& slot) { slot = reinterpret_cast<P*>(-1); }
@@ -97,7 +119,7 @@ template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
 
 template<typename T> struct SimpleClassHashTraits : GenericHashTraits<T> {
     static const bool emptyValueIsZero = true;
-    static void constructDeletedValue(T& slot) { new (NotNull, &slot) T(HashTableDeletedValue); }
+    static void constructDeletedValue(T& slot) { new (NotNull, std::addressof(slot)) T(HashTableDeletedValue); }
     static bool isDeletedValue(const T& value) { return value.isHashTableDeletedValue(); }
 };
 
@@ -105,31 +127,76 @@ template<typename T, typename Deleter> struct HashTraits<std::unique_ptr<T, Dele
     typedef std::nullptr_t EmptyValueType;
     static EmptyValueType emptyValue() { return nullptr; }
 
+    static void constructDeletedValue(std::unique_ptr<T, Deleter>& slot) { new (NotNull, std::addressof(slot)) std::unique_ptr<T, Deleter> { reinterpret_cast<T*>(-1) }; }
+    static bool isDeletedValue(const std::unique_ptr<T, Deleter>& value) { return value.get() == reinterpret_cast<T*>(-1); }
+
     typedef T* PeekType;
     static T* peek(const std::unique_ptr<T, Deleter>& value) { return value.get(); }
     static T* peek(std::nullptr_t) { return nullptr; }
-};
-
-template<typename T> struct HashTraits<OwnPtr<T>> : SimpleClassHashTraits<OwnPtr<T>> {
-    typedef std::nullptr_t EmptyValueType;
-    static EmptyValueType emptyValue() { return nullptr; }
 
-    typedef T* PeekType;
-    static T* peek(const OwnPtr<T>& value) { return value.get(); }
-    static T* peek(std::nullptr_t) { return nullptr; }
+    static void customDeleteBucket(std::unique_ptr<T, Deleter>& value)
+    {
+        // The custom delete function exists to avoid a dead store before the value is destructed.
+        // The normal destruction sequence of a bucket would be:
+        // 1) Call the destructor of unique_ptr.
+        // 2) unique_ptr store a zero for its internal pointer.
+        // 3) unique_ptr destroys its value.
+        // 4) Call constructDeletedValue() to set the bucket as destructed.
+        //
+        // The problem is the call in (3) prevents the compile from eliminating the dead store in (2)
+        // becase a side effect of free() could be observing the value.
+        //
+        // This version of deleteBucket() ensures the dead 2 stores changing "value"
+        // are on the same side of the function call.
+        ASSERT(!isDeletedValue(value));
+        T* pointer = value.release();
+        constructDeletedValue(value);
+
+        // The null case happens if a caller uses std::move() to remove the pointer before calling remove()
+        // with an iterator. This is very uncommon.
+        if (LIKELY(pointer))
+            Deleter()(pointer);
+    }
 };
 
 template<typename P> struct HashTraits<RefPtr<P>> : SimpleClassHashTraits<RefPtr<P>> {
-    static P* emptyValue() { return 0; }
+    static P* emptyValue() { return nullptr; }
 
     typedef P* PeekType;
     static PeekType peek(const RefPtr<P>& value) { return value.get(); }
     static PeekType peek(P* value) { return value; }
+
+    static void customDeleteBucket(RefPtr<P>& value)
+    {
+        // See unique_ptr's customDeleteBucket() for an explanation.
+        ASSERT(!SimpleClassHashTraits<RefPtr<P>>::isDeletedValue(value));
+        auto valueToBeDestroyed = WTFMove(value);
+        SimpleClassHashTraits<RefPtr<P>>::constructDeletedValue(value);
+    }
+};
+
+template<typename P> struct HashTraits<Ref<P>> : SimpleClassHashTraits<Ref<P>> {
+    static const bool emptyValueIsZero = true;
+    static Ref<P> emptyValue() { return HashTableEmptyValue; }
+
+    static const bool hasIsEmptyValueFunction = true;
+    static bool isEmptyValue(const Ref<P>& value) { return value.isHashTableEmptyValue(); }
+
+    static void assignToEmpty(Ref<P>& emptyValue, Ref<P>&& newValue) { ASSERT(isEmptyValue(emptyValue)); emptyValue.assignToHashTableEmptyValue(WTFMove(newValue)); }
+
+    typedef P* PeekType;
+    static PeekType peek(const Ref<P>& value) { return const_cast<PeekType>(value.ptrAllowingHashTableEmptyValue()); }
+    static PeekType peek(P* value) { return value; }
+
+    typedef std::optional<Ref<P>> TakeType;
+    static TakeType take(Ref<P>&& value) { return isEmptyValue(value) ? std::nullopt : std::optional<Ref<P>>(WTFMove(value)); }
 };
 
 template<> struct HashTraits<String> : SimpleClassHashTraits<String> {
     static const bool hasIsEmptyValueFunction = true;
     static bool isEmptyValue(const String&);
+
+    static void customDeleteBucket(String&);
 };
 
 // This struct template is an implementation detail of the isHashTraitsEmptyValue function,
@@ -146,6 +213,30 @@ template<typename Traits, typename T> inline bool isHashTraitsEmptyValue(const T
     return HashTraitsEmptyValueChecker<Traits, Traits::hasIsEmptyValueFunction>::isEmptyValue(value);
 }
 
+template<typename Traits, typename T>
+struct HashTraitHasCustomDelete {
+    static T& bucketArg;
+    template<typename X> static std::true_type TestHasCustomDelete(X*, decltype(X::customDeleteBucket(bucketArg))* = nullptr);
+    static std::false_type TestHasCustomDelete(...);
+    typedef decltype(TestHasCustomDelete(static_cast<Traits*>(nullptr))) ResultType;
+    static const bool value = ResultType::value;
+};
+
+template<typename Traits, typename T>
+typename std::enable_if<HashTraitHasCustomDelete<Traits, T>::value>::type
+hashTraitsDeleteBucket(T& value)
+{
+    Traits::customDeleteBucket(value);
+}
+
+template<typename Traits, typename T>
+typename std::enable_if<!HashTraitHasCustomDelete<Traits, T>::value>::type
+hashTraitsDeleteBucket(T& value)
+{
+    value.~T();
+    Traits::constructDeletedValue(value);
+}
+
 template<typename FirstTraitsArg, typename SecondTraitsArg>
 struct PairHashTraits : GenericHashTraits<std::pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType>> {
     typedef FirstTraitsArg FirstTraits;
@@ -156,7 +247,7 @@ struct PairHashTraits : GenericHashTraits<std::pair<typename FirstTraitsArg::Tra
     static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
     static EmptyValueType emptyValue() { return std::make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); }
 
-    static const int minimumTableSize = FirstTraits::minimumTableSize;
+    static const unsigned minimumTableSize = FirstTraits::minimumTableSize;
 
     static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot.first); }
     static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); }
@@ -197,14 +288,24 @@ struct KeyValuePairHashTraits : GenericHashTraits<KeyValuePair<typename KeyTrait
     typedef ValueTraitsArg ValueTraits;
     typedef KeyValuePair<typename KeyTraits::TraitType, typename ValueTraits::TraitType> TraitType;
     typedef KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType> EmptyValueType;
+    typedef typename ValueTraitsArg::TraitType ValueType;
 
     static const bool emptyValueIsZero = KeyTraits::emptyValueIsZero && ValueTraits::emptyValueIsZero;
     static EmptyValueType emptyValue() { return KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType>(KeyTraits::emptyValue(), ValueTraits::emptyValue()); }
 
-    static const int minimumTableSize = KeyTraits::minimumTableSize;
+    static const unsigned minimumTableSize = KeyTraits::minimumTableSize;
 
     static void constructDeletedValue(TraitType& slot) { KeyTraits::constructDeletedValue(slot.key); }
     static bool isDeletedValue(const TraitType& value) { return KeyTraits::isDeletedValue(value.key); }
+
+    static void customDeleteBucket(TraitType& value)
+    {
+        static_assert(std::is_trivially_destructible<KeyValuePair<int, int>>::value,
+            "The wrapper itself has to be trivially destructible for customDeleteBucket() to make sense, since we do not destruct the wrapper itself.");
+
+        hashTraitsDeleteBucket<KeyTraits>(value.key);
+        value.value.~ValueType();
+    }
 };
 
 template<typename Key, typename Value>
@@ -225,7 +326,7 @@ struct CustomHashTraits : public GenericHashTraits<T> {
     
     static void constructDeletedValue(T& slot)
     {
-        new (NotNull, &slot) T(T::DeletedValue);
+        new (NotNull, std::addressof(slot)) T(T::DeletedValue);
     }
     
     static bool isDeletedValue(const T& value)