Variance in Rust

(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.)