Repository: rust
Issue: Overflow evaluating requirements when referencing associated type without a type parameter
Labels: A-trait-system,T-compiler,C-bug,T-types,fixed-by-next-solver

This code fails to compile on stable (1.41.0), beta (1.42.0-beta.3), and nightly:

```rust
use std::ops::Add;

struct Container<S: Data>(S);

trait Data {
    type Elem;
}

impl<A> Data for Vec<A> {
    type Elem = A;
}

impl<A, S> Add<Container<S>> for f32
where
    f32: Add<A, Output=A>,
    S: Data<Elem=A>,
{
    type Output = Container<S>;
    fn add(self, _rhs: Container<S>) -> Container<S> {
        unimplemented!()
    }
}

impl<'a, A, S> Add<&'a Container<S>> for f32
where
      f32: Add<A>,
      S: Data<Elem=A>,
{
    type Output = Container<Vec<<f32 as Add<A>>::Output>>;
    fn add(self, _rhs: &Container<S>) -> Self::Output {
        unimplemented!()
    }
}

fn main() {}
```

([playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0b20b5a0031756e51ca72df4489526d1))

with the following error messages:

```
error[E0275]: overflow evaluating the requirement `f32: std::ops::Add<Container<_>>`
  --> src/main.rs:24:16
   |
24 | impl<'a, A, S> Add<&'a Container<S>> for f32
   |                ^^^^^^^^^^^^^^^^^^^^^
   |
   = help: consider adding a `#![recursion_limit="256"]` attribute to your crate
   = note: required because of the requirements on the impl of `std::ops::Add<Container<_>>` for `f32`
   = note: required because of the requirements on the impl of `std::ops::Add<Container<_>>` for `f32`
   = note: required because of the requirements on the impl of `std::ops::Add<Container<_>>` for `f32`
   [...]
   = note: required because of the requirements on the impl of `std::ops::Add<Container<_>>` for `f32`
   = note: required because of the requirements on the impl of `std::ops::Add<Container<_>>` for `f32`

error[E0275]: overflow evaluating the requirement `f32: std::ops::Add<Container<_>>`
  --> src/main.rs:30:5
   |
30 | /     fn add(self, _rhs: &Container<S>) -> Self::Output {
31 | |         unimplemented!()
32 | |     }
   | |_____^
   |
   = help: consider adding a `#![recursion_limit="256"]` attribute to your crate
   = note: required because of the requirements on the impl of `std::ops::Add<Container<_>>` for `f32`
   = note: required because of the requirements on the impl of `std::ops::Add<Container<_>>` for `f32`
   = note: required because of the requirements on the impl of `std::ops::Add<Container<_>>` for `f32`
   [...]
   = note: required because of the requirements on the impl of `std::ops::Add<Container<_>>` for `f32`
   = note: required because of the requirements on the impl of `std::ops::Add<Container<_>>` for `f32`
```

I expected it to compile without errors. Adding a type parameter for the type `<f32 as Add<A>>::Output` fixes the issue. In other words, this equivalent code compiles without errors:

```rust
use std::ops::Add;

struct Container<S: Data>(S);

trait Data {
    type Elem;
}

impl<A> Data for Vec<A> {
    type Elem = A;
}

impl<A, S> Add<Container<S>> for f32
where
    f32: Add<A, Output=A>,
    S: Data<Elem=A>,
{
    type Output = Container<S>;
    fn add(self, _rhs: Container<S>) -> Container<S> {
        unimplemented!()
    }
}

// See the type `B` here.
impl<'a, A, S, B> Add<&'a Container<S>> for f32
where
      f32: Add<A, Output = B>,
      S: Data<Elem=A>,
{
    type Output = Container<Vec<B>>;
    fn add(self, _rhs: &Container<S>) -> Self::Output {
        unimplemented!()
    }
}

fn main() {}
```

([playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=d0815f4f20342c69ff611054c0236eaa))

Maybe the compiler is over-eager in evaluating the `<f32 as Add<A>>::Output` type expression, but using a type parameter instead set equal to that type prevents the compiler from going too far?

### Meta

Tested using the Rust playground.

* stable: 1.41.0
* beta: 1.42.0-beta.3 (2020-02-07 86f329b419dbac59da59)
* nightly: 1.43.0-nightly (2020-02-15 61d9231ff2604a046798)