Bug 109977

Summary: Add HashMap::isGoodKey and HashSet::isGoodValue
Product: WebKit Reporter: Anders Carlsson <andersca>
Component: New BugsAssignee: Anders Carlsson <andersca>
Status: RESOLVED FIXED    
Severity: Normal CC: benjamin, cmarcelo, darin, ojan.autocc, webkit.review.bot
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
Patch sam: review+

Anders Carlsson
Reported 2013-02-15 15:26:31 PST
Add HashMap::isGoodKey and HashSet::isGoodValue
Attachments
Patch (5.45 KB, patch)
2013-02-15 15:45 PST, Anders Carlsson
sam: review+
Anders Carlsson
Comment 1 2013-02-15 15:45:08 PST
Sam Weinig
Comment 2 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().
Darin Adler
Comment 3 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.
Darin Adler
Comment 4 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.
Darin Adler
Comment 5 2013-02-15 16:12:38 PST
Those are all of my comments.
Benjamin Poulain
Comment 6 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.
Anders Carlsson
Comment 7 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.
Darin Adler
Comment 8 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.
Anders Carlsson
Comment 9 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.
Darin Adler
Comment 10 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!!!
Anders Carlsson
Comment 11 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; }
Darin Adler
Comment 12 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.
Anders Carlsson
Comment 13 2013-02-15 17:02:39 PST
Note You need to log in before you can comment on or make changes to this bug.