Sequenced Collections

Summary

Add ReversibleCollection and ReversibleSet interfaces and retrofit them into the collection hierarchy.

Problem

See the proposal for a full design discussion, including problem and solution:

http://mail.openjdk.java.net/pipermail/core-libs-dev/2021-April/076461.html

I've attached the initial proposal as ReversibleCollection20210416.txt, and I've attached the diagram it links to as ReversibleCollectionDiagram.pdf.

Solution

See above.

Specification

Here's a skeleton of the proposed API changes, which should be sufficient to start evaluating the compatibility impact. All APIs are in java.util unless otherwise noted.

New interfaces:

public interface ReversibleCollection<E> extends Collection<E> {
    ReversibleCollection<E> reversed();
    default void addFirst(E e)
    default void addLast(E e)
    default E getFirst()
    default E getLast()
    default E removeFirst()
    default E removeLast()
}

public interface ReversibleSet<E> extends ReversibleCollection<E>, Set<E> {
    ReversibleSet<E> reversed();
}

Adjustments are made to the following classes in java.util:

List<E>:
    extends ReversibleCollection<E>
    default List<E> reversed()          // covariant override of new method

Deque<E>:
    extends ReversibleCollection<E>
    default Deque<E> reversedDeque()    // new method
                                        // note, no covariant override of reversed()

SortedSet<E>:
    extends ReversibleSet<E>
    default SortedSet<E> reversed()     // covariant override of new method

NavigableSet<E>:
    default NavigableSet<E> reversed()  // covariant override of new method

LinkedHashSet<E>:
    extends ReversibleSet<E>
    default ReversibleSet<E> reversed() // covariant override of new method

LinkedHashMap<K, V>:
    ReversibleSet<K> keySet()           // covariant override of existing method
    ReversibleSet<Entry<K,V>>           // covariant override of existing method
    ReversibleCollection<V> values()    // covariant override of existing method
    V putFirst(K, V)                    // new method
    V putLast(K, V)                     // new method

Discussion

The main concerns I have for review are the potential for source and binary incompatibilities. I believe incompatibilities can occur in the following areas:

(1) Name or return value clash by introduction of new methods "reversed" and add/get/remove x First/Last into a widely implemented interface hierarchy.

(2) Covariant overrides of reversed(). I don't think this is likely to be an issue (assuming there are no name clashes with "reversed" itself), as introducing covariant overrides for newly introduced methods should be fairly safe.

(3) Covariant overrides of existing methods on LinkedHashMap: keySet, entrySet, and values. If subclasses overrode any of these methods, either using the current return type or a covariant override of their choice, this could lead to incompatibilities.

(4) New methods on LinkedHashMap: putFirst, putLast. There is the possibility of existing subclasses defining these methods, leading to a conflict.

(5) Source incompatibilities with type inference. These are mainly related to the possibility of inference of new types that might clash with assumptions made by existing code written. (These don't seem very significant to me though.)

(6) Conflicting default methods, in general. Several new default methods are being added here. If there's no conflict, an existing method might end up overriding accidentally, which is a concern. However, a class might inherit from some other method with a conflicting default method, which would be binary and source incompatible.

(7) Conflicting default methods, in particular. The default methods here are mostly unlikely to conflict with each other, as few collections implementations inherit from more than one collection family. Indeed, this is usually illegal, as it is semantically invalid for a class to implement, say, both List and Set. However, some collections interfaces are compatible, such as List and Deque. Indeed, LinkedList implements both. (So does an internal class sun.awt.util.IdentityLinkedList.) Not providing a covariant override for Deque.reversed() avoids the unresolvable conflict over return types. However, an override must still be provided to determine which default method is called. This is a source and binary compatibility issue. It can occur with classes that implement both List and Deque. It can also occur if application code were to create an "off-label" subclass, such as one that extends LinkedHashSet and also implements List. (This is semantically invalid but it's possible that people do it anyway.)

For the name clashes and covariant overrides issues, I plan to do corpus searches. If the conflicts are minimal, I'd like to go ahead. If many conflicts turn up, I'll pursue renaming and other API adjustments as a fallback plan.

Feedback and advice is welcome about other potential compatibility issues, ways to investigate potential conflicts (e.g., different kinds of corpus searches), and ways to minimize risk of potential conflicts.