ES6: Add support for Map and Set Iterator

ES6: Add support for values/keys/entries for Map and Set

This allows code like this:

  var map = new Map();
  map.set(1, 'One');
  ...
  var iter = map.values();
  var res;
  while (!(res = iter.next()).done) {
    print(res.value);
  }

BUG=v8:1793
LOG=Y
R=mstarzinger@chromium.org

Committed: https://code.google.com/p/v8/source/detail?r=21615

[arv (Not doing code reviews), 2014-04-25 18:45:27]

cleanup

[arv (Not doing code reviews), 2014-05-06 20:49:41]

Toon, would you mind taking a look or suggest a better reviewer?

[arv (Not doing code reviews), 2014-05-07 18:45:11]

Changing back to Andreas since Toon is on/going on vacation.

[Michael Starzinger, 2014-05-07 19:15:23]

This creates iterators for Maps and Sets that are never closed. IIUC this
couples their lifetime to the lifetime of the Map/Set objects that they are
created for. This will cause OOMs in the general case. Is this a known issue
with this CL? If so, how do you plan to address this?

[rossberg, 2014-05-08 09:17:48]

I agree with Michael, that seems too simplistic an implementation. We need a
proper solution for memory management and rehashing. That requires the use of
weakness in some form or the other.

Michael and I have discussed this a couple of days ago. The current
implementation with a doubly-linked list of iterators will be very hard to make
weak correctly. We hence concluded that this is probably the wrong approach
moving forward. One alternative might be to have each map/set carry a weak set
of its iterators, and defer rehashing to points where that is empty. But perhaps
there are other solutions.

I'm also not sure iterators are worth introducing a separate flag, or a separate
file.

[arv (Not doing code reviews), 2014-05-08 13:11:50]

On 2014/05/08 09:17:48, rossberg wrote:
> I agree with Michael, that seems too simplistic an implementation. We need a
> proper solution for memory management and rehashing. That requires the use of
> weakness in some form or the other.
> 
> Michael and I have discussed this a couple of days ago. The current
> implementation with a doubly-linked list of iterators will be very hard to
make
> weak correctly. We hence concluded that this is probably the wrong approach
> moving forward. One alternative might be to have each map/set carry a weak set
> of its iterators, and defer rehashing to points where that is empty. But
perhaps
> there are other solutions.
> 
> I'm also not sure iterators are worth introducing a separate flag, or a
separate
> file.

It is true that this ties the lifetime of the iterator and the map together. It
is a known temporary restriction.

I know how to solve the memory management but I haven't yet been able to figure
out how to get that working in the V8 code base. I've talked this through with
Adam so he knows the basics of the solution too.

The idea is to have a single linked list. When GC happens we remove the
collected items from this list. Similar to how you currently do VisitWeakList
and WeakListVisitor. This means that the Map/Set does not keep the iterator
alive but the iterator keeps the Map/Set alive which is a requirement. I took
some rough notes when I looked at this last time:
https://docs.google.com/a/google.com/document/d/1-v25eMlmIJFdeAlYEziSV0VXI9QW...

This was done as a seperate file because iterators depends on Symbol which we
are not shipping and no other browser has implemented. Since everyone else is
shipping Map and Set I didn't want to gate Map and Set on Symbols.

[rossberg, 2014-05-08 13:38:04]

On 2014/05/08 13:11:50, arv wrote:
> The idea is to have a single linked list. When GC happens we remove the
> collected items from this list. Similar to how you currently do VisitWeakList
> and WeakListVisitor. This means that the Map/Set does not keep the iterator
> alive but the iterator keeps the Map/Set alive which is a requirement. I took
> some rough notes when I looked at this last time:
>
https://docs.google.com/a/google.com/document/d/1-v25eMlmIJFdeAlYEziSV0VXI9QW...

Off-hand this sounds plausible, although it looks like it would be duplicating
machinery that ObjectHashTable already provides. Also, if possible, it would be
great if we found a solution that would allow self-hosting the iterator
implementation.

> This was done as a seperate file because iterators depends on Symbol which we
> are not shipping and no other browser has implemented. Since everyone else is
> shipping Map and Set I didn't want to gate Map and Set on Symbols.

Symbols will be the next thing we stage, so I wouldn't worry about that. (Where
does it currently use symbols, btw?)

[Sven Panne, 2014-05-08 14:03:13]

I'm working on weak stuff this quarter, so I'd like to chime in... :-)

Adding yet another weak list would make the atomic pauses at the end of GC
longer, so we should try to avoid adding yet another list. What about the
following approach: Use a timestamp in the map, and remember that in the map. If
the timestamp hasn't changed, there's no need to do anything special in the
iterator. Otherwise one would have to get in sync again with the map, but this
will probably happen very rarely.

[rossberg, 2014-05-08 14:05:28]

