Make all immutable interfaces sealed to prevent implementations that allow mutations

[yogurtearl]

Right now you can roll your own mutable version of ImmutableList with something like this:

class SneakyList<E>(
    val mutableList: MutableList<E> = mutableListOf()
): ImmutableList<E> {
    override val size: Int
        get() = mutableList.size

    override fun get(index: Int): E = mutableList[index]
.
.
.
}

Even well-meaning implementations of the ImmutableList interface might accidentally enable mutability.
To make ImmutableList (and ImmutableCollection, etc) even more immutable, make all of the the interfaces in this library sealed interfaces.

[wzsaz]

I don't think this is necessary. Wrongfully implementing an interface will always cause problems.
Just because someone could implement the List interface incorrectly you would not make it sealed.
Sealed interfaces should be conceptually reserved to represent closed implementation hierarchies.

[yogurtearl]

If the implementation of the interface can be mutable, then it is not "immutable" it is just a readonly interface similar to List

[Laxystem]

If the implementation of the interface can be mutable, then it is not "immutable" it is just a readonly interface similar to List

Correct. But immutability is a contract. Just like Java's mutability is a contract broken by Guava's immutable collections. Making ImmutableList sealed will prevent people from implementing immutable collections on their own.

Consider this:

https://github.com/Kotlin/kotlinx.collections.immutable/blob/1d18389e32e8afdbf5caa89808fb5af308fb5c8d/core/commonMain/src/adapters/ReadOnlyCollectionAdapters.kt#L11C1-L20C2

[qurbonzoda]

The Immutable and Persistent interfaces were introduced to allow users implement alternative versions that better suite their use cases. For example, in projects where collections are frequently accessed but very rarely updated, a regular copy-on-write implementation of these interfaces might be more appropriate. However, we recognize that only a small number of users might find this flexibility useful. Therefore, it is very helpful to hear from you whether you utilize this flexibility or it instead poses challenges for you.

In the future, we might decide to limit the implementation of these interfaces or expose the implementation classes. So that users can be confident that the implementation is indeed immutable.

[yogurtearl]

I find that kotlin.collections.List provides the needed flexibility for alternative list implementations.
But when using ImmutableList I am looking for the strongest possible multiplatform immutability guarantees from a security and thread safety point of view. (I know reflection, serialization, agents, etc can be used to subvert some guarantees)

As an example, if I bring in 2 third party SDKs (sdk1 and sdk2) I want to be sure that immutableList won't change after I pass it into sdk2:

val immutableList: ImmutableList = sdk1.getData()

val processedData: List = sdk2.process(immutableList)

// immutableList is unchanged

[yogurtearl]

To add to the example above, if sdk1.getData() returned a custom mutable implementation of ImmutableList and Sdk2 was written in Java, then Java might happily modify the list when I call sdk2.process(immutableList) (should throw an exception).

public class Sdk2 {
    static void process(List<String> list) {
        list.add("foo");
    }
}

Also, I imagine there are potential performance gains that could be had by knowing all possible implementations of ImmutableList statically at compile time? i.e. faster forEach(), map() etc.

[Laxystem]

To further my point, if we make ImmutableList sealed, shouldn't we do the same for mutable ones, too? Afterall, the same arguments apply - the contract can be broken, it could have some performance benefits...

What you're suggesting applies to any interface: if we couple the implementation with the API (by making the interface sealed), we can get better performance and reliability.

But SOLID tells us not to. The interface is open for a reason - to allow alternative implementations - for example, to wrap native list implementations - why would I make them falsely implement mutable list and then wrap them with an adapter instead of just implementing immutable list?

[Sporking]

I don't think ImmutableList should be a sealed interface. I think it should be a final class, not an interface at all, which is what Google Guava does. Guava does it that way for pretty much exactly the reasons described in this bug report. (Specifically, that allowing additional implementations of ImmutableList and other immutable types can create serious security holes.)

This is not the first time this issue has been brought up. See for instance my comments here and here on a bug which was filed in 2017.

Regarding @Laxystem's argument that this isn't SOLID: That's true, but irrelevant in this case. Immutable types are often necessary for security, and as is often true in security, maximally flexible code is often unfixably insecure code. Sometimes making sure that nobody CAN violate a contract (even if they want to!) is very important. There's a reason that java.util.String doesn't allow subclasses of it to be created. If someone wants a "kind of, mostly, sort of immutable" class that is flexible to their own needs, they can subclass the List interface and do what they like. The entire point of an ImmutableList interface, on the other hand, is that its contents are NOT, EVER, UNDER ANY CIRCUMSTANCES supposed to change, unlike other subclasses of the List interface which does not make that guarantee. The fact that an ImmutableList is truly immutable enables special behavior such as being able to "copy" by just passing references around without needing to make defensive copies of the referenced data: that would not be possible if some "kind of, mostly, sort of immutable" subclass was being used. Therefore allowing subclasses of ImmutableList to be created violates this immutability guarantee and defeats the purpose and trustworthyness of ImmutableList itself.

