Collections.emptyList().sort() does nothing

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Collections.emptyList().sort() does nothing

Tagir Valeev
Hello!

According to `List.sort` specification [1] "This list must be modifiable".
According to `Collections.emptyList` specification [2] "Returns an
empty list (immutable)."

So I assume that `List.sort` cannot be called on
`Collections.emptyList` result. However in fact this call is allowed
doing nothing. Is this behavior documented somehow? Can I rely that it
will not change in future Java updates?

It's even more strange with `Collections.singletonList` [3] which
"Returns an immutable list containing only the specified object".
Obviously I cannot do:

List<String> list = Collections.singletonList("foo");
ListIterator<String> it = list.listIterator();
it.next();
it.set("bar"); // UOE

However list.sort(null) works perfectly. On the other hand [1] clearly says:

Throws: UnsupportedOperationException - if the list's list-iterator
does not support the set operation.

To me it seems that emptyList and (especially) singletonList
implementation does not follow the specification. Am I missing
something?

With best regards,
Tagir Valeev.

[1] https://docs.oracle.com/javase/9/docs/api/java/util/List.html#sort-java.util.Comparator-
[2] https://docs.oracle.com/javase/9/docs/api/java/util/Collections.html#emptyList--
[3] https://docs.oracle.com/javase/9/docs/api/java/util/Collections.html#singletonList-T-
Reply | Threaded
Open this post in threaded view
|

Re: Collections.emptyList().sort() does nothing

Martin Buchholz-3
Different maintainers of the core library differed on whether it's
important to pedantically check for such corner case mistakes.  Recently
the trend has been to check for all errors up front, even if it ends up
making no difference.  Users should not depend on the library implementer's
mood or vigilance, unless they're professional testers.

On Tue, Nov 14, 2017 at 7:52 PM, Tagir Valeev <[hidden email]> wrote:

> Hello!
>
> According to `List.sort` specification [1] "This list must be modifiable".
> According to `Collections.emptyList` specification [2] "Returns an
> empty list (immutable)."
>
> So I assume that `List.sort` cannot be called on
> `Collections.emptyList` result. However in fact this call is allowed
> doing nothing. Is this behavior documented somehow? Can I rely that it
> will not change in future Java updates?
>
> It's even more strange with `Collections.singletonList` [3] which
> "Returns an immutable list containing only the specified object".
> Obviously I cannot do:
>
> List<String> list = Collections.singletonList("foo");
> ListIterator<String> it = list.listIterator();
> it.next();
> it.set("bar"); // UOE
>
> However list.sort(null) works perfectly. On the other hand [1] clearly
> says:
>
> Throws: UnsupportedOperationException - if the list's list-iterator
> does not support the set operation.
>
> To me it seems that emptyList and (especially) singletonList
> implementation does not follow the specification. Am I missing
> something?
>
> With best regards,
> Tagir Valeev.
>
> [1] https://docs.oracle.com/javase/9/docs/api/java/util/
> List.html#sort-java.util.Comparator-
> [2] https://docs.oracle.com/javase/9/docs/api/java/util/
> Collections.html#emptyList--
> [3] https://docs.oracle.com/javase/9/docs/api/java/util/Collections.html#
> singletonList-T-
>
Reply | Threaded
Open this post in threaded view
|

Re: Collections.emptyList().sort() does nothing

Bernd Eckenfels-4
I would however vote for allowing an empty list to be sorted. This is such a common case to return a replacement empty list that it will not only introduce changed behavior but also forces ugly code.

For singleton list I can kind of understand that you want to fail early, but it could be made the same argument as for the empty case.

In the end, if we allow one or both, it requires to be spelled out explicitely (unfortunately a spec change, even when it is the more likely usage already)

Gruss
Bernd
--
http://bernd.eckenfels.net
________________________________
From: core-libs-dev <[hidden email]> on behalf of Martin Buchholz <[hidden email]>
Sent: Wednesday, November 15, 2017 5:10:06 AM
To: Tagir Valeev
Cc: core-libs-dev
Subject: Re: Collections.emptyList().sort() does nothing

Different maintainers of the core library differed on whether it's
important to pedantically check for such corner case mistakes.  Recently
the trend has been to check for all errors up front, even if it ends up
making no difference.  Users should not depend on the library implementer's
mood or vigilance, unless they're professional testers.

On Tue, Nov 14, 2017 at 7:52 PM, Tagir Valeev <[hidden email]> wrote:

> Hello!
>
> According to `List.sort` specification [1] "This list must be modifiable".
> According to `Collections.emptyList` specification [2] "Returns an
> empty list (immutable)."
>
> So I assume that `List.sort` cannot be called on
> `Collections.emptyList` result. However in fact this call is allowed
> doing nothing. Is this behavior documented somehow? Can I rely that it
> will not change in future Java updates?
>
> It's even more strange with `Collections.singletonList` [3] which
> "Returns an immutable list containing only the specified object".
> Obviously I cannot do:
>
> List<String> list = Collections.singletonList("foo");
> ListIterator<String> it = list.listIterator();
> it.next();
> it.set("bar"); // UOE
>
> However list.sort(null) works perfectly. On the other hand [1] clearly
> says:
>
> Throws: UnsupportedOperationException - if the list's list-iterator
> does not support the set operation.
>
> To me it seems that emptyList and (especially) singletonList
> implementation does not follow the specification. Am I missing
> something?
>
> With best regards,
> Tagir Valeev.
>
> [1] https://docs.oracle.com/javase/9/docs/api/java/util/
> List.html#sort-java.util.Comparator-
> [2] https://docs.oracle.com/javase/9/docs/api/java/util/
> Collections.html#emptyList--
> [3] https://docs.oracle.com/javase/9/docs/api/java/util/Collections.html#
> singletonList-T-
>
Reply | Threaded
Open this post in threaded view
|

Re: Collections.emptyList().sort() does nothing

Andrej Golovnin-2
Hi Bernd,

On Wed, Nov 15, 2017 at 7:04 AM, Bernd Eckenfels <[hidden email]> wrote:
> I would however vote for allowing an empty list to be sorted. This is such a common case to return a replacement empty list that it will not only introduce changed behavior but also forces ugly code.

I think we would need to write ugly code in any case as Java 9 has now
two empty list implementations: Collections.emptyList() and List.of().

Collections.emptyList().sort() does not throw an exception.

List.of().sort() throws an exception.

Best regards,
Andrej Golovnin

>
> For singleton list I can kind of understand that you want to fail early, but it could be made the same argument as for the empty case.
>
> In the end, if we allow one or both, it requires to be spelled out explicitely (unfortunately a spec change, even when it is the more likely usage already)
>
> Gruss
> Bernd
> --
> http://bernd.eckenfels.net
> ________________________________
> From: core-libs-dev <[hidden email]> on behalf of Martin Buchholz <[hidden email]>
> Sent: Wednesday, November 15, 2017 5:10:06 AM
> To: Tagir Valeev
> Cc: core-libs-dev
> Subject: Re: Collections.emptyList().sort() does nothing
>
> Different maintainers of the core library differed on whether it's
> important to pedantically check for such corner case mistakes.  Recently
> the trend has been to check for all errors up front, even if it ends up
> making no difference.  Users should not depend on the library implementer's
> mood or vigilance, unless they're professional testers.
>
> On Tue, Nov 14, 2017 at 7:52 PM, Tagir Valeev <[hidden email]> wrote:
>
>> Hello!
>>
>> According to `List.sort` specification [1] "This list must be modifiable".
>> According to `Collections.emptyList` specification [2] "Returns an
>> empty list (immutable)."
>>
>> So I assume that `List.sort` cannot be called on
>> `Collections.emptyList` result. However in fact this call is allowed
>> doing nothing. Is this behavior documented somehow? Can I rely that it
>> will not change in future Java updates?
>>
>> It's even more strange with `Collections.singletonList` [3] which
>> "Returns an immutable list containing only the specified object".
>> Obviously I cannot do:
>>
>> List<String> list = Collections.singletonList("foo");
>> ListIterator<String> it = list.listIterator();
>> it.next();
>> it.set("bar"); // UOE
>>
>> However list.sort(null) works perfectly. On the other hand [1] clearly
>> says:
>>
>> Throws: UnsupportedOperationException - if the list's list-iterator
>> does not support the set operation.
>>
>> To me it seems that emptyList and (especially) singletonList
>> implementation does not follow the specification. Am I missing
>> something?
>>
>> With best regards,
>> Tagir Valeev.
>>
>> [1] https://docs.oracle.com/javase/9/docs/api/java/util/
>> List.html#sort-java.util.Comparator-
>> [2] https://docs.oracle.com/javase/9/docs/api/java/util/
>> Collections.html#emptyList--
>> [3] https://docs.oracle.com/javase/9/docs/api/java/util/Collections.html#
>> singletonList-T-
>>
Reply | Threaded
Open this post in threaded view
|

