699565 - Implement Harmony for-of loops

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jason Orendorff [:jorendorff]]

Attachment: WIP 1 - first stab, works only with proxies, no decompiler support yet, no tests

There will be some workarounds for the lack of modules and private names, but we can get the basics working now.

We do already have proxies, and in fact the iterate trap exists, so that part should work fine.

Comment 1

[Jason Orendorff [:jorendorff]]

Attachment: WIP 2 - works with proxies and generator-iterators, decompiler works, a few tests

I'm out of town all next week, but I'll get on this when I come back.

I've been looking ahead to see how array iteration might work. The key question is whether array iterator objects are to be exposed to user code. dherman may take this question to TC39.

If array iterators are internal-use-only, i.e. there is no builtin function Array.prototype[iterate], then TC39 can avoid having to specify a lot of details, because then there are fewer opportunities to observe or side-effect the iterator state. We can avoid actually having to expose a .next() method for them. Iteration would likely be easier to optimize as a result.

If array iterator objects are exposed to user code, here is a sketch that hints at the amount of specification work TC39 will have to do:

/*
  Array iterators are like this:

  Array.prototype[iterate] = function () {
      for (var i = 0; i < (this.length >>> 0); i++) {
          var desc = Object.getOwnPropertyDescriptor(this, i);
          yield desc === undefined ? undefined : this[i];
      }
  }

  This has the following implications:

    - Array iterators are generic; Array.prototype[iterate] can be
      transferred to any other object to create iterators over it.

    - The next() method of an Array iterator is non-reentrant. Trying to
      reenter, e.g. by using it on an object with a length getter that
      calls it.next() on the same iterator, causes a TypeError.

    - The iterator fetches obj.length every time its next() method is
      called.

    - The iterator converts obj.length to a whole number using
      ToUint32. As a consequence the iterator can't go on forever; it
      can yield at most 2^32-1 values. Then i will be 0xffffffff, and no
      possible length value will be greater than that.

    - The iterator does not skip "array holes". When it encounters a
      hole, it yields undefined.

    - The iterator never consults the prototype chain.

    - If an element has a getter which throws, the exception is
      propagated, and the iterator is closed (that is, all future calls
      to next() will simply throw StopIteration).

  However I think we want iterator objects to differ from the above
  code in a few details, like their [[Prototype]] and perhaps
  [[Class]]. The [[Prototype]] would need to be specified.

  Note that if next() were reentrant, even more ridiculous little
  details of the next method's inner workings would be observable.

*/

Comment 2

[Jason Orendorff [:jorendorff]]

Attachment: WIP 3, part 1 - basics

This is just like WIP 2 but with a couple extra tests.

Comment 3

[Jason Orendorff [:jorendorff]]

Attachment: WIP 3, part 2 - array support

This is rudimentary; it is not optimized (the JIT doesn't even know for-of exists) and there's a bug or two. But the feature is so nice.

In my notes, it says that we also want for-of support for TypedArrays, ctypes arrays, maybe Arguments objects, maybe String objects, maybe Strings. And definitely DOM Nodelists and other collections.

Comment 4

[Jason Orendorff [:jorendorff]]

Attachment: WIP 4, part 1 - basics

Unbitrotted. This works for scripted proxies but I don't think it works correctly for C++ proxies, which is a problem considering that's what NodeLists are, to say nothing of working transparently across compartment boundaries. So this needs some more work and a raft of new tests.

Comment 5

[Jason Orendorff [:jorendorff]]

Attachment: WIP 4, part 2 - array support

Unbitrotted, and new tests for slow arrays, break, throw, return.

Comment 6

[Jason Orendorff [:jorendorff]]

Attachment: WIP 5, part 1 - basics

Comment 7

[Jason Orendorff [:jorendorff]]

Attachment: WIP 5, part 2 - arrays

Comment 8

[Jason Orendorff [:jorendorff]]

Attachment: WIP 5, part 3 - array-like DOM objects

Comment 9

[Jason Orendorff [:jorendorff]]

Attachment: silly html test case

This actually works with the WIP 5 patches applied.

Comment 10

[Jason Orendorff [:jorendorff]]

Attachment: v6, part 1 - basics

This is what's going through the Try Server right now. If it looks good I'll ask for a review.

Comment 11

[Jason Orendorff [:jorendorff]]

Attachment: v6, part 2 - arrays

Comment 12

[Jason Orendorff [:jorendorff]]

Attachment: v6, part 3 - wrappers

Comment 13

[Jason Orendorff [:jorendorff]]

Attachment: v6, part 4 - array-like DOM objects

Comment 14

[Jason Orendorff [:jorendorff]]

Attachment: v6, part 5 - arguments

Comment 15

[Jason Orendorff [:jorendorff]]

Attachment: v6, part 6 - typed arrays

Comment 16

[Jason Orendorff [:jorendorff]]

(I'll file a follow-up bug for ctypes arrays. Also strings and String objects, if it turns out that TC39 is going to specify for-of on those.)

Comment 17

[Jason Orendorff [:jorendorff]]

Attachment: v6.1, part 4 - array-like DOM objects

There was a minor bug in one of the tests in this patch. Otherwise the Try run was successful.

Comment 18

[Jason Orendorff [:jorendorff]]

Comment on attachment 590056 [details] [diff] [review]
v6, part 2 - arrays

I have to apologize a little bit for how ugly this is. Iteration has accumulated a lot of cruft, and this adds a little to it -- but in the scheme of things, only a little.

Cleaning it up isn't a major priority but I can think of two things that would help:

1) fuse js_IteratorNext and js_IteratorMore (bug 683694).

2) add an iteratorNext hook to js::Class and an iteratorNext method to JSObject, so as to get rid of js_IteratorNext and js_IteratorMore entirely.

