Incorrect trait bound resolution in the presence of associated types

[wuggen]

The following code:

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

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

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.

Several code and error examples

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:

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:

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>
   |                                                                                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

[hombit]

I have the same nalgebra problem. Is there any work around?