<p>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.</p>
<p>What approaches do languages or language implementations take, to prevent bugs caused by mutating collections while iterating over them?</p>

<iterators><mutability>
What approaches are there to prevent modifying a collection while iterating over it?
CC BY-SA 4.0
2023-07-27T21:58:29.957Z
Would "implicitly make a shallow copy" qualify as what you have in mind? Is it worth mentioning?
Karl Knechtel
CC BY-SA 4.0
2023-07-27T22:01:27.993Z
@KarlKnechtel I think that's a fine example to mention in an answer, particularly if there are any existing language implementations which do this.
kaya3
CC BY-SA 4.0
2023-07-27T22:20:05.797Z
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.
Karl Knechtel
CC BY-SA 4.0
2023-07-28T12:04:22.463Z
Functional languages solve this problem naturally, as function inputs aren't modifiable.
Toby Speight
CC BY-SA 4.0
2023-07-28T12:14:43.310Z
@TobySpeight Sure, though I'd rather say that this problem doesn't *exist* in functional languages which don't have mutable collections.
kaya3
CC BY-SA 4.0
2023-07-28T12:59:12.460Z
@KarlKnechtel, look at how the C++ [erase-remove idiom](https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom) handles that - we don't invalidate the iterators until the selection phase is complete.
Toby Speight
<h2>Versioning for mutable objects</h2>
<p>Java collections are expected to throw a <code>ConcurrentModificationException</code> when this is detected at runtime. To detect it, the collection object has a &quot;version number&quot; field which is incremented each time an unsafe modification occurs, and the iterator object has its own &quot;version number&quot; field holding the collection's &quot;version number&quot; 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. (<a href="https://github.com/openjdk/jdk/blob/c55d29ff119598a410e714ef36f47fb6626a1a7a/src/java.base/share/classes/java/util/ArrayList.java#L653" rel="noreferrer">Source link</a>)</p>
<h2>Object ownership policies</h2>
<p>Rust's borrow checker prevents this at compile-time. To mutate a collection, you must either have sole ownership of it or a <code>&amp;mut</code> reference to it; and to iterate over it, you must either move out of it or have a shared <code>&amp;</code> 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.</p>

CC BY-SA 4.0
2023-07-27T21:20:56.910Z
2023-07-27T21:49:02.803Z
2023-07-27T21:49:02.803Z
kaya3
<h2>Copying collections on iteration to sidestep the issue entirely</h2>
<p>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.</p>
<p>Bonus is you can do things like this:</p>
<pre><code>for k in collection:
    if k.property:
        collection.remove(k)
</code></pre>
<p>Which would require a secondary array and some bookkeeping if collection was not copied.</p>
<p>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.</p>
<p>Overall this is a good approach for beginner focused languages where performance isn't the primary concern.</p>

CC BY-SA 4.0
2023-07-28T04:46:36.380Z
2023-07-28T04:46:36.380Z
mousetail 'he-him'
CC BY-SA 4.0
2023-07-28T06:44:12.363Z
How exactly is this different from André L F S Bacci's answer?
Karl Knechtel
CC BY-SA 4.0
2023-07-28T06:46:19.377Z
@KarlKnechtel I explained it in more detail
mousetail 'he-him'
<h2>Specific iterator</h2>
<p>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 <code>(data, error)</code>, so the programmers may have a hint that is possible, even expected to occur.</p>
<h2>Snapshot collections and iterators</h2>
<p>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.</p>
<h2>Combining both</h2>
<p>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.</p>
<p>This will force any enumerating call site to only ask for a <code>GetStableEnumerator()</code>, implemented in a <code>StableEnumerator</code> 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...</p>
<p>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.</p>
<p>For this, I will argue that collections should only expose an <code>StableEnumeration</code> or <code>MutatingEnumeration</code> interface as appropriate, and the language should generate a compiler warning when trying to iterate over <code>MutatingEnumeration</code>.</p>
<p>On source level, the compiler only implicit enumerates over <code>StableEnumeration</code> collections, and the programmer must explicitly ask for a <code>MutatingEnumeration</code> in other cases. If <code>StableEnumeration</code> is implicitly convertible and/or implements <code>MutatingEnumeration</code>, it is possible to express strict stable or possible mutating failing enumeration without additional keywords.</p>
<pre class="lang-cs prettyprint-override"><code>foreach ( var item in collection )
{
    // collection dessugars to
    // ((StableEnumeration)collection).GetStableEnumeration()
}

