addAll enters infinite loop

[DartBot]

This issue was originally filed by [email protected]

---

What steps will reproduce the problem?

1. Execute this code:
     var x = [1];
     x.addAll(x);

What is the expected output?
x should be [1, 1]

What do you see instead?
The program hangs.

What version of the product are you using? On what operating system?
Dartboard and the VM. OS X.

Please provide any additional information below.
I think you just need to record length before the loop, rather than recomputing it each iteration.

[DartBot]

This comment was originally written by [email protected]

---

Added Area-VM, Triaged labels.

[ghost]

This is not a VM issue (replicateable in Dartboard and VM) but a Library issue/feature. Library needs to clarify the behavior when an a List attempts addAll on itself. I would assume that we need to check if receiver and collection are the same, in which case we copy the collection before adding it to receiver.

---

Removed Area-VM label.
Added Area-Library label.

[floitschG]

Yes this is a library issue.
Just checking if the collections are the same is unfortunately not enough (at least not in the general case). Collection.addAll takes an iterable as argument. So the problem is, when the iterator is backed by the collection we are adding to.
We only discussed this shortly in the office, but haven't yet reached a conclusion. One possibility would be to specify addAll as if it was adding into a temporary list first. Implementations could still try to shortcut. In the general case it would be slower though :(

[jmesserly]

Just hit this bug too.

A few typical ways to prevent these kinds of errors:

1. throw if mutation happens during iteration. One way to implement is to track a version number in collections and iterators, and throw if version mismatch happens. (Of course, immutable collections can skip this check). This catches a lot of potential programmer errors at the cost of extra field per collection/iterator and more difficult implementation.

2a. check "collection === this" in addAll. It won't catch sophisticated usage like people creating iteratables backed by your list, but it catches the common case and is a simple fix. (IMO, creating a collection backed by a mutable list, and exposing that mutable list is asking for trouble anyway).

2b. check "collection is Collection" first, and if it is, only add items up to "collection.length" This also allows you to pre-grow the destination list first. It's a pattern we should be using in more places (IMO). Like 2a this won't catch all possible errors, but guards against the identity case and is usually more efficient if you pre-grow the array to the desired size.

[floitschG]

If I'm not wrong this is fixed now (Iterators keep track of the List.length now).

---

Set owner to @lrhn.
Added Fixed label.

[lrhn]

We have probably missed some existing iterators that won't detect the modification, but that would be a separate bug.

List iteration should err if the list's length changes during iteration.
Set iteration should err if the set changes during iteration.
Map iteration should err if the map's key-set changes during iteration.
Queue iteration should err if the queue's start or end moves during iteration (i.e., any change).

It hasn't been implemented everywhere yet, though. I hope to spend some time on it next week.