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

help
1

I have read the section [subtyping and Variance] in Rustonomicon, and also read other blogs such as Understanding Rust Lifetimes – NEAR Protocol. However, I still cannot understand why Box<&' longer T> is a subtype of Box<&' shorter T>.

I can understand that in a type &'a T, its lifetime 'a and the behind type T are covariant. I also can understand that T in Box<T> is covariant. However, since the lifetime is also a part of the type system, that means the enclosed types in Box<&' longer T> and Box<&' shorter T> are different types, that is to say, we should view them as Box<T> and Box<U>.

In this example, I know 'longer is a subtype of 'shorter since 'longer : 'shorter. However, why is &' longer T a subtype of &'shorter T? Moreover, why Box<T> is a subtype of Box<U> if T is a subtype of U?

1 Like
2

Because you can use a &'long T anywhere you need a &'short T. IOW, it's fine if the referent lives longer than the region that would be considered strictly necessary by some other part of the code.

Because a Box<T> is essentially just a T allocated on the heap instead of being stored inline. But almost every other property of T is conferred to the Box that is holding it (modulo things like ?Sized-ness and Unpin), since the box has unique ownership of its contents. And it doesn't matter from the PoV of lifetimes whether some value lives on the stack or on the heap or anywhere else. It's all just memory, and the important properties are described by types, not by where the value is stored.

5 Likes
3

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.

4

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
5

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
6

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[1] be coerced into U with a no-op[2]. 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[3]. 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 :slightly_smiling_face:.

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
7

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?

8

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<A> ⊆ T<B> iff A ⊆ B
Contravariant: T<A> ⊆ T<B> iff A ⊇ B
Invariant: T<A> ⊆ T<B> iff A = B
(where ⊆ means “is a subtype of”)
9 Likes
9

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
10

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
11

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?

12

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

1 Like
13

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

14

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
15

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. [1] 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
16

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. :relieved:

2 Likes
17

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
18

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.

19

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

20

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