Replace uses of hash_map in //base

Replace uses of hash_map in //base

base::hash_map is deprecated in favor of std::unordered_map (which it is a
typedef of).

The changes to tracing required updating of callers in third_party/WebKit.

Some uses were replaced with more appropriate variants: std::map,
base::flat_map, and base::small_map.

A std::hash implementation of base::FilePath is added.

BUG=576864
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.android:android_optional_gpu_tests_rel;master.tryserver.chromium.linux:linux_optional_gpu_tests_rel;master.tryserver.chromium.mac:mac_optional_gpu_tests_rel;master.tryserver.chromium.win:win_optional_gpu_tests_rel

Review-Url: https://codereview.chromium.org/2830093003
Cr-Commit-Position: refs/heads/master@{#467761}
Committed: https://chromium.googlesource.com/chromium/src/+/1ce49f64ab5be7af3fa0a06d9bd1f826a13a0962

[brettw, 2017-04-21 17:01:54]

Description was changed from

==========
Replace uses of hash_map in //base

base::hash_map is deprecated in favor of std::unordered_map (which it is a
typedef of).

Some uses were replaced with more appropriate variants.
==========

to

==========
Replace uses of hash_map in //base

base::hash_map is deprecated in favor of std::unordered_map (which it is a
typedef of).

Some uses were replaced with more appropriate variants.

A std::hash implementation of base::FilePath is added.
==========

[brettw, 2017-04-21 17:22:18]

Description was changed from

==========
Replace uses of hash_map in //base

base::hash_map is deprecated in favor of std::unordered_map (which it is a
typedef of).

Some uses were replaced with more appropriate variants.

A std::hash implementation of base::FilePath is added.
==========

to

==========
Replace uses of hash_map in //base

base::hash_map is deprecated in favor of std::unordered_map (which it is a
typedef of).

The changes to tracing required updating of callers in third_party/WebKit.

Some uses were replaced with more appropriate variants.

A std::hash implementation of base::FilePath is added.
==========

[brettw, 2017-04-21 17:22:41]

Description was changed from

==========
Replace uses of hash_map in //base

base::hash_map is deprecated in favor of std::unordered_map (which it is a
typedef of).

The changes to tracing required updating of callers in third_party/WebKit.

Some uses were replaced with more appropriate variants.

A std::hash implementation of base::FilePath is added.
==========

to

==========
Replace uses of hash_map in //base

base::hash_map is deprecated in favor of std::unordered_map (which it is a
typedef of).

The changes to tracing required updating of callers in third_party/WebKit.

Some uses were replaced with more appropriate variants.

A std::hash implementation of base::FilePath is added.

BUG=576864
==========

[brettw, 2017-04-21 17:25:52]

brettw@chromium.org changed reviewers:
+ eae@chromium.org, lukasza@chromium.org

[brettw, 2017-04-21 17:25:53]

eae: owners for WebKit/platform. These changes should be no-ops since
base::hash_map is already a typedef for unordered_map

lukasza: everything else.

[brettw, 2017-04-21 17:25:57]

The CQ bit was checked by brettw@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-21 17:26:16]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-21 20:23:37]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-21 20:23:38]

Dry run: This issue passed the CQ dry run.

[Łukasz Anforowicz, 2017-04-21 22:01:09]

On 2017/04/21 17:25:53, brettw (plz ping after 24h) wrote:
> lukasza: everything else.

I am OOO today - I'll take a look on Monday (feel free to reassign if you'd
rather not wait).

[Primiano Tucci (use gerrit), 2017-04-21 22:03:41]

If it can help  base/Trace_event (and the memory stuff in blink, but I am not an
owner there) lgtm.

[eae, 2017-04-21 23:51:26]

LGTM for third_party/WebKit

[Łukasz Anforowicz, 2017-04-24 18:46:11]

This CL looks mostly good to me, but I had some questions and comments below. 
Thanks for pushing forward with the deprecation of base::hash_map.

When reviewing this CL, I was wondering whether I should try to audit all types
used as a key in base::small_map and base::flat_map (which now default to
std::hash rather than BASE_HASH_NAMESPACE::hash).  I think such audit is not
really necessary, because I see that there is a limited number of
BASE_HASH_NAMESPACE::hash specializations and this CL accounts for all of them,
so I think we are okay here.

