# Is there a simple and quick way to determine the variance if a type has multiple nested types with different variances?

Consider this case

``````T1  = &'a fn(&'b i32)->&'c i32
T2  = &'a fn(&'b1 i32)->&'c1 i32
``````

If we say `T1` is a subtype of `T2`, what is the relationship between `'b` and `b1`, and `c` and `c1`? Currently, I only have a slow way to compute the relationship. My thought process is:

1. `&'a U` is a subtype of `&'a U2` if `U` is a subtype of `U2` since `&'a T` is covariant in its `T`
2. Hence, `fn(&'b i32)->&'c i32` must be a subtype of `fn(&'b1 i32)->&'c1 i32`
3. Since `fn(T)->U` is contravariant in its `T` and covariant in its `U`
4. Hence, `&'b i32` must be a supertype of `&'b1 i32`
5. The above step means `'b1: 'b`
6. `&'c i32` must be a subtype of `&'c1 i32`, which gets `'c:'c1`

Hence, when

``````'b1: 'b and  'c:'c1
``````

`T1` is a subtype of `T2`. However, this way is too verbose and easy to be wrong. Is there a simple way to compute the relationship?

BTW, if `'b : 'b1` and `c:'c1`, what is the variance relationship between `fn(&'b i32)->&'c i32` and `fn(&'b1 i32)->&'c1 i32`?

Intuition I would say. Variance rules are not created out of thin air, it formed from
the soundness requirement. You should reason from the soundness, not from the basic rule of variance. You are doing it backward.

Yes, this example exactly starts from a practice. Merely, in this example, the type is a bit complex for deciding the variance. Moreover, for the second issue, I think it is meaningful.

Well. For really complicated case (which you should avoid in real code), just check contravariance level, or stop at invariance.

The simplest surefire way is probably to throw together a quick test per lifetime combination.

In practice there's rarely more than a couple lifetimes at play and one doesn't worry about variance until it bites, in which case it's usually invariance due to some lifetime

• Behind a `mut` or `UnsafeCell`
• As a trait parameter
• In `fn` input and output position
• In a GAT [1]

And/or just having a feel, like some recent conversation in a couple of other people's threads about not bothering with

``````fn foo<'a: 'b, 'b>(thing: &'a Thing) -> &'b Output
``````

``````fn foo(thing: &Thing) -> &Output
``````

Because, due to variance, the former is no more general than the latter... and vice-versa. Being comfortable with not adding unnecessary lifetimes can come from getting a feel for the common variance scenarios.

1. speculating this may become more common as GATs become more common âŠī¸

1 Like

I make a bit of modification to your linked code in the Rust Playground

