Crust of Rust: Subtyping and Variance

This chapter explores the advanced, highly technical concepts of subtyping and variance in Rust. While these concepts are largely handled automatically by the compiler, they frequently surface as confusing compiler errors when writing APIs that involve mutable references, nested lifetimes, or unsafe code. By implementing a Rust equivalent of the classic C strtok function, we will diagnose why lifetime unification fails, construct a robust mental model for subtyping, and examine how variance guarantees memory safety.

1. The Motivating Problem: Implementing strtok in Rust

To understand why variance matters in practical programming, we will implement a string tokenization function similar to strtok from C/C++.

The Behavior of strtok

The strtok function takes a mutable reference to a string slice and a delimiter character. It searches for the delimiter, mutates the input reference in-place to point to the suffix after the delimiter, and returns the prefix before the delimiter.

Naive Implementation (Single Lifetime)

Let's write a naive implementation where we unify all lifetimes under a single lifetime parameter 'a:

pub fn strtok<'a>(s: &mut &'a str, delimiter: char) -> &'a str {
    if let Some(i) = s.find(delimiter) {
        let prefix = &s[..i];
        // Skip past the character delimiter
        let suffix = &s[i + delimiter.len_utf8()..];
        *s = suffix;
        prefix
    } else {
        let prefix = *s;
        *s = "";
        prefix
    }
}

The Test Case

We write a test case to verify this behavior:

#[test]
fn it_works() {
    let mut x = "hello world"; // x is a &mut &'static str
    
    {
        let hello = strtok(&mut x, ' ');
        assert_eq!(hello, "hello");
    } // hello is dropped here
    
    assert_eq!(x, "world");
}

The Compilation Failure

When we attempt to compile this test, the Rust compiler rejects the code with a confusing error:

Even though hello is dropped before we assert against x, the compiler insists that x remains mutably borrowed for its entire existence. To understand why this happens, we must explore the mechanics of subtyping and variance.

2. The Mental Model of Subtyping

In many object-oriented languages, subtyping is tied to class inheritance (e.g., a Cat is a subtype of Animal). In Rust, subtyping does not apply to structs or enums, but it applies directly to lifetimes.

The "At Least as Useful" Rule

We can define the subtyping relationship formally:

This means that anywhere a type $U$ is expected, you can safely provide a type $T$ instead.

Lifetimes as Subtypes

In Rust, the 'static lifetime lives for the entire duration of the program. Any generic lifetime 'a lives for some subset of the program.

Because a 'static reference lives forever, it is at least as useful as a reference living for a shorter lifetime 'a. You can always pass a &'static str to a function expecting a &'a str.

3. Understanding Variance

Variance describes how the subtyping of a type's generic parameters affects the subtyping of the type itself. If $T \le U$, how does the container type $F\langle T\rangle$ relate to $F\langle U\rangle$?

There are three categories of variance in Rust:

1. Covariance: Subtyping relation is preserved. If $T \le U$, then $F\langle T\rangle \le F\langle U\rangle$.
2. Contravariance: Subtyping relation is reversed. If $T \le U$, then $F\langle U\rangle \le F\langle T\rangle$.
3. Invariance: No subtyping relation is preserved. $F\langle T\rangle \le F\langle U\rangle$ if and only if $T$ and $U$ are exactly identical ($T = U$).

Tabular Synthesis of Variance in Rust

4. Why Invariance is Crucial for Memory Safety

To understand why &mut T must be invariant over T, let us examine what would happen if it were covariant.

The "Invariance Attack" Scenario

Imagine a helper function that takes a mutable reference to a string slice and overwrites it with a short-lived, stack-allocated string slice:

fn assign_short_lived<'a>(r: &mut &'a str, short: &'a str) {
    *r = short; // Overwrites the reference
}

Now, let's write code that attempts to exploit this if &mut T were covariant:

fn exploit() {
    // 1. We start with a static string reference
    let mut static_str: &'static str = "hello";
    
    {
        // 2. Create a short-lived string on the stack
        let local_string = String::from("short");
        let short_ref: &str = &local_string; // Lifetime is 'local
        
        // 3. If &mut T were COVARIANT over T, we could downgrade
        //    &mut &'static str to &mut &'local str.
        assign_short_lived(&mut static_str, short_ref);
    } 
    // 4. local_string is dropped here!
    
    // 5. static_str now points to deallocated stack memory!
    println!("{}", static_str); // USE-AFTER-FREE / UNDEFINED BEHAVIOR
}

How Invariance Prevents This

Because &mut T is invariant over T, the compiler refuses to downgrade &mut &'static str to &mut &'local str.

• The type parameter T in &mut T is &'static str.
• The function expects &mut &'local str.
• Because of invariance, &'static str must exactly equal &'local str, which is impossible because 'static outlives 'local.
• The compiler rejects the code, preventing a use-after-free vulnerability.

5. Covariance of Lifetimes vs. Invariance of Types in &'a mut T

A common point of confusion is that &'a mut T has two distinct lifetime-related components:

1. The lifetime of the borrow itself ('a).
2. The lifetime parameters inside the type being pointed to (T).

Shortening the Borrow Lifetime

It is always safe to shorten the lifetime of the borrow itself. If you borrow a variable mutably, you can pass that mutable reference to a function that expects a shorter borrow. This is because &'a mut T is covariant over 'a.

The strtok Lifetime Lock-In

Now we can diagnose why our naive strtok implementation failed:

pub fn strtok<'a>(s: &mut &'a str, delimiter: char) -> &'a str

1. We pass &mut x where x is &'static str.
2. The compiler unifies the lifetime of the return value and the inner string slice to 'a. Thus, 'a must be 'static.
3. The signature requires the input parameter to be &mut &'static str.
4. Because &mut T is invariant over T, the compiler cannot shorten the inner lifetime of x from 'static to a local lifetime.
5. Therefore, the outer mutable borrow of x is forced to last for 'static (the entire duration of the program).
6. As a result, x remains mutably borrowed forever, and any subsequent read of x triggers a borrow checker error.

6. Solving the strtok Lifetime Crisis

To fix this issue, we must decouple the lifetime of the outer mutable borrow from the lifetime of the underlying string slice.

Decoupled Lifetime Signature

We introduce a second lifetime parameter, 'b, to represent the lifetime of the string slice, while 'a represents the lifetime of the mutable borrow:

pub fn strtok<'a, 'b>(s: &'a mut &'b str, delimiter: char) -> &'b str {
    if let Some(i) = s.find(delimiter) {
        let prefix = &s[..i];
        let suffix = &s[i + delimiter.len_utf8()..];
        *s = suffix;
        prefix
    } else {
        let prefix = *s;
        *s = "";
        prefix
    }
}

Why This Works

• 'b is unified with 'static (the lifetime of our string literal).
• 'a is unified with the short, local lifetime of the borrow of x inside the test block.
• The compiler does not need to perform any invalid subtyping on the invariant inner type of s because 'b remains 'static throughout.
• The mutable borrow of x only lasts for 'a, allowing x to be accessed immutably immediately after the block ends.

Idiomatic Lifetime Elision

We can simplify this signature using Rust's lifetime elision rules. If we omit the outer borrow's lifetime, the compiler automatically generates a distinct anonymous lifetime for it:

pub fn strtok<'b>(s: &mut &'b str, delimiter: char) -> &'b str

This is expanded by the compiler to exactly the decoupled 'a, 'b signature shown above, keeping the API clean and ergonomic.

7. PhantomData, Drop Check, and Variance Control

When writing custom collection types, smart pointers, or FFI wrappers, you often need to control the variance of generic parameters manually. This is achieved using std::marker::PhantomData.

PhantomData Patterns and Their Effects

The Drop Check Problem

If your type contains PhantomData<T>, the compiler's drop checker assumes your type will drop instances of T when it goes out of scope. This can restrict usability if T contains references that are dropped before your container.

If your type does not own or drop T (for example, a parser or deserializer that merely references T during its lifetime), you should use PhantomData<fn() -> T>:

use std::marker::PhantomData;

// Covariant over T, but tells the drop checker we do NOT drop T
pub struct Deserializer<T> {
    _marker: PhantomData<fn() -> T>,
}

Covariant Raw Pointers: NonNull<T>

By default, the raw mutable pointer *mut T is invariant over T. However, the standard library provides std::ptr::NonNull<T>, which is explicitly designed to be covariant over T.

pub struct NonNull<T: ?Sized> {
    pointer: *const T, // Covariant under the hood
}

If you are building a custom pointer type (like Box<T> or Rc<T>) and want it to be covariant over T, you should use NonNull<T> instead of *mut T. If your type allows mutation and requires safety invariants, you must manually add PhantomData to enforce invariance where necessary.

8. Summary and Key Takeaways

• Subtyping in Rust is almost exclusively applied to lifetimes, where 'static is a subtype of any generic lifetime 'a ($'\text{static} \le '\text{a}$).
• Covariance allows you to pass a longer-lived reference where a shorter-lived reference is expected.
• Invariance is a critical safety mechanism that prevents you from writing short-lived references into long-lived mutable references, which would otherwise cause use-after-free bugs.
• &mut T is invariant over T but covariant over its own borrow lifetime.
• Lifetime Unification Errors (such as "cannot borrow as immutable because it is also borrowed as mutable") often occur when you accidentally unify the borrow lifetime with the data lifetime in a single parameter.
• Decoupling Lifetimes (e.g., &'a mut &'b str) resolves unification errors by allowing the compiler to shorten the borrow lifetime 'a while preserving the data lifetime 'b.
• PhantomData is the primary tool for manually specifying variance and drop-check behavior in generic types that do not directly store their generic parameters.