Repository: rust
Issue: Incorrect trait bound resolution in the presence of associated types
Labels: A-trait-system,A-associated-items,T-compiler,C-bug

<!--
Thank you for filing a bug report! 🐛 Please provide a short summary of the bug,
along with any information you feel relevant to replicating the bug.
-->

The following code:

```rust
pub trait Foo<T> {
    type FooType;
}

pub trait Bar {
    type BarType;
}

pub struct ConcreteBar;

impl Bar for ConcreteBar {
    type BarType = ();
}

pub trait Xyzzy<T> {}

pub trait Quux {}

pub struct SomeStruct<S, A>(PhantomData<(S, A)>);

impl<S, A> Quux for SomeStruct<S, A>
where
    A: Foo<<ConcreteBar as Bar>::BarType>,
    <A as Foo<<ConcreteBar as Bar>::BarType>>::FooType: Xyzzy<S>,
{
}
```

produces the following error:

```
error[E0277]: the trait bound `A: Foo<()>` is not satisfied
  --> src/minimal1.rs:23:1
   |
23 | / impl<S, A> Quux for SomeStruct<S, A>
24 | | where
25 | |     A: Foo<<ConcreteBar as Bar>::BarType>,
26 | |     <A as Foo<<ConcreteBar as Bar>::BarType>>::FooType: Xyzzy<S>,
27 | | {
28 | | }
   | |_^ the trait `Foo<()>` is not implemented for `A`
   |
help: consider further restricting this bound
   |
25 |     A: Foo<<ConcreteBar as Bar>::BarType> + Foo<()>,
   |                                           ^^^^^^^^^
```

In theory, this should compile fine. `ConcreteBar::BarType` is `()`, so the trait bound `A: Foo<<ConcreteBar as Bar>::BarType>` should be equivalent to `A: Foo<()>`.

Changing the first bound to `A: Foo<()>` eliminates the error. Additionally, adding a third type parameter `B` and changing the bounds to the following:

```
B: Bar,
A: Foo<B::BarType>,
<A as Foo<B::BarType>>::FooType: Xyzzy<S>,
```

eliminates the error. However, see the additional context below.

### Meta
<!--
If you're using the stable version of the compiler, you should also check if the
bug also exists in the beta or nightly versions.
-->
This has been tested on the current stable and nightly compilers:
```
rustc 1.47.0 (18bf6b4f0 2020-10-07)
binary: rustc
commit-hash: 18bf6b4f01a6feaf7259ba7cdae58031af1b7b39
commit-date: 2020-10-07
host: x86_64-unknown-linux-gnu
release: 1.47.0
LLVM version: 11.0

rustc 1.49.0-nightly (1eaadebb3 2020-10-21)
binary: rustc
commit-hash: 1eaadebb3dee31669c7649b32747381d11614fae
commit-date: 2020-10-21
host: x86_64-unknown-linux-gnu
release: 1.49.0-nightly
LLVM version: 11.0
```

<!--
Include a backtrace in the code block by setting `RUST_BACKTRACE=1` in your
environment. E.g. `RUST_BACKTRACE=1 cargo build`.
-->

### Additional context

I encountered this issue while working with generic traits from typenum, generic-array, and nalgebra, and in this context the above-mentioned workarounds do not work. Unfortunately I have yet to find an example of this more persistent version of the issue that does not use types and traits from these crates.

<details><summary>Several code and error examples</summary>

