On Subtyping and Variance in Rust

1 Introduction

Subtyping is a relationship between types, where a type S conforms to the type T’s interface and therefore can be used in any context that expects T.

We write S <: T and say “S is a subtype of T” (equivalently, T is a supertype of S). This idea is known as the principle of safe substitution^{pierce-2002, pp.182}, and is closely related to the Liskov Substitution Principle (the “L” in SOLID).

2 Subtyping in Rust

So, in Rust, subtyping is defined over lifetimes and the core rule is:

If 'long lives at least as long as 'short ('long >= 'short), then 'long <: 'short.

This may feel backwards at first, but the intuition is straightforward: a reference that lives longer is strictly more useful than one that lives shorter, and thus you can always use it in a context that requires the shorter lifetime, but not vice versa.

As a special case, 'static outlives every lifetime, so 'static <: 'a for all 'a.

 1fn print_all(v: Vec<&str>) {
 2    for s in v {
 3        println!("{s}");
 4    }
 5}
 6
 7fn example() {
 8    let v: Vec<&'static str> = vec!["hello", "world"];
 9    // `'static <: 'a`, so Vec<&'static str> is accepted where Vec<&'a str> is expected.
10    // The subtyping propagates through Vec, no conversion needed.
11    print_all(v);
12}

Lifetime subtyping propagates through type constructors like Vec<T>, &mut T, or fn(T)? It brings us to another important notion, that of variance, which describes how a type constructor preserves, reverses, or ignores the subtyping relationship of its parameters.

3 Variance

Variance describes how the subtyping relationship of a type parameter is affected when that parameter is used inside a type constructor F.

There are three kinds.

3.1 Covariance

A type constructor F is covariant over its parameter T if:

$$S <: T \implies F\langle S \rangle <: F\langle T \rangle$$

In other words, covariance preserves the subtyping direction.

The most common example is the shared reference &'a T: it is covariant over both 'a and T.

 1fn take_option(o: Option<&str>) {
 2    if let Some(s) = o {
 3        println!("{s}");
 4    }
 5}
 6
 7fn example() {
 8    let o: Option<&'static str> = Some("hello");
 9    // Option is covariant over T, and &'static str <: &'a str,
10    // so Option<&'static str> <: Option<&'a str>.
11    take_option(o);
12}

Common covariant types: &'a T, *const T, Vec<T>, Box<T>, Rc<T>, Arc<T>.

3.2 Contravariance

A type constructor F is contravariant over its parameter T if:

$$S <: T \implies F\langle T \rangle <: F\langle S \rangle$$

Contravariance reverses the subtyping direction.

In Rust, fn(T) is contravariant over T.

The intuition is simple: subtype is expected to be more useful, and a function that can handle any &str (a broader input) is more useful than one that can only handle &'static str (a narrower input).

So fn(&str) <: fn(&'static str).

 1fn apply(f: fn(&'static str), s: &'static str) {
 2    f(s);
 3}
 4
 5fn print_any(s: &str) {
 6    println!("{s}");
 7}
 8
 9// fn(&str) <: fn(&'static str) because fn(T) is contravariant over T.
10// `print_any` accepts any &str, so it can certainly handle &'static str.
11apply(print_any, "hello");
12
13// Another example:
14let handlers: Vec<fn(&'static str)> = vec![
15    print_any, // fn(&str) accepted where fn(&'static str) expected
16];

3.3 Invariance

A type constructor F is invariant over its parameter T if no subtyping relationship is produced regardless of the relationship between its arguments, i.e. $S <: T$ does not imply any relationship between $F\langle S \rangle \text{ and } F\langle T \rangle$:

The most important invariant type is &'a mut T, which is invariant over T (but covariant over 'a).

Why must &mut T be invariant over T?

Because if it were covariant, you could write a short-lived value into a slot that expects a long-lived one:

 1fn overwrite<'a>(dest: &mut &'a str, src: &'a str) {
 2    *dest = src;
 3}
 4
 5fn main() {
 6    let mut long_lived: &'static str = "hello";
 7
 8    {
 9        let short_lived = String::from("temporary");
10        // If &mut T were covariant over T, then &mut &'static str <: &mut &'a str,
11        // and this call would be accepted:
12        overwrite(&mut long_lived, &short_lived);
13    }
14    // short_lived is dropped, but long_lived now points to freed memory!
15    println!("{long_lived}"); // use-after-free
16}

The compiler rejects this: &mut T is invariant over T, so &mut &'static str cannot be used where &mut &'a str is expected. The lifetimes must match exactly.

The same reasoning applies to Cell<T>, since it allows interior mutation, it must be invariant over T:

 1use std::cell::Cell;
 2
 3fn replace<'a>(cell: &Cell<&'a str>, new_val: &'a str) {
 4    cell.set(new_val);
 5}
 6
 7fn main() {
 8    let cell = Cell::new("hello"); // Cell<&'static str>
 9
10    {
11        let short_lived = String::from("temporary");
12        // If Cell<T> were covariant, Cell<&'static str> <: Cell<&'a str>,
13        // and this call would be accepted:
14        replace(&cell, &short_lived);
15    }
16    // short_lived is dropped, but cell still holds a reference to it!
17    println!("{}", cell.get()); // use-after-free
18}

Again, the compiler rejects this because Cell<T> is invariant over T.

Common invariant types: &'a mut T (over T), Cell<T>, RefCell<T>, UnsafeCell<T>, *mut T.

4 Variance in Custom Types

The variance of a struct is determined by the variance of its fields. The compiler computes it automatically: for each type parameter, it combines the variance from all fields where that parameter appears, and the most restrictive field wins.

For example, a struct with both &'a T (covariant over T) and &'a mut T (invariant over T) will be invariant over T, because invariance is more restrictive than covariance.

To mark a struct with particular kind of variance, rely on PhantomData:

 1use std::marker::PhantomData;
 2
 3// Covariant over 'a and T
 4struct Covariant<'a, T> {
 5    _marker: PhantomData<&'a T>,
 6}
 7
 8// Contravariant over T
 9struct Contravariant<T> {
10    _marker: PhantomData<fn(T)>,
11}
12
13// Invariant over T
14struct Invariant<T> {
15    _marker: PhantomData<*mut T>,
16}

5 Summary

• Subtyping in Rust is lifetime-based: 'long <: 'short. A longer lifetime can substitute for a shorter one. Trait bounds are not subtyping.
• Variance describes how subtyping propagates through type constructors.
• Three kinds: covariance (preserves direction, e.g. &'a T), contravariance (reverses direction, e.g. fn(T)), invariance (no relation, e.g. &mut T over T).
• PhantomData<T> lets you control variance in custom types without storing a value of T.

6. References

• Types and Programming Languages, Benjamin C. Pierce, 2002
• Subtyping vs Inheritance, counterexamples.org
• Subtyping — The Rust Reference
• Subtyping and Variance — The Rustonomicon
• PhantomData — The Rustonomicon

Ready to Level Up Your Team?

I'm open to exciting opportunities and collaborations.
Curious about my experience and what I can bring to your project?

Learn more about me ➤