Proposal: Collection mutability marker interfaces

Wed Aug 24 15:21:47 UTC 2022

> From: "Ethan McCue" <ethan at mccue.dev>
> To: "Remi Forax" <forax at univ-mlv.fr>
> Cc: "John Hendrikx" <john.hendrikx at gmail.com>, "core-libs-dev"
> <core-libs-dev at openjdk.org>
> Sent: Wednesday, August 24, 2022 4:27:01 PM
> Subject: Re: Proposal: Collection mutability marker interfaces

>> so it's perhaps better to call add() inside a try/catch on
> > UnsupportedOperationException.

> As much as sin is wrong, sketching out what that might look like... forgive the
> toyness of the example

> VS

> final class Ex {
> private Ex() {}

> /*
> * Adds the odd numbers from 1 to 10 to the List then makes all the odds even.
> *
> * Takes ownership of the list, avoids making copies if it doesn't need to
> */
> static List<Integer> addOdds(List<Integer> l) {
> for (int i = 1; i <= 10; i++) {
> try {
> l.add(i);
> } catch (UnsupportedOperationException e) {
> l = new ArrayList<>(l);

i -= 1; // restart with an ArrayList 

> }
> }

> for (int i = 0; i < l.size(); i++) {
> if (l.get(i) % 2 == 1) {
> try {
> l.set(i, l.get(i) + 1);
> } catch (UnsupportedOperationException e) {
> l = new ArrayList<>(l);
> }
> }
> }
> }
> }

as Roger said, there is no way in Java to know if the caller has not kept a reference (unlike Rust), 
so having trouble to write this kind of code is more a feature than an issue :) 

This kind of examples scream the Stream API, which has the correct semantics 
IntStream.rangeClosed(1, 10).map(i -> i % 2 == 0? i + 1: i).boxed().toList() 

Rémi 

> On Wed, Aug 24, 2022 at 10:03 AM Remi Forax < [ mailto:forax at univ-mlv.fr |
> forax at univ-mlv.fr ] > wrote:

>>> From: "Ethan McCue" < [ mailto:ethan at mccue.dev | ethan at mccue.dev ] >
>>> To: "John Hendrikx" < [ mailto:john.hendrikx at gmail.com | john.hendrikx at gmail.com
>>> ] >
>>> Cc: "core-libs-dev" < [ mailto:core-libs-dev at openjdk.org |
>>> core-libs-dev at openjdk.org ] >
>>> Sent: Wednesday, August 24, 2022 3:38:26 PM
>>> Subject: Re: Proposal: Collection mutability marker interfaces

>>> A use case that doesn't cover is adding to a collection.

>>> Say as part of a method's contract you state that you take ownership of a List.
>>> You aren't going to copy even if the list is mutable.

>>> Later on, you may want to add to the list. Add is supported on ArrayList so you
>>> don't need to copy and replace your reference, but you would if the list you
>>> were given was made with List.of or Arrays.asList

>> You can ask if the spliterator considers the collection as immutable or not,
>> list.spliterator().hasCharacteristics(Spliterator.IMMUTABLE)

>> sadly, List.of()/Map.of() does not report the spliterator characteristics
>> correctly (the spliterator implementations are inherited from
>> AbstracList/AbstractMap).

>> so it's perhaps better to call add() inside a try/catch on
>> UnsupportedOperationException.

>> Rémi

>>> On Wed, Aug 24, 2022, 8:13 AM John Hendrikx < [ mailto:john.hendrikx at gmail.com |
>>> john.hendrikx at gmail.com ] > wrote:

>>>> Would it be an option to not make the receiver responsible for the decision
>>>> whether to make a copy or not? Instead put this burden (using default methods)
>>>> on the various collections?

>>>> If List/Set/Map had a method like this:

>>>> List<T> immutableCopy(); // returns a (shallow) immutable copy if list is
>>>> mutable (basically always copies, unless proven otherwise)

>>>> Paired with methods on Collections to prevent collections from being modified:

>>>> Collections.immutableList(List<T>)

>>>> This wrapper is similar to `unmodifiableList` except it implements
>>>> `immutableCopy` as `return this`.

>>>> Then for the various scenario's, where `x` is an untrusted source of List with
>>>> unknown status:

>>>> // Create a defensive copy; result is a private list that cannot be modified:

>>>> List<T> y = x.immutableCopy();

>>>> // Create a defensive copy for sharing, promising it won't ever change:

>>>> List<T> y = Collections.immutableList(x.immutableCopy());

>>>> // Create a defensive copy for mutating:

>>>> List<T> y = new ArrayList<>(x); // same as always

>>>> // Create a mutable copy, modify it, then expose as immutable:

>>>> List<T> y = new ArrayList<>(x); // same as always

>>>> y.add( <some element> );

>>>> List<T> z = Collections.immutableList(y);

>>>> y = null; // we promise `z` won't change again by clearing the only path to
>>>> mutating it!

>>>> The advantage would be that this information isn't part of the type system where
>>>> it can easily get lost. The actual implementation knows best whether a copy
>>>> must be made or not.

>>>> Of course, the immutableList wrapper can be used incorrectly and the promise
>>>> here can be broken by keeping a reference to the original (mutable) list, but I
>>>> think that's an acceptable trade-off.

>>>> --John

>>>> PS. Chosen names are just for illustration; there is some discussion as what
>>>> "unmodifiable" vs "immutable" means in the context of collections that may
>>>> contain elements that are mutable. In this post, immutable refers to shallow
>>>> immutability .
>>>> On 24/08/2022 03:24, Ethan McCue wrote:

>>>>> Ah, I'm an idiot.

