(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:
- Invariant, e.g.
Cell<T>
andCell<U>
are totally different types. - Covariant, e.g.
Vec<T>
is a subtype ofVec<U>
iffT
is a subtype ofU
. - Contravariant, e.g.
fn(T)
is a subtype offn(U)
iffT
is a supertype ofU
. - Bivariant, meaning the parameter is unused, and thus
X<T>
andX<U>
are always compatible even ifT
andU
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 ofVec<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 ofVec<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.)