The Mystery of Mutable Kotlin Collections
An investigation inside how Kotlin let you use Java collections as if they were implementing Kotlin interfaces
This post is a little more low-level than my recent posts about Kotlin Pearls, so brace yourself to a tour on the inner workings of Kotlin.
Part I — the surprise
It started with a (mostly) harmless piece of code.
I wanted to show why it is not right to assume that List in Kotlin is immutable. The reason is that MutableList inherits from List:
public interface MutableList<E> : List<E>, MutableCollection<E> {...}So, if you think about it, it means that you can pass a MutableList where a List is expected, but you cannot pass a List where a MutableList is expected.
List interface in Kotlin is defined as:
A generic ordered collection of elements. Methods in this interface support only read-only access to the list;
read/write access is supported through the [MutableList] interface.public interface List<out E> : Collection<E> {...
It’s easy to think that something implementing List must be an immutable collection but this is not correct. It is just one we cannot modify.
In other words, if you have a function like this:
fun eatAll(fruits: List<Fruit>) = ...You are not declaring that eatAll() will only accept an immutable fruits.
What you are declaring instead, is that eatAll() does not need to modify fruits.
So far so good. Maybe this is nothing new for you, but please bear with me because now things start becoming interesting.
As an example and a warning, I wrote this “naughty” code:
fun boringMethodWithAList(list: List<*>){
println( list::class.java )
println( "before $list" )
naughtyFun( list )
println( "after $list" )
}
fun <T> naughtyFun(list: List<T>) {
if (list.size > 1 && list is MutableList<T>){
val e = list[0]
list[0] = list[1]
list[1] = e
}
}fun main() {
val mutableList = mutableListOf(1,2,3,4)
boringMethodWithAList(mutableList)
}
The naughtyFun() is switching the position of the first two elements of the list.
Looking only at the code of boringMethodWithAList() you may think the two outputs will be completely identical but the actual output is:
class java.util.ArrayList
[1, 2, 3, 4]
[2, 1, 3, 4]This is what I wanted to show. Surprising but expected. So far so good.
Next step would have been with a really immutable list to compare the output. So instead of calling mutableListOf() I replaced it with listOf() and…
fun main() {
val list = listOf("albert", "brian", "charlie")
boringMethodWithAList(list)
}Can you guess the outputs?
class java.util.Arrays$ArrayList
[albert, brian, charlie]
[brian, albert, charlie]So even our supposedly “immutable list” is implementing MutableList interface and it let us switch values! I was surprised.
Note that we are not using tricks like calling hidden methods with reflection or doing unsafe casts. This is perfectly plain Kotlin code that honors the List interface contract.
Part II — Kotlin List implementations
Looking a the first line of our output, we can see that listOf() returns an instance of Arrays$ArrayList while mutableListOf() is returning an instance ofArrayList.
Everybody knows about ArrayList in Java because the easiest way (up to Java9 at least) to create a List is to call new ArrayList(). The Java List interface is mutable, so no surprises here.
Arrays$ArrayList is probably not as widely known. It is just a thin wrapper over an array to present it as a List. You cannot create it directly but it’s returned by Arrays.asList() and since Java9 by List.of(). Since it is just a view over an array, it allows to read and write values in a specific position of the original array but not to change the array size, so set() is working fine butadd() and remove() methods return an exception.
We can now look into the Kotlin implementation of mutableListOf() and listOf() in kotlin-stdlib-common.
`/**
* Returns a new [MutableList] with the given elements.
* @sample samples.collections.Collections.Lists.mutableList
*/
public fun <T> mutableListOf(vararg elements: T): MutableList<T> =
if (elements.size == 0) ArrayList() else ArrayList(ArrayAsCollection(elements, isVarargs = true))mutableListOf() is just creating a new java ArrayList instance as we saw before.
The declaration of listOf() is more interesting:
/**
* Returns a new read-only list of given elements. The returned list is serializable (JVM).
* @sample samples.collections.Collections.Lists.readOnlyList
*/
public fun <T> listOf(vararg elements: T): List<T> = if (elements.size > 0) elements.asList() else emptyList()[...]/**
* Returns a [List] that wraps the original array.
*/
public expect fun <T> Array<out T>.asList(): List<T>
It uses the expect keyword and it has no code. This means that on different platforms (KotlinJS, KotlinNative, etc.) there could be different implementations.
From the Kotlin documentation:
Kotlin provides a mechanism of expected and actual declarations. With this mechanism, a common module can define expected declarations, and a platform module can provide actual declarations corresponding to the expected ones.
So where is the real code? Inside some JVM only jar, we need to find a method with the same name and the actual keyword.
And here it is. In the generated file _ArraysJvm.kt, part of kotlin-stdlib.jar.
public actual fun <T> Array<out T>.asList(): List<T> {
return ArraysUtilJVM.asList(this)
}Which refers to a Java class in Kotlin stdlib for JVM:
class ArraysUtilJVM {
static <T> List<T> asList(T[] array) {
return Arrays.asList(array);
}
}Now we can see that listOf() returns a Java mutable list (java.util.Arrays$ArrayList) under the Kotlin non-modifiable List interface (kotlin.collections.List).
Part III — unveiling the mystery
But it was at this point that I realized there was an elephant in the room!
Adding a Kotlin interface to an existing Java class?
That should not be possible!
This is true both for ArrayList and Arrays$ArrayList which are implementing Kotlin MutableList, and by consequence, List.
In the JVM there is (unfortunately) no way to add an Interface to an existing Class. So I was intrigued…
To see how this magic is working we can start looking at how is MutableList is implemented in ByteCode. If we look at this piece of Kotlin code:
if (list.size > 1 && list is MutableList<T>) {...}We can see how it is translated in ByteCode:
LINENUMBER 21 L1
ALOAD 0
INVOKEINTERFACE java/util/List.size ()I (itf)
ICONST_1
IF_ICMPLE L2
ALOAD 0
INVOKESTATIC kotlin/jvm/internal/TypeIntrinsics.isMutableList (Ljava/lang/Object;)Z
IFEQ L2
L3The important things here are:
1) methods on List are actually called using the java.util.List interface, not kotlin.collections.List.
2) the check on the interface is not using the standard ByteCode instructionINSTANCEOF but a static method on a class called TypeIntrinsics.
As a matter of fact, kotlin.collections.List is a just a mock interface. It’s there for the syntax checking but it disappears from the compiled code and all the calls are mapped on java.util.List.
No matter what you do you cannot implement Kotlin List!
You are probably thinking now: “com’on, what if I write a new class in Kotlin implementing Kotlin List?”.
Ok, let’s try:
data class NonMutableList<T>(private val origList: List<T>): List<T> by origListUsing implementation delegation is a nice trick to avoid writing all the boilerplate code.
So what about our new class NonMutableList? Looking at the generated ByteCode we can see:
public final class com/ubertob/immutableCollections/NonMutableList implements java/util/List kotlin/jvm/internal/markers/KMappedMarker {There you go, Kotlin List interface has disappeared! We will discuss soon also about KMappedMarker interface which has been added.
You may wonder about the missing methods of java List. No worry they got generated for us by the Kotlin compiler, for example:
public addAll(Ljava/util/Collection;)Z
NEW java/lang/UnsupportedOperationException
DUP
LDC "Operation is not supported for read-only collection"
INVOKESPECIAL java/lang/UnsupportedOperationException.<init> (Ljava/lang/String;)V
ATHROW
MAXSTACK = 3
MAXLOCALS = 2What about the second point and cast checking?
TypeIntrinsics is a Java class and we can look at the code of isMutableList (asMutableList is similar):
public static boolean isMutableList(Object obj) {
return obj instanceof List &&
(!(obj instanceof KMappedMarker) || obj instanceof KMutableList);
}You can see that it is checking two special interfaces which are used by the compiler and work like markers: KMutableList and KMappedMarker. Their use is defined in the file mutabilityMarkerInterfaces.kt. We saw that KMappedMarker is automatically added to any new List implementation written in Kotlin.
I couldn’t find much information about these markers and how they work in the compiler, but the final result seems that all Java implementation of List are recognized as MutableList together with only the Kotlin classes that explicitly implement MutableList interface.
In other words, if you write a Kotlin class implementing List, it will not implement MutableList.
So if we check our newly created NonMutableList with the code at the beginning of this post, we can see that is not implementing MutableList.
class com.ubertob.immutableCollections.NonMutableList
before NonMutableList(origList=[albert, brian, charlie])
later NonMutableList(origList=[albert, brian, charlie])More generally, everything discussed here is not limited to List but it is valid for all Java collection related classes. Any check, cast or access on Kotlin other collections interfaces like Map, Set, Collection, Iterable, etc. is directly translated at compile time on the equivalent Java collection.
As an aside, my first test was calling list.remove(0) instead of swapping elements. In that case, I’ve got a UnsupportedOperationException. Thanks to Nicolai Parlog for reminding me of Arrays$ArrayList.set().
In the same Twitter thread, Andrey Breslav (the designer of Kotlin) confirmed Kotlin collection interfaces don’t really exist.
Part IV — Conclusions
A big part of the success of Kotlin as a language is the seamless integration with Java code. I can see that their choice of using Java collections in “stealth” mode is a very pragmatical compromise between clean design and productivity.
Personally, I would also like to have an ImmutableList interface deriving from List in the Kotlin stdlib with a native Kotlin implementation to be able to force immutability better.
In any case, I hope you enjoyed reading this post at least half as much as I enjoyed writing it. Kotlin is a fantastic language and it is really interesting how it is implemented!
If you like more posts like this, please applaud it and follow me on Twitter and Medium.
