FnOnce with GAT argument with HRTB is misinterpreted by the type system

[Eliah-Lakhin]

I tried this code:

trait GAT {
    type Assoc<'a>;
}

fn foo<A: GAT>(
    f: impl for<'a> FnOnce(<A as GAT>::Assoc<'a>) -> <A as GAT>::Assoc<'a>,
) {}

And it fails to compile:

error[[E0582]](https://doc.rust-lang.org/stable/error-index.html#E0582): binding for associated type `Output` references lifetime `'a`, which does not appear in the trait input types
 --> src/lib.rs:7:54
  |
7 |     f: impl for<'a> FnOnce(<A as GAT>::Assoc<'a>) -> <A as GAT>::Assoc<'a>,
  |                                                      ^^^^^^^^^^^^^^^^^^^^^

For more information about this error, try `rustc --explain E0582`.

Even if it's not a bug, but the current type system limitations, the error description E0582 seems to be misleading(or is not well descriptive).

Meta

Checked with rustc:

• 1.67.0
• 1.68.0-beta.1
• 2023-01-30 001a77f

[compiler-errors]

So the short story is that the lifetime 'a appears in FnOnce's input types, but it's not constrained. After substituting A and normalizing A::Assoc<'a>, it may be that the normalized type doesn't reference 'a, which causes issues.

I agree the diagnostic really is misleading though.

[nandesu-utils]

So the short story is that the lifetime 'a appears in FnOnce's input types, but it's not constrained. After substituting A and normalizing A::Assoc<'a>, it may be that the normalized type doesn't reference 'a, which causes issues.

Why does normalizing introduce issues? Let's consider another but very similar example:

trait GAT {
    //             >  < added a bound
    type Assoc<'a>: 'a;
}

fn foo<A: GAT>(f: impl for<'a> FnOnce(<A as GAT>::Assoc<'a>) -> <A as GAT>::Assoc<'a>) {}

And now the error still persists. However from the standpoint of foo, the argument does indeed carry lifetime information, which does constrain the argument to a specific lifetime.

Another way to think about it is that GATs resemble type constructors and if we consider &'a T to be a type constructor &<'a, T> (which it is?) and remember that 'a is covariant then we would notice that in impl for<'a> FnOnce(&'a T) the argument carries same generic 'a bound, as if it was written as &T: 'a, hence you can put whatever lifetime "bigger" than 'a into it.

However what about variance in GATs? I don't think A::Assoc<'a> is covariant, it isn't stated to be so at least.

[Pzixel]

@compiler-errors hmm, so you're saying that it's okay but just an error is misleading? If so is it even possible at all then to declare a function with such intent, i.e. accepting rank-2 labmda that has an argument of whatever lifetime and returns it?

[marmeladema]

it may be that the normalized type doesn't reference 'a

But both the argument and the return type will be normalized to the same type? So if the normalized type references the lifetime then the input flows into the output, or it doesn't, and then there is no issue?
But I am probably misinterpreting what you said. I am definitely not an expert of the trait system 🥲

[SkiFire13]

Looks like a duplicate of #86702

My understanding of the issue is that the compiler is being overly conservative when reasoning about whether a lifetime can appear in the generic parameters and/or associated types of a trait bound (for Fn* traits the input types are generic parameters and the output type is an associated type). In particular it can only check if a lifetime always/may/never appears in the generic.
In case a lifetime may appear in both the generic parameters and the associated types it can't rule out that there may be some cases where it appears only in the generic parameters and not in the associated types.

To fix this I think it should reason about the relations between those types, and simple equality is not enough (see the second example in this comment of mine)

[Kolsky]

Issue #32330 mentions desugaring, and the primary reason seems to relate to the fact that closure types can only ever be parameterless in their desugared form in their current implementation. It's also why generic closures aren't supported, as far as I understand.

[SkiFire13]

Issue #32330 mentions desugaring, and the primary reason seems to relate to the fact that closure types can only ever be parameterless in their desugared form in their current implementation. It's also why generic closures aren't supported, as far as I understand.

The issue in #32330 was only due to lifetimes only appearing in the output type/associated type. In the case of this issue this is impossible, since if the lifetime appear in the output then it will also have to appear in the input (and FnOnce(&'a ()) -> &'a () is a perfectly valid trait!)

The problem is that the current logic for preventing the bug described in #32330 is overly conservative and assumes that projections in input types never contain lifetimes, while projections in output types always contain lifetimes, which obviously fails when the input and output types are the same (or at least somehow related)

[Kolsky]

The problem is that the current logic for preventing the bug described in #32330 is overly conservative and assumes that projections in input types never contain lifetimes, while projections in output types always contain lifetimes, which obviously fails when the input and output types are the same (or at least somehow related)

While it's true, the lifetimes in GATs aren't ever considered used (and for a good reason: they don't have to be used at all!), and this would also exclude more general cases such as GatT::Type<'a> -> GatU::Type<'a> anyway (with no guarantee for any sort of relation between usage of corresponding lifetimes in input vs. output)[1]. In fact lifetimes don't have to appear in the input, they just have to be constrained by either closure type or Fn* trait, evading bivariance (they can't be constrained by type Output, at least in a current solver). If we look at it strictly from Fn* input perspective (used in trait impl), each output lifetime can be assigned to PhantomUsed<'_> input argument (ignoring variance for a moment). Then, since such lifetimes must already appear in impl generics, we can notice that these PhantomUsed<'_> args can be transferred to a closure's type (fields) WLOG. Adding variance back, it may make sense to overly restrict it to invariance for a case with generics, albeit it can still make a lot of use cases inconvenient, so I'm not sure what to do here. Maybe it would be fine with HRTB.

[1] The less general case only considers Gat::Type<'a0, 'a1, ...> -> Gat::Type<'a0, 'a1, ...>; it would always be valid, because either each of 'a0, 'a1, ... appears in both input/output, or none. That's not the case for more advanced/complex GAT usages, and desugaring here isn't quite obvious.

[SkiFire13]

Then, since such lifetimes must already appear in impl generics, we can notice that these PhantomUsed<'_> args can be transferred to a closure's type (fields) WLOG.

But the issue is about higher ranked trait bounds, whose lifetimes can't be named by the bounded type, thus you can't move them to the closure type.

[Kolsky]

Fn* traits can have special handling for this specific use case, or be modified in a way that allows working with them uniformly.

Edit: unfortunately adding a lifetime to a type wouldn't really work, I've just realized. Accounting for a lifetime use in associated type still can unless I'm missing something.