RFR: 8266571: Sequenced Collections

[Stuart Marks]

On Tue, 8 Feb 2022 17:23:38 GMT, Stuart Marks <smarks at openjdk.org> wrote:

> PR for Sequenced Collections implementation.

I'm not convinced it's binary compatible. :-) Perhaps this particular case is, but there are a bunch of other cases (additional subclasses, etc.) that need to be considered.

Thanks for the SourceGraph query. I'll take a look at those.

The fallback position is to do something like NavigableMap and provide the SequencedX-returning methods with different names, avoiding covariant overrides. I was discussing this with KevinB not long ago and he said this would make him sad. It would make me sad too. :-) But it might be a forced move; I'm not convinced it's possible to add covariant overrides into a hierarchy as widely used and subclassed as the collections framework without introducing unacceptable incompatibilities.

Still working on compatibility analysis.

See compatibility report attached to the CSR [JDK-8266572](https://bugs.openjdk.org/browse/JDK-8266572).

Summary of recent design changes:

1. Covariant override restored for `Deque::reversed`. It turns out that `LinkedList` (and other classes that inherit conflicting default methods because they implement both `List` and `Deque`) can resolve this conflict by providing a covariant override that returns a subtype of `List` and `Deque`.

2. Added `SequencedMap` interface retrofitted above `LinkedHashMap` and `SortedMap`.

3. Removed covariant override proposal for `Map` view methods `keySet`, `values`, and `entrySet`. These methods will remain as-is. New methods `sequencedKeySet`, `sequencedValues`, and `sequencedEntrySet` are introduced that return the sequenced types.

> I might take another swing at this and see if there's a way to get throwing [methods] into SequencedMap. The problem is that `firstKey` throws if empty but `firstEntry` returns `null` if empty. So to make things consistently throwing, we'd need to add `getFirst`/`LastEntry` and `removeFirst`/`LastEntry` to `SequencedMap` (and probably get rid of some of the other methods). This would make `SequencedMap` and probably `LinkedHashMap` fairly nice, but it would clutter up `NavigableMap`.

After some more consultation and thinking, I've decided not to do this. We can't make things fully consistent; we can only choose where to put the inconsistency. Currently, `List` has throwing-style methods. For example, to remove the first element, you need to do `list.remove(0)`. Of course this throws if the list is empty, so code must check first. It thus makes sense to have `removeFirst` be a throwing method. (`NavigableSet` uses a mixture of throwing and null-returning, but `List` is used an order of magnitude more frequently so we'll follow `List`.)

By contrast, `Map` doesn't have any throwing-style methods. Methods like `get` and `remove` return `null` if the requested key isn't present (which is the case if the map is empty). All of the navigation methods on `NavigableMap` also return `null` if the map is empty or if the element isn't present. Thus, adding throwing methods will do a fair amount of damage to `NavigableMap`.

The real outliers are `firstKey` and `lastKey`, which throw if the map is empty. They're defined on `SortedMap`. These don't actually add much, but they do add some confusion and inconsistency, so I think it would actually be helpful to remove them from `SequencedMap`.

Specdiff posted:

https://cr.openjdk.org/~smarks/collections/specdiff-sequenced-20230316/overview-summary.html

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

PR Comment: https://git.openjdk.org/jdk/pull/7387#issuecomment-1099824260
PR Comment: https://git.openjdk.org/jdk/pull/7387#issuecomment-1162132964
PR Comment: https://git.openjdk.org/jdk/pull/7387#issuecomment-1253162447
PR Comment: https://git.openjdk.org/jdk/pull/7387#issuecomment-1253163561
PR Comment: https://git.openjdk.org/jdk/pull/7387#issuecomment-1307810991
PR Comment: https://git.openjdk.org/jdk/pull/7387#issuecomment-1474442816