Bug 204562 – Add DefaultHash<OptionSet<T>> and HashTrait<OptionSet<T>> specializations

• Status: RESOLVED
• Resolution: FIXED
• Component: Web Template Framework

[Fujii Hironori]

Add DefaultHash<OptionSet<T>> and HashTrait<OptionSet<T>> specializations

[Fujii Hironori]

Created attachment 384264 [details]
Patch

[Fujii Hironori]

Created attachment 384265 [details]
Patch

[Fujii Hironori]

Created attachment 384266 [details]
Patch

[Fujii Hironori]

Created attachment 384268 [details]
Patch

[Daniel Bates]

Comment on attachment 384268 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=384268&action=review

This patch looks good. It can be made a tiny bit better by moving all the templates to a separate file, say OptionSetHash.h, that includes <wtf/HashTraits.h> And <wtf/HashFunctions.h> because:

1. It keeps this file focused on the data structure.

2. A separate header just for the hash stuff can include <wtf/HashTraits.h> instead of relying on that already being included.

3. Because of (2), no need to forward declare HashTraits, GenericHashTraits, etc etc, which adds noise to the implementation.

4. Putting the hash stuff in a separate file will speed up the build a tiny bit compared to not doing it since a developer will only pay the parsing cost for the hash stuff if they #include it.

