Generics and Variance

In the previous lesson we saw that an extension is chosen by the static type: the decision was made on the declared type of the variable. In this lesson we put a parameter inside that declared type. List<Int> and List<String> look like two separate types; the questions are whether the two are really separate at run time, and whether a List<Int> can take the place of a List<Any>.

Generics are the way of writing a class or a function with a type parameter whose type is decided later: class Holder<T>. The parameter is filled with a concrete type at the call. A constraint is a condition that limits the types the type parameter can be filled with: T : Comparable<T> accepts only comparable types.

The measure is the same as in every lesson of this course: what makes these two values equal? In M08/K02 we looked at which type makes a decision; here the question is different: we measure whether the type parameter affects equality.

The Measurement Setup

Criterion stays in the first block, in the same form, in every lesson. Each observation carries three values: first, twin (a value built separately with the same recipe), and other (a value that differs in only one respect). The rule sees the result, not the reason.

// Criterion.kt — classifies the criterion that makes two values equal
class Criterion(val label: String, first: Any?, twin: Any?, other: Any?) {
    val sameObject = first === twin
    val equalTwin = first == twin
    val equalOther = first == other

    val name: String = when {
        sameObject -> "singleton"
        !equalTwin -> "identity"
        !equalOther -> "content"
        else -> "partial-content"
    }

    fun report() {
        println("$label: same-object=$sameObject, twin=$equalTwin, other=$equalOther -> $name")
    }
}

fun summarize(checks: List<Criterion>) {
    for (name in listOf("singleton", "identity", "content", "partial-content")) {
        println("$name: ${checks.count { it.name == name }}")
    }
}

TN35. Because the parameters of Criterion are Any? in this lesson, values with type parameters also look like ordinary objects when they are passed to it; the measurement sees the run-time object, not the static type.

Generic Class, Function, and Constraint

The block below writes three generic definitions. Holder<T> holds a value of any type. largest works only on comparable types, with the T : Comparable<T> constraint. sumInts asks for two constraints together: the where clause is the way to put more than one constraint on a single parameter.

// Main.kt — generic class, upper-bound constraint, and where
class Holder<T>(val item: T) {
    fun describe(): String = "box:" + item
}

fun <T : Comparable<T>> largest(first: T, second: T): T =
    if (first >= second) first else second

fun <T> sumInts(first: T, second: T): Int where T : Number, T : Comparable<T> =
    first.toInt() + second.toInt()

fun main() {
    println(Holder(7).describe())
    println(Holder("ada").describe())
    println(largest(3, 9))
    println(largest("apple", "pear"))
    println(sumInts(2, 3))
}

box:7
box:ada
9
pear
5

The same Holder was used with an Int and with a String; the type parameter was inferred at each call, and no type was added to the text. largest worked with both numbers and strings, because both are Comparable. sumInts compiles only for types that are both Number and Comparable; Int satisfies both.

TN36. That passing a type that does not satisfy the constraint to largest fails to compile was not measured separately; only calls that satisfy the constraint were written.

No Type Parameter at Run Time

The type parameter of a generic class is checked at compile time and is not carried to run time. This is called type erasure. The result is that two values of the same generic type built with different parameters are of the same class at run time. More striking, some standard functions return a single shared object: an empty list can be the same object for every element type. We measure this.

We also put three small tools side by side. A star projection, written as List<*>, allows reading without knowing the type parameter. A parameter marked reified in an inline function becomes readable at run time; this is the only exception to erasure, because the compiler expands the body of that function at the call site.

// Main.kt — type erasure and reified
class Holder<T>(val item: T)

fun countAll(values: List<*>): Int = values.size

inline fun <reified T> nameOf(): String = T::class.simpleName ?: "unnamed"

fun main() {
    val ints = Holder(1)
    val texts = Holder("ada")
    println(ints::class == texts::class)
    println(countAll(listOf(1, 2, 3)))
    println(countAll(listOf("a", "b")))
    println(nameOf<Int>())
    println(nameOf<String>())

    val checks = listOf(
        Criterion("empty-lists", emptyList<Int>(), emptyList<String>(), listOf(1)),
        Criterion("boxes", ints, texts, Holder(2)),
    )
    for (check in checks) check.report()
    summarize(checks)
}

true
3
2
Int
String
empty-lists: same-object=true, twin=true, other=false -> singleton
boxes: same-object=false, twin=false, other=false -> identity
singleton: 1
identity: 1
content: 0
partial-content: 0

ints and texts were built with different type parameters, but their classes came out the same. countAll read the sizes of the two lists without knowing their elements. nameOf showed the limit of erasure: with reified the type parameter could be read at run time, and the names Int and String were printed.

The first line of the criterion table is singleton: emptyList<Int>() and emptyList<String>() resolved to the same object. Although they were called with two separate type parameters, there was a single empty list in hand, because the element type is not stored in the object. The second line is identity: Holder is an ordinary class that does not redefine equals. The type parameter did not change equality in either direction.

Variance: out and in

Even if the type parameter is erased inside the object, the compiler checks it in assignments. Variance tells whether a Box<Sub> value can take the place of a Box<Super>. It has three forms. Covariance means a box of a subtype can take the place of a box of a supertype, and it is marked with out: the parameter can be used only in an output position, that is, in a return type. Contravariance is the opposite and is marked with in: the parameter can be used only in an input position, that is, as a function parameter. Invariance is the state in which neither is allowed, and it is the default of an unmarked type parameter.

// Main.kt — assignment with out and in
class Source<out T>(private val value: T) {
    fun get(): T = value
}

class Sink<in T> {
    fun accept(item: T): String = "accepted:" + item
}

fun main() {
    val ints: List<Int> = listOf(1, 2)
    val anys: List<Any> = ints
    println(anys.size)

    val source: Source<Any> = Source<String>("ada")
    println(source.get())

    val sink: Sink<String> = Sink<Any>()
    println(sink.accept("ali"))
    Criterion("covariant-assignment", ints, anys, listOf<Any>("x")).report()
}

2
ada
accepted:ali
covariant-assignment: same-object=true, twin=true, other=false -> singleton

A List<Int> was assigned to a List<Any> variable, because List is read-only and declared with out T; no new object was built in that assignment, the same object was read with two different types, and the criterion came out singleton. A Source<String> also took the place of a Source<Any>. Sink worked in the opposite direction: a Sink<Any> took the place of a Sink<String> that accepts String, because a receiver that accepts every Any accepts a String as well.

A mutable list, on the other hand, cannot be covariant. We checked this first: the fragment below did not compile in Kotlin 2.4.21, which is why it stays without output.

val numbers: MutableList<Int> = mutableListOf(1)
val anys: MutableList<Any> = numbers

TN37. The reason for the rejection is that if a String could be added to a MutableList<Any>, the MutableList<Int> would be corrupted; this reasoning comes from the definition of the language and was not measured here with a separate block. Only the fact that the assignment does not compile was verified.

The Limits of Erasure

Erasure means that the type parameter cannot be read at run time. It has three consequences. First, you can ask whether a value is a List<*> but not whether it is a List<String>; second, an unchecked cast to List<String> can be made and the error appears only when an element is read; third, variance can be marked not only in the class declaration but also at the use site. The block below measures the three.

numbers is in fact a list that contains Int values, but it is held with the type Any. texts is an unchecked view of that list as a List<String>. sink is declared as MutableList<in Int>: the type parameter has been made contravariant at the use site.

// Main.kt — is List<*>, unchecked cast, and use-site variance
fun main() {
    val numbers: Any = listOf(1, 2, 3)
    println(numbers is List<*>)
    @Suppress("UNCHECKED_CAST")
    val texts = numbers as List<String>
    println(texts.size)
    val outcome = try {
        val first: String = texts[0]
        "read " + first
    } catch (e: ClassCastException) {
        "class-error"
    }
    println(outcome)
    val sink: MutableList<in Int> = mutableListOf<Any>("x")
    sink.add(5)
    println(sink.size)
    println(sink[1])
    Criterion("unknown-list", numbers, texts, listOf("a")).report()
}

true
3
class-error
2
5
unknown-list: same-object=true, twin=true, other=false -> singleton

numbers is List<*> came out true: a star projection is a question asked without knowing the type parameter. texts.size printed 3. Because the cast is unchecked, reading the size did not blow up, since it does not touch the elements. The error came when the first element was read as a String: the class-error line shows that the ClassCastException was caught. The compiler believed that texts was a List<String>, while the run time saw that the element was really an Int only at the moment of reading.

This is the price of erasure. Since the type parameter is not in the object at run time, the correctness of the cast cannot be checked there; the check is postponed until an element is read. The criterion line is singleton: numbers and texts are the same object. The cast did not build a new list, it gave the same object a new type label.

sink showed use-site variance. MutableList<in Int> is a view into which an Int can be added but which yields only Any? when read. After sink.add(5) the size became 2 and sink[1] printed 5; the first element had stayed in the list as "x". It is the same rule as out/in in the class declaration, made valid for a single variable.

TN38. We do not write the claim that the compiler gives a warning for an unchecked cast; the warning is not checked in this lesson. We wrote the @Suppress mark only to show that we accept the cast explicitly.

The Erasure Rule from the Measurements

The measurements of this lesson rest on a single fact: the type parameter is not in the object at run time. Three consequences of it were measured. Two empty lists came out as the same object even though their type parameters differ. The question is List<*> was answered, but the question List<String> could not be asked. And the unchecked cast did not blow up at once: texts.size printed 3, and the error appeared only when an element was read.

A common mistake is to assume that a cast is safe. A person who writes as List<String> sees that the compiler now counts the list as a List<String>, and everything in the following code looks fine. Yet the content of the object did not change; only the promise given to the code that reads it did. When the promise is broken, the error appears not on the line where the cast was made but on the line where the element was read. If these two lines are far from each other, finding the source of the error gets hard. For this reason, instead of casting a list that comes from outside, it is sturdier to build a new list by checking the elements one by one; this lesson did not measure that, it only showed the limit of the cast.

Variance can be marked in two separate places. If out or in is written in the class declaration, the rule holds in all uses of the class; if MutableList<in Int> is written at the use site, the rule holds only for that variable. The cost of the latter is in the reading direction: sink[1] printed 5, but since the type of the read value is Any?, you must first check its type to do anything with it.

The role of the constraint and of reified is also read together with erasure. A constraint says at compile time what the type parameter has to look like; it checks nothing at run time. reified gets past erasure only in inline functions, because the compiler writes the type information into the call site. These two tools narrow the limits of erasure, but they do not remove it.

Predicting Before Measuring

In erasure, prediction comes down to the question “what information exists at run time”. An object has a class; it has no type parameter. For this reason numbers is List<*> is expected to be true, texts.size to be 3, and a class error to appear when the first element is read as a String. All three of the results match the measurement. The prediction that does not match is “the cast line blows up”: there is no check that looks at the object during the cast.

In use-site variance, the prediction splits by direction. In the writing direction, MutableList<in Int> accepts an Int; in the reading direction, the type of the element is Any?. To say that the size will be 2, it is enough to know that the list had one element at the start and one element was added. The 5 that was read depends on knowing the position of the added value.

For the criterion line the prediction is simple. numbers and texts look at the same list, and the cast does not build a new object; so same-object is true and the criterion stays singleton. What makes these lines singleton is that the type information is not in the object: the information belongs not to the object but to the compiler that reads the code.

None of these predictions is a habit; all of them derive from a single sentence. The run time knows the class of the object, and it does not know the type parameter. If the result of an expression cannot be derived from this sentence, the expression is asking about something resolved at compile time, for example the validity of an assignment. Separating the compile-time question from the run-time question prevents most of the mistakes made with generics.

The Bounding Measurement

Since the type parameter is erased at run time, what makes two values of a generic type equal cannot be the type parameter: it has to be the element values. The block below measures this in two ways. A generic data class, Wrapper, is given 1 and 1L, that is, an Int and a Long. The second line compares two lists of type Any.

// Main.kt — equality in a generic data class looks at the value
data class Wrapper<T>(val value: T)

fun main() {
    val checks = listOf(
        Criterion("wrapper", Wrapper(1), Wrapper(1), Wrapper(1L)),
        Criterion("list-1-1L", listOf<Any>(1), listOf<Any>(1), listOf<Any>(1L)),
        Criterion("empty-and-full", emptyList<Int>(), emptyList<Int>(), listOf(1)),
    )
    for (check in checks) check.report()
    summarize(checks)
}

wrapper: same-object=false, twin=true, other=false -> content
list-1-1L: same-object=false, twin=true, other=false -> content
empty-and-full: same-object=true, twin=true, other=false -> singleton
singleton: 1
identity: 0
content: 2
partial-content: 0

The first two lines came out as content: two values built separately with the same recipe were equal, and the equality broke when 1L was put in place of 1. Wrapper(1) and Wrapper(1L) are not equal, because their value fields are an Int value and a Long value and equals looks at them; this comparison rests not on the type parameter but on the run-time values. The third line is singleton: the same empty list object.

Summary

• Generics let you write a class or a function with a type parameter; T : Comparable<T> is a constraint, and where is the way to put more than one constraint.
• The type parameter is erased at run time; emptyList<Int>() and emptyList<String>() are the same object, and reified gets past erasure in a function.
• out gives covariance and in gives contravariance; an unmarked parameter is invariant, and a MutableList<Int> cannot be assigned to a MutableList<Any> variable.
• A read-only List<Int> is assigned to a List<Any>; no new object is created in the assignment.
• In a generic data class, equality looks not at the type parameter but at the run-time values of the fields.
• The criterion of this lesson: singleton. Because the type parameter is erased, two empty lists called with different parameters are the same object.

Next Step

With this lesson the topic of types closes: from the single object to the delegated behavior, the function added from the outside, and the erased type parameter, we saw that equality always comes from the value itself. The next topic is “Collections and Concurrency Basics”, which begins with “Collection Types”: lists, sets, and maps are generic types too, and whether the values inside them count as equal depends not on the kind of the collection but on its content.