Rust Quiz 5: when will higher-ranked closure type be yielded?

https://dtolnay.github.io/rust-quiz/5
Here is the code:

trait Trait {
    fn p(self);
}

impl<T> Trait for fn(T) {
    fn p(self) {
        print!("1");
    }
}

impl<T> Trait for fn(&T) {
    fn p(self) {
        print!("2");
    }
}

fn f(_: u8) {}
fn g(_: &u8) {}

fn main() {
    let a: fn(_) = f;
    let b: fn(_) = g;
    let c: fn(&_) = g;
    a.p();  // 1
    b.p();  // 1
    c.p();  // 2
}

I'm kind of confused about the output of c.p(). According to the revelation:

For b we infer _ = &'x u8 for some concrete lifetime 'x that will ultimately feed into the borrow checker. The type of b is fn(&'x u8) .
And finally for c we infer _ = u8 , yielding the higher-ranked closure type for<'a> fn(&'a u8) .

I can't tell when will higher-ranked closure type be yielded.
And In this case, for b,when the lifetime 'x be a concrete value and what is it?
And what's the usage scenario for HRTB

2 Likes

In this particular case, I believe the phrase "higher-ranked closure type" is incorrect. fn(...) is a function pointer, not a closure.

cc @dtolnay

1 Like

Below is my personal understanding of higher-ranked types, maybe incorrect.

I just read the article about Higher-ranked types and it's very useful :slight_smile:

So, I think higher-ranked types means when you use those types, the "type parameter" can not be decided. for example, fn<T> add(a: T, b: T), when we use this, we can replace the type parameter with a concrete type like i32 etc, so we should not call this function-pointer type higher-ranked.

In the second implementation, fn(&T) requires a "type parameter" called lifetime(because it use reference/borrow), and this type parameter(lifetime) can not be decide until the function is called, right? like this doc - hrtb said:

How on earth are we supposed to express the lifetimes on F 's trait bound? We need to provide some lifetime there, but the lifetime we care about can't be named until we enter the body of call ! Also, that isn't some fixed lifetime; call works with any lifetime &self happens to have at that point.

So, if we add lifetime annotation to the second impl, it would be this (playground, the output is 112 with some warnings):

impl<T> Trait for for<'a> fn(&'a T) {
    fn p(self) {
        print!("2");
    }
}

See this issue for more details.

You may ask, why not declare the lifetime along with type parameter T, like this:

impl<'a, T: 'a> Trait for fn(&'a T) {
    fn p(self) {
        print!("2");
    }
}

Well, if you run this code, you will get this error:

error[E0119]: conflicting implementations of trait `Trait` for type `fn(&_)`
  --> src/main.rs:11:1
   |
5  | impl<T> Trait for fn(T) {
   | ----------------------- first implementation here
...
11 | impl<'a, T: 'a> Trait for fn(&'a T) {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `fn(&_)`

For more information about this error, try `rustc --explain E0119`.
error: could not compile `playground` due to previous error

It means we add two impl to the same type(or we can say T already include '&a T, the first impl already included the second impl), you can run rustc --explain E0119 to see what this means. T is a type parameter that can be any types, if we change type parameter T in second impl to the name A, we get this error:

error[E0119]: conflicting implementations of trait `Trait` for type `fn(&_)`
  --> src/main.rs:11:1
   |
5  | impl<T> Trait for fn(T) {
   | ----------------------- first implementation here
...
11 | impl<'a, A: 'a> Trait for fn(&'a A) {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `fn(&_)`

For more information about this error, try `rustc --explain E0119`.
error: could not compile `playground` due to previous error

You can see, T can be &'a A, it is a type parameter, it can be any concrete type, same for type parameter A. So, when we decide the concrete type for code impl<'a, A: 'a> Trait for fn(&'a A), the lifetime 'a can be decide, because it is along with type parameter A, it constraint the type A that it must outlive 'a, since reference of A is will be pass to call of fn, that means the lifetime 'a must outlive the scope of fn, this is pretty straightforward, right? This is what happened if you write explicit lifetime notation this way.

Now, see this code:

fn with<'a, T>(callback: T)
    where T : FnMut(&'a Data)
{
    let data = Data { ... };
    callback(&data)
}

If we add the lifetime to the signature of fn width, that means the 'a must outlive the scope where fn width is called, but data is inside the width fn, when the fn is called, the fn body scope(s) is framed as call stack, and 'a is outlive this scope(s),
so what inside the stack have smaller lifetime than 'a, variable data is inside this stack, it's liveness smaller than 'a, so it can not pass to callback, compiler will report an error. In this case, we need declare that callback need a reference that can with any lifetime(smaller or bigger), see this rfc for more details.

From this rfc we know:

When using the Trait(T1, ..., Tn) notation, implicit binders are introduced for omitted lifetimes. In other words, FnMut(&int) is effectively shorthand for for<'a> FnMut(&'a int), which is itself shorthand for for<'a> FnMut<(&'a int,),()>. No implicit binders are introduced when not using the parentheses notation (i.e., Trait<T1,...,Tn>). These binders interact with lifetime elision in the usual way, and hence FnMut(&Foo) -> &Bar is shorthand for for<'a> FnMut(&'a Foo) -> &'a Bar. The same is all true (and already true) for fn types.

So, in the quiz code:

fn main() { 
	let a: fn(_) = f; 
	let b: fn(_) = g; 
	let c: fn(&_) = g; 
	a.p(); 
	b.p(); 
	c.p(); 
}
  1. a have type fn(u8), f have type fn(u8)(Pointer(ReifyFnPointer)).
  2. b have type fn(u8), g have type for <'r> fn(&'r u8) (Pointer(ReifyFnPointer)).
  3. c have type for <'r> fn(&'r u8), g have type for <'r> fn(&'r u8) (Pointer(ReifyFnPointer)).

In the method call expression, we know the receiver type is known, so b.p() have receiver type fn(u8) will look up method in the first impl.

This all seems somewhat related to the closure refactoring issue I ran into here: The implementation of FnOnce is not general enough - #2 by quinedot

I wish I could understand towry's answer better. Especially how to determine the types given below:

Also, I don't understand how the following two impls don't overlap, since T also includes &T, does it not?

I think T does includes &T, but the lifetime binder is in different place, see later-bound & early-bound Early and Late Bound Parameters - Guide to Rustc Development and the rfc link.

And this impl pattern is bad, see the issue link provided above.

We no longer accept both of these impls. Code relying on this pattern would now have to introduce "newtypes", like struct Foo(for<'a> fn(&'a u8)) .

So this may become an error in the future (now it just is a warning):

warning: conflicting implementations of trait `Trait` for type `fn(&_)`
  --> src/main.rs:11:1
   |
5  | impl<T> Trait for fn(T) {
   | ----------------------- first implementation here
...
11 | impl<T> Trait for for<'a> fn(&'a T) {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `fn(&_)`
   |
   = note: `#[warn(coherence_leak_check)]` on by default
   = warning: this was previously accepted by the compiler but is being phased out; it will become a hard error in a future release!
   = note: for more information, see issue #56105 <https://github.com/rust-lang/rust/issues/56105>
   = note: this behavior recently changed as a result of a bug fix; see rust-lang/rust#56105 for details

For your first question, you can run the quiz code in rust playground, and comment out the println statements since it's irrelevant, check out the MIR representation, you will have a better view of what is going on.

1 Like

Caveat upfront: These are things not really documented that well, when at all, and on the whole subject to some amount of change. Inference in general is a tricky area because small changes can be breaking in unexpected ways on top of that.

Also this reply (like this thread) is sort of all over the place, sorry about that.


Some more background on functions being late-bound vs early-bound, higher-ranked vs. not:

One of the take-aways is that these functions are higher-ranked:

fn f(_: &u8) {}
fn g<'a>(_: &'a u8) {}

But this one is not, because the bound -- even though otherwise meaningless! -- opts the function out of being higher-ranked:

// The bound -- ':' -- means this is sugar for a where-clause
// `where 'a: 'a`
fn h<'a: 'a>(_: &'a u8) {}

So that's how you can tell the higher-ranked-or-not nature of functions.

Unfortunately, the compiler errors aren't quite nuanced enough here -- it says things like

28 |     let c: fn(&_) = h;
   |                     ^ one type is more general than the other
   |
   = note: expected fn pointer `for<'r> fn(&'r u8)`
              found fn pointer `fn(&u8)`

Really it found the fn(&'x u8) for some concrete 'x, like in the quiz; fn(&u8) is short for for<'a> fn(&'a u8). (Granted, there is no handy syntax for the type when the lifetime is anonymous yet concrete like that...)

Also keep the subtyping in mind -- a higher-ranked for<'a> fn(&'a u8) can coerce into a fn(&'specific u8). And there are some other nuances in the weeds I'll just ignore here.


However, as it turns out, the leak coherence lint is about implementations, and it doesn't consider bounds -- only naming. So in the example provided before, these are both considered overlapping:

// Overlaps `impl<T> Trait for fn(T)
impl<'a, T: 'a> Trait for fn(&'a T) {}
impl<'a, T> Trait for fn(&'a T) {}

Even though there's no (non-implicit) bound involving 'a in the second one. Just being able to name 'a is enough. Why the difference? This part is even more a guess than the rest of this accumulated knowledge, but I think it's a combination of:

  • The lint just isn't smart enough
  • Even having a name may make it too tricky to detect problematic cases, due to implicit bounds

Well, that's the second time I've mentioned implicit bounds without defining it, so what am I talking about? I'm referring to this:

&'a T

implying that T: 'a. Sometimes this is also called a WF bound or such, which is short for "well-formed". Having a &'a T where T: 'a does not hold is undefined behavior, so it's generally just implied to hold. This is certainly great just for having to type less boilerplate, but also has practical (if convoluted) uses. But also non-convoluted uses -- remember that if you write out this implied bound on your function definitions, they will no longer be higher-ranked!


Now, looking at the leak coherence lint a little closer...

Eh, I wouldn't call it bad exactly, albeit unintuitive. Here's a bad pair:

trait Trait {}
impl Trait for for<'a, 'b> fn(&'a u32, &'b u32) {}
impl Trait for for<'c> fn(&'c u32, &'c u32) {}

Like the issue says, that used to warn as part of the same lint, but is now rejected -- those fn are subtypes of each other, i.e. the same type. However, from that same issue,

There will still be impls that trigger #56105 after this lands, however -- I hope that we will eventually just accept those impls without warning, for the most part. One example of such an impl is this pattern

trait Trait {}
impl<T> Trait for fn(&T) { }
impl<T> Trait for fn(T) { } // still accepted, but warns

Which is to say, unless the direction of Rust changes (again), when you get a leak coherence lint error, it's probably on something that is hopefully accepted some day. See also this writeup for MCP 295.

More conversation from the issue:

[...] they would be considered distinct types. In particular, the first type fn(T) cannot ever be equal to the second type for<'a> fn(&'a U) because there is no value of T that can name 'a .

So that's why they're non-overlapping: they're distinct types (although the latter is a subtype of the former).

This is an area where the direction of Rust has changed before though, if you read through all those issues.

The reason for the warning, however, is that we cannot yet distinguish that type from those where implied bounds lets us figure out that 'a is equal to some other region that T could name (I give some examples in the MCP, I think).

And this is the source of my guess on why the lint is fuzzier in terms of knowing when it will trigger than function definitions are in terms of knowing when they are higher-ranked or not.

(Probably if I reread the MCP in depth, I would regain a more solid understanding.)


So, what's the connection to closures? Closures can be higher-ranked over lifetimes too, but (unless/until RFC 3216 is implemented), you're generally relying on inference to make it that way. And it's not great at it really; hence the RFC for a better concrete way to force higher-rankedness. Adding a arg: &_ to the definition can nudge the compiler in that direction, currently. But there are no hard guarantees around it; the main thing preserving behavior is probably just a desire not to break things by changing inference too much.

Thus it's even harder to identify a higher-ranked closure on sight: It depends on both its context and how inference behaves, which is a lot fuzzier to me at least than the rules around function declarations; certainly it's a lot touchier with regards to things like refactoring. The RFC would definitely help.

(My personal take is that we should also gain a way to annotate non-higher-ranked lifetime parameters in closures, as that would open the way to making anonymous lifetimes '_ higher-ranked in closure parameter lists, just like they are in fn declarations. Then in like 4 editions or whatever we could eventually have better closure inference by default, as there would be better ways to mitigate inference breakage by being more explicit.)

((Technically I don't think the behavior with function declarations is guaranteed either [1], but it's much more concrete than inference, and a lot of things would break if it changed -- making less things higher-ranked is a big breaking change, and making turbofishable functions higher-ranked would make them no-longer-turbofishable, which is also a breaking change.))


  1. given how it is practically undocumented... ↩︎

1 Like

Woah, why does this even compile in the first place? :frowning: Why is the overlapping impl a mere warning and not an error? It's an error in any other case (I know of), and certainly it's BadTM to allow this kind of ambiguity.

I think this is a decent summary of the underlying type-theory reasons; the more up-to-date practical reasons are in the leak coherence bug and linked issues (but granted, they're not quick to digest). My impression is that the lint was leading towards disallowing the combination, but too many things rely on it now and things are swinging the other direction now, but I haven't put in the work to back up this impression by re-reading everything for citations. (Well, the current direction is clear from the MCP.)

The only completely analogous stable case I know of is dyn for<'a> Trait<&'a T> and friends (including dyn Fn(&T) etc). Non-min specialization is another (unsound) example since you can specialize on lifetimes and thus on subtypes.

Other sets of non-subtyping but coerce-able types are arguably related, like implementing differently for [T; N] and [T] or something.

1 Like

Thanks. I don't really see overlapping impls mentioned there, though. In the MCP, Niko states that

Neither, they would be considered distinct types. In particular, the first type fn(T) cannot ever be equal to the second type for<'a> fn(&'a U) because there is no value of T that can name 'a.

However, this seems to contradict the warning (and also my intuition) – impl Trait for fn(T) should apply to any and all T, and thus to any fn(T), including fn(&'a U) for any and all choices of 'a. Or did I forget my first-order logic?

It doesn't seem important whether one can syntactically express explicit specialization of the HRTB; if the impls overlap, and we get inconsistent behavior based on which type gets inferred, it's still a tremendous problem, regardless of how we got there.

Just an up-front note that I'm not advocating a position, just conveying my understanding of the situation.

I think it's analogous to why this doesn't work:

trait Trait {}
impl<T: ?Sized> Trait for T {}

fn foo<R, F>(f: F)
where
    R: Trait,
    F: 'static + Fn(&str) -> R,
{
    let local = String::new();
    f(&local);
}

fn main() {
    // This is the only part that doesn't work
    foo(std::trim);
}

R is a single, concrete type; for 'static to apply, R must be 'static. So it can't be a borrow of the input (unless the input is also 'static). However, returning a borrow can work if F is higher ranked, but the bounds would be different:

// Using `unboxed_closures` syntax so we can omit `R` as a type parameter
// (On stable you would use a helper trait)
fn foo<F>(f: F)
where
    F: 'static + for<'any> Fn<(&'any str,)>,
    for <'any> <F as FnOnce<(&'any str,)>>::Output: Trait,

The return type here can depend on the input type, and with str::trim it does. And thus it is not a concrete type over the whole of this implementation -- the type varies per input lifetime -- so it can't be a type parameter, as those always resolve to concrete types. Or in Ariel's words,

after all, what would that T be? for<'a> &'a Foo ? That is not a type

For the case where the parameter in question is an input, this means that impl Trait for fn(T) applies to fn(&'a U) for any concrete lifetime 'a -- any concrete type &'a U -- but it doesn't apply to for<'a> fn(&'a T), because the input is not a single concrete type.

(Recent thread involving trait bounds like these.)

Here comes another paragraph of my haven't-bothered-to-properly-cite recollection: The latter type is a subtype of the former type, and can be coerced to it, and this was good enough for awhile -- it was never the case that impl<T> Fn(T) applied to higher ranked types; instead, coercion would kick in elsewhere. Then the 2017 issue changed things and coercion starting failing to be "good enough"; the work-around was to have both implementations. Then NLL came along and tried to make the two implementations overlapping again, but the fallout was too great. Then came the leak coherence lint to gradually make them illegal, but with continued push-back for certain cases. Then the MCP to recognize these cases as distinct and allow them came along, but hasn't been rolled forward into an RFC or whatever yet. And here we are.


However, this seems to contradict the warning (and also my intuition)

It does, and you're not alone; e.g. this recent issue based around the lint making the things it warns about illegal, contrary to the MCP. And my comments about things changing directions and not being certain. It's a pretty un-great situation; there should be an RFC or fiat or something so that a decision on the direction is made. Or at least the messaging of the lint updated so people stop taking it as a given that it will become illegal, in the meantime.


I do wonder about another comment of Ariel's,

NB: With higher-ranked types you could theoretically have something like impl<A<*>, B<*>> JSTraceable for for<'a> fn(A<'a>) -> B<'a> , but that opens it own can of worms.

as I have pondered the possibility of such a type-constructing generic parameter myself when these higher-ranked bound discussions come up. But I'm not a type theorist or compiler dev and have no idea as to the worms. They can't be implicit though; that would make it so you couldn't collect a bunch of T into a (non-'static) Vec as it may be inferred to be a T<*>, say.

This whole topic also reminds me of variadic generics (different types based on some vector of lifetimes you're generic over). There is also occasionally mention of some desired ability to implement traits for all function pointers (and maybe Fn-like implementers? Unclear).

But these alternative approaches seem quite distant indeed, compared to an active MCP.

The fact that (as far as I know) Rust is reserving the right to let subtyping kick in "anywhere" as opposed to more formal coercion sites does make it more treacherous to allow implementations on both super- and sub-types. Which in turn reminds me of some of the conversation here, trying to suss out if subtyping actually is anything more than coercion with variance. (And also more examples of people taking the lint to mean the issue is settled in that thread.)

1 Like

Thanks for the explanation – it seems to me this is a situation where we would actually need either more theory/more formal reasoning, or at least more precise elaboration of, and more agreement around, what interpretation we want for HRTBs in these corner cases.

2 Likes