What does it mean that Box is covariant if Box<dyn B> is not a subtype of Box<dyn A> where B: A?

Question

After I read the subtyping chapter of the Nomicon, I couldn't wrap my head around covariance of a type parameter. Especially for the Box<T> type, which is described as: T is covariant.

However, if I write this code:

trait A {}
trait B: A {}

struct C;
impl A for C {}
impl B for C {}

fn foo(v: Box<dyn A>) {}

fn main() {
    let c = C;
    let b: Box<dyn B> = Box::new(c);
    foo(b);
}

(Playground)

error[E0308]: mismatched types
  --> src/main.rs:13:9
   |
13 |     foo(b);
   |         ^ expected trait `A`, found trait `B`
   |
   = note: expected type `std::boxed::Box<(dyn A + 'static)>`
              found type `std::boxed::Box<dyn B>`

B is clearly a "subtype" of A and Box is covariant over its input. I don't know why it doesn't work or why it won't do any type coercion. Why would they consider Box<T> to be covariant where the only use cases are invariants?

Answer 1

What subtyping and variance means in Rust

The Nomicon is not a fully polished document. Right now, 5 of the most recent 10 issues in that repo specifically deal with subtyping or variance based on their title alone. The concepts in the Nomicon can require substantial effort, but the information is generally there.

First off, check out some initial paragraphs (emphasis mine):

Subtyping in Rust is a bit different from subtyping in other languages. This makes it harder to give simple examples, which is a problem since subtyping, and especially variance, are already hard to understand properly.

To keep things simple, this section will consider a small extension to the Rust language that adds a new and simpler subtyping relationship. After establishing concepts and issues under this simpler system, we will then relate it back to how subtyping actually occurs in Rust.

It then goes on to show some trait-based code. Reiterating the point, this code is not Rust code anymore; traits do not form subtypes in Rust!

Later on, there's this quote:

First and foremost, subtyping references based on their lifetimes is the entire point of subtyping in Rust. The only reason we have subtyping is so we can pass long-lived things where short-lived things are expected.

Rust's notion of subtyping only applies to lifetimes.

What's an example of subtyping and variance?

Variant lifetimes

Here's an example of subtyping and variance of lifetimes at work inside of a Box.

A failing case

fn smaller<'a>(v: Box<&'a i32>) {
    bigger(v)
}

fn bigger(v: Box<&'static i32>) {}

error[E0308]: mismatched types
 --> src/lib.rs:2:12
  |
2 |     bigger(v)
  |            ^ lifetime mismatch
  |
  = note: expected type `std::boxed::Box<&'static i32>`
             found type `std::boxed::Box<&'a i32>`
note: the lifetime 'a as defined on the function body at 1:12...
 --> src/lib.rs:1:12
  |
1 | fn smaller<'a>(v: Box<&'a i32>) {
  |            ^^
  = note: ...does not necessarily outlive the static lifetime

A working case

fn smaller<'a>(v: Box<&'a i32>) {}

fn bigger(v: Box<&'static i32>) {
    smaller(v)
}

Invariant lifetimes

Here's a case that works:

struct S<'a>(&'a i32);

fn smaller<'a>(_v: &S<'a>, _x: &'a i32) {}

fn bigger(v: &S<'static>) {
    let x: i32 = 1;
    smaller(v, &x);
}

The same code with all the references changed to mutable references will fail because mutable references are invariant:

struct S<'a>(&'a mut i32);

fn smaller<'a>(_v: &mut S<'a>, _x: &'a mut i32) {}

fn bigger(v: &mut S<'static>) {
    let mut x: i32 = 1;
    smaller(v, &mut x);
}

error[E0597]: `x` does not live long enough
 --> src/lib.rs:7:16
  |
7 |     smaller(v, &mut x);
  |     -----------^^^^^^-
  |     |          |
  |     |          borrowed value does not live long enough
  |     argument requires that `x` is borrowed for `'static`
8 | }
  | - `x` dropped here while still borrowed

Addressing specific points

B is clearly a "subtype" of A

It is not.

Box is covariant over its input

It is, where covariance is only applicable to lifetimes.

I don't know why it doesn't work or why it won't do any type coercion.

This is covered by Why doesn't Rust support trait object upcasting?

Why would they consider Box<T> to be covariant

Because it is, for the things in Rust to which variance is applied.

See also

• How do I deal with wrapper type invariance in Rust?
• Why does linking lifetimes matter only with mutable references?
• What is an example of contravariant use in Rust?

Answer 2

To add a bit:

I think the confusion here is mainly due to a common misconception that when we say Foo<T>, T is always assumed to be an owned type. In fact, T can refer to a reference type, such as &i32.

As for (co)variance, Wikipedia defines it as:

Variance refers to how subtyping between more complex types relates to subtyping between their components.

In Rust, as pointed by others, subtyping applies to lifetimes only. Subtrait relationships don’t define subtypes: If trait A is a subtrait of trait B, it doesn’t mean that A is a subtype of B.

An example of subtyping among lifetimes: A shared reference (e.g. &'a i32) is a subtype of another shared reference (e.g. &'b i32) if and only if the former’s lifetime outlives the latter’s lifetimes ('a outlives 'b). Below is some code that demonstrates it:

fn main() {
    let r1: &'static i32 = &42;
    
    // This obviously works
    let b1: Box<&'static i32> = Box::new(r1);
    
    // This also works
    // because Box<T> is covariant over T
    // and `&'static i32` is a subtype of `&i32`.
    // NOTE that T here is `&i32`, NOT `i32`
    let b2: Box<&i32> = Box::new(r1);
    
    
    let x: i32 = 42;
    let r2: &i32 = &x;
    
    // This does NOT work
    // because `&i32` is NOT a subtype of `&'static i32`
    // (it is the other way around)
    let b3: Box<&'static i32> = Box::new(r2);
}