> Source/WTF/wtf/OptionSet.h:168
> +template<typename T> struct DefaultHash<OptionSet<T>> {

This is ok as-is. The optimal solution would be to have this be a specialized IntHash<OptionSet<T>> and then defining a specialized DefaultHash whose Hash = IntHash<OptionSet<T>> because:

1. An OptionSet<> is just an unsigned integer.
2. Because of (1) it seems like a specialization of IntHash.


> Source/WTF/wtf/OptionSet.h:170
> +        static unsigned hash(const OptionSet<T>& key)

This is ok as-is. It would be slightly better to take the argument by value because:

1. An OptionSet<> is a small value that fits in a register.
2. It avoids a deference.

> Source/WTF/wtf/OptionSet.h:173
> +            return DefaultHash<decltype(value)>::Hash::hash(value);

This is a ok as-is. The optimal solution is to implement this in terms of IntHash<typename OptionSet<T>::StorageType>.

> Source/WTF/wtf/OptionSet.h:176
> +        static bool equal(const OptionSet<T>& a, const OptionSet<T>& b)

This is ok as-is. It would be slightly better to take the arguments by value for the same reasons as above.

> Source/WTF/wtf/OptionSet.h:188
> +template<typename T> struct HashTraits<OptionSet<T>> : GenericHashTraits<OptionSet<T>> {

This is ok as-is. The optimal solution would be to have these traits be a specialized UnsignedWithZeroKeyHashTraits<OptionSet<T>> because:

1. An OptionSet<> is just an unsigned integer.
2. Defining under UnsignedWithZeroKeyHashTraits provides future expansion possibility for introducing an alternative, space-saving, HashTrait for OptionSet<> that treats the empty value as 0 (but doing so means you can never store OptionSet<T> {} in a hashed structure).

> Source/WTF/wtf/OptionSet.h:193
> +        return OptionSet<T>::fromRaw(std::numeric_limits<StorageType>::max());

This is ok as-is. The optimal solution is to implement this in terms of UnsignedWithZeroKeyHashTraits<typename OptionSet<T>::StorageType>.

> Source/WTF/wtf/OptionSet.h:198
> +        slot = OptionSet<T>::fromRaw(std::numeric_limits<StorageType>::max() - 1);

This is ok as-is. The optimal solution is to also implement this in terms of UnsignedWithZeroKeyHashTraits<typename OptionSet<T>::StorageType>.

> Source/WTF/wtf/OptionSet.h:203
> +        return value == OptionSet<T>::fromRaw(std::numeric_limits<StorageType>::max() - 1);

This is ok as-is. The optimal solution is to also implement this in terms of UnsignedWithZeroKeyHashTraits<typename OptionSet<T>::StorageType>.

[Daniel Bates]

Just to clarify, **everything** I wrote above is optional. The patch is okay to land as-is.

[Fujii Hironori]

Comment on attachment 384268 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=384268&action=review

>> Source/WTF/wtf/OptionSet.h:168
>> +template<typename T> struct DefaultHash<OptionSet<T>> {
> 
> This is ok as-is. The optimal solution would be to have this be a specialized IntHash<OptionSet<T>> and then defining a specialized DefaultHash whose Hash = IntHash<OptionSet<T>> because:
> 
> 1. An OptionSet<> is just an unsigned integer.
> 2. Because of (1) it seems like a specialization of IntHash.

In your proposed approach, I need to specialize both IntHash and DefaultHash. It seems just unnecessary to me. I can't believe it is better.

>> Source/WTF/wtf/OptionSet.h:170
>> +        static unsigned hash(const OptionSet<T>& key)
> 
> This is ok as-is. It would be slightly better to take the argument by value because:
> 
> 1. An OptionSet<> is a small value that fits in a register.
> 2. It avoids a deference.

Will fix.

>> Source/WTF/wtf/OptionSet.h:173
>> +            return DefaultHash<decltype(value)>::Hash::hash(value);
> 
> This is a ok as-is. The optimal solution is to implement this in terms of IntHash<typename OptionSet<T>::StorageType>.

Will fix.

>> Source/WTF/wtf/OptionSet.h:176
>> +        static bool equal(const OptionSet<T>& a, const OptionSet<T>& b)
> 
> This is ok as-is. It would be slightly better to take the arguments by value for the same reasons as above.

Will fix.

>> Source/WTF/wtf/OptionSet.h:188
>> +template<typename T> struct HashTraits<OptionSet<T>> : GenericHashTraits<OptionSet<T>> {
> 
> This is ok as-is. The optimal solution would be to have these traits be a specialized UnsignedWithZeroKeyHashTraits<OptionSet<T>> because:
> 
> 1. An OptionSet<> is just an unsigned integer.
> 2. Defining under UnsignedWithZeroKeyHashTraits provides future expansion possibility for introducing an alternative, space-saving, HashTrait for OptionSet<> that treats the empty value as 0 (but doing so means you can never store OptionSet<T> {} in a hashed structure).

In your proposed approach, I need to specialize both HashTraits and UnsignedWithZeroKeyHashTraits. It seems just unnecessary to me. I can't believe it is better.

>> Source/WTF/wtf/OptionSet.h:198
>> +        slot = OptionSet<T>::fromRaw(std::numeric_limits<StorageType>::max() - 1);
> 
> This is ok as-is. The optimal solution is to also implement this in terms of UnsignedWithZeroKeyHashTraits<typename OptionSet<T>::StorageType>.

Yeah, it'd be nice the implementation can be shared with UnsignedWithZeroKeyHashTraits.
However, constructDeletedValue can't be implemented by using UnsignedWithZeroKeyHashTraits::constructDeletedValue because OptionSet doesn't have a method to get StorageType& type.
Should I add a method just to do so?

> Tools/TestWebKitAPI/Tests/WTF/OptionSet.cpp:442
> +    HashSet<OptionSet<ExampleFlags>> hashSet;

I should add a test case of OptionSet<T> {}.

[Daniel Bates]

Comment on attachment 384268 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=384268&action=review

>>> Source/WTF/wtf/OptionSet.h:168
>>> +template<typename T> struct DefaultHash<OptionSet<T>> {
>> 
>> This is ok as-is. The optimal solution would be to have this be a specialized IntHash<OptionSet<T>> and then defining a specialized DefaultHash whose Hash = IntHash<OptionSet<T>> because:
>> 
>> 1. An OptionSet<> is just an unsigned integer.
>> 2. Because of (1) it seems like a specialization of IntHash.
> 
> In your proposed approach, I need to specialize both IntHash and DefaultHash. It seems just unnecessary to me. I can't believe it is better.

Well, that's my strong opinion. It's weakly held. So, you can do what you want.

>>> Source/WTF/wtf/OptionSet.h:188
>>> +template<typename T> struct HashTraits<OptionSet<T>> : GenericHashTraits<OptionSet<T>> {
>> 
>> This is ok as-is. The optimal solution would be to have these traits be a specialized UnsignedWithZeroKeyHashTraits<OptionSet<T>> because:
>> 
>> 1. An OptionSet<> is just an unsigned integer.
>> 2. Defining under UnsignedWithZeroKeyHashTraits provides future expansion possibility for introducing an alternative, space-saving, HashTrait for OptionSet<> that treats the empty value as 0 (but doing so means you can never store OptionSet<T> {} in a hashed structure).
> 
> In your proposed approach, I need to specialize both HashTraits and UnsignedWithZeroKeyHashTraits. It seems just unnecessary to me. I can't believe it is better.

Well, that's my strong opinion. It's weakly held. So, you can do what you want.

>>> Source/WTF/wtf/OptionSet.h:198
>>> +        slot = OptionSet<T>::fromRaw(std::numeric_limits<StorageType>::max() - 1);
>> 
>> This is ok as-is. The optimal solution is to also implement this in terms of UnsignedWithZeroKeyHashTraits<typename OptionSet<T>::StorageType>.
> 
> Yeah, it'd be nice the implementation can be shared with UnsignedWithZeroKeyHashTraits.
> However, constructDeletedValue can't be implemented by using UnsignedWithZeroKeyHashTraits::constructDeletedValue because OptionSet doesn't have a method to get StorageType& type.
> Should I add a method just to do so?

My strong opinion. weakly held is no, adding a lvalue reference getter is not needed. It is possible to implement it using UnsignedWithZero... here's two ways off the top of my head:

1. Use a local.
2. Friend this struct.

[Fujii Hironori]

Comment on attachment 384268 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=384268&action=review

>>>> Source/WTF/wtf/OptionSet.h:198
>>>> +        slot = OptionSet<T>::fromRaw(std::numeric_limits<StorageType>::max() - 1);
>>> 
>>> This is ok as-is. The optimal solution is to also implement this in terms of UnsignedWithZeroKeyHashTraits<typename OptionSet<T>::StorageType>.
>> 
>> Yeah, it'd be nice the implementation can be shared with UnsignedWithZeroKeyHashTraits.
>> However, constructDeletedValue can't be implemented by using UnsignedWithZeroKeyHashTraits::constructDeletedValue because OptionSet doesn't have a method to get StorageType& type.
>> Should I add a method just to do so?
> 
> My strong opinion. weakly held is no, adding a lvalue reference getter is not needed. It is possible to implement it using UnsignedWithZero... here's two ways off the top of my head:
> 
> 1. Use a local.
> 2. Friend this struct.

Oh, right. Will take #1.

[Fujii Hironori]

Created attachment 384283 [details]
Patch for landing

[Fujii Hironori]

Committed r252870: <https://trac.webkit.org/changeset/252870>

[Radar WebKit Bug Importer]

<rdar://problem/57480055>