Attachment 273266 Details for Bug 154941 – Patch and Unit Tests

[patch] Patch and Unit Tests

bug-154941-20160307211147.patch (text/plain), 12.67 KB, created by Daniel Bates on 2016-03-07 21:12:01 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Daniel Bates

Created: 2016-03-07 21:12:01 PST

Size: 12.67 KB

patch

obsolete

>Subversion Revision: 197723
>diff --git a/Source/WTF/ChangeLog b/Source/WTF/ChangeLog
>index 256d1bcd830209e43f548bd541303a61bcbb238d..ca2106c5fefd81376bd447d59977f0e02a4a2f7e 100644
>--- a/Source/WTF/ChangeLog
>+++ b/Source/WTF/ChangeLog
>@@ -1,3 +1,34 @@
>+2016-03-07  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
>+        <rdar://problem/24964187>
>+
>+        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-04  Alex Christensen  <achristensen@webkit.org>
> 
>         Remove vcxproj build system
>diff --git a/Source/WTF/wtf/OptionSet.h b/Source/WTF/wtf/OptionSet.h
>index 7c6a4b38d9f15011e030c1ccd2341e6e2ba69e5f..e2976ec06a6af0d0e95f4112192c9d39bf8439ba 100644
>--- a/Source/WTF/wtf/OptionSet.h
>+++ b/Source/WTF/wtf/OptionSet.h
>@@ -27,37 +27,62 @@
> #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() = default;
> 
>+#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)
>     {
>-        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 bool 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;
>@@ -71,9 +96,44 @@ public:
>     }
> 
> private:
>+    enum InitializationTag { FromRawValue };
>+    constexpr OptionSet(T t, InitializationTag)
>+        : m_storage(static_cast<StorageType>(t))
>+    {
>+    }
>     StorageType m_storage { 0 };
> };
> 
>+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 7084b26789ccf5b430b68a040680a8ea4edb6e43..b945ff23a951d47eaaa1dee4f3f08dfc6b4887b9 100644
>--- a/Tools/ChangeLog
>+++ b/Tools/ChangeLog
>@@ -1,3 +1,19 @@
>+2016-03-07  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
>+        <rdar://problem/24964187>
>+
>+        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/Test.h:
>+        (TestWebKitAPI::Util::assertStrongEnum): Helper function to assert two strong enum type for equality.
>+        * TestWebKitAPI/Tests/WTF/OptionSet.cpp:
>+        (TestWebKitAPI::TEST):
>+
> 2016-03-07  Jon Lee  <jonlee@apple.com>
> 
>         Update perf bot configuration for Animometer
>diff --git a/Tools/TestWebKitAPI/Test.h b/Tools/TestWebKitAPI/Test.h
>index ca43924a2f17f4e5d7123c6dd90fd66a5a3dabb1..cf44045fb0d0a3ea88b310bda3d00cb0dc169e76 100644
>--- a/Tools/TestWebKitAPI/Test.h
>+++ b/Tools/TestWebKitAPI/Test.h
>@@ -1,5 +1,5 @@
> /*
>- * Copyright (C) 2010 Apple Inc. All rights reserved.
>+ * Copyright (C) 2010, 2016 Apple Inc. All rights reserved.
>  *
>  * Redistribution and use in source and binary forms, with or without
>  * modification, are permitted provided that the following conditions
>@@ -26,6 +26,8 @@
> #ifndef Test_h
> #define Test_h
> 
>+#include <type_traits>
>+
> namespace TestWebKitAPI {
> 
> #define EXPECT_NOT_NULL(expression) \
>@@ -40,6 +42,18 @@ namespace TestWebKitAPI {
> #define ASSERT_NULL(expression) \
>     ASSERT_TRUE(!(expression))
> 
>+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::assertStrongEnum, expected, actual)
>+
>+
> } // namespace TestWebKitAPI
> 
> #endif // Test_h
>diff --git a/Tools/TestWebKitAPI/Tests/WTF/OptionSet.cpp b/Tools/TestWebKitAPI/Tests/WTF/OptionSet.cpp
>index 209619c85482b72f6aba566cb85fca031ab39df1..e8ab32991f14f93f14dc88622e337fbd5e3df40d 100644
>--- a/Tools/TestWebKitAPI/Tests/WTF/OptionSet.cpp
>+++ b/Tools/TestWebKitAPI/Tests/WTF/OptionSet.cpp
>@@ -25,6 +25,7 @@
> 
> #include "config.h"
> 
>+#include "Test.h"
> #include <wtf/OptionSet.h>
> 
> namespace TestWebKitAPI {
>@@ -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

Flags:

darin: review+

Actions: View | Formatted Diff | Diff

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