I think these are probably both pretty easy except for maybe the decompiler (unless the JIT code for enumeration is scary; I haven't looked).

Comment 19

[Brian Hackett [Laid off!]]

Comment on attachment 590056 [details] [diff] [review]
v6, part 2 - arrays

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

::: js/src/jsiter.cpp
@@ +1090,5 @@
>  {
>      return SuppressDeletedPropertyHelper(cx, obj, IndexRangePredicate(begin, end));
>  }
>  
> +const uint32_t CLOSED_INDEX = 0xffffffffu;

Can this use UINT32_MAX?

@@ +1101,5 @@
> +
> +inline JSObject *
> +ElementIteratorObject::getTargetObject() const
> +{
> +    return getParent();

This object should be stored in a reserved slot, not at obj->getParent().  With the objshrink stuff we now need to make separate shapes and base shapes for each distinct object parent.  It doesn't make a giant difference here, but ad hoc uses of parent should go away.

@@ +1107,5 @@
> +
> +inline void
> +ElementIteratorObject::setIndex(uint32_t index)
> +{
> +    setPrivate((void *) index);

It's also generally good to avoid objects with JSCLASS_HAS_PRIVATE, as accessing the private data is slower than going to a fixed reserved slot.  I don't know if that change should be made here though, as PrivateValue can't be used with words with the low bit set and DoubleValue or a coerced Int32Value would be ugly.

@@ +1135,5 @@
> +            vp->setUndefined();
> +    } else {
> +        /* Make a jsid for this index. */
> +        jsid id;
> +        if (i < 0x7fffffffu && INT_FITS_IN_JSID(i)) {

Can this use INT32_MAX?

@@ +1147,5 @@
> +        /* Find out if this object has an element i. */
> +        bool has;
> +        if (obj->isProxy()) {
> +            if (!Proxy::hasOwn(cx, obj, id, &has))
> +                goto error;

Does js_HasOwnProperty not work on proxies, or is this an optimization?  Can you add a comment?

Comment 20

[Jason Orendorff [:jorendorff]]

Thanks. I took all the comments. Changing ElementIteratorObject to use an int32 reserved slot for the index, rather than HAS_PRIVATE, was a tiny amount of code, so no problems there.

> Does js_HasOwnProperty not work on proxies, or is this an optimization?  Can
> you add a comment?

It doesn't work on proxies. Pretty gross, huh. I added a comment.

Comment 21

[Jeff Walden [:Waldo]]

Comment on attachment 590055 [details] [diff] [review]
v6, part 1 - basics

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

::: js/src/frontend/Parser.cpp
@@ +3274,5 @@
>          forStmt.type = STMT_FOR_IN_LOOP;
>  
> +        /* Set pn_iflags and rule out invalid combinations. */
> +        if (forOf && pn->pn_iflags != 0) {
> +            reportErrorNumber(NULL, JSREPORT_ERROR, JSMSG_BAD_FOR_EACH_LOOP);

Assert that |pn->pn_iflags == JSITER_FOREACH| in case code above this ever starts setting more iteration flags.

@@ +5463,5 @@
> +            return NULL;
> +        }
> +        if (forOf) {
> +            if (pn2->pn_iflags != JSITER_ENUMERATE) {
> +                reportErrorNumber(NULL, JSREPORT_ERROR, JSMSG_BAD_FOR_EACH_LOOP);

Again, assert that pn2->pn_iflags == JSITER_FOREACH?

::: js/src/jit-test/lib/referencesVia.js
@@ +1,1 @@
> +function referencesVia(from, edge, to) {

This seems out-of-place in this patch?

::: js/src/jit-test/tests/for-of/decompiler.js
@@ +17,5 @@
> +test("for (a of b) { f(a); }");
> +test("for (a of b) { f(a); g(a); }");
> +
> +// for-of with "in" operator nearby
> +test("for (a of b in c ? c : c.items()) { f(a); }");

Ugh is that an unreadable mess...

::: js/src/jit-test/tests/for-of/generators-6.js
@@ +1,1 @@
> +// Named break closes the right generator-iterators.

Clever.

::: js/src/jit-test/tests/for-of/non-iterable.js
@@ +7,5 @@
> +    Object.create(null),
> +    Object.create(Array.prototype),
> +    null, undefined,
> +    true, 0, 3.1416,
> +    new Boolean(true), new Number(0)];

Add a string primitive too.

@@ +12,5 @@
> +
> +for (var i = 0; i < misc.length; i++) {
> +    let obj = misc[i];
> +    var testfn = function () {
> +        for (var v of obj)

Nitpicky, but name |obj| as |v|, and change |v| to |_|?  They're not all objects.  (I nearly asked you for another set of tests for the non-enumerable cases, and that might have been affected by the name here not registering the non-object cases quite so strongly.)

::: js/src/jit-test/tests/for-of/proxy-2.js
@@ +6,5 @@
> +        for (var i = 0; i < arr.length; i++)
> +            yield arr[i];
> +    }
> +});
> +assertEq([v for (v of proxy)].join(), "a,b,c,d");

Just for extra explicitness and readability, pass "," to join?

Does the iterate hook get invoked a second time if you of it again?  Copy this line a second time, and update it if necessary.

::: js/src/jit-test/tests/for-of/proxy-3.js
@@ +1,1 @@
> +// An exception thrown from an iterate trap is propagated.

What if the iterate trap is a function, but it throws StopIteration?  Test please.

::: js/src/jit-test/tests/for-of/proxy-4.js
@@ +6,5 @@
> +    iterate: function () { throw "FAIL"; },
> +    fix: function () { return {}; }
> +});
> +Object.preventExtensions(p);
> +assertThrowsInstanceOf(function () { for (var v of p) {} }, TypeError);

So if fix returned something not |{}|, you could totally iterate here, right?  Add a test where the thing returned is itself iterable, and verify that iteration works.

::: js/src/jsiter.cpp
@@ +670,5 @@
>          if (JSIteratorOp op = obj->getClass()->ext.iteratorObject) {
> +            /*
> +             * Arrays and other classes representing iterable collections have
> +             * the JSCLASS_FOR_OF_ITERATION flag. This flag means that the
> +             * object responds all other kinds of enumeration (for-in,

You accidentally a to?

::: js/src/jsopcode.cpp
@@ +3730,5 @@
>                  js_printf(jp, ";\n");
>                  break;
>  
>                case JSOP_ITER:
> +                forOf = (pc[1] == JSITER_FOR_OF);

GET_UINT8(pc) now; you probably have a merge conflict for this, actually.

Comment 22

[Jason Orendorff [:jorendorff]]

Attachment: v6.2, part 4 - array-like DOM objects

Fix a typo in the test. I must have flubbed an hg command at some point; try server found the mistake.

Comment 23

[Jason Orendorff [:jorendorff]]

I took all Waldo's comments too except the last one quoted below.

> Add a string primitive too.

Ah, yes.  Done.  I didn't have one because I don't know if we were going
to do for-of loops over strings (visiting each 16-bit "character") or
not.  But it is better to have the test than not to have it.

> What if the iterate trap is a function, but it throws StopIteration?
> Test please.

Done.  (StopIteration is propagated like any other exception.)

> Does the iterate hook get invoked a second time if you of it again?
> Copy this line a second time, and update it if necessary.

Yes, the iterate hook is called every time you for-of the proxy.  (Btw, I
used a for i=0; i<2; i++ loop instead of copying the line.)

> So if fix returned something not |{}|, you could totally iterate here,
> right?

No, AIUI you're only allowed to return a bag of property descriptors
from the fix hook. The proxy becomes a boring Object. You could return
{length: {value: 2}, 0: {value: 'hello'}, 1: {value: 'world'}} but the
resulting fixed proxy still wouldn't be iterable any more than it would
be an Array.

This is kind of weird because the old proxy spec, containing "fix", is a
dead end. It won't be updated and we can't expect a call one way or the
other from TC39 about this issue.

The new direct proxy spec doesn't even have a fix hook, not that we have
implemented direct proxies yet.

Comment 24

[Boris Zbarsky [:bzbarsky]]

Jason, sorry for the lag here.  I'll try to make sure to get to this on Monday....

Comment 25

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 591662 [details] [diff] [review]
v6.2, part 4 - array-like DOM objects

r=me

Comment 26

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/90ecec15f74b
https://hg.mozilla.org/mozilla-central/rev/a3f31325951d
https://hg.mozilla.org/mozilla-central/rev/db1398b72779
https://hg.mozilla.org/mozilla-central/rev/426eb532589c
https://hg.mozilla.org/mozilla-central/rev/8d880d72023f
https://hg.mozilla.org/mozilla-central/rev/1a777b2a13ce

Comment 27

[Marek Stępień [:marcoos, inactive]]

The https://developer.mozilla.org/en/JavaScript/Reference/Statements/for...of article really needs improvement.

Comment 28

[teramako]

(In reply to Marek Stępień [:marcoos] from comment #27)
> The
> https://developer.mozilla.org/en/JavaScript/Reference/Statements/for...of
> article really needs improvement.

2nd example is wrong.
Thorws "TypeError: obj is not iteratable"

Comment 29

[Philip Chee]

Seems to work in the main but when I do something like:

    var treecols = treeview.tree.columns;
    for (let treecol of treecols)

I get an error:

Error: '[JavaScript Error: "treecols is not iterable" {file: "chrome://navigator/content/pageinfo/pageInfo.js" line: 134}]' when calling method: [nsITreeView::cycleHeader] = NS_ERROR_XPC_JAVASCRIPT_ERROR_WITH_DETAILS

So isn't nsITreeColumns an "array-like DOM object"?

Comment 30

[Boris Zbarsky [:bzbarsky]]

It's not, no.  It's not even a DOM object at all.

Comment 31

[Marek Stępień [:marcoos, inactive]]

(In reply to teramako from comment #28)
> 2nd example is wrong.
> Thorws "TypeError: obj is not iteratable"

I removed that example.

Comment 32

[caisui]

array is strange values.

[a for(a of [,,])]

Results:
[-4.653735800328269e+129,-4.653735800328269e+129]

Comment 33

[Yusuke Suzuki]

Attachment: adding dense array length guard

I found missing dense array length gaurd and attached patch.

Comment 34

[Masatoshi Kimura [:emk]]

Please file a new bug and block this bug instead of working on the fixed bug.

Comment 35

[Yusuke Suzuki]

(In reply to Masatoshi Kimura [:emk] from comment #34)
> Please file a new bug and block this bug instead of working on the fixed bug.

Thanks. I filed new bug 726411 and moved patch to it.

Comment 36

[Eric Shepherd [:sheppy]]

Is there any advice on what if anything still needs to be done to the documentation for for-of? If not, I will mark this as doc complete.

https://developer.mozilla.org/en/JavaScript/Reference/Statements/for...of

Comment 37

[Dão Gottwald [:dao]]

(In reply to Eric Shepherd [:sheppy] from comment #36)
> Is there any advice on what if anything still needs to be done to the
> documentation for for-of? If not, I will mark this as doc complete.
> 
> https://developer.mozilla.org/en/JavaScript/Reference/Statements/for...of

I modified this example:

> let arr = [ 3, 5, 7 ];
>
> for (let i in arr) {
>    console.log(i); // logs "0", "1", "2"
> }
>
> for (let i of arr) {
>    console.log(i); // logs "3", "5", "7"
> }

... to highlight an important difference between for..in/for each..in and for..of:

> let arr = [ 3, 5, 7 ];
> arr.foo = "hello";
>
> for (let i in arr) {
>    console.log(i); // logs "0", "1", "2", "foo"
> }
>
> for (let i of arr) {
>    console.log(i); // logs "3", "5", "7"
> }

This still needs to be verbalized.

Comment 38

[David Bruant]

Doc here: https://developer.mozilla.org/en/JavaScript/Reference/Statements/for...of