Repository: rust
Issue: Unable to resolve a recursive trait bound when resolution appears possible
Labels: A-resolve,A-trait-system,T-compiler

I've a code that's unable to resolve a recursive trait bound when resolution appears possible.  The code:

```rust
#![recursion_limit = "10"]

// Create a trait with some methods
pub trait Methods2<Other> {
    type Output;
    fn min(self, other: Other) -> Self::Output;
}

// Create a composite trait that contain multiple traits
trait AllCombos<NonRef>:
    Methods2<NonRef, Output = NonRef>
    + for<'a> Methods2<&'a NonRef, Output = NonRef>
{
}
impl<T, NonRef> AllCombos<NonRef> for T where
    T: Methods2<NonRef, Output = NonRef>
        + for<'a> Methods2<&'a NonRef, Output = NonRef>
{
}

// Implement this trait for f32
impl Methods2<f32> for f32 {
    type Output = f32;
    fn min(self, other: f32) -> Self::Output {
        self.min(other)
    }
}
impl Methods2<f32> for &f32 {
    type Output = f32;
    fn min(self, other: f32) -> Self::Output {
        (*self).min(other)
    }
}
impl Methods2<&f32> for f32 {
    type Output = f32;
    fn min(self, other: &f32) -> Self::Output {
        self.min(*other)
    }
}
impl Methods2<&f32> for &f32 {
    type Output = f32;
    fn min(self, other: &f32) -> Self::Output {
        (*self).min(*other)
    }
}

// Create a struct with a generic float inside
#[derive(Debug)]
struct MyStruct<Float> {
    x: Float,
}

// Implement to Methods2 trait for MyStruct
impl<Float> Methods2<MyStruct<Float>> for MyStruct<Float>
where
    Float: AllCombos<Float>,
    for<'a> &'a Float: AllCombos<Float>,
{
    type Output = MyStruct<Float>;
    fn min(self, other: MyStruct<Float>) -> Self::Output {
        MyStruct::<Float> {
            x: self.x.min(other.x),
        }
    }
}
impl<Float> Methods2<MyStruct<Float>> for &MyStruct<Float>
where
    Float: AllCombos<Float>,
    for<'a> &'a Float: AllCombos<Float>,
{
    type Output = MyStruct<Float>;
    fn min(self, other: MyStruct<Float>) -> Self::Output {
        MyStruct::<Float> {
            x: (&self.x).min(other.x),
        }
    }
}
impl<Float> Methods2<&MyStruct<Float>> for MyStruct<Float>
where
    Float: AllCombos<Float>,
    for<'a> &'a Float: AllCombos<Float>,
{
    type Output = MyStruct<Float>;
    fn min(self, other: &MyStruct<Float>) -> Self::Output {
        MyStruct::<Float> {
            x: self.x.min(&other.x),
        }
    }
}
impl<Float> Methods2<&MyStruct<Float>> for &MyStruct<Float>
where
    Float: AllCombos<Float>,
    for<'a> &'a Float: AllCombos<Float>,
{
    type Output = MyStruct<Float>;
    fn min(self, other: &MyStruct<Float>) -> Self::Output {
        MyStruct::<Float> {
            x: (&self.x).min(&other.x),
        }
    }
}

// Lifts a variable into MyStruct
fn lift<Float>(x: Float) -> MyStruct<Float>
where
    Float: AllCombos<Float>,
    for<'a> &'a Float: AllCombos<Float>,
{
    MyStruct { x }
}

// Create an element
fn main() {
    let bar = lift(4.0_f32).min(lift(2.0_f32));
    //let bar = lift::<f32>(4.0_f32).min(lift::<f32>(2.0_f32));
    println!("{:?}", bar.x);
}
```

produces the compiler error:

```
error[E0275]: overflow evaluating the requirement `&'a MyStruct<_>: Methods2<MyStruct<_>>`
   --> src/test06.rs:116:15
    |
106 | fn lift<Float>(x: Float) -> MyStruct<Float>
    |    ----
...
109 |     for<'a> &'a Float: AllCombos<Float>,
    |                        ---------------- required by this bound in `lift`
...
116 |     let bar = lift(4.0_f32).min(lift(2.0_f32));
    |               ^^^^
    |
    = help: consider adding a `#![recursion_limit="20"]` attribute to your crate
    = note: required because of the requirements on the impl of `for<'a> AllCombos<MyStruct<_>>` for `&'a MyStruct<_>`
    = note: required because of the requirements on the impl of `Methods2<MyStruct<MyStruct<_>>>` for `&'a MyStruct<MyStruct<_>>`
    = note: required because of the requirements on the impl of `for<'a> AllCombos<MyStruct<MyStruct<_>>>` for `&'a MyStruct<MyStruct<_>>`
    = note: required because of the requirements on the impl of `Methods2<MyStruct<MyStruct<MyStruct<_>>>>` for `&'a MyStruct<MyStruct<MyStruct<_>>>`
    = note: required because of the requirements on the impl of `for<'a> AllCombos<MyStruct<MyStruct<MyStruct<_>>>>` for `&'a MyStruct<MyStruct<MyStruct<_>>>`
    = note: required because of the requirements on the impl of `Methods2<MyStruct<MyStruct<MyStruct<MyStruct<_>>>>>` for `&'a MyStruct<MyStruct<MyStruct<MyStruct<_>>>>`
    = note: required because of the requirements on the impl of `for<'a> AllCombos<MyStruct<MyStruct<MyStruct<MyStruct<_>>>>>` for `&'a MyStruct<MyStruct<MyStruct<MyStruct<_>>>>`
    = note: required because of the requirements on the impl of `Methods2<MyStruct<MyStruct<MyStruct<MyStruct<MyStruct<_>>>>>>` for `&'a MyStruct<MyStruct<MyStruct<MyStruct<MyStruct<_>>>>>`
    = note: required because of the requirements on the impl of `for<'a> AllCombos<MyStruct<MyStruct<MyStruct<MyStruct<MyStruct<_>>>>>>` for `&'a MyStruct<MyStruct<MyStruct<MyStruct<MyStruct<_>>>>>`
```

Essentially, the `AllCombos` trait is designed to contain all ref/val combinations for a series of methods that contain two arguments.  The idea is that a user implements `Methods2` four different times for these combinations and then `AllCombos` can be used as the constraint.  Anyway, it's possible to resolve the error by using the fully qualified syntax:

```rust
let bar = lift::<f32>(4.0_f32).min(lift::<f32>(2.0_f32));
```

However, it seems like type checker should be able to resolve the trait bounds using the original call:

```rust
let bar = lift(4.0_f32).min(lift(2.0_f32));
```

since the arguments straightforwardly require the trait for `f32`.  I'm curious whether or not whether this is the intended behavior or whether there's a bug with the type checker.  For reference:

```
$ rustc --version
rustc 1.40.0-nightly (c27f7568b 2019-10-13)
```