what is variance

go back

I brought the markdown viewer to you!

Alternative resources:

# Subtyping

Subtyping is when one type (like Cat) can be used anywhere another, more general type (like Animal) is expected.

```
class Animal {}
class Cat inherits Animal {}

fn walk(animal: Animal);

// a Cat can walk!
walk(new Cat())
```

In type theory "is a subtype of" is represented with the sigil <: so Cat <: Animal. This is called a subtyping relationship. Cat can fit in places where Animal is expected because Cat is a subtype of Animal.

Type variance tells us what to do when a type is placed in a bigger type.

Can a List<Cat> be used as a List<Animal>? Maybe. A list of Cats is basically just a list of Animals. Can a fn(Cat) be used as a fn(Animal)? Maybe not. fn(Cat) expects a Cat, lets not surprise it with any Animal.

We say List<T> is "covariant" over T because List<A> <: List<B> if A <: B. With covariance, the subtyping relationship "passes through". List<Cat> can generalize to a List<Animal>.

We say fn(T) is "contravariant" over T because fn(B) <: fn(A) if A <: B. With contravariance, the subtyping relationship is inverted. fn(Animal) can specialize to a fn(Cat).

"Why is this important to Rust?"

Well, imaginary reader, read on.

# Variance

We turn a &'static str into a &'local str, using some fake syntax I made up for illustrative purposes.

```
'local: {
    let foo: &'static str = "";
    let bar: &'local str = foo;

    // bar needs to live for at least this scope
}
```

When assigning bar

```
let bar: &'local str = foo;
```

A naive borrow checker would see that 'static != 'local and refuse to compile.

But this is valid code! We'd like the borrow checker to realize that a &'static str can fit in places where a &'local str is required.

# Covariance

When a lifetime can shrink to fit. 'long <: 'short

```
let foo: &'static str = "";
let bar: &'local str = foo;
```

Because 'static outlives 'local, 'static should fit in places where 'local is expected. 'static <: 'local

A &'static T can become a &'local T because &'static T <: &'local T.

We assume 'static <: 'local implies &'static T <: &'local T, which happens to be true for &T but isn't always the case.

# Invariance

When a lifetime cannot change.

```
let foo: &mut &'static str = &mut "";
let bar: &mut &'local str = foo;

// Oh no! Setting a 'static str to a 'local str!
*bar = &String::new();
```

foo is supposed to live for 'static, but we set it to a string that only lives for 'local! We want the compiler to reject this.

When using &mut T, the type of T can't change. We say &mut T is "invariant" over T.

When assigning bar

```
let bar: &mut &'local str = foo;
```

&mut &'static str is invariant over &'static str. The type of &'static str is not allowed to become a &'local str, and the compiler successfully rejects the code.

Borrows are generic

&'a T has two generic parameters, imagine it as Borrow<'a, T>:
&'a T is covariant over 'a and covariant over T. In other words, 'a can change and T can change.

&'a mut T has two generic parameters, imagine it as BorrowMut<'a, T>:
&'a mut T is covariant over 'a but invariant over T. In other words, 'a can change but T can't.

Is the following code valid Rust?

```
let foo: &mut &'static str = &mut ...;
let bar: &mut &'local str = &mut ...;

*bar = *foo;
```

Answer

For this to be valid, either *foo has to shrink to *bar (covariant), or *bar has to grow to *foo (contravariant).

When foo is dereferenced it becomes a &'static str which shrinks to a &'local str. Once the types match, we can assign *bar to *foo.

# Contravariance

When a lifetime can grow to fit. Fn('short) <: Fn('long)

The opposite of covariance. Only ever used in function parameters.

```
let bar: fn(x: &'local str) = |_| {};
let foo: fn(x: &'static str) = bar;
```

If bar can handle a &'local str then it can handle a &'static str.

Fn(T) -> U is contravariant over T and covariant over U

# Multiplication Rules

Variance follows multiplication rules, where covariance = 1, invariance = 0, and contravariance = -1. Lets see some examples.

In &T what is the variance of T? We already know this, &T is covariant over T.

