Trouble with higher-ranked lifetimes and GATs

The following code (on the playground here for your convenience) fails with a "higher-ranked lifetime error" pointing to the use of with_callback:

pub trait MyTraitSuper {
    type Assoc<'b>: MyTrait<'b>;
}

pub trait MyTrait<'a>: MyTraitSuper + 'a {
    fn with_callback<'slf, C: for<'c> FnOnce(Self::Assoc<'c>)>(&'slf self, callback: C);
}

pub fn f<'a, T: MyTrait<'a>>(input: T) {
    input.with_callback(f);
}

What puzzles me is that the error message has a note

note: could not prove `for<'c> fn(<T as MyTraitSuper>::Assoc<'b>) {f::<'a, <T as MyTraitSuper>::Assoc<'b>>}: FnOnce<(<T as MyTraitSuper>::Assoc<'c>,)>`

and while I can see that for<'c> f::<'a, ...>: FnOnce<Assoc<'c>> doesn't hold, I would expect for<'c> f::<'c, ...>: FnOnce<Assoc<'c>> to hold, and I don't understand why rustc wants to plug in 'a for f's lifetime parameter.

Does anyone know why this happens? Or is there a different way to express what I want?

I don't know what significance the naming of the lifetimes in the error has, if any.

But each monomorphized f::<T> only takes one type, and you're asking for a closure that can take (potentially, depending on the trait implementation) many types (that differ by lifetime).

I'm not sure exactly what you do want. But given the FnOnce bound, you could just require a single lifetime, if a caller-chosen lifetime (i.e. longer than the function body) works for your use case.

If you need the higher-ranked bound, the callback probably needs to take something that can vary by lifetime. Or perhaps, find a way to force the associated type to be a single type.

1 Like

Or this

pub fn f<T: for<'a, 'b> MyTrait<'a, Assoc<'b> = T>>(input: T) {
    input.with_callback(f);
}

with_callback holds a bound for<'b> <T as MyTraitSuper>::Assoc<'b>[1], and thus needs f<T: MyTrait<'???, for<'b> Assoc<'b> = ???>>>[2].

input.with_callback(f) needs to prove T::Assoc<'anylifetime> == T, thus needs to specify the associated type in the trait bound. This means T on f should be any lifetime instead of an outer lifetime for f, which leads to f<T: for<'a> MyTrait<'a, for<'b> Assoc<'b> = T>>. To make the bound valid syntax, it ought to be the form provided above.


  1. due to C: for<'c> FnOnce(Self::Assoc<'c>) in its signature ↩︎

  2. for<'b> Assoc<'b> is invalid syntax though ↩︎

1 Like

Thanks for the hints! I will give them a try on my non-minimized problem and report back. I had tried some version of the caller-chosen lifetime already. I had some trouble implementing the trait in that case, but maybe I can get it done with the right collection of lifetime bounds.

Could you elaborate on the monomorphization, though? My understanding was that different instantiations of the lifetimes were always monomorphized to the same function, so then I don't see why that monomorphized function can't implement FnOnce for all lifetimes 'c. In fact, if the types are concrete enough then it does seem to work: in this version, rustc seems to agree that f: forall<'c> FnOnce(Concrete<'c>):

pub struct Concrete<'c>(std::marker::PhantomData<&'c mut ()>);

impl<'a> MyTrait<'a> for Concrete<'a> {
    fn with_callback<'slf, C: for<'c> FnOnce(Concrete<'c>)>(&'slf self, _callback: C) {}
}

pub trait MyTrait<'a>: 'a {
    fn with_callback<'slf, C: for<'c> FnOnce(Concrete<'c>)>(&'slf self, callback: C);
}

pub fn f<'a>(input: Concrete<'a>) {
    input.with_callback(f);
}

Thanks for the response! I don't understand why I'd expect to need that the associated type is equal to T, can you elaborate?

In my application, I was hoping to do something like

impl<'a> MyTrait<'a> for Node<'a> {
    type Assoc<'b> = Leaf<'b>;
}
impl<'a> MyTrait<'a> for Leaf<'a> {
    type Assoc<'b> = Leaf<'b>;
}

so that I could call f on a Node, and it would call the callback on a Leaf.

Because input.with_callback(f) is called in f where f takes T (i.e. f is of FnOnce(T)) and with_callback takes FnOnce(Self::Assoc) (i.e. f is of FnOnce(T::Assoc)).

In that case, you may want T::Assoc<'anylifetime> == NotT, in which you need a type parameter (or likely a concrete type Leaf) to express the associated type in the bound.

pub fn f<T, G>(input: T)
where
    G: for<'any> MyTrait<'any>,
    T: for<'a, 'b> MyTrait<'a, Assoc<'b> = G>,
{
    input.with_callback(g);
}
pub fn g<G: for<'any> MyTrait<'any>>(_: G) {}

// or
pub fn h<T>(input: T)
where
    T: for<'a, 'b> MyTrait<'a, Assoc<'b> = Leaf<'b>>,
{
    input.with_callback(leaf);
}
pub fn leaf(_: Leaf) {}
1 Like

Hm, there's still something I'm missing here. Because f is generic, I think I should be able to have f mean both f<T> (in the outer call) and f<T::Assoc> (in the callback), with type inference providing the correct instantiation. For example, the following example without lifetimes compiles fine:

pub trait MyTrait {
    type Assoc: MyTrait;
    
    fn with_callback<C: FnOnce(Self::Assoc)>(self, callback: C);
}

pub fn f<T: MyTrait>(input: T) {
    input.with_callback(f);
}

Lifetimes are erased during compilation and not monomorphized, that's true. But there's still a distinction at the type level. The function item types can sometimes end up with the lifetime as a parameter ("early bound"), in which case the function item types (after resolving the lifetime parameter) cannot meet a higher-ranked bound.

Example. You probably get why the top half doesn't work; something analogous goes on in the second half.


That's for lifetime parameters of the function declaration. Type parameters are always parameters on the function item type (early bound). f::<X> and f::<Y> are two distinct types (unless X=Y).

So you can't have a function item type that satisfies this set of bounds, say:

F: FnOnce(String) + FnOnce(u32)

Because function items like this:

fn foo<D: Display>(input: D) {}

Act like this:

struct Foo<F>(/*...*/);
impl<F: Display> FnOnce<(F,)> for Foo<F> { /* ... */ }

So foo::<String>: FnOnce(String) and foo::<u32>: FnOnce(u32) but there is no single function item type implementing both.

We might get those, and the ability to be higher-ranked over types and not just lifetimes,[1] some day -- but we don't have them today.

That's a (late bound) lifetime parameter and not a type parameter.


  1. for<T> ↩︎

1 Like

There's a lot to learn :sweat_smile:

And I doubt T: for<'a, 'b> MyTrait<'a, Assoc<'b> = G> in my answer would actually work for Concrete<'c> because Concrete<'c> would barely be any 'c (nor 'static).
T: for<'a, ...> MyTrait<'a, ...> only solves the problem in OP (where T is generic and implies 'static), but doesn't solve the problem on concrete lifetimes shorten than 'static.

Here's an example of a single type which implements FnOnce(_) for different input types (not just lifetimes) on unstable.

On stable you can approximate it with your own trait.

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.