Re: Collections.emptyList().sort() does nothing

Andrew Haley
On 15/11/17 10:03, Andrej Golovnin wrote:
> I think we would need to write ugly code in any case as Java 9 has now
> two empty list implementations: Collections.emptyList() and List.of().
>
> Collections.emptyList().sort() does not throw an exception.
>
> List.of().sort() throws an exception.

Well, that's a bug.  Sorting an empty list is perfectly valid, and application
programmers shouldn't have to special-case it.

--
Andrew Haley
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
Reply | Threaded
Open this post in threaded view
|

Re: Collections.emptyList().sort() does nothing

Andrej Golovnin-2
> On 15/11/17 10:03, Andrej Golovnin wrote:
>> I think we would need to write ugly code in any case as Java 9 has now
>> two empty list implementations: Collections.emptyList() and List.of().
>>
>> Collections.emptyList().sort() does not throw an exception.
>>
>> List.of().sort() throws an exception.
>
> Well, that's a bug.  Sorting an empty list is perfectly valid, and application
> programmers shouldn't have to special-case it.

I don't think so. I would say that the implementation of
Collections.emptyList() is broken. Collections.emptyList() and
List.of() are not only empty lists. They are also immutable per
specification.

Here is another example of an unsortable empty list:

Collections.unmodifiableList(Collections.emptyList()).sort() throws an
exception.

>
> --
> Andrew Haley
> Java Platform Lead Engineer
> Red Hat UK Ltd. <https://www.redhat.com>
> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
Reply | Threaded
Open this post in threaded view
|

Re: Collections.emptyList().sort() does nothing

Alan Bateman
In reply to this post by Andrej Golovnin-2
On 15/11/2017 10:03, Andrej Golovnin wrote:

> Hi Bernd,
>
> On Wed, Nov 15, 2017 at 7:04 AM, Bernd Eckenfels <[hidden email]> wrote:
>> I would however vote for allowing an empty list to be sorted. This is such a common case to return a replacement empty list that it will not only introduce changed behavior but also forces ugly code.
> I think we would need to write ugly code in any case as Java 9 has now
> two empty list implementations: Collections.emptyList() and List.of().
>
> Collections.emptyList().sort() does not throw an exception.
>
> List.of().sort() throws an exception.
>
>
There are indeed inconsistencies and likely other examples due to List
implementations not overriding sort (and so dependent on the default
implementation which cannot say if an empty or already sorted list is
modifiable or not). As Collections.emptyList() is around a long time
then it would likely break existing code to change it now. It might be
saner to change List0 to be consistent. In any case, the sort javadoc
will likely need some adjustment to allow for long standing behavior.

-Alan
Reply | Threaded
Open this post in threaded view
|

Re: Collections.emptyList().sort() does nothing

Vitaly Davidovich
In reply to this post by Andrej Golovnin-2
On Wed, Nov 15, 2017 at 5:21 AM Andrej Golovnin <[hidden email]>
wrote:

> > On 15/11/17 10:03, Andrej Golovnin wrote:
> >> I think we would need to write ugly code in any case as Java 9 has now
> >> two empty list implementations: Collections.emptyList() and List.of().
> >>
> >> Collections.emptyList().sort() does not throw an exception.
> >>
> >> List.of().sort() throws an exception.
> >
> > Well, that's a bug.  Sorting an empty list is perfectly valid, and
> application
> > programmers shouldn't have to special-case it.
>
> I don't think so. I would say that the implementation of
> Collections.emptyList() is broken. Collections.emptyList() and
> List.of() are not only empty lists. They are also immutable per
> specification.
>
> Here is another example of an unsortable empty list:
>
> Collections.unmodifiableList(Collections.emptyList()).sort() throws an
> exception.

One can argue that since those are empty by construction/design, sorting
them is not a bug.  That’s different from, say, trying to sort an
unmodifiable list that happens to be empty and not failing in that case.

From a user’s perspective, I agree it’s annoying to have to special case
these.  This is particularly so because immutability is not expressed in
the types or type system.

>
>
> >
> > --
> > Andrew Haley
> > Java Platform Lead Engineer
> > Red Hat UK Ltd. <https://www.redhat.com>
> > EAC8 43EB D3EF DB98 C
> <https://maps.google.com/?q=EF+DB98+C&entry=gmail&source=g>C77 2FAD A5CD
> 6035 332F A671
>
--
Sent from my phone
Reply | Threaded
Open this post in threaded view
|

Re: Collections.emptyList().sort() does nothing

Stuart Marks
In reply to this post by Tagir Valeev


On 11/14/17 7:52 PM, Tagir Valeev wrote:

> According to `List.sort` specification [1] "This list must be modifiable".
> According to `Collections.emptyList` specification [2] "Returns an
> empty list (immutable)."
>
> So I assume that `List.sort` cannot be called on
> `Collections.emptyList` result. However in fact this call is allowed
> doing nothing. Is this behavior documented somehow? Can I rely that it
> will not change in future Java updates?
>
> It's even more strange with `Collections.singletonList` [3] which
> "Returns an immutable list containing only the specified object".
> ...
> To me it seems that emptyList and (especially) singletonList
> implementation does not follow the specification. Am I missing
> something?

Hi Tagir,

This is indeed an inconsistency. As Martin noted, different maintainers of the
collections framework took different approaches on how strict to be in these cases.

Note also that

     Collections.emptyList().addAll(List.of())

is a no-op, whereas

     Collections.unmodifiableList(new ArrayList<String>()).addAll(List.of())
     List.of().addAll(List.of())

both throw UnsupportedOperationException.

The issue is whether a collection that considers itself unmodifiable allows
mutator methods to be called, if the operation wouldn't actually make a change
(lenient); or if it unconditionally throws UOE even if the operation wouldn't
actually make a change (strict).

The Collections.unmodifiableX implementations are strict, as are the new
List.of/Set.of/Map.of implementations I added in JDK 9.

As you've noticed, certain special-case collections like Collections.emptyList()
and singletonList() are described as "immutable" (really, unmodifiable), but
they are lenient. While this isn't guaranteed by the spec, changing these at
this point would be a behavioral incompatibility, so we're unlikely ever to
change them.

My view is that it's preferable for collections implementations to be strict. If
I'm handing out an unmodifiable List, it should always be illegal for the callee
to attempt to sort it, even if it has zero or one elements.

s'marks

Reply | Threaded
Open this post in threaded view
|

Re: Collections.emptyList().sort() does nothing

Tagir Valeev
Hello!

> My view is that it's preferable for collections implementations to be
> strict. If I'm handing out an unmodifiable List, it should always be illegal
> for the callee to attempt to sort it, even if it has zero or one elements.

Thank you, this totally makes sence.

> While this isn't guaranteed by the spec, changing these at this point would be a behavioral incompatibility, so we're unlikely ever to change them.

But this behavior will not be specified as well, right?

With best regards,
Tagir Valeev.
Reply | Threaded
Open this post in threaded view
|

Re: Collections.emptyList().sort() does nothing

