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 #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 #32330. It seems to intentionally ignore projection inputs:

rust/src/librustc_middle/ty/fold.rs

Lines 966 to 990 in d903a9d

	fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
	// if we are only looking for "constrained" region, we have to
	// ignore the inputs to a projection, as they may not appear
	// in the normalized form
	if self.just_constrained {
	if let ty::Projection(..) | ty::Opaque(..) = t.kind {
	return false;
	}
	}
	t.super_visit_with(self)
	}
	fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> bool {
	// if we are only looking for "constrained" region, we have to
	// ignore the inputs of an unevaluated const, as they may not appear
	// in the normalized form
	if self.just_constrained {
	if let ty::ConstKind::Unevaluated(..) = c.val {
	return false;
	}
	}
	c.super_visit_with(self)
	}

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 #32330.

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

rust/src/test/ui/associated-types/bound-lifetime-constrained.rs

Lines 37 to 41 in d903a9d

	#[cfg(clause)]
	fn clause1<T>() where T: for<'a> Fn(<() as Foo<'a>>::Item) -> &'a i32 {
	//[clause]~^ ERROR `Output` references lifetime `'a`
	}

However, @nikomatsakis wrote in #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 (#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).

[QuineDot]

I think these can be worked around with helper traits. (None of the examples have examples of application to test against though.)

The OP:

pub trait Helper<Other>: IntoIterator<Item=<Self as Helper<Other>>::Item> {
    type Item: MyTrait<T = Other>;
}

impl<U, Other> Helper<Other> for U where U: IntoIterator, U::Item: MyTrait<T = Other> {
    type Item = <Self as IntoIterator>::Item;
}

pub fn foo<T>(_: T)
where
    for<'x> &'x T: Helper<&'x i32>
{}

#70262:

pub trait Helper<I, X>: FnOnce(I) -> <Self as Helper<I, X>>::Intermediate {
    type Intermediate: Iterator<Item=X>;
}

impl<F, I, O, X> Helper<I, X> for F where F: FnOnce(I) -> O, O: Iterator<Item=X> {
    type Intermediate = O;
}

pub fn foo<F>(_f: F) where for<'a> F: Helper<&'a i32, &'a i64> {}

The GAT:

pub trait Helper<G, H>: FnOnce(G) -> H {}
impl<T, G, H> Helper<G, H> for T where T: FnOnce(G) -> H {}

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

See also this URLO thread.