HRTB bounds not resolving correctly (take 3, lifetimes on the RHS)

[Manishearth]

This is a new version of #85636 and #89196 . When reporting it I first hit an ICE which got fixed in #90638.

The basic idea is that bounds of the form for<'a> <Type as Trait<'a>>::AssocType: OtherTrait<'a> don't work. #85636, which has since been fixed, is about this same issue without a lifetime on the right side of the bound. This will likely also be a problem for GATs.

The commented out code is not necessary for it to work, but it gives an idea of why such a bound might be necessary.

Details

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


trait IsCovariant<'a> {}

struct Yoke<Y: for<'a> Yokeable<'a>> {
    data: Y,
}


// impl<Y: for<'a> Yokeable<'a>> Yoke<Y> {
//     fn project<Y2: for<'a> Yokeable<'a>>(&self, f: for<'a> fn(<Y as Yokeable<'a>>::Output, &'a ()) -> <Y2 as Yokeable<'a>>::Output) -> Yoke<Y2> {
//         unimplemented!()
//     }
// }

fn upcast<Y>(x: Yoke<Y>) -> Yoke<Box<dyn IsCovariant<'static> + 'static>> where
    Y: for<'a> Yokeable<'a>,
    for<'a> <Y as Yokeable<'a>>::Output: IsCovariant<'a>
    {
    // x.project(|data, _| {
    //     Box::new(data)
    // })
    unimplemented!()
}


impl<'a> Yokeable<'a> for Box<dyn IsCovariant<'static> + 'static> {
    type Output = Box<dyn IsCovariant<'a> + 'a>;
}

// this impl is mostly an example and unnecessary for the pure repro
use std::borrow::*;
impl<'a, T: ToOwned + ?Sized> Yokeable<'a> for Cow<'static, T> {
    type Output = Cow<'a, T>;
}
impl<'a, T: ToOwned + ?Sized> IsCovariant<'a> for Cow<'a, T> {}



fn upcast_yoke(y: Yoke<Cow<'static, str>>) -> Yoke<Box<dyn IsCovariant<'static> + 'static>> {
    upcast(y)
}

fn main() {}

(playpen)

The error shown is:

   Compiling playground v0.0.1 (/playground)
error[E0277]: the trait bound `for<'a> <_ as Yokeable<'a>>::Output: IsCovariant<'a>` is not satisfied
  --> src/main.rs:44:5
   |
44 |     upcast(y)
   |     ^^^^^^ the trait `for<'a> IsCovariant<'a>` is not implemented for `<_ as Yokeable<'a>>::Output`
   |
note: required by a bound in `upcast`
  --> src/main.rs:21:42
   |
19 | fn upcast<Y>(x: Yoke<Y>) -> Yoke<Box<dyn IsCovariant<'static> + 'static>> where
   |    ------ required by a bound in this
20 |     Y: for<'a> Yokeable<'a>,
21 |     for<'a> <Y as Yokeable<'a>>::Output: IsCovariant<'a>
   |                                          ^^^^^^^^^^^^^^^ required by this bound in `upcast`

which is incorrect, that bound is satisfied here.

I'm currently working on rustc master (d914f17) so that I can have the fix for #90638, though that fix is not necessary for the commented-out version of my code to work. This should be available on nightly soon.

cc @jackh726 @eddyb

[jackh726]

😔 always another HRTB issue

Based on the trait `for<'a> IsCovariant<'a>` is not implemented for `<_ as Yokeable<'a>>::Output, I would guess that it's similar to other issues that I've seen that we start typechecking using "some variable _", then only later unify with Yoke<Cow<'static, str>>.

[Manishearth]

@jackh726 yeah, sorry 😅

But that diagnosis makes sense

[as-com]

I think I just ran into this issue:
Does not compile: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=a1db6019612c877787c1605d4ff2b9b5

trait SomeOtherTrait<'a> {
    fn create(string: &'a mut str) -> Self;
}

trait SomeTrait<'a> {
    type Associated;

    fn do_stuff(&self, other: &mut Self::Associated);
}

fn something_else<T>(v: T)
where
    for<'b> T: SomeTrait<'b>,
    for<'b> <T as SomeTrait<'b>>::Associated: SomeOtherTrait<'b>,
{
    let mut message = "Hello".to_string();

    {
        let evil_borrow = <T::Associated as SomeOtherTrait<'_>>::create(message.as_mut_str());
    }
}

struct FooAssociated<'a> {
    blah: &'a str,
}
impl<'a> SomeOtherTrait<'a> for FooAssociated<'a> {
    fn create(string: &'a mut str) -> Self {
        Self { blah: string }
    }
}

struct Foo {}
impl<'a> SomeTrait<'a> for Foo {
    type Associated = FooAssociated<'a>;

    fn do_stuff(&self, other: &mut Self::Associated) {
        // ...
    }
}

fn foo(x: Foo) {
    something_else(x);
}

Compiles: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=0e5caed73c4c9502cab948bec7ccdda9

For those who stumble upon this, I found this workaround that may or may not be applicable to your situation: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=f4b1074af9207306222d37d2ed5a317f (create another trait with the desired associated type bounds and a blanket impl)

trait SomeTraitWithOtherAssociated<'a> {
    type Associated: SomeOtherTrait<'a>;
}

impl<'a, T: SomeTrait<'a>> SomeTraitWithOtherAssociated<'a> for T
where
    for<'b> <T as SomeTrait<'b>>::Associated: SomeOtherTrait<'b>,
{
    type Associated = <T as SomeTrait<'a>>::Associated;
}

fn something_else<T>(v: T)
where
    for<'b> T: SomeTraitWithOtherAssociated<'b>,
{
    // ...

[QuineDot]

I'd like to mention another use-case where this issue (as I understand it) comes up.

Sometimes, people want to write a HRTB for Fn-implementing types that return things which borrow from the inputs. So they attempt something like

fn choose_randomly<It>(
    game: &mut GameState,
    generator: impl FnOnce(&GameState) -> It,
) -> Option<It::Item>
where
    It: Iterator,

But this doesn't work because It must be a single type. The workaround on stable is a GAT-emulating helper trait so you can do something like this instead:

fn choose_randomly<G, Item>(
    game: &mut GameState,
    generator: G,
) -> Option<Item>
where
    for<'any> G: GeneratesIterator<'any, Item=Item>,

Conceptually, you shouldn't need this, because the outputs of the Fn traits are associated types -- they're outputs of the implementation as well, so you shouldn't have to mention them directly. (You need the workaround on stable because the Fn trait sugar turns to salt by forcing you to name the output type.) But if you use the unboxed_closures feature on nightly, you run into what I assume in this issue:

fn choose_randomly<G, Item>(
    game: &mut GameState,
    generator: G,
) -> Option<Item>
where
    for<'any> G: FnOnce<(&'any GameState,)>,
    for<'any> <G as FnOnce<(&'any GameState,)>>::Output: Iterator<Item = Item> + 'any,

➡️

error[[E0277]](https://doc.rust-lang.org/nightly/error-index.html#E0277): `<_ as FnOnce<(&'any GameState,)>>::Output` is not an iterator
  --> src/main.rs:43:13
   |
43 |     let _ = choose_randomly/*::<LeSigh, _>*/(&mut game, legal_actions::evaluate as _);
   |             ^^^^^^^^^^^^^^^ `<_ as FnOnce<(&'any GameState,)>>::Output` is not an iterator
   |
   = help: the trait `for<'any> Iterator` is not implemented for `<_ as FnOnce<(&'any GameState,)>>::Output`
note: required by a bound in `choose_randomly`
  --> src/main.rs:27:58
   |
21 | fn choose_randomly<G, Item>(
   |    --------------- required by a bound in this
...
27 |     for<'any> <G as FnOnce<(&'any GameState,)>>::Output: Iterator<Item = Item> + 'any,
   |

You can't name closures or function items, so the workaround of being explicit about the type is not ideal.

I didn't keep the playground handy, but with the stable workaround, if you don't thread enough associated types like Item together, you still hit normalization or inference limitations, which is probably related. I can try to recreate it if desired.

Recent URLO issue 1

Recent URLO issue 2

[estebank]

Current output

error[E0277]: the trait bound `for<'a> <_ as Yokeable<'a>>::Output: IsCovariant<'a>` is not satisfied
  --> src/main.rs:44:5
   |
44 |     upcast(y)
   |     ^^^^^^ the trait `for<'a> IsCovariant<'a>` is not implemented for `<_ as Yokeable<'a>>::Output`
   |
   = help: the trait `IsCovariant<'a>` is implemented for `std::borrow::Cow<'a, T>`
note: required by a bound in `upcast`
  --> src/main.rs:21:42
   |
19 | fn upcast<Y>(x: Yoke<Y>) -> Yoke<Box<dyn IsCovariant<'static> + 'static>> where
   |    ------ required by a bound in this
20 |     Y: for<'a> Yokeable<'a>,
21 |     for<'a> <Y as Yokeable<'a>>::Output: IsCovariant<'a>
   |                                          ^^^^^^^^^^^^^^^ required by this bound in `upcast`