810438 - for-of loop iteration of a mutated collection doesn't visit each item

Status: RESOLVED INVALID

(Core :: JavaScript Engine, defect)

Description

[Jared Wein [:jaws] (please needinfo? me)]

The following code demonstrates this:
> var arr = [0,1,2,3,4,5];
> for (var i of arr) {
>     arr.shift();    
> }
> arr;

Expected:
At the end of the loop, arr is empty.

Actual:
At the end of the loop, arr has three elements [3,4,5].

I would expect that this loop would have six iterations, but removing items from the array while iterating is causing the iterator to move forward an extra time.

Comment 1

[Jared Wein [:jaws] (please needinfo? me)]

I noticed this because the following code had a bug in it:

let elements = document.getElementsByClassName("foo");
for (let element of elements)
  element.parentNode.removeChild(element);

At the end, elements only removed half the items and it had only removed every-other item (0th, 2nd, 4th, etc).

Comment 2

[Jason Orendorff [:jorendorff]]

For the built-in Arrays, the behavior is intentionally the same as a for-loop with an index:

    var arr = [0, 1, 2, 3, 4, 5];
    for (var i = 0; i < arr.length; i++) {
        arr.shift();
    }
    arr;  // also [3, 4, 5]

To be more specific about it, when you do `for (var i of arr)`, an iterator object is created. If arr is an array, then that iterator object is little more than a counter. It produces arr[0], then arr[1], then arr[2]; and it is completely oblivious to mutating operations like .shift()/.unshift()/.splice() that shift elements around within the array.

The DOM could certainly do it differently. Even the behavior for Arrays could change. All this is currently unspecified.

Comment 3

[Jared Wein [:jaws] (please needinfo? me)]

I think it should change. Developers can run into subtle bugs by using the for(;;) style incorrectly, whereas for..of could be the perfect place to prevent these types of bugs.

Comment 4

[Jeff Walden [:Waldo]]

Note that Array.prototype.shift, called in a loop, produces O(n**2) behavior.  Popping off the end of an array is fine; shifting off the front, on the other hand, requires adjusting the location of every array element.  (It's arguably fine to remove child nodes from the start, in contrast, because most to all DOM implementations store children in a doubly-linked list, so removal from the start is a constant-time operation.)

Comment 5

[Jason Orendorff [:jorendorff]]

The iteration behavior for Map and Set objects has been specified (just recently): they are robust against modification, so after this loop

    var set = Set([0, 1, 2, 3, 4, 5]);
    for (var i of set) {
        set.delete(i);
    }

set.size will be zero.

The same could (and in my view, should) be done for the DOM. All mutating DOM operations already specify how they affect NodeIterators. I think the same rules should apply to JS iterators over NodeLists. Do we have any DOM experts in this bug?

Comment 6

[Jason Orendorff [:jorendorff]]

Technical issues make it hard to do the same for Array.

Note that Array iterators are robust against other kinds of modifications. Just not the ones that can slide things around (.shift, .unshift, .splice) or scramble them (.reverse, .sort).

I think it is pretty clear how jaws wants .shift, .unshift, and .splice to behave. I just have a hard time seeing how to spec it in a way the committee would seriously consider.

jaws, how would you want for-of to behave in the case of .reverse? What about .sort?

Comment 7

[Jeff Walden [:Waldo]]

(In reply to Jason Orendorff [:jorendorff] from comment #6)
> jaws, how would you want for-of to behave in the case of .reverse? What
> about .sort?

Truly you are devious beyond the ken of mere mortals like me.  <obeisance/>

Comment 8

[Jason Orendorff [:jorendorff]]

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #7)
> (In reply to Jason Orendorff [:jorendorff] from comment #6)
> > jaws, how would you want for-of to behave in the case of .reverse? What
> > about .sort?
> 
> Truly you are devious beyond the ken of mere mortals like me.  <obeisance/>

In case there's any doubt, it was a sincere question!

Comment 9

[Jared Wein [:jaws] (please needinfo? me)]

I'm not sure how I would want it to behave for .reverse or .sort. That's a good question. Could those two be left as unspecified? :P

Another case that I'm not sure how it should be handled would be:
var arr = [0,1]
for (var el of arr)
  if (el == 1 && arr.length == 2)
    arr.unshift(0);
arr;

Comment 10

[Jason Orendorff [:jorendorff]]

(In reply to Jared Wein [:jaws] from comment #9)
> I'm not sure how I would want it to behave for .reverse or .sort. That's a
> good question. Could those two be left as unspecified? :P

Unspecified is bad. For the sake of argument, let's specify that iterators are unaffected.

Someone will then complain that you can't reverse() an array in a loop to start going back the way you came. But, whatever.

> Another case that I'm not sure how it should be handled would be:
> var arr = [0,1]
> for (var el of arr)
>   if (el == 1 && arr.length == 2)
>     arr.unshift(0);
> arr;

In a world where iterators are robust against shift/unshift/splice, I would expect the result to be [0, 0, 1].

----

I doubt the committee will go for this. I think they'll see "shift/unshift/splice on an array while you're iterating it" as a corner case that can be neglected. You wouldn't necessarily have stumbled across it yourself, if the DOM iterators had worked as expected.

And I don't see a simple fix. We would have to either make shift/unshift/splice partly non-generic, or add a new method (@@splice or [[Splice]]) to splice an arraylike object, keeping open iterators valid.

-> RESO INVALID; reopen after convincing TC39!