Bug 109977 – Add HashMap::isGoodKey and HashSet::isGoodValue

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Anders Carlsson]

Add HashMap::isGoodKey and HashSet::isGoodValue

[Anders Carlsson]

Created attachment 188655 [details]
Patch

[Sam Weinig]

Comment on attachment 188655 [details]
Patch

Nice, I should have done this awhile ago.  Do you think we should call it isValidKey().

[Darin Adler]

Comment on attachment 188655 [details]
Patch

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

More comments to come, but since Sam just gave you review+ I rushed to get these comments in.

> Source/WTF/ChangeLog:14
> +        (HashMap):
> +        (WTF::::isGoodKey):
> +        (WTF):

Yuck, please delete or fix this.

> Source/WTF/ChangeLog:18
> +        (HashSet):
> +        (WTF):
> +        (WTF::::isGoodValue):

Yuck, please delete or fix this.

> Source/WTF/wtf/HashMap.h:419
>      template<typename T, typename U, typename V, typename W, typename X>
> +    inline bool HashMap<T, U, V, W, X>::isGoodKey(const KeyType& key)
> +    {
> +        return key != KeyTraits::emptyValue() && !KeyTraits::isDeletedValue(key);
> +    }

I believe this function is not safe for all types. Our hash tables support types where it is not safe to compare with empty using == or != and the traits identify such types. It’s tricky for a hash map user to know you can’t call this newly added function on all maps. I don’t know whether it will be a compile time failure or runtime failure. I’d prefer a brief comment about this just above the declaration.

> Source/WTF/wtf/HashSet.h:218
> +    template<typename T, typename U, typename V>
> +    bool HashSet<T, U, V>::isGoodValue(const ValueType& value)
> +    {
> +        return value != ValueTraits::emptyValue() && !ValueTraits::isDeletedValue(value);
> +    }

Did you intentionally choose not to inline this? I ask because you marked the HashMap version inline.

Also, same concerns as for the HashMap function.

> Source/WebKit2/UIProcess/WebProcessProxy.cpp:75
> -    static uint64_t uniquePageID = 1;
> -    return uniquePageID++;
> +    static uint64_t uniquePageID;
> +    return ++uniquePageID;

This tweak looks fine, but unrelated to the rest of the patch. You should at least mention it in the change log.

> Source/WebKit2/UIProcess/WebProcessProxy.cpp:458
> -    return isGoodKey<WebFrameProxyMap>(frameID) ? m_frameMap.get(frameID).get() : 0;
> +    if (!m_frameMap.isGoodKey(frameID))
> +        return 0;
> +
> +    return m_frameMap.get(frameID).get();

I think it would be slightly clearer to use the type of m_frameMap here instead of using m_frameMap itself to call the static member function.

Also, is it really that much better to use an if with a return?

> Source/WebKit2/UIProcess/WebProcessProxy.cpp:463
> +    return m_frameMap.isGoodKey(frameID) && !m_frameMap.contains(frameID);

Ditto.

> Source/WebKit2/UIProcess/WebProcessProxy.cpp:477
> +    ASSERT(m_frameMap.isGoodKey(frameID));

Ditto.

[Darin Adler]

Comment on attachment 188655 [details]
Patch

The function that does this same operation when it can safely, as an assertion, is HashTable::checkKey. These new functions will work on some maps and sets and not on others.

[Darin Adler]

Those are all of my comments.

[Benjamin Poulain]

> > Source/WTF/wtf/HashMap.h:419
> >      template<typename T, typename U, typename V, typename W, typename X>
> > +    inline bool HashMap<T, U, V, W, X>::isGoodKey(const KeyType& key)
> > +    {
> > +        return key != KeyTraits::emptyValue() && !KeyTraits::isDeletedValue(key);
> > +    }
> 
> I believe this function is not safe for all types. Our hash tables support types where it is not safe to compare with empty using == or != and the traits identify such types. It’s tricky for a hash map user to know you can’t call this newly added function on all maps. I don’t know whether it will be a compile time failure or runtime failure. I’d prefer a brief comment about this just above the declaration.

This!

I am not sure HashMap is the right place because of this.

[Anders Carlsson]

