15
$\begingroup$

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?

$\endgroup$
6
  • 4
    $\begingroup$ Would "implicitly make a shallow copy" qualify as what you have in mind? Is it worth mentioning? $\endgroup$ Jul 27, 2023 at 21:58
  • $\begingroup$ @KarlKnechtel I think that's a fine example to mention in an answer, particularly if there are any existing language implementations which do this. $\endgroup$
    – kaya3
    Jul 27, 2023 at 22:01
  • $\begingroup$ I started writing it up, but I don't think it makes sense. When programmers explicitly copy, it only actually addresses the problem for certain algorithms. For example, if the goal of the loop is to remove many elements from the collection, there isn't a clear way to correlate elements between the iterated-copy and the mutated-original after the first mutation, nor clear semantics for what to do if the mutated-original no longer contains the element found by the iteration. $\endgroup$ Jul 27, 2023 at 22:20
  • 1
    $\begingroup$ Functional languages solve this problem naturally, as function inputs aren't modifiable. $\endgroup$ Jul 28, 2023 at 12:04
  • 1
    $\begingroup$ @TobySpeight Sure, though I'd rather say that this problem doesn't exist in functional languages which don't have mutable collections. $\endgroup$
    – kaya3
    Jul 28, 2023 at 12:14

7 Answers 7

18
$\begingroup$

Versioning for mutable objects

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)

Object ownership policies

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.

$\endgroup$
0
5
$\begingroup$

Locking

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.

Static analysis

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.

$\endgroup$
10
  • $\begingroup$ "this needs to be applied conservatively, which may annoy users" this is probably the thing I'm most annoyed at with Rust $\endgroup$
    – Seggan
    Jul 27, 2023 at 21:44
  • $\begingroup$ @Seggan I'm not entirely clear on whether Rust's implementation is an example of what I described. I know that the locking scheme I describe is fundamentally different from what Java does; I propose that the problem gets detected at runtime by the collection, rather than by the iterator. $\endgroup$ Jul 27, 2023 at 21:47
  • $\begingroup$ I was talking about the static analysis section $\endgroup$
    – Seggan
    Jul 27, 2023 at 21:50
  • 1
    $\begingroup$ Rust's borrow checker is an example of static analysis, and it is conservative in some regards. I think you have something more specific in mind, but the answer would be improved by describing how you intend to (conservatively) determine which code might mutate the collection; or alternatively, by referencing a language which does it the way you're thinking of. Anyway, I upvoted regardless. $\endgroup$
    – kaya3
    Jul 27, 2023 at 21:55
  • $\begingroup$ Regarding the locking flag, I think this needs to be a counter (aka a reentrant lock) to support nested loops over the same collection. It also has some implications for code which handles iterators manually, and it would be worth saying something about the teardown code when the loop body throws or returns. $\endgroup$
    – kaya3
    Jul 27, 2023 at 22:00
5
$\begingroup$

Copying collections on iteration to sidestep the issue entirely

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.

$\endgroup$
2
  • $\begingroup$ How exactly is this different from André L F S Bacci's answer? $\endgroup$ Jul 28, 2023 at 6:44
  • 1
    $\begingroup$ @KarlKnechtel I explained it in more detail $\endgroup$
    – mousetail
    Jul 28, 2023 at 6:46
5
$\begingroup$

Specific iterator

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.

Snapshot collections and iterators

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.

Combining both

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
}
$\endgroup$
3
  • $\begingroup$ I mentioned the snapshot thing in the comments (I forgot that terminology). It works for non-mutating algorithms where the underlying collection could get mutated by another thread, but for mutating algorithms more care is needed - it doesn't just automatically solve the problem. $\endgroup$ Jul 28, 2023 at 0:43
  • $\begingroup$ In regards to your first point, normally it only makes sense to report errors like this and allow the programmer to handle them, if the error isn't one that signals the code is incorrect. If the programmer intends to be able to modify the collection while iterating over it, then they don't want the iterator to fail with an error, and inversely if they don't intend for this to be possible then the error cannot be (locally) recovered from. Hence why ConcurrentModificationException is unchecked in Java, because it's expected that no code would intentionally cause it to be thrown. $\endgroup$
    – kaya3
    Jul 28, 2023 at 11:01
  • $\begingroup$ Also, I'm more interested in the way that the language detects or prevents this from happening, not so much the way it gets reported to the programmer when it is detected ─ there is a lengthy discussion of the latter already here. That said, if there is any example of a language which does as you describe, please reference. $\endgroup$
    – kaya3
    Jul 28, 2023 at 11:04
3
$\begingroup$

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?

Arrays

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 collection for everything

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.)

Every type of collection

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.

$\endgroup$
9
  • $\begingroup$ If you want to make this sort of frame challenge, it would be useful to explain more clearly: what approaches are there to ensuring that the code behaves as expected when modifying a collection while iterating over it (rather than, say, corrupting the internal structure of a mapping, or skipping some elements of a sequence)? $\endgroup$ Jul 28, 2023 at 6:43
  • $\begingroup$ @KarlKnechtel Most of my answer below the first header are about the different options to keep the iterator in the right place. The freezing option is also included. The frame challenge is required because the situation about arrays and other collections are different, and I can't provide an answer for just "collections". $\endgroup$
    – user23013
    Jul 28, 2023 at 7:12
  • $\begingroup$ I'm hesitant to call PHP a good example. But comments would otherwise assume I'm not advising to learn from it for solving this exact problem. It's actually basically a map from strings, just called an array. $\endgroup$
    – user23013
    Jul 28, 2023 at 7:35
  • $\begingroup$ A couple of questionable claims here: "Actually, sets and maps are not very useful if you don't intermix reads and writes." Your argument here is not very convincing, because sets and maps still have O(1) lookup operations, compared to sorted arrays which are O(log n), and building a set or map in the first place is O(n) compared to O(n log n) for a sorted array. I fairly frequently build sets or maps and then query them without mixing mutations and queries, because of their performance characteristics. "Hash tables are not supposed to be iterated" ─ whyever not? $\endgroup$
    – kaya3
    Jul 28, 2023 at 10:56
  • $\begingroup$ @kaya3-supportthestrike For sets and maps, what language are you referring to? I think most would claim red-black trees if it is said somewhere, which is O(log n) per operation. But it's difficult to look up the information. For hash tables, just read pass the comma. $\endgroup$
    – user23013
    Jul 28, 2023 at 11:59
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Probably worth mentioning that Qt containers are copy-on-write, which greatly decreases the overhead for the common case. $\endgroup$ Jul 29, 2023 at 14:28
1
$\begingroup$

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.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .