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

Sequenced Collections



    • Type: CSR
    • Status: Provisional
    • Priority: P4
    • Resolution: Unresolved
    • Fix Version/s: tbd
    • Component/s: core-libs
    • Labels:
    • Subcomponent:
    • Compatibility Kind:
      source, binary
    • Compatibility Risk:
    • Compatibility Risk Description:
      See "discussion" section
    • Interface Kind:
      Java API
    • Scope:



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


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


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


      See above.


      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:

          extends ReversibleCollection<E>
          default List<E> reversed()          // covariant override of new method
          extends ReversibleCollection<E>
          default Deque<E> reversedDeque()    // new method
                                              // note, no covariant override of reversed()
          extends ReversibleSet<E>
          default SortedSet<E> reversed()     // covariant override of new method
          default NavigableSet<E> reversed()  // covariant override of new method
          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


      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.


          Issue Links



              smarks Stuart Marks
              smarks Stuart Marks
              0 Vote for this issue
              2 Start watching this issue