Bug 109977 - Add HashMap::isGoodKey and HashSet::isGoodValue
Summary: Add HashMap::isGoodKey and HashSet::isGoodValue
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: New Bugs (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Anders Carlsson
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2013-02-15 15:26 PST by Anders Carlsson
Modified: 2013-02-15 17:02 PST (History)
5 users (show)

See Also:


Attachments
Patch (5.45 KB, patch)
2013-02-15 15:45 PST, Anders Carlsson
sam: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Anders Carlsson 2013-02-15 15:26:31 PST
Add HashMap::isGoodKey and HashSet::isGoodValue
Comment 1 Anders Carlsson 2013-02-15 15:45:08 PST
Created attachment 188655 [details]
Patch
Comment 2 Sam Weinig 2013-02-15 16:05:39 PST
Comment on attachment 188655 [details]
Patch

Nice, I should have done this awhile ago.  Do you think we should call it isValidKey().
Comment 3 Darin Adler 2013-02-15 16:09:09 PST
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.
Comment 4 Darin Adler 2013-02-15 16:12:14 PST
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.
Comment 5 Darin Adler 2013-02-15 16:12:38 PST
Those are all of my comments.
Comment 6 Benjamin Poulain 2013-02-15 16:16:04 PST
> > 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.
Comment 7 Anders Carlsson 2013-02-15 16:16:47 PST
(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.
Comment 8 Darin Adler 2013-02-15 16:19:45 PST
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.
Comment 9 Anders Carlsson 2013-02-15 16:26:26 PST
(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.
Comment 10 Darin Adler 2013-02-15 16:27:36 PST
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!!!
Comment 11 Anders Carlsson 2013-02-15 16:28:29 PST
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;
    }
Comment 12 Darin Adler 2013-02-15 16:30:12 PST
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.
Comment 13 Anders Carlsson 2013-02-15 17:02:39 PST
Committed r143071: <http://trac.webkit.org/changeset/143071>