JDK-8260400 : ArrayList's iterator() is broken: Fails to check for expectedModCount in hasNext
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 8,11,17
  • Priority: P4
  • Status: Closed
  • Resolution: Duplicate
  • OS: generic
  • CPU: generic
  • Submitted: 2021-01-25
  • Updated: 2021-05-25
  • Resolved: 2021-01-27
Related Reports
Duplicate :  
Description
ADDITIONAL SYSTEM INFORMATION :
The bug is ArrayList which is System / OS/ JRI independent, and is present in the master branch of the github openjdk repo clone as of Jan 25th 2021.

A DESCRIPTION OF THE PROBLEM :
In exotic circumstances (not involving threading, see code samples below), for ArrayList: You can make an iterator, then modify the list (and not through the iterator), then iterate on the iterator, and __no__ ConcurrentModificationException occurs. This is a bug: The javadoc of ArrayList explicitly promises that it always will.

This occurs because the hasNext method fails to check modCount; instead, it just checks if the iterator's 'position' field is equal to the backing list's 'size' field, and if so, returns false (thus e.g. ending a for(:) construct). That means that for example looping through an arraylist and removing the second-to-last element on its iterator results in the while loop ending as normal instead of the expected and according to javadoc spec required ConcurrentModificationException.

See lines 75-85 for the javadoc, I will quote here:

<p id="fail-fast">
 * The iterators returned by this class's {@link #iterator() iterator} and
 * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:
 * if the list is structurally modified at any time after the iterator is
 * created, in any way except through the iterator's own
 * {@link ListIterator#remove() remove} or
 * {@link ListIterator#add(Object) add} methods, the iterator will throw a
 * {@link ConcurrentModificationException}.  Thus, in the face of
 * concurrent modification, the iterator fails quickly and cleanly, rather
 * than risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.

which indicates that throwing that ConcurrentModificationException is __required__. The offending line is line 964, reproducing here:

public boolean hasNext() {
    return cursor != size;
}

This line should first invoke `checkForComodification();` prior to running its one line.


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Run this code:

List<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
for (String item : list) if ("1".equals(item)) list.remove("1");

List<String> list2 = new ArrayList<String>();
list2.add("1");
list2.add("2");
for (String item : list) if ("2".equals(item)) list.remove("2");


EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The first block (the first for loop) should have thrown a ConcurrentModificationException. The javadoc of ArrayList itself demands that it do so.

ACTUAL -
No ConcurrentModificationException is thrown for the first block. As an example, the second block does indeed throw it, which highlights that you need a fairly specific scenario in order for the CoModEx to fail to be thrown.

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

class OopsieArrayListBroken {
    public static void main(String[] args) {
        try {
            List<String> list = new ArrayList<String>();
            list.add("1");
            list.add("2");

            for (String item : list) {
                if ("1".equals(item)) {
                    list.remove(item);
                }
            }

            throw new AssertionError("We should not get here at all!");
        } catch (ConcurrentModificationException e) {
            // this is expected.
        }
    }
}

---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Well, I doubt any code is out there that relies on ConcurrentModificationException being thrown to work correctly; this is more a case where a bug is written in someone's java code, where this openjdk bug causes their bug to be harder to find. 

FREQUENCY : always



Comments
Reasonable people can disagree. It's certainly reasonable to check for comodification in both hasNext and next. But I'd rather move long term towards **less** checking by default, and more opt-in checking, in the spirit of the assert facility.
02-02-2021

Additional Information from submitter: =========================== > ConcurrentModificationException is an example of internal consistency checks, and it is always controversial how much checking to do. In general, added checking can turn an O(N) algorithm into O(N^2) e.g. a PriorityQueue could check on every operation that the internal heap invariant continues to hold. This note is irrelevant. We know the performance cost of calling `checkForComodification()` in hasNext, and it is effectively zero: It is a `fieldA == fieldB` check, which certainly does not change the algorithmic complexity, and pragmatically speaking, 99% of the time, after calling hasNext, you call next(), so these fields will be in-cache and may even be hotspot-optimized down to nothing. The argument made here is 'hey, checks COULD be costly, even if this one is not'. That can be used to shoot down literally any check in the entire VM; this is therefore not a valid reason to close this bug report. The javadoc says 'best effort basis'. The implementation __does not do what the docs say it should__. A free check obviously falls within whatever definition of 'best effort basis' you prefer to use here.
02-02-2021

The observations on Windows 10: JDK 8: Failed, no ConcurrentModificationException thrown JDK 11: Failed JDK 17ea build 6: Failed
29-01-2021

ConcurrentModificationException is an example of internal consistency checks, and it is always controversial how much checking to do. In general, added checking can turn an O(N) algorithm into O(N^2) e.g. a PriorityQueue could check on every operation that the internal heap invariant continues to hold. I feel that such consistency checking should be available, optional, and default to no-checking. But it's a huge amount of work to provide implementations with different levels of checking, so I don't see it happening.
27-01-2021

Additional Information from submitter: =========================== I searched before, but somehow I missed it - I found it now, however: This bug has been reported before, here: https://bugs.openjdk.java.net/browse/JDK-4902078 However, before copy-pasting that rejection into this bug report / marking this bug report as a duplicate of 4902078, note that the decision to WONTFIX 4902708 is __17 years old__, and the reasoning stated there is suspect/there is no stated reason at all: quoting from 4902708: "because a Sun-internal regulatory body rejected it", based on "The formal ruling indicated that the change "has demonstrated the potential to have significant compatibility impact upon existing code." - Given the warning on the javadoc not to rely on this, that is clearly either a mistranslation of what this 'sun-internal regulatory body' actually decided, or obviously an error by that body. Whilst the javadoc does indeed say that the fail-fast behaviour must not be relied upon, this is still a bug: * It says 'best-effort'. The entire section about best-effort is fairly clearly referring to when you modify the list from another thread. Not the case here. I'd interpret that section of the javadoc of '_if_ modification occurs from another thread and unsynchronized, then the fail-fast behaviour is best-effort / cannot be relied upon'. Even if that is not a fair characterisation of what that javadoc is conveying, then it's still a problem: The javadoc promises 'best-effort', and not calling `checkForComodification()` in the hasNext is _not_ best-effort: That is a cheap and reliable call. Best-effort basis implies it therefore runs the check. * If the idea is to skip the check because 'The specs as listed in the javadoc give the implementation the freedom to skip the check, and it _is_ more performant not to do it, even if the performance gain is extremely marginal', then why not remove the entire concurrent modification system? That's a much bigger performance savings: Even if 64-bit aligned, this reduces the aligned-total-field-size of iterators made from arraylists to 64-bit, down from 128-bit, that's far more significant (because the expectedModCount field can be removed). Note that the behaviour when you run into this bug is quite bizarre and harmful if you don't understand ArrayList's internals: If the second-to-last element is removed as it is iterated over, then iteration just stops (no exception) afterwards, which means the last item in the list (which is not removed at all and still in there) never even gets iterated. _If_ this (admittedly exotic) bug is triggered, the effects are quite harmful and hard to understand: Exactly what the comodification system is designed to prevent.
27-01-2021

Agreed, throwing ConcurrentModificationException isn't guaranteed. This specific behavior happens to be one where hasNext() returns false, causing iteration loops to terminate normally instead of throwing CME. Lack of CME is not considered a bug. Closing as a duplicate of JDK-8136821.
27-01-2021

>> The javadoc of ArrayList explicitly promises that it always will. * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. Fail-fast iterators * throw {@code ConcurrentModificationException} on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: <i>the fail-fast behavior of iterators * should be used only to detect bugs.</i> Likely a dup of some old bug that was closed Not An Issue.
26-01-2021