On 2014/05/08 14:03:13, Sven Panne wrote:
> I'm working on weak stuff this quarter, so I'd like to chime in... :-)
> 
> Adding yet another weak list would make the atomic pauses at the end of GC
> longer, so we should try to avoid adding yet another list. What about the
> following approach: Use a timestamp in the map, and remember that in the map.
If
> the timestamp hasn't changed, there's no need to do anything special in the
> iterator. Otherwise one would have to get in sync again with the map, but this
> will probably happen very rarely.

Yeah, we discussed that, but the problem is that there is no obvious way to get
in sync again.

[arv (Not doing code reviews), 2014-05-08 16:26:57]

On 2014/05/08 13:38:04, rossberg wrote:

> Symbols will be the next thing we stage, so I wouldn't worry about that.
(Where
> does it currently use symbols, btw?)

Map.prototype[Symbol.iterator] should be there before we ship Map iterators.

[arv (Not doing code reviews), 2014-05-08 16:31:19]

On 2014/05/08 14:05:28, rossberg wrote:
> On 2014/05/08 14:03:13, Sven Panne wrote:
> > I'm working on weak stuff this quarter, so I'd like to chime in... :-)
> > 
> > Adding yet another weak list would make the atomic pauses at the end of GC
> > longer, so we should try to avoid adding yet another list. What about the
> > following approach: Use a timestamp in the map, and remember that in the
map.
> If
> > the timestamp hasn't changed, there's no need to do anything special in the
> > iterator. Otherwise one would have to get in sync again with the map, but
this
> > will probably happen very rarely.
> 
> Yeah, we discussed that, but the problem is that there is no obvious way to
get
> in sync again.

Yeah, I do not see how that would work.

Another option is to not allow compacting of the list while there are live
iterators. Then the map would only need to keep track of number of live
iterators. We would still need to have some kind of finalization though.

[arv (Not doing code reviews), 2014-05-08 16:37:16]

On 2014/05/08 13:38:04, rossberg wrote:

> Off-hand this sounds plausible, although it looks like it would be duplicating
> machinery that ObjectHashTable already provides. Also, if possible, it would
be
> great if we found a solution that would allow self-hosting the iterator
> implementation.

Just throwing this out there... After we implemented the Map and its iterator I
had an idea of an alternative approach.

Instead of implementing things in C++, we introduce a single runtime function,
%GetHashCode(Object). Then we use an InternalArray for the list and the table.
The logic would be identical.

This still does not solve the GC issues though but it would allow us to skip
writing Hydrogen code.

[rossberg, 2014-05-12 09:38:47]

We threw around a lot of different ideas for avoiding complicated
weakness schemes for maps and iterators (which our GC guys would not
like). Here is what I now think is the easiest solution: a variant of
difference arrays. That's a technique from functional language
compilers for implementing non-destructive persistent arrays with
constant-time read & update.

Adapted to the iterator scenario it would work as follows:

- Every iterator references (a version of) the backing store of the
map directly, instead of just the map object.
- Normally, add and remove operations just modify the backing store in
place, deletes are marked by tombstones (as now).
- When compacting, create a new backing store, copy over, update the
map to point to that (as now).
- At the same time, the old backing store is marked as deprecated, and
amended with (1) a pointer to the new backing store, and (2) an
appropriate description of the diff.
- On .next, iterators can check for the deprecation mark and easily
resync using the extra info.

Note how in this scheme, versions of the backing store are forward
linked, forming a change log (the chains can be longer than 1, of
course). No weakness is involved. If no iterator references the old
version of a backing store it becomes garbage immediately; otherwise
it does after all iterators have either resynced or become garbage
themselves.

[rossberg, 2014-05-12 09:51:08]

On 2014/05/12 09:38:47, rossberg wrote:
> We threw around a lot of different ideas for avoiding complicated
> weakness schemes for maps and iterators (which our GC guys would not
> like). Here is what I now think is the easiest solution: a variant of
> difference arrays. That's a technique from functional language
> compilers for implementing non-destructive persistent arrays with
> constant-time read & update.
> 
> Adapted to the iterator scenario it would work as follows:
> 
> - Every iterator references (a version of) the backing store of the
> map directly, instead of just the map object.
> - Normally, add and remove operations just modify the backing store in
> place, deletes are marked by tombstones (as now).
> - When compacting, create a new backing store, copy over, update the
> map to point to that (as now).
> - At the same time, the old backing store is marked as deprecated, and
> amended with (1) a pointer to the new backing store, and (2) an
> appropriate description of the diff.
> - On .next, iterators can check for the deprecation mark and easily
> resync using the extra info.
> 
> Note how in this scheme, versions of the backing store are forward
> linked, forming a change log (the chains can be longer than 1, of
> course). No weakness is involved. If no iterator references the old
> version of a backing store it becomes garbage immediately; otherwise
> it does after all iterators have either resynced or become garbage
> themselves.

