`overflow evaluating the requirement` with `impl`s those seem to be right

[WaffleLapkin]

I tried this code:

#![recursion_limit="5"] // without it the error is the same, but much bigger
struct Nil;
struct Cons<H, T>(H, T);

pub trait Map<F> {
    type Output;
}

impl<FH, FM, FT, H, M, T, R> Map<Cons<FH, Cons<FM, FT>>> for Cons<H, Cons<M, T>>
where
    FH: FnOnce(H) -> R,
    Cons<M, T>: Map<Cons<FM, FT>>,
{
    type Output = Cons<R, <Cons<M, T> as Map<Cons<FM, FT>>>::Output>;
}

impl<F, H, T, R> Map<F> for Cons<H, T>
where
    F: FnMut(H) -> R,
    T: Map<F>,
{
    type Output = Cons<R, T::Output>;
}

I expected this code to compile.

Instead, the compiler fails with a huge error:

error[E0275]: overflow evaluating the requirement `Cons<_, Cons<_, _>>: Map<Cons<_, Cons<_, _>>>`
  |
  = help: consider adding a `#![recursion_limit="10"]` attribute to your crate (`playground`)
  = note: required because of the requirements on the impl of `Map<Cons<_, Cons<_, Cons<_, _>>>>` for `Cons<_, Cons<_, Cons<_, _>>>`
  = note: required because of the requirements on the impl of `Map<Cons<_, Cons<_, Cons<_, Cons<_, _>>>>>` for `Cons<_, Cons<_, Cons<_, Cons<_, _>>>>`
  = note: required because of the requirements on the impl of `Map<Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, _>>>>>>` for `Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, _>>>>>`
  = note: required because of the requirements on the impl of `Map<Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, _>>>>>>>` for `Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, _>>>>>>`
  = note: required because of the requirements on the impl of `Map<Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, _>>>>>>>>` for `Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, _>>>>>>>`

(playground)

Note that very similar code with a slightly different trait works, so I assume this is a bug (though, I may miss something)

Also, note that there is a lot of issues with E0275, however, I couldn't find one that fits my problem.

Meta

Tested on 1.45.0 and 1.47.0-nightly (2020-07-25 d6953df14657f5932270)

[WaffleLapkin]

I've created more minimal example:

#![recursion_limit="5"] // without it the error is the same, but much bigger

struct Nil;
struct Cons<H, T>(H, T);

pub trait Map<F> {}

impl<F, H, M, T> Map<F> for Cons<H, Cons<M, T>>
where
    Cons<(), T>: Map<Cons<(), ()>>,
{}

impl<F, H, T> Map<F> for Cons<H, T> {}

(playground)

I don't expect this to compile (in difference with original example), though the error should definitely be

error[E0119]: conflicting implementations of trait `Map<_>` for type `Cons<_, Cons<_, _>>`

instead of

error[E0275]: overflow evaluating the requirement `Cons<_, Cons<_, _>>: Map<Cons<_, Cons<_, _>>>`

[RodBurman]

The current tool chain:

% cargo -v -V
cargo 1.84.1 (66221abde 2024-11-19)
release: 1.84.1
commit-hash: 66221abdeca2002d318fde6efff516aab091df0e
commit-date: 2024-11-19
host: aarch64-apple-darwin
libgit2: 1.8.1 (sys:0.19.0 vendored)
libcurl: 8.7.1 (sys:0.4.74+curl-8.9.0 system ssl:(SecureTransport) LibreSSL/3.3.6)
ssl: OpenSSL 1.1.1w  11 Sep 2023
os: Mac OS 15.3.1 [64-bit]

compiles the original code with just a warning:

cargo build
   Compiling overev v0.1.0 (/Users/rod/code/rust/triage/overev)
warning: struct `Nil` is never constructed
 --> src/main.rs:2:8
  |
2 | struct Nil;
  |        ^^^
  |
  = note: `#[warn(dead_code)]` on by default

warning: `overev` (bin "overev") generated 1 warning
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 3.63s

So no overflow or other error, I think this issue can be closed.

[WaffleLapkin]

Indeed, the issue seems to be fixed. Still, it'd be interesting to see which PR fixed the issue, and add test(s) in case the PR which fixed this did not have similar tests already. Tagging this issue appropriately.

[moxian]

Bisects to #130654
I believe there is appropriate test coverage in that PR as well, but I might be misreading this.

@rustbot label: -E-needs-bisection +S-has-bisection +A-coherence