Importing operators

[cbruegg]

From the readme:

Note: you need to import these operators from kotlinx.collections.immutable package in order for them to take the precedence over the ones from the standard library.

That makes it very easy to accidentally use the standard operators, which obviously has bad performance implications. Perhaps the operator functions should be instance methods so that the compiler prefers them over the standard plus/minus extension functions?

[ilya-g]

Yes, that is a valid concern.

Unfortunately making them member would clutter the interfaces.

I have another option in mind: if the standard operators know something about immutable collections, they can be specialized in runtime to utilize immutability of those collections.

[ilya-g]

We have discussed the issue. The issue is that even if we provide more specific operations and operators for immutable collections, without an explicit import the same-named operations from the standard library will take precedence over the former.

There were three options how to resolve it:

1. Name all specific operations differently

   • good names are not cheap
   • operators can't be renamed
   • it introduces even more confusion

2. Make extensions on immutable collections more preferable than the same-named extensions on read-only collections, even when they're not imported.

   2.1. Light way: make completion prefer package with those extensions and insert required import automatically.

   • removing import changes the behavior and it can be left unnoticed, copy-pasting code block without imports changes the behavior.

   2.2. Hard way: allow to distinguish these extensions, so they are follow the type as members and do not require explicit import.

   • may require a lot of design work in compiler

3. Make immutable collection interfaces not extend read-only collection interfaces at all, including Iterable<T>.

   • This way no existing Iterable/List/Set/Map extensions would be availabe on immutable collections.
   • In order to pass such collection where a read-only collection is required, an explicit conversion, i.e. asList() or asMap(), have to be invoked.
   • An immutable collection implementation may actually implement corresponding read-only collection, so that conversion will be a no-op.

Out of all options the third looks the most realistic, though on a first sight it might look awkward that an immutable collection do not extend read-only one.

What do you guys think about it?

[cbruegg]

Option 3 sounds fair to me, especially since 1 and 2 really don't seem like feasible solutions.
Would all of the current extensions to Iterable/List/Set/Map be made available separately and optimized for the corresponding immutable types? Most of my method calls where collections are passed are calls to those, so if they existed, there wouldn't be too many places where I'd need to add asList() in my application code.

[Sporking]

I'm a heavy user of the Guava immutable collections. Overall, I am impressed by the design of that library: I think the design is close to ideal, given the syntactic restrictions of Java, some of which are not shared by Kotlin, as well as Java's annoying insistence that all collections interfaces such as java.util.List expose mutation functions even if they aren't implemented.

With that in mind, I very, very much dislike the idea suggested above that a Kotlin ImmutableList might not be inherited from the List interface. I think that calling asList(), etc. all over the place would add needless code clutter. (Using Guava, I often find myself calling an existing function that takes a parameter of type java.util.List with an ImmutableList.)

I think that this would be less of a problem with PersistentList, since that is really a different data structure with a different interface, although it would be nice if that too implemented the List interface. Perhaps the copying mutation functions ('plus', etc.) could be added to List itself as extension functions so that someone could call List.plus(List) for any List instance, not just an Immutable or a Persistent one, and the implementation of the plus function could choose the type of the object to be created based on the types of the arguments? Since you are dealing with a finite number of non-extensible ('final' in Java) classes here, this seems feasible.

In general, I would like Kotlin's ImmutableList to be functionally similar to Guava's: A known list of objects which won't ever change once constructed. If I need to add new items to it, I can use a builder to construct a new object (ImmutableList.builder() factory function in Guava) and then add the old list's contents, or I can construct an ordinary mutable ArrayList, modify it as I like, and then construct an immutable list from it using the equivalent of Guava's ImmutableList.copy(...) function. Note that builders can have code optimized for easy addition of items, while the items that they build are instead optimized for fast access and minimal size. (in Kotlin, Collection.toImmutableList() could act as a builder, or could use such a builder internally.)

The following link may be useful, for anyone who hasn't seen it yet. It describes some of the design motivations for Guava's support of immutable collections:

https://github.com/google/guava/wiki/ImmutableCollectionsExplained

I do have some concerns with the idea that Kotlin's current ImmutableList is an interface, rather than a class. This leaves open the possibility that someone could create a subclass of it which is not, in fact, immutable, and that a function of mine which took a parameter of type ImmutableList could be surprised to find the list's contents changing out from under it. This was a design concern with Guava, if I recall correctly, and one of the reasons that ImmutableList is, not an interface, but is instead a class which is declared 'final'.