(Real difference arrays of course avoid copying the array altogether. We could
do the same here, for the price of one more indirection. But as long as we don't
do in-place compaction anyway that's not a concern.)

[arv (Not doing code reviews), 2014-05-12 17:52:00]

On 2014/05/12 09:51:08, rossberg wrote:
> On 2014/05/12 09:38:47, rossberg wrote:
> > We threw around a lot of different ideas for avoiding complicated
> > weakness schemes for maps and iterators (which our GC guys would not
> > like). Here is what I now think is the easiest solution: a variant of
> > difference arrays. That's a technique from functional language
> > compilers for implementing non-destructive persistent arrays with
> > constant-time read & update.
> > 
> > Adapted to the iterator scenario it would work as follows:
> > 
> > - Every iterator references (a version of) the backing store of the
> > map directly, instead of just the map object.
> > - Normally, add and remove operations just modify the backing store in
> > place, deletes are marked by tombstones (as now).
> > - When compacting, create a new backing store, copy over, update the
> > map to point to that (as now).
> > - At the same time, the old backing store is marked as deprecated, and
> > amended with (1) a pointer to the new backing store, and (2) an
> > appropriate description of the diff.
> > - On .next, iterators can check for the deprecation mark and easily
> > resync using the extra info.
> > 
> > Note how in this scheme, versions of the backing store are forward
> > linked, forming a change log (the chains can be longer than 1, of
> > course). No weakness is involved. If no iterator references the old
> > version of a backing store it becomes garbage immediately; otherwise
> > it does after all iterators have either resynced or become garbage
> > themselves.
> 
> (Real difference arrays of course avoid copying the array altogether. We could
> do the same here, for the price of one more indirection. But as long as we
don't
> do in-place compaction anyway that's not a concern.)

Thanks Andreas. I started looking at this and since the iterator only needs to
keep track of the index the diff should be pretty simple. I'll post a new CL
with forEach only before revisiting this.

[arv (Not doing code reviews), 2014-05-21 02:17:25]

Update to support Symbol.iterator

[arv (Not doing code reviews), 2014-05-28 19:15:57]

Remove Symbol.iterator part

[arv (Not doing code reviews), 2014-05-28 19:21:36]

No need for harmony_symbol implication for now

[arv (Not doing code reviews), 2014-05-28 19:23:20]

This is now ready for review again.

The big difference from before is that the Create* functions have been removed
from C++ and the instance are created using `new MapIterator`. MapIterator is
only available to builtins.

PTAL

[adamk, 2014-05-29 00:07:13]

Mostly looks fine to me, happy to see some C++ code die. Only nits from me.

https://codereview.chromium.org/259883002/diff/120001/src/collection-iterator.js
File src/collection-iterator.js (right):

https://codereview.chromium.org/259883002/diff/120001/src/collection-iterator...
src/collection-iterator.js:1: // Copyright 2014 the V8 project authors. All
rights reserved.
Nit: I think you can use a short license header for this.

https://codereview.chromium.org/259883002/diff/120001/test/mjsunit/harmony/co...
File test/mjsunit/harmony/collection-iterator.js (right):

https://codereview.chromium.org/259883002/diff/120001/test/mjsunit/harmony/co...
test/mjsunit/harmony/collection-iterator.js:2: // Redistribution and use in
source and binary forms, with or without
Same nit, short license.

[arv (Not doing code reviews), 2014-05-29 17:21:35]

Short license header

[arv (Not doing code reviews), 2014-05-29 17:25:31]

PTAL

[arv (Not doing code reviews), 2014-05-29 21:00:29]

Add back @iterator part

[Michael Starzinger, 2014-06-02 11:53:36]

LGTM from my end. Just a couple of remarks.

https://codereview.chromium.org/259883002/diff/160001/src/bootstrapper.cc
File src/bootstrapper.cc (right):

https://codereview.chromium.org/259883002/diff/160001/src/bootstrapper.cc#new...
src/bootstrapper.cc:2020: INSTALL_EXPERIMENTAL_NATIVE(i, collections,
"collection-iterator.js")
Just out of curiosity, is there a particular reason for putting this into a
separate file? How would you feel about merging it into the existing
collection.js file?

https://codereview.chromium.org/259883002/diff/160001/src/runtime.cc
File src/runtime.cc (right):

https://codereview.chromium.org/259883002/diff/160001/src/runtime.cc#newcode1597
src/runtime.cc:1597: holder->set_index(Smi::FromInt(0));
Remark: This gives a short window of time during which "index" and "kind" are
initialized to undefined (which is totally fine). The JSSetIteratorVerify
assumes those two fields are always Smi. In the current implementation I don't
see how anything in between the allocation of an iterator and here could cause a
heap verification to be triggered.

I just wanted to leave this comment for posterity. Should there ever be a change
that causes a GC along the way from the constructor to here, then the
verification method needs to be loosened.

https://codereview.chromium.org/259883002/diff/160001/src/runtime.cc#newcode1701
src/runtime.cc:1701: holder->set_index(Smi::FromInt(0));
Likewise.

https://codereview.chromium.org/259883002/diff/160001/test/mjsunit/harmony/co...
File test/mjsunit/harmony/collection-iterator.js (right):

https://codereview.chromium.org/259883002/diff/160001/test/mjsunit/harmony/co...
test/mjsunit/harmony/collection-iterator.js:20: assertEquals(new
Set().values().__proto__. SetIteratorPrototype);
typo: there is a period instead of a comma after "__proto__" here. Gotta love
JavaScript for that. :/

https://codereview.chromium.org/259883002/diff/160001/test/mjsunit/harmony/co...
test/mjsunit/harmony/collection-iterator.js:115: assertEquals(new
Map().values().__proto__. MapIteratorPrototype);
typo: Likewise.

[rossberg, 2014-06-02 12:24:27]

https://codereview.chromium.org/259883002/diff/160001/test/mjsunit/harmony/co...
File test/mjsunit/harmony/collection-iterator.js (right):

https://codereview.chromium.org/259883002/diff/160001/test/mjsunit/harmony/co...
test/mjsunit/harmony/collection-iterator.js:20: assertEquals(new
Set().values().__proto__. SetIteratorPrototype);
On 2014/06/02 11:53:36, Michael Starzinger wrote:
> typo: there is a period instead of a comma after "__proto__" here. Gotta love
> JavaScript for that. :/

OMG. This language is so far beyond repair...

[arv (Not doing code reviews), 2014-06-02 23:35:01]

Code review changes

[arv (Not doing code reviews), 2014-06-02 23:40:52]

All fixed

https://codereview.chromium.org/259883002/diff/160001/src/bootstrapper.cc
File src/bootstrapper.cc (right):

https://codereview.chromium.org/259883002/diff/160001/src/bootstrapper.cc#new...
src/bootstrapper.cc:2020: INSTALL_EXPERIMENTAL_NATIVE(i, collections,
"collection-iterator.js")
On 2014/06/02 11:53:36, Michael Starzinger wrote:
> Just out of curiosity, is there a particular reason for putting this into a
> separate file? How would you feel about merging it into the existing
> collection.js file?

The initial reason was that I had them under a different flag.

I would actually prefer to split this into even more files. One for Map, Set,
WeakMap, WeakSet, MapIterator and SetIterator respectively.

https://codereview.chromium.org/259883002/diff/160001/src/runtime.cc
File src/runtime.cc (right):

https://codereview.chromium.org/259883002/diff/160001/src/runtime.cc#newcode1597
src/runtime.cc:1597: holder->set_index(Smi::FromInt(0));
On 2014/06/02 11:53:36, Michael Starzinger wrote:
> Remark: This gives a short window of time during which "index" and "kind" are
> initialized to undefined (which is totally fine). The JSSetIteratorVerify
> assumes those two fields are always Smi. In the current implementation I don't
> see how anything in between the allocation of an iterator and here could cause
a
> heap verification to be triggered.
> 
> I just wanted to leave this comment for posterity. Should there ever be a
change
> that causes a GC along the way from the constructor to here, then the
> verification method needs to be loosened.

I added  IsUndefined checks to the verifier.

https://codereview.chromium.org/259883002/diff/160001/src/runtime.cc#newcode1701
src/runtime.cc:1701: holder->set_index(Smi::FromInt(0));
On 2014/06/02 11:53:36, Michael Starzinger wrote:
> Likewise.

Done.

https://codereview.chromium.org/259883002/diff/160001/test/mjsunit/harmony/co...
File test/mjsunit/harmony/collection-iterator.js (right):

https://codereview.chromium.org/259883002/diff/160001/test/mjsunit/harmony/co...
test/mjsunit/harmony/collection-iterator.js:20: assertEquals(new
Set().values().__proto__. SetIteratorPrototype);
On 2014/06/02 12:24:27, rossberg wrote:
> On 2014/06/02 11:53:36, Michael Starzinger wrote:
> > typo: there is a period instead of a comma after "__proto__" here. Gotta
love
> > JavaScript for that. :/
> 
> OMG. This language is so far beyond repair...

Done.

https://codereview.chromium.org/259883002/diff/160001/test/mjsunit/harmony/co...
test/mjsunit/harmony/collection-iterator.js:115: assertEquals(new
Map().values().__proto__. MapIteratorPrototype);
On 2014/06/02 11:53:36, Michael Starzinger wrote:
> typo: Likewise.

Done.

[adamk, 2014-06-03 00:34:12]

Committed patchset #9 manually as r21615 (presubmit successful).