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.

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.

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

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>):

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.

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:

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:

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.