ReversibleCollection proposal

[Stuart Marks]

On 4/19/21 4:05 PM, forax at univ-mlv.fr wrote:
>>   * There's a useful clump of semantics here, combined with sensible operations
>>   that
>> rely on those semantics. There are a lot of places in the spec where there is
>> hedging of the form "if the collection has an ordering, then... otherwise the
>> results are undefined". This is unnecessary in the context of a new type.
>> Furthermore, the new operations fit well with the new types' semantics, with no
>> hedging necessary.
> 
> You can only say that a reversible collection has an ordering. But usually you want the opposite, all collections that have an ordering are a reversible collection. But while this can be true for the implementations inside the JDK that will never be true in Java because there all already collection implementations with an ordering which do not implement ReversibleCollection.
> 
> Sadly, this ship has sailed.
> The spec will still have to say "if the collection has an ordering", otherwise the new semantics is not a backward compatible.

The value being provided here is that the ReversibleCollection interface provides a 
context within which specs no longer need to hedge about "if the collection has an 
ordering". APIs that produce or consume ReversibleCollection no longer need to 
include this hedge, or have disclaimers about ordering. Potential new 
ReversibleCollection implementations also need not worry about this issue in the 
same way they did when they were forced to implement Collection directly.

Of course there will always be ordered collections that don't implement 
ReversibleCollection. (Examples of this are the Queue-but-not-Deque implementations 
in the JDK and 3rd party ordered collections that implement Collection directly.) 
Existing APIs that produce or consume Collection but have stipulations about 
ordering may need to remain, although some could be adjusted depending on the context.

You rightly point out that this problem can never be solved in general. However, 
it's not a goal for ReversibleCollection to represent *all* ordered collections, so 
it's hardly a criticism that it doesn't solve a problem that cannot be solved.

>>   * These semantics appear across a broad range of existing collection types and
>> implementations. It's quite valuable to have a type that unifies the common
>> pieces
>> of List, Deque, SortedSet, and LinkedHashSet into a single abstraction.
> 
> yes in term of documentation, but in Java, it also means that you can use that interface as a type.
> 
> For a List, a Deque or a Set, there are known algorithms that takes such type has parameter so it makes sense to have such type.
> For a ReversibleCollection, i do not see many codes that will benefit taking a ReversibleCollection as parameter instead of using Collection.

It seems likely that many public APIs (both in the JDK and in external libraries) 
will continue to use Collection, for compatibility reasons.

In certain cases (such as LinkedHashMap, see below) the APIs could be adjusted, if 
the compatibility impact is small or can be mitigated.

ReversibleCollection unifies a broad set of existing collections without requiring 
any retrofitting at all. Many applications and libraries don't have their own 
collection implementations; they just use the ones in the JDK. They can benefit from 
the new APIs in ReversibleCollection immediately, without the need for any 
retrofitting at all.

ReversibleCollection also provide opportunities for new code and for existing APIs 
that don't have stringent compatibility constraints. Consider an application that 
has a method wants to consume an ordered collection; a reasonable API would take a 
List as a parameter.

Suppose a caller happened to have a LinkedHashSet in the right order (for example, 
because it wanted to deduplicate the elements). Either the caller would be forced to 
copy the LHS into a List before passing it, or the callee could adjust its parameter 
to be Collection -- but this creates the possibility of bugs if a HashSet is passed 
by accident. Using ReversibleCollection as a parameter type fixes this problem.

>>   * It's useful to have a new type for return types in APIs. Consider
>> LinkedHashMap's entrySet, keySet, and values views. While we clearly get by with
>> having these return Set or Collection today, we need a place to put the new
>> methods.
>> Either they go on Collection (and have extremely weak semantics) or we define
>> new
>> interfaces.
> 
> Even if you define a new interface, you can not change the return type of LinkedHashMap entrySet because it's not a backward compatible change. LinkedHashMap is not final so you have to update all subclasses of LinkedHashMap too.

As I've mentioned, introducing the covariant overrides for LinkedHashMap views is a 
compatibility *risk* but by itself this is not dispositive.

In the past we had no way to assess this risk, so we simply avoided ever making such 
changes. This might be why NavigableMap introduced navigableKeySet to return a 
NavigableSet instead of providing a covariant override for keySet.

If we can ascertain (via code searching) that introducing covariant overrides to 
LinkedHashMap introduces minimal incompatibilities, we might decide to go ahead with 
the change. (What's considered "minimal" is of course up for discussion.)

If however we decide the incompatibilities are too great, a fallback plan would be 
to introduce new methods reversibleEntrySet() et al for the reversible views. This 
would be a little bit disappointing, but it doesn't invalidate the 
ReversibleCollection/ReversibleSet concept.

s'marks