Variance in Rust

Go to the profile of kennytm
kennytm

(Just some notes when checking how variance should work with DST.)

Subtype

Subtype relationship between two types means the following is a valid program:

let s: Sub = ...;
let u: Base = s;      // ok!

Subtyping relationship is written as Sub: Base in Rust, or S <: B mathematically.

Unlike traditional OOP languages like Java and C#, Rust has no concept of inheritance. Subtyping in Rust concerns about lifetime. A 'longer lifetime is a subtype of a 'shorter lifetime (written in code as 'longer: 'shorter), and 'static is the “base” or “bottom” of all lifetimes.

let s: &'static str = ...;
let u: &'short str = s;     // ok!

Intuitively, a supertype encompass a general concept, and a subtype is some specialization of it. There is only one 'static lifetime region, while there are many many 'short lifetime regions, so 'static is a subtype.

Variance

Variance is a property of a generic parameter of a type constructor (e.g. Vec), which affects subtype relationship among constructed types. Rust 1.24 recognizes four kinds of variances:

  1. Invariant, e.g. Cell<T> and Cell<U> are totally different types.
  2. Covariant, e.g. Vec<T> is a subtype of Vec<U> iff T is a subtype of U.
  3. Contravariant, e.g. fn(T) is a subtype of fn(U) iff T is a supertype of U.
  4. Bivariant, meaning the parameter is unused, and thus X<T> and X<U> are always compatible even if T and U are totally different.

Variance Arithmetic

Let the set of variances be {0, +, −, ∞}, meaning in-, co-, contra- and bivariant respectively. We define the following operations:

Transform (V × W).

  • Combines variances where the type constructors are composed.
  • Example: Vec<fn(T)>has variance of Vec<T> × fn(T).
  • Unit element is + (covariant).
  • Implemented in rustc::ty::Variance::xform in rustc source.
╔═══╦═══╤═══╤═══╤═══╗
║ × ║ 0 │ + │ − │ ∞ ║
╠═══╬═══╪═══╪═══╪═══╣
║ 0 ║ 0 │ 0 │ 0 │ 0 ║
╟───╫───┼───┼───┼───╢
║ + ║ 0 │ + │ − │ ∞ ║
╟───╫───┼───┼───┼───╢
║ − ║ 0 │ − │ + │ ∞ ║
╟───╫───┼───┼───┼───╢
║ ∞ ║ ∞ │ ∞ │ ∞ │ ∞ ║
╚═══╩═══╧═══╧═══╧═══╝

GLB (V ∧ W), short for greatest-lower-bound, also known as meet or infimum.

  • Combines variances where two types form a tuple.
  • Example: (Vec<T>, fn(T)) has variance of Vec<T> ∧ fn(T).
  • Unit element is ∞ (bivariant).
  • Implemented in rustc_typeck::variance::xform::glb in rustc source.
╔═══╦═══╤═══╤═══╤═══╗
║ ∧ ║ 0 │ + │ − │ ∞ ║
╠═══╬═══╪═══╪═══╪═══╣
║ 0 ║ 0 │ 0 │ 0 │ 0 ║
╟───╫───┼───┼───┼───╢
║ + ║ 0 │ + │ 0 │ + ║
╟───╫───┼───┼───┼───╢
║ − ║ 0 │ 0 │ − │ − ║
╟───╫───┼───┼───┼───╢
║ ∞ ║ 0 │ + │ − │ ∞ ║
╚═══╩═══╧═══╧═══╧═══╝

Variance of Built-in Type Constructors

  • Primitives (u32, str, bool, extern type):
    ∞ (bivariant)
  • Generic parameter (T):
    + (covariant)
  • References (&'a<'b> _, &'a<'b> mut _)
    'b = + (covariant) × 'a.
  • Shared pointer (&X<T>, *const X<T>):
    T = + (covariant) × X.
  • Unique pointer (&mut X<T>, *mut X<T>):
    T = 0 (invariant) × X.
  • Arrays and slices ([X<T>]):
    T = + (covariant) × X.
  • Aggregates (tuples, struct, enum, union): 
    GLB of all fields
  • Traits (Trait<Input<T>, Output=Output<U>> + 'a<'b>):
    T = 0 (invariant) × Input.
    U = + (covariant) × Output.
    'b = + (covariant) × 'a.
  • Function pointers (fn(Input<T>) -> Output<U>):
    T = − (contravariant) × Input.
    U = + (covariant) × Output.

(Note when reading source code: the variance of lifetimes are annotated in an inverted manner, see RFC issue #391 for detail.)