rust - Why do I get an "overflow evaluating the requirement" error for a simple trait implementation?

Question

I'm getting an error[E0275]: overflow evaluating the requirement on this simple code, and I don't know how to resolve it. The error message suggests adding a recursion limit attribute to the trait; however, when I add the attribute it produces a new error message and suggests I double the recursion limit until it is so large that rustc overflows its stack. There are many other questions already about this error, but they seem different than my case.

struct Foo<T>(T);

impl<T> From<&'_ Foo<T>> for String
where
    for<'a> &'a T: Into<String>,
{
    fn from(s: &Foo<T>) -> String {
        (&s.0).into()
    }
}

fn main() {
    println!("{}", String::from(&Foo(String::new())));
}

error[E0275]: overflow evaluating the requirement `String: From<&'a Foo<_>>`
  --> src/main.rs:13:20
   |
13 |     println!("{}", String::from(&Foo(String::new())));
   |                    ^^^^^^^^^^^^
   |
   = help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`playground`)
   = note: required because of the requirements on the impl of `for<'a> Into<String>` for `&'a Foo<_>`
   = note: required because of the requirements on the impl of `From<&'a Foo<Foo<_>>>` for `String`
   = note: 126 redundant requirements hidden
   = note: required because of the requirements on the impl of `From<&Foo<Foo<Foo<...>>>>` for `String`

Answer 1

This is an unresolved compiler issue. First reported in 2016 as #37748: Overflow for trait implemented recursively on references with the reproducible example:

trait Foo {}
impl<'a> Foo for &'a usize {}
impl<'a, T> Foo for &'a Vec<T> where &'a T: Foo {}

fn foo<T>(_: T) where for<'a> &'a T: Foo {}

fn main() {
    foo(0);
}

While the specifics of the error message have changed over time, its evident the core issue is the same:

error[E0275]: overflow evaluating the requirement `&Vec<_>: Foo`
 --> srcmain.rs:8:5
  |
5 | fn foo<T>(_: T) where for<'a> &'a T: Foo {}
  |                                      --- required by this bound in `foo`
...
8 |     foo(0);
  |     ^^^
  |
  = help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`guessing_game`)
  = note: required because of the requirements on the impl of `Foo` for `&Vec<Vec<_>>`
  = note: 127 redundant requirements hidden
  = note: required because of the requirements on the impl of `for<'a> Foo` for `&'a Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<Vec<_>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`

This pattern is seen in other issues: #77158 #78982 #65420 #60603 #49017 #48767 #39959 (these could probably do with some consolidation). And unfortunately, none of these provide a solution or general workaround. The only real suggestion is to convert the generic implementation into concrete ones, which may or may not be possible:

impl From<&'_ Foo<String>> for String {
    fn from(s: &Foo<String>) -> String {
        (&s.0).into()
    }
}

From my naive understanding, the trait solver will first determine candidate implementations to select from during the resolution process. It can find concrete and generic candidates well enough even with recursive definitions, but seems to have trouble if the types being recursed include lifetimes. I won't pretend to know exactly where it goes wrong, just that lifetimes are handled differently. You can read more about the trait solver in the Guide to Rustc Development.

Its not clear to me the Rust team's perspective on this issue. It may be solved as an edge case for specialization or they may be waiting for chalk to handle it. But its evident this is not a priority.