foreach ( var item in collection.GetMutatingEnumeration() )
{
    // item is Result&lt;T,E&gt;
    // Never fails on stable or fixed collections
    // May generate error in mutating collections
}
</code></pre>

CC BY-SA 4.0
2023-07-27T23:14:06.850Z
2023-07-28T16:00:00.830Z
2023-07-28T16:00:00.830Z
André L F S Bacci
CC BY-SA 4.0
2023-07-28T00:43:53.137Z
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.
Karl Knechtel
CC BY-SA 4.0
2023-07-28T11:01:56.753Z
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.
kaya3
CC BY-SA 4.0
2023-07-28T11:04:02.327Z
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](https://langdev.stackexchange.com/q/15/89). That said, if there is any example of a language which does as you describe, please reference.
kaya3
<h2>Locking</h2>
<p>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.</p>
<p>Keep in mind that this globally slows down all collection mutation operations, whether or not they have anything to do with iteration.</p>
<h2>Static analysis</h2>
<p>Reject, at compile time, code that could modify the collection <em>within</em> the loop, including calls to functions that could modify the collection, including as a side effect.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-07-27T21:41:11.503Z
2023-07-27T22:09:00.533Z
2023-07-27T22:09:00.533Z
Karl Knechtel
CC BY-SA 4.0
2023-07-27T21:44:00.877Z
"this needs to be applied conservatively, which may annoy users" this is probably the thing I'm most annoyed at with Rust
Seggan
CC BY-SA 4.0
2023-07-27T21:47:11.957Z
@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.
Karl Knechtel
CC BY-SA 4.0
2023-07-27T21:50:33.247Z
I was talking about the static analysis section
Seggan
CC BY-SA 4.0
2023-07-27T21:55:00.970Z
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.
kaya3
CC BY-SA 4.0
2023-07-27T22:00:32.293Z
Regarding the locking flag, I think this needs to be a counter (aka a [reentrant lock](https://en.wikipedia.org/wiki/Reentrant_mutex)) 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.
kaya3
CC BY-SA 4.0
2023-07-27T22:00:47.657Z
One example might be: scan the loop code for uses of the container's mutation API; scan (transitively) any called code for uses of the container's *type*'s mutation API (in case that code obtains a reference to the original container somehow). I had thought that the nested-loop problem could be avoided by only adding the setup/teardown logic to the outermost loop, but that wouldn't work with calls to other functions.
Karl Knechtel
CC BY-SA 4.0
2023-07-27T22:38:18.183Z
The question seeks approaches taken by languages or language implementations, so it would be good to identify the languages that use these approaches. At the moment they're just unattested concepts.
Michael Homer
CC BY-SA 4.0
2023-07-27T22:40:55.690Z
Well, yes; but insofar as it does so, I think it's contrary to the spirit of [prior meta discussion](https://langdev.meta.stackexchange.com/questions/409) (which, incidentally, previously featured OP's answer and my agreement that I added right before finding this question).
Karl Knechtel
CC BY-SA 4.0
2023-07-28T00:44:37.270Z
Answers, ideally, would still provide some substantiation for what they proposed. See also [this currently-featured meta post](https://langdev.meta.stackexchange.com/q/543/133) on the subject that you may also like to comment on.
Michael Homer
CC BY-SA 4.0
2023-07-28T00:46:19.997Z
@MichaelHomer I think I'll want to start a separate meta discussion about the general idea of theoretical/unproven techniques; I don't want to prolong this comment section (feel free to clean it up now). But briefly re your link, I agree with user23013's first heading there.
Karl Knechtel
<p><a href="https://stackoverflow.com/questions/23612885/why-does-qt-foreach-create-a-copy-of-the-container">Qt foreach loop</a> copies the collection being iterated:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>Such copying is already mentioned in some answers as a possible solution, but I would like to bring Qt into context.</p>

CC BY-SA 4.0
2023-07-28T17:07:08.863Z
2023-07-28T17:07:08.863Z
Audrius Meškauskas
CC BY-SA 4.0
2023-07-29T14:28:55.430Z
Probably worth mentioning that Qt containers are copy-on-write, which greatly decreases the overhead for the common case.
Toby Speight
<p>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 <a href="https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/CopyOnWriteArrayList.html" rel="nofollow noreferrer"><code>CopyOnWriteArrayList</code></a>.  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.</p>

CC BY-SA 4.0
2023-07-28T20:59:13.880Z
2023-07-28T20:59:13.880Z
occipita
CC BY-SA 4.0
2023-07-28T21:30:56.807Z
[mousetail's answer](https://langdev.stackexchange.com/a/2603/89) already mentions copy-on-write.
kaya3
<p>TL;DR: Some of the problems are irregularities of <em>arrays</em>, 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.</p>
<p>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.</p>
<p>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.</p>
<p>So I recommend against doing this, because it is against the spirit of some types of the collections.</p>
<p><strong>Things said,</strong> 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. <strong>So there might be something could be done in the language design.</strong> But a question is, do you want to prevent this for every type of collection, just arrays, or a specific type called a &quot;collection&quot; to be used for everything for these programmers?</p>
<h2>Arrays</h2>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<h2>A collection for everything</h2>
<p>A good example is PHP, where you could skip indexes in an &quot;array&quot;. It's easier to unset the index in a loop, so the array would have some holes, and renumber the elements using <code>array_values</code> only after the loop, than to think of how to keep the indexes continuous all the way. Actually <em>there isn't a builtin to remove in the middle like a normal array</em>, so the programmer could not make mistakes this way.</p>
<p>(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.)</p>
<h2>Every type of collection</h2>
<p>Most commonly used data structures other than arrays, linked lists, hash tables, has a <a href="https://en.wikipedia.org/wiki/Persistent_data_structure" rel="nofollow noreferrer">persistent version</a> 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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-07-28T01:37:26.430Z
2023-07-28T12:54:21.060Z
2023-07-28T12:54:21.060Z
user23013
CC BY-SA 4.0
2023-07-28T06:43:24.023Z
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)?
Karl Knechtel
CC BY-SA 4.0
2023-07-28T07:12:14.620Z
@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".
user23013
CC BY-SA 4.0
2023-07-28T07:35:38.563Z
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.
user23013
CC BY-SA 4.0
2023-07-28T10:56:21.790Z
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?
kaya3
CC BY-SA 4.0
2023-07-28T11:59:20.753Z
@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.
user23013
CC BY-SA 4.0
2023-07-28T12:09:05.407Z
@kaya3-supportthestrike In case it's not clear, I'm referring to structures like the C++ ordered std::set and std::map. If you are using a language with unordered sets and maps, it might be hash tables, which you iterate over it like arrays, and all the sets and maps part doesn't apply.
user23013
CC BY-SA 4.0
2023-07-28T12:09:29.937Z
Sets and maps are typically implemented using hashtables; see the built-in `set` and `dict` data structures in CPython, the `Set` and `Map` classes in Javascript implementations including V8, and so on. I read past the comma of course, and didn't see anything which made your claim less questionable.
kaya3
CC BY-SA 4.0
2023-07-28T12:11:45.820Z
Yes, that is absolutely not clear from your answer which doesn't mention C++, and also I don't know why you would choose to focus on C++. Also yes, hashtables are iterated like arrays (except for the fact that not all of their entries represent actual elements in the collection), but this seems to contradict your other claim that "Hash tables are not supposed to be iterated".
kaya3
CC BY-SA 4.0
2023-07-28T12:20:56.647Z
@kaya3-supportthestrike Changed to ordered sets and maps to make it clearer. Hash tables as a data structure are not iterated. Hash tables as a class in the library may support iterating, but in that case the hash table part is not used, and is not relevant to the discussion.
user23013
# What approaches are there to prevent modifying a collection while iterating over it?
Posted by: username_0 on 2023-07-27
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?
**Tags:** iterators mutability
> **Comments:**
> **username_1**: Would "implicitly make a shallow copy" qualify as what you have in mind? Is it worth mentioning?  
> **username_0**: @KarlKnechtel I think that's a fine example to mention in an answer, particularly if there are any existing language implementations which do this.  
> **username_1**: 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.  
> **username_2**: Functional languages solve this problem naturally, as function inputs aren't modifiable.  
> **username_0**: @TobySpeight Sure, though I'd rather say that this problem doesn't *exist* in functional languages which don't have mutable collections.  
> **username_2**: @KarlKnechtel, look at how the C++ [erase-remove idiom](https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom) handles that - we don't invalidate the iterators until the selection phase is complete.  
---
## 7 answers
### Answer by username_0 on 2023-07-27. Score: 18
## 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](https://github.com/openjdk/jdk/blob/c55d29ff119598a410e714ef36f47fb6626a1a7a/src/java.base/share/classes/java/util/ArrayList.java#L653))

## 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.
---
### Answer by username_3 on 2023-07-28. Score: 5
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.
> **Comments:**
> **username_1** (2023-07-28): How exactly is this different from André L F S Bacci's answer?  
> **username_3** (2023-07-28): @KarlKnechtel I explained it in more detail  
---
### Answer by username_4 on 2023-07-27. Score: 5
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
    // Never fails on stable or fixed collections
    // May generate error in mutating collections
}
> **Comments:**
> **username_1** (2023-07-28): 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.  
> **username_0** (2023-07-28): 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.  
> **username_0** (2023-07-28): 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](https://langdev.stackexchange.com/q/15/89). That said, if there is any example of a language which does as you describe, please reference.  
---
### Answer by username_1 on 2023-07-27. Score: 5
## 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.
> **Comments:**
> **username_5** (2023-07-27): "this needs to be applied conservatively, which may annoy users" this is probably the thing I'm most annoyed at with Rust  
> **username_1** (2023-07-27): @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.  
> **username_5** (2023-07-27): I was talking about the static analysis section  
> **username_0** (2023-07-27): 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.  
> **username_0** (2023-07-27): Regarding the locking flag, I think this needs to be a counter (aka a [reentrant lock](https://en.wikipedia.org/wiki/Reentrant_mutex)) 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.  
> **username_1** (2023-07-27): One example might be: scan the loop code for uses of the container's mutation API; scan (transitively) any called code for uses of the container's *type*'s mutation API (in case that code obtains a reference to the original container somehow). I had thought that the nested-loop problem could be avoided by only adding the setup/teardown logic to the outermost loop, but that wouldn't work with calls to other functions.  
> **username_6** (2023-07-27): The question seeks approaches taken by languages or language implementations, so it would be good to identify the languages that use these approaches. At the moment they're just unattested concepts.  
> **username_1** (2023-07-27): Well, yes; but insofar as it does so, I think it's contrary to the spirit of [prior meta discussion](https://langdev.meta.stackexchange.com/questions/409) (which, incidentally, previously featured OP's answer and my agreement that I added right before finding this question).  
> **username_6** (2023-07-28): Answers, ideally, would still provide some substantiation for what they proposed. See also [this currently-featured meta post](https://langdev.meta.stackexchange.com/q/543/133) on the subject that you may also like to comment on.  
> **username_1** (2023-07-28): @MichaelHomer I think I'll want to start a separate meta discussion about the general idea of theoretical/unproven techniques; I don't want to prolong this comment section (feel free to clean it up now). But briefly re your link, I agree with user23013's first heading there.  
---
### Answer by username_9 on 2023-07-28. Score: 3
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](https://en.wikipedia.org/wiki/Persistent_data_structure) 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.
> **Comments:**
> **username_1** (2023-07-28): 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)?  
> **username_9** (2023-07-28): @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".  
> **username_9** (2023-07-28): 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.  
> **username_0** (2023-07-28): 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?  
> **username_9** (2023-07-28): @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.  
> **username_9** (2023-07-28): @kaya3-supportthestrike In case it's not clear, I'm referring to structures like the C++ ordered std::set and std::map. If you are using a language with unordered sets and maps, it might be hash tables, which you iterate over it like arrays, and all the sets and maps part doesn't apply.  
> **username_0** (2023-07-28): Sets and maps are typically implemented using hashtables; see the built-in `set` and `dict` data structures in CPython, the `Set` and `Map` classes in Javascript implementations including V8, and so on. I read past the comma of course, and didn't see anything which made your claim less questionable.  
> **username_0** (2023-07-28): Yes, that is absolutely not clear from your answer which doesn't mention C++, and also I don't know why you would choose to focus on C++. Also yes, hashtables are iterated like arrays (except for the fact that not all of their entries represent actual elements in the collection), but this seems to contradict your other claim that "Hash tables are not supposed to be iterated".  
> **username_9** (2023-07-28): @kaya3-supportthestrike Changed to ordered sets and maps to make it clearer. Hash tables as a data structure are not iterated. Hash tables as a class in the library may support iterating, but in that case the hash table part is not used, and is not relevant to the discussion.  
---
### Answer by username_7 on 2023-07-28. Score: 2
[Qt foreach loop](https://stackoverflow.com/questions/23612885/why-does-qt-foreach-create-a-copy-of-the-container) 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.
> **Comments:**
> **username_2** (2023-07-29): Probably worth mentioning that Qt containers are copy-on-write, which greatly decreases the overhead for the common case.  
---
### Answer by username_8 on 2023-07-28. Score: 1
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`](https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/CopyOnWriteArrayList.html). 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.
> **Comments:**
> **username_0** (2023-07-28): [mousetail's answer](https://langdev.stackexchange.com/a/2603/89) already mentions copy-on-write.  
---
