Last Comment Bug 699565 - Implement Harmony for-of loops
: Implement Harmony for-of loops
Status: RESOLVED FIXED
: dev-doc-complete
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Other Branch
: x86 Mac OS X
: -- normal (vote)
: mozilla13
Assigned To: Jason Orendorff [:jorendorff]
:
Mentors:
Depends on: 726411 728079 738193 738196 746791
Blocks: es6
  Show dependency treegraph
 
Reported: 2011-11-03 13:59 PDT by Jason Orendorff [:jorendorff]
Modified: 2013-04-29 03:16 PDT (History)
27 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
WIP 1 - first stab, works only with proxies, no decompiler support yet, no tests (8.79 KB, patch)
2011-11-03 13:59 PDT, Jason Orendorff [:jorendorff]
no flags Details | Diff | Splinter Review
WIP 2 - works with proxies and generator-iterators, decompiler works, a few tests (28.89 KB, patch)
2011-11-04 16:54 PDT, Jason Orendorff [:jorendorff]
no flags Details | Diff | Splinter Review
WIP 3, part 1 - basics (30.61 KB, patch)
2011-11-04 17:25 PDT, Jason Orendorff [:jorendorff]
no flags Details | Diff | Splinter Review
WIP 3, part 2 - array support (18.07 KB, patch)
2011-11-04 17:32 PDT, Jason Orendorff [:jorendorff]
no flags Details | Diff | Splinter Review
WIP 4, part 1 - basics (32.17 KB, patch)
2012-01-05 19:11 PST, Jason Orendorff [:jorendorff]
no flags Details | Diff | Splinter Review
WIP 4, part 2 - array support (27.52 KB, patch)
2012-01-05 19:12 PST, Jason Orendorff [:jorendorff]
no flags Details | Diff | Splinter Review
WIP 5, part 1 - basics (32.09 KB, patch)
2012-01-13 15:09 PST, Jason Orendorff [:jorendorff]
no flags Details | Diff | Splinter Review
WIP 5, part 2 - arrays (27.52 KB, patch)
2012-01-13 15:09 PST, Jason Orendorff [:jorendorff]
no flags Details | Diff | Splinter Review
WIP 5, part 3 - array-like DOM objects (2.65 KB, patch)
2012-01-13 15:10 PST, Jason Orendorff [:jorendorff]
no flags Details | Diff | Splinter Review
silly html test case (1.49 KB, text/html)
2012-01-13 15:11 PST, Jason Orendorff [:jorendorff]
no flags Details
v6, part 1 - basics (32.47 KB, patch)
2012-01-19 17:14 PST, Jason Orendorff [:jorendorff]
jwalden+bmo: review+
Details | Diff | Splinter Review
v6, part 2 - arrays (29.42 KB, patch)
2012-01-19 17:15 PST, Jason Orendorff [:jorendorff]
bhackett1024: review+
Details | Diff | Splinter Review
v6, part 3 - wrappers (9.21 KB, patch)
2012-01-19 17:15 PST, Jason Orendorff [:jorendorff]
bhackett1024: review+
Details | Diff | Splinter Review
v6, part 4 - array-like DOM objects (7.37 KB, patch)
2012-01-19 17:16 PST, Jason Orendorff [:jorendorff]
no flags Details | Diff | Splinter Review
v6, part 5 - arguments (9.56 KB, patch)
2012-01-19 17:17 PST, Jason Orendorff [:jorendorff]
bhackett1024: review+
Details | Diff | Splinter Review
v6, part 6 - typed arrays (5.89 KB, patch)
2012-01-19 17:17 PST, Jason Orendorff [:jorendorff]
bhackett1024: review+
Details | Diff | Splinter Review
v6.1, part 4 - array-like DOM objects (6.11 KB, patch)
2012-01-20 02:25 PST, Jason Orendorff [:jorendorff]
no flags Details | Diff | Splinter Review
v6.2, part 4 - array-like DOM objects (7.45 KB, patch)
2012-01-25 17:22 PST, Jason Orendorff [:jorendorff]
bzbarsky: review+
Details | Diff | Splinter Review
adding dense array length guard (744 bytes, patch)
2012-02-11 08:07 PST, Yusuke Suzuki
no flags Details | Diff | Splinter Review

Description Jason Orendorff [:jorendorff] 2011-11-03 13:59:06 PDT
Created attachment 571770 [details] [diff] [review]
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] 2011-11-04 16:54:05 PDT
Created attachment 572126 [details] [diff] [review]
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] 2011-11-04 17:25:38 PDT
Created attachment 572134 [details] [diff] [review]
WIP 3, part 1 - basics

This is just like WIP 2 but with a couple extra tests.
Comment 3 Jason Orendorff [:jorendorff] 2011-11-04 17:32:33 PDT
Created attachment 572137 [details] [diff] [review]
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] 2012-01-05 19:11:38 PST
Created attachment 586320 [details] [diff] [review]
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] 2012-01-05 19:12:27 PST
Created attachment 586321 [details] [diff] [review]
WIP 4, part 2 - array support

Unbitrotted, and new tests for slow arrays, break, throw, return.
Comment 6 Jason Orendorff [:jorendorff] 2012-01-13 15:09:16 PST
Created attachment 588537 [details] [diff] [review]
WIP 5, part 1 - basics
Comment 7 Jason Orendorff [:jorendorff] 2012-01-13 15:09:46 PST
Created attachment 588538 [details] [diff] [review]
WIP 5, part 2 - arrays
Comment 8 Jason Orendorff [:jorendorff] 2012-01-13 15:10:09 PST
Created attachment 588539 [details] [diff] [review]
WIP 5, part 3 - array-like DOM objects
Comment 9 Jason Orendorff [:jorendorff] 2012-01-13 15:11:04 PST
Created attachment 588540 [details]
silly html test case

This actually works with the WIP 5 patches applied.
Comment 10 Jason Orendorff [:jorendorff] 2012-01-19 17:14:53 PST
Created attachment 590055 [details] [diff] [review]
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] 2012-01-19 17:15:23 PST
Created attachment 590056 [details] [diff] [review]
v6, part 2 - arrays
Comment 12 Jason Orendorff [:jorendorff] 2012-01-19 17:15:59 PST
Created attachment 590057 [details] [diff] [review]
v6, part 3 - wrappers
Comment 13 Jason Orendorff [:jorendorff] 2012-01-19 17:16:27 PST
Created attachment 590058 [details] [diff] [review]
v6, part 4 - array-like DOM objects
Comment 14 Jason Orendorff [:jorendorff] 2012-01-19 17:17:01 PST
Created attachment 590059 [details] [diff] [review]
v6, part 5 - arguments
Comment 15 Jason Orendorff [:jorendorff] 2012-01-19 17:17:40 PST
Created attachment 590060 [details] [diff] [review]
v6, part 6 - typed arrays
Comment 16 Jason Orendorff [:jorendorff] 2012-01-19 17:18:34 PST
(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] 2012-01-20 02:25:07 PST
Created attachment 590157 [details] [diff] [review]
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] 2012-01-20 02:40:06 PST
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 (:bhackett) 2012-01-23 14:30:11 PST
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] 2012-01-24 16:30:50 PST
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] (remove +bmo to email) 2012-01-25 15:55:28 PST
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] 2012-01-25 17:22:28 PST
Created attachment 591662 [details] [diff] [review]
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] 2012-01-27 10:44:52 PST
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 [:bz] 2012-01-27 10:46:17 PST
Jason, sorry for the lag here.  I'll try to make sure to get to this on Monday....
Comment 25 Boris Zbarsky [:bz] 2012-02-01 12:37:56 PST
Comment on attachment 591662 [details] [diff] [review]
v6.2, part 4 - array-like DOM objects

r=me
Comment 27 Marek Stępień [:marcoos, inactive] 2012-02-08 12:27:31 PST
The https://developer.mozilla.org/en/JavaScript/Reference/Statements/for...of article really needs improvement.
Comment 28 teramako 2012-02-09 07:45:28 PST
(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 2012-02-10 11:13:05 PST
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 [:bz] 2012-02-10 11:28:15 PST
It's not, no.  It's not even a DOM object at all.
Comment 31 Marek Stępień [:marcoos, inactive] 2012-02-10 11:32:28 PST
(In reply to teramako from comment #28)
> 2nd example is wrong.
> Thorws "TypeError: obj is not iteratable"

I removed that example.
Comment 32 caisui 2012-02-11 06:46:19 PST
array is strange values.

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

Results:
[-4.653735800328269e+129,-4.653735800328269e+129]
Comment 33 Yusuke Suzuki 2012-02-11 08:07:18 PST
Created attachment 596332 [details] [diff] [review]
adding dense array length guard

I found missing dense array length gaurd and attached patch.
Comment 34 Masatoshi Kimura [:emk] 2012-02-12 01:28:56 PST
Please file a new bug and block this bug instead of working on the fixed bug.
Comment 35 Yusuke Suzuki 2012-02-12 02:17:18 PST
(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] 2012-02-15 12:20:09 PST
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] 2012-03-21 03:18:17 PDT
(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.

Note You need to log in before you can comment on or make changes to this bug.