Formalizing variance

How can all these intuitions be formalized? It's done through the idea of variance.

Some kinds of memory live longer than others. This is captured through the idea of the outlives relationship. If 'b outlives 'a, it is written as 'b: 'a. For example, in the definition:

#![allow(dead_code)]
fn main() { }

struct OutlivesExample<'a, 'b: 'a> {
    a_str: &'a str,
    b_str: &'b str,
}

the borrowed string b_str lives at least as long as a_str, and possibly longer.

 

The Rust compiler annotates every lifetime parameter with one of three settings. For a type T<'a>, 'a may be:

  • covariant, which means that if 'b: 'a then T<'b>: T<'a>. This is the default for immutable data.

  • invariant, which means that even if 'b: 'a, nothing can be said about the relationship between T<'b> and T<'a>. This can happen for one of two reasons:

    • If the lifetime is present "inside" some sort of mutable context -- whether a &mut reference, or interior mutability like Cell/RefCell/Mutex.

    • If the lifetime is used in multiple spots where the variances conflict. See Conflicts and type parameters for an example.

  • contravariant, which means that if 'b: 'a then T<'a>: T<'b>. This is uncommon and only shows up in parameters to fn pointers.

The variance of a parameter is determined entirely through the type definition. There's no marker trait for this.

Quick exercise

In the struct below, what are the variances of each lifetime parameter?

#![allow(dead_code)]
fn main() {}

use std::cell::Cell;

struct Multi<'a, 'b, 'c, 'd1, 'd2> {
    a: &'a str,
    b: Cell<&'b str>,
    c: fn(&'c str) -> usize,
    d: &'d1 mut &'d2 str,
}

fn a<'a, 'b, 'c, 'd1, 'd2>(
    x: Multi<'static, 'b, 'c, 'd1, 'd2>
) -> Multi<'a, 'b, 'c, 'd1, 'd2> {
    x
}

fn c<'a, 'b, 'c, 'd1, 'd2>(
    x: Multi<'a, 'b, 'c, 'd1, 'd2>
) -> Multi<'a, 'b, 'static, 'd1, 'd2> {
    x
}

fn d1<'a, 'b, 'c, 'd1, 'd2>(
    x: Multi<'a, 'b, 'c, 'static, 'd2>
) -> Multi<'a, 'b, 'c, 'd1, 'd2> {
    x
}

The answers

  • 'a is covariant, because it only shows up in an immutable context. This means that, similar to the shortener functions above, you can define a function like:
#![allow(dead_code)]
fn main() {}

use std::cell::Cell;

struct Multi<'a, 'b, 'c, 'd1, 'd2> {
    a: &'a str,
    b: Cell<&'b str>,
    c: fn(&'c str) -> usize,
    d: &'d1 mut &'d2 str,
}

fn a<'a, 'b, 'c, 'd1, 'd2>(
    x: Multi<'static, 'b, 'c, 'd1, 'd2>
) -> Multi<'a, 'b, 'c, 'd1, 'd2> {
    x
}

fn c<'a, 'b, 'c, 'd1, 'd2>(
    x: Multi<'a, 'b, 'c, 'd1, 'd2>
) -> Multi<'a, 'b, 'static, 'd1, 'd2> {
    x
}

fn d1<'a, 'b, 'c, 'd1, 'd2>(
    x: Multi<'a, 'b, 'c, 'static, 'd2>
) -> Multi<'a, 'b, 'c, 'd1, 'd2> {
    x
}
  • 'b is invariant, because it is "inside" the mutable Cell context.

Exercise: try writing a function that fails to compile because 'b is invariant.

  • 'c is contravariant, because it shows up in the parameter to a callback.
#![allow(dead_code)]
fn main() {}

use std::cell::Cell;

struct Multi<'a, 'b, 'c, 'd1, 'd2> {
    a: &'a str,
    b: Cell<&'b str>,
    c: fn(&'c str) -> usize,
    d: &'d1 mut &'d2 str,
}

fn a<'a, 'b, 'c, 'd1, 'd2>(
    x: Multi<'static, 'b, 'c, 'd1, 'd2>
) -> Multi<'a, 'b, 'c, 'd1, 'd2> {
    x
}

fn c<'a, 'b, 'c, 'd1, 'd2>(
    x: Multi<'a, 'b, 'c, 'd1, 'd2>
) -> Multi<'a, 'b, 'static, 'd1, 'd2> {
    x
}

fn d1<'a, 'b, 'c, 'd1, 'd2>(
    x: Multi<'a, 'b, 'c, 'static, 'd2>
) -> Multi<'a, 'b, 'c, 'd1, 'd2> {
    x
}
  • 'd1 is covariant! Even though it is a mutable reference, it is not "inside" the &mut pointer.
#![allow(dead_code)]
fn main() {}

use std::cell::Cell;

struct Multi<'a, 'b, 'c, 'd1, 'd2> {
    a: &'a str,
    b: Cell<&'b str>,
    c: fn(&'c str) -> usize,
    d: &'d1 mut &'d2 str,
}

fn a<'a, 'b, 'c, 'd1, 'd2>(
    x: Multi<'static, 'b, 'c, 'd1, 'd2>
) -> Multi<'a, 'b, 'c, 'd1, 'd2> {
    x
}

fn c<'a, 'b, 'c, 'd1, 'd2>(
    x: Multi<'a, 'b, 'c, 'd1, 'd2>
) -> Multi<'a, 'b, 'static, 'd1, 'd2> {
    x
}

fn d1<'a, 'b, 'c, 'd1, 'd2>(
    x: Multi<'a, 'b, 'c, 'static, 'd2>
) -> Multi<'a, 'b, 'c, 'd1, 'd2> {
    x
}
  • 'd2 is invariant, because it is "inside" a &mut reference.