The old mutate the collection while iterating trick

[som-snytt]

reproduction steps

• using Scala?

scala 2.13.2> val xs = collection.mutable.ArrayBuffer(1,2,3)
val xs: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(1, 2, 3)

scala 2.13.2> val it = xs.iterator
val it: Iterator[Int] = <iterator>

scala 2.13.2> it.hasNext
val res0: Boolean = true

scala 2.13.2> xs.clear()

scala 2.13.2> it.hasNext
val res2: Boolean = true

scala 2.13.2> it.next()
val res3: Int = 0

scala 2.13.2> it.to(List)
val res4: List[Int] = List(null, null)

scala 2.13.2> xs.size
val res5: Int = 0

problem

Documentation should tell me not to do that.

It would be nice if the iterator told me there was a problem. It's just using indexes from the view.

See #8154

[joroKr21]

TIL some countries limit the number of precautionary statements on GHS labels and others don't. The EU where I live mandates a maximum of 6. I propose "mutating hazard".

[SethTisue]

as I said on Gitter, when someone mutates a collection on which there is a live iterator, I doubt there we can offer any better guarantee in general other than shrug and say "sorry, undefined behavior"

that said, certainly

1. this should be documented somewhere, if it isn't already
2. there's nothing wrong with improving behaviors in particular scenarios (e.g. to throw an exception rather than silently returning null) if it can be done without too great an impact to performance or maintainability

[LPTK]

@SethTisue do you think it would be acceptable, performance-wise, to have a private var version: Int field in mutable collections, which is incremented every time a mutable operation is done, and which is captured by iterators (so iterators can check whether the collection has changed under their feet when doing hasNext/next).

[ritschwumm]

@LPTK this field would probably have to be volatile to ensure the mechanism works accross threads... all in all, this (to me) sounds like another reason to eschew mutable collections altogether, except in very few and tightly controlled places.

[Jasper-M]

The version field thing seems to be how the java.util collections implement fail-fast iterators.

this field would probably have to be volatile to ensure the mechanism works accross threads

I don't think mutable collections offer any synchronization guarantees in general anyway.

[ritschwumm]

well, they don't offer any guarantees concerning mutation while using a live iterator either, and still people seem to be surprised when that goes wrong :)

[LPTK]

@ritschwumm IMHO there's a huge difference between behaving in a buggy way in single-threaded contexts, and behaving in a buggy way in multi-threaded contexts. It's widely accepted that the latter is expected of a non-thread-safe API; but the former just seems to reflect a bad API/implementation design.

I think Java got at least that part right: basic Java collections are not thread-safe, but they do make sure you're not misusing them in single-threaded code (if they do it, I guess it shows it's not prohibitive in terms of performance).

[SethTisue]

perhaps my initial reaction was too pessimistic/dismissive?

do you think it would be acceptable, performance-wise

@LPTK if the Java collections do that then that's good evidence it would be okay for us performance wise

do the checks they do seem simple/maintainable? or does it get hairy? if not, that would be also be evidence this could be feasible for us

[ritschwumm]

@LPTK yeah, agreed - with multi-threading, people tend to know it won't work well with mutable collections in the general case.

i wonder why, though - to me, an iterator is not so much different than a suspended thread. if you ignore memory model issues like cpu caches, the code ran between one call to an iterator and the next is conceptually the same as running something in a separate thread. if that mucks with the state the iterator relies on, you are in trouble...

the more interesting question is - is there a good way to integrate a version check like this in the current colllections implementation? ideally, it would be easier for someone working on the implementation of a mutable collection to have the version field updated for each and every mutation than not doing it. the same goes for actually checking that field in an iterator created on that collection.

on a side note: personally, i'd prefer collections not doing any of this at all over collections where some mutations are checked, and others are not, and there's no way to know which ones are. i already see future me having to refactor some code where a junior relied on version mismatch exceptions to be thrown in very specific cases...

[NthPortal]

I believe (some of?) the Java collections detect concurrent modification across multiple threads as well - see https://docs.oracle.com/javase/8/docs/api/java/util/ConcurrentModificationException.html

[retronym]

Some more verbiage from Java's documentation for ArrayList

The iterators returned by this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

[NthPortal]

the only simple way to apply this "in bulk" to most of the collections without lots of code duplication and manual work is to add a MutationTracking trait with a mutationCount field (or similar), a method to increment that count that can be dropped in at the beginning/end of every mutating method, and an inner class/trait CheckedIterator that checks for a change to the mutation count in its methods, and throws an exception if that is found. sadly, we cannot add MutationTracking to public collection implementations, as that would require it to be public as well, thus breaking bincompat.

Perhaps we could have a MutationTracker that is a field/member of collections though (and is private[collection], thus not breaking bincompat)?