Peter Levart
In reply to this post by Vitaly Davidovich
Hi,

On 11/15/2017 12:18 PM, Vitaly Davidovich wrote:

> On Wed, Nov 15, 2017 at 5:21 AM Andrej Golovnin <[hidden email]>
> wrote:
>
>>> On 15/11/17 10:03, Andrej Golovnin wrote:
>>>> I think we would need to write ugly code in any case as Java 9 has now
>>>> two empty list implementations: Collections.emptyList() and List.of().
>>>>
>>>> Collections.emptyList().sort() does not throw an exception.
>>>>
>>>> List.of().sort() throws an exception.
>>> Well, that's a bug.  Sorting an empty list is perfectly valid, and
>> application
>>> programmers shouldn't have to special-case it.
>> I don't think so. I would say that the implementation of
>> Collections.emptyList() is broken. Collections.emptyList() and
>> List.of() are not only empty lists. They are also immutable per
>> specification.
>>
>> Here is another example of an unsortable empty list:
>>
>> Collections.unmodifiableList(Collections.emptyList()).sort() throws an
>> exception.
> One can argue that since those are empty by construction/design, sorting
> them is not a bug.  That’s different from, say, trying to sort an
> unmodifiable list that happens to be empty and not failing in that case.
>
>  From a user’s perspective, I agree it’s annoying to have to special case
> these.  This is particularly so because immutability is not expressed in
> the types or type system.

There are 3 kinds of List(s) in JDK according to which optional methods
are supported and which throw UOE:

A - normal mutable lists (ala ArrayList)
B - immutable/unmodifiable lists (ala Collections.unmodifiableList(...),
List.of(...))
C - structurally unmodifiable mutable lists (ala Arrays.asList(...))

What is Collections.emptyList()? In terms of the original (as of jdk 1.2
API), it can be either B or C. Additional (default) List methods added
later may blur this distinction, but they can only do that "artificially".

Suppose that you have and API where you want to return List(s) of type C
to the user, so that user may choose to consume them as-is or sort them
1st in-place. What list would you return when you have 0 elements to
return? Would you return Collections.emptyList() and instruct the user
that he may not blindly sort any given List he gets, but only those that
are not empty? Would you rather return Arrays.asList() and create new
object every time? Why can't I have both?

Well, I can have both:

     private static final List<T> EMPTY_LIST = Arrays.asList();

     ...
     return EMPTY_LIST;
}


But this is complicated and has to be done over and over again. It's
like the story of empty array(s) that have to be declared as a private
static final field in each and every class which wants to optimize empty
returns.

Not to mention that changing Collections.emptyList().sort() to throw UOE
is an incompatible change. Programs may already use emptyList() as kind
C list and depend on it. So why would not Collections.emptyList() be
simply declared to be of kind C and that's it. No code to change and no
code to break. If one wants to get an empty list of type B, he should
use List.of().

Regards, Peter

>
>>
>>> --
>>> Andrew Haley
>>> Java Platform Lead Engineer
>>> Red Hat UK Ltd. <https://www.redhat.com>
>>> EAC8 43EB D3EF DB98 C
>> <https://maps.google.com/?q=EF+DB98+C&entry=gmail&source=g>C77 2FAD A5CD
>> 6035 332F A671
>>

Reply | Threaded
Open this post in threaded view
|

Re: Collections.emptyList().sort() does nothing

Stuart Marks
In reply to this post by Tagir Valeev


On 11/15/17 11:52 PM, Tagir Valeev wrote:
>> While this isn't guaranteed by the spec, changing these at this point would be a behavioral incompatibility, so we're unlikely ever to change them.
>
> But this behavior will not be specified as well, right?

I don't have any plans to change the docs to specify that these particular
implementations allow calling a no-op mutator method (i.e., they do not throw an
exception).

The Collection class specification allows for flexibility in how implementations
deal with such cases. See the paragraph that begins «The "destructive"
methods....» My copyOf proposal, recently reviewed, rewords this somewhat but
keeps this flexibility.

s'marks