Friday, August 20, 2010

Fixing a ConcurrentModificationException

Question:
The following code throws a ConcurrentModificationException. What additional code can you add between the <FIXME>...</FIXME> tags in order to prevent this exception from being thrown?
final List<String> list = new ArrayList<String>();
list.add("HELLO");
final Iterator<String> iter = list.iterator();
System.out.println(iter.next());
list.add("WORLD");
//<FIXME>

//</FIXME>
System.out.println(iter.next());
Solution:
In this example, a ConcurrentModificationException is thrown because the Iterator detects that the list over which it is iterating has been changed. If you look into the source code for these classes you will find that when an Iterator is created, it contains an int variable called expectedModCount which is initialised to the modCount of the backing list. Whenever the backing list is structurally modified (with an add or remove operation, for example) then the modCount is incremented. As a result, the iterator's expectedModCount no longer matches the list's modCount and the iterator throws a ConcurrentModificationException.

In order to prevent this exception from being thrown, we need to bring the expectedModCount of the iterator and the modCount of the list back in line with each other. Here are a couple of ways this can be done:

1. Reflection:
Reflection is the easiest way to change the internal counters of the iterator and list. In the fix below, I have set the expectedModCount of the iterator to the same value as the modCount of the list. The code no longer throws the ConcurrentModificationException.

final List<String> list = new ArrayList<String>();
list.add("HELLO");
final Iterator<String> iter = list.iterator();
System.out.println(iter.next());
list.add("WORLD");
//<FIXME>
/* Using Reflection */
try{
  //get the modCount of the List
  Class cls = Class.forName("java.util.AbstractList");
  Field f = cls.getDeclaredField("modCount");
  f.setAccessible(true);
  int modCount = f.getInt(list);

  //change the expectedModCount of the iterator
  //to match the modCount of the list
  cls = iter.getClass();
  f = cls.getDeclaredField("expectedModCount");
  f.setAccessible(true);
  f.setInt(iter, modCount);
}
catch(ClassNotFoundException e){
  e.printStackTrace();
}
catch(NoSuchFieldException e){
  e.printStackTrace();
}
catch(IllegalAccessException e){
  e.printStackTrace();
}
//</FIXME>
System.out.println(iter.next());
2. Integer Overflow:
Another approach is to keep modifying the list until the integer modCount overflows and reaches the same value as expectedModCount. At the moment, modCount=2 and expectedModCount=1. In the fix below, I repeatedly change the list (by calling trimToSize), forcing modCount to overflow and reach expectedModCount. This code took 38s to run on my machine.
final List<String> list = new ArrayList<String>();
list.add("HELLO");
final Iterator<String> iter = list.iterator();
System.out.println(iter.next());
list.add("WORLD");
//<FIXME>
for(int i = Integer.MIN_VALUE ; i < Integer.MAX_VALUE ; i++){
  ((ArrayList)list).trimToSize();
}
//</FIXME>
System.out.println(iter.next());

No comments:

Post a Comment