JDK-4902078 : concurrent modification not detected on 2nd to last iteration
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 1.3.0,1.4.2
  • Priority: P4
  • Status: Closed
  • Resolution: Won't Fix
  • OS: windows_nt,windows_2000
  • CPU: x86
  • Submitted: 2003-08-06
  • Updated: 2021-03-03
  • Resolved: 2004-02-27
Related Reports
Duplicate :  
Duplicate :  
Relates :  
Relates :  
Description

Name: gm110360			Date: 08/06/2003


FULL PRODUCT VERSION :
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.1_01-b01)
Java HotSpot(TM) Client VM (build 1.4.1_01-b01, mixed mode)

FULL OPERATING SYSTEM VERSION :
Microsoft Windows 2000 [Version 5.00.2195]

A DESCRIPTION OF THE PROBLEM :
Concurrent modification exception is not thrown on the
second to last iteration of an iterator.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
1. Compile and run the small test program -- it should
   die with concurrent modification exception.  If the
   item removed from the list is anything but "c" it works.

EXPECTED VERSUS ACTUAL BEHAVIOR :
Expected a concurrent modification exception in this case:
Iterator iter = list.iterator();
while(iter.next()) {
   Object o = iter.next();
   if(2nd to last item in list) {
      list.remove(o); // <-- expected exception here!
   }
}

ERROR MESSAGES/STACK TRACES THAT OCCUR :
the problem is the lack of an exception

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.Iterator;
import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

/**
 * @author Steven R Brandt
 */
public class CopyIterator {
    public void remove() {
        throw new Error("cannot remove from CopyIterator");
    }

    public static void main(String[] args) throws Exception {
        list.add(new ToyListener("a"));
        list.add(new ToyListener("b"));
        list.add(new ToyListener("c"));
        list.add(new ToyListener("d"));
        Iterator iter = list.iterator();
        while(iter.hasNext()) {
            ToyListener toy = (ToyListener)iter.next();
            toy.event();
            System.out.println(toy);
        }
    }
    static List list = new Vector();
    public static class ToyListener {
        String name;
        ToyListener(String name) {
            this.name = name;
        }
        public void event() {
            // this should cause a concurrent modification exception
            // if "a", "b", or "d" are used it will
            if(name.equals("c")) {
                list.remove(this);
            }
        }
        public String toString() {
            return "Toy: "+name;
        }
    }
}
---------- END SOURCE ----------

CUSTOMER WORKAROUND :
write your own iterator
(Incident Review ID: 180003) 
======================================================================

Comments
PUBLIC COMMENTS ...
10-06-2004

EVALUATION The reporter is correct. Techically, this is not a spec violation, as ConcurrentModificationException is specified to be thrown on a "best-effort" basis. That said, the observed behavior is clearly suboptimal, and can be fixed with little impact on performance. ###@###.### 2004-02-08 If a collection is modified during the process of iteration, arbitrary behavior is permitted to occur: The spec for java.util.Iteator.remove says "The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method." Most of our collections provide "fail fast iterators": they promise to make a best effort to detect comodification during iteration, and to deliver a ConcurrentModificationException if such activity is detected. This allows the programmer to diagnose and fix the bug. This bug report says, in essence, that our "best efforts" at detecting comodification in AbstractList and the concrete list implementations that inherit from it aren't good enough. When the Collections Framework was added to the platform it was deemed too expensive to check for comodification once rather than twice per iteration; the check was made on Iterator.next rather than Iterator.hasNext. Expert reviewers thought this was sufficient. They were unaware that it fails to detect one important case: if an element is removed from the list immediately prior to the final call to hasNext in an iteration, the call returns false and the iteration terminates, silently ignoring the last element on the list. The following example illustrates this behavior: import java.util.*; public class Decontaminate { public static void main(String[] args) { List stuff = new ArrayList(Arrays.asList(new String[] { "milk", "cookies", "plutonium", "plutonium"})); System.out.println(stuff); decontaminate(stuff); System.out.println(stuff); } // broken!!! private static void decontaminate(List items) { for (Iterator it = items.iterator(); it.hasNext(); ) { String nextItem = (String) it.next(); if (nextItem.equals("plutonium")) items.remove(nextItem); // Should be it.remove() (*) } } } The decontaminate procedure is intended to remove all the plutonium for the list of otherwise safe items, but silently fails to do so because of the starred bug, in conjunction with our current approach to detecting comodification. It is likely that most programmers would prefer to seen an exception at run-time alerting them to the problem. The naive solution is to add comodification checks to hasNext in AbstractList, but this doubles the cost of comodification checking. It turns out that it is sufficient to do the test only on the last iteration, which adds virtually nothing to the cost. In other words, the current implementation of hasNext: public boolean hasNext() { return nextIndex() < size; } Is replaced by this implementation: public boolean hasNext() { if (cursor != size()) return true; checkForComodification(); return false; } This change will not be made because a Sun-internal regulatory body rejected it. The formal ruling indicated that the change "has demonstrated the potential to have significant compatibility impact upon existing code." (The "compatibility impact" is that the fix has the potential to replace silent misbehavior with a ConcurrentModificationException.) ###@###.### 2004-02-26
26-02-2004