https://codereview.chromium.org/2830093003/diff/20001/base/containers/small_m...
File base/containers/small_map.h (right):

https://codereview.chromium.org/2830093003/diff/20001/base/containers/small_m...
base/containers/small_map.h:553: int size_;  // negative = using map
nit: s/using map/using |map_| instead of |array_|./g ?

https://codereview.chromium.org/2830093003/diff/20001/base/files/file_path.h
File base/files/file_path.h (right):

https://codereview.chromium.org/2830093003/diff/20001/base/files/file_path.h#...
base/files/file_path.h:476: // TODO(brettw) remove this when base::hash_map is
removed.
I don't understand why we need to wait for removal of base::hash_map.

I see that the default BASE_HASH_NAMESPACE::hash<T> (defined in
base/containers/hash_tables.h) forwards to std::hash<base::FilePath> that you
are adding below.  Doesn't this mean that we can remove the
BASE_HASH_NAMESPACE::hash<base::FilePath> specialization today (i.e. without
waiting for removal of base::hash_map)?

PS. I guess I am fine with doing the removal in a separate CL, I am just trying
to understand what is going on in this CL :-)

PPS. If we could remove references to BASE_HASH_NAMESPACE in
base/files/file_path.h, then we could also (I think) remove #include of
base/containers/hash_tables.h (and it seems desirable to limit who
[transitively] includes this file).

https://codereview.chromium.org/2830093003/diff/20001/base/id_map.h
File base/id_map.h (right):

https://codereview.chromium.org/2830093003/diff/20001/base/id_map.h#newcode43
base/id_map.h:43: using HashTable = std::unordered_map<KeyType, V>;
The declaration on previous line (using |std::unordered_map|) seems in conflict
with the preceding comment (saying |unordered_map is not used|).  Did you mean
to say |std::map| in the comment?

Also - once the above is straightened out, it seems weird that we need to add an
#include for both <map> and <unordered_map>, when we only add a reference to
*one* of these types.


Actually, could you please help me understand the requirement for "stable
iterators"?  AFAICT base::IdMap won't mutate |data_| while there are still some
iterators out there, so I don't understand why HashTable = base::small_map
couldn't be used here.  (and if the explanation/example are small, then maybe
they can be put into a comment above for the benefit of future
readers/maintainers?)

https://codereview.chromium.org/2830093003/diff/20001/base/id_map.h#newcode244
base/id_map.h:244: base::flat_set<KeyType> removed_ids_;
nit: I wonder if you could please expand the CL description and spell out what
"more appropriate types are" - this would have helped me more quickly understand
the change above.  For example:

"""
Some uses were replaced with more appropriate variants (e.g. base::flat_map or
base::small_map rather than std::unordered_map).
"""

https://codereview.chromium.org/2830093003/diff/20001/base/id_map_unittest.cc
File base/id_map_unittest.cc (right):

https://codereview.chromium.org/2830093003/diff/20001/base/id_map_unittest.cc...
base/id_map_unittest.cc:109: // IDMap has no predictable iteration order.
Thanks for making the comment more generic - this is great.

nit: Do you think this comment should also be made part of the public contract
of the IDMap (e.g. by also adding an equivalent of this comment to the doc
comments of IdMap::Iterator class)?

https://codereview.chromium.org/2830093003/diff/20001/base/task/cancelable_ta...
File base/task/cancelable_task_tracker.cc (right):

https://codereview.chromium.org/2830093003/diff/20001/base/task/cancelable_ta...
base/task/cancelable_task_tracker.cc:152: for (const auto it : task_flags_)
nit:s/const auto/const auto&/ ?

https://codereview.chromium.org/2830093003/diff/20001/base/task/cancelable_ta...
File base/task/cancelable_task_tracker.h (right):

https://codereview.chromium.org/2830093003/diff/20001/base/task/cancelable_ta...
base/task/cancelable_task_tracker.h:149: base::small_map<std::map<TaskId,
CancellationFlag*>, 4> task_flags_;
optional nit: I notice that the declaration above uses an unnecessary |base::|
namespace qualifier - this is probably fine, but it is inconsistent with other
type references in this file (which omit the |base::| namespace qualifier when
referring to types like SequenceChecker).

