Re: [External] : Re: ReversibleCollection proposal
On 20/05/2021 08:35, dfranken@gmail.com wrote: I also think the proposal of Stuart is reasonable though, but it seemed to me that we had reached some sort of impasse in this discussion. As Remi points out, we have (default) methods which sometimes throw exceptions when they are implemented to signify they don't actually implement the given feature, but we also have interfaces which add new methods. So any choice we make here seems to be inconsistent with some choice we made in the past, but such is the nature of software development I guess. I think progress is still possible. The discussion has shown some alternatives which are not better than new ReversibleCollection/ReversibleSet types. The discussion has raised some concerns about compatibility but they are not to hard to overcome (mostly just source-level). There is clearly a benefit from new types although migration to use them will not be fast. But it might be faster than we are used to. The most difficult was (and for some still is) a JDK 8 -> JDK 9 jump, but once you are on JDK 9+ it is relatively easy to follow latest JDK release. With LTS JDK 17 around the corner, I expect most production code which now runs on JDK 11 will relatively quickly migrate to JDK 17 just for improvements in JVM/GC if not for Language/APIs. I think adding these types will surely trigger some disturbance but nothing major. Peter
Re: [External] : Re: ReversibleCollection proposal
Dear Brian,
I understand this would be a massive undertaking.
Still, the date-time library was a mess before Java 8 and it has been
rewritten and found its way to most other libraries.
So while I understand this isn't going to be done any time soon, my
only question was whether it had been thought about at any time in the
past. And if the consensus at that time was 'well, it would be great
if we could do it, but it's totally impractical, so let's not do it' I
would be okay with that.
I also think the proposal of Stuart is reasonable though, but it seemed
to me that we had reached some sort of impasse in this discussion. As
Remi points out, we have (default) methods which sometimes throw
exceptions when they are implemented to signify they don't actually
implement the given feature, but we also have interfaces which add new
methods. So any choice we make here seems to be inconsistent with some
choice we made in the past, but such is the nature of software
development I guess.
Given the choices of what is actually possible, I would go the
interface route.
Kind regards,
Dave
On Wed, 2021-05-19 at 17:23 -0400, Brian Goetz wrote:
>
> > Has it ever been conceived to create an entire new API like how it
> > was
> > done for Dates and Times? Obviously this would be a massive
> > undertaking, but it seems to me we've just about reached the limits
> > of
> > how far we can stretch the current API.
>
> "This code is a mess, we should throw it away and rewrite it"
>
> -- every developer
>
> Don't confuse the volume of "I would rather do it this way" replies
> with
> the complexity of this issue; I think that's just the nature of the
> game
> ("Being the biggest crime of the last 50 years, and everybody wanted
> to
> get in the newspaper story about it.") Stuart's proposal is a
> measured,
> responsible, carefully-thought-through way to extend the framework we
> have.
>
> In addition to "massive undertaking", and in addition to "if you
> think
> you can't get people to agree on something the size of a golf ball,
> try
> to get them to agree on something the size of Montana", there's
> another
> massive problem here: migration. It's not just a matter of having a
> "better" Collections library; the collection interfaces we have
> (Collection, List, Map, Set) have found their way into the API of
> nearly
> every Java library. Moving to Collections II would then force a
> migration on every one of those libraries (or consumer of those
> libraries.)
>
>
Re: [External] : Re: ReversibleCollection proposal
Has it ever been conceived to create an entire new API like how it was
done for Dates and Times? Obviously this would be a massive
undertaking, but it seems to me we've just about reached the limits of
how far we can stretch the current API.
"This code is a mess, we should throw it away and rewrite it"
-- every developer
Don't confuse the volume of "I would rather do it this way" replies with
the complexity of this issue; I think that's just the nature of the game
("Being the biggest crime of the last 50 years, and everybody wanted to
get in the newspaper story about it.") Stuart's proposal is a measured,
responsible, carefully-thought-through way to extend the framework we have.
In addition to "massive undertaking", and in addition to "if you think
you can't get people to agree on something the size of a golf ball, try
to get them to agree on something the size of Montana", there's another
massive problem here: migration. It's not just a matter of having a
"better" Collections library; the collection interfaces we have
(Collection, List, Map, Set) have found their way into the API of nearly
every Java library. Moving to Collections II would then force a
migration on every one of those libraries (or consumer of those libraries.)
Re: [External] : Re: ReversibleCollection proposal
In reading all of the messages in this discussion, it becomes clear to me that this is not a trivial change, because we are mostly hindered by the Collection API as it currently exists. Adding interfaces seems like the correct OOP way to do things, but it may hinder adoption, because we have to wait for it to cascade through the ecosystem. Adding default methods seems like the most compatible way, but then we create even more confusion in the Collection class. If add() can throw an exception, but getFirst() never will but may just return a random element, that does not seem consistent to me. Has it ever been conceived to create an entire new API like how it was done for Dates and Times? Obviously this would be a massive undertaking, but it seems to me we've just about reached the limits of how far we can stretch the current API. When given the choice between the current proposals to add interfaces or default methods, I'm kind of torn. Maybe we should just yield and add the methods to the different sub-interfaces like List, etc? This seems to be the least disruptive, but obviously it doesn't greatly improve the overall design. Kind regards, Dave On Fri, 2021-05-14 at 00:15 +0200, fo...@univ-mlv.fr wrote: > - Mail original - > > De: "Anthony Vanelverdinghe" > > À: "Remi Forax" > > Cc: "Stuart Marks" , "core-libs-dev" > > > > 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 th
Re: [External] : Re: ReversibleCollection proposal
- Mail original - > De: "Anthony Vanelverdinghe" > À: "Remi Forax" > Cc: "Stuart Marks" , "core-libs-dev" > > 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 >|---| >|unorderedordered sorted >distinct >|distinct & ordereddistinct & sorted | >|Set > | >| Queue = (get|remove)First + addLast PriorityQueue >| | >| Stack = (add|get|remove)Last >| | >| Deque = Queue + Stack + addFirst >| LinkedHashSet SortedSet | >| List = Deque + (add|get|remove)IndexedList::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, fo...@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 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 cau
Re: ReversibleCollection proposal
Hi Stuart
Will EnumSet also be updated to implement ReversibleSet? Or will it be updated
to implement NavigableSet [1] independently of this enhancement?
I'd also like to propose adding `ReversibleSet::of` factory methods. This is
something I miss having on SortedSet occasionally, but ReversibleSet would
actually be a better fit for such methods.
Kind regards, Anthony
[1] https://bugs.openjdk.java.net/browse/JDK-6278287
On Friday, April 16, 2021 19:40 CEST, Stuart Marks
wrote:
> This is a proposal to add a ReversibleCollection interface to the Collections
> Framework. I'm looking for comments on overall design before I work on
> detailed
> specifications and tests. Please send such comments as replies on this email
> thread.
>
> Here's a link to a draft PR that contains the code diffs. It's prototype
> quality,
> but it should be good enough to build and try out:
>
> https://github.com/openjdk/jdk/pull/3533
>
> And here's a link to a class diagram showing the proposed additions:
>
>
> https://cr.openjdk.java.net/~smarks/ReversibleCollection/ReversibleCollectionDiagram.pdf
>
> Thanks,
>
> s'marks
>
>
> # Ordering and Reversibility
>
>
> A long-standing concept that's been missing from collections is that of the
> positioning, sequencing, or arrangement of elements as a structural property
> of a
> collection. (This is sometimes called the "iteration order" of a collection.)
> For
> example, a HashSet is not ordered, but a List is. This concept is mostly not
> manifested in the collections API.
>
> Iterating a collection produces elements one after another in *some*
> sequence. The
> concept of "ordered" determines whether this sequence is defined or whether
> it's a
> coincidence of implementation. What does "having an order" mean? It implies
> that
> there is a first element and that each element has a successor. Since
> collections
> have a finite number of elements, it further implies that there is a last
> element
> that has no successor. However, it is difficult to discern whether a
> collection has
> a defined order. HashSet generally iterates its elements in the same undefined
> order, and you can't actually tell that it's not a defined order.
>
> Streams do have a notion of ordering ("encounter order") and this is
> preserved,
> where appropriate, through the stream pipeline. It's possible to detect this
> by
> testing whether its spliterator has the ORDERED characteristic. Any
> collection with
> a defined order will have a spliterator with this characteristic. However,
> this is
> quite a roundabout way to determine whether a collection has a defined order.
> Furthermore, knowing this doesn't enable any additional operations. It only
> provides
> constraints on the stream's implementations (keeping the elements in order)
> and
> provides stronger semantics for certain operations. For example, findFirst()
> on an
> unordered stream is the same as findAny(), but actually finds the first
> element if
> the stream is ordered.
>
> The concept of ordering is thus present in the system but is surfaced only in
> a
> fairly indirect way. We can strengthen abstraction of ordering by making a few
> observations and considering their implications.
>
> Given that there is a first element and a last element, the sequence of
> elements has
> two ends. It's reasonable to consider operations (add, get, remove) on either
> end.
> Indeed, the Deque interface has a full complement of operations at each end.
> This is
> an oft-requested feature on various other collections.
>
> Each element except for the last has a successor, implying that each element
> except
> for the first has a predecessor. Thus it's reasonable to consider iterating
> the
> elements from first to last or from last to first (that is, in forward or
> reverse
> order). Indeed, the concept of iterating in reverse order appears already in
> bits
> and pieces in particular places around the collections:
>
> - List has indexOf() and lastIndexOf()
> - Deque has removeFirstOccurrence() and removeLastOccurrence()
> - List has a ListIterator with hasPrevious/previous methods
> - Deque and NavigableSet have descendingIterator methods
>
> Given an ordered collection, though, there's no general way to iterate it in
> reverse
> order. Reversed iteration isn't the most common operation, but there are some
> frequent use cases, such as operating on elements in most-recently-added
> order.
> Questions and bug reports about this have come up repeatedly over the years.
>
> Unfortunately, iterating in reverse order is much harder than iterating in
> forward
> order. There are a variety of ways to iterate in forward order. For example,
> given a
> List, one can do any of the following:
>
> for (var e : list) { ... }
> list.forEach(...)
> list.stream()
> list.toArray()
>
> However, to iterate a list in reverse order, one must use an explicit loop
> over
> ListIterator:
>
> for (var it =
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). 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 ---| |unorderedordered sorted distinctdistinct & ordereddistinct & sorted | |Set | | Queue = (get|remove)First + addLast PriorityQueue | | Stack = (add|get|remove)Last | | Deque = Queue + Stack + addFirst LinkedHashSet SortedSet | | List = Deque + (add|get|remove)IndexedList::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. * LinkedHashSet and SortedSet lack a common ancestor which asserts "this is an ordered set". So when defining an API, I'm forced to choose between SortedSet, which is more specific than I want, or List, which is more generic than I want (usually I go with SortedSet, because enforcing something through Javadoc isn't very reliable (cf. Collectors::toList: even though the spec clearly says the result might not be modifiable, people tend to simply assume it is)). Now with RC/RS these issues would be solved, where RC is ~ Deque + reversed, and RS ~ Deque + distinct + reversed. In terms of the diagram, they group together a bunch of closely-related Collection types (see [1] if needed): |- Collection ---| |unorderedordered sorted distinctdistinct & ordereddistinct & sorted | |Set | | Queue = (get|remove)First + addLast PriorityQueue | | Stack = (add|get|remove)Last | ||- ReversibleCollection ---| |- ReversibleSet ---|| ||Deque = Queue + Stack + addFirst | |LinkedHashSet SortedSet|| ||List = Deque + (add|get|remove)IndexedList::sort | | NavigableSet || ||--| |---|| || On Wednesday, May 12, 2021 13:22 CEST, fo...@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 keySet()`. > 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
Re: [External] : Re: ReversibleCollection proposal
- Mail original - > De: "Peter Levart" > À: "Stuart Marks" > Cc: "core-libs-dev" > Envoyé: Mercredi 12 Mai 2021 08:28:07 > Objet: Re: [External] : Re: ReversibleCollection proposal > On 5/12/21 2:55 AM, Stuart Marks wrote: >> As you point out, add() is kind of like addLast(), except without the >> reordering semantics for LinkedHashSet. And reversed().add() is a >> roundabout way of saying addFirst() -- also without the reordering >> semantics for LinkedHashSet. I think most people's reactions would be >> "Why didn't they just provide addFirst/addLast?" Plus the reordering >> would be missing for LHS. >> >> A second-order issue is performance. I'd expect that implementations >> would want to provide a fast-path for addFirst() that is amenable to >> JIT optimization; this seems harder to achieve with reversed().add(). > > > The allocation of a reversed view instance typically goes away when C2 > compiles the method (if the instance isn't cached like in > AbstractMap.keySet/values) so this can be as performant as specialized > addFirst(), but lack of reordering of existent element in LinkedHashSet > is a different problem I haven thought about. Don't forget that the default method implementation is just that a default method, at least the JDK implementations like LinkedHashSet can/should provide a better implementation. > > > Regards, Peter regards, Rémi
Re: [External] : Re: ReversibleCollection proposal
- Mail original - > De: "Stuart Marks" > À: "Remi Forax" > Cc: "core-libs-dev" > Envoyé: Mercredi 12 Mai 2021 07:27:51 > Objet: Re: [External] : Re: ReversibleCollection proposal >>> I'm certain that uses of RC/RS will be rare in the beginning, because they >>> will >>> be >>> new, and people won't be familar with them. And then there will the people >>> who >>> say >>> "I can't use them because I'm stuck on JDK 11 / 8 / 7 / 6 " It was the >>> same >>> thing with lambdas and streams in Java 8, with List.of() etc in Java 9, >>> records >>> in >>> Java 16, etc. This wasn't an argument not to add them, and it isn't an >>> argument >>> not >>> to add RC/RS. >> >> All the changes you are listing here are "client side" changes, the ones that >> can be adopted quickly because they do not require to change the API side of >> any libraries. >> ReversibleCollection is an API side change, like generics is, those changes >> have >> a far higher cost because you have to wait your library dependencies to be >> updated. >> On the Valhalla list, we have discussed several times about how to alleviate >> those API side change cost using automatic bridging or methods forwarding, >> even >> for Valhalla, we are currently moving in a state where those mechanisms are >> not >> needed. > > This isn't an argument against RC/RS. Application code can find uses for the > new > APIs, e.g. getFirst and addLast on List, or more ordering flexibility on > LinkedHashSet, on day one. Applications' internal APIs can also benefit on day > one. > Certainly libraries will have to wait for their clients to catch up to later > JDKs. > This has *always* been the case, even for library internals (such as use of > lambdas > or APIs introduced in newer JDKs) because libraries need to be compiled for > the > lowest version of the JDK their clients support. For example, you can't use > List.of() in a library -- even internally -- if your clients are still on JDK > 8. > There are no new issues here. First, i think we have overlooked ReversibleMap, if you have a LinkedHashMap, the keySet should be a ReversibleSet. It is because with RC/RS/RM, you have to wait far longer, being able to use the JDK version is not enough to be able to introduce a public method that takes a ReversibleCollection, you also need to be sure that all clients of your library are using collections that have been upgraded to implement ReversibleCollection. In practice, enough client might be Ok, but that's a huge difference. Instead, if we follow the path of using default methods on Collection and not new interfaces, you only need to wait until you decide to upgrade the library to the JDK version, because with default methods all existing collections are "automatically" upgraded. > >> The abstraction already exists but it's not defined in term of interface >> because >> it's an implementation decision and those are cleanly separated in the >> current >> Collection design. >> >> Let take a step back, the collection API defines basic data structure >> operations >> in term of interfaces like List, Deque, Set, etc those interfaces are >> decoupled >> from implementation capabilities like mutable, nullable, ordered and checked. >> >> Depending on the implementation capabilities, the interfaces method >> implementation may throw an exception, non-mutable implementations use >> UnsupportedOperationException, non-nullable implementations use NPE and >> checked >> implementations use CCE. >> >> So what is missing is methods on Collection interfaces that require the >> collection implementation to be ordered like descendingList(), getFirst(), >> etc. >> Those methods that may throw a specific exception if the implementation is >> not >> ordered, not UnsupportedOperationException but a new one like >> NotOrderedException. >> >> So to answer to your question about LinkedHashSet, the reverse-ordered >> LinkedHashSet is a Set with a method descendingSet() that do not throw >> NotOrderedException like any Set with an order. >> >> To summarize, if we introduce ReversibleCollection, we should also introduce >> ImmutableCollection, NonNullableCollection and CheckedCollection. >> I think it's better to consider the fact that being ordered as a capability >> (hint: this is already what the Spliterator API does) and not as a specific >> interface. > > This discussion, and your ensuing prop
Re: [External] : Re: ReversibleCollection proposal
On 5/12/21 2:55 AM, Stuart Marks wrote: As you point out, add() is kind of like addLast(), except without the reordering semantics for LinkedHashSet. And reversed().add() is a roundabout way of saying addFirst() -- also without the reordering semantics for LinkedHashSet. I think most people's reactions would be "Why didn't they just provide addFirst/addLast?" Plus the reordering would be missing for LHS. A second-order issue is performance. I'd expect that implementations would want to provide a fast-path for addFirst() that is amenable to JIT optimization; this seems harder to achieve with reversed().add(). The allocation of a reversed view instance typically goes away when C2 compiles the method (if the instance isn't cached like in AbstractMap.keySet/values) so this can be as performant as specialized addFirst(), but lack of reordering of existent element in LinkedHashSet is a different problem I haven thought about. Regards, Peter
Re: [External] : Re: ReversibleCollection proposal
I'm certain that uses of RC/RS will be rare in the beginning, because they will be new, and people won't be familar with them. And then there will the people who say "I can't use them because I'm stuck on JDK 11 / 8 / 7 / 6 " It was the same thing with lambdas and streams in Java 8, with List.of() etc in Java 9, records in Java 16, etc. This wasn't an argument not to add them, and it isn't an argument not to add RC/RS. All the changes you are listing here are "client side" changes, the ones that can be adopted quickly because they do not require to change the API side of any libraries. ReversibleCollection is an API side change, like generics is, those changes have a far higher cost because you have to wait your library dependencies to be updated. On the Valhalla list, we have discussed several times about how to alleviate those API side change cost using automatic bridging or methods forwarding, even for Valhalla, we are currently moving in a state where those mechanisms are not needed. This isn't an argument against RC/RS. Application code can find uses for the new APIs, e.g. getFirst and addLast on List, or more ordering flexibility on LinkedHashSet, on day one. Applications' internal APIs can also benefit on day one. Certainly libraries will have to wait for their clients to catch up to later JDKs. This has *always* been the case, even for library internals (such as use of lambdas or APIs introduced in newer JDKs) because libraries need to be compiled for the lowest version of the JDK their clients support. For example, you can't use List.of() in a library -- even internally -- if your clients are still on JDK 8. There are no new issues here. The abstraction already exists but it's not defined in term of interface because it's an implementation decision and those are cleanly separated in the current Collection design. Let take a step back, the collection API defines basic data structure operations in term of interfaces like List, Deque, Set, etc those interfaces are decoupled from implementation capabilities like mutable, nullable, ordered and checked. Depending on the implementation capabilities, the interfaces method implementation may throw an exception, non-mutable implementations use UnsupportedOperationException, non-nullable implementations use NPE and checked implementations use CCE. So what is missing is methods on Collection interfaces that require the collection implementation to be ordered like descendingList(), getFirst(), etc. Those methods that may throw a specific exception if the implementation is not ordered, not UnsupportedOperationException but a new one like NotOrderedException. So to answer to your question about LinkedHashSet, the reverse-ordered LinkedHashSet is a Set with a method descendingSet() that do not throw NotOrderedException like any Set with an order. To summarize, if we introduce ReversibleCollection, we should also introduce ImmutableCollection, NonNullableCollection and CheckedCollection. I think it's better to consider the fact that being ordered as a capability (hint: this is already what the Spliterator API does) and not as a specific interface. This discussion, and your ensuing proposal to add a bunch of throwing default methods to Collection, is based on a flawed premise. That premise is that there is a fundamental distinction between "data structure operations" which must be embodied as types, and "implementation capabilities" which must manifest at runtime either by allowing the operation or by throwing an exception. But this distinction isn't fundamental. In what way is being ordered not a "basic data structure" issue? In what way is indexed access (as for List) not an "implementation capability"? Really, these are two different aspects of the same thing. Over time, new "data structure operations" and new "implementation capabilities" have been added to the collections framework. Some of them were embodied as types, and some were not. Which ones were embodied as types was the result of design decisions that considered a bunch of tradeoffs. What you're attempting to do is to declare absolutes. This drives you to one of two extremes, which is either 1) to never add new types and to always add possibly-throwing operations to existing types (which seems to be what you're describing as an alternative); or 2) to claim that everything needs to be manifested as a new type (giving rise to your straw-man argument that we should also have ImmutableCollection, NonNullableCollection, CheckedCollection, etc.). The argument seems to be that we wouldn't want to add all those other types, so we mustn't add ReversibleCollection either. No. In summary, I reject the premise that adding ReversibleCollection implies that a bunch of other types also need to be added, so I don't accept this line of reasoning as an argument against ReversibleCollection. s'marks
Re: [External] : Re: ReversibleCollection proposal
On 5/1/21 7:36 AM, Peter Levart wrote:
On 4/30/21 9:25 PM, Stuart Marks wrote:
So I think we're stuck with void-returning add{First,Last} methods.
Have you thought of perhaps not adding them at all?
Collection.add() for:
List(s) - behaves the same as addLast()
LinkedHashSet - behaves the same as addLast()
Deque - behaves the same as addLast()
So for all ReversibleCollection(s) where it works, addLast() would be equivalent to
add()
addFirst(x) can be written as: reversed().add(x) if reversed() is specified to
return a reversed view over the underlying ReversibleCollection.
To me, and I think to most people, add, get, and remove all belong together, just
like offer/peek/poll. (See the tables in the Deque class spec.) Of course the issue
is that addX can't be implemented for SortedSet (or it can be, but only with some
contrivances discussed previously). The choice is between which asymmetry we want:
1. add/get/remove across most of the ReversibleCollection implementations except for
SortedSet, or
2. get/remove across all ReversibleCollection implementations, with addX() "missing"
from the set of operations.
As you point out, add() is kind of like addLast(), except without the reordering
semantics for LinkedHashSet. And reversed().add() is a roundabout way of saying
addFirst() -- also without the reordering semantics for LinkedHashSet. I think most
people's reactions would be "Why didn't they just provide addFirst/addLast?" Plus
the reordering would be missing for LHS.
A second-order issue is performance. I'd expect that implementations would want to
provide a fast-path for addFirst() that is amenable to JIT optimization; this seems
harder to achieve with reversed().add().
s'marks
Re: [External] : Re: ReversibleCollection proposal
- Mail original -
> De: "Peter Levart"
> À: "Remi Forax" , "dfranken jdk"
> Cc: "Stuart Marks" , "core-libs-dev"
>
> Envoyé: Mardi 11 Mai 2021 13:44:08
> Objet: Re: [External] : Re: ReversibleCollection proposal
> Hi Remi,
Hi Peter,
>
>
> I see you avoided addFirst/addLast methods. While getFirst/removeFirst
> could be specified to be consistent with iterator().next(), so the
> "first" part of the name would be softer, addFirst is cursed two times:
> it has no equivalent in current API and it clashes with void returning
> method in Deque. So the best "soft" alternative seems to be the existing
> Collection.add(E) method which is equivalent to addFirst() when
> Collection is ordered or something totally different when it is sorted
> (i.e. SortedSet) and again different when it is neither.
yes, i've chosen to not have addFirst/addLast because of addFirst/addLast on
Deque returning void.
To simplify the issue of adding addFirst/addLast on List,
SortedSet/NavigableSet, EnumSet, LinkedHashSet and adding
addFirstEntry/addLastEntry on SortedMap/NavigableMap, EnumMap and LinkedHashMap
can be discussed separately.
>
> To avoid bugs when an API expects an ordered Collection but has no
> static type to express that, a means to perform a runtime check would be
> needed. Marker interface is a way to add a bit of static typing to be
> used in generic methods like:
>
>
> & Ordered> void doSomething(C
> orderedCollection);
>
>
> ...but that's very limited. So probably not worth it.
yes,
and also if we go with Ordered people will also want Sorted, NoDuplicate,
NonNullable, etc.
> Stream API choose a different approach: Spliterator.characteristics(). So
> probably,
> Collection.characteristics() could also be added. The set of bit
> constants in Spliterator is applicable also to Collection (except
> SUBSIZED which has no sense in Collection, while SIZED is always present):
>
> ORDERED
> DISTINCT
> SORTED
> SIZED
> NONNULL
> IMMUTABLE
> CONCURRENT
>
> Specifically for Collection I would also add:
>
> REVERSIBLE
>
> ...to indicate that Collection.reversed() would succeed.
>
>
> The question is what would the default value of
> Collection.characteristics() be. The most sensible would be SIZED with
> overrides in:
>
> - List (SIZED | ORDERED | REVERSIBLE)
> - Set (SIZED | DISTINCT)
> - SortedSet (SIZED | SORTED | REVERSIBLE | DISTINCT)
> - LinkedHashSet (SIZED | ORDERED | REVERSIBLE | DISTINCT)
> - Queue (SIZED | ORDERED)
> - Deque (SIZED | ORDERED | REVERSIBLE)
>
> ... Immutable JDK List and Set implementations could also add IMMUTABLE
>| NONNULL, while concurrent JDK implementations would add CONCURRENT |
> NONNULL.
>
>
> ...but one could also base default value on something like this:
>
>
> default int characteristics() {
> return stream().spliterator().characteristics() &
> ~Spliterator.SUBSIZED;
> }
There is already a method Collection.spliterator() [1], no need to use an
intermediary stream
and also collection.spliterator() != collection.stream().spliterator(), but i'm
not sure if it is specified somewhere.
For me, adding a method characteristics() to Collection is also a separate
issue,
perhaps it's more a documentation issue, so adding a paragraph in the javadoc
explaining what are the Spliterator characteristics of each collections is
enough.
>
>
> Wrappers like Collections.unmodifiableXXX() would just delegate to the
> underlying Collection and augment the returned bits (with IMMUTABLE for
> example).
>
>
> An API that expects a particular kind of collection could then check
> that at runtime. Some of existing collections would have to be updated
> to express the correct characteristics, but defaults in interfaces would
> be sufficient for most and conservative.
>
>
> WDYT?
>
> Peter
Rémi
[1]
https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/util/Collection.html#spliterator()
>
>
> On 5/11/21 9:26 AM, fo...@univ-mlv.fr wrote:
>>
>>> Are you proposing to just add methods to the root Collection interface,
>>> because it already has methods which may or may not be implemented or
>>> throw Exceptions by its implementations ?
>> yes, the idea is to add getFirst/getLast/removeFirst/removeLast and reversed
>> on
>> Collection as default methods.
>> Something like
>>
>> interface Collection {
>>/**
>> * throws NoSuchElementException if the collection is empty
>> */
>>public default E getFirst() {
>> return iterator().next
Re: [External] : Re: ReversibleCollection proposal
* throws NoSuchElementException if the map is empty
* throws NonOrderedCollectionException if the map.keySet() is non ordered
*/
public default E getLastEntry() {
return reversedMap().getFirstEntry();
}
/**
* throws NoSuchElementException if the map is empty
* throws UnsupportedOperationException if the map is non mutable
* throws NonOrderedCollectionException if the map.keySet() is non ordered
*/
public default E removeLast() {
return reversedMap().removeFirstEntry();
}
}
And adds an implementation of reversedMap(), getLastEntry() and
removeLastEntry() on NavigableMap/LinkedHasMap and EnumMap.
But we could also view "having (possibly duplicate) items in a
sequence" as a capability and that is defined by an actual interface,
List.
It already exist for a Spliterator, the capability is called DISTINCT, by
example, set.stream() and list.stream().distinct() are both Streams with no
duplicate.
I do fear that if we add methods to the Collection interface, users
might not expect them to throw exceptions. E.g. if we add getFirst(),
users may just expect it to return the element that iterator().next()
or .stream().findFirst().orElseThrow() would return instead of an
UnsupportedOperationException. And while HashSet does not have a
defined order, it would in practice always return the same element.
I agree, getFirst() and removeFirst() should have their semantics based on
iterator (see above),
because as you said, it's already how findFirst() is specified.
So while I accept that some hidden capabilities are surfaced only
through return values of certain methods, I think an interface is still
a better choice here. However, if we go that route, I also agree on the
fact that we might need to explore defining proper interfaces for the
other capabilities at some point.
Kind regards,
Dave
regards,
Rémi
On Mon, 2021-05-10 at 12:22 +0200, fo...@univ-mlv.fr wrote:
- Mail original -
De: "dfranken jdk"
À: "Remi Forax" , "Stuart Marks"
Cc: "core-libs-dev"
Envoyé: Dimanche 9 Mai 2021 12:13:58
Objet: Re: [External] : Re: ReversibleCollection proposal
When I thought about Collection's role in the hierarchy, it seemed
to
me that 'Collection' is an interface for describing how elements
are
stored in a cardboard box (we can and and remove them) and that we
might need a different, yet related, interface to describe how to
retrieve the items from the box. This way we are not tied to the
Collection hierarchy and we could have one Set implementation which
is
ordered and another Set implementation which is not and they would
both
still implement Collection, but only one would implement the
interface.
So you want to model ReversibleSet as Set + Reversible,
Reversible being an interface with a small number of method specific
to the fact that the implementation is reversible.
This does not work well for two reasons,
- there is no syntax to represent the union of types in Java,
Set & Reversible set = ...
is not a valid syntax. You can use a type variable with several
bounds instead but it does work nicely with the rest of the language
(overidding, overloading, etc).
- having public methods that takes an interface with few methods is a
common design error.
Let suppose you have a method foo that only prints the elements of
a collection, in that case you may want to type the first parameter
as Iterable or Collection.
But requirements change an now you want to prints the elements
sorted, oops, you have to change the signature of the public method
which may be something not possible
depending how many "clients" this method has.
Providing interfaces with a small number of access methods will
lead to this kind of issue.
Imagine an interface like 'java.lang.OrderedEnumerable` if you will
with methods such as 'first(), last(), etc', then each
implementation
would be free to choose to implement the interface or not. I also
thought about 'OrderedIterable', but there would be too much
confusion
with 'Iterable', but I think these are related too. Retrieving
items is
an iteration problem, not a storage problem.
The problem is that is you multiply the number of interfaces to
access the elements, you add the dilemma of choice in the mix.
The first iteration of the Scala Collection were like this, too many
interfaces, at least for my taste.
While I would love to see the Collection hierarchy redesigned to
also
allow for ImmutableCollection which for instance would not have an
`add(T e)` method, I don't think we can simply do something like
that
without breaking too many things.
Dear Santa, i want an interface BuilderCollection that only allows
add() but no remove()/clear(), because if you can not remove
elements, then all the iterators can implement the snapshot at the
beginning semantics,
so no ConcurrentModificationException anymore. For me, being able to
snapshot/freeze a collection is better
Re: [External] : Re: ReversibleCollection proposal
- Mail original -
> De: "dfranken jdk"
> À: "Remi Forax"
> Cc: "Stuart Marks" , "core-libs-dev"
>
> Envoyé: Mardi 11 Mai 2021 08:45:15
> Objet: Re: [External] : Re: ReversibleCollection proposal
> Dear mr. Forax,
Hi Dave,
>
> I understand your point of view. You don't like to have separate
> standalone interfaces for things that seem to belong in a hierarchy, is
> that correct? Now that I thought about it, I agree.
yes,
>
> So if a reversable/ordered set is a specialized form of a reversable
> collection where reversable collection is a specialized form of a
> collection, it makes sense to add it into the hierarchy.
>
> Are you proposing to just add methods to the root Collection interface,
> because it already has methods which may or may not be implemented or
> throw Exceptions by its implementations ?
yes, the idea is to add getFirst/getLast/removeFirst/removeLast and reversed on
Collection as default methods.
Something like
interface Collection {
/**
* throws NoSuchElementException if the collection is empty
*/
public default E getFirst() {
return iterator().next();
}
/**
* throws NoSuchElementException if the collection is empty
* throws UnsupportedOperationException if the collection is non mutable
*/
public default E removeFirst() {
var it = iterator();
var element = it.next();
it.remove();
return element;
}
/**
* throws NonOrderedCollectionException if the collection is non ordered
*/
public default Collection reversed() {
throw new NonOrderedCollectionException();
}
/**
* throws NoSuchElementException if the collection is empty
* throws NonOrderedCollectionException if the collection is non ordered
*/
public default E getLast() {
return reversed().getFirst();
}
/**
* throws NoSuchElementException if the collection is empty
* throws UnsupportedOperationException if the collection is non mutable
* throws NonOrderedCollectionException if the collection is non ordered
*/
public default E removeLast() {
return reversed().removeFirst();
}
}
And adds an implementation of reversed(), getLast() and removeLast() on
NavigableSet/LinkedHashSet/EnumSet/Deque and List.
And do the same thing for Map:
interface Map {
/**
* throws NoSuchElementException if the map is empty
*/
public default Map.Entry getFirstEntry() {
return entrySet().iterator().next();
}
/**
* throws NoSuchElementException if the map is empty
* throws UnsupportedOperationException if the map is non mutable
*/
public default Map.Entry removeFirstEntry() {
var it = entrySet().iterator();
var element = it.next();
it.remove();
return element;
}
/**
* throws NonOrderedCollectionException if the map.keySet() is non ordered
*/
public default Map reversedMap() {
throw new NonOrderedCollectionException();
}
/**
* throws NoSuchElementException if the map is empty
* throws NonOrderedCollectionException if the map.keySet() is non ordered
*/
public default E getLastEntry() {
return reversedMap().getFirstEntry();
}
/**
* throws NoSuchElementException if the map is empty
* throws UnsupportedOperationException if the map is non mutable
* throws NonOrderedCollectionException if the map.keySet() is non ordered
*/
public default E removeLast() {
return reversedMap().removeFirstEntry();
}
}
And adds an implementation of reversedMap(), getLastEntry() and
removeLastEntry() on NavigableMap/LinkedHasMap and EnumMap.
>
> But we could also view "having (possibly duplicate) items in a
> sequence" as a capability and that is defined by an actual interface,
> List.
It already exist for a Spliterator, the capability is called DISTINCT, by
example, set.stream() and list.stream().distinct() are both Streams with no
duplicate.
>
> I do fear that if we add methods to the Collection interface, users
> might not expect them to throw exceptions. E.g. if we add getFirst(),
> users may just expect it to return the element that iterator().next()
> or .stream().findFirst().orElseThrow() would return instead of an
> UnsupportedOperationException. And while HashSet does not have a
> defined order, it would in practice always return the same element.
I agree, getFirst() and removeFirst() should have their semantics based on
iterator (see above),
because as you said, it's already how findFirst() is specified.
>
> So while I accept that some hidden capabilities are surfaced only
> through return values of certain methods, I think an interface is still
> a better choice here. However, if we go that route, I also agree on the
> fact that we might need to explore defining proper interfaces for the
> other capabilities at some point.
>
> Kind regards,
>
> Dave
Re: [External] : Re: ReversibleCollection proposal
Dear mr. Forax, I understand your point of view. You don't like to have separate standalone interfaces for things that seem to belong in a hierarchy, is that correct? Now that I thought about it, I agree. So if a reversable/ordered set is a specialized form of a reversable collection where reversable collection is a specialized form of a collection, it makes sense to add it into the hierarchy. Are you proposing to just add methods to the root Collection interface, because it already has methods which may or may not be implemented or throw Exceptions by its implementations? Or were you just pointing out that's just how it works now? That the capabilities a certain collection has, like unmodifiability or not allowing null elements, are not exposed through a proper interface but through what it returns for certain methods? But we could also view "having (possibly duplicate) items in a sequence" as a capability and that is defined by an actual interface, List. I do fear that if we add methods to the Collection interface, users might not expect them to throw exceptions. E.g. if we add getFirst(), users may just expect it to return the element that iterator().next() or .stream().findFirst().orElseThrow() would return instead of an UnsupportedOperationException. And while HashSet does not have a defined order, it would in practice always return the same element. So while I accept that some hidden capabilities are surfaced only through return values of certain methods, I think an interface is still a better choice here. However, if we go that route, I also agree on the fact that we might need to explore defining proper interfaces for the other capabilities at some point. Kind regards, Dave On Mon, 2021-05-10 at 12:22 +0200, fo...@univ-mlv.fr wrote: > - Mail original - > > De: "dfranken jdk" > > À: "Remi Forax" , "Stuart Marks" > > > > Cc: "core-libs-dev" > > Envoyé: Dimanche 9 Mai 2021 12:13:58 > > Objet: Re: [External] : Re: ReversibleCollection proposal > > > When I thought about Collection's role in the hierarchy, it seemed > > to > > me that 'Collection' is an interface for describing how elements > > are > > stored in a cardboard box (we can and and remove them) and that we > > might need a different, yet related, interface to describe how to > > retrieve the items from the box. This way we are not tied to the > > Collection hierarchy and we could have one Set implementation which > > is > > ordered and another Set implementation which is not and they would > > both > > still implement Collection, but only one would implement the > > interface. > > So you want to model ReversibleSet as Set + Reversible, > Reversible being an interface with a small number of method specific > to the fact that the implementation is reversible. > > This does not work well for two reasons, > - there is no syntax to represent the union of types in Java, > Set & Reversible set = ... > is not a valid syntax. You can use a type variable with several > bounds instead but it does work nicely with the rest of the language > (overidding, overloading, etc). > > - having public methods that takes an interface with few methods is a > common design error. > Let suppose you have a method foo that only prints the elements of > a collection, in that case you may want to type the first parameter > as Iterable or Collection. > But requirements change an now you want to prints the elements > sorted, oops, you have to change the signature of the public method > which may be something not possible > depending how many "clients" this method has. > Providing interfaces with a small number of access methods will > lead to this kind of issue. > > > > > Imagine an interface like 'java.lang.OrderedEnumerable` if you will > > with methods such as 'first(), last(), etc', then each > > implementation > > would be free to choose to implement the interface or not. I also > > thought about 'OrderedIterable', but there would be too much > > confusion > > with 'Iterable', but I think these are related too. Retrieving > > items is > > an iteration problem, not a storage problem. > > The problem is that is you multiply the number of interfaces to > access the elements, you add the dilemma of choice in the mix. > The first iteration of the Scala Collection were like this, too many > interfaces, at least for my taste. > > > > > While I would love to see the Collection hierarchy redesigned to > > also > > allow for ImmutableCollection which for instance would not have an > > `add(T e)` method, I don't think we can simply do something like > > that > > w
Re: [External] : Re: ReversibleCollection proposal
- Mail original - > De: "dfranken jdk" > À: "Remi Forax" , "Stuart Marks" > Cc: "core-libs-dev" > Envoyé: Dimanche 9 Mai 2021 12:13:58 > Objet: Re: [External] : Re: ReversibleCollection proposal > When I thought about Collection's role in the hierarchy, it seemed to > me that 'Collection' is an interface for describing how elements are > stored in a cardboard box (we can and and remove them) and that we > might need a different, yet related, interface to describe how to > retrieve the items from the box. This way we are not tied to the > Collection hierarchy and we could have one Set implementation which is > ordered and another Set implementation which is not and they would both > still implement Collection, but only one would implement the interface. So you want to model ReversibleSet as Set + Reversible, Reversible being an interface with a small number of method specific to the fact that the implementation is reversible. This does not work well for two reasons, - there is no syntax to represent the union of types in Java, Set & Reversible set = ... is not a valid syntax. You can use a type variable with several bounds instead but it does work nicely with the rest of the language (overidding, overloading, etc). - having public methods that takes an interface with few methods is a common design error. Let suppose you have a method foo that only prints the elements of a collection, in that case you may want to type the first parameter as Iterable or Collection. But requirements change an now you want to prints the elements sorted, oops, you have to change the signature of the public method which may be something not possible depending how many "clients" this method has. Providing interfaces with a small number of access methods will lead to this kind of issue. > > Imagine an interface like 'java.lang.OrderedEnumerable` if you will > with methods such as 'first(), last(), etc', then each implementation > would be free to choose to implement the interface or not. I also > thought about 'OrderedIterable', but there would be too much confusion > with 'Iterable', but I think these are related too. Retrieving items is > an iteration problem, not a storage problem. The problem is that is you multiply the number of interfaces to access the elements, you add the dilemma of choice in the mix. The first iteration of the Scala Collection were like this, too many interfaces, at least for my taste. > > While I would love to see the Collection hierarchy redesigned to also > allow for ImmutableCollection which for instance would not have an > `add(T e)` method, I don't think we can simply do something like that > without breaking too many things. Dear Santa, i want an interface BuilderCollection that only allows add() but no remove()/clear(), because if you can not remove elements, then all the iterators can implement the snapshot at the beginning semantics, so no ConcurrentModificationException anymore. For me, being able to snapshot/freeze a collection is better than an ImmutableCollection, because it can be immutable when you want. Anyway, it's not gonna to happen, there is so many ways to slice an onion and each have pros and cons and providing all the possible interfaces is a good.way to make something simple complex. > > So in short, separating retrieval aspects from storage aspects with a > different interface might be the way to go. > > Kind regards, > > Dave Franken > regards, Rémi > On Wed, 2021-05-05 at 12:41 +0200, fo...@univ-mlv.fr wrote: >> - Mail original - >> > De: "Stuart Marks" >> > À: "Remi Forax" >> > Cc: "core-libs-dev" >> > Envoyé: Mercredi 5 Mai 2021 02:00:03 >> > Objet: Re: [External] : Re: ReversibleCollection proposal >> >> > On 5/1/21 5:57 AM, fo...@univ-mlv.fr wrote: >> > > I suppose the performance issue comes from the fact that >> > > traversing a >> > > LinkedHahSet is slow because it's a linked list ? >> > > >> > > You can replace a LinkedHashSet by a List + Set, the List keeps >> > > the values in >> > > order, the Set avoids duplicates. >> > > >> > > Using a Stream, it becomes >> > > Stream.of(getItemsFromSomeplace(), getItemsFromAnotherPlace(), >> > > getItemsFromSomeplaceElse()) >> > > .flatMap(List::stream) >> > > .distinct() // use a Set internally >> > > .collect(toList()); >> > >> > The problem with any example is that simplifying assumptions are >> > necessary for >> > showing the example, but those assumptions enable it
Re: [External] : Re: ReversibleCollection proposal
When I thought about Collection's role in the hierarchy, it seemed to me that 'Collection' is an interface for describing how elements are stored in a cardboard box (we can and and remove them) and that we might need a different, yet related, interface to describe how to retrieve the items from the box. This way we are not tied to the Collection hierarchy and we could have one Set implementation which is ordered and another Set implementation which is not and they would both still implement Collection, but only one would implement the interface. Imagine an interface like 'java.lang.OrderedEnumerable` if you will with methods such as 'first(), last(), etc', then each implementation would be free to choose to implement the interface or not. I also thought about 'OrderedIterable', but there would be too much confusion with 'Iterable', but I think these are related too. Retrieving items is an iteration problem, not a storage problem. While I would love to see the Collection hierarchy redesigned to also allow for ImmutableCollection which for instance would not have an `add(T e)` method, I don't think we can simply do something like that without breaking too many things. So in short, separating retrieval aspects from storage aspects with a different interface might be the way to go. Kind regards, Dave Franken On Wed, 2021-05-05 at 12:41 +0200, fo...@univ-mlv.fr wrote: > - Mail original - > > De: "Stuart Marks" > > À: "Remi Forax" > > Cc: "core-libs-dev" > > Envoyé: Mercredi 5 Mai 2021 02:00:03 > > Objet: Re: [External] : Re: ReversibleCollection proposal > > > On 5/1/21 5:57 AM, fo...@univ-mlv.fr wrote: > > > I suppose the performance issue comes from the fact that > > > traversing a > > > LinkedHahSet is slow because it's a linked list ? > > > > > > You can replace a LinkedHashSet by a List + Set, the List keeps > > > the values in > > > order, the Set avoids duplicates. > > > > > > Using a Stream, it becomes > > > Stream.of(getItemsFromSomeplace(), getItemsFromAnotherPlace(), > > > getItemsFromSomeplaceElse()) > > > .flatMap(List::stream) > > > .distinct() // use a Set internally > > > .collect(toList()); > > > > The problem with any example is that simplifying assumptions are > > necessary for > > showing the example, but those assumptions enable it to be easily > > picked apart. > > Of > > course, the example isn't just a particular example; it is a > > *template* for a > > whole > > space of possible examples. Consider the possibility that the items > > processing > > client needs to do some intermediate processing on the first group > > of items > > before > > adding the other groups. This might not be possible to do using > > streams. Use > > your > > imagination. > > > > > I think there are maybe some scenarios where ReversibleCollection > > > can be useful, > > > but they are rare, to the point where when there is a good > > > scenario for it > > > people will not recognize it because ReversibleCollection will > > > not be part of > > > their muscle memory. > > > > I'm certain that uses of RC/RS will be rare in the beginning, > > because they will > > be > > new, and people won't be familar with them. And then there will the > > people who > > say > > "I can't use them because I'm stuck on JDK 11 / 8 / 7 / 6 " It > > was the same > > thing with lambdas and streams in Java 8, with List.of() etc in > > Java 9, records > > in > > Java 16, etc. This wasn't an argument not to add them, and it isn't > > an argument > > not > > to add RC/RS. > > All the changes you are listing here are "client side" changes, the > ones that can be adopted quickly because they do not require to > change the API side of any libraries. > ReversibleCollection is an API side change, like generics is, those > changes have a far higher cost because you have to wait your library > dependencies to be updated. > On the Valhalla list, we have discussed several times about how to > alleviate those API side change cost using automatic bridging or > methods forwarding, even for Valhalla, we are currently moving in a > state where those mechanisms are not needed. > > > > > > There is a real value to add methods like > > > descendingSet/descendingList()/getFirst/getLast on existing > > > collections, but we > > > don't need a new interface (or two) for that. > > > > It depends on what you mean by "n
Re: [External] : Re: ReversibleCollection proposal
- Mail original - > De: "Stuart Marks" > À: "Remi Forax" > Cc: "core-libs-dev" > Envoyé: Mercredi 5 Mai 2021 02:00:03 > Objet: Re: [External] : Re: ReversibleCollection proposal > On 5/1/21 5:57 AM, fo...@univ-mlv.fr wrote: >> I suppose the performance issue comes from the fact that traversing a >> LinkedHahSet is slow because it's a linked list ? >> >> You can replace a LinkedHashSet by a List + Set, the List keeps the values in >> order, the Set avoids duplicates. >> >> Using a Stream, it becomes >>Stream.of(getItemsFromSomeplace(), getItemsFromAnotherPlace(), >>getItemsFromSomeplaceElse()) >> .flatMap(List::stream) >> .distinct() // use a Set internally >> .collect(toList()); > > The problem with any example is that simplifying assumptions are necessary for > showing the example, but those assumptions enable it to be easily picked > apart. > Of > course, the example isn't just a particular example; it is a *template* for a > whole > space of possible examples. Consider the possibility that the items processing > client needs to do some intermediate processing on the first group of items > before > adding the other groups. This might not be possible to do using streams. Use > your > imagination. > >> I think there are maybe some scenarios where ReversibleCollection can be >> useful, >> but they are rare, to the point where when there is a good scenario for it >> people will not recognize it because ReversibleCollection will not be part of >> their muscle memory. > > I'm certain that uses of RC/RS will be rare in the beginning, because they > will > be > new, and people won't be familar with them. And then there will the people who > say > "I can't use them because I'm stuck on JDK 11 / 8 / 7 / 6 " It was the > same > thing with lambdas and streams in Java 8, with List.of() etc in Java 9, > records > in > Java 16, etc. This wasn't an argument not to add them, and it isn't an > argument > not > to add RC/RS. All the changes you are listing here are "client side" changes, the ones that can be adopted quickly because they do not require to change the API side of any libraries. ReversibleCollection is an API side change, like generics is, those changes have a far higher cost because you have to wait your library dependencies to be updated. On the Valhalla list, we have discussed several times about how to alleviate those API side change cost using automatic bridging or methods forwarding, even for Valhalla, we are currently moving in a state where those mechanisms are not needed. > >> There is a real value to add methods like >> descendingSet/descendingList()/getFirst/getLast on existing collections, but >> we >> don't need a new interface (or two) for that. > > It depends on what you mean by "need". Sure, we could get away without this; > after > all, we've survived the past twenty years without it, so we could probably > survive > the next twenty years as well. > > It would indeed be useful to add various methods to List, Deque, SortedSet, > and > LinkedHashSet to provide a full set of methods on all of them. And it would > also > be > nice to have those methods be similar to one another. An interface helps with > that, > but I agree, that's not really the reason to have an interface though. > > The reversed-view concept could also be added individually to the different > places. > A reverse-ordered List is a List, a reverse-ordered Deque is a Deque, a > reverse-ordered SortedSet is a SortedSet, and a reverse-ordered LinkedHashSet > is > a > ... ? And what is the type of the keySet of a LinkedHashMap, that enables one > to > (say) get the last element? see below > > After working with a system like this for a while, it begins to emerge that > there is > an abstraction missing from the collections framework, something like an > "ordered > collection". People have been missing this for quite a long time. The most > recent > example (which this proposal builds on) is Tagir's proposal from a year ago. > And > it's been asked about several times before that. ReversibleCollection fills in > that > missing abstraction. The abstraction already exists but it's not defined in term of interface because it's an implementation decision and those are cleanly separated in the current Collection design. Let take a step back, the collection API defines basic data structure operations in term of interfaces like List, Deque, Set, etc those interfaces are decoupled from implementation capabilities like mutable, nullable, ordered
Re: [External] : Re: ReversibleCollection proposal
On 5/1/21 5:57 AM, fo...@univ-mlv.fr wrote: I suppose the performance issue comes from the fact that traversing a LinkedHahSet is slow because it's a linked list ? You can replace a LinkedHashSet by a List + Set, the List keeps the values in order, the Set avoids duplicates. Using a Stream, it becomes Stream.of(getItemsFromSomeplace(), getItemsFromAnotherPlace(), getItemsFromSomeplaceElse()) .flatMap(List::stream) .distinct() // use a Set internally .collect(toList()); The problem with any example is that simplifying assumptions are necessary for showing the example, but those assumptions enable it to be easily picked apart. Of course, the example isn't just a particular example; it is a *template* for a whole space of possible examples. Consider the possibility that the items processing client needs to do some intermediate processing on the first group of items before adding the other groups. This might not be possible to do using streams. Use your imagination. I think there are maybe some scenarios where ReversibleCollection can be useful, but they are rare, to the point where when there is a good scenario for it people will not recognize it because ReversibleCollection will not be part of their muscle memory. I'm certain that uses of RC/RS will be rare in the beginning, because they will be new, and people won't be familar with them. And then there will the people who say "I can't use them because I'm stuck on JDK 11 / 8 / 7 / 6 " It was the same thing with lambdas and streams in Java 8, with List.of() etc in Java 9, records in Java 16, etc. This wan't an argument not to add them, and it isn't an argument not to add RC/RS. There is a real value to add methods like descendingSet/descendingList()/getFirst/getLast on existing collections, but we don't need a new interface (or two) for that. It depends on what you mean by "need". Sure, we could get away without this; after all, we've survived the past twenty years without it, so we could probably survive the next twenty years as well. It would indeed be useful to add various methods to List, Deque, SortedSet, and LinkedHashSet to provide a full set of methods on all of them. And it would also be nice to have those methods be similar to one another. An interface helps with that, but I agree, that's not really the reason to have an interface though. The reversed-view concept could also be added individually to the different places. A reverse-ordered List is a List, a reverse-ordered Deque is a Deque, a reverse-ordered SortedSet is a SortedSet, and a reverse-ordered LinkedHashSet is a ... ? And what is the type of the keySet of a LinkedHashMap, that enables one to (say) get the last element? After working with a system like this for a while, it begins to emerge that there is an abstraction missing from the collections framework, something like an "ordered collection". People have been missing this for quite a long time. The most recent example (which this proposal builds on) is Tagir's proposal from a year ago. And it's been asked about several times before that. ReversibleCollection fills in that missing abstraction. s'marks
Re: [External] : Re: ReversibleCollection proposal
The line of discussion here was introduced by Remi, who was making an argument of the form "introducing a type cannot solve this particular problem, therefore, introducing a new type is not useful at all." I was providing an example of where the new type is useful as a method parameter. That's all. Have you considered the alternative of a collection providing a Reversed view of itself, in the same sense that unmodifiable collections are views of an underlying collection? The proposal does define ReversibleCollection::reversed as providing a reversed view, through which modifications to the underlying collection are visible, and to which modifications are written through to the underlying collection. Or are you talking about something different? s'marks On 4/30/21 4:15 PM, Alan Snyder wrote: It sounds like the items processing maintainer would be looking for OrderedCollection and might or might not find ReversibleCollection. :-) I suspect you would agree that OrderedCollection by itself is too weak to justify being a type. It’s basically Iterable with the extra bit that the iteration order is not an implementation artifact. In this example, using the type system to detect a bug like the old bug seems like overkill. Even if the parameter were Ordered, it still might not be the *right* order. The maintainer of the client code needs to understand that. Suppose the items processor wants to require that the parameter collection not contain duplicates. Would you suggest adding a type for that? Clearly Set would be just as unnecessarily restrictive as List was for ordering. Absurdity approaches… The issue of Reversible remains, above and beyond Ordered. Have you considered the alternative of a collection providing a Reversed view of itself, in the same sense that unmodifiable collections are views of an underlying collection? Alan On Apr 30, 2021, at 3:42 PM, Stuart Marks wrote: Consider the case of a large application or other system, one that's large enough to have lots of internal APIs, but that is built as a single unit, so release-to-release compatibility isn't an issue. Suppose there is some method processItemsInOrder(List items) that has to process items in the order in which they occur, because processing of later items might depend the processing of earlier ones. The maintainer of this API chose to accept a List as a parameter, because it's a common interface and it's clearly an ordered collection. Now consider a client that gets items from different places, keeping them in order, but removing duplicates. It might do something like this: var items = new LinkedHashSet(); items.addAll(getItemsFromSomeplace()); items.addAll(getItemsFromAnotherPlace()); items.addAll(getItemsFromSomeplaceElse()); processItemsInOrder(new ArrayList<>(items)); It turns out the copying of the items into an ArrayList is a performance bottleneck, so the maintainer of the client code asks the maintainer of the items processing code to change the API to accept Collection instead. The items processing maintainer demurs, recalling that the API *did* accept Collection in the past, and a bug where somebody accidentally passed a HashSet resulted in a customer escalation because of item processing irregularities. In the aftermath of that escalation, the API was changed to List. The client maintainer reluctantly pursues alternatives for generating a deduplicated List. But wait! Those Java guys added a ReversibleCollection interface in Java N. It has the desired property of being ordered, and conveniently it's a supertype of both List and LinkedHashSet. The items processing maintainer adjusts the API to consume ReversibleCollection, and the client maintainer removes the temporary ArrayList, and everybody is happy. s'marks
Re: [External] : Re: ReversibleCollection proposal
On 4/30/21 9:25 PM, Stuart Marks wrote:
So I think we're stuck with void-returning add{First,Last} methods.
Have you thought of perhaps not adding them at all?
Collection.add() for:
List(s) - behaves the same as addLast()
LinkedHashSet - behaves the same as addLast()
Deque - behaves the same as addLast()
So for all ReversibleCollection(s) where it works, addLast() would be
equivalent to add()
addFirst(x) can be written as: reversed().add(x) if reversed() is
specified to return a reversed view over the underlying
ReversibleCollection.
Peter
Re: ReversibleCollection proposal
- Mail original - > De: "Stuart Marks" > À: "Remi Forax" > Cc: "core-libs-dev" > Envoyé: Samedi 1 Mai 2021 00:42:10 > Objet: Re: ReversibleCollection proposal >> You did not really answer to the real question, why should i use >> ReversibleCollection instead of a Collection as parameter. >> You said that it's a better type because you can not send a HashSet, but as i >> said, sending a HashSet of 0 or 1 element is perfectly valid. >> For me, we are not far from, it's typechecking for the sake of typechecking. > > I thought I did answer it, but it might have been in response to a different > message > on a different part of the thread. But I'll make the case in a more explicit > fashion > here. > > First, a couple background points related to this: > > - ReversibleCollection is not intended to, and indeed cannot represent all > ordered > collections. Queue is ordered and is not a ReversibleCollection, and there are > likely other collections out there that are ordered but that implement > Collection > directly. Also, they might or might not be reversible. > > - I expect that few, if any Java SE APIs will be adjusted to use > ReversibleCollection as a parameter type. Any APIs that use Collection but > require > an ordered type cannot be changed because of compatibility reasons. > > Despite both of these points, I believe ReversibleCollection can be > successful, > and > it can be useful in APIs as a parameter type. (The proposal itself uses > ReversibleCollection and ReversibleSet as method return types.) > > Consider the case of a large application or other system, one that's large > enough to > have lots of internal APIs, but that is built as a single unit, so > release-to-release compatibility isn't an issue. Suppose there is some method > > processItemsInOrder(List items) > > that has to process items in the order in which they occur, because processing > of > later items might depend the processing of earlier ones. The maintainer of > this > API > chose to accept a List as a parameter, because it's a common interface and > it's > clearly an ordered collection. > > Now consider a client that gets items from different places, keeping them in > order, > but removing duplicates. It might do something like this: > > var items = new LinkedHashSet(); > items.addAll(getItemsFromSomeplace()); > items.addAll(getItemsFromAnotherPlace()); > items.addAll(getItemsFromSomeplaceElse()); > processItemsInOrder(new ArrayList<>(items)); > > It turns out the copying of the items into an ArrayList is a performance > bottleneck, > so the maintainer of the client code asks the maintainer of the items > processing > code to change the API to accept Collection instead. > > The items processing maintainer demurs, recalling that the API *did* accept > Collection in the past, and a bug where somebody accidentally passed a HashSet > resulted in a customer escalation because of item processing irregularities. > In > the > aftermath of that escalation, the API was changed to List. The client > maintainer > reluctantly pursues alternatives for generating a deduplicated List. > > But wait! Those Java guys added a ReversibleCollection interface in Java N. It > has > the desired property of being ordered, and conveniently it's a supertype of > both > List and LinkedHashSet. The items processing maintainer adjusts the API to > consume > ReversibleCollection, and the client maintainer removes the temporary > ArrayList, > and > everybody is happy. I suppose the performance issue comes from the fact that traversing a LinkedHahSet is slow because it's a linked list ? You can replace a LinkedHashSet by a List + Set, the List keeps the values in order, the Set avoids duplicates. Using a Stream, it becomes Stream.of(getItemsFromSomeplace(), getItemsFromAnotherPlace(), getItemsFromSomeplaceElse()) .flatMap(List::stream) .distinct() // use a Set internally .collect(toList()); I think there are maybe some scenarios where ReversibleCollection can be useful, but they are rare, to the point where when there is a good scenario for it people will not recognize it because ReversibleCollection will not be part of their muscle memory. There is a real value to add methods like descendingSet/descendingList()/getFirst/getLast on existing collections, but we don't need a new interface (or two) for that. > > s'marks Rémi
Re: ReversibleCollection proposal
It sounds like the items processing maintainer would be looking for OrderedCollection and might or might not find ReversibleCollection. :-) I suspect you would agree that OrderedCollection by itself is too weak to justify being a type. It’s basically Iterable with the extra bit that the iteration order is not an implementation artifact. In this example, using the type system to detect a bug like the old bug seems like overkill. Even if the parameter were Ordered, it still might not be the *right* order. The maintainer of the client code needs to understand that. Suppose the items processor wants to require that the parameter collection not contain duplicates. Would you suggest adding a type for that? Clearly Set would be just as unnecessarily restrictive as List was for ordering. Absurdity approaches… The issue of Reversible remains, above and beyond Ordered. Have you considered the alternative of a collection providing a Reversed view of itself, in the same sense that unmodifiable collections are views of an underlying collection? Alan > On Apr 30, 2021, at 3:42 PM, Stuart Marks wrote: > > Consider the case of a large application or other system, one that's large > enough to have lots of internal APIs, but that is built as a single unit, so > release-to-release compatibility isn't an issue. Suppose there is some method > >processItemsInOrder(List items) > > that has to process items in the order in which they occur, because > processing of later items might depend the processing of earlier ones. The > maintainer of this API chose to accept a List as a parameter, because it's a > common interface and it's clearly an ordered collection. > > Now consider a client that gets items from different places, keeping them in > order, but removing duplicates. It might do something like this: > >var items = new LinkedHashSet(); >items.addAll(getItemsFromSomeplace()); >items.addAll(getItemsFromAnotherPlace()); >items.addAll(getItemsFromSomeplaceElse()); >processItemsInOrder(new ArrayList<>(items)); > > It turns out the copying of the items into an ArrayList is a performance > bottleneck, so the maintainer of the client code asks the maintainer of the > items processing code to change the API to accept Collection instead. > > The items processing maintainer demurs, recalling that the API *did* accept > Collection in the past, and a bug where somebody accidentally passed a > HashSet resulted in a customer escalation because of item processing > irregularities. In the aftermath of that escalation, the API was changed to > List. The client maintainer reluctantly pursues alternatives for generating a > deduplicated List. > > But wait! Those Java guys added a ReversibleCollection interface in Java N. > It has the desired property of being ordered, and conveniently it's a > supertype of both List and LinkedHashSet. The items processing maintainer > adjusts the API to consume ReversibleCollection, and the client maintainer > removes the temporary ArrayList, and everybody is happy. > > s'marks >
Re: ReversibleCollection proposal
You did not really answer to the real question, why should i use ReversibleCollection instead of a Collection as parameter. You said that it's a better type because you can not send a HashSet, but as i said, sending a HashSet of 0 or 1 element is perfectly valid. For me, we are not far from, it's typechecking for the sake of typechecking. I thought I did answer it, but it might have been in response to a different message on a different part of the thread. But I'll make the case in a more explicit fashion here. First, a couple background points related to this: - ReversibleCollection is not intended to, and indeed cannot represent all ordered collections. Queue is ordered and is not a ReversibleCollection, and there are likely other collections out there that are ordered but that implement Collection directly. Also, they might or might not be reversible. - I expect that few, if any Java SE APIs will be adjusted to use ReversibleCollection as a parameter type. Any APIs that use Collection but require an ordered type cannot be changed because of compatibility reasons. Despite both of these points, I believe ReversibleCollection can be successful, and it can be useful in APIs as a parameter type. (The proposal itself uses ReversibleCollection and ReversibleSet as method return types.) Consider the case of a large application or other system, one that's large enough to have lots of internal APIs, but that is built as a single unit, so release-to-release compatibility isn't an issue. Suppose there is some method processItemsInOrder(List items) that has to process items in the order in which they occur, because processing of later items might depend the processing of earlier ones. The maintainer of this API chose to accept a List as a parameter, because it's a common interface and it's clearly an ordered collection. Now consider a client that gets items from different places, keeping them in order, but removing duplicates. It might do something like this: var items = new LinkedHashSet(); items.addAll(getItemsFromSomeplace()); items.addAll(getItemsFromAnotherPlace()); items.addAll(getItemsFromSomeplaceElse()); processItemsInOrder(new ArrayList<>(items)); It turns out the copying of the items into an ArrayList is a performance bottleneck, so the maintainer of the client code asks the maintainer of the items processing code to change the API to accept Collection instead. The items processing maintainer demurs, recalling that the API *did* accept Collection in the past, and a bug where somebody accidentally passed a HashSet resulted in a customer escalation because of item processing irregularities. In the aftermath of that escalation, the API was changed to List. The client maintainer reluctantly pursues alternatives for generating a deduplicated List. But wait! Those Java guys added a ReversibleCollection interface in Java N. It has the desired property of being ordered, and conveniently it's a supertype of both List and LinkedHashSet. The items processing maintainer adjusts the API to consume ReversibleCollection, and the client maintainer removes the temporary ArrayList, and everybody is happy. s'marks
Re: [External] : Re: ReversibleCollection proposal
OK, I think we can wrap up this portion of the thread.
As the proposal stands, it has add{First,Last} returning void instead of some useful
value. For SortedSet and for LinkedHashMap's views, these throw UOE. Can we do better?
Collection has add(), Deque has add{First,Last} and offer{First,Last}, and
BlockingDeque has put{First,Last}. I'm loathe to add new insertion methods that
differ from these, either in signatures or semantics.
The BlockingDeque putX methods have blocking behavior, which only makes sense for a
concurrent collection. Still, because these exist, we mustn't add putX methods
elsewhere that have different semantics.
After having thought about this for a couple days, I think it's a really bad idea to
reuse offerX methods. These would allow a collection to refuse the addition of an
element and merely return a boolean indicating that. I can easily see people writing
offerX code that doesn't check the return value, and if things shift around in their
program, elements can be silently dropped. This would set a new precedent, as the
present behavior is that collections can reject adding an element only by throwing
an exception. Allowing refusal by returning 'false' would be a bad precedent.
So I think we're stuck with void-returning add{First,Last} methods.
Regarding throwing UOE, I think it's useful to distinguish between the LinkedHashMap
views and SortedSet. Today, it's already the case that Map's view collections don't
support addition, so the ReversibleX views of LinkedHashMap are similar in this regard.
SortedSet is different, as it's a top-level collection interface instead of a view
collection. It's unusual for it not to support the addX operations. We explored some
alternatives, such as throwing exceptions if preconditions aren't met. These seem
fairly rare, and the alternative behaviors don't seem all that useful. In any case
nothing emerged that was clearly better than simple UOE-throwing behavior.
OK, I think it's been useful to analyze various alternatives -- in particular I
hadn't seriously considered the offerX methods -- but I'll leave the proposal as it
stands regarding add{First,Last} methods.
s'marks
On 4/28/21 6:54 AM, Peter Levart wrote:
On 4/28/21 7:19 AM, Stuart Marks wrote:
On 4/27/21 9:17 AM, Anthony Vanelverdinghe wrote:
On Tuesday, April 27, 2021 11:25 CEST, Peter Levart
wrote:
Now just some of my thoughts about the proposal:
- SortedSet.addFirst/.addLast - I think an operation that would be used
in situations like: "I know this element should always be greater than
any existing element in the set and I will push it to the end which
should also verify my assumption" is a perfectly valid operation. So
those methods throwing IllegalStateException in case the invariant can't
be kept seem perfectly fine to me.
This was raised before and addressed by Stuart in [0]:
"An alternative as you suggest might be that SortedSet::addFirst/addLast could
throw
something like IllegalStateException if the element is wrongly positioned.
(Deque::addFirst/addLast will throw ISE if the addition would exceed a capacity
restriction.) This seems error-prone, though, and it's easier to understand and
specify that these methods simply throw UOE unconditionally. If there's a good
use
case for the alternative I'd be interested in hearing it though."
Yes, to be clear, it was Stephen Coleborne who raised this previously [1] and it's
my response that's quoted above.
Some further thoughts on this.
This is an example where, depending on the current state of the collection, the
method might throw or it might succeed. This is useful in concurrent collections
(such as the capacity-restricted Deque above), where the caller cannot check
preconditions beforehand, because they might be out of date by the time the
operation is attempted. In such cases the caller might not want to block, but
instead it might catch the exception and report an error to its caller (or drop
the request). Thus, calling the exception-throwing method is appropriate.
Something like SortedSet::addLast seems different, though. The state is the
*values* of the elements already in the collection. This is something that can
easily be checked, and probably should be checked beforehand:
if (sortedSet.isEmpty() || sortedSet.last().compareTo(e) <= 0)
sortedSet.add(e);
else
// e wouldn't be the last element, do something different
I was thinking more of a case where the else branch would actually throw
IllegalStateException and do nothing else - a kind of add with precondition check. A
precondition in the sense of Objects.requireNonNull(). I can't currently think of a
real usecase now, so this kind of operation is probably very rare. Probably not
useful since if you're adding to SortedSet, the order of elements added should not
matter because SortedSet will sort them. If you just want to check the order of
elements added and you are not willing
Re: [External] : Re: ReversibleCollection proposal
On 4/28/21 7:19 AM, Stuart Marks wrote: On 4/27/21 9:17 AM, Anthony Vanelverdinghe wrote: On Tuesday, April 27, 2021 11:25 CEST, Peter Levart wrote: Now just some of my thoughts about the proposal: - SortedSet.addFirst/.addLast - I think an operation that would be used in situations like: "I know this element should always be greater than any existing element in the set and I will push it to the end which should also verify my assumption" is a perfectly valid operation. So those methods throwing IllegalStateException in case the invariant can't be kept seem perfectly fine to me. This was raised before and addressed by Stuart in [0]: "An alternative as you suggest might be that SortedSet::addFirst/addLast could throw something like IllegalStateException if the element is wrongly positioned. (Deque::addFirst/addLast will throw ISE if the addition would exceed a capacity restriction.) This seems error-prone, though, and it's easier to understand and specify that these methods simply throw UOE unconditionally. If there's a good use case for the alternative I'd be interested in hearing it though." Yes, to be clear, it was Stephen Coleborne who raised this previously [1] and it's my response that's quoted above. Some further thoughts on this. This is an example where, depending on the current state of the collection, the method might throw or it might succeed. This is useful in concurrent collections (such as the capacity-restricted Deque above), where the caller cannot check preconditions beforehand, because they might be out of date by the time the operation is attempted. In such cases the caller might not want to block, but instead it might catch the exception and report an error to its caller (or drop the request). Thus, calling the exception-throwing method is appropriate. Something like SortedSet::addLast seems different, though. The state is the *values* of the elements already in the collection. This is something that can easily be checked, and probably should be checked beforehand: if (sortedSet.isEmpty() || sortedSet.last().compareTo(e) <= 0) sortedSet.add(e); else // e wouldn't be the last element, do something different I was thinking more of a case where the else branch would actually throw IllegalStateException and do nothing else - a kind of add with precondition check. A precondition in the sense of Objects.requireNonNull(). I can't currently think of a real usecase now, so this kind of operation is probably very rare. Probably not useful since if you're adding to SortedSet, the order of elements added should not matter because SortedSet will sort them. If you just want to check the order of elements added and you are not willing to pay the price of SortedSet, you will be adding them to a List or LinkedHashSet, but then the method would not do the check... Now this is a fair bit of code, and it would be shorter just to call sortedSet.addLast(e). But does that actually help? What if e is already in the set and is the last element? In that case the operation would be a no-op (or it would replace the element with the parameter - a slight difference as the element can be .equals() but not the same instance). Is catching an exception really what we want to do if e wouldn't be the last element? Maybe we'd want to do nothing instead. If so, catching an exception in order to do nothing is extra work. I was only thinking of situations where propagating the exception would be the desired thing. Again, I'd like to hear about use cases for a conditionally-throwing version of addLast et. al. I don't want to be limited by failure of imagination, but it does seem like this kind of behavior would be useful only in a narrow set of cases where it happens to do exactly the right thing. Otherwise, it just gets in the way, and its behavior is pretty obscure. So, color me skeptical. Right, I don't know how common such operation would be. Probably not very. Peter which are a continual source of errors.) I'll think about this more, but it doesn't seem promising. s'marks
Re: [External] : Re: ReversibleCollection proposal
Hi,
(I think the first version of this message never went through, so here it
goes just in case)
I just read quickly the proposal and it made me think about another common
issue. I wonder if we could tackle it as well.
I will call it the "find the first element when there is only one" problem.
It happens on unordered collections like a HashSet. It forces to do
Set s = new HashSet<>();
if (s.size() == 1) {
return s.iterator().next();
// or
return s.stream().findFirst().get();
}
Which is a lot of ugliness and object instantiations just to get the first
element.
I would be nice to have a public T findFirst() directly on Iterable.
With a default implementation returning iterator().next(). Things like
ArrayList will want to override will return elementData[0]. It would return
null when the list is empty. Or NoSuchElementException.
It needs to be polished of course but will that be acceptable?
Thanks,
Henri
Re: ReversibleCollection proposal
- Mail original - > De: "Stuart Marks" > À: "Remi Forax" > Cc: "core-libs-dev" > Envoyé: Vendredi 23 Avril 2021 08:56:53 > Objet: Re: ReversibleCollection proposal >> 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. > > This is a gigantic overstatement of the issue. > > It is true that an API *in the JDK* as a practical matter cannot change a > Collection > parameter to ReversibleCollection, because it will break any callers that are > currently passing Collection. The same is true of any library APIs where > compatibility is a concern. > > However, it can be quite useful in many contexts to use ReversibleCollection > as > a > parameter. Newly introduced APIs can use ReversibleCollection. Certain APIs > that > consume List could reasonably be adjusted to consume a ReversibleCollection > instead. > (More likely an overload would probably be added in order to preserve binary > compatibility.) You did not really answer to the real question, why should i use ReversibleCollection instead of a Collection as parameter. You said that it's a better type because you can not send a HashSet, but as i said, sending a HashSet of 0 or 1 element is perfectly valid. For me, we are not far from, it's typechecking for the sake of typechecking. This can be an interesting exercise for my students but it is not really a goal in Java, we have Haskell and Scala for that. I see the point of having getFirst()/getLast() or descendingSet() on LinkedHashMap (your right that getFirst() on Collection should be getAny()), I don't see the point of using ReversibleCollection as a type of a parameter, there is no algorithm that uses a ReversibleCollection as parameter in the litterature. > > s'marks Rémi
Re: ReversibleCollection proposal
- Mail original - > De: "Stuart Marks" > À: "Peter Levart" > Cc: "core-libs-dev" , "Stephen Colebourne" > > Envoyé: Mercredi 28 Avril 2021 02:04:22 > Objet: Re: ReversibleCollection proposal > On 4/27/21 2:25 AM, Peter Levart wrote: >> Right, I'm persuaded. Now if only the problems of transition to the usage of >> new >> type that Remi is worried about were mild enough. Source (in)compatibility is >> not >> that important if workarounds exist that are also backwards source >> compatible so >> that the same codebase can be compiled with different JDKs. Binary >> compatibility >> is >> important. And I guess there is a variant of the proposal that includes >> ReversibleCollection and ReversibleSet and is binary compatible. > > Yes, the source incompatibilities with the types seem to involve type > inference > (e.g., use of var choosing differently based on new types in the library) so > it > should be possible to make minor source code changes to adjust or override the > type > that's inferred. > > On binary compatibility, that comes mostly from the newly introduced methods > (reversed, addFirst etc.) and from adding covariant overrides to > LinkedHashSet. > I > guess the "variant" you mention is adding new methods with the new return > types > (e.g., reversibleEntrySet) instead of covariant overrides. Or was it something > else? Yes, you need type inference (compute lub), var is not necessary, after all var a = f(); g(a) is equivalent to g(f()) So you have an issue with varargs like T..., any method that takes two T like m(T, T), or with the ternary operator ?: At best you have a source compatibility issue, at worst, you have a runtime error or a runtime slowdown. This is something that have not been study well but the worst scenario is when a VarHandle or a MethodHandle is involved IMO, because a call like methodHandle.invokeExact() or VarHandle.compareAndSet will still compile if the inferred type changed but at runtime at best you will have a WrongMethodTypeException, at worst it will still work but performance will fall of the cliff. But maybe nobody has ever written a code like methodHandle.invoke(flag? list: linkedHashMap) Also the source compatibility issues are not only restricted to Java - source compatiblity can also be a bigger issue than it was before for people that are using jshell/java as a shell script. - and what about the other JVM languages that are using the collection API, mostly Groovy and Kotlin because they are leveraging inference far more than in Java. Scala tends to use Scala collection, and Clojure or JRuby are dynamically typed so it should not be less an issue. > > s'marks Rémi
Re: ReversibleCollection proposal
On 4/28/21 2:04 AM, Stuart Marks wrote:
Binary compatibility is important. And I guess there is a variant of
the proposal that includes ReversibleCollection and ReversibleSet and
is binary compatible.
Yes, the source incompatibilities with the types seem to involve type
inference (e.g., use of var choosing differently based on new types in
the library) so it should be possible to make minor source code
changes to adjust or override the type that's inferred.
On binary compatibility, that comes mostly from the newly introduced
methods (reversed, addFirst etc.) and from adding covariant overrides
to LinkedHashSet. I guess the "variant" you mention is adding new
methods with the new return types (e.g., reversibleEntrySet) instead
of covariant overrides. Or was it something else?
Right, either adding new method with different name or not doing
anything (left to user to insert a cast). As you already pointed out,
introduction of NavigableSet/NavigableMap opted for new method name:
(navigableKeySet) and new method parameters (subMap, headMap, tailMap)
which were actually useful. So this trick might also bi applicable here:
public interface SortedMap/LinkedHashMap {
ReversibleSet> entrySet(boolean reversed);
ReversibleSet keySet(boolean reversed);
ReversibleCollection values(boolean reversed);
So you would say:
map.keySet(false) or map.keySet(true)
instead of:
map.reversibleKeySet() or map.reversibleKeySet().reversed()
The later is more readable, but nowadays almost everybody uses IDE(s),
so they see the following for the former:
map.keySet(reversed: false) or map.keySet(reversed: true)
Peter
Peter
Re: [External] : Re: ReversibleCollection proposal
On 4/27/21 9:17 AM, Anthony Vanelverdinghe wrote: On Tuesday, April 27, 2021 11:25 CEST, Peter Levart wrote: Now just some of my thoughts about the proposal: - SortedSet.addFirst/.addLast - I think an operation that would be used in situations like: "I know this element should always be greater than any existing element in the set and I will push it to the end which should also verify my assumption" is a perfectly valid operation. So those methods throwing IllegalStateException in case the invariant can't be kept seem perfectly fine to me. This was raised before and addressed by Stuart in [0]: "An alternative as you suggest might be that SortedSet::addFirst/addLast could throw something like IllegalStateException if the element is wrongly positioned. (Deque::addFirst/addLast will throw ISE if the addition would exceed a capacity restriction.) This seems error-prone, though, and it's easier to understand and specify that these methods simply throw UOE unconditionally. If there's a good use case for the alternative I'd be interested in hearing it though." Yes, to be clear, it was Stephen Coleborne who raised this previously [1] and it's my response that's quoted above. Some further thoughts on this. This is an example where, depending on the current state of the collection, the method might throw or it might succeed. This is useful in concurrent collections (such as the capacity-restricted Deque above), where the caller cannot check preconditions beforehand, because they might be out of date by the time the operation is attempted. In such cases the caller might not want to block, but instead it might catch the exception and report an error to its caller (or drop the request). Thus, calling the exception-throwing method is appropriate. Something like SortedSet::addLast seems different, though. The state is the *values* of the elements already in the collection. This is something that can easily be checked, and probably should be checked beforehand: if (sortedSet.isEmpty() || sortedSet.last().compareTo(e) <= 0) sortedSet.add(e); else // e wouldn't be the last element, do something different Now this is a fair bit of code, and it would be shorter just to call sortedSet.addLast(e). But does that actually help? What if e is already in the set and is the last element? Is catching an exception really what we want to do if e wouldn't be the last element? Maybe we'd want to do nothing instead. If so, catching an exception in order to do nothing is extra work. Again, I'd like to hear about use cases for a conditionally-throwing version of addLast et. al. I don't want to be limited by failure of imagination, but it does seem like this kind of behavior would be useful only in a narrow set of cases where it happens to do exactly the right thing. Otherwise, it just gets in the way, and its behavior is pretty obscure. So, color me skeptical. [0] https://mail.openjdk.java.net/pipermail/core-libs-dev/2021-April/076518.html [1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2021-April/076505.html - ReversibleCollection.addFirst/.addLast are specified to have void return type. This works for List and Deque which always add element and so have no information to return. OTOH Collection.add is specified to return boolean to indicate whether collection was modified or not, but Set modifies the specification of that method a bit to be: return false or true when Set already contained an element equal to the parameter or not. So ReversibleCollection.addFirst/.addLast could play the same trick. for List(s) and Deque(s) it would always return true, but for ReversibleSet(s) it would return true only if the set didn't contain an element equal to the parameter, so re-positioning of equal element would return false although the collection was modified as a result. If addFirst/addLast were to return boolean, Deque would no longer compile due to its existing methods being incompatible with the new ones. Right, the current proposal copies the addX method signatures from Deque into ReversibleCollection. I think it was Mike Duigou who said that a method that returns void is a missed opportunity. The idea is, the library probably has some useful bit of information it can return. If the caller doesn't need it, the caller can just ignore it. On Collection::add returning a boolean, most calls to this ignore the return value, and the boolean "did this collection change as a result of this call?" is only occasionally useful. Sometimes it can be used for little tricks, such as an easy way to determine if a stream contains all unique elements: stream.allMatch(new HashSet<>()::add) But really, the boolean return value doesn't seem all that useful. Still, it could be added. The methods couldn't be called addFirst/addLast as Anthony pointed out, as this would clash with those methods already on Deque. However, Deque already contains boolean-returning
Re: ReversibleCollection proposal
On 4/27/21 2:25 AM, Peter Levart wrote: Right, I'm persuaded. Now if only the problems of transition to the usage of new type that Remi is worried about were mild enough. Source (in)compatibility is not that important if workarounds exist that are also backwards source compatible so that the same codebase can be compiled with different JDKs. Binary compatibility is important. And I guess there is a variant of the proposal that includes ReversibleCollection and ReversibleSet and is binary compatible. Yes, the source incompatibilities with the types seem to involve type inference (e.g., use of var choosing differently based on new types in the library) so it should be possible to make minor source code changes to adjust or override the type that's inferred. On binary compatibility, that comes mostly from the newly introduced methods (reversed, addFirst etc.) and from adding covariant overrides to LinkedHashSet. I guess the "variant" you mention is adding new methods with the new return types (e.g., reversibleEntrySet) instead of covariant overrides. Or was it something else? Now just some of my thoughts about the proposal: - SortedSet.addFirst/.addLast - I think an operation that would be used in situations like: "I know this element should always be greater than any existing element in the set and I will push it to the end which should also verify my assumption" is a perfectly valid operation. So those methods throwing IllegalStateException in case the invariant can't be kept seem perfectly fine to me. - ReversibleCollection.addFirst/.addLast are specified to have void return type. This works for List and Deque which always add element and so have no information to return. OTOH Collection.add is specified to return boolean to indicate whether collection was modified or not, but Set modifies the specification of that method a bit to be: return false or true when Set already contained an element equal to the parameter or not. So ReversibleCollection.addFirst/.addLast could play the same trick. for List(s) and Deque(s) it would always return true, but for ReversibleSet(s) it would return true only if the set didn't contain an element equal to the parameter, so re-positioning of equal element would return false although the collection was modified as a result. Anthony Vanelverdinghe replied to both of these points so I'll follow up in a reply to his message. - Perhaps unrelated to this proposal, but just for completeness, existing Collection interface could be extended with methods like: getAny() and removeAny(). Yes, I think there's something going on here, but the issues lead off in a different direction, which I think would be a distraction from ReversibleCollection. So I'd like to keep this as a separate topic. (But it's not a prohibition against talking about them.) Indeed, I see that Henri Tremblay has coincidentally (?) raised a similar topic, so I'll reply further to his message. s'marks
Re: ReversibleCollection proposal
On Tuesday, April 27, 2021 11:25 CEST, Peter Levart wrote: > Now just some of my thoughts about the proposal: > > - SortedSet.addFirst/.addLast - I think an operation that would be used > in situations like: "I know this element should always be greater than > any existing element in the set and I will push it to the end which > should also verify my assumption" is a perfectly valid operation. So > those methods throwing IllegalStateException in case the invariant can't > be kept seem perfectly fine to me. This was raised before and addressed by Stuart in [0]: "An alternative as you suggest might be that SortedSet::addFirst/addLast could throw something like IllegalStateException if the element is wrongly positioned. (Deque::addFirst/addLast will throw ISE if the addition would exceed a capacity restriction.) This seems error-prone, though, and it's easier to understand and specify that these methods simply throw UOE unconditionally. If there's a good use case for the alternative I'd be interested in hearing it though." > - ReversibleCollection.addFirst/.addLast are specified to have void > return type. This works for List and Deque which always add element and > so have no information to return. OTOH Collection.add is specified to > return boolean to indicate whether collection was modified or not, but > Set modifies the specification of that method a bit to be: return false > or true when Set already contained an element equal to the parameter or > not. So ReversibleCollection.addFirst/.addLast could play the same > trick. for List(s) and Deque(s) it would always return true, but for > ReversibleSet(s) it would return true only if the set didn't contain an > element equal to the parameter, so re-positioning of equal element would > return false although the collection was modified as a result. If addFirst/addLast were to return boolean, Deque would no longer compile due to its existing methods being incompatible with the new ones. > Regards, Peter Kind regards, Anthony [0] https://mail.openjdk.java.net/pipermail/core-libs-dev/2021-April/076518.html
ReversibleCollection proposal
Hi,
Not sure if this will end up in the right mailing list thread but let's see.
I just read quickly the proposal and it made me think about another common
issue. I wonder if we could tackle it as well.
I will call it the "find the first element when there is only one" problem.
It happens on unordered collections like a HashSet. It forces to do
Set s = new HashSet<>();
if (s.size() == 1) {
return s.iterator().next();
// or
return s.stream().findFirst().get();
}
Which is a lot of ugliness and object instantiation just to get the first
element.
I would be nice to have a public T findFirst() directly on Iterable.
With a default implementation returning iterator().next(). Things like
ArrayList will want to override will return elementData[0]. It would return
null when the list is empty. Or NoSuchElementException.
It needs to be polished of course but will that be acceptable?
Thanks,
Henri
Re: ReversibleCollection proposal
On 4/27/21 5:50 AM, Stuart Marks wrote:
On 4/25/21 11:09 AM, Peter Levart wrote:
When making this proposition, I was only thinking of how to enable
new yet-nonexistent operations on collections that have order / are
reversible and that the code calling these methods would already
knows that it is dealing with ordered / reversible collections. I
wasn't thinking about how to prevent mistakes like passing unordered
collection to code that expects ordered / reversible collection. This
can only be solved in two ways. The way immutability of collections
is solved (throw exception in runtime when requesting operation that
makes no sense in unordered collection) or by introducing new type -
ReversibleCollection that solves this in compile time. So I take back
my vote for suggestion to introduce methods like getFirst(),
removeFirst() that would return arbitrary element. There's still a
possibility for those methods to throw at runtime though. But I don't
know whether this would be so nicely accepted as immutability was. WDYT?
Consider some collection implementation X that has some semantics and
a suite of operations that support those semantics. An implementation
can throw UnsupportedOperationException if for some reason that
operation doesn't make sense for the implementation, but fundamentally
that implementation still has "X-ness".
Look at Arrays.asList for example. It's backed by an array, so add and
remove operations aren't supported. But it's still fundamentally a
List in that it has N elements, is ordered, the elements are numbered
from 0 to N-1, sublists can be obtained between two arbitrary indexes,
its ListIterator supports iteration in both directions, it has a clear
and useful definition for equals() and hashCode(), etc.
Similarly, an unmodifiable List is still a List.
Now consider adding {add,get,remove}{First,Last} methods to the
Collection interface. Collection doesn't have any semantics for these
methods itself, so we're hoping that there is some sensible mapping
from these methods to appropriate operations on Collections
implementations or subinterfaces.
* Presumably for unordered collections like HashSet, all of these
methods would be left to throw UOE.
* A queue has a head and a tail, so perhaps these are mapped to first
and last, respectively, and Queue would support addLast and
removeFirst but not addFirst and removeLast. But that wouldn't work
for PriorityQueue.
* A stack has a "top": the most recently pushed element. Does the
stack top correspond to the first or the last? It could be either --
in fact, in the JDK, for Stack the top is the last element but for
Deque the top is the first element.
* For some other ordered collection, who knows what a reasonable
mapping would be?
This approach feels backwards to me. Instead of starting from an
abstraction that has strong semantics and then applying all (or at
least most) of the applicable methods, we're starting with a suite of
methods and looking around for relationships to a variety of
abstractions that might or might not have much in common. That seems
like a recipe for a bad API to me.
s'marks
Right, I'm persuaded. Now if only the problems of transition to the
usage of new type that Remi is worried about were mild enough. Source
(in)compatibility is not that important if workarounds exist that are
also backwards source compatible so that the same codebase can be
compiled with different JDKs. Binary compatibility is important. And I
guess there is a variant of the proposal that includes
ReversibleCollection and ReversibleSet and is binary compatible.
Now just some of my thoughts about the proposal:
- SortedSet.addFirst/.addLast - I think an operation that would be used
in situations like: "I know this element should always be greater than
any existing element in the set and I will push it to the end which
should also verify my assumption" is a perfectly valid operation. So
those methods throwing IllegalStateException in case the invariant can't
be kept seem perfectly fine to me.
- ReversibleCollection.addFirst/.addLast are specified to have void
return type. This works for List and Deque which always add element and
so have no information to return. OTOH Collection.add is specified to
return boolean to indicate whether collection was modified or not, but
Set modifies the specification of that method a bit to be: return false
or true when Set already contained an element equal to the parameter or
not. So ReversibleCollection.addFirst/.addLast could play the same
trick. for List(s) and Deque(s) it would always return true, but for
ReversibleSet(s) it would return true only if the set didn't contain an
element equal to the parameter, so re-positioning of equal element would
return false although the collection was modified as a result.
- Perhaps unrelated to this proposal, but just for completeness,
existing Collection interface could be extended
Re: ReversibleCollection proposal
On 4/25/21 11:09 AM, Peter Levart wrote:
When making this proposition, I was only thinking of how to enable new
yet-nonexistent operations on collections that have order / are reversible and that
the code calling these methods would already knows that it is dealing with ordered /
reversible collections. I wasn't thinking about how to prevent mistakes like passing
unordered collection to code that expects ordered / reversible collection. This can
only be solved in two ways. The way immutability of collections is solved (throw
exception in runtime when requesting operation that makes no sense in unordered
collection) or by introducing new type - ReversibleCollection that solves this in
compile time. So I take back my vote for suggestion to introduce methods like
getFirst(), removeFirst() that would return arbitrary element. There's still a
possibility for those methods to throw at runtime though. But I don't know whether
this would be so nicely accepted as immutability was. WDYT?
Consider some collection implementation X that has some semantics and a suite of
operations that support those semantics. An implementation can throw
UnsupportedOperationException if for some reason that operation doesn't make sense
for the implementation, but fundamentally that implementation still has "X-ness".
Look at Arrays.asList for example. It's backed by an array, so add and remove
operations aren't supported. But it's still fundamentally a List in that it has N
elements, is ordered, the elements are numbered from 0 to N-1, sublists can be
obtained between two arbitrary indexes, its ListIterator supports iteration in both
directions, it has a clear and useful definition for equals() and hashCode(), etc.
Similarly, an unmodifiable List is still a List.
Now consider adding {add,get,remove}{First,Last} methods to the Collection
interface. Collection doesn't have any semantics for these methods itself, so we're
hoping that there is some sensible mapping from these methods to appropriate
operations on Collections implementations or subinterfaces.
* Presumably for unordered collections like HashSet, all of these methods would be
left to throw UOE.
* A queue has a head and a tail, so perhaps these are mapped to first and last,
respectively, and Queue would support addLast and removeFirst but not addFirst and
removeLast. But that wouldn't work for PriorityQueue.
* A stack has a "top": the most recently pushed element. Does the stack top
correspond to the first or the last? It could be either -- in fact, in the JDK, for
Stack the top is the last element but for Deque the top is the first element.
* For some other ordered collection, who knows what a reasonable mapping would
be?
This approach feels backwards to me. Instead of starting from an abstraction that
has strong semantics and then applying all (or at least most) of the applicable
methods, we're starting with a suite of methods and looking around for relationships
to a variety of abstractions that might or might not have much in common. That seems
like a recipe for a bad API to me.
s'marks
Re: ReversibleCollection proposal
On 4/23/21 8:33 AM, Stuart Marks wrote: This is what I intended anyway, ie that its OK for "first" to work on an unordered collection, just that addFirst() has very weak semantics wrt first-ness. "Ensures that this collection contains the specified element(optional operation). This has the same basic behaviour as add(E), but implementations may choose to add the element in first position if they have some kind of guarantee of ordering. An exception should not be thrown unless add(E) would also have thrown the exception." What seems to be going on here is that people want to add generality by promoting this set of methods from ReversibleCollection up to Collection. Unfortunately, the only way to do so is to make the specification so loose that the semantics are destroyed. Having these methods on Collection could lead to a situation where calling addFirst and then getFirst might result in getFirst returning a different element from what was passed to addFirst. This doesn't make any sense for methods that have "first" in the name. When making this proposition, I was only thinking of how to enable new yet-nonexistent operations on collections that have order / are reversible and that the code calling these methods would already knows that it is dealing with ordered / reversible collections. I wasn't thinking about how to prevent mistakes like passing unordered collection to code that expects ordered / reversible collection. This can only be solved in two ways. The way immutability of collections is solved (throw exception in runtime when requesting operation that makes no sense in unordered collection) or by introducing new type - ReversibleCollection that solves this in compile time. So I take back my vote for suggestion to introduce methods like getFirst(), removeFirst() that would return arbitrary element. There's still a possibility for those methods to throw at runtime though. But I don't know whether this would be so nicely accepted as immutability was. WDYT? Peter
Re: ReversibleCollection proposal
On Fri, 23 Apr 2021 at 07:33, Stuart Marks wrote: > On 4/22/21 8:36 AM, Stephen Colebourne wrote: > Having these methods on Collection could lead to a situation where calling > addFirst > and then getFirst might result in getFirst returning a different element from > what > was passed to addFirst. This doesn't make any sense for methods that have > "first" in > the name. FWIW, I'm comfortable with that weirdness. The method could be called addPreferFirst() but that is a bit of a mouthful. I'd also note that it is much easier for developers of other Collection implementations to add a method with a matching name than it is to implement a new interface. Even libraries maintaining compatibility with Java 5 could do that. Your proposal has a similar issue BTW - addFirst() on a SortedSet. Your proposal is to throw UnsupportedOperationException, but I (like Remi) think that isn't a good answer when UnsupportedOperationException in collections is usually about immutability. It is a natural problem of the domain that adding first when the implementation is sorted is going to be confusing. I am simply suggesting embracing the weirdness, rather than trying to exception your way out of it. Stephen
Re: ReversibleCollection proposal
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. This is a gigantic overstatement of the issue. It is true that an API *in the JDK* as a practical matter cannot change a Collection parameter to ReversibleCollection, because it will break any callers that are currently passing Collection. The same is true of any library APIs where compatibility is a concern. However, it can be quite useful in many contexts to use ReversibleCollection as a parameter. Newly introduced APIs can use ReversibleCollection. Certain APIs that consume List could reasonably be adjusted to consume a ReversibleCollection instead. (More likely an overload would probably be added in order to preserve binary compatibility.) In contexts where compatibility across maintenance boundaries is not an issue -- that is, where APIs can be changed incompatibly by updating all callers -- it's easy to imagine a variety of scenarios where a List or Collection parameter can usefully be adjusted to ReversibleCollection. 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. We're not actually disagreeing. Many applications and libraries *do* use only the collections in the JDK. It is probably also true that other collection libraries are popular and are *also* used in many places. Non-JDK collections libraries benefit, because any List, SortedSet, and Deque implementations provided by these libraries are automatically retrofitted to implement ReversibleCollection. 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. Sure, this is vacuously true. It doesn't seem to be an argument against ReversibleCollection. 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. Ah, now you're talking about cost vs. benefit. Thus, you must agree that ReversibleCollection/ReversibleSet is a valid concept! It's premature to make a decision based on costs and benefits -- really, risks of incompatibilities. I've done some preliminary searching and what I've found so far is promising; the risk of incompatibilities seems low. Additional searching might reveal information that changes the situation. s'marks
Re: ReversibleCollection proposal
On 4/22/21 8:36 AM, Stephen Colebourne wrote:
On Thu, 22 Apr 2021 at 13:58, Remi Forax wrote:
I would like to preserve the invariant that, when calling a method on a
Collection/iterator, an UnsupportedOperationException only occurs when trying
to mutate that collection.
If we are ok with that, this means that addFirst can not be a default method of
Collection.
This implementation meets the invariant:
public interface Collection {
default void addFirst(E e) { add(e); }
default E getFirst() { return iterator().next(); }
default E removeFirst() {
var i = iterator(); i.next();
i.remove();
}
}
This is what I intended anyway, ie that its OK for "first" to work on
an unordered collection, just that addFirst() has very weak semantics
wrt first-ness.
"Ensures that this collection contains the specified element(optional
operation). This has the same basic behaviour as add(E), but
implementations may choose to add the element in first position if
they have some kind of guarantee of ordering. An exception should not
be thrown unless add(E) would also have thrown the exception."
What seems to be going on here is that people want to add generality by promoting
this set of methods from ReversibleCollection up to Collection. Unfortunately, the
only way to do so is to make the specification so loose that the semantics are
destroyed.
Having these methods on Collection could lead to a situation where calling addFirst
and then getFirst might result in getFirst returning a different element from what
was passed to addFirst. This doesn't make any sense for methods that have "first" in
the name.
It seems like there's some other use case that people have in mind, such as "get an
arbitrary element from this collection". The obvious way to implement this is
iterator().next() which gets the "first" element from the iteration and so people
are latching onto the name "getFirst". But let's not confuse the "first" element in
a semantic ordering with the "first" element returned by an iterator. They're distinct.
s'marks
Re: ReversibleCollection proposal
On Thu, 22 Apr 2021 at 13:58, Remi Forax wrote:
> I would like to preserve the invariant that, when calling a method on a
> Collection/iterator, an UnsupportedOperationException only occurs when trying
> to mutate that collection.
> If we are ok with that, this means that addFirst can not be a default method
> of Collection.
This implementation meets the invariant:
public interface Collection {
default void addFirst(E e) { add(e); }
default E getFirst() { return iterator().next(); }
default E removeFirst() {
var i = iterator(); i.next();
i.remove();
}
}
This is what I intended anyway, ie that its OK for "first" to work on
an unordered collection, just that addFirst() has very weak semantics
wrt first-ness.
"Ensures that this collection contains the specified element(optional
operation). This has the same basic behaviour as add(E), but
implementations may choose to add the element in first position if
they have some kind of guarantee of ordering. An exception should not
be thrown unless add(E) would also have thrown the exception."
Stephen
Re: ReversibleCollection proposal
- Mail original - > De: "Stuart Marks" > À: "Remi Forax" > Cc: "core-libs-dev" > Envoyé: Mercredi 21 Avril 2021 19:38:23 > Objet: Re: ReversibleCollection proposal > On 4/19/21 4:05 PM, fo...@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 Rev
Re: ReversibleCollection proposal
- Mail original -
> De: "Stephen Colebourne"
> À: "core-libs-dev"
> Envoyé: Jeudi 22 Avril 2021 00:14:10
> Objet: Re: ReversibleCollection proposal
> On Wed, 21 Apr 2021 at 18:39, Stuart Marks wrote:
>> 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.
>
> Having thought about this for a few days my "interesting thought" is
> that adding a `ReversibleCollection` interface and adding additional
> methods can be orthogonal choices.
>
> Specifically, I do rather like Peter's suggestion of adding more
> methods to Collection. Adding these methods would be pretty useful in
> general and give the proposed change much greater reach:
>
> public interface Collection {
> default void addFirst(E e) { throw new
> UnsupportedOperationException(); }
> default E getFirst() { return iterator().next(); }
> default E removeFirst() { var i = iterator(); i.next();
> i.remove(); }
> }
>
> My view being that every collection has some notion of "first", even
> if that notion is "undefined". If that was the only change made, I
> think that would be a good move forward.
>
> These would be the various options:
>
> - 7 new methods on ReversibleCollection (Stuart's suggestion)
> - 7 new methods on Collection, no ReversibleCollection (Peter's suggestion)
> - 3 new methods on Collection, no ReversibleCollection (my suggestion #1)
> - 3 new methods on Collection, 4 methods on ReversibleCollection (my
> suggestion #2)
> - 7 new methods on Collection, 0 methods on ReversibleCollection (my
> suggestion #3)
>
> FWIW, I think I prefer my suggestion #2
I would like to preserve the invariant that, when calling a method on a
Collection/iterator, an UnsupportedOperationException only occurs when trying
to mutate that collection.
If we are ok with that, this means that addFirst can not be a default method of
Collection.
getFirst() on Collection is a nice addition has I already said.
And i'm not a big fan of removeFirst() on Collection, mostly because i think
that the sequence this.iterator + next() + remove() is pretty rare on a
Collection or a Set
(i would also like to keep the invariant that Set and Collection have the same
set of methods).
So addFirst/addLast/removeFirst/removeLast should be added to
SortedSet/NavigableSet, Deque, List and LinkedHashMap (if there are not already
present).
For reverse/descending, I still prefer to have descendingSet() on Set and
descendingList() on List, the same way we have keySet() or subList() (the
method names have the resulting interface has suffix).
This also solve the issue with LinkedList implementing both List and Deque.
I believe that the cost of introducing ReversibleCollection is too high
- it's not source backward compatible change
- replacing Collection/Set by ReversibleCollection/ReversibleSet has return
type of an existing interface/class is not a source backward compatible change
- to be able to use ReversibleCollection parameter of a public method of a
library, we have to wait the whole Java ecosystem to have been updated to
implement ReversibleCollection (Python 2/3 like migration).
>
> Stephen
Rémi
Re: [External] : Re: ReversibleCollection proposal
- Mail original -
> De: "Stuart Marks"
> À: "Remi Forax"
> Cc: "core-libs-dev"
> Envoyé: Mercredi 21 Avril 2021 20:53:25
> Objet: Re: [External] : Re: ReversibleCollection proposal
> On 4/19/21 2:01 PM, Remi Forax wrote:
>> - Mail original -
>> Thinking a little bit about your proposal,
>> introducing an interface right in the middle of a hierarchy is not a backward
>> compatible change
>> (you have an issue when the compiler has to use the lowest upper bound).
>>
>> By example
>>void m(List> list) { ... }
>>
>>var list = List.of(new LinkedHashSet(), List.of("foo"));
>>m(list); // does not compile anymore
>>
>> currently the type of list is List> but with your
>> proposal,
>> the type will be List>
>
> Yes, interesting. Not too difficult to fix though. Either change the method
> declaration to
>
> void m(List> list)
>
> or change the 'var' to an explicit declaration of List>.
or specify the type argument in between '.' and 'of'
var list = List.>of(new LinkedHashSet(),
List.of("foo"));
anyway, the issue here is that adding ReversibleCollection is a source breaking
change,
which significantly raises the bar to add this interface.
>
> s'marks
Rémi
Re: ReversibleCollection proposal
On 4/22/21 12:14 AM, Stephen Colebourne wrote:
public interface Collection {
default E getFirst() { return iterator().next(); }
Searching for ".iterator().next()" yields 74 matches in JDK sources...
Peter
Re: ReversibleCollection proposal
On Wed, 21 Apr 2021 at 18:39, Stuart Marks wrote:
> 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.
Having thought about this for a few days my "interesting thought" is
that adding a `ReversibleCollection` interface and adding additional
methods can be orthogonal choices.
Specifically, I do rather like Peter's suggestion of adding more
methods to Collection. Adding these methods would be pretty useful in
general and give the proposed change much greater reach:
public interface Collection {
default void addFirst(E e) { throw new
UnsupportedOperationException(); }
default E getFirst() { return iterator().next(); }
default E removeFirst() { var i = iterator(); i.next();
i.remove(); }
}
My view being that every collection has some notion of "first", even
if that notion is "undefined". If that was the only change made, I
think that would be a good move forward.
These would be the various options:
- 7 new methods on ReversibleCollection (Stuart's suggestion)
- 7 new methods on Collection, no ReversibleCollection (Peter's suggestion)
- 3 new methods on Collection, no ReversibleCollection (my suggestion #1)
- 3 new methods on Collection, 4 methods on ReversibleCollection (my
suggestion #2)
- 7 new methods on Collection, 0 methods on ReversibleCollection (my
suggestion #3)
FWIW, I think I prefer my suggestion #2
Stephen
Re: [External] : Re: ReversibleCollection proposal
On 4/19/21 2:01 PM, Remi Forax wrote:
- Mail original -
Thinking a little bit about your proposal,
introducing an interface right in the middle of a hierarchy is not a backward
compatible change
(you have an issue when the compiler has to use the lowest upper bound).
By example
void m(List> list) { ... }
var list = List.of(new LinkedHashSet(), List.of("foo"));
m(list); // does not compile anymore
currently the type of list is List> but with your proposal, the type
will be List>
Yes, interesting. Not too difficult to fix though. Either change the method
declaration to
void m(List> list)
or change the 'var' to an explicit declaration of List>.
s'marks
Re: ReversibleCollection proposal
On 4/19/21 4:05 PM, fo...@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
Re: ReversibleCollection proposal
- Mail original - > De: "Stuart Marks" > À: "Remi Forax" > Cc: "core-libs-dev" > Envoyé: Lundi 19 Avril 2021 17:41:11 > Objet: Re: ReversibleCollection proposal > On 4/17/21 9:49 AM, Remi Forax wrote: >> I think the analysis is spot on but I don't think the proposed solution is >> the >> right one. >> >> Introducing a new interface (two in this case) has a really huge cost and in >> this case, i've trouble to see why i will want to write a method that takes a >> ReversibleCollection as parameter, ReversibleCollection as a type does not >> seem >> to be useful. About the cost of introducing a new collection interface, it >> means that we also have to update all emptyXXX, singleXXX, uncheckedXXX with >> a >> new interface, and that only for the JDK. Every libraries that proxy >> collections has also to be updated to take care of this new type, otherwise >> the >> integration with an application that uses this new type and the library is >> not >> seamless anymore. > > Hi Remi, > > Thanks for looking at this. There are several issues intertwined here, so > let's > try > to break it down. > > There are a bunch of factory methods emptyX, singletonX, etc. that give > instances of > particular types. As Tagir noted, List is a ReversibleCollection, so you can > just > use emptyList or List.of or whatever if you need an instance of > ReversibleCollection. Also, SortedSet/NavigableSet are ReversibleSets, so if > you > need an empty ReversibleSet, you can use Collections.emptyNavigableSet. > There's > no > singletonNavigableSet, but you could do > > Collections.unmodifiableNavigableSet(new TreeSet<>(List.of(x))) > > which is a bit of a mouthful, but it's possible. (The fact that there's no > Collections.singletonNavigableSet may mean this use case is so narrow that few > people really needed it.) > > As for the wrappers, synchronizedX and checkedX are mostly disused, so I don't > see a > need to provide those wrappers. Having unmodifiable RC and RS is probably > useful, so > I could see adding those. That's a certain amount of work, but not a > tremendous > cost. It's a shame that checkedX are not used more, at least in tests, because it's a simple way to know if a method will work with the new generics of Valhalla (it's the same semantics). Anyway, the problem is not only for the JDK, but for all libraries like guava, eclipse collections, etc and also JVM languages that provides a collection interopt like Clojure or Scala. > >> All these methods can be introduced has default methods on the existing >> collection interfaces, there is no need of a special interface (or two) for >> that. > > Clearly it's possible to get by without new interfaces. After all the > collections > framework has gotten by without them for 20+ years already. It's certainly > possible > to fill out the individual interfaces (List, Deque, Sorted/NavSet) and classes > (LinkedHashSet, LinkedHashMap) with methods that are all similar to each > other, > and > that would be useful. Or as Peter Levart pointed out, we could push all of > them > up > to Collection and write the specs in a loose enough way to encompass even > unordered > collections. > > Any of those alternatives (do nothing, add individual methods, add > loosely-spec'd > methods to Collection) are *possible* to do. However, I think you know how > minimal > we are with the JDK APIs, and we wouldn't have proposed new interfaces without > good > cause. Thus, I think introducing new *types* here is useful, for the following > reasons. > > * 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. > > * These semantics appear across a broad range of
Re: ReversibleCollection proposal
- Mail original -
> De: "Stuart Marks"
> À: "core-libs-dev"
> Envoyé: Vendredi 16 Avril 2021 19:40:55
> Objet: ReversibleCollection proposal
> This is a proposal to add a ReversibleCollection interface to the Collections
> Framework. I'm looking for comments on overall design before I work on
> detailed
> specifications and tests. Please send such comments as replies on this email
> thread.
>
> Here's a link to a draft PR that contains the code diffs. It's prototype
> quality,
> but it should be good enough to build and try out:
>
> https://github.com/openjdk/jdk/pull/3533
>
> And here's a link to a class diagram showing the proposed additions:
>
>
> https://cr.openjdk.java.net/~smarks/ReversibleCollection/ReversibleCollectionDiagram.pdf
>
> Thanks,
>
> s'marks
Thinking a little bit about your proposal,
introducing an interface right in the middle of a hierarchy is not a backward
compatible change
(you have an issue when the compiler has to use the lowest upper bound).
By example
void m(List> list) { ... }
var list = List.of(new LinkedHashSet(), List.of("foo"));
m(list); // does not compile anymore
currently the type of list is List> but with your proposal,
the type will be List>
Rémi
Re: ReversibleCollection proposal
On 4/17/21 9:49 AM, Remi Forax wrote:
I think the analysis is spot on but I don't think the proposed solution is the
right one.
Introducing a new interface (two in this case) has a really huge cost and in
this case, i've trouble to see why i will want to write a method that takes a
ReversibleCollection as parameter, ReversibleCollection as a type does not seem
to be useful. About the cost of introducing a new collection interface, it
means that we also have to update all emptyXXX, singleXXX, uncheckedXXX with a
new interface, and that only for the JDK. Every libraries that proxy
collections has also to be updated to take care of this new type, otherwise the
integration with an application that uses this new type and the library is not
seamless anymore.
Hi Remi,
Thanks for looking at this. There are several issues intertwined here, so let's try
to break it down.
There are a bunch of factory methods emptyX, singletonX, etc. that give instances of
particular types. As Tagir noted, List is a ReversibleCollection, so you can just
use emptyList or List.of or whatever if you need an instance of
ReversibleCollection. Also, SortedSet/NavigableSet are ReversibleSets, so if you
need an empty ReversibleSet, you can use Collections.emptyNavigableSet. There's no
singletonNavigableSet, but you could do
Collections.unmodifiableNavigableSet(new TreeSet<>(List.of(x)))
which is a bit of a mouthful, but it's possible. (The fact that there's no
Collections.singletonNavigableSet may mean this use case is so narrow that few
people really needed it.)
As for the wrappers, synchronizedX and checkedX are mostly disused, so I don't see a
need to provide those wrappers. Having unmodifiable RC and RS is probably useful, so
I could see adding those. That's a certain amount of work, but not a tremendous cost.
All these methods can be introduced has default methods on the existing
collection interfaces, there is no need of a special interface (or two) for
that.
Clearly it's possible to get by without new interfaces. After all the collections
framework has gotten by without them for 20+ years already. It's certainly possible
to fill out the individual interfaces (List, Deque, Sorted/NavSet) and classes
(LinkedHashSet, LinkedHashMap) with methods that are all similar to each other, and
that would be useful. Or as Peter Levart pointed out, we could push all of them up
to Collection and write the specs in a loose enough way to encompass even unordered
collections.
Any of those alternatives (do nothing, add individual methods, add loosely-spec'd
methods to Collection) are *possible* to do. However, I think you know how minimal
we are with the JDK APIs, and we wouldn't have proposed new interfaces without good
cause. Thus, I think introducing new *types* here is useful, for the following reasons.
* 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.
* 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.
* It's useful to have a new type for parameters in APIs. There are times when one
wants to accept something like a List -or- a LinkedHashSet. Typically one would
accept a Collection and then write a spec with hedging as above ("the argument
collection must have a defined ordering"). But this also allows bugs, for example if
somebody accidentally passes a HashSet. Having ReversibleCollection helps 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.
* It's a useful interface for new collection implementations. There are data
structures that are ordered, double-ended, and reversible, but for which
implementing List is too onerous. Supporting int indexes in various List APIs is
where stumbling blocks usually occur. I note that the LinkedHashMap view collections
are examples of this that already exist in the prototype code. (Other possibilities
might be something like SpinedBuffer or chunked linked lists.)
In general, I agree that there should be strict criteria for introducing new
interfaces into collections, but I think this proposal meets them.
s'marks
Re: ReversibleCollection proposal
On 4/18/21 9:51 AM, Peter Levart wrote:
public interface Collection {
default Collection reversed() { return this; }
default void addFirst(E e) { throw new
UnsupportedOperationException(); }
default void addLast(E e) { throw new
UnsupportedOperationException(); }
default E getFirst() { return iterator().next(); }
default E getLast() { return iterator().next(); }
default E removeFirst() { var i = iterator(); i.next();
i.remove(); }
default E removeLast() { var i = iterator(); i.next();
i.remove(); }
}
List, SortedSet and Deque would of course override them with
implementations as proposed. Would anything be wrong with above
implementations?
Yeah, I forgot about the Queue. Would something like the following be
too much throwing?
public interface Queue ... {
default Queue reversed() { throw new
UnsupportedOperationException(); }
default void addFirst(E e) { throw new
UnsupportedOperationException(); }
default void addLast(E e) { add(e); }
default E getFirst() { return element(); }
default E getLast() { throw new UnsupportedOperationException(); }
default E removeFirst() { return remove(); }
default E removeLast() { throw new
UnsupportedOperationException(); }
}
Peter
Re: ReversibleCollection proposal
On 4/18/21 9:51 AM, Peter Levart wrote:
public interface Collection {
default Collection reversed() { return this; }
default void addFirst(E e) { throw new
UnsupportedOperationException(); }
default void addLast(E e) { throw new
UnsupportedOperationException(); }
For unordered collections this could as well be:
default void addFirst(E e) { return add(e); }
default void addLast(E e) { return add(e); }
As the iteration of such modified unordered collection would not
guarantee any order. SortedSet would of course override them with
throwing methods.
default E getFirst() { return iterator().next(); }
default E getLast() { return iterator().next(); }
default E removeFirst() { var i = iterator(); i.next();
i.remove(); }
default E removeLast() { var i = iterator(); i.next();
i.remove(); }
}
Re: ReversibleCollection proposal
A word for Remi's concern...
While it is good that List (and SortedSet and Deque) extend
ReversibleCollection in the proposal, it is a pity the same is not true
for Set and Queue. If Set and Queue could also be
ReversibleCollection(s), then we would not need ReversibleCollection at
all and the methods could be added to Collection itself.
So let's see them:
public interface Collection {
default Collection reversed() { return this; }
default void addFirst(E e) { throw new
UnsupportedOperationException(); }
default void addLast(E e) { throw new
UnsupportedOperationException(); }
default E getFirst() { return iterator().next(); }
default E getLast() { return iterator().next(); }
default E removeFirst() { var i = iterator(); i.next();
i.remove(); }
default E removeLast() { var i = iterator(); i.next();
i.remove(); }
}
List, SortedSet and Deque would of course override them with
implementations as proposed. Would anything be wrong with above
implementations?
Collection is an Iterable which allows to iterate over elements. We can
still iterate a Collection that does not define the order of iteration.
We can not rely on such undefined order in our code, but we can still
iterate it. Stream.findFirst() is equivalent to Stream.findAny() for
unordered streams. So why would Collection.getFirst() and
Collection.getLast() not be equivalent (to Collection.getAny()) for
unordered Collections? Why would coll.reversed() be any different than
coll for unordered collections?
Peter
On 4/18/21 3:53 AM, Tagir Valeev wrote:
Hello, Remi!
On Sat, Apr 17, 2021 at 11:50 PM Remi Forax wrote:
Introducing a new interface (two in this case) has a really huge cost and in
this case, i've trouble to see why i will want to write a method that takes a
ReversibleCollection as parameter, ReversibleCollection as a type does not seem
to be useful. About the cost of introducing a new collection interface, it
means that we also have to update all emptyXXX, singleXXX, uncheckedXXX with a
new interface, and that only for the JDK. Every libraries that proxy
collections has also to be updated to take care of this new type, otherwise the
integration with an application that uses this new type and the library is not
seamless anymore.
Note that in Stuart's proposal, java.util.List extends
ReversibleCollection. So, existing emptyList() and singletonList()
also return ReversibleCollection and no new methods are necessary
here. Probably unmodifiableReversibleSet could be useful as a
LinkedHashSet wrapper. On the other hand, we don't have, e.g.
checkedDeque or synchronizedDeque, and it looks like nobody complains.
So probably it's not always necessary to create a wrapper for every
single collection interface.
I fully agree that having a way to reverse a collection is a powerful API
point, as Brian said, it's better to reverse the collection and then ask for a
stream than providing a method reverseStream (and this is true for iterators or
views like keySet/entrySet/values or subList too). Several people also ask to
have findLast() on Stream, using list.descendingList().findFirst() will be
equivalent.
A dedicated findLast() would be a great addition to reversible
streams! It could short-circuit for reversible stream
(reverse().findFirst()) and use reduce((a, b) -> b) for non-reversible
(so intermediate buffering is not necessary). I've found 8 Stream API
call chains ending with .reduce((a, b) -> b) in our sources. Clearly,
some of them could short-circuit, as the source is potentially
reversible (e.g. allAnchors.subList(0,
idx).stream().filter(hasNewName).reduce((x1, x2) -> x2)). Having
dedicated findLast operation would be less error-prone, compared to
creating the stream as reversed().stream(), as you don't have to think
whether the stream is reversible or not. If you accidentally add a
non-reversible operation, you'll miss the optimization but not
correctness.
With best regards,
Tagir Valeev.
Re: ReversibleCollection proposal
Hello, Remi! On Sat, Apr 17, 2021 at 11:50 PM Remi Forax wrote: > Introducing a new interface (two in this case) has a really huge cost and in > this case, i've trouble to see why i will want to write a method that takes a > ReversibleCollection as parameter, ReversibleCollection as a type does not > seem to be useful. About the cost of introducing a new collection interface, > it means that we also have to update all emptyXXX, singleXXX, uncheckedXXX > with a new interface, and that only for the JDK. Every libraries that proxy > collections has also to be updated to take care of this new type, otherwise > the integration with an application that uses this new type and the library > is not seamless anymore. Note that in Stuart's proposal, java.util.List extends ReversibleCollection. So, existing emptyList() and singletonList() also return ReversibleCollection and no new methods are necessary here. Probably unmodifiableReversibleSet could be useful as a LinkedHashSet wrapper. On the other hand, we don't have, e.g. checkedDeque or synchronizedDeque, and it looks like nobody complains. So probably it's not always necessary to create a wrapper for every single collection interface. > I fully agree that having a way to reverse a collection is a powerful API > point, as Brian said, it's better to reverse the collection and then ask for > a stream than providing a method reverseStream (and this is true for > iterators or views like keySet/entrySet/values or subList too). Several > people also ask to have findLast() on Stream, using > list.descendingList().findFirst() will be equivalent. A dedicated findLast() would be a great addition to reversible streams! It could short-circuit for reversible stream (reverse().findFirst()) and use reduce((a, b) -> b) for non-reversible (so intermediate buffering is not necessary). I've found 8 Stream API call chains ending with .reduce((a, b) -> b) in our sources. Clearly, some of them could short-circuit, as the source is potentially reversible (e.g. allAnchors.subList(0, idx).stream().filter(hasNewName).reduce((x1, x2) -> x2)). Having dedicated findLast operation would be less error-prone, compared to creating the stream as reversed().stream(), as you don't have to think whether the stream is reversible or not. If you accidentally add a non-reversible operation, you'll miss the optimization but not correctness. With best regards, Tagir Valeev.
Re: ReversibleCollection proposal
> Adding a REVERSIBLE characteristic to spliterators is easy enough
Actually not. There are already tons of delegating spliterators in the
wild, and many of them delegate characteristics in one or another way.
Usually, it's like 'copy all the source characteristics except A and
B' (i.e. `source.characteristics() & (~(A|B))`), so if we introduce a
new one, some existing spliterators may start reporting it without
actually providing the claimed functionality. As the author of the
library that contains dozens of custom spliterator, I think, this is
the largest problem. I don't buy an infinite streams argument, as
`sorted()` is equally not applicable to infinite streams, yet it's
possible to call it (btw reversed() after sorted() could be optimized,
even if the original source is not reversible). Also, in fact,
infinite streams are not widely used. I think, 99% of real-life
streams start from collection, array, or integral range. Yes, my idea
was to fall back to drain-line implementation.
> But, Stuart's proposal gives us much of this with less fuss. IF a collection
> is reversible, you can just say
>
> c.reversed().stream()
>
> and off you go, plus a similar method for arrays (Arrays.reversedStream).
> Given that, what is the value of pushing this further into stream?
Arrays.reversedStream should be added for Object/int/long/double and
probably for array slices. Also, IntStream.reversedRange, please! And
LongStream.reversedRange. And probably `reversedRangeClosed`. So we
already have 12 methods to add (aside from collections). Adding single
.reversed() to the Stream is a much smaller API surface. Though I
admit that it requires much more work. On the other hand, I believe
(efforts/usefulness) for this feature is much bigger than, say, for
parallel streams.
In StreamEx, I have
public static StreamEx ofReversed(List list)
public static StreamEx ofReversed(T[] array)
(did not bother to add IntStreamEx ofReversed(int[] array) and friends)
the List version just assumes that every list is random access and
does something like IntStream.range(0, size).mapToObj(idx ->
list.get(size - idx - 1))
I've found 16 usages of them in IntelliJ IDEA sources (10 for List and
6 for array), which is not very small, given the fact that only a few
of our developers in our project know/use StreamEx.
I also have three-arg IntStreamEx.range(int startInclusive, int
endExclusive, int step) (and rangeClosed, and the corresponding
LongStreamEx), which can be used for reverse range (with step = -1)
I've found a couple of usages with step = -1 to iterate over a slice
of an array in reverse order. Though step = 2 is more popular.
I also checked the uses of Collections::reverse. There are hundreds of
them. Often it's traversal in tree-like structure through the parent
chain from leaf to root, like Stream.iterate(leaf, Objects::nonNull,
Node::getParent),
then the result is dumped into the list (probably with some
intermediate ops like map(Node::getName)), then reversed to get "from
root to leaf" order. Sometimes the resulting list is just returned (so
it's possible to create
Collectors.toReversedList() to avoid extra reversal step), sometimes
it's converted to an array and returned, sometimes it's
iterated/streamed again. In one case, it's even followed by
left-to-right reduction,
so foldRight is what was actually wanted there.
One more case is a simple parser of the Java stack trace:
String[] lines = stack.split("\n");
List calls =
StreamEx.of(lines).filter(s -> s.startsWith("\tat")).map(method ->
getMethodCall(method, ...)).nonNull().toList();
Collections.reverse(calls);
Here's an example of a stream where reversibility is preserved during
the whole pipeline. It's possible to rewrite it using
StreamEx.ofReversed() (probably the code author was not aware of this
method). But it also could be stack.lines().reversed() (and it's
possible to make String::lines reversible without extra buffering!),
so with the dedicated reversed() method it could be completely lazy.
I also see patterns like fill LinkedHashSet, dump it to the List, then
reverse the list and iterate from it. Clearly, it can benefit from the
Stuart's proposal.
With best regards,
Tagir Valeev.
>
> On 4/17/2021 7:49 AM, Tagir Valeev wrote:
>
> Great proposal, thanks!
>
> It has most functionality from my previous proposal, except the
> ability to iterate LinkedHashSet starting from a specific element.
> Well, probably we can skip this for now.
>
> Some people really want to reverse Streams as well. E. g., the
> corresponding StackOverflow question [1] has 171 upvotes and 200k+
> views. Also, if the stream were reversible, it would be possible to
> implement efficient foldRight/reduceRight operation. See the
> discussion at [2]. It would be nice to explore the possibility of
> extending Stream API to take into account the source reversibility.
> Some existing ordered sources that have no underlying collection (e.g.
> IntStream.range, or Arrays.stream) can be
Re: ReversibleCollection proposal
> I'm also concerned about conflicts over the other method names; something > like addFirst() is a pretty obvious method to add to a custom List > implementation. I haven't seen any, but that doesn't mean there aren't any. > > s'marks The getFirst() and getLast() methods will have collisions. We have both these methods on Eclipse Collections, and thankfully they return the same type. It is possible that someone decided to implement these methods and return Optional.
Re: ReversibleCollection proposal
Hi, Stuart, happy to help. I took a look at Groovy and Kotlin. Groovy has reverse() [1] and Kotlin has reversed() [2] and asReversed() [3] and reverse() [4]. I’m not quite familiar enough with Kotlin to know whether the reversed() method will collide. [1] http://docs.groovy-lang.org/latest/html/groovy-jdk/java/util/List.html#reverse() [2] https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/reversed.html [3] https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/as-reversed.html [4] https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/reverse.html > On Apr 17, 2021, at 2:24 PM, Stuart Marks wrote: > > > > On 4/16/21 3:06 PM, Donald Raab wrote: >> We should be cautious when adding new APIs to existing interfaces. There may >> be libraries which extend JDK types and already have reversed(), >> toReversed() or asReversed() APIs and corresponding interfaces. >> There are OrderedIterable and ReversibleIterable interfaces and asReversed() >> and toReversed() methods in the Eclipse Collections API. > > Hi Don, thanks for looking at the proposal. > > Certainly a lot of care is required when introducing new interfaces, new > methods on existing interfaces, and covariant overrides. I believe the > primary risks are with name clashes and with return type mismatches. > > On name clashes, "reversed" seems to thread the needle well, as I cannot find > any methods with that exact name on Eclipse Collections, Guava, Apache > Commons Collections, or several others. There are methods with similar names, > of course, such as "reverse", "asReversed", and "toReversed" but they > shouldn't cause name conflicts. > > (There might be semantic conflicts, such as creating an reversed copy instead > of a reversed view, but I don't think that can be helped.) > > If there are no name clashes with "reversed", the covariant overrides in the > sub-interfaces won't a problem. The covariant overrides on existing methods > (such as LinkedHashMap.entrySet) are a greater danger, I think. There are a > lot of LinkedHashMap subclasses (several dozen are visible in the Yawkat > browser) but only one had a conflicting override. It's trivially fixable, but > nonetheless it's an incompatibility. > > I'm also concerned about conflicts over the other method names; something > like addFirst() is a pretty obvious method to add to a custom List > implementation. I haven't seen any, but that doesn't mean there aren't any. > > s'marks
Re: ReversibleCollection proposal
On 4/17/21 4:49 AM, Tagir Valeev wrote: Great proposal, thanks! It has most functionality from my previous proposal, except the ability to iterate LinkedHashSet starting from a specific element. Well, probably we can skip this for now. Thanks! And thanks for making that proposal a year ago; the ideas there and in the ensuing discussion clearly informed this proposal. I did spend a bunch of time thinking about the "start from a specific element" case. Certainly it isn't difficult to create an iterator that starts from a specific element and proceeds in either direction. However, it's 2021, and nobody wants to program using Iterators anymore!! :-) Perhaps an obvious extension is a LinkedHashSet subset-view from a particular element to the end (or beginning). This is kind of interesting, however, it leads off into the weeds. That is, the complexity in doing this seemed to outweigh the rest of the proposal, especially for the limited value it supplies, so I've left it aside for now. It's possible to get a stream of LHS elements starting or ending at a particular element though a combination of reversed, takeWhile, and dropWhile. s'marks
Re: ReversibleCollection proposal
On 4/17/21 2:48 AM, Stephen Colebourne wrote:
On Fri, 16 Apr 2021 at 18:41, Stuart Marks wrote:
This is a proposal to add a ReversibleCollection interface to the Collections
Framework. I'm looking for comments on overall design before I work on detailed
specifications and tests. Please send such comments as replies on this email
thread.
I think this could be an interesting addition to the framework.
Great!
# Ordering and Reversibility
Reading this section, it seems like ordering is a more significant
quality than reversibility. Yet the API is named "reversible". That
seems odd, esepcially given the stream characteristic.
I probably could have explained this better in the writeup.
"Reversible" is a stronger concept (i.e., it implies more things) than "Ordered". A
reversible collection is ordered, it is traversable in both directions, both ends
are accessible, and it affords operations at both ends. However, being ordered does
not imply reversibility. For example, a PriorityQueue is ordered, but you can't get
to the tail or iterate in reverse without a bunch of computation.
SortedSet::addFirst and addLast throw UnsupportedOperationException. This is
because
SortedSet's ordering is determined by the comparison method and cannot be
controlled
explicitly.
This seems undesirable. Maybe SortedSet should not implement
reversible/ordered? Maybe they should add to the set but validate
whether they would be in first/last position? Simply allowing users to
get a new instance with a different (eg. reversed) comparator would
meet much of the use case.
This is certainly an unpleasant asymmetry. But this is the Collections Framework; we
should be used to unpleasant asymmetries. :-)
My typical examples of this are: various Map views like entrySet are that elements
can be removed but they cannot be added; elements in Arrays.asList can be set but
not added or removed; CopyOnWriteArrayList is mutable, but its iterators are not; etc.
Of course the presence of asymmetries doesn't justify the addition of more. But
there is a precedent here: collections will implement an interface if they can
support "most" of the operations, and the ones that aren't appropriate will throw
UnsupportedOperationException. That's the precedent I'm following here with
SortedSet (and NavigableSet).
An alternative as you suggest might be that SortedSet::addFirst/addLast could throw
something like IllegalStateException if the element is wrongly positioned.
(Deque::addFirst/addLast will throw ISE if the addition would exceed a capacity
restriction.) This seems error-prone, though, and it's easier to understand and
specify that these methods simply throw UOE unconditionally. If there's a good use
case for the alternative I'd be interested in hearing it though.
Also, SortedSet uses first() and last(), yet the proposed interface
uses getFirst() and getLast().
Deque defines a full set of operations at both ends, including:
{ add, get, remove } x { First, Last }
so it seemed sensible to take that complete set and promote it to
ReversibleCollection.
s'marks
Re: ReversibleCollection proposal
On 4/16/21 3:06 PM, Donald Raab wrote: We should be cautious when adding new APIs to existing interfaces. There may be libraries which extend JDK types and already have reversed(), toReversed() or asReversed() APIs and corresponding interfaces. There are OrderedIterable and ReversibleIterable interfaces and asReversed() and toReversed() methods in the Eclipse Collections API. Hi Don, thanks for looking at the proposal. Certainly a lot of care is required when introducing new interfaces, new methods on existing interfaces, and covariant overrides. I believe the primary risks are with name clashes and with return type mismatches. On name clashes, "reversed" seems to thread the needle well, as I cannot find any methods with that exact name on Eclipse Collections, Guava, Apache Commons Collections, or several others. There are methods with similar names, of course, such as "reverse", "asReversed", and "toReversed" but they shouldn't cause name conflicts. (There might be semantic conflicts, such as creating an reversed copy instead of a reversed view, but I don't think that can be helped.) If there are no name clashes with "reversed", the covariant overrides in the sub-interfaces won't a problem. The covariant overrides on existing methods (such as LinkedHashMap.entrySet) are a greater danger, I think. There are a lot of LinkedHashMap subclasses (several dozen are visible in the Yawkat browser) but only one had a conflicting override. It's trivially fixable, but nonetheless it's an incompatibility. I'm also concerned about conflicts over the other method names; something like addFirst() is a pretty obvious method to add to a custom List implementation. I haven't seen any, but that doesn't mean there aren't any. s'marks
Re: ReversibleCollection proposal
- Mail original -
> De: "Stuart Marks"
> À: "core-libs-dev"
> Envoyé: Vendredi 16 Avril 2021 19:40:55
> Objet: ReversibleCollection proposal
> This is a proposal to add a ReversibleCollection interface to the Collections
> Framework. I'm looking for comments on overall design before I work on
> detailed
> specifications and tests. Please send such comments as replies on this email
> thread.
>
> Here's a link to a draft PR that contains the code diffs. It's prototype
> quality,
> but it should be good enough to build and try out:
>
> https://github.com/openjdk/jdk/pull/3533
>
> And here's a link to a class diagram showing the proposed additions:
>
>
> https://cr.openjdk.java.net/~smarks/ReversibleCollection/ReversibleCollectionDiagram.pdf
>
> Thanks,
>
> s'marks
>
>
> # Ordering and Reversibility
>
>
> A long-standing concept that's been missing from collections is that of the
> positioning, sequencing, or arrangement of elements as a structural property
> of
> a
> collection. (This is sometimes called the "iteration order" of a collection.)
> For
> example, a HashSet is not ordered, but a List is. This concept is mostly not
> manifested in the collections API.
>
> Iterating a collection produces elements one after another in *some* sequence.
> The
> concept of "ordered" determines whether this sequence is defined or whether
> it's
> a
> coincidence of implementation. What does "having an order" mean? It implies
> that
> there is a first element and that each element has a successor. Since
> collections
> have a finite number of elements, it further implies that there is a last
> element
> that has no successor. However, it is difficult to discern whether a
> collection
> has
> a defined order. HashSet generally iterates its elements in the same undefined
> order, and you can't actually tell that it's not a defined order.
>
> Streams do have a notion of ordering ("encounter order") and this is
> preserved,
> where appropriate, through the stream pipeline. It's possible to detect this
> by
> testing whether its spliterator has the ORDERED characteristic. Any collection
> with
> a defined order will have a spliterator with this characteristic. However,
> this
> is
> quite a roundabout way to determine whether a collection has a defined order.
> Furthermore, knowing this doesn't enable any additional operations. It only
> provides
> constraints on the stream's implementations (keeping the elements in order)
> and
> provides stronger semantics for certain operations. For example, findFirst()
> on
> an
> unordered stream is the same as findAny(), but actually finds the first
> element
> if
> the stream is ordered.
>
> The concept of ordering is thus present in the system but is surfaced only in
> a
> fairly indirect way. We can strengthen abstraction of ordering by making a few
> observations and considering their implications.
>
> Given that there is a first element and a last element, the sequence of
> elements
> has
> two ends. It's reasonable to consider operations (add, get, remove) on either
> end.
> Indeed, the Deque interface has a full complement of operations at each end.
> This is
> an oft-requested feature on various other collections.
>
> Each element except for the last has a successor, implying that each element
> except
> for the first has a predecessor. Thus it's reasonable to consider iterating
> the
> elements from first to last or from last to first (that is, in forward or
> reverse
> order). Indeed, the concept of iterating in reverse order appears already in
> bits
> and pieces in particular places around the collections:
>
> - List has indexOf() and lastIndexOf()
> - Deque has removeFirstOccurrence() and removeLastOccurrence()
> - List has a ListIterator with hasPrevious/previous methods
> - Deque and NavigableSet have descendingIterator methods
>
> Given an ordered collection, though, there's no general way to iterate it in
> reverse
> order. Reversed iteration isn't the most common operation, but there are some
> frequent use cases, such as operating on elements in most-recently-added
> order.
> Questions and bug reports about this have come up repeatedly over the years.
>
> Unfortunately, iterating in reverse order is much harder than iterating in
> forward
> order. There are a variety of ways to iterate in forward order. For example,
> given a
> List, one can do any of the following:
>
> for (var e : list) { ... }
> list.forEach(...)
> list.stream()
> list.toArray()
>
> However, to iter
Re: ReversibleCollection proposal
Adding a REVERSIBLE characteristic to spliterators is easy enough, and
as you say, many useful sources can easily provide an efficient reverse
operation. Filtering and mapping can preserve reversibility. The real
question is what to do if someone calls reverse() on a non-reversible
stream. (Finite streams that are not easily reversible can still be
reversed by draining the stream into a buffer, but that's likely
inefficient; infinite streams have no chance.) Should reverse() just
throw when it encounters a source not designed for reversibility? I
don't particularly like the idea of throwing based on a dynamic source
property, but trying to thread ReversibleStream through the static types
is probably worse.
In the "drain" it case, the user can always simulate this manually: call
toArray and get a reversed stream from that (since array-based streams
are trivially reversible.)
I'm not particularly convinced of the value of folding from both
directions. The main value of foldr over foldl in Haskell is that
because of laziness, foldr on infinite lists can work with
short-circuiting combiners, whereas foldl cannot. In strict languages,
this benefit is not present, making the marginal value of foldr over
foldl much smaller.
But, Stuart's proposal gives us much of this with less fuss. IF a
collection is reversible, you can just say
c.reversed().stream()
and off you go, plus a similar method for arrays
(Arrays.reversedStream). Given that, what is the value of pushing this
further into stream?
On 4/17/2021 7:49 AM, Tagir Valeev wrote:
Great proposal, thanks!
It has most functionality from my previous proposal, except the
ability to iterate LinkedHashSet starting from a specific element.
Well, probably we can skip this for now.
Some people really want to reverse Streams as well. E. g., the
corresponding StackOverflow question [1] has 171 upvotes and 200k+
views. Also, if the stream were reversible, it would be possible to
implement efficient foldRight/reduceRight operation. See the
discussion at [2]. It would be nice to explore the possibility of
extending Stream API to take into account the source reversibility.
Some existing ordered sources that have no underlying collection (e.g.
IntStream.range, or Arrays.stream) can be easily reversed as well. Map
and filter operations preserve reversibility and flatMap is reversible
if the supplied stream is reversible as well.
With best regards,
Tagir Valeev.
[1] https://stackoverflow.com/q/24010109/4856258
[2] https://bugs.openjdk.java.net/browse/JDK-8133680
On Sat, Apr 17, 2021 at 12:41 AM Stuart Marks wrote:
This is a proposal to add a ReversibleCollection interface to the Collections
Framework. I'm looking for comments on overall design before I work on detailed
specifications and tests. Please send such comments as replies on this email
thread.
Here's a link to a draft PR that contains the code diffs. It's prototype
quality,
but it should be good enough to build and try out:
https://github.com/openjdk/jdk/pull/3533
And here's a link to a class diagram showing the proposed additions:
https://cr.openjdk.java.net/~smarks/ReversibleCollection/ReversibleCollectionDiagram.pdf
Thanks,
s'marks
# Ordering and Reversibility
A long-standing concept that's been missing from collections is that of the
positioning, sequencing, or arrangement of elements as a structural property of
a
collection. (This is sometimes called the "iteration order" of a collection.)
For
example, a HashSet is not ordered, but a List is. This concept is mostly not
manifested in the collections API.
Iterating a collection produces elements one after another in *some* sequence.
The
concept of "ordered" determines whether this sequence is defined or whether
it's a
coincidence of implementation. What does "having an order" mean? It implies that
there is a first element and that each element has a successor. Since
collections
have a finite number of elements, it further implies that there is a last
element
that has no successor. However, it is difficult to discern whether a collection
has
a defined order. HashSet generally iterates its elements in the same undefined
order, and you can't actually tell that it's not a defined order.
Streams do have a notion of ordering ("encounter order") and this is preserved,
where appropriate, through the stream pipeline. It's possible to detect this by
testing whether its spliterator has the ORDERED characteristic. Any collection
with
a defined order will have a spliterator with this characteristic. However, this
is
quite a roundabout way to determine whether a collection has a defined order.
Furthermore, knowing this doesn't enable any additional operations. It only
provides
constraints on the stream's implementations (keeping the elements in order) and
provides stronger semantics for certain operations. For example, findFirst() on
an
unordered stream is the same as findAny(), but actually finds
Re: ReversibleCollection proposal
Great proposal, thanks!
It has most functionality from my previous proposal, except the
ability to iterate LinkedHashSet starting from a specific element.
Well, probably we can skip this for now.
Some people really want to reverse Streams as well. E. g., the
corresponding StackOverflow question [1] has 171 upvotes and 200k+
views. Also, if the stream were reversible, it would be possible to
implement efficient foldRight/reduceRight operation. See the
discussion at [2]. It would be nice to explore the possibility of
extending Stream API to take into account the source reversibility.
Some existing ordered sources that have no underlying collection (e.g.
IntStream.range, or Arrays.stream) can be easily reversed as well. Map
and filter operations preserve reversibility and flatMap is reversible
if the supplied stream is reversible as well.
With best regards,
Tagir Valeev.
[1] https://stackoverflow.com/q/24010109/4856258
[2] https://bugs.openjdk.java.net/browse/JDK-8133680
On Sat, Apr 17, 2021 at 12:41 AM Stuart Marks wrote:
>
> This is a proposal to add a ReversibleCollection interface to the Collections
> Framework. I'm looking for comments on overall design before I work on
> detailed
> specifications and tests. Please send such comments as replies on this email
> thread.
>
> Here's a link to a draft PR that contains the code diffs. It's prototype
> quality,
> but it should be good enough to build and try out:
>
> https://github.com/openjdk/jdk/pull/3533
>
> And here's a link to a class diagram showing the proposed additions:
>
>
> https://cr.openjdk.java.net/~smarks/ReversibleCollection/ReversibleCollectionDiagram.pdf
>
> Thanks,
>
> s'marks
>
>
> # Ordering and Reversibility
>
>
> A long-standing concept that's been missing from collections is that of the
> positioning, sequencing, or arrangement of elements as a structural property
> of a
> collection. (This is sometimes called the "iteration order" of a collection.)
> For
> example, a HashSet is not ordered, but a List is. This concept is mostly not
> manifested in the collections API.
>
> Iterating a collection produces elements one after another in *some*
> sequence. The
> concept of "ordered" determines whether this sequence is defined or whether
> it's a
> coincidence of implementation. What does "having an order" mean? It implies
> that
> there is a first element and that each element has a successor. Since
> collections
> have a finite number of elements, it further implies that there is a last
> element
> that has no successor. However, it is difficult to discern whether a
> collection has
> a defined order. HashSet generally iterates its elements in the same undefined
> order, and you can't actually tell that it's not a defined order.
>
> Streams do have a notion of ordering ("encounter order") and this is
> preserved,
> where appropriate, through the stream pipeline. It's possible to detect this
> by
> testing whether its spliterator has the ORDERED characteristic. Any
> collection with
> a defined order will have a spliterator with this characteristic. However,
> this is
> quite a roundabout way to determine whether a collection has a defined order.
> Furthermore, knowing this doesn't enable any additional operations. It only
> provides
> constraints on the stream's implementations (keeping the elements in order)
> and
> provides stronger semantics for certain operations. For example, findFirst()
> on an
> unordered stream is the same as findAny(), but actually finds the first
> element if
> the stream is ordered.
>
> The concept of ordering is thus present in the system but is surfaced only in
> a
> fairly indirect way. We can strengthen abstraction of ordering by making a few
> observations and considering their implications.
>
> Given that there is a first element and a last element, the sequence of
> elements has
> two ends. It's reasonable to consider operations (add, get, remove) on either
> end.
> Indeed, the Deque interface has a full complement of operations at each end.
> This is
> an oft-requested feature on various other collections.
>
> Each element except for the last has a successor, implying that each element
> except
> for the first has a predecessor. Thus it's reasonable to consider iterating
> the
> elements from first to last or from last to first (that is, in forward or
> reverse
> order). Indeed, the concept of iterating in reverse order appears already in
> bits
> and pieces in particular places around the collections:
>
> - List has indexOf() and lastIndexOf()
> - Deque has removeFirstOccurrence() and removeLastOccurrence()
> - List has a ListIterator with hasPrevious/previous methods
> - Deque and NavigableSet have descendingIterator methods
>
> Given an ordered collection, though, there's no general way to iterate it in
> reverse
> order. Reversed iteration isn't the most common operation, but there are some
> frequent use cases, such as operating on elements in
Re: ReversibleCollection proposal
On Saturday, April 17, 2021 11:48 CEST, Stephen Colebourne wrote: > On Fri, 16 Apr 2021 at 18:41, Stuart Marks wrote: > > This is a proposal to add a ReversibleCollection interface to the > > Collections > > Framework. I'm looking for comments on overall design before I work on > > detailed > > specifications and tests. Please send such comments as replies on this > > email thread. > > I think this could be an interesting addition to the framework. > > > # Ordering and Reversibility > > Reading this section, it seems like ordering is a more significant > quality than reversibility. Yet the API is named "reversible". That > seems odd, esepcially given the stream characteristic. Since `reversible = ordered + sized`, using reversible makes sense imho (even though in the context of the Collections Framework, reversible <-> ordered, since all collections are sized). Also, I think "reversible" is much less likely to clash with existing code (e.g. a quick GitHub search shows 1 result for `ReversibleCollection`, while there's plenty for `OrderedCollection`). > > > SortedSet::addFirst and addLast throw UnsupportedOperationException. This > > is because > > SortedSet's ordering is determined by the comparison method and cannot be > > controlled > > explicitly. > > This seems undesirable. Maybe SortedSet should not implement > reversible/ordered? Maybe they should add to the set but validate > whether they would be in first/last position? Simply allowing users to > get a new instance with a different (eg. reversed) comparator would > meet much of the use case. I'd argue throwing UOE is the right thing to do. Not having `SortedSet` implement `ReversibleSet` doesn't make sense to me. Adding with validation is reasonable in itself, but then you'd have to specify `IllegalArgumentException` in `ReversibleCollection` (where you'd have a hard time specifying the conditions under which it might be thrown without explicitly referencing `SortedSet`), just to accommodate these 2 methods which would be very rarely used. > > Also, SortedSet uses first() and last(), yet the proposed interface > uses getFirst() and getLast(). Since `Deque` uses `getFirst()` and `getLast()`, it's impossible to match all existing methods in the different interfaces. > > Stephen Kind regards, Anthony
Re: ReversibleCollection proposal
On Fri, 16 Apr 2021 at 18:41, Stuart Marks wrote: > This is a proposal to add a ReversibleCollection interface to the Collections > Framework. I'm looking for comments on overall design before I work on > detailed > specifications and tests. Please send such comments as replies on this email > thread. I think this could be an interesting addition to the framework. > # Ordering and Reversibility Reading this section, it seems like ordering is a more significant quality than reversibility. Yet the API is named "reversible". That seems odd, esepcially given the stream characteristic. > SortedSet::addFirst and addLast throw UnsupportedOperationException. This is > because > SortedSet's ordering is determined by the comparison method and cannot be > controlled > explicitly. This seems undesirable. Maybe SortedSet should not implement reversible/ordered? Maybe they should add to the set but validate whether they would be in first/last position? Simply allowing users to get a new instance with a different (eg. reversed) comparator would meet much of the use case. Also, SortedSet uses first() and last(), yet the proposed interface uses getFirst() and getLast(). Stephen
Re: ReversibleCollection proposal
Hi Stuart,
We should be cautious when adding new APIs to existing interfaces. There may be
libraries which extend JDK types and already have reversed(), toReversed() or
asReversed() APIs and corresponding interfaces.
There are OrderedIterable and ReversibleIterable interfaces and asReversed()
and toReversed() methods in the Eclipse Collections API.
JavaDoc:
https://www.eclipse.org/collections/javadoc/10.4.0/org/eclipse/collections/api/ordered/OrderedIterable.html
https://www.eclipse.org/collections/javadoc/10.4.0/org/eclipse/collections/api/ordered/ReversibleIterable.html
Code Browser:
https://code.yawk.at/org.eclipse.collections/eclipse-collections-api/10.4.0/org/eclipse/collections/api/ordered/OrderedIterable.java
https://code.yawk.at/org.eclipse.collections/eclipse-collections-api/10.4.0/org/eclipse/collections/api/ordered/ReversibleIterable.java
OrderedIterable and ReversibleIterable appear in the mind map for RichIterable
and have corresponding primitive versions in the mind map for PrimitiveIterable.
https://medium.com/oracledevs/visualizing-eclipse-collections-646dad9533a9?source=friends_link=3370a5e8bb5a516e6b5d7040f7d0955b
There are methods asReversed() and toReversed() on ReversibleIterable().
https://code.yawk.at/org.eclipse.collections/eclipse-collections-api/10.4.0/org/eclipse/collections/api/ordered/ReversibleIterable.java#org.eclipse.collections.api.ordered.ReversibleIterable%23asReversed%28%29
https://code.yawk.at/org.eclipse.collections/eclipse-collections-api/10.4.0/org/eclipse/collections/api/ordered/ReversibleIterable.java#org.eclipse.collections.api.ordered.ReversibleIterable%23toReversed%28%29
The toReversed() method is co-variantly overridden in subtypes of
ReversibleIterable.
https://code.yawk.at/org.eclipse.collections/eclipse-collections-api/10.4.0/org/eclipse/collections/api/list/ListIterable.java#org.eclipse.collections.api.list.ListIterable%23toReversed%28%29
The asReversed() method returns a ReverseIterable which is lazy.
https://code.yawk.at/org.eclipse.collections/eclipse-collections/9.2.0/org/eclipse/collections/impl/lazy/ReverseIterable.java
Thanks,
Don
> On Apr 16, 2021, at 1:40 PM, Stuart Marks wrote:
>
> This is a proposal to add a ReversibleCollection interface to the Collections
> Framework. I'm looking for comments on overall design before I work on
> detailed specifications and tests. Please send such comments as replies on
> this email thread.
>
> Here's a link to a draft PR that contains the code diffs. It's prototype
> quality, but it should be good enough to build and try out:
>
>https://github.com/openjdk/jdk/pull/3533
>
> And here's a link to a class diagram showing the proposed additions:
>
> https://cr.openjdk.java.net/~smarks/ReversibleCollection/ReversibleCollectionDiagram.pdf
>
> Thanks,
>
> s'marks
>
>
> # Ordering and Reversibility
>
>
> A long-standing concept that's been missing from collections is that of the
> positioning, sequencing, or arrangement of elements as a structural property
> of a collection. (This is sometimes called the "iteration order" of a
> collection.) For example, a HashSet is not ordered, but a List is. This
> concept is mostly not manifested in the collections API.
>
> Iterating a collection produces elements one after another in *some*
> sequence. The concept of "ordered" determines whether this sequence is
> defined or whether it's a coincidence of implementation. What does "having an
> order" mean? It implies that there is a first element and that each element
> has a successor. Since collections have a finite number of elements, it
> further implies that there is a last element that has no successor. However,
> it is difficult to discern whether a collection has a defined order. HashSet
> generally iterates its elements in the same undefined order, and you can't
> actually tell that it's not a defined order.
>
> Streams do have a notion of ordering ("encounter order") and this is
> preserved, where appropriate, through the stream pipeline. It's possible to
> detect this by testing whether its spliterator has the ORDERED
> characteristic. Any collection with a defined order will have a spliterator
> with this characteristic. However, this is quite a roundabout way to
> determine whether a collection has a defined order. Furthermore, knowing this
> doesn't enable any additional operations. It only provides constraints on the
> stream's implementations (keeping the elements in order) and provides
> stronger semantics for certain operations. For example, findFirst() on an
> unordered stream is the same as findAny(), but actually finds the first
> element if the stream is ordered.
>
> The concept of ordering is thus present in the system but is surfaced only in
> a fairly indirect way. We can strengthen abstraction of ordering by making a
> few observations and considering their implications.
>
> Given that there is a first element and a last element, the
ReversibleCollection proposal
This is a proposal to add a ReversibleCollection interface to the Collections
Framework. I'm looking for comments on overall design before I work on detailed
specifications and tests. Please send such comments as replies on this email thread.
Here's a link to a draft PR that contains the code diffs. It's prototype quality,
but it should be good enough to build and try out:
https://github.com/openjdk/jdk/pull/3533
And here's a link to a class diagram showing the proposed additions:
https://cr.openjdk.java.net/~smarks/ReversibleCollection/ReversibleCollectionDiagram.pdf
Thanks,
s'marks
# Ordering and Reversibility
A long-standing concept that's been missing from collections is that of the
positioning, sequencing, or arrangement of elements as a structural property of a
collection. (This is sometimes called the "iteration order" of a collection.) For
example, a HashSet is not ordered, but a List is. This concept is mostly not
manifested in the collections API.
Iterating a collection produces elements one after another in *some* sequence. The
concept of "ordered" determines whether this sequence is defined or whether it's a
coincidence of implementation. What does "having an order" mean? It implies that
there is a first element and that each element has a successor. Since collections
have a finite number of elements, it further implies that there is a last element
that has no successor. However, it is difficult to discern whether a collection has
a defined order. HashSet generally iterates its elements in the same undefined
order, and you can't actually tell that it's not a defined order.
Streams do have a notion of ordering ("encounter order") and this is preserved,
where appropriate, through the stream pipeline. It's possible to detect this by
testing whether its spliterator has the ORDERED characteristic. Any collection with
a defined order will have a spliterator with this characteristic. However, this is
quite a roundabout way to determine whether a collection has a defined order.
Furthermore, knowing this doesn't enable any additional operations. It only provides
constraints on the stream's implementations (keeping the elements in order) and
provides stronger semantics for certain operations. For example, findFirst() on an
unordered stream is the same as findAny(), but actually finds the first element if
the stream is ordered.
The concept of ordering is thus present in the system but is surfaced only in a
fairly indirect way. We can strengthen abstraction of ordering by making a few
observations and considering their implications.
Given that there is a first element and a last element, the sequence of elements has
two ends. It's reasonable to consider operations (add, get, remove) on either end.
Indeed, the Deque interface has a full complement of operations at each end. This is
an oft-requested feature on various other collections.
Each element except for the last has a successor, implying that each element except
for the first has a predecessor. Thus it's reasonable to consider iterating the
elements from first to last or from last to first (that is, in forward or reverse
order). Indeed, the concept of iterating in reverse order appears already in bits
and pieces in particular places around the collections:
- List has indexOf() and lastIndexOf()
- Deque has removeFirstOccurrence() and removeLastOccurrence()
- List has a ListIterator with hasPrevious/previous methods
- Deque and NavigableSet have descendingIterator methods
Given an ordered collection, though, there's no general way to iterate it in reverse
order. Reversed iteration isn't the most common operation, but there are some
frequent use cases, such as operating on elements in most-recently-added order.
Questions and bug reports about this have come up repeatedly over the years.
Unfortunately, iterating in reverse order is much harder than iterating in forward
order. There are a variety of ways to iterate in forward order. For example, given a
List, one can do any of the following:
for (var e : list) { ... }
list.forEach(...)
list.stream()
list.toArray()
However, to iterate a list in reverse order, one must use an explicit loop over
ListIterator:
for (var it = list.listIterator(list.size()); it.hasPrevious(); ) {
var e = it.previous();
...
}
Streaming the elements of a List in reverse order is even worse. One approach would
be to implement a reverse-ordered Iterator that wraps a ListIterator and delegates
hasNext/next calls to the ListIterator's hasPrevious/previous methods. Then, this
Iterator can be turned into a Spliterator, which is then turned into a Stream. (The
code to do this is left as an exercise for the reader.) Obtaining the elements in
reverse via other means -- forEach() or toArray() -- is similarly difficult.
Obtaining the elements in reverse order can be accomplished by adopting a concept
from
