725909 - Make Maps and Sets iterable

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jason Orendorff [:jorendorff]]

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]]

Attachment: 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 3

[Jason Orendorff [:jorendorff]]

Comment on attachment 597146 [details] [diff] [review]
SetIteratorObject, v1

I'm going to do something else here.

Comment 4

[Jason Orendorff [:jorendorff]]

Attachment: WIP 1

Needs tests.

Comment 5

[Jason Orendorff [:jorendorff]]

Attachment: v2

This righteous patch applies on top of the patches in bug 743107 and bug 725907.

Comment 6

[Luke Wagner [:luke]]

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]]

(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]]

(In reply to Jason Orendorff [:jorendorff] from comment #7)
> Does your r+ stand, given all this?
Yessir, thanks.

Comment 9

[Jason Orendorff [:jorendorff]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/8e3bc766092d

This is the culmination of a lot of work.

Comment 10

[Asaf Romano (gone)]

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]]

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]]

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]]

https://hg.mozilla.org/mozilla-central/rev/8e3bc766092d

Comment 14

[(no longer active)]

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]]

Could someone re-land this? Would be great to get that for Firefox 16.

Comment 16

[Jason Orendorff [:jorendorff]]

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]]

Relanded. Missed FF16, alas.
https://hg.mozilla.org/integration/mozilla-inbound/rev/76fba3ad58dd

Comment 18

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/76fba3ad58dd

Comment 19

[Tooru Fujisawa [:arai]]

Updated following pages:
  https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/@@iterator
  https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/prototype
  https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set/@@iterator
  https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set/prototype

Following pages were already updated:
  https://developer.mozilla.org/en-US/Firefox/Releases/17
  https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map (example, compat table)
  https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set (example, compat table)
  https://developer.mozilla.org/en-US/docs/Web/JavaScript/New_in_JavaScript/ECMAScript_6_support_in_Mozilla

Comment 20

[Florian Scholz (Open Web Docs)]

Thanks for the doc updates, :arai!