Subtyping & Variance

CIS 198 Lecture 16

Higher-Rank Trait Bounds

struct Closure<F> {
    data: (u8, u16),
    func: F,
}
impl<F> Closure<F> where F: Fn(&(u8, u16)) -> &u8 {
    fn call(&self) -> &u8 {
        (self.fun)(&self.data)
    }
}
fn do_it(data: &(u8, u16)) -> &u8 { &data.0 }
fn main() {
    let c = Closure { data: (0, 1), func: do_it, };
    c.call();
}

???

Closures in Rust are pretty magical when it comes to their underlying implementation. This code compiles fine, but has some lifetime weirdness. Let’s desugar it and explictly annotate the lifetimes that the compiler inserts (more or less). Note that the code on the next slide doesn’t compile in Rust because you can’t annotate lifetimes that way, but the idea we’re expressing is correct.

Higher-Rank Trait Bounds

struct Closure<F> {
    data: (u8, u16),
    func: F,
}
impl<F> Closure<F> where F: Fn(&'??? (u8, u16)) -> &'??? u8 {
    fn call<'a>(&'a self) -> &'a u8 {
        (self.fun)(&self.data)
    }
}
fn do_it<'b>(data: &'b (u8, u16)) -> &'b u8 { &'b data.0 }
fn main() {
    'x: {
        let c = Closure { data: (0, 1), func: do_it, };
        c.call();
    }
}

???

Here, we can describe the lifetimes of everything in play except for the references in use in the function we’re storing inside the Closure struct. We have to provide some lifetime bound for these references, but the lifetime can’t be named until the body of call is entered, so we’re stuck. Moreover, call has to work with any lifetime that &self has at this point; we already know that this code compiles and works fine in Rust, so how does it work?

Higher-Rank Trait Bounds

impl<F> Closure<F> where for<'a> F: Fn(&'a (u8, u16)) -> &'a u8 {
    fn call<'a>(&'a self) -> &'a u8 {
        (self.fun)(&self.data)
    }
}

???

The compiler desugars this lifetime bound like so. You can read this as “where for all choices of the lifetime a, F is such and such type”. This effectively produces an infinite list of trait bounds that F must satisfy. Generally, this doesn’t come up very much. However, if you’re doing something more complex with function pointers and closures, you may run into needing this syntax. Anywhere you may have a Trait<'a>, a for<'a> Trait<'a> is also allowed. It may not seem super obvious why you need these at all if you aren’t thinking about lifetimes too hard. However, recall that lifetimes are kind of like type parameters— an &'a and an &'static may not always be compatible! Without HRTBs, it would be hard to abstract over function types, as lifetime bounds would cause conflicts.

Inheritance vs. Subtyping

• Rust does not support structural inheritance.
  • No classes, virtual functions (sort of), method overriding, etc.
• Subtyping in Rust derives exclusively from lifetimes.
• Lifetimes may be partially ordered based on a containment relation.

Lifetime Subtyping

• Lifetime subtyping is in terms of the containment relationship:
  • If lifetime a contains (outlives) lifetime b, then 'a is a subtype of 'b.
  • In Rust syntax, this relationship is written as 'a: 'b.

???

This relationship is somewhat counter-intuitive— if a outlives b, why is a a subtype of b? a is larger than b, but it’s a subtype; why do we express this relationship this way? From a typing perspective, think of it like this: if you want an &'a str and I give you an &'static str, that should be totally fine. Similarly, in an OO world with structural inheritance, if you have a collection of type Animal and I give you a Cat to insert into it, that should be fine as well. Hence, lifetimes express the same subtyping relationship. If you have a higher-rank lifetime (e.g. from a higher-rank trait bound), they’re also subtypes of every concrete lifetime, since they can specify any arbitrary lifetime.

Type Variance

• Variance is a property of type constructors with respect to their arguments.
• Type constructors in Rust can be either variant or invariant over their types.
• Variance: F is variant over T if T being a subtype of U implies F<T> is a subtype of F<U>.
  • Subtyping “passes through”.
• Invariance: F is invariant over T in all other cases.
  • No subtyping relation can be derived.

???

Rust’s variance relation is actually a covariance relation; other languages also have contravariance over certain types, but Rust doesn’t except over functions, which may change in the future. For reference, fn(T) is contravariant in T. However, because traits don’t have inferred variance, Fn(T) is invariant in T.

Type Variance

• &'a T is variant over 'a and T
  • As is *const T.
• &'a mut T is variant over 'a but invariant over T.
• Fn(T) -> U is invariant over T but variant over U.
• Box<T>, Vec<T>, etc. are all variant over T
• Cell<T> and any other types with interior mutability are invariant over T
  • As is *mut T.

Type Variance

• Why do the above properties hold?

???

&'a T is variant over 'a for reasons already discussed. Why over T? An &&'static str is appropriate when an &&'a str would be. &'a mut T‘s lifetime variance also makes sense, but its type invariance might not. Let’s look at a code example…

&'a mut T Type Invariance

fn overwrite<T: Copy>(input: &mut T, new: &mut T) {
    *input = *new;
}
let mut forever: &'static str = "hello";
{
    let s = String::from("world");
    overwrite(&mut forever, &mut &*s);
}
println!("{}", forever);

• In general, if variance would allow you to store a short-lived value into a longer-lived slot, you must have invariance.

???

Everything about this code looks fine, except it actually ends up printing freed memory at the end. If &mut T were variant over T, then &mut &'static str would be a subtype of &mut &'a str, and you could downgrade the 'static lifetime to 'a. This would allow you to overwrite forever with a s, drop s after the inner scope exits in the above program, and then still access its memory via forever. This is tricky, since you have to remember that lifetimes are part of types, and therefore their variance must be considered in the T slot of other references. &'a mut T is allowed to be variant over 'a because 'a is a property of the reference, but T is borrowed by the reference. If the 'a changes, only the reference will know; if you change the T, somebody else will know, so you can’t do this. “The 'a is owned, the T is borrowed.”

Type Variance

• Box and Vec are variant over T, even though this looks like it breaks the rule we just defined.
• Because you can only mutate a Box via an &mut reference, they become invariant when mutated!
  • This prevents you from storing shorter-lived types into longer-lived containers.
• Cell types need invariance over T for the same reason &mut T does.
  • Without invariance, you could smuggle shorter-lived types into longer-lived cells.

Type Variance

• What about the variance of types you define yourself?
• Struct Foo contains a field of type A…
  • Foo is variant over A if all uses of A are variant.
  • Otherwise, it’s invariant over A.

Type Variance

    struct Foo<'a, 'b, A: 'a, B: 'b, C, D, E, F, G, H> {
        a: &'a A,     // variant over 'a and A
        b: &'b mut B, // variant over 'b, invariant over B
        c: *const C,  // variant over C
        d: *mut D,    // invariant over D
        e: Vec<E>,    // variant over E
        f: Cell<F>,   // invariant over F
        g: G,         // variant over G
        h1: H,        // would be variant over H...
        h2: Cell<H>,  // ...but Cell forces invariance
    }

Type Variance

• A good way to think about lifetime variance is in terms of ownership.
• If someone else owns a value, and you own a reference to it, the reference can be variant over its lifetime, but might not be variant over the value’s type.