[External] : Re: ReversibleCollection proposal

[forax at univ-mlv.fr]

----- Mail original -----
> De: "Anthony Vanelverdinghe" <dev at anthonyv.be>
> À: "Remi Forax" <forax at univ-mlv.fr>
> Cc: "Stuart Marks" <stuart.marks at oracle.com>, "core-libs-dev" <core-libs-dev at openjdk.java.net>
> Envoyé: Jeudi 13 Mai 2021 21:18:22
> Objet: Re: [External] : Re:  ReversibleCollection proposal

> Hi Rémi
> 
> The discussion "new types? or new default methods?" is indeed a valid one. In
> fact, I think this choice has already been made once in favor of a default
> method, when adding `List::sort` was chosen over adding `SortedList` (though I
> imagine that choice was a no-brainer).

yes, very true, there is no SortedList even if it would be useful to know if a list is already sorted, by example, we can add binarySearch() on it with no problem of people using it on an unsorted list.

> 
> In this case I prefer adding new types though, so I wanted to share my take on
> this.
> 
> In the following diagram (see [1] in case it got mangled), I've tried to arrange
> all relevant Collection types by their defining characteristics:
> 
>|- Collection
>|---------------------------------------------------------------------------------------------------------------|
>|unordered    ordered                                   sorted           distinct
>|distinct & ordered    distinct & sorted |
>|                                                                        Set                                                 |
>|             Queue = (get|remove)First + addLast       PriorityQueue
>|             |
>|             Stack = (add|get|remove)Last
>|             |
>|             Deque = Queue + Stack + addFirst
>|             LinkedHashSet         SortedSet         |
>|             List = Deque + (add|get|remove)Indexed    List::sort
>|             NavigableSet      |
>|----------------------------------------------------------------------------------------------------------------------------|
> 
> As I see it, there are a couple of issues with this:
> * conceptually, every List is a Deque, but List doesn't extend Deque. If it
> would, all uses of List (e.g. as a parameter type in APIs) where the indexed
> access isn't required could be replaced with Deque instead. Or e.g. when you
> need to take a stack as argument: currently Deque is the recommended parameter
> type, but that means you can't just pass a List to the method as-is. With RC,
> you'd be able to use that as parameter type and pass both Deque and List.

You can use the same argument to have a common super type between Map and Collection, it would be very useful.

Until you think what methods are available on that type, size() and isEmpty(), meh, this is useless.

RC has the same issue, it's stuck in between Collection and List, so the cases where you don't want a Collection because it has not enough methods you want to use but at the same time you don't want a List because it has too many methods are vanishingly small.

The problem is that adding RC is not source compatible, so you are asking to add something in the JDK which serve a corner case but at the same time forces people to change their code even if they don't use RC.
It's a loose / loose situation, we will have to maintain a collection forever in the JDK that nobody uses but everybody will pay for it.

[...]

> 
> On Wednesday, May 12, 2021 13:22 CEST, forax at univ-mlv.fr wrote:
> 
>> First, i think we have overlooked ReversibleMap, if you have a LinkedHashMap,
>> the keySet should be a ReversibleSet.
> 
> I'm not sure what you meant, but the PR already defines `LinkedHashMap::keySet`
> as `public ReversibleSet<K> keySet()`.

LinkedHashMap is perhaps the only implementation which has a keySet which is reversible, but there are a lot of other collection implementations, Apache collection, Guava, Eclipse, clojure-core, etc that may have such kind of implementation too. The same way you want RC between Queue and List, you want ReversibleMap between those Map implementations.

> 
>> Again, we have seen that introducing those interfaces
>> - is not source backward compatible thus it will be painful for some of our
>> users,
>>   I believe NavigableSet/NavigableMap did not have that issue because only one
>>   existing implementation per interface was retrofitted to implement those
>>   interfaces, TreeSet for NavigableSet and TreeMap for NavigableMap.
>>   ConcurrentSkipListSet/ConcurrentSkipListMap were added at the same time, so
>>   there was no existing code doing a lub (lowest upper bound) between TreeSet and
>>   ConcurrentSkipListSet.
>>   Here, they are a lot of implementations that will implement be retrofitted to
>>   ReversibleCollection, ReversibleSet and ReversibleMap.
> 
> As far as I understand, both options might cause source incompatibilities, but I
> assume you estimate the actual impact of adding default methods to be (much)
> smaller?

Adding a default method may creates source incompatibilities but this can be solved by having a name with no collision, that why Iterator.forEachRemaining is such a long name by example.

Adding a common supertype to at least two already existing types change the inferred type in methods like Array.asList(), List.of() or in Stream so either there is no such problem, which means that nobody wants a supertype between Deque and List, or we have a lot of codes that now fail to compile. In both case, it means we should not add RC.

> 
>> - people will have to wait a theoretically infinite time before being to
>> introduce a public method that takes a ReversibleCollection, ReversibleSet and
>> ReversibleMap to their library, because it requires
>>   all existing implementations of collection with an order to be retrofitted to
>>   implement those interfaces.
> 
> I think I'm missing something here. I just did an experiment to convince myself
> that the set of interfaces a class implements isn't hard-wired in its class
> file. In other words, that any custom List/Deque/SortedSet/... implementation
> would be seen as implementing RC/RS without having to recompile it (that, or my
> experiment was flawed somehow, of course). So am I correct that your concerns
> are only about custom collections that implement Collection directly? If so, if
> I'd introduce a public method in my library today, I'd have to declare the
> parameter as Collection in order for custom collections to be able to use it.
> So in the future, I could either introduce an overloaded the method (one with a
> Collection parameter & one with a ReversibleCollection), or I could expect
> clients to do `List::copyOf`... right? I'd appreciate it if you could elaborate
> on this point, because I don't understand the concern yet.

Let say Java 18 adds RC, so in my new shiny library, i use it by introducing a method
  void foo(ReversibleCollection c) { ...

What it means for people that want to use the method foo ? if they are using the JDK collection, it all clear, now if they are using an ordered Collection from Apache, Guava,  Eclipse, etc, that Collection has not yet being retrofitted to implement ReversibleCollection so it means that as a user he will not use my shiny method foo until the library that provides the implementation is updated.

As you said, as a user i can also use new ArrayList<>() or List.copyOf(), but in that case, why not declaring foo as taking a List in the first place, it will make the adoption of my library faster.
So it's a kind of vicious circle, until enough libraries that provides a collection API has been updated, as a library developer, i will not use ReversibleCollection.
And given that no library are using ReversibleCollection, collection library developers have no incentive to update their library (that forces all their users to update their JDK version).

When you have this kind of relation, it takes a loooong time until you reach the point where people will start to using RC.

> 
>> - adding any new interfaces has a real cognitive cost, the collection API is
>> supposed to be simple, does being reversible really worth such new weight.
> 
> I believe this is subjective, but to me the new interfaces are like "the missing
> piece" of the Collections API puzzle. I believe their value is also in the fact
> that they reconcile List/Deque and LinkedHashSet/SortedSet and are very useful
> as parameter/return types in APIs.

Again, for you ReversibleCollection is the missing piece of the puzzle, for far more people it's ImmutableList, for me it's an interface which is a supertype of Collection that does not allow remove and clear because I very rarely use those methods and if there is no remove you can make the Iterator far faster. Everybody has its fantasy interface he wants to add on the collection API. But i hope that t next time we add one, it will be more useful and with a better compatibility story than ReversibleCollection, ReversibleSet and ReversibleMap. 

> 
> Kind regards, Anthony

regards,
Rémi

> 
> [1] https://gist.github.com/anthonyvdotbe/e2e313693f032e4336e5385334a476db