The default bug view has changed. See this FAQ.

Make Maps and Sets iterable

RESOLVED FIXED in mozilla17

Status

()

Core
JavaScript Engine
RESOLVED FIXED
5 years ago
2 years ago

People

(Reporter: jorendorff, Assigned: jorendorff)

Tracking

(Blocks: 2 bugs, {dev-doc-complete})

Other Branch
mozilla17
dev-doc-complete
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [DocArea=JS])

Attachments

(1 attachment, 2 obsolete attachments)

(Assignee)

Description

5 years ago
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
(Assignee)

Comment 1

5 years ago
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.
Assignee: general → jorendorff
Attachment #597146 - Flags: review?(luke)
Duplicate of this bug: 735950
Blocks: 738911
(Assignee)

Comment 3

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

I'm going to do something else here.
Attachment #597146 - Flags: review?(luke)
(Assignee)

Updated

5 years ago
Depends on: 743107
(Assignee)

Comment 4

5 years ago
Created attachment 634027 [details] [diff] [review]
WIP 1

Needs tests.
Attachment #597146 - Attachment is obsolete: true
(Assignee)

Updated

5 years ago
Depends on: 725907
(Assignee)

Comment 5

5 years ago
Created attachment 634230 [details] [diff] [review]
v2

This righteous patch applies on top of the patches in bug 743107 and bug 725907.
Attachment #634027 - Attachment is obsolete: true
Attachment #634230 - Flags: review?(luke)

Comment 6

5 years ago
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?
Attachment #634230 - Flags: review?(luke) → review+
(Assignee)

Comment 7

5 years ago
(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

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

Comment 9

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

This is the culmination of a lot of work.
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.
Keywords: dev-doc-needed
(Assignee)

Comment 11

5 years ago
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]
(Assignee)

Comment 12

5 years ago
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.)
https://hg.mozilla.org/mozilla-central/rev/8e3bc766092d
Status: NEW → RESOLVED
Last Resolved: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla16
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
Status: RESOLVED → REOPENED
Resolution: FIXED → ---

Comment 15

5 years ago
Could someone re-land this? Would be great to get that for Firefox 16.
(Assignee)

Comment 16

5 years ago
You bet I am working on re-landing this. It bounced due to grossness in bug 749010 which is now resolved.

Updated

5 years ago
Blocks: 775781
(Assignee)

Comment 17

5 years ago
Relanded. Missed FF16, alas.
https://hg.mozilla.org/integration/mozilla-inbound/rev/76fba3ad58dd
https://hg.mozilla.org/mozilla-central/rev/76fba3ad58dd
Status: REOPENED → RESOLVED
Last Resolved: 5 years ago5 years ago
Resolution: --- → FIXED
Depends on: 779025
Target Milestone: mozilla16 → mozilla17
Depends on: 788364
Whiteboard: [DocArea=JS]
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
Thanks for the doc updates, :arai!
Keywords: dev-doc-needed → dev-doc-complete
You need to log in before you can comment on or make changes to this bug.