JDK-5060257 : please change return type of Iterable.iterator() to Iterator
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util
  • Affected Version: 5.0,6
  • Priority: P2
  • Status: Closed
  • Resolution: Won't Fix
  • OS: solaris_8,windows_xp
  • CPU: generic,x86
  • Submitted: 2004-06-09
  • Updated: 2017-05-19
  • Resolved: 2004-06-11
Related Reports
Duplicate :  
Duplicate :  
Relates :  
Relates :  
Relates :  
Relates :  
Description
We noticed a recurring problem that in some program designs that
require a coding pattern that is entirely typesafe yet can't be
expressed in the current type system.  It occurs in the implementation
of Collections and it arose recently in a compiler refactoring.  The coding
pattern can be made typesafe but it requires a small API change.  We propose
to make that API change in Tiger.  It cannot be done after Tiger because
the change would be incompatible with the APIs in Tiger.

Here is the issue.

Consider the following optimization.  Suppose you have a List class

    class MyList<T> implements Iterable<T> {
        public Iterator<T> iterator() {
            return new Iterator<T> {
                public boolean hasNext() {
                    return whatever;
                }
                public void remove() {
                }
                public T next() {
                    return whatever;
                }
            }
        }
    }

now suppose your application happens to be structured such that most
lists are empty.  You can avoid creating a new iterator object every
time an empty loop appears in a for-each statement by the following
optimization:

    class MyList<T> implements Iterable<T> {
        private final static Iterator EMPTY_ITERATOR = new Iterator() {
            public boolean hasNext() { return false }
            public void remove() {
                throw new UnsupportedOperationException();
            }
            public Object next() { throw new NoSuchElementException(); }
        };
        public Iterator<T> iterator() {
            if (size == 0) return EMPTY_ITERATOR; // ***
            return new Iterator<T>() {
                public boolean hasNext() {
                    return whatever;
                }
                public void remove() {
                }
                public T next() {
                    return whatever;
                }
            }
        }
    }

Now there is no object creation when you ask for an iterator on an
empty List.  However, there is an unchecked conversion at the line
marked *** even though this coding pattern is perfectly safe, and
there is no way to express in the Java type system that this is safe.

There is a trivial extension to the Java type system that can be used
along with a simple API change to make this safe.  The required API
change is to change Iterable from this

    public interface Iterable<T> {
        java.util.Iterator<T> iterator();
    }

to this

    public interface Iterable<T> {
        java.util.Iterator<? extends T> iterator();
    }

Although not required, we would also benefit from making this change
in any interface that extends Iterable.  This change to the return
type of Iterable.iterator() and its overriders is what is proposed for
tiger.  It enables the rest of the solution to be completed in a
subsequent version of the languae.  If we don't make the API change
now, we will never be able to make the coding pattern typesafe without
making incompatible API changes.

The language part of the change is to introduce a name for the null
type.  For simplicity, I recommend it be called "null".  Since types
and variables occupy separate namespaces, there is no
confusion.  With these two changes, the coding pattern can now be
expressed in a typesafe way:

    class MyList<T> implements Iterable<T> {
        private final static Iterator<null> EMPTY_ITERATOR = new Iterator<null>() {
            public boolean hasNext() { return false }
            public void remove() {
                throw new UnsupportedOperationException();
            }
            public null next() { throw new NoSuchElementException(); }
        };
        public Iterator<? extends T> iterator() {
            if (size == 0) return EMPTY_ITERATOR; // ***
            return new Iterator<T>() {
                public boolean hasNext() {
                    return whatever;
                }
                public void remove() {
                }
                public T next() {
                    return whatever;
                }
            }
        }
    }

The marked line is now totally typesafe.

Because the Iterable and Iterator interfaces are inherently covariant it is
safe, for example, for a Collection<Object>'s iterator() method to return an
Iterator<String> instead of an Iterator<Object>.  This proposed change
makes that possible when it is useful in an application.

Clients using the for-each language construct need not adjust 

Comments
PUBLIC COMMENTS ...
18-06-2004

EVALUATION Will propose for Tiger. If not approved such code can never be made typesafe. ###@###.### 2004-06-08 The Tiger core team has declined this change for Tiger. Since the change would be incompatible with the current generification for Iterable, this is not something that can be done after Tiger. Closing as will not fix. As the required coding pattern with the current signature is not dynamically typesafe, this decision pretty much prevents us from ever supporting reification of type parameters in the Java Programming Language. The horizon on this design space is now in sight. ###@###.### 2004-06-11 Here is the rationale for refusing the change: First, it complicates the source of most loops that uses iterators. It forces programmers to learn wildcards before they would otherwise have any need to. On the other hand, the benefit occurs only in a very rare coding pattern. Second, it is a change that requires fairly wide changes throughout the J2SE source base - every Iterable implementation or client needs to be updated. We are in the very final stages of the Tiger release, where only very serious bugs with very low risk fixes are accepted into the source base. We're past the code freeze date, and in the testing phase in preparation for the release. Had this "problem" been noticed a month or two ago, the situation might be different. Third, there is a reasonable workaround. We can isoloate the unsafety required in this coding pattern by adding the following method to our library in some future release: public static <T> Iterator<T> emptyIterator(); Because it's not my decision, I have the luxury of taking the following position: Although I disagree with the decision, I believe it is the right one under the circumstances. ###@###.### 2004-06-15
15-06-2004