```rust
use generic_array::ArrayLength;
use nalgebra::{base::dimension::DimName, ArrayStorage, Vector, U1};
use std::{marker::PhantomData, ops::Mul};
use typenum::Prod;

pub trait Foo {
    type FooType;
}

pub struct SomeStruct<D>(PhantomData<D>);

impl<D> Foo for SomeStruct<D>
where
    D: DimName,
    D::Value: Mul<<U1 as DimName>::Value>,
    Prod<D::Value, <U1 as DimName>::Value>: ArrayLength<f32>,
{
    type FooType = Vector<f32, D, ArrayStorage<f32, D, U1>>;
}
```
```
error[E0277]: cannot multiply `<D as DimName>::Value` by `UInt<UTerm, B1>`
  --> src/using_crates.rs:18:5
   |
18 |     type FooType = Vector<f32, D, ArrayStorage<f32, D, U1>>;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ no implementation for `<D as DimName>::Value * UInt<UTerm, B1>`
   |
  ::: /home/john/.cargo/registry/src/github.com-1ecc6299db9ec823/nalgebra-0.22.1/src/base/array_storage.rs:41:15
   |
41 |     R::Value: Mul<C::Value>,
   |               ------------- required by this bound in `ArrayStorage`
   |
   = help: the trait `Mul<UInt<UTerm, B1>>` is not implemented for `<D as DimName>::Value`
help: consider further restricting the associated type
   |
16 |     Prod<D::Value, <U1 as DimName>::Value>: ArrayLength<f32>, <D as DimName>::Value: Mul<UInt<UTerm, B1>>
   |                                                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
```
(Plus a couple of duplicate errors pointing to different spans.)

Bounding on `Mul<typenum::U1>` directly:

```rust
impl<D> Foo for SomeStruct<D>
where
    D: DimName,
    D::Value: Mul<typenum::U1>,
    Prod<D::Value, <U1 as DimName>::Value>: ArrayLength<f32>,
{
    type FooType = Vector<f32, D, ArrayStorage<f32, D, U1>>;
}
```
```
error[E0277]: the trait bound `<<D as DimName>::Value as Mul<UInt<UTerm, B1>>>::Output: generic_array::ArrayLength<f32>` is not satisfied
  --> src/using_crates.rs:18:5
   |
18 |     type FooType = Vector<f32, D, ArrayStorage<f32, D, U1>>;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `generic_array::ArrayLength<f32>` is not implemented for `<<D as DimName>::Value as Mul<UInt<UTerm, B1>>>::Output`
   |
  ::: /home/john/.cargo/registry/src/github.com-1ecc6299db9ec823/nalgebra-0.22.1/src/base/array_storage.rs:42:31
   |
42 |     Prod<R::Value, C::Value>: ArrayLength<N>,
   |                               -------------- required by this bound in `ArrayStorage`
   |
help: consider further restricting the associated type
   |
16 |     Prod<D::Value, <U1 as DimName>::Value>: ArrayLength<f32>, <<D as DimName>::Value as Mul<UInt<UTerm, B1>>>::Output: generic_array::ArrayLength<f32>
   |                                                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
```

Using the compiler-suggested bound actually leads to it suggesting the exact same bound again:

```rust
impl<D> Foo for SomeStruct<D>
where
    D: DimName,
    D::Value: Mul<typenum::U1>,
    <<D as DimName>::Value as Mul<UInt<UTerm, B1>>>::Output: generic_array::ArrayLength<f32>
{
    type FooType = Vector<f32, D, ArrayStorage<f32, D, U1>>;
}
```
```
error[E0277]: the trait bound `<<D as DimName>::Value as Mul<UInt<UTerm, B1>>>::Output: generic_array::ArrayLength<f32>` is not satisfied
  --> src/using_crates.rs:18:5
   |
18 |     type FooType = Vector<f32, D, ArrayStorage<f32, D, U1>>;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `generic_array::ArrayLength<f32>` is not implemented for `<<D as DimName>::Value as Mul<UInt<UTerm, B1>>>::Output`
   |
  ::: /home/john/.cargo/registry/src/github.com-1ecc6299db9ec823/nalgebra-0.22.1/src/base/array_storage.rs:42:31
   |
42 |     Prod<R::Value, C::Value>: ArrayLength<N>,
   |                               -------------- required by this bound in `ArrayStorage`
   |
help: consider further restricting the associated type
   |
16 |     <<D as DimName>::Value as Mul<UInt<UTerm, B1>>>::Output: generic_array::ArrayLength<f32>, <<D as DimName>::Value as Mul<UInt<UTerm, B1>>>::Output: generic_array::ArrayLength<f32>
   |                                                                                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
```
</details>