ReversibleCollection proposal

[forax at univ-mlv.fr]

----- Mail original -----
> De: "Stuart Marks" <stuart.marks at oracle.com>
> À: "Remi Forax" <forax at univ-mlv.fr>
> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>
> Envoyé: Mercredi 21 Avril 2021 19:38:23
> Objet: Re: ReversibleCollection proposal

> 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.

An API can not use ReversibleCollection as parameter before all the implementations of Collection that have an ordering are updated to implement ReversibleCollection instead of Collection.

By example, if I add a method
  public void foo(ReversibleCollection c)  
in my library, people that want to be able to use foo with an existing collection with an ordering have to wait that collection implementation to be updated.

So i will not add a method like foo in my API until enough (whatever enough means) implementation of Collection with an ordering have migrated.

This is a similar issue as the migration from Python 2 to Python 3, it takes at least 10 years, so in 10 years, I will be able to had a public method that takes a ReversibleCollection in my API,
without people not be able to using it.


> 
> 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.

nope, many applications do not use *only* the collection from the JDK,
but also collections that comes from other libraries than msut to be upgraded to use ReversibleCollection.

> 
> 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.

ReversibleCollection can be a solution, it's also not the best way to say that you want a collection with an ordering,
any collections with zero or one element is also a valid ordered collection, so by example a HashSet with only one element is a valid argument.

> 
>>>   * 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.

It shows that the concept ReversibleCollection/ReversibleSet concept while useful out of the blue, needs to be shoehorned in the JDK, making it not worth it because the cost vs reward has changed. 

> 
> s'marks

Rémi