https://codereview.chromium.org/2830093003/diff/20001/base/trace_event/heap_p...
File base/trace_event/heap_profiler_allocation_context.h (right):

https://codereview.chromium.org/2830093003/diff/20001/base/trace_event/heap_p...
base/trace_event/heap_profiler_allocation_context.h:130: }  // std
Right - I was wondering why we couldn't do something similar for
base/files/file_path.h (rather than retaining both the old BASE_HASH_NAMESPACE
definition and the new std definition).

https://codereview.chromium.org/2830093003/diff/20001/base/trace_event/malloc...
File base/trace_event/malloc_dump_provider.cc (right):

https://codereview.chromium.org/2830093003/diff/20001/base/trace_event/malloc...
base/trace_event/malloc_dump_provider.cc:299:
std::unordered_map<AllocationContext, AllocationMetrics> metrics_by_context;
IWYU: #include <unordered_map> ?  (I don't see such include here nor in
malloc_dump_provider.h)

https://codereview.chromium.org/2830093003/diff/20001/base/trace_event/trace_...
File base/trace_event/trace_event_memory_overhead.h (right):

https://codereview.chromium.org/2830093003/diff/20001/base/trace_event/trace_...
base/trace_event/trace_event_memory_overhead.h:64:
small_map<std::unordered_map<const char*, ObjectCountAndSize>, 16>;
IWYU: #include <unordered_map>?

https://codereview.chromium.org/2830093003/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/PartitionAllocMemoryDumpProvider.cpp
(right):

https://codereview.chromium.org/2830093003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/PartitionAllocMemoryDumpProvider.cpp:139:
std::unordered_map<base::trace_event::AllocationContext,
IWYU: #include <unordered_map>?

https://codereview.chromium.org/2830093003/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/platform/heap/BlinkGCMemoryDumpProvider.cpp
(right):

https://codereview.chromium.org/2830093003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/heap/BlinkGCMemoryDumpProvider.cpp:70:
std::unordered_map<base::trace_event::AllocationContext,
IWYU: #include <unordered_map>?

https://codereview.chromium.org/2830093003/diff/20001/third_party/WebKit/Sour...
File
third_party/WebKit/Source/platform/instrumentation/tracing/web_process_memory_dump.h
(right):

https://codereview.chromium.org/2830093003/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/platform/instrumentation/tracing/web_process_memory_dump.h:128:
const std::unordered_map<base::trace_event::AllocationContext,
IWYU: #include <unordered_map>?

[brettw, 2017-04-25 21:53:45]

Description was changed from

==========
Replace uses of hash_map in //base

base::hash_map is deprecated in favor of std::unordered_map (which it is a
typedef of).

The changes to tracing required updating of callers in third_party/WebKit.

Some uses were replaced with more appropriate variants.

A std::hash implementation of base::FilePath is added.

BUG=576864
==========

to

==========
Replace uses of hash_map in //base

base::hash_map is deprecated in favor of std::unordered_map (which it is a
typedef of).

The changes to tracing required updating of callers in third_party/WebKit.

Some uses were replaced with more appropriate variants: std::map,
base::flat_map, and base::small_map.

A std::hash implementation of base::FilePath is added.

BUG=576864
==========

[brettw, 2017-04-25 23:32:11]

Description was changed from

==========
Replace uses of hash_map in //base

base::hash_map is deprecated in favor of std::unordered_map (which it is a
typedef of).

The changes to tracing required updating of callers in third_party/WebKit.

Some uses were replaced with more appropriate variants: std::map,
base::flat_map, and base::small_map.

A std::hash implementation of base::FilePath is added.

BUG=576864
==========

to

==========
Replace uses of hash_map in //base

base::hash_map is deprecated in favor of std::unordered_map (which it is a
typedef of).

The changes to tracing required updating of callers in third_party/WebKit.

Some uses were replaced with more appropriate variants: std::map,
base::flat_map, and base::small_map.

A std::hash implementation of base::FilePath is added.

BUG=576864
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.android:android_optional_gpu_tests_rel;master.tryserver.chromium.linux:linux_optional_gpu_tests_rel;master.tryserver.chromium.mac:mac_optional_gpu_tests_rel;master.tryserver.chromium.win:win_optional_gpu_tests_rel
==========

