Trait bounds on associated type projections via HRTB are broken

[sfackler]

I believe this should successfully compile, but it currently fails claiming that vec's iterator isn't ExactSizeIterator:

fn foo<T>(t: T) -> usize
where
    for<'a> &'a T: IntoIterator,
    for<'a> <&'a T as IntoIterator>::IntoIter: ExactSizeIterator,
{
    t.into_iter().len()
}

fn main() {
    foo::<Vec<u32>>(vec![]);
}

error[E0277]: the trait bound `for<'a> <&'a std::vec::Vec<u32> as std::iter::IntoIterator>::IntoIter: std::iter::ExactSizeIterator` is not satisfied
  --> src/main.rs:10:5
   |
10 |     foo::<Vec<u32>>(vec![]);
   |     ^^^^^^^^^^^^^^^ the trait `for<'a> std::iter::ExactSizeIterator` is not implemented for `<&'a std::vec::Vec<u32> as std::iter::IntoIterator>::IntoIter`
   |
   = help: the following implementations were found:
             <&'a mut I as std::iter::ExactSizeIterator>
note: required by `foo`
  --> src/main.rs:1:1
   |
1  | / fn foo<T>(t: T) -> usize
2  | | where
3  | |     for<'a> &'a T: IntoIterator,
4  | |     for<'a> <&'a T as IntoIterator>::IntoIter: ExactSizeIterator,
5  | | {
6  | |     t.into_iter().len()
7  | | }
   | |_^

error: aborting due to previous error

For more information about this error, try `rustc --explain E0277`.

Things compile correctly if the bounds are changed to T rather than for<'a> &'a T.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=c96139308ad1602c281e71c4c54c73ec

[Centril]

It does seem like it should compile... cc @rust-lang/wg-traits

[jonhoo]

Another instance of this from #57671:

trait Bar<T> {
    type Assoc;
}
impl<'a> Bar<&'a ()> for () {
    type Assoc = Box<Send>;
}

fn oops<C>()
where
    for<'a> C: Bar<&'a ()>,
    for<'a> <C as Bar<&'a ()>>::Assoc: Send,
{
}

fn main() {
    oops::<()>();
}

fails with

error[E0277]: `<() as Bar<&'a ()>>::Assoc` cannot be sent between threads safely
  --> src/lib.rs:16:5
   |
16 |     oops::<()>();
   |     ^^^^^^^^^^ `<() as Bar<&'a ()>>::Assoc` cannot be sent between threads safely
   |
   = help: the trait `for<'a> std::marker::Send` is not implemented for `<() as Bar<&'a ()>>::Assoc`
note: required by `oops`
  --> src/lib.rs:8:1
   |
8  | / fn oops<C>()
9  | | where
10 | |     for<'a> C: Bar<&'a ()>,
11 | |     for<'a> <C as Bar<&'a ()>>::Assoc: Send,
12 | | {
13 | | }
   | |_^

[jonhoo]

@sfackler do you know of a workaround for this bug? It's currently blocking me and I'm not entirely sure how else to structure my code.

[sfackler]

The only workaround I know of is to remove the lifetime parameter

On Thu, Jan 17, 2019 at 10:02 AM Jon Gjengset ***@***.***> wrote: @sfackler <https://github.com/sfackler> do you know of a workaround for this bug? It's currently blocking me and I'm not entirely sure how else to structure my code. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#56556 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABY2UW0Y2cj6SRaHA6WUrpeo6C4gM1jLks5vELqegaJpZM4ZF3D3> .

-- Steven Fackler

[devyn]

I believe this issue I ran in to might be related - StackOverflow.

I was trying to put a bound on an associated type Key from two different types and require them to be PartialOrd, but Rust always just wanted to assume the types must be the same. By creating a separate trait KeyedCmp that is implemented without relying on an HRTB, and then using the HRTB around that trait, it did compile. I'm fairly sure this is a bug. rustc ought to still be able to resolve what the associated type actually is and then evaluate traits on that. It seems like it's trying to look for implementations on a hypothetical associated type black box rather than the real type it points to.

[Lucretiel]

Another example, when trying to bind for <'a> <&'a C as IntoIterator>::Item: Display:

https://stackoverflow.com/questions/53364798/why-does-the-compiler-claim-that-a-generic-doesnt-implement-display-even-thou

[Lucretiel]

Ran into this in one of my own projects, and used this odd workaround (suggested on satck overflow): https://github.com/Lucretiel/joinery/blob/master/src/join.rs#L174-L188

[roosmaa]

Another variation of this issue (as far as I can tell):

trait Bar<'a> {
    type Assoc;
}

impl<'a> Bar<'a> for () {
    type Assoc = ();
}

fn oops<C>()
where
    for<'a> C: Bar<'a>,
    for<'a> <C as Bar<'a>>::Assoc: Send,
{
}

fn main() {
    oops::<()>();
}

Fails with:

error[E0277]: `<() as Bar<'a>>::Assoc` cannot be sent between threads safely
  --> src/main.rs:17:5
   |
9  | fn oops<C>()
   |    ---- required by a bound in this
...
12 |     for<'a> <C as Bar<'a>>::Assoc: Send,
   |                                    ---- required by this bound in `oops`
...
17 |     oops::<()>();
   |     ^^^^^^^^^^ `<() as Bar<'a>>::Assoc` cannot be sent between threads safely
   |
   = help: the trait `for<'a> std::marker::Send` is not implemented for `<() as Bar<'a>>::Assoc`

[H2CO3]

I just ran into this (playground):

#[derive(Clone, Copy, Debug)]
struct Value<'a> {
    num: NonZeroU64,
    marker: PhantomData<&'a ()>,
}

impl<'a> TryFrom<u64> for Value<'a> {
    type Error = TryFromIntError;
    
    fn try_from(value: u64) -> Result<Self, Self::Error> {
        NonZeroU64::try_from(value).map(|num| Value { num, marker: PhantomData })
    }
}

trait ToValue {
    fn to_value(&self) -> Result<Value, ValueError>;
}

#[derive(Clone, Copy, Default, Debug)]
struct ValueError;

impl From<TryFromIntError> for ValueError {
    fn from(_: TryFromIntError) -> Self {
        ValueError
    }
}

impl<T> ToValue for T
    where
        T: Clone,
        T: for<'a> TryInto<Value<'a>>,
        ValueError: for<'a> From<<T as TryInto<Value<'a>>>::Error>,
{
    fn to_value(&self) -> Result<Value, ValueError> {
        self.clone().try_into().map_err(Into::into)
    }
}

fn main() {
    let v: Value = 42_u64.to_value().unwrap();
    println!("{:#?}", v);
}

I get the following error on latest stable (1.52.1):

error[E0599]: the method `to_value` exists for type `u64`, but its trait bounds were not satisfied
  --> src/main.rs:44:27
   |
24 | struct ValueError;
   | ------------------ doesn't satisfy `_: From<<u64 as TryInto<Value<'a>>>::Error>`
...
44 |     let v: Value = 42_u64.to_value().unwrap();
   |                           ^^^^^^^^ method cannot be called on `u64` due to unsatisfied trait bounds
   |
   = note: the following trait bounds were not satisfied:
           `ValueError: From<<u64 as TryInto<Value<'a>>>::Error>`
           which is required by `u64: ToValue`

The workaround in my case was to pull out the associated type into a type parameter, and require that it be invariant w.r.t. the universally quantified lifetime parameter (playground):

impl<T, E> ToValue for T
    where
        T: Clone,
        T: for<'a> TryInto<Value<'a>, Error = E>,
        ValueError: From<E>,
{
    fn to_value(&self) -> Result<Value, ValueError> {
        self.clone().try_into().map_err(Into::into)
    }
}

[jackh726]

Fixed by #85499, marking as needs-test because wasn't an ICE and a simple enough example I'd like to have a test for.

[sffc]

This bug might not be completely fixed. Here is another test case that still fails on nightly and beta:

https://play.rust-lang.org/?version=beta&mode=debug&edition=2018&gist=c50c84aede1fad33bfac1238424a7c2a

EDIT: Made the case a bit smaller:

https://play.rust-lang.org/?version=beta&mode=debug&edition=2018&gist=025e2d4cefe09821650352a935b0baed

[fee1-dead]

this is the smallest example I can find:

This below works:

fn test<T>()
where
    for<'a> &'a T: IntoIterator,
    for<'a> <&'a T as IntoIterator>::IntoIter: Clone,
{
}

fn main() {
    test::<Vec<u8>>();
}

While this doesn't:

use std::ops::Deref;

fn test<T, TDeref>()
where
    T: Deref<Target = TDeref>,
    TDeref: ?Sized,
    for<'a> &'a TDeref: IntoIterator,
    for<'a> <&'a TDeref as IntoIterator>::IntoIter: Clone,
{
}

fn main() {
    test::<Vec<u8>, _>();
}

@jackh726 Can you confirm that the second case works in your PR as well?

[fee1-dead]

this is still not fixed on latest nightly.

cc @jackh726

EDIT: I suspect that this example is some form of #89196.

[Manishearth]

Another bug of this kind: #90950