Closed Bug 699565 Opened 8 years ago Closed 8 years ago

Implement Harmony for-of loops

Categories

(Core :: JavaScript Engine, defect)

Other Branch
x86
macOS
defect
Not set

Tracking

()

RESOLVED FIXED
mozilla13

People

(Reporter: jorendorff, Assigned: jorendorff)

References

(Blocks 1 open bug)

Details

(Keywords: dev-doc-complete)

Attachments

(8 files, 11 obsolete files)

1.49 KB, text/html
Details
32.47 KB, patch
Waldo
: review+
Details | Diff | Splinter Review
29.42 KB, patch
bhackett
: review+
Details | Diff | Splinter Review
9.21 KB, patch
bhackett
: review+
Details | Diff | Splinter Review
9.56 KB, patch
bhackett
: review+
Details | Diff | Splinter Review
5.89 KB, patch
bhackett
: review+
Details | Diff | Splinter Review
7.45 KB, patch
bzbarsky
: review+
Details | Diff | Splinter Review
744 bytes, patch
Details | Diff | Splinter Review
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.
Blocks: es6
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.

*/
Attachment #571770 - Attachment is obsolete: true
Attached patch WIP 3, part 1 - basics (obsolete) — Splinter Review
This is just like WIP 2 but with a couple extra tests.
Assignee: general → jorendorff
Attachment #572126 - Attachment is obsolete: true
Attached patch WIP 3, part 2 - array support (obsolete) — Splinter Review
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.
Attached patch WIP 4, part 1 - basics (obsolete) — Splinter Review
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.
Attachment #572134 - Attachment is obsolete: true
Attached patch WIP 4, part 2 - array support (obsolete) — Splinter Review
Unbitrotted, and new tests for slow arrays, break, throw, return.
Attachment #572137 - Attachment is obsolete: true
Attached patch WIP 5, part 1 - basics (obsolete) — Splinter Review
Attachment #586320 - Attachment is obsolete: true
Attached patch WIP 5, part 2 - arrays (obsolete) — Splinter Review
Attachment #586321 - Attachment is obsolete: true
Attached file silly html test case
This actually works with the WIP 5 patches applied.
This is what's going through the Try Server right now. If it looks good I'll ask for a review.
Attachment #588537 - Attachment is obsolete: true
Attachment #588538 - Attachment is obsolete: true
Attachment #588539 - Attachment is obsolete: true
(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.)
There was a minor bug in one of the tests in this patch. Otherwise the Try run was successful.
Attachment #590058 - Attachment is obsolete: true
Attachment #590055 - Flags: review?(jwalden+bmo)
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).
Attachment #590056 - Flags: review?(bhackett1024)
Attachment #590057 - Flags: review?(bhackett1024)
Attachment #590157 - Flags: review?(bzbarsky)
Attachment #590059 - Flags: review?(bhackett1024)
Attachment #590060 - Flags: review?(bhackett1024)
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?
Attachment #590056 - Flags: review?(bhackett1024) → review+
Attachment #590057 - Flags: review?(bhackett1024) → review+
Attachment #590059 - Flags: review?(bhackett1024) → review+
Attachment #590060 - Flags: review?(bhackett1024) → review+
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 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.
Attachment #590055 - Flags: review?(jwalden+bmo) → review+
Fix a typo in the test. I must have flubbed an hg command at some point; try server found the mistake.
Attachment #590157 - Attachment is obsolete: true
Attachment #590157 - Flags: review?(bzbarsky)
Attachment #591662 - Flags: review?(bzbarsky)
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.
Jason, sorry for the lag here.  I'll try to make sure to get to this on Monday....
Comment on attachment 591662 [details] [diff] [review]
v6.2, part 4 - array-like DOM objects

r=me
Attachment #591662 - Flags: review?(bzbarsky) → review+
(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"
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"?
It's not, no.  It's not even a DOM object at all.
(In reply to teramako from comment #28)
> 2nd example is wrong.
> Thorws "TypeError: obj is not iteratable"

I removed that example.
array is strange values.

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

Results:
[-4.653735800328269e+129,-4.653735800328269e+129]
I found missing dense array length gaurd and attached patch.
Attachment #596332 - Flags: review?(jorendorff)
Please file a new bug and block this bug instead of working on the fixed bug.
(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.
Attachment #596332 - Flags: review?(jorendorff)
Depends on: 726411
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
Depends on: 728079
(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.
Depends on: 738193
Depends on: 738196
Depends on: 746791
You need to log in before you can comment on or make changes to this bug.