[brettw, 2017-04-25 23:32:36]

New snap up with fixes, thanks.

https://codereview.chromium.org/2830093003/diff/20001/base/files/file_path.h
File base/files/file_path.h (right):

https://codereview.chromium.org/2830093003/diff/20001/base/files/file_path.h#...
base/files/file_path.h:476: // TODO(brettw) remove this when base::hash_map is
removed.
I missed the forwarding to std::hash. I'll remove.

Removing the include forced me to fix a smattering of random files across the
code base that were relying on this include for either base/hash.h and
base/containers/hash_tables.h

https://codereview.chromium.org/2830093003/diff/20001/base/id_map.h
File base/id_map.h (right):

https://codereview.chromium.org/2830093003/diff/20001/base/id_map.h#newcode43
base/id_map.h:43: using HashTable = std::unordered_map<KeyType, V>;
I misunderstood the implementation and stable iterators aren't required. I
removed the comment, thanks for noticing.

[brettw, 2017-04-25 23:32:43]

The CQ bit was checked by brettw@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-25 23:33:38]

Dry run: CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-25 23:38:12]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-25 23:38:12]

Dry run: Try jobs failed on following builders:
  android_compile_dbg on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/android_comp...)
  android_cronet on master.tryserver.chromium.android (JOB_FAILED,
https://build.chromium.org/p/tryserver.chromium.android/builders/android_cron...)
  ios-device on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-device/builds...)
  ios-device-xcode-clang on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-device-xcode-...)
  ios-simulator on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-simulator/bui...)
  ios-simulator-xcode-clang on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-simulator-xco...)
  mac_optional_gpu_tests_rel on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_optional_gpu_...)

[brettw, 2017-04-25 23:40:38]

Merge

[brettw, 2017-04-25 23:40:39]

The CQ bit was checked by brettw@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-25 23:41:30]

Dry run: CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[Łukasz Anforowicz, 2017-04-25 23:49:01]

lgtm - thanks!

https://codereview.chromium.org/2830093003/diff/20001/base/id_map.h
File base/id_map.h (right):

https://codereview.chromium.org/2830093003/diff/20001/base/id_map.h#newcode43
base/id_map.h:43: using HashTable = std::unordered_map<KeyType, V>;
On 2017/04/25 23:32:36, brettw (plz ping after 24h) wrote:
> I misunderstood the implementation and stable iterators aren't required. I
> removed the comment, thanks for noticing.

Thanks.  I see that the CL switches |removed_ids_| from being a |set::set| to
being a |base::flat_set|.  I wonder if a similar change (into
|base::small_map|?) might be beneficial also for |data_| (since a comment for
IDMap says that it is "optimized for relatively small data sets").

This is totally optional - I understand that it is probably safest to just
replace base::hash_map with std::unordered_map (the change should be a no-op
since base::hash_map is a typedef for std::unordered_map).  OTOH, if the CL
already modifies |removed_ids_|, then maybe it is also worth it to look into
modifying |data_|.

Hmmm.... thinking about it a bit more, I think we should just land the CL under
review as-is (and maybe consider what I wrote above in a separate CL).  Smaller
CLs = better (e.g. easier to attribute a perf regression [if any] to a smaller
CL).

[commit-bot: I haz the power, 2017-04-25 23:58:31]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-25 23:58:33]

Dry run: Try jobs failed on following builders:
  ios-device-xcode-clang on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-device-xcode-...)

[brettw, 2017-04-26 18:21:05]

Fixes

[brettw, 2017-04-26 18:21:06]

The CQ bit was checked by brettw@chromium.org

[brettw, 2017-04-26 18:21:07]

The patchset sent to the CQ was uploaded after l-g-t-m from
primiano@chromium.org, eae@chromium.org, lukasza@chromium.org
Link to the patchset: https://codereview.chromium.org/2830093003/#ps80001
(title: "Fixes")

[commit-bot: I haz the power, 2017-04-26 18:21:40]

CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-26 18:37:44]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-26 18:37:46]

Try jobs failed on following builders:
  ios-device-xcode-clang on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-device-xcode-...)

[brettw, 2017-04-26 19:38:48]

Some tests

[brettw, 2017-04-26 19:38:48]

The CQ bit was checked by brettw@chromium.org

[brettw, 2017-04-26 19:38:49]

The patchset sent to the CQ was uploaded after l-g-t-m from
primiano@chromium.org, lukasza@chromium.org, eae@chromium.org
Link to the patchset: https://codereview.chromium.org/2830093003/#ps100001
(title: "Some tests")

[commit-bot: I haz the power, 2017-04-26 19:39:31]

CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-26 20:04:06]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-26 20:04:07]

Try jobs failed on following builders:
  ios-simulator on master.tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-simulator/bui...)

[brettw, 2017-04-26 20:20:46]

iOS

[brettw, 2017-04-26 20:20:47]

The CQ bit was checked by brettw@chromium.org

[brettw, 2017-04-26 20:20:48]

The patchset sent to the CQ was uploaded after l-g-t-m from
primiano@chromium.org, lukasza@chromium.org, eae@chromium.org
Link to the patchset: https://codereview.chromium.org/2830093003/#ps120001
(title: "iOS")

[commit-bot: I haz the power, 2017-04-26 20:21:52]

CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[brettw, 2017-04-26 20:51:58]

https://codereview.chromium.org/2830093003/diff/20001/base/id_map.h
File base/id_map.h (right):

https://codereview.chromium.org/2830093003/diff/20001/base/id_map.h#newcode43
base/id_map.h:43: using HashTable = std::unordered_map<KeyType, V>;
IDMap is a template used in a bunch of places for things like IPC message
routing. I didn't want to mess with the performance of that, and I was also
concerned about code bloat from small_map. For the removed_ids, it's much easier
to understand the impact since it's used only for removals while iterating
through the map.

[commit-bot: I haz the power, 2017-04-26 23:30:41]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-26 23:30:43]

Try jobs failed on following builders:
  linux_chromium_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[brettw, 2017-04-27 16:52:00]

The CQ bit was checked by brettw@chromium.org

[commit-bot: I haz the power, 2017-04-27 16:52:44]

CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-27 19:42:35]

CQ is committing da patch.

Bot data: {"patchset_id": 120001, "attempt_start_ts": 1493311920644380,
"parent_rev": "27ff7475715673ebc736e4b198c3e90696d83022", "commit_rev":
"1ce49f64ab5be7af3fa0a06d9bd1f826a13a0962"}

[commit-bot: I haz the power, 2017-04-27 19:42:45]

Description was changed from

==========
Replace uses of hash_map in //base

base::hash_map is deprecated in favor of std::unordered_map (which it is a
typedef of).

The changes to tracing required updating of callers in third_party/WebKit.

Some uses were replaced with more appropriate variants: std::map,
base::flat_map, and base::small_map.

A std::hash implementation of base::FilePath is added.

BUG=576864
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.android:android_optional_gpu_tests_rel;master.tryserver.chromium.linux:linux_optional_gpu_tests_rel;master.tryserver.chromium.mac:mac_optional_gpu_tests_rel;master.tryserver.chromium.win:win_optional_gpu_tests_rel
==========

to

==========
Replace uses of hash_map in //base

base::hash_map is deprecated in favor of std::unordered_map (which it is a
typedef of).

The changes to tracing required updating of callers in third_party/WebKit.

Some uses were replaced with more appropriate variants: std::map,
base::flat_map, and base::small_map.

A std::hash implementation of base::FilePath is added.

BUG=576864
CQ_INCLUDE_TRYBOTS=master.tryserver.chromium.android:android_optional_gpu_tests_rel;master.tryserver.chromium.linux:linux_optional_gpu_tests_rel;master.tryserver.chromium.mac:mac_optional_gpu_tests_rel;master.tryserver.chromium.win:win_optional_gpu_tests_rel

Review-Url: https://codereview.chromium.org/2830093003
Cr-Commit-Position: refs/heads/master@{#467761}
Committed:
https://chromium.googlesource.com/chromium/src/+/1ce49f64ab5be7af3fa0a06d9bd1...
==========

[commit-bot: I haz the power, 2017-04-27 19:42:46]

Committed patchset #7 (id:120001) as
https://chromium.googlesource.com/chromium/src/+/1ce49f64ab5be7af3fa0a06d9bd1...