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

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 `T`is `&'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

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, for`fn(&'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.

4 thoughts on “Variance in Rust: An intuitive explanation”

1. William D Tanksley Jr says:

I’ve seen papers on the Eiffel and Sather languages refer to “novariance”, which manages to not be confusable with an ordinary English word.

2. Tom says:

Thanks for trying to clear this up! I’d recommend explaining the compiler results for each example, so the reader doesn’t have to navigate away, and because a new person might not understand why a result is surprising. Also it’d help to clarify your intended audience up front, because I didn’t understand the content as an intermediate Rust programmer.

1. Ehsan says:

Thank you for your suggestion Tom! I added them to the post.

This site uses Akismet to reduce spam. Learn how your comment data is processed.