Abstract: A nice puzzle to brighten your day - how can we make the Iterator think that the List has not been changed?
Welcome to the 283rd edition of The Java(tm) Specialists' Newsletter, sent to you from the beautiful Island of Crete. We have had a rather odd summer. Warm weather, of course, but few tourists. Chania looks like it does in winter, just warmer. The beaches are void of organized sun umbrellas. Cretans, famous for their hospitality, are cautious of outsiders. But this too will pass.
I am speaking at the JVM Community Virtual Conference in Nigeria tomorrow (29th August) (more info here).
javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.
A few days ago, I tweeted a #Java puzzle, asking how we could let an iterator continue to work, even after its collection had changed.
Here is the puzzle code:
import java.util.*; public class ListSurprise { public static void main(String[] args) { // Make ListSurprise print 3.14159 System.setSecurityManager(new SecurityManager()); List<Integer> numbers = new ArrayList<>(); Collections.addAll(numbers, 3, 1, 4, 1, 5, 5, 9); Iterator<Integer> it = numbers.iterator(); System.out.print(it.next()); // 3 System.out.print('.'); System.out.print(it.next()); // 1 System.out.print(it.next()); // 4 System.out.print(it.next()); // 1 System.out.print(it.next()); // 5 doSomething(numbers); // should make the next output be 9 System.out.println(it.next()); if (!numbers.equals(List.of(3, 1, 4, 1, 5, 9))) throw new AssertionError(); } private static void doSomething(List<Integer> list) { // how??? } }
The modCount
field in AbstractList
helps to discover concurrent updates to a list. Whenever the
list is changed, the modCount
is also
incremented. When the Iterator
is created, it
makes a copy of the current modCount
. If this
changes during iteration, then the backing list must have
changed. However, if we remove an item with the iterator
itself, then the iterator's expectedModCount
is
also changed to match the list's modCount
.
The trick is thus to remove the element at index 5,
and to then change the list another 4294967295 times, thus
looping the int
back to the starting
point. My friend Olivier Croisier wrote about this trick
ten years ago. Here
is what it would look like:
private static void doSomething(List<Integer> list) { // Remove element at index 5 and modify list 4 billion times list.remove(5); for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) { ((ArrayList<Integer>) list).trimToSize(); } }
The trimToSize()
method increments the
modCount
even if it does not really change the
structure of the list. It is thus a fairly quicky way of
spinning the modCount
back to its original value.
Another interesting approach was with threads. The
list.set()
method does not increment
modCount
, since it does not change the structure
of the list. Furthermore, when we look
at System.out.println(it.next());
,
it is tempting to read from left to right. However, we all
know that it.next()
is executed first and then
the System.out.println()
. The second solution
spawns a thread that synchronizes on System.out
,
thus preventing the main thread from continuing until we have
removed the element at index 6.
I saw several solutions following similar approaches using
Thread.sleep()
. Here is mine, using Phaser and
a spin loop that monitors the main thread's state. Once it
is BLOCKED, we continue with removing the last element.
private static void doSomething(List<Integer> list) { // Set item 5 to 9; block main thread as we remove last item list.set(5, 9); Phaser phaser = new Phaser(2); Thread main = Thread.currentThread(); new Thread(() -> { synchronized (System.out) { phaser.arriveAndDeregister(); while(main.getState() != Thread.State.BLOCKED) Thread.onSpinWait(); list.remove(6); } }).start(); phaser.arriveAndAwaitAdvance(); }
The third approach was even more obscure. We take advantage
of type erasure to insert a magical object into the list.
When toString()
is called, which would be after
the call to it.next()
, but before the call to
System.out.println()
, we remove
this
, leaving behind the desired
list of Integer
objects.
private static void doSomething(List<Integer> list) { // Replace 5 with object that removes itself and returns "9" ((List)list).set(5, new Object() { public String toString() { list.remove(this); return "9"; } }); }
The first and third solutions would work even with a stricter security manager installed. The second might not, since it is possible to prevent thread construction.
Here is one more that is the simplest solution, but also one that I like the least:
private static void doSomething(List<Integer> list) { // Println 9 and exit System.out.println(9); System.exit(0); }
Deep reflection was not possible due to the security manager, although one of my respondents set up a policy file to allow that.
The lesson to learn from this is that the ConcurrentModificationException
is best-effort. It might happen if a collection is modified,
but we can also see other strange behaviour. We need to
eradicate this exception from our systems.
Kind regards from Crete
Heinz
We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)
We deliver relevant courses, by top Java developers to produce more resourceful and efficient programmers within their organisations.