Understanding Kotlin Generics - Covariance and Invariance

Tags:

What does covariant mean?

Int can be used as Any (Any corresponds to Object in Java).

Then:

  1. Can List<Int> be treated as List<Any>?
  2. Can MutableList<Int> be treated as MutableList<Any>?

The answer depends on whether the generic class being used is covariant or invariant with respect to its type parameter.

  1. List<Int> can be used as List<Any> (List is covariant).
  2. MutableList<Int> cannot be used as MutableList<Any> (MutableList is not covariant, meaning it is invariant).

When a generic class is covariant, the parent-child relationship of the type specified as the type argument is preserved in the parent-child relationship of the types generated by that generic class. For example, List<E> is covariant with respect to its type parameter E, so List<Int> can be treated as List<Any> (List<Int> is considered a subtype of List<Any>).

List<Int> can be treated as List<Any>

fun showElems(list: List<Any>) {
    for (e in list) {
        println(e)
    }
}

fun main() {
    val a = listOf(0, 1, 2) // List<Int>
    showElems(a)            // OK!
}

On the other hand, MutableList<E> is not covariant with respect to the type parameter E, so MutableList<Int> cannot be treated as MutableList<Any>. It is treated as a completely incompatible type.

Why does this difference occur? It is easy to understand if you consider the following code.

MutableList<Int> cannot be treated as MutableList<Any>

fun addElems(list: MutableList<Any>) {
    list.add("Hello")
    list.add("World")
}

fun main() {
    val a = mutableListOf(0, 1, 2)  // MutableList<Int>
    addElems(a)                     // Compile Error!
}

If the code above were allowed, arbitrary elements other than Int could be added to an object of type MutableList<Int>. Therefore, MutableList<E> is defined as not covariant with respect to the type parameter E, and the code above causes a compile error.

There is no problem if the elements of List<Int> are only used as the more general type Any, but it is a problem for MutableList<Int> to accept the more general type Any.

Covariance and invariance are somewhat difficult, but they are very important concepts when working with Kotlin generics, so let’s summarize them again.

When A is a subtype of B, List<A> becomes a subtype of List<B>. Such a generic class is called covariant. Even if A is a subtype of B, MutableList<A> cannot be a subtype of MutableList<B>. Such a generic class is called invariant, meaning it is not covariant.

Defining a covariant generic class

To define a generic class that is covariant with respect to a type parameter, add the out keyword to the type parameter. Conversely, if you define a type parameter without any modifier, the generic class is invariant by default.

class Holder<out T>(val elem: T) {
    fun get(): T = elem
}

Adding out to a type parameter is also a declaration that the type parameter will be used only for output in the implementation of that generic class. Using it for output means using that type parameter only in return-value positions. Such classes are sometimes called producers, and sample code often uses Producer as the class name. Personally, that name can make sample code harder to understand, so this article uses the class name Holder.

In technical terms, using a type in output positions such as getters is called using it in an out position, and using it in input positions such as setters is called using it in an in position. You can add out to a type parameter only when that type parameter is used only in out positions, or more precisely, when it is not used in in positions.

For example, in the code above, the type parameter T is used only as the return type of the getter, which is an out position. It is also used as a constructor parameter, but a constructor val parameter essentially defines a getter, so it is considered an out position. Because the type parameter T is not used in any in position, the out modifier can be added, making the generic class covariant.

If a type parameter marked with out is used in an in position as follows:

class Holder<out T>(val elem: T) {
    fun dump(t: T) { ... }  // ERROR
}

Type parameter T is declared as 'out' but occurs in 'in' position in type T

This compile error occurs because allowing this usage could break type safety, as in the MutableList example described earlier.

Now suppose there are Animal and Bird classes with an inheritance relationship. Bird is a subtype of Animal.

open class Animal {
    fun eat() { println("EAT") }
}

class Bird : Animal() {
    fun fly() { println("FLY") }
}

And suppose the doEat function receives Holder<Animal> as a parameter.

fun doEat(holder: Holder<Animal>) {
    val animal = holder.get()
    animal.eat()
}

Because the Holder class is defined as a covariant generic class by adding out to type parameter T, a Holder<Bird> object can be used instead of a Holder<Animal> object. Therefore, a Holder<Bird> object can be passed to the doEat function as follows.

val holder: Holder<Bird> = Holder(Bird())
doEat(holder)

This is the effect of defining the type parameter with out, as in class Holder<out T>. If it had been defined as an invariant class like class Holder<T> without out, calling doEat(holder) would produce the following error.

Type mismatch: inferred type is Holder<Bird> but Holder<Animal> was expected

This is because Holder is not covariant, so there is no compatibility between Holder<Bird> and Holder<Animal>. However, there is a small way around this: on the side that uses the generic class, in this case where the doEat function is defined, you can add out as follows and declare that it will be used as a covariant type parameter.

fun doEat(holder: Holder<out Animal>) {
    val animal = holder.get()
    animal.eat()
}

This indicates that even though the Holder class itself is not defined as covariant, at least this function implementation uses it as a covariant class. In other words, Holder<Bird> may be passed instead of Holder<Animal>. Adding the out modifier to a type argument at the point where a generic class is used is called use-site variance. More details are explained below.

Definitions of Kotlin List and MutableList

Now let’s look at the definitions of Kotlin’s List and MutableList interfaces.

interface List<out E> : Collection<E> { ... }
interface MutableList<E> : List<E>, MutableCollection<E> { ... }

The type parameter E of the List interface has out, but the MutableList interface does not. Therefore, List is a covariant generic class with respect to type parameter E, and MutableList is an invariant generic class.

The out modifier on a type parameter is often used for factory-like classes or immutable data holder classes. However, a function such as clear() can modify the object’s contents without receiving any parameter, so covariant classes are not limited to immutable classes.

Defining a contravariant generic class

A concept close to covariance, but with the opposite property, is contravariance. Types generated from a covariant generic class preserve the parent-child relationship of the type specified as the type argument, but types generated from a contravariant generic class reverse that relationship. This is hard to understand in words alone, so let’s look at code.

First, let’s review covariance. A covariant type parameter is marked with out.

interface List<out E>

List<Int> is a subtype of List<Any>.

Next is an example of contravariance. A typical example of a contravariant interface is the Comparator interface. A contravariant type parameter is marked with in.

interface Comparator<in T> {
    fun compare(a: T, b: T): Int
}

Comparator<Int> becomes a supertype of Comparator<Any>. In other words, Comparator<Any> becomes a subtype of Comparator<Int>. Because the parent-child relationship is reversed compared with covariance, this is called contravariance.

Why is the parent-child relationship reversed like this? Consider the relationship between Comparator<Any> and Comparator<Int>. A function that receives Comparator<Int> as a parameter can receive a Comparator<Any> object.

val anyComp = Comparator<Any> { a, b ->
    a.hashCode() - b.hashCode()
}

val intList = mutableListOf(3, 1, 5)
intList.sortWith(anyComp)

This works because an implementation of Comparator<Any> only refers to the Any interface, so there is no problem using that implementation to compare Int objects.

A type parameter can be marked with in only when it is limited to in positions, or more precisely, when it is not used in out positions such as the return value of public functions. Because the generic class uses the type parameter only to accept or consume values, such a generic class is sometimes called a consumer. Therefore, sample code sometimes names contravariant generic classes Consumer.

Kotlin’s Continuation interface is also one of the contravariant generic interfaces.

interface Continuation<in T> {
   val context: CoroutineContext
   fun resume(value: T)
   fun resumeWithException(exception: Throwable)
}

Declaration-site variance and use-site variance

As briefly mentioned in the explanation of the Holder class, when variance modifiers such as out or in are added to type parameters of a generic class, Kotlin divides where they are added into two patterns.

  • declaration-site variance
    • Modifies type parameters with out or in when declaring a class or interface.
  • use-site variance
    • Adds out or in to type arguments when using an already defined generic class.

Declaration-site variance

The following is the method of adding the out or in modifier to a type parameter when declaring an interface, as in the List interface.

interface List<out E> : Collection<E> { ... }

In this case, places that use this List interface treat it as covariant by default. For example, a function that receives List<Number> can receive List<Int> or List<Double>.

fun showNumbers(nums: List<Number>) {
    println(nums)
}

fun main() {
    showNumbers(listOf(1, 2, 3))       // can pass List<Int>
    showNumbers(listOf(0.1, 0.2, 0.3)) // can also pass List<Double>
}

Put more simply, the List interface allows the following assignment.

val nums: List<Number> = listOf<Int>(1, 2, 3)  // OK

Conversely, because the MutableList interface is not defined as covariant, meaning it is invariant, the following assignment is not possible.

val nums: MutableList<Number> = mutableListOf<Int>(1, 2, 3)  // NG

Use-site variance

This is the method of adding the in or out keyword to a type argument when using a generic class.

For example, Kotlin’s MutableList is an invariant generic class, so MutableList<Int> cannot be treated as MutableList<Number> as follows.

val list: MutableList<Number> = mutableListOf<Int>(1, 2, 3)  // ERROR

Even with such an invariant class, adding the out keyword at the usage site lets that part be treated as covariant. As a side effect, elements can no longer be handled in an in position, so functions such as add() cannot be called.

val list: MutableList<out Number> = mutableListOf<Int>(1, 2, 3)
list.add(1.5)  // ERROR

Using type arguments in this way is technically called type projection. In this case, because the out keyword is attached, it is called out-projected.

As a more practical example, consider a function that copies the contents of an array.

fun <T> copyArray(src: Array<T>, dst: Array<T>) {
    assert(src.size == dst.size)
    for (i in src.indices) {
        dst[i] = src[i]
    }
}

Kotlin’s Array class is an invariant generic class like MutableList because its type parameter has no variance modifier (out or in), as shown below.

class Array<T>

Therefore, Array<Int> and Array<Number> are not compatible, and the following code causes an error.

val arr1 = arrayOf<Int>(1, 2, 3)
val arr2 = arrayOfNulls<Number>(3)
copyArray(arr1, arr2)  // ERROR

Therefore, using the use-site variance mechanism, add the in keyword to the type parameter of the dst parameter and make it contravariant. Adding the in keyword declares that this dst object only consumes elements of type T.

fun <T> copyArray2(src: Array<T>, dst: Array<in T>) {
    assert(src.size == dst.size)
    for (i in src.indices) {
        dst[i] = src[i]
    }
}

Then, if Array<Int> is passed to the src parameter of this function, Array<Number> and similar arrays can be passed to the dst parameter as supertypes.

val arr1 = arrayOf<Int>(1, 2, 3)
val arr2 = arrayOfNulls<Number>(3)
copyArray2(arr1, arr2)  // OK

This means the Array class was originally defined as invariant, but this function can use it contravariantly.

For reference, Java has only this use-site variance, and it uses upper and lower bounds such as <? extends Hoge> and <? super Hoge>.

In position and out position

To make a type parameter covariant, add the out modifier. To make it contravariant, add the in modifier. The constraints when adding these modifiers are as follows.

  • out: cannot be added to a type parameter used in an in position.
  • in: cannot be added to a type parameter used in an out position.

Here is a summary of which references to type parameters are considered in positions or out positions.

  • in position
    • Parameters of public functions
    • Setters of public properties, meaning constructor parameters marked with var. Because a setter is defined internally, this is considered an in position.
  • out position
    • Return values of public functions
    • Getters of public properties, meaning constructor parameters marked with val or var. Because a getter is defined internally, this is considered an out position.
  • Neither in position nor out position, so covariance or contravariance is possible
    • Parameters and return values of private functions or properties, because private functions do not risk type misuse.
    • Constructor parameters that are not marked with either val or var, because they are called only during initialization and have little risk of type-parameter misuse.

Kotlin arrays are invariant, Java arrays are covariant

Kotlin’s Array class is defined as an invariant generic class. Therefore, by default, no parent-child relationship occurs between different types generated from the Array class, except when using the type projection mechanism described earlier.

val arr: Array<Any> = arrayOf<Int>(1, 2, 3) // ERROR

On the other hand, Java arrays are defined as covariant. Therefore, the following assignment was possible.

Integer[] nums = {1, 2, 3};
Object[] objs = nums;
objs[0] = "ABC"; // Runtime ERROR

The problem with this specification is that code that stores a String object in an Integer[] array can be compiled, as shown above. To solve this problem, Kotlin made the Array<E> class invariant, just like IntArray and CharArray, which contain primitive elements. Because Array<Int> and Array<Any> are not compatible, there is no risk of unexpected element types being stored as in the Java example above.

Difference between List<Any?> and List<*> (star projection)

When defining a function that receives an object of a generic type, and you do not particularly care about element type information, you can use the more concise star projection syntax instead of a type parameter.

fun dump(list: List<*>) {
    for ((index, elem) in list.withIndex()) {
        println("$index: $elem")
    }
}

fun main() {
    val list = listOf("AAA", "BBB", "CCC")
    dump(list)
}

The dump function above can be defined with a type parameter as follows and still work the same way, but because the function definition does not use type information, star projection syntax is simpler.

fun <T> dump(list: List<T>)

Specifying <*> in the type parameter position and specifying <Any?> may feel similar, but they have the following clear difference.

  • MutableList<*>: a list containing elements of some specific type
  • MutableList<Any?>: a list that can contain anything

A list referenced as MutableList<*> may actually be MutableList<Int>, but a list referenced as MutableList<Any?> is necessarily MutableList<Any?>.

A function that receives MutableList<*> does not care about the concrete type, but it expects a list created by the caller with a concrete type argument. Therefore, the following code causes a compile error because it is not type-safe.

fun addSomething(list: MutableList<*>) {
    list.add("Hello")  // ERROR: you must not insert a String arbitrarily.
}

fun main() {
    var intList = mutableListOf(1, 2, 3)
    addSomething(intList)
}

On the other hand, MutableList<Any?> indicates a list that can store anything.

fun addSomething(list: MutableList<Any?>) {
    list.add("Hello")
}

fun main() {
    var list = mutableListOf<Any?>(1, "A", null)
    addSomething(list)
}

Because MutableList is an invariant class, a function that receives MutableList<Any?> can receive only a MutableList<Any?> object.

Star projection has the characteristic of making elements read-only.

val list1 = mutableListOf(1, 2, 3)
list1.add(100)  // OK

val list2: MutableList<*> = list1
list2.add(100)  // ERROR

For reference, Java uses ? as its wildcard character instead of *, but like Kotlin, it has the effect of making collection classes read-only.

List<String> strList = new ArrayList<>();
strList.add("Hello");  // OK

List<?> roList = strList;
roList.add("World");  // ERROR