Attachment 272708 Details for Bug 154941 – Patch and Unit tests

[patch] Patch and Unit tests

bug-154941-20160302170752.patch (text/plain), 12.55 KB, created by Daniel Bates on 2016-03-02 17:08:07 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Daniel Bates

Created: 2016-03-02 17:08:07 PST

Size: 12.55 KB

patch

obsolete

>Subversion Revision: 197424
>diff --git a/Source/WTF/ChangeLog b/Source/WTF/ChangeLog
>index b8ebe9f80f93a9ff98acb7609eab1755999265e5..6650448fcdb1856dc34509fb4437ec04bdb68ba8 100644
>--- a/Source/WTF/ChangeLog
>+++ b/Source/WTF/ChangeLog
>@@ -1,5 +1,35 @@
> 2016-03-02  Daniel Bates  <dabates@apple.com>
> 
>+        Support iterating over an OptionSet and checking if it is empty
>+        https://bugs.webkit.org/show_bug.cgi?id=154941
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        Implements support for iterating over the enumerators in an OptionSet as well as
>+        determining if the set is empty.
>+
>+        Iterating over an OptionSet is in Big Theta(N) where N is the number of items in
>+        the set. More precisely, it is in Big Theta(log M) where M is the bitmask represented
>+        by the bitwise OR-ing of all enumerators in the set.
>+
>+        * wtf/OptionSet.h: Added comment to describe the purpose of this class and its invariant -
>+        the enumerators must be positive powers of two.
>+        (WTF::OptionSet::fromRaw): Instantiate using specialized private constructor to allow
>+        instantiation with a raw value of 0.
>+        (WTF::OptionSet::OptionSet): Specialized constructor that asserts that the specified value
>+        is a positive power of two. This variant is only compiled when assertions are enabled (i.e. !ASSERT_DISABLED).
>+        (WTF::OptionSet::isEmpty): Returns whether the set is empty.
>+        (WTF::OptionSet::begin): Returns an iterator to the enumerator with the smallest value in the set.
>+        (WTF::OptionSet::end): Returns an iterator that represents the end sentinel of the set.
>+        (WTF::OptionSetIterator::OptionSetIterator): Implements a forward iterator for the set.
>+        (WTF::OptionSetIterator::operator=): Added.
>+        (WTF::OptionSetIterator::operator*): Returns the enumerator pointed to by the iterator.
>+        (WTF::OptionSetIterator::operator++): Advance to the next smallest enumerator in the set. 
>+        (WTF::OptionSetIterator::operator==): Returns whether the iterator is equal to the specified iterator.
>+        (WTF::OptionSetIterator::operator!=): Returns whether the iterator is not equal to the specified iterator.
>+
>+2016-03-02  Daniel Bates  <dabates@apple.com>
>+
>         Add unit tests for WTF::OptionSet
>         https://bugs.webkit.org/show_bug.cgi?id=154925
> 
>diff --git a/Source/WTF/wtf/OptionSet.h b/Source/WTF/wtf/OptionSet.h
>index e99e976b29013eb690be0d8d0f4f516e8b7e8822..a9ba40467a84eb6ccbfec2ba3228791350db1bd0 100644
>--- a/Source/WTF/wtf/OptionSet.h
>+++ b/Source/WTF/wtf/OptionSet.h
>@@ -27,18 +27,28 @@
> #define OptionSet_h
> 
> #include <initializer_list>
>+#include <iterator>
> #include <type_traits>
>+#include <wtf/Assertions.h>
>+#include <wtf/MathExtras.h>
> 
> namespace WTF {
> 
>+template<typename T, typename StorageType> class OptionSetIterator;
>+
>+// OptionSet is a class that represents a set of enumerators in a space-efficient manner. The enumerators
>+// must be powers of two greater than 0. This class is useful as a replacement for passing a bitmask of
>+// enumerators around.
> template<typename T> class OptionSet {
>     static_assert(std::is_enum<T>::value, "T is not an enum type");
>     typedef typename std::make_unsigned<typename std::underlying_type<T>::type>::type StorageType;
> 
> public:
>+    typedef OptionSetIterator<T, StorageType> iterator;
>+
>     static OptionSet fromRaw(StorageType storageType)
>     {
>-        return static_cast<T>(storageType);
>+        return OptionSet(static_cast<T>(storageType), OptionSet::FromRawValue);
>     }
> 
>     constexpr OptionSet()
>@@ -46,22 +56,37 @@ public:
>     {
>     }
> 
>+#if ASSERT_DISABLED
>     constexpr OptionSet(T t)
>         : m_storage(static_cast<StorageType>(t))
>     {
>     }
>+#else
>+    OptionSet(T t)
>+        : m_storage(static_cast<StorageType>(t))
>+    {
>+        ASSERT_WITH_MESSAGE(hasOneBitSet(static_cast<StorageType>(t)), "Enumerator is not a positive power of two.");
>+    }
>+#endif
> 
>     // FIXME: Make this constexpr once we adopt C++14 as C++11 does not support for-loops
>     // in a constexpr function.
>     OptionSet(std::initializer_list<T> initializerList)
>         : m_storage(0)
>     {
>-        for (auto& option : initializerList)
>+        for (auto& option : initializerList) {
>+            ASSERT_WITH_MESSAGE(hasOneBitSet(static_cast<StorageType>(option)), "Enumerator is not a positive power of two.");
>             m_storage |= static_cast<StorageType>(option);
>+        }
>     }
> 
>     constexpr StorageType toRaw() const { return m_storage; }
> 
>+    constexpr StorageType isEmpty() const { return !m_storage; }
>+
>+    constexpr iterator begin() const { return m_storage; }
>+    constexpr iterator end() const { return 0; }
>+
>     constexpr bool contains(OptionSet optionSet) const
>     {
>         return m_storage & optionSet.m_storage;
>@@ -75,9 +100,44 @@ public:
>     }
> 
> private:
>+    enum InitializationTag { FromRawValue };
>+    constexpr OptionSet(T t, InitializationTag)
>+        : m_storage(static_cast<StorageType>(t))
>+    {
>+    }
>     StorageType m_storage;
> };
> 
>+template<typename T, typename StorageType> class OptionSetIterator {
>+public:
>+    OptionSetIterator(const StorageType value) : m_value(value) { }
>+    OptionSetIterator(const OptionSetIterator& other) : m_value(other.m_value) { }
>+
>+    OptionSetIterator& operator=(const OptionSetIterator& other)
>+    {
>+        m_value = other.m_value;
>+        return *this;
>+    }
>+
>+    // Isolate the rightmost set bit.
>+    T operator*() const { return static_cast<T>(m_value & -m_value); }
>+
>+    // Iterates from smallest to largest enum value by turning off the rightmost set bit.
>+    OptionSetIterator& operator++()
>+    {
>+        m_value &= m_value - 1;
>+        return *this;
>+    }
>+
>+    OptionSetIterator& operator++(int) = delete;
>+
>+    bool operator==(const OptionSetIterator& other) const { return m_value == other.m_value; }
>+    bool operator!=(const OptionSetIterator& other) const { return m_value != other.m_value; }
>+
>+private:
>+    StorageType m_value;
>+};
>+
> }
> 
> using WTF::OptionSet;
>diff --git a/Tools/ChangeLog b/Tools/ChangeLog
>index 181b39d291a0502dca6fe26b7903a597b908174d..ad28ec610280b24a9609da02d84053017d34dd5e 100644
>--- a/Tools/ChangeLog
>+++ b/Tools/ChangeLog
>@@ -1,5 +1,20 @@
> 2016-03-02  Daniel Bates  <dabates@apple.com>
> 
>+        Support iterating over an OptionSet and checking if it is empty
>+        https://bugs.webkit.org/show_bug.cgi?id=154941
>+
>+        Reviewed by NOBODY (OOPS!).
>+
>+        Add tests to ensure that we do not regression both iteration of an OptionSet and
>+        determining whether an OptionSet is empty.
>+
>+        * TestWebKitAPI/PlatformUtilities.h:
>+        (TestWebKitAPI::Util::assertStrongEnum): Helper function to assert two strong enum type for equality.
>+        * TestWebKitAPI/Tests/WTF/OptionSet.cpp:
>+        (TestWebKitAPI::TEST):
>+
>+2016-03-02  Daniel Bates  <dabates@apple.com>
>+
>         Add unit tests for WTF::OptionSet
>         https://bugs.webkit.org/show_bug.cgi?id=154925
> 
>diff --git a/Tools/TestWebKitAPI/PlatformUtilities.h b/Tools/TestWebKitAPI/PlatformUtilities.h
>index 7583e4ee077e3e883e6a57db5d1b89ec4794294b..cf696f61d40bde5fb51af0f983ae8babe52bb25e 100644
>--- a/Tools/TestWebKitAPI/PlatformUtilities.h
>+++ b/Tools/TestWebKitAPI/PlatformUtilities.h
>@@ -75,6 +75,18 @@ static inline ::testing::AssertionResult assertWKStringEqual(const char* expecte
> #define EXPECT_WK_STREQ(expected, actual) \
>     EXPECT_PRED_FORMAT2(TestWebKitAPI::Util::assertWKStringEqual, expected, actual)
> 
>+template<typename T>
>+static inline ::testing::AssertionResult assertStrongEnum(const char* expected_expression, const char* actual_expression, T expected, T actual)
>+{
>+    static_assert(std::is_enum<T>::value, "T is not an enum type");
>+    typedef typename std::underlying_type<T>::type UnderlyingStorageType;
>+    return ::testing::internal::CmpHelperEQ(expected_expression, actual_expression, static_cast<UnderlyingStorageType>(expected), static_cast<UnderlyingStorageType>(actual));
>+}
>+
>+#define EXPECT_STRONG_ENUM_EQ(expected, actual) \
>+    EXPECT_PRED_FORMAT2(TestWebKitAPI::Util::assertStrongEnum, expected, actual)
>+
>+
> #if WK_API_ENABLED
> extern NSString * const TestPlugInClassNameParameter;
> #endif
>diff --git a/Tools/TestWebKitAPI/Tests/WTF/OptionSet.cpp b/Tools/TestWebKitAPI/Tests/WTF/OptionSet.cpp
>index 209619c85482b72f6aba566cb85fca031ab39df1..cb8f83de4f942d4428ffc1da464aabb112fc0795 100644
>--- a/Tools/TestWebKitAPI/Tests/WTF/OptionSet.cpp
>+++ b/Tools/TestWebKitAPI/Tests/WTF/OptionSet.cpp
>@@ -24,6 +24,7 @@
>  */
> 
> #include "config.h"
>+#include "PlatformUtilities.h"
> 
> #include <wtf/OptionSet.h>
> 
>@@ -38,6 +39,7 @@ enum class ExampleFlags {
> TEST(WTF_OptionSet, EmptySet)
> {
>     OptionSet<ExampleFlags> set;
>+    EXPECT_TRUE(set.isEmpty());
>     EXPECT_FALSE(set.contains(ExampleFlags::A));
>     EXPECT_FALSE(set.contains(ExampleFlags::B));
>     EXPECT_FALSE(set.contains(ExampleFlags::C));
>@@ -46,6 +48,7 @@ TEST(WTF_OptionSet, EmptySet)
> TEST(WTF_OptionSet, ContainsOneFlag)
> {
>     OptionSet<ExampleFlags> set = ExampleFlags::A;
>+    EXPECT_FALSE(set.isEmpty());
>     EXPECT_TRUE(set.contains(ExampleFlags::A));
>     EXPECT_FALSE(set.contains(ExampleFlags::B));
>     EXPECT_FALSE(set.contains(ExampleFlags::C));
>@@ -54,6 +57,7 @@ TEST(WTF_OptionSet, ContainsOneFlag)
> TEST(WTF_OptionSet, ContainsTwoFlags)
> {
>     OptionSet<ExampleFlags> set { ExampleFlags::A, ExampleFlags::B };
>+    EXPECT_FALSE(set.isEmpty());
>     EXPECT_TRUE(set.contains(ExampleFlags::A));
>     EXPECT_TRUE(set.contains(ExampleFlags::B));
>     EXPECT_FALSE(set.contains(ExampleFlags::C));
>@@ -71,11 +75,13 @@ TEST(WTF_OptionSet, OperatorBitwiseOr)
> TEST(WTF_OptionSet, EmptyOptionSetToRawValueToOptionSet)
> {
>     OptionSet<ExampleFlags> set;
>+    EXPECT_TRUE(set.isEmpty());
>     EXPECT_FALSE(set.contains(ExampleFlags::A));
>     EXPECT_FALSE(set.contains(ExampleFlags::B));
>     EXPECT_FALSE(set.contains(ExampleFlags::C));
> 
>     auto set2 = OptionSet<ExampleFlags>::fromRaw(set.toRaw());
>+    EXPECT_TRUE(set2.isEmpty());
>     EXPECT_FALSE(set2.contains(ExampleFlags::A));
>     EXPECT_FALSE(set2.contains(ExampleFlags::B));
>     EXPECT_FALSE(set2.contains(ExampleFlags::C));
>@@ -84,11 +90,13 @@ TEST(WTF_OptionSet, EmptyOptionSetToRawValueToOptionSet)
> TEST(WTF_OptionSet, OptionSetThatContainsOneFlagToRawValueToOptionSet)
> {
>     OptionSet<ExampleFlags> set = ExampleFlags::A;
>+    EXPECT_FALSE(set.isEmpty());
>     EXPECT_TRUE(set.contains(ExampleFlags::A));
>     EXPECT_FALSE(set.contains(ExampleFlags::B));
>     EXPECT_FALSE(set.contains(ExampleFlags::C));
> 
>     auto set2 = OptionSet<ExampleFlags>::fromRaw(set.toRaw());
>+    EXPECT_FALSE(set2.isEmpty());
>     EXPECT_TRUE(set2.contains(ExampleFlags::A));
>     EXPECT_FALSE(set2.contains(ExampleFlags::B));
>     EXPECT_FALSE(set2.contains(ExampleFlags::C));
>@@ -97,14 +105,56 @@ TEST(WTF_OptionSet, OptionSetThatContainsOneFlagToRawValueToOptionSet)
> TEST(WTF_OptionSet, OptionSetThatContainsTwoFlagsToRawValueToOptionSet)
> {
>     OptionSet<ExampleFlags> set { ExampleFlags::A, ExampleFlags::C };
>+    EXPECT_FALSE(set.isEmpty());
>     EXPECT_TRUE(set.contains(ExampleFlags::A));
>     EXPECT_TRUE(set.contains(ExampleFlags::C));
>     EXPECT_FALSE(set.contains(ExampleFlags::B));
> 
>     auto set2 = OptionSet<ExampleFlags>::fromRaw(set.toRaw());
>+    EXPECT_FALSE(set2.isEmpty());
>     EXPECT_TRUE(set2.contains(ExampleFlags::A));
>     EXPECT_TRUE(set2.contains(ExampleFlags::C));
>     EXPECT_FALSE(set2.contains(ExampleFlags::B));
> }
> 
>+TEST(WTF_OptionSet, TwoIteratorsIntoSameOptionSet)
>+{
>+    OptionSet<ExampleFlags> set { ExampleFlags::C, ExampleFlags::B };
>+    OptionSet<ExampleFlags>::iterator it1 = set.begin();
>+    OptionSet<ExampleFlags>::iterator it2 = it1;
>+    ++it1;
>+    EXPECT_STRONG_ENUM_EQ(ExampleFlags::C, *it1);
>+    EXPECT_STRONG_ENUM_EQ(ExampleFlags::B, *it2);
>+}
>+
>+TEST(WTF_OptionSet, IterateOverOptionSetThatContainsTwoFlags)
>+{
>+    OptionSet<ExampleFlags> set { ExampleFlags::A, ExampleFlags::C };
>+    OptionSet<ExampleFlags>::iterator it = set.begin();
>+    OptionSet<ExampleFlags>::iterator end = set.end();
>+    EXPECT_TRUE(it != end);
>+    EXPECT_STRONG_ENUM_EQ(ExampleFlags::A, *it);
>+    ++it;
>+    EXPECT_STRONG_ENUM_EQ(ExampleFlags::C, *it);
>+    ++it;
>+    EXPECT_TRUE(it == end);
>+}
>+
>+TEST(WTF_OptionSet, IterationOrderTheSameRegardlessOfInsertionOrder)
>+{
>+    OptionSet<ExampleFlags> set1 = ExampleFlags::C;
>+    set1 |= ExampleFlags::A;
>+
>+    OptionSet<ExampleFlags> set2 = ExampleFlags::A;
>+    set2 |= ExampleFlags::C;
>+
>+    OptionSet<ExampleFlags>::iterator it1 = set1.begin();
>+    OptionSet<ExampleFlags>::iterator it2 = set2.begin();
>+
>+    EXPECT_TRUE(*it1 == *it2);
>+    ++it1;
>+    ++it2;
>+    EXPECT_TRUE(*it1 == *it2);
>+}
>+
> } // namespace TestWebKitAPI

Actions: View | Formatted Diff | Diff

Attachments on bug 154941: 272708 | 272710 | 272785 | 273266