E0581/E0582 (lifetime not found in input type) occurs even when the lifetime is in traits used as inputs

[Manishearth]

trait Yokeable<'a>: 'static {
    type Output: 'a;
}

fn project<Y, P, F>(f: F)
    where Y: for<'a> Yokeable<'a>,
        P: for<'a> Yokeable<'a>,
        F: for<'a> FnOnce(<Y as Yokeable<'a>>::Output) -> <P as Yokeable<'a>>::Output {}
fn project_fn<Y, P>(f: for<'a> fn(<Y as Yokeable<'a>>::Output) -> <P as Yokeable<'a>>::Output)
    where Y: for<'a> Yokeable<'a>,
            P: for<'a> Yokeable<'a> {}

fn main() {}

(playpen, also tested on rustc 1.54.0-nightly (fe72845f7 2021-05-16))

produces

   Compiling playground v0.0.1 (/playground)
error[E0582]: binding for associated type `Output` references lifetime `'a`, which does not appear in the trait input types
  --> src/main.rs:10:59
   |
10 |         F: for<'a> FnOnce(<Y as Yokeable<'a>>::Output) -> <P as Yokeable<'a>>::Output
   |                                                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^

error[E0581]: return type references lifetime `'a`, which is not constrained by the fn input types
  --> src/main.rs:14:67
   |
14 | fn project_fn<Y, P>(f: for<'a> fn(<Y as Yokeable<'a>>::Output) -> <P as Yokeable<'a>>::Output)
   |                                                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: aborting due to 2 previous errors

The lifetime is used in the inputs, just behind a trait.

[Manishearth]

A workaround to this bug is to just add an &'a () parameter to the function. Ultimately, you are still allowed to write closures that borrow from the other parameter.

[Manishearth]

cc @eddyb @tmandry

[eddyb]

The lifetime is used in the inputs, just behind a trait.

Sadly, it's not "used" in the specific sense that rustc cares about here ("constrained by" is much better IMO).
<Y as Yokeable<'a>>::Output is not obligated to keep 'a (once normalized), this is why projections don't count as "(constraining) uses" of parameters. You can always have a blanket impl with type Output = ();, for example.

And the important thing is that not only the generic form (still parameterized by Y and P) has to have a way to extract 'a in the output type from the input types, but any normalization.

As far as rustc is concerned, Yokeable impls could exist which would result in for<'a> FnOnce(()) -> Foo<'a>.
And now you have an unbound lifetime, which is a source of unsoundness (it can become anything).

---

I was trying to find some history on this, and there's a RFC (0447) but I remember these things being a huge soundness hole - there's issues like #32330 and more recently #47470, but they don't link together nicely.

---

Anyway, I'd probably let @nikomatsakis handle this, but I'd either close this as "working as intended", or turn it into a diagnostic issue, in that we could special-case the error to not sound wrong.

Specifically, "which does not appear in the trait input types" is not technically correct (the lifetime appears but is unconstrained by the type it appears in).
The other error, "which is not constrained by the fn input types", is, but both could benefit from a note along the lines of "the lifetime shows up in an associated types, which cannot constrain it".

[Manishearth]

Yeah I definitely think this situation should have a diagnostic that at a minimum talks about the soundness issue and perhaps proposes the workaround.

[SkiFire13]

Is there any change to make this more permissible when it can be proven that if the normalized output type contains a lifetime then one of the input types must also contain it?

For example I would expect the following snippet to compile because the input and output types are the same, so there's no way only the return type contains a lifetime after normalization:

trait A<'a> {
    type Assoc;
}

fn test<T, F>(_: F)
where
    T: for<'a> A<'a>,
    F: for<'a> FnOnce(<T as A<'a>>::Assoc) -> <T as A<'a>>::Assoc
{}

This is a more complicated example, but I would also expect it to compile because if <<T as A<'a>>::AssocA as B>::AssocB contains a lifetime then it must come from <T as A<'a>>::AssocA, which is also present in the input types.

trait A<'a> {
    type AssocA: B;
}

trait B {
    type AssocB;
}

fn test<T, F>(_: F)
where
    T: for<'a> A<'a>,
    F: for<'a> FnOnce(<T as A<'a>>::AssocA) -> <<T as A<'a>>::AssocA as B>::AssocB
{}