Better errors for polymorphic recursion

[jake-87]

Code

enum Nested<T> {
    End,
    Cons(T, Box<Nested<Vec<T>>>),
}

fn length<T>(x: Nested<T>) -> u64 {
    match x {
        Nested::End => 1,
        Nested::Cons(_, xs) => 1 + length(*xs)
    }
}

Current output

Compiling playground v0.0.1 (/playground)
error[E0320]: overflow while adding drop-check rules for `Nested<T>`
 --> src/lib.rs:6:14
  |
6 | fn length<T>(x: Nested<T>) -> u64 {
  |              ^
  |
  = note: overflowed on `Nested<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<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`

error[E0320]: overflow while adding drop-check rules for `Box<Nested<Vec<T>>>`
 --> src/lib.rs:9:25
  |
9 |         Nested::Cons(_, xs) => 1 + length(*xs)
  |                         ^^
  |
  = note: overflowed on `Nested<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<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`

error[E0320]: overflow while adding drop-check rules for `Nested<Vec<T>>`
 --> src/lib.rs:9:43
  |
9 |         Nested::Cons(_, xs) => 1 + length(*xs)
  |                                           ^^^
  |
  = note: overflowed on `Nested<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<Vec<T>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`

For more information about this error, try `rustc --explain E0320`.
error: could not compile `playground` (lib) due to 3 previous errors

Desired output

Not sure what an ideal output would be (Is polymorphic recursion too complex/confusing a term? Presumably if someone is writing code like the above they might know what it is), but ideally something that doesn't spam ~120 Vecs at you when erroring.

Rationale and extra context

Polymorphic recursion is not valid in rust, due to both drop restrictions (what causes the error above), and monomorphization restrictions (it cannot be monomorphized). The current errors are not very explanatory as to what the core issue is.

Other cases

Rust Version

$ rustc 1.85.0-nightly (917bfa784 2024-12-26)
binary: rustc
commit-hash: 917bfa78478cbcc77406e5ea37b24c3eedefacf4
commit-date: 2024-12-26
host: x86_64-unknown-linux-gnu
release: 1.85.0-nightly
LLVM version: 19.1.6

Anything else?

No response

[theemathas]

Surprisingly.... polymorphic recursion seems to be accepted by the compiler if you're not dropping values?

This compiles:

enum Nested<T> {
    End,
    Cons(T, Box<Nested<Vec<T>>>),
}

fn length<T>(x: &Nested<T>) -> u64 {
    match x {
        Nested::End => 1,
        Nested::Cons(_, xs) => 1 + length(xs)
    }
}

fn foo(x: &Nested<i32>) -> u64 {
    length::<i32>(x)
}

Edit: It errors as soon as you make foo public, which seems to cause the compiler to attempt monomorphization.

[jake-87]

Interesting, thank you. That is also less than ideal, however. One would hope that marking something pub does not change whether it errors or not, I presume. Fixing this would require some sort of dedicated polymorphic recursion check though, I think - otherwise there's no way to know until monomorphization time.

This is the error, as expected upon making foo public:

error: reached the recursion limit while instantiating `length::<Vec<Vec<Vec<Vec<Vec<...>>>>>>`
 --> src/lib.rs:9:36
  |
9 |         Nested::Cons(_, xs) => 1 + length(xs)
  |                                    ^^^^^^^^^^
  |
note: `length` defined here
 --> src/lib.rs:6:1
  |
6 | fn length<T>(x: &Nested<T>) -> u64 {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  = note: the full type name has been written to '/playground/target/debug/deps/playground-f300214f41d7cb9c.long-type.txt'

[fmease]

cc #4287 #18874

[saethlin]

One would hope that marking something pub does not change whether it errors or not, I presume.

Errors that require monomorphization to occur are not necessarily detected in dead code. We always type-check and borrow-check all code, but from that point onwards the compiler tries to prune dead code from compilation.

[jake-87]

@fmease Thank you for linking those two. I did take note of #4287, but I decided to open this issue as I believe the solution that closed that issue was not satisfactory, error-message-wise.

@saethlin I see - that does make sense, and I assumed that was why it was not "correctly" erroring.
Seeing as a dedicated pass is most likely entirely too complex for what is a quite niche issue, I personally think it would be reasonable to improve the error ergonomics of both mentioned situations separately, if needed.