Variance in Rust: An intuitive explanation

Recently I've made a presentation about subtyping and variance in Rust for our local Vancouver Rust meetup, but I still think intuition was rather lost in the formalism, so here's my shot at explaining it as intuitively as I can. For more succinct definitions, please checkout the presentation or the resources at the end.

First, two important points that we're going to talk about

1. Variance is a concept related to generic parameter(s).
2. Rust has subtyping wrt lifetime parameters.

Things can get confusing because a lifetime parameter is actually a generic parameter, so variance and subtyping are tied together.

Intuition

Variance in Rust is about allowing a lifetime parameter to be ok (i.e. approximated) with a

1. Shorter lifetime: co-variance
2. Longer lifetime: contra-variance
3. Neither shorter nor longer lifetime: in-variance

These are actually the assumptions we need to make so that we can be sure our implementation is sound.

Note: Wherever you see variance in Rust, by default it means covariance.

Now here's a classic example:

Try to guess the output first. (Playground link)

struct MyCell<T> {
    value: T
}

impl<T: Copy> MyCell<T> {
    fn new(value: T) -> Self {
        MyCell { value }
    }
    
    fn get(&self) -> T {
        self.value
    }
    
    fn set(&self, new_value: T) {
        // signature: pub unsafe fn write<T>(dst: *mut T, src: T)
        // Overwrites a memory location with the given value without reading
        // or dropping the old value
        unsafe { std::ptr::write(&self.value as *const T as *mut T, new_value); }
    }
}

fn foo(rcell: &MyCell<&i32>) { 
    let val: i32 = 13;
    rcell.set(&val);
    println!("foo set value: {}", rcell.value);
}

fn main() {
    static X: i32 = 10;
    let cell = MyCell::new(&X);
    foo(&cell);
    println!("end value: {}", cell.value);
}

And the output is

foo set value: 13
end value: 32766 // ???

If you could guess the end value will be non-sense you might skip to the end and if it's unsettling and you were hoping the compiler will guide us here, please keep reading.

Well, before going into more details here's the example using Cell<T>. Can you guess the output now? (Run in playground)

use std::cell::Cell;

fn foo(rcell: &Cell<&i32>) { 
    let val: i32 = 13;
    rcell.set(&val);
}

fn main() {
    static X: i32 = 10;
    let cell = Cell::new(&X);
    foo(&cell);
}

And it doesn't compile because of

error[E0597]: `val` does not live long enough
 --> src/main.rs:7:15
  |
5 | fn foo(rcell: &Cell<&i32>) { 
  |                     - let's call the lifetime of this reference `'1`
6 |     let val: i32 = 13;
7 |     rcell.set(&val);
  |     ----------^^^^-
  |     |         |
  |     |         borrowed value does not live long enough
  |     argument requires that `val` is borrowed for `'1`
8 | }
  | - `val` dropped here while still borrowed

error: aborting due to previous error

Ok! this is what we expect from the compiler, right?

To understand where the root of the problem is in MyCell<T>, let's try to analyze using nomicon's visual representation of lifetime

static X: i32 = 10;
'a: {
    let cell = MyCell::new(&'a X);
    'b: {
        // foo(&'b cell) more or less is:
        let val: i32 = 13; // <-- created here
        'c: {
            rcell.set(&'c val);
            println!("foo set value: {}", rcell.value);
        }
    } // <-- val is dropped here
    println!("end value: {}", cell.value);
}

The problem occurs when we've allowed change/mutation to be ok for shorter lifetime `c than `a (co-variant assumption). However, clearly this is not sound, because val exists in `b and is dropped at the end of `b's scope, that's why printing the cell.value will be nonsense (content of a freed pointer!).

Claim: It doesn't matter how you implement set for MyCell<T> it'll always be unsound.

Pretty powerful claim! The reason is that the essence of MyCell<T> doesn't put any restrictions on not allowing shorter lifetimes to mess up with its value. In other words, we're kind of forgetting about any particular lifetime constraints, meaning that our MyCell<T> is co-variant wrt T where for our case Tis &'a i32 so is co-variant wrt `a.

To be able to make such claims, we need to have type-level knowledge (more succinct treatment through type constructor) and value-level knowledge is not enough. We can be pretty sure that these issues have been taken care of when using types provided for us in standard library.

But how does Cell<T> enforce in-variance?

Here's the stripped down definition of Cell<T>

pub struct Cell<T: ?Sized> {
    value: UnsafeCell<T>,
}

#[lang = "unsafe_cell"] // --> known to the compiler
pub struct UnsafeCell<T: ?Sized> {
    value: T,
}

Wait what? what's the difference? o_0

The answer has deep root in compiler with the attribute #[lang = "unsafe_cell"].

Can we fix MyCell<T> somehow?

If you find yourself in a situation that need to make your type in-variant, you can include any in-variant type, such as Cell<T> or UnsafeCell<T> in PhantomData, for example with PhantomData<Cell<T>> (Exercise: Can you find other in-variant types?). Checkout how it fixes the issue.

I hope you can see how important variance is and how the compiler is handling it for us in most cases. Complete understanding of this matter becomes really important when writing unsafe code in FFI for example.

You might ask how using a longer lifetime could be ok? Well, it's kind of rare in fact. For example, forfn(&'a i32) it's ok to use fn(&'static i32) so it is contra-variant wrt its arguments (and `fn` is co-variant wrt return types in general).

Lastly, for the sake of completeness, there's a fourth case such as most of primitive types that are bi-variant, meaning they're both co-variant and contra-variant.

Resources

If you're interested in knowing more there are some great resources

1. Felix Klock presentation
2. Rustonomicon.
3. Other resources at the end of my presentation here.
4. The Variance RFC is excellent but don't get confused with some historic changes.
5. Rust compiler guide.