Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
Manishearth opened this issue Nov 16, 2021 · 7 comments
Open

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

Manishearth opened this issue Nov 16, 2021 · 7 comments
Labels
A-higher-ranked Area: Higher-ranked things (e.g., lifetimes, types, trait bounds aka HRTBs) A-lifetimes Area: Lifetimes / regions C-bug Category: This is a bug. fixed-by-next-solver Fixed by the next-generation trait solver, `-Znext-solver`. S-bug-has-test Status: This bug is tracked inside the repo by a `known-bug` test. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.

Comments

@Manishearth
Copy link
Member

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.

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

@Manishearth Manishearth added A-lifetimes Area: Lifetimes / regions T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. C-bug Category: This is a bug. labels Nov 16, 2021
@jackh726
Copy link
Member

😔 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
Copy link
Member Author

@jackh726 yeah, sorry 😅

But that diagnosis makes sense

@as-com
Copy link
Contributor

as-com commented Jan 8, 2022

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
Copy link

QuineDot commented Jun 7, 2022

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
Copy link
Contributor

estebank commented Jul 7, 2022

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`

@jackh726 jackh726 added the S-has-mcve Status: A Minimal Complete and Verifiable Example has been found for this issue label Oct 31, 2022
Manishearth added a commit to Manishearth/rust that referenced this issue Nov 14, 2022
…imulacrum

Add a few known-bug tests

The labels of these tests should be changed from `S-bug-has-mcve` to `S-bug-has-test` once this is merged.

cc:
rust-lang#101518
rust-lang#99492
rust-lang#90950
rust-lang#89196
rust-lang#104034
rust-lang#101350
rust-lang#103705
rust-lang#103899

I couldn't reproduce the failures in rust-lang#101962 and rust-lang#100772 (so either these have started passing, or I didn't repro properly), so leaving those out for now.

rust-lang#102065 was a bit more complicated, since it uses `rustc_private` and I didn't want to mess with that.
@jackh726 jackh726 added S-bug-has-test Status: This bug is tracked inside the repo by a `known-bug` test. and removed S-has-mcve Status: A Minimal Complete and Verifiable Example has been found for this issue labels Nov 14, 2022
@steffahn
Copy link
Member

I’ve only tested the first two examples, but this hasn’t been mentioned here yet – the code examples compile successfully if the type argument is specified explicitly, e.g. calling upcast::<Cow<'_, _>>(y) instead of upcast(y) in the first playground, or calling something_else::<Foo>(x) instead of something_else(x) in the second playground.

@compiler-errors compiler-errors added the fixed-by-next-solver Fixed by the next-generation trait solver, `-Znext-solver`. label Aug 15, 2023
@Ddystopia
Copy link
Contributor

That code fails to compile:

struct Opaque;

trait FromRef<'r>: 'r {
    fn from_ref(_: &'r Opaque) -> Self;
}

struct Bar<'r>(&'r Opaque);

impl<'r> FromRef<'r> for Bar<'r> {
    fn from_ref(op: &'r Opaque) -> Self {
        Bar(op)
    }
}

trait Foo<I, O> {
    fn call_foo(&self, op: &Opaque);
}

impl<I: for<'r> FromRef<'r>, O, H: Fn(I) -> O> Foo<I, O> for H {
    fn call_foo(&self, op: &Opaque) {
        let i = I::from_ref(op);
        let _: O = self(i);
    }
}

struct FooImpl;

impl<I: for<'r> FromRef<'r>> Foo<I, ()> for FooImpl {
    fn call_foo(&self, op: &Opaque) {
        let _ = I::from_ref(op);
    }
}

fn asserted<'r>(_: Bar<'r>) {}

fn main() {
    let op = Opaque;
    // fails:
    asserted.call_foo(&op);
    // also fails:
    FooImpl.call_foo(&op);
}

While working on another code from picoserve I got such note, which guided me here. If this is not the right place, please guide me to elsewhere

image

@fmease fmease added the A-higher-ranked Area: Higher-ranked things (e.g., lifetimes, types, trait bounds aka HRTBs) label Sep 24, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-higher-ranked Area: Higher-ranked things (e.g., lifetimes, types, trait bounds aka HRTBs) A-lifetimes Area: Lifetimes / regions C-bug Category: This is a bug. fixed-by-next-solver Fixed by the next-generation trait solver, `-Znext-solver`. S-bug-has-test Status: This bug is tracked inside the repo by a `known-bug` test. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

9 participants