Tech @ Runtastic • 28.11.2017 • Runtastic Tech Team

Kotlin Collections Inside. Part 1

by Andrew Khrystian,
Software Engineer Android @Runtastic

We use collection every day in Java/Android development for different purposes: modifying data collections and displaying a UI with a list of items as well as business logic-related processes. Java collections are quite straightforward and an easy component for simple use cases. At the same time, we have a lot of different collection interface implementations. It’s the developer’s task to choose the right implementation for the given purpose. Of course, you still have Java to Kotlin compatibility, so all Java collections are available for Kotlin applications as well. Let’s look at what Kotlin collections actually are. Here is a general scheme of a Kotlin collection framework:

As you can see, the immutability principle was implemented, which means that you cannot perform modifications on collections. The first interface in the collections hierarchy is Iterable. It provides the iterator that gives you the possibility to iterate your collection. MutableIterable extends Iterable and provides the MutableIterator for mutable collections.

The iterator has the hasNext() and next() methods

public abstract operator fun hasNext(): kotlin.Boolean
public abstract operator fun next(): T

MutableIterator extends the iterator and also provides the remove() method:

public abstract fun remove(): kotlin.Unit

Let’s look at immutability in practice. Here I’ve extended the iterator interface and implemented two of the required methods.

class IteratorExample: Iterator<Any>{
    override fun hasNext(): Boolean = false
    override fun next(): Any = Any()
}

Looks pretty clear. Let’s look at the bytecode to understand how it actually works.

public final class client/root/com/client/flow/repository/IteratorExample implements java/util/Iterator kotlin/jvm/internal/markers/KMappedMarker  {
// access flags 0x1
  public hasNext()Z
   L0
    LINENUMBER 8 L0
    ICONST_0
    IRETURN
   L1
    LOCALVARIABLE this Lclient/root/com/client/flow/repository/IteratorExample; L0 L1 0
    MAXSTACK = 1
    MAXLOCALS = 1
// access flags 0x1
  public next()Ljava/lang/Object;
  @Lorg/jetbrains/annotations/NotNull;() // invisible
   L0
    LINENUMBER 9 L0
    NEW java/lang/Object
    DUP
    INVOKESPECIAL java/lang/Object.<init> ()V
    ARETURN
   L1
    LOCALVARIABLE this Lclient/root/com/client/flow/repository/IteratorExample; L0 L1 0
    MAXSTACK = 2
    MAXLOCALS = 1
// access flags 0x1
  public <init>()V
   L0
    LINENUMBER 6 L0
    ALOAD 0
    INVOKESPECIAL java/lang/Object.<init> ()V
    RETURN
   L1
    LOCALVARIABLE this Lclient/root/com/client/repository/IteratorExample; L0 L1 0
    MAXSTACK = 1
    MAXLOCALS = 1
// access flags 0x1
  public remove()V
    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 = 1
}

Okay, so what can we see here? There is bytecode realization of our methods, and we have the remove method that is throwing java.lang.UnsupportedOperationException with the message: “Operation is not supported for read-only collection”. You might be wondering how we call this method if we don’t have any realization. This is impossible in Kotlin, but we can call it from Java class. Take a look:

public class JavaClass {
    public JavaClass() {
        IteratorExample iteratorExample = new IteratorExample();
        iteratorExample.remove();
    }
}

This is possible, but you will receive an exception. So immutability in Kotlin collections is a fake. It totally works for Kotlin classes, but in Java, you still have to be careful when you are using custom immutable Kotlin collections. Summing up we can say that:

1.) Kotlin collections in Java can be immutable.
2.) Java collections in Kotlin classes are always mutable.

Simple. For this time, that’s all you need to know.

Let’s take a look at the realizations that the Kotlin collection framework offers.

List and MutableList

List is the most useful collection for many different cases. How does it work in Kotlin?

1. Structure:

List extends the Collection interface and describes the following methods:

override val size: Int
override fun isEmpty(): Boolean
override fun contains(element: @UnsafeVariance E): Boolean
override fun iterator(): Iterator<E>
override fun containsAll(elements: Collection<@UnsafeVariance E>): Boolean
public operator fun get(index: Int): E
public fun indexOf(element: @UnsafeVariance E): Int
public fun lastIndexOf(element: @UnsafeVariance E): Int
public fun listIterator(): ListIterator<E>
public fun listIterator(index: Int): ListIterator<E>
public fun subList(fromIndex: Int, toIndex: Int): List<E>

And as you can see, there are no methods for changing list elements. Obviously, they are described in the MutableList interface

override fun add(element: E): Boolean
override fun remove(element: E): Boolean
override fun addAll(elements: Collection<E>): Boolean
public fun addAll(index: Int, elements: Collection<E>): Boolean
override fun removeAll(elements: Collection<E>): Boolean
override fun retainAll(elements: Collection<E>): Boolean
override fun clear(): Unit
public operator fun set(index: Int, element: E): E
public fun add(index: Int, element: E): Unit
public fun removeAt(index: Int): E
override fun listIterator(): MutableListIterator<E>
override fun listIterator(index: Int): MutableListIterator<E>
override fun subList(fromIndex: Int, toIndex: Int): MutableList<E>

MutableList extends MutableCollection, and MutableCollection extends Collection.

You have to remember that immutability works the same way for the list as it does for the iterators.

2. Creation

To create an immutable list, there are a few default methods in Collections.kt:

var list = emptyList()

Here we are creating an empty immutable list. This function returns simple List interface realization that is called EmptyList:

internal object EmptyList : List<Nothing>, Serializable, RandomAccess {
    private const val serialVersionUID: Long = -7390468764508069838L
    override fun equals(other: Any?): Boolean = other is List<*> && other.isEmpty()
    override fun hashCode(): Int = 1
    override fun toString(): String = "[]"
    override val size: Int get() = 0
    override fun isEmpty(): Boolean = true
    override fun contains(element: Nothing): Boolean = false
    override fun containsAll(elements: Collection<Nothing>): Boolean = elements.isEmpty()
    override fun get(index: Int): Nothing = throw IndexOutOfBoundsException("Empty list doesn't contain element at index $index.")
    override fun indexOf(element: Nothing): Int = -1
    override fun lastIndexOf(element: Nothing): Int = -1
    override fun iterator(): Iterator<Nothing> = EmptyIterator
    override fun listIterator(): ListIterator<Nothing> = EmptyIterator
    override fun listIterator(index: Int): ListIterator<Nothing> {
        if (index != 0) throw IndexOutOfBoundsException("Index: $index")
        return EmptyIterator
    }
    override fun subList(fromIndex: Int, toIndex: Int): List<Nothing> {
        if (fromIndex == 0 && toIndex == 0) return this
        throw IndexOutOfBoundsException("fromIndex: $fromIndex, toIndex: $toIndex")
    }
    private fun readResolve(): Any = EmptyList
}

This class is also part of Collections.kt.

To create a list with elements, we need to use the listOf(vararg elements: T) method

val list = listOf("One", "Two", "Three")

listOf also provides two overloaded methods

val list = listOf()
val listTwo = listOf("One")

The first method calls emptyList(), and the second one returns an immutable list with one element. Lets see how the listOf function actually works

public fun <T> listOf(vararg elements: T): List<T> = if (elements.size > 0) elements.asList() else emptyList()

Here we can see that it uses the function asList() to create a new list containing all elements. If the size of the elements is equal to 0, the function returns a simple empty list. The asList function is implemented in the _Arrays.kt class and its realization looks like:

public fun <T> Array<out T>.asList(): List<T> {
    return ArraysUtilJVM.asList(this)
}

ArraysUtilsJVM is the java class with a single asList() method. This method simply calls Java Arrays.asList() that as you know returns a simple ArrayList containing all the required elements. So basically your listOf() returns a Java ArrayList, but during compilation, all the methods that are responsible for the list changes will be replaced by another realization. As you know, this realization throws java.lang.UnsupportedOperationException when trying to modify the list.

Everything is much simpler in mutable lists. There are also a few methods:

val list = mutableListOf("One", "Two", "Three")
val arrayList = arrayListOf("One", "Two", "Three")
val emptyMutableList = mutableListOf<Any>()
val emptyArrayList = arrayListOf<Any>()

To understand how it works, let’s look at the source code.

/**
public fun <T> mutableListOf(vararg elements: T): MutableList<T>
        = if (elements.size == 0) ArrayList() else ArrayList(ArrayAsCollection(elements, isVarargs = true))
public fun <T> arrayListOf(vararg elements: T): ArrayList<T>
        = if (elements.size == 0) ArrayList() else ArrayList(ArrayAsCollection(elements, isVarargs = true))

These two functions are very similar. The only difference is the return type. In the first function, the return type is MutableList and in the second,  java.util.ArrayList. It looks a little bit confusing because the java.util.ArrayList does not extend kotlin.MutableList, and at the same time, MutableList doesn’t have any connection to java.util.List. Perhaps we have to go deeper.

 

 

I’ve created a simple class that extends MutableList

class MutableMagic(override val size: Int) : MutableList<Any> {
    
    override fun contains(element: Any): Boolean = false
    override fun get(index: Int): Any = null
    override fun indexOf(element: Any): Int = 0
    
    ...
}

Let’s look at the bytecode below:

public final class root/com/yalantisopentour/data/MutableMagic implements java/util/List kotlin/jvm/internal/markers/KMutableList  {
// access flags 0x1
  public contains(Ljava/lang/Object;)Z
    @Lorg/jetbrains/annotations/NotNull;() // invisible, parameter 0
   L0
    ALOAD 1
    IFNULL L1
    GOTO L2
   L1
    ICONST_0
    IRETURN
   L2
    ALOAD 1
    LDC "element"
    INVOKESTATIC kotlin/jvm/internal/Intrinsics.checkParameterIsNotNull (Ljava/lang/Object;Ljava/lang/String;)V
   L3
    LINENUMBER 8 L3
    ICONST_0
    IRETURN
   L4
    LOCALVARIABLE this Lroot/com/yalantisopentour/data/MutableMagic; L0 L4 0
    LOCALVARIABLE element Ljava/lang/Object; L0 L4 1
    MAXSTACK = 2
    MAXLOCALS = 2
....

It’s not all of the bytecode, just the most interesting part. In the original code, there is only one extended interface, but in bytecode, there is also java.util.List. It explains why we don’t get type exceptions in the mutableListOf() or listOf() methods.

In one of our next articles, we will show you how to deal with sets and maps. We hope you’ve enjoyed diving into Kotlin Collections. Feel free to leave comments and questions. We’d love to hear your feedback.

***

Runtastic Tech Team

We are made up of all the technical departments at Runtastic like iOS, Android, Web, Infrastructure, Data Engineering, etc. We’re eager to tell you about how we work here at Runtastic, what our processes look like, the cool stuff we create and what we have learned along the way. And BTW we are always looking for talented people who want to join us!


View all posts by Runtastic Tech Team »