In Fn(Fn(T)) what is the variance of T? Fn(T) is contravariant over T and Fn(Fn(T)) is contravariant again over T. -1 * -1 = 1, two negatives make a positive, so Fn(Fn(T)) is covariant over T.

In &mut Fn(T) what is the variance of T? Well, &mut T is invariant over T, anything multiplied by 0 is 0, so &mut Fn(T) is invariant over T.

# Variance In Structs

To find the variance of a struct. We need to look at its fields.

If all the fields are covariant it is covariant.

```
// MyStruct<'a> is covariant over 'a
struct MyStruct<'a> {
    x: &'a str,  // covariant over 'a
    y: &'a bool, // covariant over 'a
}

let foo: MyStruct<'local> = MyStruct<'static> { ... };
```

If all the fields are contravariant it is contravariant.

```
// MyStruct<'a> is contravariant over 'a
struct MyStruct<'a> {
    x: fn(&'a str),  // contravariant over 'a
    y: fn(&'a bool), // contravariant over 'a
}

let foo: MyStruct<'static> = MyStruct<'local> { ... };
```

If any field is invariant it is invariant.

```
// MyStruct<'a> is invariant over 'a
struct MyStruct<'a> {
    x: *mut &'a str, // invariant over 'a
    y: &'a bool,     // covariant over 'a
    z: fn(&'a u32),  // contravariant over 'a
}

let foo: MyStruct<'local> = MyStruct<'local> { ... };
```

If the fields have conflicting variance it is invariant.

```
// MyStruct<'a> is invariant over 'a
struct MyStruct<'a> {
    x: &'a str,     // covariant over 'a
    y: fn(&'a str), // contravariant over 'a
}

let foo: MyStruct<'local> = MyStruct<'local> { ... };
```

This is because covariance requires MyStruct<'a> <: MyStruct<'b> and contravariance requires MyStruct<'b> <: MyStruct<'a> which can only be satisfied by invariance.

# WTF? fn(&'a ()) -> &'a ()

I've only ever seen this in std::task::Context but I feel the need to explain it anyway.

If we have the type

```
type F<'a> = fn(&'a ()) -> &'a ()
```

The contravariant function argument fn(&'a ()) requires that F<'short> <: F<'long>.

The covariant return type -> &'a () requires that F<'long> <: F<'short>.

Both requirements F<'short> <: F<'long> and F<'long> <: F<'short> combine to make F<'a> invariant over 'a.

In the source code for std::task::Context:

```
struct Context<'a> {
    ...
    _marker: PhantomData<fn(&'a ()) -> &'a ()>,
    ...
}
```

This makes Context<'a> invariant over 'a.

This is almost the same as using *mut &'a () to force invariance, because *mut T is invariant over T.

```
struct Context<'a> {
    ...
    _marker: PhantomData<*mut &'a ()>,
    ...
}
```

But *mut T affects how auto traits are implemented (e.g Send/Sync), which is why it's not used.

If you don't know, an auto-trait is a trait that is automatically implemented for every type only if all of their fields also implement that trait, and *mut &'a () blocks some auto-traits from being implemented. See docs.

# Why is &'a mut T not contravariant over T?

I asked this myself, and found this person asking the same question.

With immutable references, we accept lifetimes bigger than the one we asked for.

```
// I asked for a 'local but a 'static will do
let x: &'local str = "" as &'static str;
```

With mutable references, it seems ok to do this.

```
let short: &mut &'local str = &mut &String::new();
// contravariance allows growing lifetime
let long: &mut &'static str = short;
// why not?
*long = "" as &'static str;
```

But &'a mut T lets us read data too.

```
let short: &mut &'local str = &mut &String::new();
let long: &mut &'static str = short;
// uh oh! turn a 'local into a 'static
let oops: &'static str = *long;
```

&mut T doesn't let you read bigger lifetimes than the value it holds so it cannot be contravariant.

&mut T doesn't let you write smaller lifetimes than the value it holds so it cannot be covariant.

It must be invariant.

Mutability is generally invariant, this includes UnsafeCell and friends.