JDK-6529795 : (coll) Iterator.remove() fails if next() threw NoSuchElementException
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 6
  • Priority: P3
  • Status: Closed
  • Resolution: Fixed
  • OS: linux
  • CPU: x86
  • Submitted: 2007-03-01
  • Updated: 2012-10-08
  • Resolved: 2011-05-17
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 6 JDK 7
6u2Fixed 7 b10Fixed
Related Reports
Relates :  
Description
FULL PRODUCT VERSION :
java version "1.6.0"
Java(TM) SE Runtime Environment (build 1.6.0-b105)
Java HotSpot(TM) Client VM (build 1.6.0-b105, mixed mode, sharing)

ADDITIONAL OS VERSION INFORMATION :
Linux 2.6.18.5-gg3 #1 SMP i686 GNU/Linux

A DESCRIPTION OF THE PROBLEM :
The contract of Iterator.remove() says: "Removes from the underlying collection the last element returned by the iterator". Consider the case where next() is called repeatedly until the end of the collection is reached and a NoSuchElementException is thrown; a subsequent call to remove() should remove the last element returned by next(). However, HashMap.HashIterator and several other Iterator implementations instead throw an IllegalStateException.

This behavior is inconsistent with JDK 5 and with other Iterator implementations, such as those returned by ArrayList and LinkedList.

The problem can be easily seen in the nextEntry() method of HashMap.HashIterator. In JDK 5, the "current" field was not assigned until the return statement. In JDK 6, the "current" field is assigned before the NoSuchElementException is thrown. A similar bug can be see in TreeMap.

The bug appears to affect the following collections in JDK 6:

java.util.HashSet
java.util.TreeSet
java.util.HashMap.entrySet()
java.util.TreeMap.entrySet()
java.util.HashMap.keySet()
java.util.TreeMap.keySet()
java.util.HashMap.values()
java.util.TreeMap.values()

The following collections are *unaffected* in JDK 6:

java.util.ArrayList
java.util.LinkedList
java.util.LinkedHashSet
java.util.LinkedHashMap.entrySet()
java.util.LinkedHashMap.keySet()
java.util.LinkedHashMap.values()

There are other classes which I did not test. None of the tested classes were affected in JDK 5, build 1.5.0_06-b05.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Given an iterator, such as hashMap.keySet().iterator(),

1. Call next() repeatedly until a NoSuchElementException is thrown.
2. Call remove().

See source code below for a concrete example.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Calling remove() should remove the last element returned by the iterator, namely the last element in the underlying collection.
ACTUAL -
An IllegalStateException is thrown.

ERROR MESSAGES/STACK TRACES THAT OCCUR :
java.lang.IllegalStateException
        at java.util.HashMap$HashIterator.remove(HashMap.java:808)
        ...

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.*;

public class IteratorTests {
  private static final int SIZE = 4;

  public static void main(String[] args) {
    testArrayList();
    testLinkedList();
    testLinkedHashSet();
    testHashSet();
    testTreeSet();
    testHashMapEntrySet();
    testLinkedHashMapEntrySet();
    testTreeMapEntrySet();
    testHashMapKeySet();
    testLinkedHashMapKeySet();
    testTreeMapKeySet();
    testHashMapValues();
    testLinkedHashMapValues();
    testTreeMapValues();
  }

  public static <T> void test(Collection<T> collection, String name) {
    int size = collection.size();
    Iterator<T> iterator = collection.iterator();
    try {
      while (true) {
        iterator.next();
      }
    } catch (NoSuchElementException expected) {}
    try {
      iterator.remove();
    } catch (IllegalStateException e) {
      System.out.println("FAILED " + name);
      return;
    }
    System.out.println("PASSED " + name);
  }

  public static void testArrayList() {
    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < SIZE; i++) {
      list.add(i);
    }
    test(list, "java.util.ArrayList");
  }

  public static void testLinkedList() {
    List<Integer> list = new LinkedList<Integer>();
    for (int i = 0; i < SIZE; i++) {
      list.add(i);
    }
    test(list, "java.util.LinkedList");
  }

  public static void testLinkedHashSet() {
    Set<Integer> set = new LinkedHashSet<Integer>();
    for (int i = 0; i < SIZE; i++) {
      set.add(i);
    }
    test(set, "java.util.LinkedHashSet");
  }

  public static void testHashSet() {
    Set<Integer> set = new HashSet<Integer>();
    for (int i = 0; i < SIZE; i++) {
      set.add(i);
    }
    test(set, "java.util.HashSet");
  }

  public static void testTreeSet() {
    Set<Integer> set = new TreeSet<Integer>();
    for (int i = 0; i < SIZE; i++) {
      set.add(i);
    }
    test(set, "java.util.TreeSet");
  }

  public static void testHashMapEntrySet() {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < SIZE; i++) {
      map.put(i, i);
    }
    test(map.entrySet(), "java.util.HashMap.entrySet()");
  }

  public static void testLinkedHashMapEntrySet() {
    Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
    for (int i = 0; i < SIZE; i++) {
      map.put(i, i);
    }
    test(map.entrySet(), "java.util.LinkedHashMap.entrySet()");
  }

  public static void testTreeMapEntrySet() {
    Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
    for (int i = 0; i < SIZE; i++) {
      map.put(i, i);
    }
    test(map.entrySet(), "java.util.TreeMap.entrySet()");
  }

  public static void testHashMapKeySet() {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < SIZE; i++) {
      map.put(i, i);
    }
    test(map.keySet(), "java.util.HashMap.keySet()");
  }

  public static void testLinkedHashMapKeySet() {
    Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
    for (int i = 0; i < SIZE; i++) {
      map.put(i, i);
    }
    test(map.keySet(), "java.util.LinkedHashMap.keySet()");
  }

  public static void testTreeMapKeySet() {
    Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
    for (int i = 0; i < SIZE; i++) {
      map.put(i, i);
    }
    test(map.keySet(), "java.util.TreeMap.keySet()");
  }

  public static void testHashMapValues() {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < SIZE; i++) {
      map.put(i, i);
    }
    test(map.values(), "java.util.HashMap.values()");
  }

  public static void testLinkedHashMapValues() {
    Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
    for (int i = 0; i < SIZE; i++) {
      map.put(i, i);
    }
    test(map.values(), "java.util.LinkedHashMap.values()");
  }

  public static void testTreeMapValues() {
    Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
    for (int i = 0; i < SIZE; i++) {
      map.put(i, i);
    }
    test(map.values(), "java.util.TreeMap.values()");
  }

}
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Use JDK 5, or consider the state of an Iterator undefined after any exception is thrown.

Release Regression From : 5.0u11
The above release value was the last known release where this 
bug was not reproducible. Since then there has been a regression.

Comments
EVALUATION The specification is not completely clear here, but consistency and compatibility demand the same behavior as jdk 5. The coding style of using exceptions to check for end of iteration is not recommended, especially when there is a handy hasNext() method. It is a principle of style that a method that throws an exception should try not to modify the internal state of the object. Iterator implementations in ConcurrentSkipListMap and CopyOnWriteArrayList are also imperfect in this way.
01-03-2007