Bug 84524 - Iterating a HashMap<String, X> involves a string equality comparison to check for the empty value
Summary: Iterating a HashMap<String, X> involves a string equality comparison to check...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Template Framework (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Darin Adler
URL:
Keywords:
Depends on: 84615
Blocks:
  Show dependency treegraph
 
Reported: 2012-04-21 01:44 PDT by Darin Adler
Modified: 2012-04-25 18:12 PDT (History)
7 users (show)

See Also:


Attachments
Patch (9.94 KB, patch)
2012-04-21 01:49 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch with attempt to fix Chromium build (11.04 KB, patch)
2012-04-21 09:48 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch (11.08 KB, patch)
2012-04-21 10:03 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch with another cut at fixing Chromium build (10.51 KB, patch)
2012-04-21 12:36 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch (8.04 KB, patch)
2012-04-21 15:15 PDT, Darin Adler
no flags Details | Formatted Diff | Diff
Patch (2.25 KB, patch)
2012-04-24 21:46 PDT, Darin Adler
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Darin Adler 2012-04-21 01:44:43 PDT
Iterating a HashMap<String, X> involves a string equality comparison to check for the empty value
Comment 1 Darin Adler 2012-04-21 01:49:29 PDT
Created attachment 138226 [details]
Patch
Comment 2 WebKit Review Bot 2012-04-21 01:52:05 PDT
Attachment 138226 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WTF/ChangeLog', u'Source/WTF/wtf/Ha..." exit_code: 1
Source/WTF/wtf/text/StringHash.h:34:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Total errors found: 1 in 7 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 3 Darin Adler 2012-04-21 02:23:46 PDT
Comment on attachment 138226 [details]
Patch

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

> Source/WTF/wtf/HashTraits.h:163
> +    template<typename T, typename U, typename V, typename W> inline bool isEqualToEmptyValue(const pair<T, U>& value, const pair<V, W>& emptyValue) { return value.first == emptyValue.first && value.second == emptyValue.second; }

I should probably change this to call isEqualToEmptyValue twice instead of directly using == twice.
Comment 4 Darin Adler 2012-04-21 02:24:58 PDT
Comment on attachment 138226 [details]
Patch

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

>> Source/WTF/wtf/text/StringHash.h:34
>> +    template<> struct HashTraits<String> : SimpleClassHashTraits<String> {
> 
> Code inside a namespace should not be indented.  [whitespace/indent] [4]

I wonder if we should teach the style bot that we don’t want to reindent existing files.
Comment 5 WebKit Review Bot 2012-04-21 02:31:44 PDT
Comment on attachment 138226 [details]
Patch

Attachment 138226 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/12489008
Comment 6 Darin Adler 2012-04-21 09:48:55 PDT
Created attachment 138240 [details]
Patch with attempt to fix Chromium build
Comment 7 WebKit Review Bot 2012-04-21 09:53:32 PDT
Attachment 138240 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WTF/ChangeLog', u'Source/WTF/wtf/Ha..." exit_code: 1
Source/WTF/wtf/text/StringHash.h:34:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Total errors found: 1 in 9 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 8 Darin Adler 2012-04-21 10:03:29 PDT
Created attachment 138241 [details]
Patch
Comment 9 WebKit Review Bot 2012-04-21 10:07:32 PDT
Attachment 138241 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WTF/ChangeLog', u'Source/WTF/wtf/Ha..." exit_code: 1
Source/WTF/wtf/text/StringHash.h:34:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Total errors found: 1 in 9 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 10 WebKit Review Bot 2012-04-21 10:57:14 PDT
Comment on attachment 138241 [details]
Patch

Attachment 138241 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/12465528
Comment 11 Darin Adler 2012-04-21 12:36:01 PDT
Created attachment 138254 [details]
Patch with another cut at fixing Chromium build
Comment 12 WebKit Review Bot 2012-04-21 12:39:42 PDT
Attachment 138254 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WTF/ChangeLog', u'Source/WTF/wtf/Ha..." exit_code: 1
Source/WTF/wtf/text/StringHash.h:34:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Total errors found: 1 in 8 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 13 Darin Adler 2012-04-21 13:07:31 PDT
Comment on attachment 138254 [details]
Patch with another cut at fixing Chromium build

Chromium’s use of maps with string keys is so different from the other platforms that I’m going to take a different approach. Not great, but not a big deal either.
Comment 14 WebKit Review Bot 2012-04-21 13:29:30 PDT
Comment on attachment 138254 [details]
Patch with another cut at fixing Chromium build

Attachment 138254 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/12481488
Comment 15 Darin Adler 2012-04-21 15:15:04 PDT
Created attachment 138257 [details]
Patch
Comment 16 WebKit Review Bot 2012-04-21 15:17:27 PDT
Attachment 138257 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WTF/ChangeLog', u'Source/WTF/wtf/Ha..." exit_code: 1
Source/WTF/wtf/text/StringHash.h:31:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Total errors found: 1 in 4 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 17 Darin Adler 2012-04-23 10:26:29 PDT
Committed r114914: <http://trac.webkit.org/changeset/114914>
Comment 18 Eric Seidel (no email) 2012-04-23 10:35:23 PDT
This patch seems to have hung cr-ews #1 in the unittests.  bug 84611.
Comment 19 Eric Seidel (no email) 2012-04-23 10:42:36 PDT
The cr-linux-3 bot was also hung processing this patch.  It's possible it was a cooincidence, or it's possible this patch made the c++ unittests hang.
Comment 20 James Robinson 2012-04-23 11:31:40 PDT
I'm getting an infinite hang locally as well under HashMap::add().  There are a few maps that are producing the hang, here's one that I've caught in GDB:

    typedef std::pair<int, int> TileMapKey;
    struct TileMapKeyTraits : HashTraits<TileMapKey> {
        static const bool emptyValueIsZero = false;
        static const bool needsDestruction = false;
        static TileMapKey emptyValue() { return std::make_pair(-1, -1); }
        static void constructDeletedValue(TileMapKey& slot) { slot = std::make_pair(-2, -2); }
        static bool isDeletedValue(TileMapKey value) { return value.first == -2 && value.second == -2; }
    };
    typedef HashMap<TileMapKey, OwnPtr<Tile>, DefaultHash<TileMapKey>::Hash, TileMapKeyTraits> TileMap;


and the key being used is an std::pair (0, 0)
Comment 21 Antti Koivisto 2012-04-23 12:17:17 PDT
This apparently got rolled out in http://trac.webkit.org/changeset/114923
Comment 22 Eric Seidel (no email) 2012-04-23 12:29:54 PDT
Sorry, I think I rebooted the sheriff-bot mid-rollout, which may have caused failures to update bugs like this one. :(  (The sheriff runs on the same hardware as cr-linux-03, which I was rebooting to recover after unittest hangs from this patch.)
Comment 23 Antti Koivisto 2012-04-23 12:41:29 PDT
I think that the problem is specifically with TileMapKeyTraits here. It should either explicitly unset hasEmptyValueFunction or implement isEmptyValue().
Comment 24 Darin Adler 2012-04-23 14:54:54 PDT
Not sure why I did not see those hangs locally in my initial testing. I’ll try again and come back with a new version.
Comment 25 Darin Adler 2012-04-23 15:15:16 PDT
(In reply to comment #23)
> I think that the problem is specifically with TileMapKeyTraits here. It should either explicitly unset hasEmptyValueFunction or implement isEmptyValue().

I didn’t realize anyone had specialized pair traits. I see now that I caused the problem by making pair traits return true for hasEmptyValueFunction.
Comment 26 Darin Adler 2012-04-23 15:15:38 PDT
A good way to re-land this is to just leave pair traits alone and deal with that in a separate patch.
Comment 27 Darin Adler 2012-04-23 15:16:15 PDT
(In reply to comment #20)
> There are a few maps that are producing the hang

Any maps that don’t use TileMapKeyTraits?
Comment 28 James Robinson 2012-04-23 15:29:40 PDT
(In reply to comment #27)
> (In reply to comment #20)
> > There are a few maps that are producing the hang
> 
> Any maps that don’t use TileMapKeyTraits?

I think it's possible that all of the hangs were with TileMapKeyTraits - there were several tests, but without attaching GDB it's hard to tell which map they were hanging on.  I think that all of the tests did instantiate one map of this type.
Comment 29 Darin Adler 2012-04-23 15:34:58 PDT
I don’t have time or a computer set up for development right now, but if someone wants to test and re-land a version of this that leaves out the patch to PairHashTraits, that should work fine.
Comment 30 Darin Adler 2012-04-24 10:09:35 PDT
Committed r115078: <http://trac.webkit.org/changeset/115078>
Comment 31 Darin Adler 2012-04-24 12:31:37 PDT
Reopening this bug because the fix that I landed solves the problem for HashSet<String> but does not solve the problem for HashMap<String, X> yet.
Comment 32 Darin Adler 2012-04-24 21:46:46 PDT
Created attachment 138736 [details]
Patch
Comment 33 WebKit Review Bot 2012-04-24 21:50:11 PDT
Attachment 138736 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WTF/ChangeLog', u'Source/WTF/wtf/Ha..." exit_code: 1
Source/WTF/wtf/HashMap.h:28:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
Total errors found: 1 in 2 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 34 Antti Koivisto 2012-04-25 01:17:10 PDT
Comment on attachment 138736 [details]
Patch

r=me
Comment 35 WebKit Review Bot 2012-04-25 18:12:21 PDT
Comment on attachment 138736 [details]
Patch

Clearing flags on attachment: 138736

Committed r115272: <http://trac.webkit.org/changeset/115272>
Comment 36 WebKit Review Bot 2012-04-25 18:12:27 PDT
All reviewed patches have been landed.  Closing bug.