Variance

A lot was written about variance and its application in generics. This is another trial to explain variance and its practical usage. Let’s explore this using Kotlin. This article expects basic knowledge about generics.

---

Variance is a powerful way to allow your code to do more. It is most obvious when you consider generics with bounds — i.e. with a type that restricts the subset of possible generic argument types. Also, another important condition is a state, variance is usually allowed only for classes and interfaces (since it does not make sense for generic functions).

We split variance to three states: invariant, covariant and contravariant.

Invariant

I dug into this because I wanted to properly type Nextras Orm’s Collections (a PHP project typed via PHPStan). That is an ideal use-case for generics. Let’s have one immutable collection (in Kotlin):

interface Entity 

interface Collection<E : Entity> {
     fun getAll(): List<E>
}

When generic argument is “inferred” to specific type, by default the type is considered invariant. That means that such type cannot be assigned to the same generic and its generic parameter sub-type or super-type.

abstract class Vehicle : Entity
abstract class Car : Vehicle()
class Audi : Car()
class Skoda : Car()

fun test(carsCollection: Collection<Car>) {
   val vehicles: Collection<Vehicle> = carsCollection
   // compilation fails, no variance

   val cars: Collection<Car> = carsCollection
   // compilation succeeds

   val audis: Collection<Audi> = carsCollection
   // compilation fails, no variance
}

The invariant generics are most simple and usually most used. You may say that the example is quite non-sense. Why I would like to assign collection to type where the generic parameter is a super-type? And you are right, I don’t. That’s the reason why the Collection is using generic argument type as invariant.

Covariant

So, you have the Collection and you would like to write functions which will be able to work with it. For example a simple count function.

fun count(collection: Collection<Entity>): Int {
    return collection.getAll().size
}

This was simple, wasn’t it? Oh, it was but it doesn’t universally work. As aforementioned, you cannot pass Collection<Car> as an argument to the count function.

To solve this, you have to make the generic parameter other than invariant. Changing generic parameter variance for specific use-case is called use-site variance. It is changed/defined only for one specific usage. In Kotlin you use out and in keywords. That’s quite clever choice! You see that our generic’s parameter type is used as return type of getAll() function, so we will use out. Such variance is called covariant.

fun count(collection: Collection<out Entity>): Int {
    return collection.getAll().size
}

Suddenly, you can pass yours collection of cars correctly.

fun test(collection: Collection<Car>) {
    count(collection) 
    // compilation succeeds
}

Be aware that using the out keyword won’t allow anything. It will just enable common sub/super-type relationship. In covariant case it will allow to pass a sub-type in place requiring its super-type. I.e. you won’t be able to pass Collection<Cars> to function requiring Collection<out Audi> or Collection<out Bike>.

Contravariant

Let’s assume that the Collection is mutable.

interface Collection<E : Entity> {
    fun getAll(): List<E>
    fun add(e: E)
}

You would like to write function that will add Audi entity instance three times:

fun addAudis(collection: Collection<Audi>) {
    collection.add(Audi())
    collection.add(Audi())
    collection.add(Audi())
}

fun test(vehicles: Collection<Vehicle>) {
    addAudis(vehicles)
    // compilation fails
}

Implementation is quite simple, but again this won’t work if you would like to use this function on collection of Vehicles, because the default usage is invariant.

To workaround it, you have to make the generic parameter contravariant using in keyword. That can be remembered the same way as the out keyword, you will put things in.

fun addAudis(collection: Collection<in Audi>) {
    collection.add(Audi())
    collection.add(Audi())
    collection.add(Audi())
}

fun test(vehicles: Collection<Vehicle>) {
    addAudis(vehicles)
    // compilation succeeds
}

Be aware that using the in keyword won’t allow anything. It will just enable reversed sub/super-type relationship. In contravariant case it will allow to pass a super-type in place requiring its sub-type. I.e. you won’t be able to pass Collection<Skoda> to function requiring Collection<in Audi>.

Declaration-site Variance

