Type inference results in infinite recursion in trait resolution

[konnorandrews]

I ran into a type inference issue with some code and minimized it to the following.

#![recursion_limit = "10"]

fn main() {
    let _x: () = of(); // doesn't work

    let _x: () = of::<()>(); // works
}

impl MyTrait for &'static () {}

trait MyTrait {}

impl<T> MyTrait for (T,) where T: MyTrait {}

impl<T> MyTrait for &'static (T,) where &'static T: MyTrait {}

fn of<T: 'static>() -> T
where
    &'static T: MyTrait,
{
    todo!()
}

impl<T> MyTrait for &'static &'static T where &'static T: MyTrait {}

playground link

The above results in the following (both stable and nightly).

error[[E0275]](https://doc.rust-lang.org/nightly/error_codes/E0275.html): overflow evaluating the requirement `&'static (_,): MyTrait`
  --> src/main.rs:4:18
   |
4  |     let _x: () = of(); // doesn't work
   |                  ^^
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "20"]` attribute to your crate (`playground`)
note: required for `&'static ((_,),)` to implement `MyTrait`
  --> src/main.rs:15:9
   |
15 | impl<T> MyTrait for &'static (T,) where &'static T: MyTrait {}
   |         ^^^^^^^     ^^^^^^^^^^^^^                   ------- unsatisfied trait bound introduced here
   = note: 8 redundant requirements hidden
   = note: required for `&'static ((((((((((_,),),),),),),),),),)` to implement `MyTrait`
note: required by a bound in `of`
  --> src/main.rs:19:17
   |
17 | fn of<T: 'static>() -> T
   |    -- required by a bound in this function
18 | where
19 |     &'static T: MyTrait,
   |                 ^^^^^^^ required by this bound in `of`

For more information about this error, try `rustc --explain E0275`.

I expected that rustc would have inferred the type to be () in the first case. If you comment out the first line of main it works.

This may be related to #39959 but I am not sure.

Meta

rustc --version --verbose (from the playground):

1.72.0-nightly (2023-06-21 065a1f5df9c2f1d93269)

[konnorandrews]

#![recursion_limit = "10"]

fn main() {
    let _x: () = of(); // doesn't work

    let _x: () = of::<()>(); // works
}

trait MyTrait {}

impl MyTrait for &'static () {}

impl<T> MyTrait for &'static (T,) where &'static T: MyTrait {}

fn of<T: 'static>() -> T
where
    &'static T: MyTrait,
{
    todo!()
}

playground link

Turns out 2 of the impl aren't actually needed to reproduce the error.

[konnorandrews]

Removing the impl<T> MyTrait for &'static (T,) where &'static T: MyTrait {} line without changing main() results in it compiling.

[konnorandrews]

After playing around with it some more I found out having the impl anywhere in the module tree including inside a function's scope results in the same thing.

#![recursion_limit = "6"]

fn main() {
    let _x: () = of(); // doesn't work

    let _x: () = of::<()>(); // works
}

trait MyTrait {}

impl MyTrait for &'static () {}

mod other {
    use super::MyTrait;

    fn some_function() {
        struct hello_from_inside_other_mod<T>(T);

        impl<T> MyTrait for &'_ hello_from_inside_other_mod<T> where for<'a> &'a T: MyTrait {}
    }
}

fn of<T: 'static>() -> T
where
    &'static T: MyTrait,
{
    todo!()
}

playground link

Which results in the following.

error[[E0275]](https://doc.rust-lang.org/nightly/error_codes/E0275.html): overflow evaluating the requirement `for<'a> &'a hello_from_inside_other_mod<_>: MyTrait`
  --> src/main.rs:4:18
   |
4  |     let _x: () = of(); // doesn't work
   |                  ^^
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "12"]` attribute to your crate (`playground`)
note: required for `&'a hello_from_inside_other_mod<hello_from_inside_other_mod<_>>` to implement `for<'a> MyTrait`
  --> src/main.rs:19:17
   |
19 |         impl<T> MyTrait for &'_ hello_from_inside_other_mod<T> where for<'a> &'a T: MyTrait {}
   |                 ^^^^^^^     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^                      ------- unsatisfied trait bound introduced here
   = note: 4 redundant requirements hidden
   = note: required for `&hello_from_inside_other_mod<hello_from_inside_other_mod<hello_from_inside_other_mod<...>>>` to implement `MyTrait`
   = note: the full type name has been written to '/playground/target/debug/deps/playground-729223f269b31276.long-type-2301279540383687721.txt'
note: required by a bound in `of`
  --> src/main.rs:25:17
   |
23 | fn of<T: 'static>() -> T
   |    -- required by a bound in this function
24 | where
25 |     &'static T: MyTrait,
   |                 ^^^^^^^ required by this bound in `of`

For more information about this error, try `rustc --explain E0275`.

[tweqx]

I think I found a similar issue. This fails exactly in the same way as yours:

struct Wrapped<T>(T);

trait Trait {
}
impl<T> Trait for ((), T) {
}
impl<T, V> Trait for (Wrapped<T>, Wrapped<V>)
where
    (T, V): Trait,
{
}

fn test<T, U>(_x: T, _y: U)
where
    (T, U): Trait,
{
}

fn main() {
    test::<(), ()>((), ()); // compiles
    test((), ()); // does not compile
}

Instead of a reference to (T,) (equivalent to my Wrapped<T>), mine is based on the use of a tuple.

[DzenanJupic]

Same issue here

[playground]

pub trait Serialize<As: ?Sized = Self> {}

pub fn empty<T: ?Sized>() -> Vec<u8>
where
    T: Serialize,
{
    todo!();
}

pub struct Int<A>(pub A);

impl Serialize for Int<[u8; 1]> {}

impl<T, As> Serialize<Int<&As>> for Int<&T> 
where
    Int<T>: Serialize<Int<As>>,
{}

fn weird_error() {
    let _: Vec<u8> = empty();
}

results in:

Actual error

error[[E0275]](https://doc.rust-lang.org/stable/error_codes/E0275.html): overflow evaluating the requirement `Int<&_>: Serialize`
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`playground`)
note: required for `Int<&&_>` to implement `Serialize`
  --> src/lib.rs:16:13
   |
16 | impl<T, As> Serialize<Int<&As>> for Int<&T> 
   |             ^^^^^^^^^^^^^^^^^^^     ^^^^^^^
17 | where
18 |     Int<T>: Serialize<Int<As>>,
   |             ------------------ unsatisfied trait bound introduced here
   = note: 126 redundant requirements hidden
   = note: required for `Int<&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&_>` to implement `Serialize`

instead of the expected type annotations needed error

Expected error

error[[E0283]](https://doc.rust-lang.org/stable/error_codes/E0283.html): type annotations needed
  --> src/lib.rs:38:22
   |
38 |     let _: Vec<u8> = empty();
   |                      ^^^^^ cannot infer type of the type parameter `T` declared on the function `empty`
   |
   = note: cannot satisfy `_: Serialize`
note: required by a bound in `empty`
  --> src/lib.rs:7:8
   |
5  | pub fn empty<T: ?Sized>() -> Vec<u8>
   |        ----- required by a bound in this function
6  | where
7  |     T: Serialize,
   |        ^^^^^^^^^ required by this bound in `empty`
help: consider specifying the generic argument
   |
38 |     let _: Vec<u8> = empty::<T>();
   |                           +++++

Both on stable and rustc 1.73.0-nightly (08d00b40a 2023-08-09)