# How to understand why Box<&'longer T> is a subtype of Box<&'shorter T>>

Intuitively, I say we all agree on this point. The reference that has a longer "lifetime" can definitely be used in a context that only needs a shorter lifetime, which is guaranteed to be a valid use. However, from a pedantic perspective, which rules say this point? I would expect we have a formula that can help us determine these points.

I'm not sure what you are asking here or what sort of formula you are looking for. The rule is that `&'long T` is a subtype of `&'short T`, by definition. And the reason for this definition/rule is because it results in correct, memory-safe programs.

If you are looking for a formal, mathematically rigorous specification for Rust: there isn't one. You can google "Ferrocene", "RustBelt", and "Stacked Borrows" to read more about ongoing efforts to compile one.

2 Likes

Variance is the property of a type wrt its generic arguments that determines how subtyping of the arguments affects subtyping of the final type. `Box<T>` being covariant in `T` by definition means that if `T` is a subtype of `U` then `Box<T>` is a subtype of `Box<U>`. Combined with the fact that `&'longer T` is a subtype of `&'shorter T`, because shared references are covariant in both the lifetime and the pointed type, it means that `Box<&'longer T>` is a subtype of `Box<&'shorter T>`.

Now, why is `Box<T>` covariant in `T`? Because `Box<T>` is just an owned `T`, except put behind a pointer, so it inherits its type properties.
And why is `&'a T` covariant in `'a`? Because a references that is valid for `'longer` is also a reference that is valid for `'shorter`, thus it satisfies the is-a relationship.

These are not formar answers though, but I don't think such answers exist yet. To have them you would first need a formal definition of `Box`, shared references and the type system, and this is still lacking.

Technically lifetimes aren't types, so `'longer` is not a subtype of `'shorter`. However the effect is still the same when considering subtyping relations of types that contain them.

1 Like

It’s exactly the rules called “variance” (mostly “covariance”).

Regarding your previous statements on covariance

I’m not sure how good your understanding here is, since AFAIK the very definition of “`Box<T>` is covariant in the parameter `T`” is that “if `T` is a subtype of `U`, then `Box<T>` is a subtype of `Box<U>`” . So, you have me a bit confused by both stating “I understand `Box<T>` is covariant” and asking “why is `Box<T>` is a subtype of `Box<U>` if `T` is a subtype of `U`?”

As to give more motivation on what subtyping in Rust means: The necessary condition for `U` being a subtype of `T` in Rust is that `T` can soundly be coerced into `U` with a no-op. The sufficient condition then is that the variance and subtyping rules define `T` to be a subtype of `U`. I.e. not all types that could soundly be subtypes of each other (as determined by the necessary condition explained above) actually are subtypes of each other in Rust. I’ve given an example of applying my understanding of Rust’s variance rules on a non-trivial example e.g. in this post here, but you can also try to look up other sources; one introduction is e.g. this chapter in the nomicon edit… ah, I didn’t notice, that introduction is where you came from .

The covariance of `&'a T` in `'a` is sound because when `'a` is longer than `'b`, then `&'a T` can be coerced into `&'b T` as a no-op, i.e. without doing anything to the run-time value. And `Box<T>` is soundly covariant in `T` since if `T` can be converted into `U` as a no-op, then this no-op conversion can also logically happen behind one extra level of indirection, so `Box<T>` can be converted into `Box<U>` as a no-op.

1. as always in Rust, “soundness” refers to language design or library design that makes sure that memory safety cannot be violated without `unsafe` code; a coercion would be unsound if it can be exploited to break memory safety in safe Rust code ↩︎

2. i.e. without changing anything about the value at run-time. Also, Rust requires such a conversion between subtypes to be sound behind shared references, which is why `Cell<T>` can not be covariant in `T` ↩︎

3. E.g. arguably `fn() -> Cell<&'a ()>` could (AFAICT) soundly be a subtype of `fn() -> Cell<&'b ()>` if `'a: 'b`(*), but it isn’t because the variance rules of Rust conservatively don’t allow it. Similarly, arguably, `&'a mut T` could soundly be a subtype of `&'a T`, but people might not like this, since subtyping in Rust is currently only/mostly about lifetimes

(*) FYI, the relation `'a: 'b` is typically read as “`'a` outlives `'b`” and it means that the lifetime `'a` is “at least as long as” the lifetime `'b` (so the lifetimes could also be equal) ↩︎

10 Likes

Maybe, this is the question that I haven't understood well yet. What's the exact meaning of saying `U` is covariant in `T`? Means `U` can be coerced to `T`, or something else? AFAIK, the covariance only applies to the lifetime in type in rust, as you mentioned above. If `U` is covariant in `T` means `U` can be coerced to `T`, then we say `Box<T>` is covariant in `T` just means `Box<T>` can be coerced to `T`, why it is relevant to `Box<T>` is a subtype of `Box<U>` if `T` is a subtype of `U`?

This is not correct. `U` can be coerced to `T`, iff `U` is a subtype of `T`.

Variance is a property of a type constructor T<𝒳> which describes the subtyping relationship between `T<A>` and `T<B>` in terms of the relationship between `A` and `B`:

 Covariant: T ⊆ T iff A ⊆ B Contravariant: T ⊆ T iff A ⊇ B Invariant: T ⊆ T iff A = B
(where ⊆ means “is a subtype of”)
9 Likes

You seem to be missing the critical detail of variance, which is that it's not a relationship between types, but a relationship between relationships between types.

Specifically, saying "`Box<T>` is covariant in `T`" is not talking about an example `T` type, but the actual type parameter. Covariance means two instantiations of `Box`, say `Box<A>` and `Box<B>`, have parameters that have a subtype relation, say `A` is a subtype of `B`, then those instantiations have the same relation, here `Box<A>` is a subtype of `Box<B>`.

The way reference lifetimes work can be thought about in the same way, if you think of `&'a T` as syntax for `Ref<'a, T>`.

(Curse this phone, of course @2e71828 sniped me and prettier: hopefully this helps though!)

10 Likes

To give some practical examples beyond @2e71828's explanation: Variance can be different for each lifetime. E.g. `fn(&'a u8) -> &'b u8` is covariant in `'b` and contravariant in `'a`. And variance applies to lifetime variables as well as type variables. E.g. `&'a T` is covariant in `'a` and covariant in `T`, whereas `&'a mut T` is covariant in `'a` but invariant in `T`.

As I explored further in the post I’ve already linked above, variance of type variables ultimately affects variance of lifetimes. The type `Box<&'a Foo>` is covariant in `'a`; which can be determined by looking at the variance of `Box<T>` and `&'b S` (here `T`, `S`, and `'b` are type/lifetime variables).

`Box<&'a Foo>` is composed by: plugging in `'a` for `'b` and `Foo` for `S` in `&'b S`, and then pluggin the resulting `&'a Foo` for `T` in `Box<T>`. So the lifetime `'b` is appearing in the first/only (“`T`”) type argument of `Box<T>`, and then inside of that in the first/only (“`'b`”) lifetime argument of `&'b S`. The variance of these arguments, i.e. fact that `Box<T>` is covariant in `T` and `&'b S` is covariant in `'b`, combine to let us derive that `Box<&'a Foo>` is covariant in `'a`.

You could try to apply similar reasoning to infer e.g. that `&'a mut &'b mut u8` is covariant in `'a` and invariant in `'b`.

The reason why this reasoning/deduction works becomes clear if you expand the definition of variance in each case.

`Box<T>` is covariant in `T`” means that for every subtype `U` of `V`, `Box<U>` is a subtype of `Box<V>`

and “`&'b S` is covariant in `'b`” means that for every lifetime `'x` that outlives `'y`, and every type `S`, `&'x S` is a subtype of `&'y S`.

Now, “`Box<&'a Foo>` is covariant in `'a`” means that for every lifetime `'l` that outlives `'m`, `Box<&'l Foo>` is a subtype of `Box<&'m Foo>`. We can prove that this is the case based on the previous two statements, by instantiating type variables and lifetime variables:

`U` := `&'l Foo`
`V` := `&'m Foo`
`'x` := `'l`
`'y` := `'m`
`S` := `Foo`

Note: What do I mean by “instantiating”? Replacing the variables with these above instantiations, and we can infer