``````fn f<'b1: 'b,'b, 'c: 'c1, 'c1>(
mut f: fn(&'b i32) -> &'c i32,
mut g: fn(&'b1 i32) -> &'c1 i32
) {
// f = g; This line would result in an error
g = f;  // Ok
}
``````

the type of `f` is a subtype of `g`, so `g = f;` is ok as analyzed in my question. The compiler would emit an error for the first one `f = g;`, which says

lifetime may not live long enough

Based on the essence, `g` cannot be coerced to the type of `f` since a supertype cannot be coerced to a subtype anyway.

However, if we change the trait bound the following, Rust Playground

``````fn f<'b1, 'b:'b1, 'c: 'c1, 'c1>(
mut f: fn(&'b i32) -> &'c i32,
mut g: fn(&'b1 i32) -> &'c1 i32
) {
f = g;
g = f;
}
``````

Both lines would give the error. But, in this time, I didn't know the reason, because I cannot determine the relationship between `fn(&'b i32) -> &'c i32` and `fn(&'b1 i32) -> &'c1 i32`, they are invariant?

Seems that each element that impacts the variance of the complete type would make the complete type a subtype of the other complete type, then that complete type is a subtype of the other type, otherwise, if the different variances exist for the complete type, it will be invariant. It's my suppose.

They're not invariant, but variance can't get you from one to the other. Each lifetime parameter has its own variance, making subtyping more than one dimensional, and not all concrete values have a sub/supertype relationship.

`f` is covariant in `'c` and g is covariant in `'c1`, and `c: 'c1`.

• So `f` can return both `'c` and `'c1` as outputs, but `g` can't return `'c`

`f` is contravariant in `'b` and `g` is contravariant `'b1`, and `'b: 'b1`.

• So `g` can accept both `'b1` and `'b` as inputs, but `f` can't return `b1`

So neither of these is true:

• `g` can accept `'b` as an output and return `'c` as an output
• `f` can accept `'b1` as an output and return `'c1` as an output

If I have

``````// Cat is a subtype of Animal
// Circle is a subtype of Shape
f: fn(Cat) -> Circle,
g: fn(Animal) -> Shape,
``````

I can pass a `Cat` to `g` and I can get a `Shape` back from `f`, but I can't

• Pass an `Animal` to `f`
• Get a `Circle` back from `g`

So I can't cast `f` to `g` or vice-versa.

1 Like

But, anyway, whether a value can be used to initialize another variable is based on whether type coercion can happen, as said in Type coercions - The Rust Reference.

Type coercions are implicit operations that change the type of a value.

We just interpret the case from the perspective that whether these types can be compatible, but it's not how the type coercion works. Or, be more clear, we use `as` syntax

``````f = g as fn(&'b i32) -> &'c i32;
``````

`as` can be used to explicitly perform coercions, as well as the following additional casts.

So, if `as` is not permitted in this case, we should interpret why based on coercion.

Maybe think of it this way:

``````         Input lifetime     Output Lifetime
* 'static        'static *
Big           |                        |
|                        |
* 'b ------ f ------- 'c *
|                        |
|                        |
|                        |
* 'b1 ----- g ------ 'c1 *
|                        |
Small         |                        |
``````

Either function can slide their input lifetime up and slide their output lifetime down, but you can't raise `g` up to `f` or lower `f` down to `g`. And here's a Hasse diagram of subtypes for all the combinations of input and output lifetimes in the figure:

``````// supermost
fn('static) -> 'c1
/           \
fn('b) -> 'c1         fn('static) -> 'c
/             \           /     \
fn('b1) -> 'c1              fn('b) -> 'c      fn('static) -> 'static
\             /           \     /
fn('b1) -> 'c             fn('b) -> 'static
\           /
fn('b1) -> 'static
// submost
``````

There is no upward path between `fn('b1) -> 'c1` and `fn('b) -> 'c` or vice-versa, so neither is a subtype of each other.

5 Likes

Is there as simple and quick way to determine the variance

• `fn` args are contravariant / invert the variance inside them / lifetimes can grow
• `fn` output is covariant / pass-through / lifetimes can shrink
• the lifetime behind `&` is covariant / can shrink:
``````//     â      â           â
T1  = &'a fn(&'b i32) -> &'c i32
``````

So for it to be a subtype by "moving" `'b` and `'c`, we need:

• a bigger `'b`,
• or a smaller `'c`.

(or a smaller `'a` if we also consider "moving" that one)

I'm unsure of the relationship between the lifetime parameters in this diagram. Do they satisfy those relationships?

``````'static : ' b
'b : 'b1

'static : 'c
'c : 'c1
``````

Your answer is wonderful but a bit academic, I'm not familiar with the knowledge of the Hass diagram. How could I simply understand this diagram? Does it mean an element in the diagram always can change in an upward direction but cannot change to a low direction?

Furthermore, in the diagram, we first consider the lifetime in the parameter type of the function type. Since `'b` is a subtype of `'b1`, hence `fn('b) -> 'c1 ` is on the above position of `fn('b1) -> 'c1`, `'static` is a subtype of `'b`, hence `fn('static) -> 'c1` is on the above position of `fn('b) -> 'c1`, I can understand this path. However, when we consider the return type of the function type. `'static` is a subtype of `'c` and `'c` is a subtype of `'c1`, why is `fn('b1) -> 'c` on the below position of `fn('b1) -> 'c1`, `fn('b1) -> 'static` is on the below position of `fn('b1) -> 'c`? Aren't they should similar to the case when we only consider the order of parameter types?

Yes.

Right, going up in the diagram (by following paths) is going from a subtype to a supertype (upcasting).

It means that subtype relation of types that correspond to a given type constructor is a partial order, similar to the intention behind say `PartialOrd::partial_cmp`. It's partial because you can't always compare two types `A` and `B` and give one of these answers:

• `A` is a subtype of `B` (`Less` or `Equal`)
• `B` is a subtype of `A` (`Equal` or `Greater`)

However, this doesn't mean that the constructor is invariant in its parameters! An invariant parameter would mean there are no paths where that parameter changed in the diagram.

In analogy to other partial orders,

• For sets
• `{x, y}` and `{x, z}` are not sub/supersets of one another, but they still have subsets and supersets other than themselves
• For divisibility
• 20 and 30 are not divisors/multiples of one another, but they still have divisors and multiples other than themselves

And so too

• For the previous snippet
• `fn(&'b i32) -> &'c i32` and `fn(&'b1 i32) -> &'c1 i32` are not sub/supertypes of one another, but they still have subtypes and supertypes other than themselves

See my updated comment, please interpret how the path is formed. I have some confusion about the path.

Furthermore, in the diagram, we first consider the lifetime in the parameter type of the function type. Since `'b` is a subtype of `'b1`, hence `fn('b) -> 'c1 ` is on the above position of `fn('b1) -> 'c1`, `'static` is a subtype of `'b`, hence `fn('static) -> 'c1` is on the above position of `fn('b) -> 'c1`, I can understand this path. However, when we consider the return type of the function type. `'static` is a subtype of `'c` and `'c` is a subtype of `'c1`, why is `fn('b1) -> 'c` placed on the below position of `fn('b1) -> 'c1`, `fn('b1) -> 'static` is placed on the below position of `fn('b1) -> 'c`? Shouldn't they be similar to the case when we only consider the order of parameter types?

@quinedot Oh, I seem to understand the reason for why we form the path, the path is talking about the variance of the whole function type, not of the single parameter type or return type in the function type. Since, `fn(T)->U` is contravariant in its parameter type but covariant in its return type, so for any `T1` that is a subtype of `T2`, `fn(T2)->U` is a subtype of `fn(T1)->U`, they have the same `U`. Then for the same parameter type, for any `U1` that is a subtype of `U2`, `fn(T)->U1` is a subtype of `U2`.

For any two types, the supertype always appears in the above position of the subtype. For example, `fn('b) -> 'c1` is a supertype of `fn('b1) -> 'c1`, so it appears above `fn('b1) -> 'c1`, `fn('b1) -> 'c1` is a supertype of `fn('b1) -> 'c`, so it appears above the latter.

That is, the diagram is based on this principle:

1. Supertype is always above(positionally) the subtype
2. Conversely, the subtype is always below(positionally) the supertype.

In the diagram, any two nodes are always reachable from one to another if the paths keep upward. Once, the paths contain any downward, they are not reachable. In Rust, one type can be coerced into another type by going through the upward path. Is my understanding right?

Right.

There has to be a path, if that's what you meant by positionally. If that's what you meant, yes.

(`fn(&'static) -> 'static` is "above" `fn('b1) -> 'c` in the diagram in terms of line numbers, say, but there's no upward path between them.)

Yes, if there's an upward path, you can coerce them.

You can start anywhere in the diagram and choose one parameter to change, and the subgraph will be that of the type constructor as-if the other parameters were invariant (or non-lifetime-carrying types if you prefer). Or conversely, the graph is like a cartesian product of these two:

``````// <-- sub                                                    super -->

fn() -> &'static i32  ----  fn() -> &'c i32    ----  fn() -> &'c1 i32

fn(&'b1 i32) -> ()    ----  fn(&'b i32) -> ()  ----  fn(&'static) -> ()
``````

But take care as this method of construction only holds if the lifetimes are independent. For example, `fn(&'a i32) -> &'a i32` is invariant in the lifetime (in the two lifetime positions), as the lifetime cannot grow in the output position and cannot shrink in the input position.

1 Like

Yes, I just meant that. I may use non-normative wording for describing the term in the Hasse diagram.

`fn(&'static) -> 'static` is "above" `fn('b1) -> 'c` in the diagram in terms of line numbers, say, but there's no upward path between them.

I used the wording "In the diagram, any two nodes are always reachable from one to another if the paths keep upward." to mean it.

Say `/` and `\` are roads. In order to say the position, we must first have a continuous road to reach that node from a node.

From `fn('b1) -> 'c` to `fn('static) -> 'static`, the continuous road/path is

``````                               fn('static) -> 'c #3 // #3 above #1,#2, and #4
#2 to #3, upward direction -> /               \   <- #3 to #4, downward direction
fn('b) -> 'c #2                  fn('static) -> 'static  #4
/   <- #1 to #2, upward direction
fn('b1) -> 'c  #1

``````

In this example, despite we have a continuous path/road from `#1` to `#4`, there is a downward direction, so we cannot coerce `fn('b1) -> 'c` to ` fn('static) -> 'static`. However, we can coerce `fn('b1) -> 'c ` to `fn('b) -> 'c`, or to `fn('static) -> 'c`. We even can coerce `fn('static) -> 'static` to `fn('static) -> 'c`, because all these paths that connect the source node to the destination node consist of only single upward paths.

Yes, that all sounds right to me.

1 Like

Thanks very much. I see.

I think the Rust reference should update for this part.

The variance of other `struct`, `enum`, and `union` types is decided by looking at the variance of the types of their fields. If the parameter is used in positions with different variances then the parameter is invariant.

This sounds like this rule only applies to `struct`, `enum`, and `union`. However, it should apply to any type constructor.

1 Like

@quinedot I try to use another example to check whether I can draw the diagram by myself. Given the relationships for these lifetimes

``````'static: 'ib
'ib    : 'is

'static: 'ob
'ob    :'os
``````

If we start the diagram from `fn('is)->'ob`, is this the correct diagram?

``````                                   fn('static)->'os
/
fn('ib)->'os      fn('static)->'ob
\       /       \
fn('is)->'os	  fn('ib)->'ob      fn('static)->'static
\		/       \       /
fn('is)->'ob   fn('ib)->'static
\       /
fn('is)->'static
``````

Honestly, I would say this diagram is hard to draw correctly, I have tried many times.