Last Comment Bug 725909 - Make Maps and Sets iterable
: Make Maps and Sets iterable
Status: RESOLVED FIXED
[DocArea=JS]
: dev-doc-complete
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Other Branch
: All All
: -- normal with 1 vote (vote)
: mozilla17
Assigned To: Jason Orendorff [:jorendorff]
:
Mentors:
: 735950 (view as bug list)
Depends on: 725907 743107 779025 788364
Blocks: es6 775781 738911
  Show dependency treegraph
 
Reported: 2012-02-09 18:06 PST by Jason Orendorff [:jorendorff]
Modified: 2014-11-30 08:42 PST (History)
17 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
SetIteratorObject, v1 (34.98 KB, patch)
2012-02-14 12:58 PST, Jason Orendorff [:jorendorff]
no flags Details | Diff | Review
WIP 1 (23.95 KB, patch)
2012-06-18 07:36 PDT, Jason Orendorff [:jorendorff]
no flags Details | Diff | Review
v2 (51.38 KB, patch)
2012-06-18 16:35 PDT, Jason Orendorff [:jorendorff]
luke: review+
Details | Diff | Review

Description Jason Orendorff [:jorendorff] 2012-02-09 18:06:44 PST
var m = new Map;
m.set("x", 1);
m.set("y", 2);
[x for (x of m)]  // should produce [["x", 1], ["y", 2]], currently a TypeError

var s = new Set;
s.add(42);
[x for (x of s)]  // should produce [42], currently a TypeError
Comment 1 Jason Orendorff [:jorendorff] 2012-02-14 12:58:51 PST
Created attachment 597146 [details] [diff] [review]
SetIteratorObject, v1

This is the ugliest patch I have written this year.

I will be disappointed if this doesn't get an r-, but I need some help with this.

There is an alternative design where we just keep a version number alongside the Set (this is not the same thing as the generation() number), but overflow is possible. The workaround for overflow is to detect it and force GC, and each GC cycle first invalidate all Set iterators with old versions, then set all Sets' version numbers to 0. It seems kind of crazy, but maybe less crazy than this.

Here are the tradeoffs:

- Insn overhead on each mutation of the set
  this design: +1 read and a branch, hopefully well-predicted (never taken)
  alt. design: +1 read and write (increment version number)
- Insn overhead on each setiter.next() call
  this design: no overhead
  alt. design: +1 read from the Iterator and well-predicted branch
- Space cost
  this design: +1 slot per Set, +2 slots per SetIterator
  alt. design: +1 int per Set, +1 int per SetIterator
- Code complexity
  this design: insane, casts and weak pointers all over the place
  alt. design: absurd, GC has to build and walk a linked list of Sets

Another possibility is to keep a 53- or 64-bit overflow and just assume it'll never roll over. I regret not considering that more seriously before writing all this.
Comment 2 Mano (::mano, needinfo? for any questions; not reading general bugmail) 2012-03-24 04:01:53 PDT
*** Bug 735950 has been marked as a duplicate of this bug. ***
Comment 3 Jason Orendorff [:jorendorff] 2012-04-04 11:39:51 PDT
Comment on attachment 597146 [details] [diff] [review]
SetIteratorObject, v1

I'm going to do something else here.
Comment 4 Jason Orendorff [:jorendorff] 2012-06-18 07:36:26 PDT
Created attachment 634027 [details] [diff] [review]
WIP 1

Needs tests.
Comment 5 Jason Orendorff [:jorendorff] 2012-06-18 16:35:04 PDT
Created attachment 634230 [details] [diff] [review]
v2

This righteous patch applies on top of the patches in bug 743107 and bug 725907.
Comment 6 Luke Wagner [:luke] 2012-06-28 16:35:41 PDT
Comment on attachment 634230 [details] [diff] [review]
v2

Review of attachment 634230 [details] [diff] [review]:
-----------------------------------------------------------------

Looks clean, nice tests.  r+ assuming you've had someone like dherman check out the semantics you've spelled out in your test-cases.

::: js/src/builtin/MapObject.cpp
@@ +384,5 @@
> +    ValueMap::Range *range = cx->new_<ValueMap::Range>(data->all());
> +    if (!range)
> +        return false;
> +
> +    JSObject *iterobj = NewObjectWithGivenProto(cx, &class_, proto, global);

We should be able to give JSObject::global etc a Handle return type (using fromMarkedLocation on JSCompartment::global_) which would allow inline use of mapobj->global() here.

@@ +418,5 @@
> +        if (range) {
> +            cx->delete_(range);
> +            thisobj->setReservedSlot(RangeSlot, PrivateValue(NULL));
> +        }
> +        return js_ThrowStopIteration(cx);

I'd rather read two different if statements here to avoid the more complex nesting.

::: js/src/builtin/MapObject.h
@@ +127,5 @@
> +    enum { TargetSlot, RangeSlot, SlotCount };
> +    static JSFunctionSpec methods[];
> +    static SetIteratorObject *create(JSContext *cx, HandleObject setobj, ValueSet *data);
> +  private:
> +    inline ValueSet::Range *getRange();

