Implement Harmony sets and maps.

Implement Harmony sets and maps.

This implementation extends the internal ObjectHashTable to be able to
hold arbitrary objects (e.g. Smis, Strings, ...) as keys by applying
specialized hashing functions to primitive types. Equality of keys is
defined using the internal SameValue function.

R=rossberg@chromium.org
BUG=v8:1622
TEST=mjsunit/harmony/collections

Committed: http://code.google.com/p/v8/source/detail?r=9777

[Michael Starzinger, 2011-10-24 09:13:17]

PTAL.

[rossberg, 2011-10-24 15:44:10]

http://codereview.chromium.org/8372027/diff/1/src/collection.js
File src/collection.js (right):

http://codereview.chromium.org/8372027/diff/1/src/collection.js#newcode31
src/collection.js:31: // const $Object = global.Object;
Not needed?

http://codereview.chromium.org/8372027/diff/1/src/flag-definitions.h
File src/flag-definitions.h (right):

http://codereview.chromium.org/8372027/diff/1/src/flag-definitions.h#newcode103
src/flag-definitions.h:103: DEFINE_bool(harmony_collections, false,
I think you can remove the separate hormony_weakmaps flag and subsume it under
harmony_collections.

http://codereview.chromium.org/8372027/diff/1/src/objects.cc
File src/objects.cc (right):

http://codereview.chromium.org/8372027/diff/1/src/objects.cc#newcode754
src/objects.cc:754: return this_value == other_value;
Test the common case first. Also, you can condense these two lines to

return this == that || (isnan(this) && isnan(that));

http://codereview.chromium.org/8372027/diff/1/src/objects.cc#newcode12229
src/objects.cc:12229: if (key->IsJSReceiver()) {
For example, this conditional is redundant if GetHash created a hash. (Same in
Put.)

http://codereview.chromium.org/8372027/diff/1/src/objects.h
File src/objects.h (right):

http://codereview.chromium.org/8372027/diff/1/src/objects.h#newcode947
src/objects.h:947: uint32_t GetHash();
It is not very intuitive that this function fails on a JSReceiver that does not
have a hash yet. Is this ever useful behaviour? At the very least, you should
document it.

But I think it's preferable to always create it - and you could avoid a couple
of extra cases and repeated hash lookups in your code.

http://codereview.chromium.org/8372027/diff/1/src/runtime.cc
File src/runtime.cc (right):

http://codereview.chromium.org/8372027/diff/1/src/runtime.cc#newcode731
src/runtime.cc:731: enum SetAccessOperation {
I'm not sure I like this. The amount of code it safes is far too tiny to warrant
introducing a special construction like this.

http://codereview.chromium.org/8372027/diff/1/src/runtime.cc#newcode776
src/runtime.cc:776: CONVERT_ARG_CHECKED(JSReceiver, key, 1);
Why is the key still a JSReceiver here (and below)?

http://codereview.chromium.org/8372027/diff/1/test/mjsunit/harmony/collection...
File test/mjsunit/harmony/collections.js (right):

http://codereview.chromium.org/8372027/diff/1/test/mjsunit/harmony/collection...
test/mjsunit/harmony/collections.js:63: assertTrue(Map.prototype.delete
instanceof Function)
I don't see any proper test cases for maps (especially, I think you will still
fail on non-object keys, see runtime.cc).

http://codereview.chromium.org/8372027/diff/1/test/mjsunit/harmony/proxies-ha...
File test/mjsunit/harmony/proxies-hash.js (right):

http://codereview.chromium.org/8372027/diff/1/test/mjsunit/harmony/proxies-ha...
test/mjsunit/harmony/proxies-hash.js:90: assertSame(321, m.get(p2));
Now that you have the special code paths for non-existing hashs, can you add
tests for .has and .delete? (The latter also for sets.)

[Michael Starzinger, 2011-10-25 11:17:26]

Added new patch set. PTAL.

http://codereview.chromium.org/8372027/diff/1/src/collection.js
File src/collection.js (right):

http://codereview.chromium.org/8372027/diff/1/src/collection.js#newcode31
src/collection.js:31: // const $Object = global.Object;
On 2011/10/24 15:44:11, rossberg wrote:
> Not needed?

Done.

http://codereview.chromium.org/8372027/diff/1/src/flag-definitions.h
File src/flag-definitions.h (right):

http://codereview.chromium.org/8372027/diff/1/src/flag-definitions.h#newcode103
src/flag-definitions.h:103: DEFINE_bool(harmony_collections, false,
On 2011/10/24 15:44:11, rossberg wrote:
> I think you can remove the separate hormony_weakmaps flag and subsume it under
> harmony_collections.

Done. In this case it might be useful to move the WeakMap implementation from
the weakmap.js file into the collection.js file for consistency reasons.

http://codereview.chromium.org/8372027/diff/1/src/objects.cc
File src/objects.cc (right):

http://codereview.chromium.org/8372027/diff/1/src/objects.cc#newcode754
src/objects.cc:754: return this_value == other_value;
On 2011/10/24 15:44:11, rossberg wrote:
> Test the common case first. Also, you can condense these two lines to
> 
> return this == that || (isnan(this) && isnan(that));

Done.

http://codereview.chromium.org/8372027/diff/1/src/objects.cc#newcode12229
src/objects.cc:12229: if (key->IsJSReceiver()) {
On 2011/10/24 15:44:11, rossberg wrote:
> For example, this conditional is redundant if GetHash created a hash. (Same in
> Put.)

Done (see comment in objects.h).

http://codereview.chromium.org/8372027/diff/1/src/objects.h
File src/objects.h (right):

http://codereview.chromium.org/8372027/diff/1/src/objects.h#newcode947
src/objects.h:947: uint32_t GetHash();
On 2011/10/24 15:44:11, rossberg wrote:
> It is not very intuitive that this function fails on a JSReceiver that does
not
> have a hash yet. Is this ever useful behaviour? At the very least, you should
> document it.
> 
> But I think it's preferable to always create it - and you could avoid a couple
> of extra cases and repeated hash lookups in your code.

Done. As discussed extensively offline, the only feasible solution to prevent
special handling of JSReceiver at the caller site it to return MaybeObject. This
limits the space of available hash codes to 31 bit. Always creating it is not an
option because a GC might be caused when storing the hash as a hidden property.

http://codereview.chromium.org/8372027/diff/1/src/runtime.cc
File src/runtime.cc (right):

http://codereview.chromium.org/8372027/diff/1/src/runtime.cc#newcode731
src/runtime.cc:731: enum SetAccessOperation {
On 2011/10/24 15:44:11, rossberg wrote:
> I'm not sure I like this. The amount of code it safes is far too tiny to
warrant
> introducing a special construction like this.

Done.

http://codereview.chromium.org/8372027/diff/1/src/runtime.cc#newcode776
src/runtime.cc:776: CONVERT_ARG_CHECKED(JSReceiver, key, 1);
On 2011/10/24 15:44:11, rossberg wrote:
> Why is the key still a JSReceiver here (and below)?

Done (fixed by second patch set).

http://codereview.chromium.org/8372027/diff/1/test/mjsunit/harmony/collection...
File test/mjsunit/harmony/collections.js (right):

http://codereview.chromium.org/8372027/diff/1/test/mjsunit/harmony/collection...
test/mjsunit/harmony/collections.js:63: assertTrue(Map.prototype.delete
instanceof Function)
On 2011/10/24 15:44:11, rossberg wrote:
> I don't see any proper test cases for maps (especially, I think you will still
> fail on non-object keys, see runtime.cc).

Done.

http://codereview.chromium.org/8372027/diff/1/test/mjsunit/harmony/proxies-ha...
File test/mjsunit/harmony/proxies-hash.js (right):

http://codereview.chromium.org/8372027/diff/1/test/mjsunit/harmony/proxies-ha...
test/mjsunit/harmony/proxies-hash.js:90: assertSame(321, m.get(p2));
On 2011/10/24 15:44:11, rossberg wrote:
> Now that you have the special code paths for non-existing hashs, can you add
> tests for .has and .delete? (The latter also for sets.)

Done (I suppose you mean non-existing keys).

[rossberg, 2011-10-25 13:53:59]

lgtm

http://codereview.chromium.org/8372027/diff/3024/src/flag-definitions.h
File src/flag-definitions.h (right):

http://codereview.chromium.org/8372027/diff/3024/src/flag-definitions.h#newco...
src/flag-definitions.h:104: "enable harmony collections (sets, maps and weak
maps)")
Nit: I think you put a comma before the "and" in English.

[Erik Corry, 2011-10-25 19:36:00]

http://codereview.chromium.org/8372027/diff/3024/src/flag-definitions.h
File src/flag-definitions.h (right):

http://codereview.chromium.org/8372027/diff/3024/src/flag-definitions.h#newco...
src/flag-definitions.h:104: "enable harmony collections (sets, maps and weak
maps)")
On 2011/10/25 13:53:59, rossberg wrote:
> Nit: I think you put a comma before the "and" in English.

Some do, some don't.  http://en.wikipedia.org/wiki/Serial_comma

[arv (Not doing code reviews), 2011-10-26 17:09:44]

lgtm

Drive by.

This is awesome. I can't wait for this to hit Chromium.

Is there an open bug about enumeration? I guess that is pretty far off due to
its long tail of dependencies.

http://codereview.chromium.org/8372027/diff/3024/src/objects.h
File src/objects.h (right):

http://codereview.chromium.org/8372027/diff/3024/src/objects.h#newcode7022
src/objects.h:7022: // The JSSet describes EcmaScript Harmony maps
nit 

// The JSSet describes EcmaScript Harmony *sets*

http://codereview.chromium.org/8372027/diff/3024/test/mjsunit/harmony/collect...
File test/mjsunit/harmony/collections.js (right):

http://codereview.chromium.org/8372027/diff/3024/test/mjsunit/harmony/collect...
test/mjsunit/harmony/collections.js:72: for (i = 0; i < 20; i++) {
missing var

http://codereview.chromium.org/8372027/diff/3024/test/mjsunit/harmony/collect...
test/mjsunit/harmony/collections.js:102: var keys = [ +0, -0, +Infinity,
-Infinity, true, false ];
is it worth testing NaN, undefined and null too?

http://codereview.chromium.org/8372027/diff/3024/test/mjsunit/harmony/collect...
test/mjsunit/harmony/collections.js:187: for (i = 0; i < 20; i++) {
var

[Michael Starzinger, 2011-10-27 15:36:05]

Thanks for the drive-by!

http://codereview.chromium.org/8372027/diff/3024/src/objects.h
File src/objects.h (right):

http://codereview.chromium.org/8372027/diff/3024/src/objects.h#newcode7022
src/objects.h:7022: // The JSSet describes EcmaScript Harmony maps
On 2011/10/26 17:09:44, arv wrote:
> nit 
> 
> // The JSSet describes EcmaScript Harmony *sets*

Done (will include in next CL).

http://codereview.chromium.org/8372027/diff/3024/test/mjsunit/harmony/collect...
File test/mjsunit/harmony/collections.js (right):

http://codereview.chromium.org/8372027/diff/3024/test/mjsunit/harmony/collect...
test/mjsunit/harmony/collections.js:72: for (i = 0; i < 20; i++) {
On 2011/10/26 17:09:44, arv wrote:
> missing var

Done (will include in next CL).

http://codereview.chromium.org/8372027/diff/3024/test/mjsunit/harmony/collect...
test/mjsunit/harmony/collections.js:102: var keys = [ +0, -0, +Infinity,
-Infinity, true, false ];
On 2011/10/26 17:09:44, arv wrote:
> is it worth testing NaN, undefined and null too?

Currently "undefined" and "null" cannot be used as keys to Maps, I am working on
that. The test for correct "NaN" handling is further down at line 203.

http://codereview.chromium.org/8372027/diff/3024/test/mjsunit/harmony/collect...
test/mjsunit/harmony/collections.js:187: for (i = 0; i < 20; i++) {
On 2011/10/26 17:09:44, arv wrote:
> var

Done (will include in next CL).