I have now heard twice (the last time was in that podcast) that Rust does not need variance annotations for generics because it has lifetime annotations.

This sentence can be quite puzzling for someone coming from a language like Scala, or for a Rust programmer wondering what the hell variance annotations are.

The thing that immediately came to my mind was "interesting, variance annotations in Scala are there to protect you from performing incorrect assignments when mutating values. On the other hand, Rust has a lifetime system to prevent you from making mistakes with mutations. Certainly, the variance annotations in Scala manifest as lifetimes in Rust then".

The actual situation is that the two situations present some similarities but are, in fact, different.

Why do we need variance annotations in Scala?

Variance in Scala is introduced here. I will summarize the crux of it with the following code

trait Animal
class Cat extends Animal
class Dog extends Animal

val cat: Cat = Cat()
val animal: Animal = cat

class Box[T](t: T)

val boxedCat: Box[Cat] = Box(cat)
val boxedAnimal: Box[Animal] = boxedCat

In the code above we are very tempted to say that a Box[Cat] is a Box[Animal] because a Cat is an Animal. But Scala, by default, will not allow it. If we want to let a Box[Cat] be a Box[Animal] we have to declare Box[T] with a + annotation

class Box[+T](t: T)

+ means that Box is now "covariant" in T:

• if S <: T, "S is a subtype of T"

• then Box[S] < Box[T], "Box[S] is a subtype of Box[T]" or "everywhere a Box[T] is accepted, a Box[S] can be provided"

But now, there is something else that we cannot do. We cannot mutate the content of Box. We cannot declare the following

class Box[+T](var t: T)

This would break type soundness as shown in this example:

val boxedCat: Box[Cat] = Box(cat)
val boxedAnimal: Box[Animal] = boxedCat

// why not, since a Dog is an Animal?
boxedAnimal.t = Dog()

// Oh no the cat became a dog!
val cat: Cat = boxedCat.t

So the point of variance annotations is to be able to declare the developer's intention concerning subtyping and rule out some possibilities that would not be typesafe.

Maybe as a Rust developer, you might have noticed that :

• the "bad" example involves mutation

• it also involves maintaining a reference to a structure mutated "by someone else"

Isn't there a whole type system in Rust devoted to making mutations safe? Is it what this is about here? Yes and no :-).

What does variance mean in Rust?

It is not entirely obvious to talk about variance in Rust when trying to come up with a similar example. For a simple reason: Rust does not have "a subtyping relationship for types". There is no way to declare a type Animal, a type Cat and declare that Cat is a subtype of Animal, allowing a Cat to be used anywhere an Animal is expected.

You can declare an Animal trait, a Cat struct, and have Cat implements Animal. But this is not a subtyping relationship.

In that sense it is meaningless to think that there could be variance annotations for collections in Rust because there is simply no subtyping relationship for types!

Why do I insist on "for types"? Because there is a subtyping relationship for lifetimes in Rust. If you consider a lifetime as "the section of the code for which a given value exists" it is easy to picture that some sections can be included in others.

The subtyping relationship, 'a <: 'b means "everywhere you accept values with a lifetime 'b then you should accept values with lifetime 'a. For this to work it is not hard to see that the lifetime 'a must be a code section containing the code section for the lifetime 'b. If you think about types as being "sets of values" this is a similar but inverted situation:

• A type A is a subtype of a type B if its set of values is contained in the set of values for be => the subtype is the smaller set

• A lifetime 'a is a subtype of a lifetime 'b if the active code section of 'b is contained in the one for 'a => the subtype is the greater set

We can now use this notion of subtyping to reason about some of the possible substitutions in Rust. For example, if a parameter is of the form &'a T then you can always pass a &'static T. That's because:

• the Rust compiler knows that the declaration &'a T is covariant in the lifetime 'a. Any &'b T can be accepted as long as 'b <: 'a

• 'static <: 'a "the 'static lifetime is the largest one"

It is easy to see what would happen if the compiler did not check those rules:

• you could pass a value with a more restricted lifetime than 'a

• then free the value while it is still needed in the scope delimited by 'a

There is a table in the Rustonomicon describing all those rules

That table is quite confusing though. It shows situations where T can be considered "covariant" or "contravariant", or "invariant". Didn't we say that variance is related to subtyping and that there's no subtyping relationship for types in Rust?

If you are confused, and I am too, this is normal, you are not the first one :-). What is not particularly well explained is the fact that types can also be generic in terms of lifetimes!

struct MyBox<'a, T> { t: &'a T }
struct MyHyperBox<'b, T> { t: &'b MyBox<'b, T> }

let my_box = MyBox { t: &1 }; 

{
    let my_hyperbox: MyHyperBox<u32> = MyHyperBox { t: &my_box };
}

In this example, my_hyperbox has a short lifetime but can still contain a value with a type annotated by a larger lifetime and the substitution works.

In conclusion

What we are seeing in Scala and Rust is not the exact same situation just translated from one language to another. We are observing:

• the possibility of subtyping relationships which make substituting expressions easier in our programs

• the type-checking rules that have to be enforced by the compiler to make sure that types in our programs stay consistent