Since infallible, effectively fields, could you remove the "get" prefix?
Comment 7 Jason Orendorff [:jorendorff] 2012-07-03 16:35:50 PDT
(In reply to Luke Wagner [:luke] from comment #6)
> Looks clean, nice tests.  r+ assuming you've had someone like dherman check
> out the semantics you've spelled out in your test-cases.

Well, mostly. In broad terms, these are the semantics dherman and I agreed on:
- iterate over entries in insertion order
- iterate over the live data, not a copy
- in the face of changes, don't skip any entry that wasn't deleted

The tests here run ahead of the current spec work a bit, and dherman knows that. The current proposal in the wiki doesn't deal with changes to the Map/Set during iteration in a way that TC39 would really want to specify.

I haven't gone through the tests one by one with dherman. TC39 may still decide to make some of this behavior just throw, rather than specify how iterators should behave in the face of certain kinds of changes. If so, I'll update the implementation.

Does your r+ stand, given all this?

> We should be able to give JSObject::global etc a Handle return type (using
> fromMarkedLocation on JSCompartment::global_) which would allow inline use
> of mapobj->global() here.

Excellent. Patch coming up in bug 770737.

> I'd rather read two different if statements here to avoid the more complex
> nesting.

Fixed.

> > +    inline ValueSet::Range *getRange();
> Since infallible, effectively fields, could you remove the "get" prefix?

Done.
Comment 8 Luke Wagner [:luke] 2012-07-03 17:21:27 PDT
(In reply to Jason Orendorff [:jorendorff] from comment #7)
> Does your r+ stand, given all this?
Yessir, thanks.
Comment 9 Jason Orendorff [:jorendorff] 2012-07-04 09:12:44 PDT
https://hg.mozilla.org/integration/mozilla-inbound/rev/8e3bc766092d

This is the culmination of a lot of work.
Comment 10 Mano (::mano, needinfo? for any questions; not reading general bugmail) 2012-07-04 11:16:03 PDT
Thanks for your hard work on this, Jason.

I'm not sure if this was discussed somewhere, but just in case it's a bug: "[x for (x of m)]" (as mentioned in your original report) still does not work.

Setting dev-doc-needed for map.iterator.
Comment 11 Jason Orendorff [:jorendorff] 2012-07-04 12:35:41 PDT
It works for me. In the JS shell:

js> var m = new Map;
js> m.set("x", 1);
js> m.set("y", 2);
js> [x for (x of m)]
[["x", 1], ["y", 2]]
js> var s = new Set;
js> s.add(42);
js> [x for (x of s)]
[42]
Comment 12 Jason Orendorff [:jorendorff] 2012-07-04 13:03:30 PDT
Things to document here:

- You can now iterate over all the members of a Set using for-of:

    var myset = Set([4, 7, 6, 5, 3]);
    for (var item of set)
        alert(item);  // alerts each number in this order: 4, 7, 6, 5, 3

  This visits all the elements of the set--in the order they were inserted.

- You can now iterate over all the pairs in a Map using for-of:

    var mymap = new Map;
    mymap.set("x", 1);
    mymap.set("y", 2);
    for (var pair of mymap)
        alert(pair);  // alerts twice, first "x,1" then "y,2".

  Each pair is just an ordinary Array.

- When iterating over the contents of a Map, it's useful to provide a pair
  of variables:

    for (var [key, val] of mymap)
        alert(key + "==>" + val);  // alerts twice, "x==>1" then "y==>2".

  I think this is one of the most useful examples of destructuring in the
  language.

- How to convert a Set to a plain Array:

    var myarr = [v for (v of myset)];  // [4, 7, 6, 5, 3]

  Again, the values come out in the same order they were inserted.

- How to get all the keys, or all the values, of a Map:

    var keys = [k for ([k, v] of mymap)];  // ["x", "y"]
    var vals = [v for ([k, v] of mymap)];  // [1, 2]

  (There will also be standard methods for this, probably called
  .keys() and .values(); but they're not implemented yet.)

- It's OK to add entries to a Set or Map while you're iterating over it.
  The loop will continue until it has visited all the entries in the Map or Set,
  including those that were added during iteration.

- It's OK to remove entries from a Set (using the .remove(val) method)
  or Map (using the .delete(key) method) while you're iterating over it.
  The loop will continue until it has visited all the entries that are still
  in the Map or Set. It will not visit entries that aren't there anymore.

- About the .iterator methods, perhaps it is best to say only that they return
  a new iterator object, and link to some documentation (if we have any) about
  iterators. You should rarely, if ever, see a call to an .iterator() method
  in JS code. Instead, JS programs will normally just use a for-of loop.

  (Similarly, in Python it is distinctly odd to call an .__iter__() method
  explicitly. The for-loop does that for you.)
Comment 13 Ryan VanderMeulen [:RyanVM] 2012-07-04 16:24:42 PDT
https://hg.mozilla.org/mozilla-central/rev/8e3bc766092d
Comment 14 :Ehsan Akhgari (out sick) 2012-07-04 16:55:18 PDT
I was backing out a number of patches in the js land, and unfortunately this patch caused a number of merge conflicts which I did not trust myself to resolve.  Therefore, I had to back it out.  Please reland after fixing the conflicts resulting from the backouts.  Thanks, and apologies for the inconvenience.

Backout changeset:
https://hg.mozilla.org/mozilla-central/rev/cd8db9c2ffc3
Comment 15 Paul Rouget [:paul] 2012-07-13 06:32:20 PDT
Could someone re-land this? Would be great to get that for Firefox 16.
Comment 16 Jason Orendorff [:jorendorff] 2012-07-18 13:46:50 PDT
You bet I am working on re-landing this. It bounced due to grossness in bug 749010 which is now resolved.
Comment 17 Jason Orendorff [:jorendorff] 2012-07-25 12:09:12 PDT
Relanded. Missed FF16, alas.
https://hg.mozilla.org/integration/mozilla-inbound/rev/76fba3ad58dd
Comment 18 Ed Morley [:emorley] 2012-07-26 05:10:21 PDT
https://hg.mozilla.org/mozilla-central/rev/76fba3ad58dd
Comment 20 Florian Scholz [:fscholz] (MDN) 2014-11-30 08:42:05 PST
Thanks for the doc updates, :arai!

Note You need to log in before you can comment on or make changes to this bug.