Variance with fn pointers

Hey folks,

sorry, I have to ask again because I want to be sure that I really understand it. Could anybody verify that what I think about the different cases (comments) is correct?

fn _foo<'x, 'y>(_: &'x mut &'y (), _: &'y ()) {}

fn _bar<'c, T>() {
	
	// All good - just as the function signature.
	let fp: for<'a, 'b> fn(&'a mut &'b (), &'b ()) = _foo; 

	// Supertype coercion to 'c for second 'b, contravariance not ok, because (('c >= any lifetime 'b in invariant position can be) = not true).
	let _: for<'a, 'b> fn(&'a mut &'b (), &'c ()) = fp;

	// Supertype coercion to 'static in second 'b, contravariance ok, because (('static >= any lifetime 'b in invariant position can be) = true).
	let _: for<'a, 'b> fn(&'a mut &'b (), &'static ()) = fp;
	
	// Supertype coercion to 'c for first 'b. Not ok because bound 'b: 'c is due to invariance from position of 'c required but non-existent.
	let _: for<'a, 'b> fn(&'a mut &'c (), &'b ()) = fp;

	// Supertype Coercion of both 'b's to 'c - ok.
	let _: for<'a> fn(&'a mut &'c (), &'c ()) = fp;

	// Works. Supertype Coercion of both 'b's. 'static will always outlive 'c.
	let _: for<'a> fn(&'a mut &'c (), &'static ()) = fp;

	// Fails. 'b cannot always outlive 'static.
	let _: for<'a, 'b> fn(&'a mut &'static (), &'b ()) = fp;

	// Also fails. 'c must outlive 'static. 'c is here in contravariant position and behaves covariant when using the fn pointer. The lifetime must not be less than 'static due to invariance of 'static in the first parameter.
	let _: for<'a> fn(&'a mut &'static (), &'c ()) = fp;
	
	// Trivial. Also works.
	let _: for<'a> fn(&'a mut &'static (), &'static ()) = fp;

}

I would be very grateful for that. :pray:

Regards
keks

EDIT: Removed unused lifetimes and changed names of lifetimes at _foo to make it better readable.

You're going to confuse yourself by using the same names for different things. Let's rename lifetimes at the top.

fn _foo<'x, 'y>(_: &'x mut &'y (), _: &'y ()) {}

Let's look at:

	// Works. Supertype Coercion of both 'b's. 'static will always outlive 'c.
	let _: for<'a, 'b> fn(&'a mut &'c (), &'static ()) = fp;

No, there's only one coercion here. This is what happens:

// This is the type of the `fp` expression itself with no coercions.
let v1: for<'a> fn(&'a mut 'c (), &'c ()) = fp;
// The latter lifetime is coerced from 'c to 'static.
let v2: for<'a> fn(&'a mut 'c (), &'static ()) = v1;
// An unused lifetime is added.
let v3: for<'a, 'b> fn(&'a mut 'c (), &'static ()) = v1;

So the lifetime behind the mutable reference is not coerced ... and of course it can't be coerced.

1 Like

Hmm... ok, but when going from a higher-kinded lifetime to a regular generic lifetime isn't a coercion, what is it then?

... and when going from 'b to 'static in the latter 'b is a coercion is going from 'b to 'static in the former position no coercion when you say lifetimes behind mutable references can't be coerced? ... because the last example works:

	let _: for<'a> fn(&'a mut &'static (), &'static ()) = fp;

This declaration:

means that for any lifetime 'x and 'y you can get a function. You're choosing to do that with 'x = 'a and 'y = 'static, which gives you that signature.

Degenralization

1 Like

There seems to be a bit of variation on how the word “coercion” is used in previous replies. For how I would use this terminology: the word “coercion” refers to a conversion operation between values of different types.

If using the terminology like this, I wouldn’t say “the lifetime is coerced”. The thing that is being coerced is the function pointer fp itself.


Or the function item _foo for that matter, which would be coerced here

let fp: for<'a, 'b> fn(&'a mut &'b (), &'b ()) = _foo;

because this is a coercion between different type. You are coercing the function item _foo

  • from its anonymous, zero-sized, higher-ranked function item type
  • to the higher-ranked function pointer type for<'a, 'b> fn(&'a mut &'b (), &'b ()) (function pointers are called by dynamic function calls, and have pointer-sized values)

All your other examples also are about coercions; and indeed specifically about a subtype-to-supertype type of coercion.

When using the word “coercion” like this, it is definitely true that “going from 'b to 'static”, turning fp into a value of type for<'a> fn(&'a mut &'static (), &'static ()), is a coercion.

This type of subtyping is explicitly documented (though the reference text isn’t perfect here IMO, e.g. I can’t find any mention of how to do subtyping within higher-ranked function pointer types).

This section became more technical than I planned originally, but I wanted to some aspects of fn-pointer-subtyping more clear to myself; feel free to skip it.

An attempt to sketch out a more complete definition for subtyping

Trying to write down a definition, I could come up with about 4(+2)[1] rules for subtyping in Rust; where 2(+1) rules are simple / base cases, and 2(+1) are recursive rules:

the 2 basic rules would be

  • [substituting a lifetime, according to variance]: some type[2] containing a (free[3]) lifetime 'a[4] is subtype of the same type with 'a replaced by any other (free) lifetime 'b[5] whenever it is the case that 'a and 'b relate as required by the variance with which the position 'a appears in the type
    • for a covariant position, this requires 'a: 'b to be the fulfilled
    • for a contravariant position, this requires 'b: 'a to be the fulfilled
    • for an invariant position, this requires 'a: 'b and 'b: 'a to be the fulfilled
  • [substitution / instantiation of higher-ranked lifetimes with concrete ones]: some type of the form for<'a, …> fn(…) -> … or dyn … + for<'a, …> Trait<…> – is a subtype of the same type with 'a removed from the for<…> and all (bound) occurrences/mentions of that 'a systematically replaced by the same (free) lifetime 'b[6]

as additionally, there’s

  • [reflexivity]: every type is subtype of itself

the 2 recursive rules would be

  • [subtyping inside of higher-ranked function pointer types]: a function pointer type of the form for<'a, lifetimes…> fn(Args1…) -> Ret1… is a subtype of for<'a, lifetimes…> fn(Args2…) -> Ret2… whenever it is the case that: for<lifetimes…> fn(Args1…) -> Ret1… would be a subtype of for<lifetimes…> fn(Args2…) -> Ret2… [this is the same relation, but with 'a removed from the for<…>[7]] in a context that’s (also) fully generic over <'a>[8]
  • [substituting an entire type in type-level sub-expressions, according to variance]: some type containing a (free[9]) type sub-expression[10] T1[11] is subtype of the same type with the sub-expression T1 replaced by any other (free) sub-expression T2 whenever it is the case that the types T1 and T2 relate as required by the variance with which the position T1 appears in the type
    • for a covariant position, this requires T1 to be a subtype of T2
    • for a contravariant position, this requires T2 to be a subtype of T1
    • for an invariant position, this requires T1 and T2 to be the same type^(this is slightly stronger than requiring T1 and T2 to be mutual subtypes; though discussing the exact question of what types are or aren’t the “same” is beyond the scope of this reply)

and additionally, there’s

  • [transitivity]: if some type T1 is subtype of T2 which is subtype of T3, then T1 is subtype of T3.

(These rules aren’t polished, and may contain mistakes or bad phrasing.)

Additionally to rules akin to these, there would be a handful of additional things to consider. For instance: higher-ranked function pointer or trait object types come with implied bounds; and many type constructors might also come with validity constraints. Those things also matter in the whole picture; but this would go too far, and it’s a topic so complex that there are even known soundness issues where the compiler itself isn’t handling those correctly yet.


Finally, it’s important to note that a type of the form

  • for<'a, …> fn(…) -> … or dyn … + for<'a, …> Trait<…>

is the same type as the corresponding type

  • for<…> fn(…) -> … or dyn … + for<…> Trait<…>, i.e. the same thing with the parameter 'a removed from the for<…> binder

whenever it is the case that the lifetime 'a isn’t actually used/appearing anywhere within the types of the args&return of the function pointer signature, or the generic parameters of the trait bound, respectively.

Also, reordering of the lifetimes listed in a for<…> binder never changes the type; and the same applies to completely removing an empty “for<>” binder.

Example usage of the rules

To repeat the list with shortened names, the 2 + 2 main rules I could determine are

  • “lifetime variance”
  • “instantiation of higher-ranked”
  • “inside of higher-ranked”
  • “sub-expressions”

With this list of rules available, we can then cite the relevant rule (usually, transitivity is not explicitly called out) to prove a subtyping relationship more systematically. E.g. let's follow the same steps @alice already did before:

This corresponds to determining for<'a, 'b> fn(&'a mut &'b (), &'b ()) a subtype of for<'a, 'b> fn(&'a mut 'c (), &'static ()):

  1. for<'a, 'b> fn(&'a mut &'b (), &'b ()) is a subtype of for<'a> fn(&'a mut 'c (), &'c ()) under the “instantiation of higher-ranked”-rule
  2. for<'a> fn(&'a mut 'c (), &'c ()) is a subtype of for<'a> fn(&'a mut 'c (), &'static ()) under the “lifetime variance”-rule
  3. for<'a> fn(&'a mut 'c (), &'static ()) is the same type as for<'a, 'b> fn(&'a mut 'c (), &'static ()), as 'b isn’t used anywhere. You could quote “reflexivity” if you will… and you could quote “transitivity” to combine all these steps.

Back to the question I was answering…

Anyway… after this longer-than-anticipated aside, let me get back to my previous statements, i.e. to reply to

I already wrote above[12], I would answer this with: yes, this is also a coercion (at least when using the word “coercion” like the Rust reference).

Now, this following point on how choosing generic arguments for function items isn’t a coercion, is also (mostly) true.

It only applies in a different context though; the original question was about different function-pointer types, whereas the direct meaning of what you get from a function declaration is rather about function items.

In the world of (higher-ranked) function pointer types, for<'a, 'b> fn(&'a mut &'b (), &'b ()) and for<'a, 'b> fn(&'a mut &'c (), &'c ()) both exist, and they are distinct types.

How do the anonymous, zero-sized types of function items handle generics?

They usually do it with concrete type parameters. E.g. if you have a

fn foo<T>(x: T) { … }

then any usage of it will define the type for the generic argument.

Maybe let's look at a concrete example… let’s do without coercing to an fn pointer, but also one where where the item is used a bit more value-like than what a simple foo(x) call expression would do:

fn usage(x: i32) {
    (foo,).0(x)
}

Now, after type-inference, the above code is actually more like sugar for a more explicit

fn usage(x: i32) {
    (foo::<i32>,).0(x)
}

using foo::<i32> instead of just foo. If we were to model these anonymous types with a struct, it could look like struct FooItem<T>(PhantomData<fn(T)>);, and foo::<T> creates a value of type FooItem<T>.

Notably, without further context, foo itself has an ambiguous type; you only use it by substituting in a concrete type in place of T, which is either given explicitly by adding ::<i32>, or inferred. Type inference makes this choice implicit, but there isn’t any coercion[13] happening here, just as something like let x: usize = 42; isn’t doing any coercion[14].

A concrete value of this function item type can't generically handle multiple types, not even multiple lifetimes:

it doesn't work in concrete usage

use std::cell::Cell;

fn usage<'a>(x: Cell<&'a i32>, y: Cell<&'static i32>) {
    let f = foo::<Cell<&'_ i32>>;
    f(x); // both of these calls
    f(y); // together don't work
}

(playground)

nor does it support creation a higher-ranked-lifetime function pointer

fn usage(x: Cell<&'a i32>, y: Cell<&'static i32>) {
    let f: fn(&i32) = foo; // error[E0308]: mismatched types
    //                ^^^ one type is more general than the other
}

(playground)

The way this works for lifetime arguments is more subtle & involved; the compiler differentiates so-called “early-bound” lifetimes which work like type parameters, from “late-bound” ones, which support higher-ranked function pointers, and are never part of the function item type.

Your function is the “late-bound” case; so while @alice’s explanation is correctly describing the intended basic mental model for generic functions, from the compiler’s and the type system’s point of view, arguably fn _foo<'x, 'y>(_: &'x mut &'y (), _: &'y ()) {} is it’s own inherently-generic kind of entity and you aren’t even allowed to further specify these lifetimes arguments:

fn _foo<'x, 'y>(_: &'x mut &'y (), _: &'y ()) {}

fn usage<'a>() {
    let f = _foo::<'a, 'static>; // error[E0794]: cannot specify
    // lifetime arguments explicitly if late bound lifetime parameters
    // are present
}

  1. the +2 being reflexivity and transitivity ↩︎

  2. by “any type” I mean any type expression, however complex it may be

    the rules for determining the variance of a lifetime in a type expression (or later also: a type within a larger type expression) are beyond the scope of this comment

    with the second recursive rules below taken into account, these rules become partially redundant/overlapping, e.g. Foo<Bar<'a>> being a subtype of Foo<Bar<'static>> could be determined with this rule, observing 'a as covariant in Foo<Bar<'a>>, or by using the “substituting entire types”-rule (presented further down below), by observing Bar<'a> in a covariant position in Foo, and Bar<'a> being subtype of Bar<'static>

    this redundancy suggests, there’s probably more minimal ways of stating the preconditions for this rule, but like this, it’s easier to avoid pulling the whole definition of variance into this ↩︎

  3. i.e. it doesn’t refer to a lifetime introduced by a for<'a, …>-binder within the same type expression ↩︎

  4. 'a is meant as a stand-in for any name, even 'static ↩︎

  5. 'b is meant as a stand-in for any name, even 'static ↩︎

  6. 'b is meant as a stand-in for any name, even 'static ↩︎

  7. which turns every mention of this 'a inside of the Args… and Ret… types into a free lifetime ↩︎

  8. i.e. the same kind of setting like when doing type-checking inside the body of some generic function foobar<'a> or withing some impl<'a> block; if the original context already has generic arguments, imagine a new context with a new parameter 'a added ↩︎

  9. i.e. it doesn’t contain any lifetimes introduced by a for<'a, …>-binder outside of T1 ↩︎

  10. this “sub-” has nothing to do with subtyping ↩︎

  11. T1 is meant as a stand-in for type-expression however complex, like Foo<'a, Bar, [Baz; 42]> ↩︎

  12. I’m referring to these paragraphs:

    All your other examples also are about coercions; and about a subtype-to-supertype type of coercion more concretely.

    When using the word “coercion” like this, it is definitely true that “going from 'b to 'static”, turning fp into a value of type for<'a> fn(&'a mut &'static (), &'static ()), is a coercion.

    ↩︎
  13. the type of the expression foo is inferred and directly evaluates be a function item of the anonymous type of foo::<i32> to begin with ↩︎

  14. the type of the literal expression 42 is inferred and directly evaluates to be an integer of type usize to begin with ↩︎

2 Likes

Thank you very much for your detailed explanation and your thoughts about this! :hushed::pray: