Enhanced for loop and ConcurrentModificationException

A Java blog i read has this entry, asking why Java behaves differently on for-each loop and a regular list loop. Here is an example:

Suppose we have an ArrayList initialized:

 1     List<String> t = new ArrayList<String>();
2 t.add("Elma");
3 t.add("Armut");
4 t.add("Kiraz");
if we make a loop as this, and remove one element from the list,

 1     for (String s : t) {
2 if(s.equals("Elma"))
3 t.remove(s);
4 }
it throws

Exception in thread "main" java.util.ConcurrentModificationException at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372) at java.util.AbstractList$Itr.next(AbstractList.java:343)

But, if we do it the pre-Java5 way, using iterators and removing it through an iterator, code works fine.

 1     for (Iterator<String> it = t.iterator(); it.hasNext();) {
2 if(it.next().equals("Elma"))
3 it.remove();
4 }
And, another way, if we do it without using the enhanced for loop, but accessing the list via indexes without using iterators:

 1     for (int i = 0; i < t.size(); i++) {
2 if(t.get(i).equals("Elma"))
3 t.remove(t.get(i));
4 }
this will also not throw that exception

So, why this is happening in the enhanced for loop? the answer is rather easy to guess, because we are using two different remove methods. First example is using the remove() method of the ArrayList, the second one is using the Iterator's remove() method. To understand what is going on, we should look at the code. Actually the exception itself is giving us the hint.

at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
at java.util.AbstractList$Itr.next(AbstractList.java:343)

First of all, the enhanced for each loop actually uses an Iterator, but we just don't see it. That is why they call it "synthetic sugar". As far as i know, during the compilation, iterator related code is embedded into the byte code. So, foreach code above is equivalent of this:

 1     for (Iterator<String> it = t.iterator(); it.hasNext();) {
2 String s = it.next();
3 if(s.equals("Elma"))
4 t.remove(s);
5 }

So, lets now go to the inner code of the ArrayList for Iterators (i am using JDK6, it has some differences from JDK5). ArrayList iterator() method uses the parent class AbstractList's iterator method. it instantiates a private Iterable class Itr.

  1     private class Itr implements Iterator<E> {
one of the member parameters of this class is called int expectedModCount, which is equivalent id modCount parameter of AbstractList. modCount is used for counting the modifications made in the list. So, when a Itr class is created, iterator will contain the current modification count parameter as the reference. If, there is a modification made in the list, such as addition, or removal, modCount will change. like ArrayList's add() method:

  1     public boolean add(E e) {
2 ensureCapacity(size + 1); // Increments modCount!!
3 elementData[size++] = e;
4 return true;
5 }

notice the comment, ensureCapacity method increments the modCount variable of the AbstractList.

In each next() method call of the iterator,

  1  final void checkForComodification() {
2 if (modCount != expectedModCount)
3 throw new ConcurrentModificationException();
4 }
metod is called, to check if there is a chance is made in the list. This throws the ConcurrentModificationException in case they do not match. This is because, Iterator's are staefull objects. They contain cursors which will be incremented by each next() call. iterator instance cannot follow the changes done by the List itself, like the list remove method, but if, the rmeove() method is called within the Iterator, since the state variables are changed accordingly it works fine. so this is the Itr's remove() method.

  1  public void remove() {
2 if (lastRet == -1)
3 throw new IllegalStateException();
4 checkForComodification();
5
6
try {
7 AbstractList.this.remove(lastRet);
8 if (lastRet < cursor)
9 cursor--;
10 lastRet = -1;
11 expectedModCount = modCount;
12 } catch (IndexOutOfBoundsException e) {
13 throw new ConcurrentModificationException();
14 }
15 }

13 comments:

Toolman said...

"synthetic sugar" - I think you mean "syntactic sugar".

http://en.wikipedia.org/wiki/Syntactic_sugar

Anonymous said...

Really, this behavior is a bug and needs to be fixed, regardless of its reason. Otherwise, programmers won't be able to trues the enhanced for loop. Just don't use it.

Anonymous said...

thanks a lot, it helps me much.

Robin said...

Great Explanation. Thanks

Anonymous said...

You're the man. It helped me also. Thanks.

Anonymous said...

Thanks helped me also - I hate my job.

Anonymous said...

the clearest and most complete explanation I have read about this so far. really thanks

Anonymous said...

fantastic , was writing the code for spring security & suddenly this exception started to come. Your blog then helped me to understand where exactly the problem was happening. Thanks

Melissa Brazil said...

fantastic, thank so much for this post

Imperfect Coder said...

but why there is a need to create one more additional class Itr . Can't we put all these iterator methods inside the abstractlist or arraylist directely ? Also i didn't get the way Itr class methods accesses the values in the list using "this" object. Could you please explain it ?

Tom said...

Many thanks! You saved my night's sleep ;)
It took me a while to find a real explanation, instead of a simple "copy this code" answer.

Anonymous said...

This is really very helpful for those who failed to understand ConcurrentModificationException and to know how to understand internals of Java API.

Romero Meireles said...

Very good explanation. Thank you.