• from “`Box<T>` is covariant in `T`”, that
• if `U` is a subtype of `V`, then `Box<U>` is a subtype of `Box<V>`, thus in particular:
• if `&'l Foo` is a subtype of `&'m Foo`, `Box<&'l Foo>` is a subtype of `Box<&'m Foo>`,
• from “`&'b S` is covariant in `'b`”, that
• if `'x` outlives `'y`, then `&'x S` is a subtype of `&'y S`, thus in particular:
• if `'l` outlives `'m`, then `&'l Foo` is a subtype of `&'m Foo`.

Putting things together, “`Box<T>` is covariant in `T`” gives us the desired relation `Box<&'l Foo>` is a subtype of `Box<&'m Foo>`, provided that `&'l Foo` is a subtype of `&'m Foo`. And `&'l Foo` is a subtype of `&'m Foo` from the fact that “`&'b S` is covariant in `'b`”, provided that `'l` outlives `'m`.

This chain of implications shows indeed that for every lifetime `'l` that outlives `'m` , `Box<&'l Foo>` is a subtype of `Box<&'m Foo>`.

6 Likes

From your answer, "covariant" sounds like the relationship of the type parameters can be transferred between the result of the constructed types. AFAN, I just have a vague understanding. Say `Know<T>` is contravariant in `T`, what does it mean? Give the following type, `Know<T>`, `Know<U>` where T is a subtype of `U`. Furthermore, how the relationship would be if we say `Know<T>` is invariant in `T`?

@2e71828 answered this better than I could above (though you should know "iff" means "if and only if")

1 Like

Is the relationship defined in the table always true regardless of how covariant/ contravariant/invariant is between `T<A>` and `A`?

That's not true. Coercion is a separate relation. If `U` is a subtype of `T`, then `U` can be coerced to `T`, but the converse isn't true. For example, references always coerce to pointers.

The short answer is that `Box<T>` is an owned value of `T`, and thus must have the same variance as `T` itself, i.e. covariant.

The low-level answer is that the (edited) definition of Box is

``````pub struct Box<T: ?Sized, A: Allocator = Global>(Unique<T>, A);
``````

Here the allocator parameter is irrelevant for `T` variance, and `Unique<T>` is an unstable type defined as

``````pub struct Unique<T: ?Sized> {
pointer: NonNull<T>,
_marker: PhantomData<T>,
}
``````

The `NotNull<T>` is covariant, because

``````pub struct NonNull<T: ?Sized> {
pointer: *const T,
}
``````

and `*const T` is covariant by definition. The `Unique._marker` field is also covariant, because `PhantomData<T>` acts by definition as if an instance of `T`, i.e. also covariant in `T`.

Why is `*const T` covariant? I assume to make the inferences above work. Also, `&T` can be coerced to `*const T`, and `&T` must obviously be covariant, so it would be confusing if the implicit coercion could change variance in drastic ways. And the unsafe way to construct a `&T` is to take `*const T` and dereference it, which would also likely be unsound in most code if the types had different variances.

6 Likes

Are you trying to suss out the recursive nature of variance, in contrast with the relationships between subtypes?

If you boil it down to "can I shrink or grow lifetimes", you're asking whether a given lifetime is covariant (can shrink), contravariant (can grow), or invariant (can't change) in the type as a whole. The variance of a type as a whole is summarized in this article, although it is a bit dated. Perhaps this is what you meant when you referred to a relationship between the type constructor (`T<a>`) and its parameter (`A`).

In practice, though, you'll probably only care about covariance and invariance, and deeply nested generics are rare. Most people just get used to covariance and are occasionally surprised by invariance.  I'd say the most important cases for invariance are:

• `T` in `&'_ mut T` (but the outer lifetime is still covariant)
• By far the most common in tripping people up
• Trait parameters
• `T` in `Cell<T>` or other interior mutability types
• Parameters in `fn` input and output position simultaneously: `fn(&'a str) -> &'a str`
• This is an example of the "GLB" in the linked article
• Generic associated type parameters (at a guess; soon to be stabilized)

1. And though function parameters are contravariant, usually when it matters they're higher-ranked and accept any lifetime, in contrast with a specific contravariant lifetime. Or they're invariant because they also return the input lifetime. ↩︎

7 Likes

`SubType: SuperType`

• `T: U` means T can be used in a context where U is expected
• `T` is called the SubType; `U` is the SuperType

A type constructor `F` in Rust means any generic type with unbound arguments.

Covariance means:

• given `T: U`, then `F<T>: F<U>`
• given `T: U`, `F<T>` can be used anywhere `F<U>` is needed
• covariance can happen where there are multiple fields or generic types:
• e.g. `&'a X` is `F<'a, X>`, and covariant over `'a` and `X`, and
• given `'long: 'short`, then `&'long X: &'short X`
• given `Y: X`, then `&'a Y: &'a X`
• given `'long: 'short` and `Y: X`, then `&'long Y: &'short X`
• e.g. your custom `Struct<'a, T>(&'a T)` is `F<'a, T>`
• and specifically `Struct<'a, &'b W>` is `F<'a, &<'b, W>>` and an implied `'b: 'a`

An example is here:

``````fn main() {
let _static: Box<&'static str> = Box::new("");
let s = String::new();
let ref_s: &String = &s; // denote the type of `ref_s` is `&'s`

f(Box::new(ref_s), &_static); // works: thanks to the covariance and you even didn't notice that

let b: Box<&str> = Box::new(ref_s); // denote the type of `b` is `Box<&'b str>` because `'s: 'b` (`ref_s: &'s str` is used as `&'b str`)
// given `'b: 'a` (required by the annotation) and the fact `'static: 'a` ('static is a subtype of any lifetime),
// so for a specific `Box<&<'a, str>>` (a lifetime resolved by the compiler),
// `_static: Box<&'static str>` is used as `Box<&'a str>`,
// where `'a` is the region starting after `b: Box<&'b str>`.
f(b, &_static);

// A detail here: the coercion `&String -> &str` happens before the covariance.
// let b: Box<&String> = Box::new(ref_s);
// f(b, &_static); // expected struct `std::boxed::Box<&str>`
//    found struct `std::boxed::Box<&std::string::String>`

let s2 = String::new();
f(Box::new(ref_s), &Box::new(&s2)); // f(Box<&'s str>, &Box<&'s2 str>) obviously `'s: 's2` holds
// `Box<&'s str>` is used as `Box<&'s_short str>`
f(Box::new(&s2), &Box::new(ref_s)); // f(Box<&'ref_s2 str>, &Box<&'s_short str>)
// where `'s_short` is the region that starts after `'ref_s2` and ends at semicolon (at most)
}

#[allow(clippy::redundant_allocation)]
#[allow(clippy::borrowed_box)]
// Ignore `&Box`, because I don't want to instantiate `Box<&'static str>` multiple times.
fn f<'a, 'b: 'a>(_: Box<&'b str>, _: &Box<&'a str>) {}
``````

And adding a reference for the first parameter `fn f<'a, 'b: 'a>(_: &Box<&'b str>, _: &Box<&'a str>)` won't be terrifying or recondite any more. 2 Likes

Throwing in this reference from @jonhoo as I don't believe it was already mentioned.
The examples in this discussion are what helped variance click for me.

Crust of Rust: Subtyping and Variance (video)

2 Likes

What is the purpose we define the relationship in terms of covariant, invariant, and contravariant in rust? My rough impression about them is we only care how the `lifetime` in the source type would be changed to that that is suitable for the destination type. My rough understanding of covariant is that, if we say something `A` in `T` is covariant, that means a longer lifetime in `A` can be shrunk to be a shorter lifetime in order to match the destination type. Invariant means the lifetime cannot be changed at all whatever how the lifetime would be longer than that in the destination type. Not sure whether this is a correct understanding.

For contravariant, I have no idea about this concept. By the way, Is there any simple way to determine whether `G<T>` is a subtype of `G<U>` or not, or whether they are covariant, invariant, contravariant, or not? That `G` may be a generic type defined in the standard library, or may it be a customized generic type.

Is there any condition, such as `F<T>` is covariant over `T`, to make this statement true?

The condition is covariance, which is clearly stated there.

By comparison, invariance means given `T: U` there is no relation between `F<T>` and `F<U>`, so you must pass `F<U>` when `F<U>` is needed.

2 Likes

So, given `Cell<T>` and `Cell<U>`, where `T:U`, then `Cell<T>: Cell<U>`?

No, as described above that is invariant. The rule of thumb/ideal is:

• If you can't read from it, it's covariant
• If you can't write to it, it's contravariant
• If you can do both, it's invariant

For rust, this is about when the name is mut, that is, it's about the type.

1 Like