(In reply to comment #3)
> (From update of attachment 188655 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=188655&action=review
> 
> More comments to come, but since Sam just gave you review+ I rushed to get these comments in.
> 
> > Source/WTF/wtf/HashMap.h:419
> >      template<typename T, typename U, typename V, typename W, typename X>
> > +    inline bool HashMap<T, U, V, W, X>::isGoodKey(const KeyType& key)
> > +    {
> > +        return key != KeyTraits::emptyValue() && !KeyTraits::isDeletedValue(key);
> > +    }
> 
> I believe this function is not safe for all types. Our hash tables support types where it is not safe to compare with empty using == or != and the traits identify such types. It’s tricky for a hash map user to know you can’t call this newly added function on all maps. I don’t know whether it will be a compile time failure or runtime failure. I’d prefer a brief comment about this just above the declaration.

Good point. I can add a COMPILE_ASSERT that safeToCompareToEmptyOrDeleted is true.

> 
> > Source/WTF/wtf/HashSet.h:218
> > +    template<typename T, typename U, typename V>
> > +    bool HashSet<T, U, V>::isGoodValue(const ValueType& value)
> > +    {
> > +        return value != ValueTraits::emptyValue() && !ValueTraits::isDeletedValue(value);
> > +    }
> 
> Did you intentionally choose not to inline this? I ask because you marked the HashMap version inline.

Nope, that was just an oversight. 
> 
> Also, same concerns as for the HashMap function.
> 
> > Source/WebKit2/UIProcess/WebProcessProxy.cpp:75
> > -    static uint64_t uniquePageID = 1;
> > -    return uniquePageID++;
> > +    static uint64_t uniquePageID;
> > +    return ++uniquePageID;
> 
> This tweak looks fine, but unrelated to the rest of the patch. You should at least mention it in the change log.
> 
> > Source/WebKit2/UIProcess/WebProcessProxy.cpp:458
> > -    return isGoodKey<WebFrameProxyMap>(frameID) ? m_frameMap.get(frameID).get() : 0;
> > +    if (!m_frameMap.isGoodKey(frameID))
> > +        return 0;
> > +
> > +    return m_frameMap.get(frameID).get();
> 
> I think it would be slightly clearer to use the type of m_frameMap here instead of using m_frameMap itself to call the static member function.

I thought it was clever, but I’ll change it since we have a typedef.

> 
> Also, is it really that much better to use an if with a return?

I think that it’s easier to read; just my personal opinion though.

[Darin Adler]

Comment on attachment 188655 [details]
Patch

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

>>> Source/WTF/wtf/HashMap.h:419
>>> +    }
>> 
>> I believe this function is not safe for all types. Our hash tables support types where it is not safe to compare with empty using == or != and the traits identify such types. It’s tricky for a hash map user to know you can’t call this newly added function on all maps. I don’t know whether it will be a compile time failure or runtime failure. I’d prefer a brief comment about this just above the declaration.
> 
> Good point. I can add a COMPILE_ASSERT that safeToCompareToEmptyOrDeleted is true.

Even when safe I am not 100% sure that you can just call isDeletedValue without involving the translator. I guess that extra complexity is only needed inside the HashTable class, not here in the HashMap and HashSet classes; translators are used to implement HashMap and the special translated add functions but probably not an issue here.

[Anders Carlsson]

(In reply to comment #8)
> (From update of attachment 188655 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=188655&action=review
> 
> >>> Source/WTF/wtf/HashMap.h:419
> >>> +    }
> >> 
> >> I believe this function is not safe for all types. Our hash tables support types where it is not safe to compare with empty using == or != and the traits identify such types. It’s tricky for a hash map user to know you can’t call this newly added function on all maps. I don’t know whether it will be a compile time failure or runtime failure. I’d prefer a brief comment about this just above the declaration.
> > 
> > Good point. I can add a COMPILE_ASSERT that safeToCompareToEmptyOrDeleted is true.
> 
> Even when safe I am not 100% sure that you can just call isDeletedValue without involving the translator. I guess that extra complexity is only needed inside the HashTable class, not here in the HashMap and HashSet classes; translators are used to implement HashMap and the special translated add functions but probably not an issue here.

Right, I don’t think it’s an issue. I also though about something like:

    template<typename T, typename U, typename V, typename W, typename X>
    inline bool HashMap<T, U, V, W, X>::isValidKey(const KeyType& key)
    {
        if (KeyTraits::isDeletedValue(key))
            return false;

        if (HashFunctions::safeToCompareToEmptyOrDeleted) {
            if (key == KeyTraits::emptyValue())
                return false;
            if (isHashTraitsEmptyValue<KeyTraits>(key))
                return false;
        }

        return true;
    }

but I’m not sure if it’s better.

[Darin Adler]

Comment on attachment 188655 [details]
Patch

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

>>>>> Source/WTF/wtf/HashMap.h:419
>>>>> +    }
>>>> 
>>>> I believe this function is not safe for all types. Our hash tables support types where it is not safe to compare with empty using == or != and the traits identify such types. It’s tricky for a hash map user to know you can’t call this newly added function on all maps. I don’t know whether it will be a compile time failure or runtime failure. I’d prefer a brief comment about this just above the declaration.
>>> 
>>> Good point. I can add a COMPILE_ASSERT that safeToCompareToEmptyOrDeleted is true.
>> 
>> Even when safe I am not 100% sure that you can just call isDeletedValue without involving the translator. I guess that extra complexity is only needed inside the HashTable class, not here in the HashMap and HashSet classes; translators are used to implement HashMap and the special translated add functions but probably not an issue here.
> 
> Right, I don’t think it’s an issue. I also though about something like:
> 
>     template<typename T, typename U, typename V, typename W, typename X>
>     inline bool HashMap<T, U, V, W, X>::isValidKey(const KeyType& key)
>     {
>         if (KeyTraits::isDeletedValue(key))
>             return false;
> 
>         if (HashFunctions::safeToCompareToEmptyOrDeleted) {
>             if (key == KeyTraits::emptyValue())
>                 return false;
>             if (isHashTraitsEmptyValue<KeyTraits>(key))
>                 return false;
>         }
> 
>         return true;
>     }
> 
> but I’m not sure if it’s better.

It’s definitely not better. A function that lies to you and returns true when it doesn’t know!!!

[Anders Carlsson]

Err, I meant

    template<typename T, typename U, typename V, typename W, typename X>
    inline bool HashMap<T, U, V, W, X>::isValidKey(const KeyType& key)
    {
        if (KeyTraits::isDeletedValue(key))
            return false;

        if (HashFunctions::safeToCompareToEmptyOrDeleted) {
            if (key == KeyTraits::emptyValue())
                return false;
        } else {
            if (isHashTraitsEmptyValue<KeyTraits>(key))
                return false;
        }

        return true;
    }

[Darin Adler]

Something like that is OK if it would actually make this function work for more key types. I’m not sure it would, though. It’s hard to think these things through in the abstract.

[Anders Carlsson]

Committed r143071: <http://trac.webkit.org/changeset/143071>