Rust: E0582 on valid HRTB code

[bill-myers]

The compiler rejects this code with E0582.

trait MyTrait
{
    type T;
}

fn foo<T>(t: T)
   where for<'x> &'x T: IntoIterator, for<'x> <&'x T as IntoIterator>::Item: MyTrait<T = &'x i32>
{}

The code is obviously valid.

[mark-i-m]

Playground: https://play.rust-lang.org/?gist=8609bbaa03052ed99c69f2e16693ed5f&version=undefined

[rw]

Seconded.

Found this issue via https://github.com/rust-lang/rust/issues/70262

[jplatte]

I'm running into the same issue with GAT (playground):

#![feature(generic_associated_types)]

pub trait Trait {
    type Gat<'a>;
}

fn fun<T, U, F>()
where
    T: Trait,
    U: Trait,
    F: for<'a> FnOnce(T::Gat<'a>) -> U::Gat<'a>,
{
}

What's the way forward here?

[jonas-schievink]

This error was introduced as a fix for https://github.com/rust-lang/rust/issues/32330. It seems to intentionally ignore projection inputs:

https://github.com/rust-lang/rust/blob/d903a9def4c29846ec6215ccc7fa76d39428f577/src/librustc_middle/ty/fold.rs#L966-L990

The reasoning there makes sense to me. Allowing this would potentially (depending on the IntoIterator impl) allow late-bound regions to appear in the assoc. type binding, which caused the unsoundness in https://github.com/rust-lang/rust/issues/32330.

There is also this test that makes sure that this is rejected, which matches the code in the original report almost exactly:

https://github.com/rust-lang/rust/blob/d903a9def4c29846ec6215ccc7fa76d39428f577/src/test/ui/associated-types/bound-lifetime-constrained.rs#L37-L41

However, @nikomatsakis wrote in https://github.com/rust-lang/rust/issues/32330:

The current treatment of early- vs late-bound is something that hasn't really scaled up well to the more complex language we have now. It is also central to #25860, for example. I think it is feasible to actually revamp how we handle things in the compiler in a largely backwards compatible way to close this hole -- and the refactoring would even take us closer to HKT. Basically we'd be pulling the Binder out of FnSig and object types and moving to be around types in general.

Is this still accurate, and has there been any movement on this? Would it allow the code posted here to compile? It looks like the work on universes (https://github.com/rust-lang/rust/issues/56105) may be part of the solution here.

Since the example in the original report can be simply made to compile by making 'a early-bound, it would also be helpful if the folks affected by this could write up what kind of code they'd like to be able to write, and why that cannot be accomplished without late-bound regions here.

[nikomatsakis]

Hmm. To be honest, I don't think this has much to do with the early- vs late-bound region distinction, or maybe it's just to far out of cache. Things like for<'a> would always be late-bound.

It is definitely true that the 'a in F: for<'a> Fn(<T as Foo<'a>>::Item) -> &'a u32 is effectively unconstrained, in some sense -- i.e., it doesn't necessarily appear in the trait inputs, but it appears in the trait output.

On the other hand, this is not obviously a problem to me. Quite possibly that where clause would not be provable, so the fn likely couldn't be called, but it might be that the function itself could ultimately be type-checked successfully.

To be honest thought I wouldn't expect to make many changes here for the moment. It doesn't seem like a major pattern or enabler to me and I'd be happier waiting until we make more progress in transitioning to chalk or at least improving other aspects of rustc's trait solver (which we are starting to do in order to enable GATs).