Closed Bug 725909 Opened 12 years ago Closed 12 years ago

Make Maps and Sets iterable

Categories

(Core :: JavaScript Engine, defect)

Other Branch
defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla17

People

(Reporter: jorendorff, Assigned: jorendorff)

References

(Blocks 1 open bug)

Details

(Keywords: dev-doc-complete, Whiteboard: [DocArea=JS])

Attachments

(1 file, 2 obsolete files)

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
Attached patch SetIteratorObject, v1 (obsolete) — Splinter Review
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)
Blocks: 738911
Comment on attachment 597146 [details] [diff] [review]
SetIteratorObject, v1

I'm going to do something else here.
Attachment #597146 - Flags: review?(luke)
Depends on: 743107
Attached patch WIP 1 (obsolete) — Splinter Review
Needs tests.
Attachment #597146 - Attachment is obsolete: true
Depends on: 725907
Attached patch v2Splinter Review
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 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+
(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.
(In reply to Jason Orendorff [:jorendorff] from comment #7)
> Does your r+ stand, given all this?
Yessir, thanks.
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
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]
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
Closed: 12 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 → ---
Could someone re-land this? Would be great to get that for Firefox 16.
You bet I am working on re-landing this. It bounced due to grossness in bug 749010 which is now resolved.
Blocks: 775781
https://hg.mozilla.org/mozilla-central/rev/76fba3ad58dd
Status: REOPENED → RESOLVED
Closed: 12 years ago12 years ago
Resolution: --- → FIXED
Depends on: 779025
Target Milestone: mozilla16 → mozilla17
Whiteboard: [DocArea=JS]
Thanks for the doc updates, :arai!
You need to log in before you can comment on or make changes to this bug.