Unrecognized associated type bound on another associated type

[kvark]

trait Bar<T> { fn dummy(&self); }
trait Car<T> { fn dummy(&self); }

trait Foo {
    type A;
    type B: Bar<Self::A>;
    type C: Car<Self::A>;

    fn get_b(&self) -> &Self::B;
}

fn test_bar<A, B: Bar<A>>(_: &B) {}

fn test<A, F: Foo<A=A>>(f: &F) {
    test_bar(f.get_b());
}

Gives me:

<anon>:15:16: 15:23 error: the trait `Bar<A>` is not implemented for the type `<F as Foo>::B` [E0277]
<anon>:15     test_bar(f.get_b());
                         ^~~~~~~
<anon>:15:16: 15:23 error: the trait `Car<A>` is not implemented for the type `<F as Foo>::C` [E0277]
<anon>:15     test_bar(f.get_b());
                         ^~~~~~~
error: aborting due to 2 previous errors
playpen: application terminated with error code 101

There is a workaround:

fn test<A, B: Bar<A>, C: Car<A>, F: Foo<A=A, B=B, C=C>>(f: &F) {
    test_bar(f.get_b());
}

But it's ugly and should not be necessary.

We hit this problem a lot with gfx::Device, and I'd like to see cleaner use of it without explicit CommandBuffer bounds that we use as a workaround.

[apasel422]

This may be related to #23481.

[Mark-Simulacrum]

Edited original post to remove PhantomFn bounds, they're no longer needed. Issue still reproduces:

error[E0277]: the trait bound `<F as Foo>::B: Bar<A>` is not satisfied
  --> test.rs:14:1
   |
14 | / fn test<A, F: Foo<A=A>>(f: &F) {
15 | |     test_bar(f.get_b());
16 | | }
   | |_^ the trait `Bar<A>` is not implemented for `<F as Foo>::B`
   |
   = help: consider adding a `where <F as Foo>::B: Bar<A>` bound
   = note: required by `Foo`

error[E0277]: the trait bound `<F as Foo>::C: Car<A>` is not satisfied
  --> test.rs:14:1
   |
14 | / fn test<A, F: Foo<A=A>>(f: &F) {
15 | |     test_bar(f.get_b());
16 | | }
   | |_^ the trait `Car<A>` is not implemented for `<F as Foo>::C`
   |
   = help: consider adding a `where <F as Foo>::C: Car<A>` bound
   = note: required by `Foo`

error: aborting due to 2 previous errors

[rkarp]

A lot of related issues for this have been opened over time.

Duplicates: #37808, #39532, #40093, #48674, #54375, #54844

Probably same underlying cause: #32722, #37883, #38917, #43475, #47897, #54149

There's also a related discussion on the Rust forums: https://users.rust-lang.org/t/bounds-on-associated-types-enforced-too-soon/12948

[nikomatsakis]

Mildly simplified:

trait Bar<T> { fn dummy(&self); }

trait Foo {
    type A;
    type B: Bar<Self::A>;

    fn get_b(&self) -> &Self::B;
}

fn test_bar<A, B: Bar<A>>(_: &B) {}

fn test<A, F: Foo<A=A>>(f: &F) {
    test_bar(f.get_b());
}

fn main() { }

So, probably the fix is "just" that we need to do some normalization somewhere or other. My preference is to fix this by moving over to lazy normalization and chalk, which will do away with these sorts of shortcomings for good. But it's probably worth looking to see if this can be fixed a touch more rapidly by adding a normalization in the right place. I'll try to do that in a bit and mentor/open a fix if it seems reasonable.

[malbarbo]

Any progress here @nikomatsakis?

[ZerothLaw]

Looks like the issue is known and mentioned at this line: https://github.com/rust-lang/rust/blob/master/src/librustc_typeck/check/compare_method.rs#L252

This indicates this may be the area to check in when working on this? Still working on understanding a lot of this code, so I'm not sure.

[daboross]

Ran into this as well. Here's my minimal test case:

trait Bar<T> {}
trait Caz {
    type A;
    type B: Bar<Self::A>;
}

fn test<T, U>() where T: Caz, U: Caz<A = T::A> {}

error[E0277]: the trait bound `<U as Caz>::B: Bar<<T as Caz>::A>` is not satisfied
 --> src/main.rs:7:1
  |
7 | fn test<T, U>() where T: Caz, U: Caz<A = T::A> {}
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `Bar<<T as Caz>::A>` is not implemented for `<U as Caz>::B`
  |
  = help: consider adding a `where <U as Caz>::B: Bar<<T as Caz>::A>` bound
note: required by `Caz`
 --> src/main.rs:2:1
  |
2 | trait Caz {
  | ^^^^^^^^^

[elidupree]

I've just run into this issue in one of my own projects, and reduced it to a test case that's even simpler than the last one:

trait Bar<T> {}
trait Caz {
    type A;
    type B: Bar<Self::A>;
}
fn test<T: Caz<A = ()>>() {}

Although it compiles successfully if you add the bizarrely-tautological-looking where T::B: Bar<T::A>.

For now, I'm stuck with adding the where clause, but that's putting a LOT of boilerplate in my code (the actual where clause is 71 characters long and appears in dozens of places, including being de-facto required in code that uses my library, not just inside the library itself). Is there any progress on this?

[estebank]

Current output:

error[E0277]: the trait bound `<F as Foo>::B: Bar<A>` is not satisfied
  --> src/lib.rs:14:1
   |
4  |   trait Foo {
   |   --------- required by `Foo`
...
14 |   fn test<A, F: Foo<A=A>>(f: &F) {
   |   ^                             - help: consider further restricting the associated type: `where <F as Foo>::B: Bar<A>`
   |  _|
   | |
15 | |     test_bar(f.get_b());
16 | | }
   | |_^ the trait `Bar<A>` is not implemented for `<F as Foo>::B`

error[E0277]: the trait bound `<F as Foo>::C: Car<A>` is not satisfied
  --> src/lib.rs:14:1
   |
4  |   trait Foo {
   |   --------- required by `Foo`
...
14 |   fn test<A, F: Foo<A=A>>(f: &F) {
   |   ^                             - help: consider further restricting the associated type: `where <F as Foo>::C: Car<A>`
   |  _|
   | |
15 | |     test_bar(f.get_b());
16 | | }
   | |_^ the trait `Car<A>` is not implemented for `<F as Foo>::C`

Applying the suggestions makes the code compile.

Edit: updated output:

error[E0277]: the trait bound `<F as Foo>::B: Bar<A>` is not satisfied
  --> src/lib.rs:14:15
   |
4  | trait Foo {
   |       --- required by a bound in this
5  |     type A;
6  |     type B: Bar<Self::A>;
   |             ------------ required by this bound in `Foo`
...
14 | fn test<A, F: Foo<A=A>>(f: &F) {
   |               ^^^^^^^^ the trait `Bar<A>` is not implemented for `<F as Foo>::B`
   |
help: consider further restricting the associated type
   |
14 | fn test<A, F: Foo<A=A>>(f: &F) where <F as Foo>::B: Bar<A> {
   |                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^

error[E0277]: the trait bound `<F as Foo>::C: Car<A>` is not satisfied
  --> src/lib.rs:14:15
   |
4  | trait Foo {
   |       --- required by a bound in this
...
7  |     type C: Car<Self::A>;
   |             ------------ required by this bound in `Foo`
...
14 | fn test<A, F: Foo<A=A>>(f: &F) {
   |               ^^^^^^^^ the trait `Car<A>` is not implemented for `<F as Foo>::C`
   |
help: consider further restricting the associated type
   |
14 | fn test<A, F: Foo<A=A>>(f: &F) where <F as Foo>::C: Car<A> {
   |                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^

---

Niko's minimized version:

error[E0277]: the trait bound `<F as Foo>::B: Bar<A>` is not satisfied
  --> src/main.rs:12:1
   |
3  |   trait Foo {
   |   --------- required by `Foo`
...
12 |   fn test<A, F: Foo<A=A>>(f: &F) {
   |   ^                             - help: consider further restricting the associated type: `where <F as Foo>::B: Bar<A>`
   |  _|
   | |
13 | |     test_bar(f.get_b());
14 | | }
   | |_^ the trait `Bar<A>` is not implemented for `<F as Foo>::B`

---

@daboross' case:

error[E0277]: the trait bound `<U as Caz>::B: Bar<<T as Caz>::A>` is not satisfied
 --> src/lib.rs:7:1
  |
2 | trait Caz {
  | --------- required by `Caz`
...
7 | fn test<T, U>() where T: Caz, U: Caz<A = T::A> {}
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^-^^
  | |                                             |
  | |                                             help: consider further restricting the associated type: `, <U as Caz>::B: Bar<<T as Caz>::A>`
  | the trait `Bar<<T as Caz>::A>` is not implemented for `<U as Caz>::B`

Update: this case now compiles.

---

In call cases applying the suggestions fulfill the requirements.

[dignifiedquire]

@nikomatsakis any update on this? Is there anything I can do help with this? I'd be happy and try to help where I can, as this is blocking a lot of nice usages of typenum for me at the moment.

[daboross]

It looks like this compiles under -Z chalk, or at least the bounds compile. The body function complains about inference, but I'm inclined to think that's just a chalk bug / missing feature and unrelated to this issue.

Given that, the solution might just be fully stable chalk integration. If it is, then this issue would fall into the same bucket as features like implied bounds, where there isn't a lot we can do outside of just pushing chalk integration.

[nikomatsakis]

I think my original analysis is still correct. I think the normalizing is missing here:

rust/src/librustc_trait_selection/traits/select/mod.rs

Line 1295 in ff4a253

let bounds = predicates_of.instantiate(self.tcx(), substs);

After we invoke instantiate, we should also be normalizing, probably kind of like this

rust/src/librustc_trait_selection/traits/select/mod.rs

Lines 1855 to 1863 in ff4a253

	let Normalized { value: impl_trait_ref, obligations: mut nested_obligations } =
	ensure_sufficient_stack(|| {
	project::normalize_with_depth(
	self,
	obligation.param_env,
	obligation.cause.clone(),
	obligation.recursion_depth + 1,
	&impl_trait_ref,
	)

If Chalk solves this, it is probably because of lazy normalization.

[estebank]

All of the cases I mentioned now compile. I believe this can be closed by adding tests.