RFR: 8266571: Sequenced Collections [v12]

[Stuart Marks]

On Fri, 21 Jul 2023 16:19:35 GMT, Hollis Waite <duke at openjdk.org> wrote:

>> Stuart Marks has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains 96 commits:
>> 
>>  - Merge branch 'master' into JDK-8266571-SequencedCollections
>>  - Optimizations for ReverseOrderListView; check indexes in reversed domain.
>>  - Wording tweaks to SequencedMap / NavigableMap.
>>  - Change "The implementation in this class" to "... interface."
>>  - Delegate more methods in the views of ReverseOrderSortedMapView.
>>  - Add missing @throws and @since tags.
>>  - Convert code samples to snippets.
>>  - Various editorial changes.
>>  - Fix up toArray(T[]) on reverse-ordered views.
>>  - Remove unnecessary 'final' from a couple places.
>>  - ... and 86 more: https://git.openjdk.org/jdk/compare/2ea62c13...2827aa69
>
> Backwards compatibility is indeed an issue. Nevertheless, it feels like there ought to be some way to navigate backwards and forwards during iteration. `AbstractSequentialList.listIterator(int)` provides this functionality, even though usage of this method isn't always efficient. In many cases, a SequencedCollection is backed by a doubly linked list. It's up to the user to understand performance implications. Maybe add new method `SequencedCollection.listIterator()`?
> 
>> What stops you from deriving a list from LinkedHashMap.values() as follows?
> 
> I wouldn't want to copy the whole collection. Furthermore, deletions wouldn't be backed by original collection.

@hwaite 

As @pavelrappo suggested previously, changing the return type of a method within the hierarchy is an incompatible change. The issue is that doing so would invalidate all existing subclasses and subinterfaces. Suppose for example we were to change the iterator() method of SequencedCollection and List to return ListIterator (along with all the concrete classes in the JDK). Existing List subclasses would still have an iterator() method that returned an Iterator. If anybody called it expecting to get a ListIterator, they'd get NoSuchMethodError.

I went through a bunch of similar analysis when I attempted to change SequencedMap's keySet/values/entrySet methods to return SequencedSet and SequencedCollection. The cases are pretty complicated but bottom line is that it's impractical. In retrospect though this is kind of obvious. We'd be changing the contract of an existing interface, but there's no way any existing implementation binary can fulfill this modified contract.

Stepping away from this actual change, it'd be good to understand what you're trying to do here. ListIterator fuses three different concepts: the ability to traverse forwards and backwards, the ability to mutate the underlying List at the current location (add/remove/set), and the index of the current location. Which of these is important to your use case? What operations would be helpful?

Note that ListIterator doesn't actually reverse its direction. Instead, the calling code needs to call different methods to traverse forwards (hasNext/next) vs backwards (hasPrevious/previous). In some unpublished prototypes I did experiment with a ReversibleIterator (a precursor to the original ReversibleCollection proposal) where you could switch directions in the middle of iteration. I eventually abandoned it. I forget the exact reason, but I seem to recall that the difficulty was with maintaining the right position when iteration is reversed, from within a default method.

Finally, I have feedback that ListIterator is pretty clumsy to use. I kind of suspect that a putative ReversibleIterator would also be pretty clumsy.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/7387#issuecomment-1645981312