Rustc "overflow evaluating the requirement" while it should work.

[wdanilo]

Consider this code:

#![recursion_limit = "256"]

pub trait Visit<T: ?Sized> {
    fn visit(&mut self, elem: &T);
}

pub enum Ast {
    Null,
    App(Box<Ast>,Box<Ast>)
}

impl<T> Visit<Ast> for T
where T: Visit<Box<Ast>> {
    fn visit(&mut self, elem: &Ast) {}
}

impl<T,S:?Sized> Visit<Box<S>> for T
where T: Visit<S> {
    fn visit(&mut self, elem: &Box<S>) {}
}

pub struct MyVisitor{}

fn test() {
    MyVisitor{}.visit(&Ast::Null);
}

Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=9014c0167fc65f14c8a2668428fc5df4

It gives the error:

error[[E0275]](https://doc.rust-lang.org/stable/error-index.html#E0275): overflow evaluating the requirement `MyVisitor: Visit<_>`
  [--> src/lib.rs:25:17
](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=9014c0167fc65f14c8a2668428fc5df4#)   |
25 |     MyVisitor{}.visit(&Ast::Null);
   |                 ^^^^^
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "512"]` attribute to your crate (`playground`)
   = note: required because of the requirements on the impl of `Visit<Box<_>>` for `MyVisitor`
   = note: 256 redundant requirements hidden
   = note: required because of the requirements on the impl of `Visit<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<Box<_>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>` for `MyVisitor`

For more information about this error, try `rustc --explain E0275`.
error: could not compile `playground` due to previous error

Which does not make sense. Let me explain:

1. We do MyVisitor{}.visit(&Ast::Null), which requires a bound MyVisitor: Visit<Ast>.
2. This bound is implemented (impl<T> Visit<Ast> for T), so another bound to be checked is added, which is MyVisitor: Visit<Box<Ast>>.
3. This bound is again implemented (impl<T,S:?Sized> Visit<Box<S>> for T), which while resolving (T is MyVisitor and S is Ast) results in another bound to be resolved: MyVisitor: Visit<Ast>. However, this is our initial bound that we are currently resolving so it should compile fine.

A few things to be noted:

1. The code compiles if the function test is commented out (only the usage throws the error (the impls are correct)).
2. The Box<Box<Box<... situation should never happen in the Rustc type resolver - there is something wrong happening under the hood.

[wdanilo]

This can be related: #39959, and consequently this as well: https://users.rust-lang.org/t/type-recursion-when-trait-bound-is-added-on-reference-type/74525

[b-naber]

results in another bound to be resolved: MyVisitor: Visit. However, this is our initial bound that we are currently resolving so it should compile fine

Why should our initial bound be considered true? Afaict what's going on here is that you have a cycle, once you hit your initial bound you try to again prove MyVisitor: Visit<Box<Ast>>, and then infinitely recurse.

[wdanilo]

results in another bound to be resolved: MyVisitor: Visit. However, this is our initial bound that we are currently resolving so it should compile fine

Why should our initial bound be considered true? Afaict what's going on here is that you have a cycle, once you hit your initial bound you try to again prove MyVisitor: Visit<Box<Ast>>, and then infinitely recurse.

Such loops should be supported IMO, just as they are supported in Haskell, for example. If you have a bound A and during resolution, you've got a bound B, which requires A to exist, you can tell that it's fine, because the bound is being currently resolved. Of course, if you will bring to the resolution scope bounds that are mutually exclusive, an error should be reported. However, until then, not allowing for such a situation drastically limits the expressiveness of the Rust trait system.

[jasonwhite]

I ran into this issue today (Stebalien/tempfile#224) in the tempfile crate. In this issue, the impl impl<'a, F: &'a Write> Write for &'a NamedTempFile<F> broke unrelated code just for simply existing. I don't think that should ever happen, so this definitely seems like a rustc bug.

[ToufeeqP]

Any update on this issue? I am also getting this issue on GAT