A frequent source of bugs in some languages, is to modify a mutable collection while iterating over it. Appending to a list while iterating over it can cause an infinite loop, while removing from it can cause elements to be skipped. Therefore, it is desirable to prevent this from happening.
What approaches do languages or language implementations take, to prevent bugs caused by mutating collections while iterating over them?
Java collections are expected to throw a ConcurrentModificationException when this is detected at runtime. To detect it, the collection object has a "version number" field which is incremented each time an unsafe modification occurs, and the iterator object has its own "version number" field holding the collection's "version number" from the time the iterator was created. On each iterated value, these numbers are compared, and the exception is thrown if they are not equal. (Source link)
Rust's borrow checker prevents this at compile-time. To mutate a collection, you must either have sole ownership of it or a &mut reference to it; and to iterate over it, you must either move out of it or have a shared & reference to it. The borrow checker ensures that a mutable reference cannot coexist with a shared reference, that you cannot mutate an owned value when any references to it exist, and that you cannot use a value after it has been moved.
Instead of preventing mutating a collection, one could just store a (shallow) copy of the collection in the iterator when you iterate. The copy can not be mutated since it's not exposed anywhere.
Bonus is you can do things like this:
for k in collection:
if k.property:
collection.remove(k)
Which would require a secondary array and some bookkeeping if collection was not copied.
Disadvantage is it would require a lot of time and memory to copy a large array. Only copying on write could optimize this a little so the performance cost applies at least only when you actually need the feature.
Overall this is a good approach for beginner focused languages where performance isn't the primary concern.
A simple approach is to have a counter stored in every mutable collection object that serves as a re-entrant lock for mutating operations. Have collection methods that can mutate the container raise a runtime error immediately if the counter value is non-zero. Have the counter increment when the loop is entered, and decrement when it is exited (including if an exception, the function returns or the loop is explicitly broken). Using a counter instead of a plain boolean flag allows for nested loops over the same collection, iteration by another function called within the loop, etc.
Keep in mind that this globally slows down all collection mutation operations, whether or not they have anything to do with iteration.
Reject, at compile time, code that could modify the collection within the loop, including calls to functions that could modify the collection, including as a side effect.
For program correctness, this needs to be applied conservatively, which may annoy users. The feasibility and precision of this approach will depend on how much compile-time information is available in the language about side effects.
Additionally, in a multi-threaded environment, synchronization will be necessary in order to ensure that other threads either do not have access to the collection, or cannot run during the loop.
In designing a new language, you could make your collections advertise that collection in particular may fail while iterating, with a specific enumerator that returns (data, error), so the programmers may have a hint that is possible, even expected to occur.
In some collections, it's cheap to offer a snapshot copy of the data, and so, it's cheap to offer a snapshoting iterator, so any further modification of collection is not observed after the iteration starts.
As for a way for a language to detect or prevent these classes of bugs, there is always the nuclear option: no mutating collection expose a mutating enumerator capacity.
This will force any enumerating call site to only ask for a GetStableEnumerator(), implemented in a StableEnumerator interface. So if the collection is stable, it can return itself. But if the collection is mutating, this method will try to generate a promise of stable iterating, by means of locking, snapshotting, versioning...
But this path is full of performance problems -- versioning or snapshotting a big collection is expensive -- or of deadlock problems -- one thread tries to stable iterate and modify the same collection at the same time. In other words, in the locking alternative the lock cannot be reentrant.
For this, I will argue that collections should only expose an StableEnumeration or MutatingEnumeration interface as appropriate, and the language should generate a compiler warning when trying to iterate over MutatingEnumeration.
On source level, the compiler only implicit enumerates over StableEnumeration collections, and the programmer must explicitly ask for a MutatingEnumeration in other cases. If StableEnumeration is implicitly convertible and/or implements MutatingEnumeration, it is possible to express strict stable or possible mutating failing enumeration without additional keywords.
foreach ( var item in collection )
{
// collection dessugars to
// ((StableEnumeration)collection).GetStableEnumeration()
}
foreach ( var item in collection.GetMutatingEnumeration() )
{
// item is Result<T,E>
// Never fails on stable or fixed collections
// May generate error in mutating collections
}
ConcurrentModificationException is unchecked in Java, because it's expected that no code would intentionally cause it to be thrown.
$\endgroup$
TL;DR: Some of the problems are irregularities of arrays, not applicable to other collections. While you could do something for arrays, better consider giving the programmer the alternative collections if what they want is not exactly arrays.
The problem with this is, sometimes it is useful to modify a collection while iterating over it. For example, priority queues are always supposed to be read while modifying, and are difficult to use without modifying. They are popped, not iterated. But programmers may opt to use an ordered set or an ordered map for a priority queue, if the features of sets or maps are also required.
Actually, ordered sets and maps are not very useful if you don't intermix reads and writes. In that case, you just append everything into an array, then sort and deduplicate before reading. If it could be read while modifying, it is not very reasonable to specifically forbid reading using iterators.
So I recommend against doing this, because it is against the spirit of some types of the collections.
Things said, some programmers don't know much about the details, and just want to work with collections in any way they want and expect it to work. So there might be something could be done in the language design. But a question is, do you want to prevent this for every type of collection, just arrays, or a specific type called a "collection" to be used for everything for these programmers?
If it's only for advanced programmers, actually you could give a straight warning in any situation that something is inserted or removed in the middle of an array, because it is not the right data structure for this. Most other data structures don't skip elements if something is removed in the middle. So if you are supporting this operation anyway, and solving this exact problem of skipping elements, you do it specifically to arrays.
A possible option to keep the iterator at the correct position, is to record the reference to every iterator in the array type, and update each of them when the array is modified, as the number of iterators are usually small.
Another option is to also attach a linked list with the array, and iterate using the linked list. It works best if the array elements are already references and the real data are allocated elsewhere.
If the array works in a way that removed elements might be replaced by another element at the end, like using it to allocate memory, it might be helpful to do both, to move elements in the array but not in the linked list. This might be useful if arrays are the underlying structure of another type of collection, but might not be applicable to just arrays because it changes the iterating order.
If you really want to freeze the array when an iterator is active, it still doesn't do that much damage, if it is specific to arrays and not other collections. To do this, you could choose between unfreezing the array in the iterator's destructor, and disabling the iterator after modification of the array.
For appending, if you want it to not iterate from the new elements, you may initialize the iterator using a subrange covering all the current elements of an array. But it might be equally confusing, as some programmers may expect the opposite to happen.
Some languages may also invalidate iterators and pointers on array resizing. I think this is a problem of its own. If you couldn't change it, you may have to freeze iterators. But it's better to be solved in other ways.
A good example is PHP, where you could skip indexes in an "array". It's easier to unset the index in a loop, so the array would have some holes, and renumber the elements using array_values only after the loop, than to think of how to keep the indexes continuous all the way. Actually there isn't a builtin to remove in the middle like a normal array, so the programmer could not make mistakes this way.
(Arrays are also automatically shallow-copied, making this not changing much. But the idea would work in a language that arrays are not automatically copied.)
Most commonly used data structures other than arrays, linked lists, hash tables, has a persistent version that could be shallow-copied with no overhead. So you may make a shallow copy of them automatically if that is what you want, and only deal with arrays and linked lists as special cases.
Hash tables as a data structure itself are not supposed to be iterated, and are only iterated using a built-in auxiliary data structure if it is supported, so you could solve the problem like that auxiliary data structure. It may not have the problems if the auxiliary data structure is not exactly arrays, so it makes sense to simulate the behavior as it is not even if it is.
Qt foreach loop copies the collection being iterated:
Qt automatically takes a copy of the container when it enters a foreach loop. If you modify the container as you are iterating, that won't affect the loop. If you do not modify the container, the copy still takes place, but thanks to implicit sharing copying a container is very fast. Since foreach creates a copy of the container, using a non-const reference for the variable does not allow you to modify the original container. It only affects the copy, which is probably not what you want.
Such copying is already mentioned in some answers as a possible solution, but I would like to bring Qt into context.
An alternative to copying the data out of the collection before iteration is to create a new copy of the data on every modification. Java, for example, provides versions of its collections that do this, including CopyOnWriteArrayList. This is also done implicitly in most functional languages, because all or most values in such languages are treated as immutable, so to modify a collection often involves copying it, or for simple cases (e.g. prepending to a linked list) embedding a reference to the old collection in the new one and leaving the old one unchanged.