[Laxystem]

@Sporking about security: in all Kotlin targets, the moment malicious code runs, you're fucked. Unless JetBrains is planning on improving security across the board in ways completely unprecedented for such a high-level language (besides Rust), I just don't see a reason for this.

Kotlin relies on sandboxing for security. Yes, for languages like Rust and C that are used to write the sandbox and the OS themselves you have a point - but not for a language like Kotlin that is made to be sandboxed - Android is completely sandboxed, so are Wasm and Js; The JVM as a whole is a walking security nightmare; and Kotlin/Native exists in name only.

Immutable lists serve a different point in Kotlin: thread-safety and iteration-safety.

[Laxystem]

For example, when writing a game engine, I'm keeping vectors immutable and open; Yes, one can abuse that to render completely different things on my game's window - but that same malware can just create its own window, or encrypt your entire filesystem, because the JVM is insecure af anyway.

And this is without mentioning mixins that can just inject into your immutable list implementation at runtime anyway.

[yogurtearl]

Could have a sub-interface that is sealed.

Then most people can use ImmutableList if they want to allow for alternate impls.

But if you really want a restricted set of implementations, you can use SealedImmutableList

interface ImmutableList

sealed interface SealedImmutableList: ImmutableList

class PersistentList: SealedImmutableList { ... }
class SmallList: SealedImmutableList { ... }

[popematt]

If I am going to continue using kotlinx.collections.immutable, I need to be able to take a mutable list that I own and say that it is now immutable instead of having to make a defensive copies in the hot path of my code.

For example (pseudocode):

fun buildTree(treeReader: TreeReader): Tree? {
    return when (treeReader.nextNodeType()) {
        LEAF -> Tree.Leaf(treeReader.getCurrentValue())
        BRANCH -> {
            treeReader.stepDown()
            val children = mutableListOf<Tree>()
            while (true) {
                val child = buildTree(treeReader)
                child ?: break
                children.add(child)
            }
            treeReader.stepUp()
            // Defensive copy here would be prohibitively expensive.
            Tree.Branch(ImmutableListAdapter(children))
        }
        null -> null
    }
}

I just got a significant (~75%) reduction of the memory allocation rate in the hot path of a project I maintain by getting rid of redundant defensive copying.

---

Could have a sub-interface that is sealed.

I think that @yogurtearl's suggestion is probably the best choice for balancing use cases like mine with the more security-focused use cases.

[Laxystem]

I agree with that. As for implementation, I would:

sealed interface ConstantCollection<T> : PersistentCollection<T>

fun <T> persistentListOf(vararg contents): ConstantList<T> // change return type

fun <T> List<T>.toConstantList(): ConstantList<T> = if (this is ConstantList) this else persistentListOf() + this // add new converters

Because Constant implies completely-unchangeable, similarly to how val is immutable but can be changed via contract breach (mixins or wrong implementation), but const val isn't.

Extend Persistent as all built-in impls are persistent anyway.

[JakeWharton]

val means read only. Neither the reference it points to nor the returned reference itself has to be immutable.

class NotImmutable {
  val a: MutableList<Int> get() = ArrayList()
}

[pacher]

The way I see it, the source of the dispute is that we essentially have two libraries in one: immutable collections and persistent collections.
So we also have two types of users:

1. Users like @Sporking, who came for Guava replacement and are only interested in the immutable part. The library's implementation of immutable list is expected to be as optimal as it gets, and it is hard to imagine a use case where someone would want to have their own implementation (maybe @mcpiroman can share a use case ?).
2. Users who came for persistent collections and might want to have custom mutating implementations for special cases like @rhdunn

So basically, if we seal ImmutableList but keep PersistentList open, that should make everyone happy ;-)
But if we keep ImmutableList open, it does probably make sense (as @yogurtearl suggested) to expose some subtype like StrictlyImmutableList with stronger guarantees for those who need it.

[popematt]

Regarding my use case for open immutable collections, it could also be solved if the library provided special builders for the immutable collections that avoided making defensive copies. The builder could guarantee that a mutable collection is wrapped in an immutable collection and that the mutable collection will not be leaked anywhere else. Something like this strawman example might work:

class ImmutableListBuilder<T> {
    private var size: Int = 0
    private val elements: Array<T?>? = null;

    /** Allocate new array if elements is null or if more capacity is needed */
    private fun ensureCapacity(n: Int): Array<T?> = TODO()

    fun add(element: T): ImmutableListBuilder<T> {
        val array = ensureCapacity(size + 1)
        array[size++] = element
        return this
    }

    /** Builds an ImmutableList and clears this builder */
    fun buildAndReset(): ImmutableList<T> {
        // Wrap the array without making a defensive copy
        val immutableList = ArrayBackedImmutableList(elements)
        // Ensure that only the ArrayBackedImmutableList has a reference to the backing array
        elements = null
        return immutableList
    }
}

[Laxystem]

val means read only. Neither the reference it points to nor the returned reference itself has to be immutable.

I was referring to fieldful properties.