United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
JDK-8158160 : Change in behaviour of ArrayList iterator between JDK 6 and JDK 7

Details
Type:
Bug
Submit Date:
2016-05-30
Status:
Closed
Updated Date:
2016-05-31
Project Name:
JDK
Resolved Date:
2016-05-30
Component:
core-libs
OS:
Sub-Component:
java.util:collections
CPU:
Priority:
P4
Resolution:
Won't Fix
Affected Versions:
7
Fixed Versions:

Related Reports
Relates:
Relates:

Sub Tasks

Description
Run the following test with JDK 6 and JDK 7. The output will differ on JDK 7, 
it will not print the "additionalItem". It is as if the additional item is not
present.

---

import java.util.*;

/** A List that can be initialized with a given item. */
public class ArrayListSubClass extends ArrayList<String> {

    private final String additionalItem;

    ArrayListSubClass(String additionalItems) {
        this.additionalItem = additionalItems;
    }

    @Override
    public int size() {
        return super.size() + 1;
    }

    @Override
    public String get(int index) {
        if (index < super.size()) {
            return super.get(index);
        } else {
            return additionalItem;
        }
    }

    public static void main(String[] args) {
        List<String> list = new ArrayListSubClass("additionalItem");
        list.add("first");
        list.add("second");
        list.add("third");

        int n = 0;
        for (Object o : list)
            System.out.println(++n + " : "  + o);
    }
}


$ jdk1.6.0_60/bin/java -version
java version "1.6.0_60"
Java(TM) SE Runtime Environment (build 1.6.0_60-b32)
Java HotSpot(TM) 64-Bit Server VM (build 20.60-b02, mixed mode)

$ jdk1.6.0_60/bin/java ArrayListSubClass
1 : first
2 : second
3 : third
4 : additionalItem

$ jdk1.7.0_45/bin/java ArrayListSubClass
1 : first
2 : second
3 : third

---

This is a change in behavior between JDK 6 and JDK 7. The change in behavior was
as a result of the changes in JDK-6359979, which was performance motivated.
JDK 7 shipped in mid 2011, and to the best of my knowledge this is the first
time that this issue has been reported. Extending ArrayList and relying on its
abstract's supertype, AbstractList's, behavior is not recommended practice,
though I do accept, looking at the JDK 6 API docs, that someone could get this
impression [1], albeit misguided. The extender of ArrayList should NOT make any
assumptions about its implementation.

This is not something that we can realistically change again, as it could
potentially have a negative affect on applications, running on JDK 7 and later,
making assumptions about the present behavior and performance characteristics.
Instead one should implement a composite iterator, see below for an example of
this. Such an iterator will work for both JDK 6 and future JDK releases ( no
JDK 7+ specific code is required ).

---

The behavior that the testcase was relying on in JDK 6, namely that the
implementation of ArrayList.iterator depends on the backing list's size(),
get(int), and remove(int) methods, was part of the implementation specific notes
in JDK 6 [1]. It is however, a binary compatible change to override a
supertype's method in a subtype to provide an alternative, more efficient,
implementation.

The changes for JDK-6359979 should probably have had a release note in the
compatibility guide for upgrading to JDK 7, but unfortunately they did not. 

---

Composite iterator that will work with the above testcase:

    @Override
    public Iterator<String> iterator() { return new InternalIterator(); }

    private class InternalIterator implements Iterator<String> {
        int cursor; // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

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

        public String next() {
            checkForComodification();
            int i = cursor;
            if (i >= size())
                throw new NoSuchElementException();
            cursor = i + 1;
            lastRet = i;
            return get(i);
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayListSubClass.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }


[1] http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html
    ( click on the iterator() link inherited from AbstractList )

                                    

Comments
From Effective Java, Item16: Favor composition over inheritance:

Inheritance is a powerful way to achieve code reuse, but it is not always the best tool for the job. Used inappropriately, it leads to fragile software. It is safe to use inheritance within a package, where the subclass and the superclass implementa- tions are under the control of the same programmers. It is also safe to use inherit- ance when extending classes specifically designed and documented for extension (Item 17). Inheriting from ordinary concrete classes across package boundaries, however, is dangerous. As a reminder, this book uses the word ???inheritance??? to mean implementation inheritance (when one class extends another). The problems discussed in this item do not apply to interface inheritance (when a class imple- ments an interface or where one interface extends another).

Unlike method invocation, inheritance violates encapsulation [Snyder86]. In other words, a subclass depends on the implementation details of its superclass for its proper function. The superclass???s implementation may change from release to release, and if it does, the subclass may break, even though its code has not been touched. As a consequence, a subclass must evolve in tandem with its super- class, unless the superclass???s authors have designed and documented it specifically for the purpose of being extended.

                                     
2016-05-31
I've looked into the history on this issue and concur with what Chris has in the description.

In general then one needs to be very careful when extending implementation classes, particularly when only overriding a subset of the methods (as seems to be the case here) on the assumption that all non-overridden methods are based on the overridden methods.  So if ArrayListSubClass is really representative of the escalation then it is very fragile, even more so when you look at other List methods that could potentially be dependent on the size (isEmpty, clone, toArray, to name just a few).

As regards the changes in JDK-6359979 then the motivation was performance and the changes went into an early JDK 7 build (May 2007, 9 years ago). Part of the change was to copy down the spec/javadoc from List/AbstractList::iterator so that the spec for ArrayList::iterator is clear and doesn't include the implementation spec from AbstractList. It probably should have been identified as a potential compatibility issue at the time. It wasn't, and this is why there isn't a release note on this topic. That said, I'm not aware of other issues stemming from this change. It has been in two major JDK releases and so widespread use for several years without issues (at least none that I can find that are specifically related to this change).
                                     
2016-05-31



Hardware and Software, Engineered to Work Together