All examples used use-site variance, also called type projection. In other words, use-site variance projects the type — i.e. takes a look on it from other side. Covariance/contravariance changes the rules. It brings something in and it takes something away. You can’t call method with covariant generic parameter as argument, you can’t call method returning a contravariant generic parameter. These are quite restrictions, but they allow something in return, as you may have seen.

Some languages (like Kotlin) allow to use declaration-site variance. Such variance is defined once with the class declaration. Declaration-site variance enforces the rules forever and you won’t be able to change them using use-site variance.

Declaration-site Covariance

Declaration-site covariance is commonly used in immutable or “producer” classes.

For example collections are often typed by two interfaces: covariant immutable and invariant mutable. Using immutable type allows user to do more with passed data. When you need modify the data, invariant interface is commonly used.

interface List<out E> {
    fun get(i: Int): E
}
interface MutableList<E> : List<E> { // E is changed here to invariant
    fun add(i: Int, e: E)
}

fun test1(list: List<Car>) {
    val vehicles: List<Vehicle> = list // compilation succeeds
    val cars: List<Car> = list  // compilation succeeds
    val audis: List<Audi> = list  // compilation fails
}

fun test2(list: MutableList<Car>) {
    val vehicles: MutableList<Vehicle> = list // compilation fails
    val cars: MutableList<Car> = list // compilation succeeds
    val audis: MutableList<Audi> = list // compilation fails
}

Declaration-site Contravariance

Declaration-site contravariance is connected to “consumer” classes.

For example classes connected to comparison are often declared as contravariant: Comparable<in T>.

interface Comparable<in T> {
    fun compareTo(other: T): Int
}

class Audi : Comparable<Audi> {
    fun compareTo(other: Audi): Int = TODO()
}

fun test(comparable: Comparable<Car>) {
    val vehicleComparable: Comparable<Vehicle> = comparable
    // compilation fails, Car cannot compareTo with any Vehicle type

    val audiComparable: Comparable<Audi> = comparable
    // compilation succeeds, Car can compareTo with any Audi type
}

Star Projection

There is another type of type-projection — star projection. Star projection is only a syntax-sugared way to write covariant use-site type projection.

fun count(collection: Collection<*>): Int {
    return collection.getAll().size
}

You have already seen the count function. This is the same as the previous version, just the Collection’s generic covariant type argument is replaced with *. What is the advantage? You don’t have to write the bound (Entity). It may change over time, but most importantly, you probably don’t care what comes in.

Breaking the Contract

Sometimes, you really need to loose the bounds to make some operations. Imagine creating a duplicate function which will copy/paste the collection’s entity once more at the end of the collection.

fun doubleCollection(collection: Collection<Entity>) {
    val all = collection.getAll()
    all.forEach { entity ->
        collection.add(entity)
    }
}

This function is type-safe, but as a

• invariant — doesn’t allow passing Collection<Car> — 😢 not a solution;
• covariant — doesn’t allow inserting into collection (add) — 😢 not a solution;
• contravariant — doesn’t allow reading from collection (getAll) — 😢 not a solution;

So we look for language construct which will allow us to workaround this limitation. Why not make your function generic one? That will work!

fun <T: Entity> doubleCollection(collection: Collection<T>) {
    val all = collection.getAll()
    all.forEach { entity ->
        collection.add(entity)
    }
}

So that’s use-site variance workaround. What about declaration-site variance? Kotlin has one workaround — it is a @UnsafeVariance annotation.

So when to use that annotation? Let’s return to our immutable collection. You have already seen that such collection is usually covariant. Still, you may want to check if any E is present in collection — but such E appears in “in” position. An issue. But put there @UnsafeVariance annotation and suddenly it works!

interface List<out E> {
    fun get(i: Int): E
    fun contains(e: @UnsafeVariance E): Boolean
}

Conclusion

Using variance in generics brings a lot of headache and isn’t always easy to understand. But it brings great variability in a type-safe way.

Further Reading

There is one great source which I recommend everyone to read. It is Dave Leeds’ guides on Kotlin:

• An Illustrated Guide to Covariance and Contravariance in Kotlin,
• The Ins and Outs of Generic Variance in Kotlin,
• Star-Projections and How They Work,
• Declaration-Site Variance,
• and maybe some more.