Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
142 lines (94 sloc) 8.79 KB

Subtyping and Variance in Rust 🔥

Author: Ehsan M. Kermani 😊

Date: February 6th, 2019

What is subtyping?

  • Intuition: substitutability, compatibility
  • Type theory 😎: Type S is a subtype of type T (denoted S <: T) if any term/instance of type S can be "safely" used in a context where type T is expected
  • Form of type polymorphism

Does Rust have subtyping? 😏

Yes! But not in a familiar (OOP inheritence) way (Rust doesn't have inheritence). It has subtyping wrt lifetime parameters. 😭

  • What kind of rules/relations involved between types?

  • Can we derive them from experiments?

Observations 😐

What's the type relationship between &[T] and &mut [T]?

What's the type relationship between Vec<T> and the slice [T]?

More details about the inner working later in this presetation.

Variance 😯

A set of rules/relations indicating how subtyping should behave in composition. These rules are related to generic parameter of a type constructor. 😒

pub struct Cell<T: ?Sized> {
    value: UnsafeCell<T>,
}

#[lang = "unsafe_cell"] // --> known to the compiler
pub struct UnsafeCell<T: ?Sized> {
    value: T,
}

What just happened? what is the difference? 😕

First some background

  • Unsafe is dark!

  • Lifetime is a region of code. Lifetime parameter 'a behaves like a type.

  • For a type T, we know that &'static T outlives (a generic) &'a T, therefore, &'static T <: &'a T

  • In general, if 'b: 'a (i.e. 'b outlives 'a and pedagogically, we write code from left to right so larger lifetime would encompass smaller ones), then &'b T <: &'a T, i.e. co-variant. More general,

    for 'b: 'a and S <: T then &'b S <: &'a T.

  • What about &mut 'b S <: &mut 'a T?

  • Therefore, &'a mut &'static T is NOT a subtype of &'a mut &'a T. In fact, &mut is in-variant (no variant relation) wrt general subtyping S <: T. But it is ONLY valid when S is exactly equal to T i.e. &'b mut T <: &'a mut T for 'b:'a. 😴

The problem with making &mut T covariant over T is that it gives us the power to modify the original value when we don't remember all of its constraints. [Rustonomicon]

  • Summary:
    • &'a T is covariant wrt 'a and T.
    • &mut 'a T is covariant wrt 'a and invariant wrt T.
  • Checkout the complete variance table here.

Answer to the above question:

UnsafeCall<T> is invariant wrt T (deep root in compiler with #[lang = "unsafe_cell"]), so is Cell. But our own MyCell<T> is covariant wrt T which means mutation won't remember all the constraints so it becomes dangerous 😱 💀

How to derive variance of a type?

Let F be a type constructor and S <: T then F is

  • Co-variant iff F<S> <: F<T> (example: function return type, &T, *const T, Vec<T>).
  • Contra-variant iff F<T> <: F<S> (example: function argument type)
  • In-variant iff there's no subtyping relation (example:&mut T, *mut T, UnsafeCell<T>, Cell<T>).
  • Bi-variant iff it's both covariant and contravariant i.e. generic parameter is not used (example: builtin type contructors i32, bool, str, extern type (different from extern fn), but not fn though).

Variance algebra 👻

  • Let 0, +, -, ∞ correspond to in-variance, co-variance, contra-variance and bi-variance, respectively. Then

  • Transform (denoted by x below): for type composition (example: fn(Vec<T>))

x 0 + -
0 0 0 0 0
+ 0 + -
- 0 - +
  • Greatest lower bound (denote by ^ bellow): for type aggregates (example: struct, tuple, enum, union and fn actually)
^ 0 + -
0 0 0 0 0
+ 0 + 0 +
- 0 0 - -
0 + -

More details, see Taming the Wildcards: Combining Definition and Use-Site Variance (implemented in rustc::ty::Variance)

Exercise 😉

Use the Variance algebra and derive the following

  1. Given UnsafeCell<T> is invariant wrt T, prove that Cell<T> is invariant wrt T.
  2. Show that *mut Vec<T> is invariant wrt T and the same holds for *mut Vec<i32>.
  3. Show that fn(Box<&'a T>) is contravariant wrt 'a and T.
  4. Prove that Vec<T> is covariant wrt T (hint).
  5. Show that fn(&'a [T]) -> Result<U> is contravariant wrt 'a and T and covariant wrt U. (the same for extern fn hint)
  6. Show that PhantomData<fn(T) -> T> is invariant wrt T. (one can fix our MyCell example by adding this or any invariant type!)

Inner working of Variance 😌

Earlier we observed that &Vec<i32> <: &[i32] and &mut Vec<i32> <: &mut [i32]. What is actually happening is a combination of coercion and auto-(re)borrowing.

  1. Deref coercion: Vec: Deref<Target = [T]>

  2. Auto reborrow:

passing a mutable value reference into an expression context that is itself inferred to be expecting a reference, the compiler will automatically inset &mut *value. (Felix Klock talk, see the resource below and Stackoverflow thread)

Resources 😄

You can’t perform that action at this time.