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

help
1

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?

2

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.

3

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.

4

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

5

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

Similarly, here we see that there is no sub/supertype relation between the two function pointer types.

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

Instead of

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
6

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.

7

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
8

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;

Operator expressions - The Rust Reference says

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.

9

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
10

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)

11

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?

12

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
13

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?

14

@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?

15

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
16

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.

17

Yes, that all sounds right to me.

1 Like
18

Thanks very much. I see.

19

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
20

@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.