Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8260400

ArrayList's iterator() is broken: Fails to check for expectedModCount in hasNext

    XMLWordPrintable

    Details

      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


        Attachments

          Issue Links

            Activity

              People

              Assignee:
              Unassigned Unassigned
              Reporter:
              webbuggrp Webbug Group
              Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved: