HKTB reasoning on associated type

I was surprised to find out that this doesn't compile:

use std::marker::PhantomData;

trait MyTrait {
    type Assoc;
}

struct Foo { }

struct Bar<'a> { _phantom: PhantomData<&'a u64> }

trait Marker { }

impl<'a> Marker for Bar<'a> { }

impl<'a> MyTrait for &'a Foo {
    type Assoc = Bar<'a>;
}

struct Gen<T> { _phantom: PhantomData<T> }

impl<T> Gen<T> where
        for<'a> &'a T: MyTrait,
        for<'a> <&'a T as MyTrait>::Assoc: Marker {
    fn new() -> Self { Gen { _phantom: PhantomData } }
}

fn main() {
    let x: Gen<Foo> = Gen::new();
}

(Playground)

And gets the following error:

error[E0599]: no function or associated item named `new` found for struct `Gen<_>` in the current scope
  --> src/main.rs:28:28
   |
19 | struct Gen<T> { _phantom: PhantomData<T> }
   | ------------- function or associated item `new` not found for this
...
28 |     let x: Gen<Foo> = Gen::new();
   |                            ^^^ function or associated item not found in `Gen<_>`
   |
   = note: the method `new` exists but the following trait bounds were not satisfied:
           `<&'a _ as MyTrait>::Assoc: Marker`

Even though the Marker trait is implemented for Bar with any lifetime parameter, and <&Foo as MyTrait>::Assoc is always a Bar. What am I missing?

The original example was with implementing IntoIterator on a &Foo, and trying to bound the <&Foo as IntoIterator>::Item, but I would expect the inference to work here as well.

I think this is just a limitation of traits, I think it will get resolved once chalk (the new traits solver) lands.

Then should I "report" it somewhere as another thing to make sure that works? On chalk / rustc repo?

I would report it on the rustc repo.

btw, I found a workaround, using an additional trait. https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=4a39dc571f3da6fdf39179dd01ca934f

This leads me to believe that this is likely a bug.

edit: seems related

1 Like

Thanks, cool workaround! I have to check if it solves my original problem, but this seems versatile enough to do so.

I think the workaround in the related link is along the same lines. It's useful to know these kind of tricks :slight_smile:

Anyway, I will also report it on rustc. Edit: https://github.com/rust-lang/rust/issues/73107

I suspect this is sufficiently Chalk-adjacent that it might be worthwhile to try compiling on nightly with -Z chalk and make a note of whether the compiler accepts it, rejects it or crashes with an error message.

3 Likes

I wasn't aware it was that easy to compile with chalk :slight_smile: I already reported it, but will attempt to compile this with chalk next time I'm on the computer. Thanks!

The compiler crashes with "not implemented", so I guess there's still some mileage there...

1 Like

It seems your workaround doesn't work after all... It finds the right type, but somehow that's not enough to convince the compiler that the constraint always holds, so methods from the trait in the constraint still can't be used on the associated type:
https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=2dd048f96050163dddbf87784e84b00e

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

I think that the workaround enables the compiler to check that the concrete type supplied fulfills the bounds, and therefore the impl block applies to it; however it still doesn't let the compiler reason about the code inside that block, and really understand that the types inside it always have the bounds applying to them.

I believe this is showing the compiler's lack of support for implied bounds?

Specifically, in this definition:

trait NewCheck: MyTrait where Self::Assoc: Marker {

Rust understands that for any T, if T: NewCheck, then it should be assumed that T: MyTrait. But this is currently special cased for trait bounds, and the same thing doesn't happen for the where clauses.

It would be ideal if T: NewCheck implied T::Assoc: Marker. But support for this is still gated on chalk integration (as many other trait features are).

See the traits section of the implied bounds RFC - it shows a very similar thing which similarly doesn't compile.

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.