>>>>> There is still a proposal here somewhere...maybe. right now non jdk lists can't
>>>>> participate in the special casing?

>>>>> On Tue, Aug 23, 2022, 9:00 PM Paul Sandoz < [ mailto:paul.sandoz at oracle.com |
>>>>> paul.sandoz at oracle.com ] > wrote:

>>>>>> List.copyOf already does what you want.

>>>>>> [
>>>>>> https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/List.java#L1068
>>>>>> |
>>>>>> https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/List.java#L1068
>>>>>> ]
>>>>>> [
>>>>>> https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ImmutableCollections.java#L168
>>>>>> |
>>>>>> https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ImmutableCollections.java#L168
>>>>>> ]

>>>>>> Paul.

>>>>>>> On Aug 23, 2022, at 4:49 PM, Ethan McCue < [ mailto:ethan at mccue.dev |
>>>>>> > ethan at mccue.dev ] > wrote:

>>>>>> > Hi all,

>>>>>>> I am running into an issue with the collections framework where I have to choose
>>>>>> > between good semantics for users and performance.

>>>>>>> Specifically I am taking a java.util.List from my users and I need to choose to
>>>>>> > either
>>>>>>> * Not defensively copy and expose a potential footgun when I pass that List to
>>>>>> > another thread
>>>>>> > * Defensively copy and make my users pay an unnecessary runtime cost.

>>>>>>> What I would really want, in a nutshell, is for List.copyOf to be a no-op when
>>>>>> > used on lists made with List.of().

>>>>>>> Below the line is a pitch I wrote up on reddit 7 months ago for a mechanism I
>>>>>>> think could accomplish that. My goal is to share the idea a bit more widely and
>>>>>> > to this specific audience to get feedback.

>>>>>>> [
>>>>>>> https://www.reddit.com/r/java/comments/sf8qrv/comment/hv8or92/?utm_source=share&utm_medium=web2x&context=3
>>>>>>> |
>>>>>>> https://www.reddit.com/r/java/comments/sf8qrv/comment/hv8or92/?utm_source=share&utm_medium=web2x&context=3
>>>>>> > ]

>>>>>> > Important also for context is Ron Pressler's comment above.
>>>>>> > --------------

>>>>>> > What if the collections api added more marker interfaces like RandomAccess?

>>>>>>> It's already a common thing for codebases to make explicit null checks at error
>>>>>> > boundaries because the type system can't encode null | List<String>.

>>>>>> > This feels like a similar problem.
>>>>>>> If you have a List<T> in the type system then you don't know for sure you can
>>>>>>> call any methods on it until you check that its not null. In the same way,
>>>>>>> there is a set of methods that you don't know at the type/interface level if
>>>>>> > you are allowed to call.

>>>>>> > If the List is actually a __
>>>>>> > Then you can definitely call
>>>>>> > And you know other reference holders might call
>>>>>> > And you can confirm its this case by
>>>>>> > null
>>>>>> > no methods
>>>>>> > no methods
>>>>>> > list == null
>>>>>> > List.of(...)
>>>>>> > get, size
>>>>>> > get, size
>>>>>> > ???
>>>>>> > Collections.unmodifiableList(...)
>>>>>> > get, size
>>>>>> > get, size, add, set
>>>>>> > ???
>>>>>> > Arrays.asList(...)
>>>>>> > get, size, set
>>>>>> > get, size, set
>>>>>> > ???
>>>>>> > new ArrayList<>()
>>>>>> > get, size, add, set
>>>>>> > get, size, add, set
>>>>>> > ???
>>>>>>> While yes, there is no feasible way to encode these things in the type system.
>>>>>> > Its not impossible to encode it at runtime though.
>>>>>> > interface FullyImmutable {
>>>>>> > // So you know the existence of this implies the absence
>>>>>> > // of the others
>>>>>> > default Void cantIntersect() { return null; }
>>>>>> > }

>>>>>> > interace MutationCapability {
>>>>>> > default String cantIntersect() { return ""; }
>>>>>> > }

>>>>>> > interface Addable extends MutationCapability {}
>>>>>> > interface Settable extends MutationCapability {}

>>>>>> > If the List is actually a __
>>>>>> > Then you can definitely call
>>>>>> > And you know other reference holders might call
>>>>>> > And you can confirm its this case by
>>>>>> > null
>>>>>> > no methods
>>>>>> > no methods
>>>>>> > list == null
>>>>>> > List.of(...)
>>>>>> > get, size
>>>>>> > get, size
>>>>>> > instanceof FullyImmutable
>>>>>> > Collections.unmodifiableList(...)
>>>>>> > get, size
>>>>>> > get, size, add, set
>>>>>> > !(instanceof Addable) && !(instanceof Settable)
>>>>>> > Arrays.asList(...)
>>>>>> > get, size, set
>>>>>> > get, size, set
>>>>>> > instanceof Settable
>>>>>> > new ArrayList<>()
>>>>>> > get, size, add, set
>>>>>> > get, size, add, set
>>>>>> > instanceof Settable && instanceof Addable
>>>>>>> In the same way a RandomAccess check let's implementations decide whether they
>>>>>>> want to try an alternative algorithm or crash, some marker "capability"
>>>>>>> interfaces would let users of a collection decide if they want to clone what
>>>>>> > they are given before working on it.


>>>>>> > --------------

>>>>>>> So the applicability of this would be that the list returned by List.of could
>>>>>>> implement FullyImmutable, signifying that there is no caller which might have a
>>>>>>> mutable handle on the collection. Then List.of could check for this interface
>>>>>> > and skip a copy.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20220824/f1349613/attachment-0001.htm>