Having functional-style persistent collections which can easily create modified copies (or additive/persistent copies) of themselves can be useful for many algorithms. However, I think that separating immutability and persistence (has has been done via Ilya's commits above) is a good idea, since different data structures may be best for each. For instance, an immutable hash set could, at creation time, take some time upfront to find a "perfect hash function" to optimally distribute the specific set of values to be hashed, so that later lookups could be as fast as possible. A persistent hash set, on the other hand, might instead want to optimize for ease of creation of a new hash set that delegated to an old one. Likewise constructing an immutable tree set might involve finding an optimal way to balance a specific set of tree elements, while a persistent tree set might be optimized for adding new tree elements while being able to maximally reuse existing objects from the old tree.

The algorithm tradeoffs for immutable data structures (heavyweight one-time creation of a data structure specialized for rapidly searching a specific known set of items, possibly with special cases for small sets, etc.) versus those for functional/persistent data structures (create a data structure specialized for maximum reuse of subobjects by "parent" data structures that will be created later, with more balance between speed of constructing modifier decorator objects that delegate to the original object versus speed of searching) are quite different.

[ilya-g]

With that in mind, I very, very much dislike the idea suggested above that a Kotlin ImmutableList might not be inherited from the List interface.

Don't worry, we have investigated that option and that turned out to be a dead end.

I do have some concerns with the idea that Kotlin's current ImmutableList is an interface, rather than a class. This leaves open the possibility that someone could create a subclass of it which is not, in fact, immutable

I consider this no more dangerous than other contract violations such as putting an object with non constant hash code in a hash map.

Perhaps if we had sealed interface feature in Kotlin, we could seal that interface to have implementations only in the same module, but that closes the path to potential integrations with the other immutable collection libraries.

[rgoldberg]

Extensions are selected based on static type, not runtime type.

Unless the stdlib extensions include type checks for immutable collections, you could easily call a less-performant version of an extension.

The simplest way to fix this is to refactor the extensions as interface members. What is so terrible about that? The count of members in an interface seems of trivial importance compared to code performance and to ease of use. Especially when:

• each of these functions is already in the stdlib API as an extension, so their existence / behavior shouldn't be surprising.
• each of these functions will be in the API as an extension if not as an interface member, so they won't be adding to the complexity of the overall API.
• it is likely that few people will create their own implementations of the interfaces that won't be able to use existing implementations of the interface members

If you choose option 1 or option 3, I will just use Guava immutable collections instead of this project.

[neyb]

why not going simple & putting these extensions in interfaces as default implementation ? kotlin will use them no matter the existing extensions.
also things like #12 (filter returning a fully duplicated stdlist) can be fix that way.

to me, stdlib do this with extension because they don't provide the actual implementation (they were provided by jdk, with is not the case for this library).

[Sporking]

Above, I said:

I do have some concerns with the idea that Kotlin's current ImmutableList is an interface, rather than a class. This leaves open the possibility that someone could create a subclass of it which is not, in fact, immutable

Ilya replied:

I consider this no more dangerous than other contract violations such as putting an object with non constant hash code in a hash map.

I very much disagree with this statement, and I think it is missing the point of my concern (and that of the Google Guava design team, which raised the same concern).

If I have an algorithm that accepts an ImmutableList as a parameter, then I can (in theory) perform lightweight "copies" of that object by just passing the reference around to new locations in my code. The fact that the object is immutable should guarantee that doing that is safe.

However, if that object actually is a different concrete type supplied by an attacker (say, an EvilImmutableList which inherits from an ImmutableList interface) then any references to the passed-in object may suddenly find themselves reading different data than was originally provided.

This can become a serious security issue and can lead to compromised code and hacking.

For instance, in code like this:

    fun doSomethingSecure(theData: ImmutableList) {

         checkThatDataIsValid(theData); // throw exception if invalid data is found

         // What if the attacker uses a race condition to asynchronously put invalid data
         // into theData while the following function call occurs?
         Thread.sleep(1000);

         // Are we still sure the data is valid at this point?
         doSomethingSecuritySensitiveWith(theData);
    }

In the Google Guava design, where ImmutableList is a final class, this function is safe: The contents of theData which are passed to checkThatDataIsValid are guaranteed to be the same as those that are passed to doSomethingSecuritySensitiveWith, because there is only one ImmutableList class and (because it is 'final') there can never be any subclasses of it with different behavior.

In the kotlinx.collections.immutable design, where ImmutableList is just an interface, not a final class, an attacker can create a subtype of the ImmutableList interface whose contents can be changed whenever the attacker wants them to be. The doSomethingSecure function is no longer safe! The attacker can wait until checkThatDataIsValid has returned successfully, and then can asynchronously change the data in theData so that invalid data later gets passed to doSomethingSecuritySensitiveWith. This means that to be truly safe, the doSomethingSecure class would have to be written to make defensive copies of the passed-in data in order to ensure that everything typed as an ImmutableList actually is of a safe subclass which can't be manipulated by an attacker. Of course this copying operation itself can be compromised by an attacker-supplied subclass in some cases, and also if anywhere in the code a necessary copy (at the first possible opportunity) is accidentally omitted, then there is a security hole waiting to be exploited.

This is not just "other contract violations" as Ilya has stated: This is ALLOWING FOR THE POSSIBILITY of "other contract violations" which is quite different. In the Guava design, trustworthy behavior of immutable objects is ENFORCED by the fact that the data is held in a class that is 'final', so the implementation can be trusted to be the same everywhere, and can be trusted to enforce the necessary contracts even if a hostile attacker would prefer that it didn't. In the kotlinx.collections.immutable case, the programmer must TRUST that whoever passed in an object that conforms to the ImmutableList interface actually had good intentions and didn't intentionally violate the contract or otherwise write the class in such a way as to violate security. (For instance, an EvilImmutableList class could also keep records of which list elements were accessed and in what order: not a contract violation, but it could still allow reverse-engineering of an encryption engine.)

Note that Java Standard Library classes like java.lang.String, java.lang.Integer, etc. are declared 'final' for similar security-related reasons. This is not a new issue.

Please implement immutability according to the Guava model. It actually does make a difference.