rustc hangs when compiling dyn-encoded polymorphic recursion

[naganohara-yoshino]

Summary

rustc hangs indefinitely instead of emitting a recursion limit or overflow error when compiling a generic function that uses polymorphic recursion over a non-regular recursive type.

By hiding the non-regular recursion behind a dyn Fn thunk, the compiler's drop-check overflow checks are bypassed. The generic function then triggers an infinite sequence of distinct monomorphizations, causing rustc to hang without termination or diagnostics.

Code

#![allow(dead_code)]

use std::fmt::Debug;

enum PerfectPrime<A> {
    Fst(A),
    Snd(Box<dyn Fn() -> PerfectPrime<(A, A)>>),
}

fn myprint<A: Debug>(p: PerfectPrime<A>) {
    match p {
        PerfectPrime::Fst(a) => println!("{:?}", a),
        PerfectPrime::Snd(f) => myprint(f()),
    }
}

fn main() {
    let p0: PerfectPrime<i32> = PerfectPrime::Fst(42);
    myprint(p0);
}

Expected behavior

rustc should terminate and emit an error, such as an infinite monomorphization diagnostic.

Actual behavior

rustc hangs indefinitely during compilation. In local testing, the compilation did not finish after running for over 1 hour, and the compiler output remained stuck on:

Building [                             ] 0/1: a(bin)

No diagnostic, error, or panic is emitted.

Analysis

This issue exposes a fundamental conflict between non-regular recursive types (where the type parameter changes in the recursive definition, e.g., A to (A, A)) and monomorphization.

1. The Language Design Conflict

In languages like OCaml and Haskell, generics are implemented using uniform representation (type erasure or boxing). A polymorphic function is compiled exactly once and operates on pointers. Consequently, polymorphic recursion over a non-regular type is perfectly valid.

For example, the equivalent non-regular type and polymorphic recursion in Haskell compiles and runs perfectly (laziness makes the explicit thunk unnecessary):

data Perfect a = Fst a | Snd (Perfect (a, a))

myPrint :: Show a => Perfect a -> IO ()
myPrint (Fst a) = print a
myPrint (Snd p) = myPrint p

main :: IO ()
main = do
  let p0 = Snd (Fst (1, 2))
  myPrint p0

Similarly, in OCaml, the exact thunked pattern is standard and accepted:

type 'a perfect_prime =
  | Fst of 'a
  | Snd of (unit -> ('a * 'a) perfect_prime)

Rust, however, uses monomorphization. Every time a generic function is called with a new type, the compiler generates a specialized copy of that function. Thus, non-regular polymorphic recursion is fundamentally incompatible with Rust's compilation model because it requires generating infinitely many distinct function bodies.

2. Bypassing Type-Level Limits

Normally, Rust catches this non-regular recursion during instantiation. Simply defining a directly recursive non-regular type is allowed, but instantiating it triggers a drop-check overflow:

enum Perfect<A> {
    Fst(A),
    Snd(Box<Perfect<(A, A)>>),
}

fn main() {
    let p0: Perfect<i32> = Perfect::Fst(42);
}

This fails correctly with:

error[E0320]: overflow while adding drop-check rules for `Perfect<i32>`

However, introducing the dyn Fn thunk in PerfectPrime successfully hides the infinitely expanding type behind a dynamically dispatched trait object. Because dyn Fn breaks the visible structural recursion for the drop-checker, instantiation succeeds, and the type definition bypasses structural limits.

3. Runaway Monomorphization

Because instantiation is accepted, the non-regular recursion reappears at the function level. In the Snd branch of myprint, f() returns PerfectPrime<(A, A)>. Compiling myprint::<A> forces the compiler to monomorphize myprint::<(A, A)>, which requires myprint::<((A, A), (A, A))>, and so on ad infinitum:

myprint::<A>
myprint::<(A, A)>
myprint::<((A, A), (A, A))>
myprint::<(((A, A), (A, A)), ((A, A), (A, A)))>
...

rustc continuously attempts to generate these larger instantiations but fails to trigger standard monomorphization recursion limits (like #![recursion_limit]), resulting in a silent hang.

Meta

rustc --version --verbose:

rustc 1.97.0-nightly (e95e73209 2026-05-05)
binary: rustc
commit-hash: e95e73209faf6ead2bc5c7636e45e589a751b79b
commit-date: 2026-05-05
host: x86_64-pc-windows-msvc
release: 1.97.0-nightly
LLVM version: 22.1.4

(No backtrace is available because compilation does not panic or complete).

[naganohara-yoshino]

Smaller example:

#![allow(dead_code)]
#![recursion_limit = "20"]

enum Foo<A> {
    Fst,
    Snd(Box<dyn Fn() -> Foo<(A, A)>>),
}

fn recursive<A>(x: Foo<A>) {
    match x {
        Foo::Fst => (),
        Foo::Snd(f) => recursive(f()),
    }
}

fn main() {
    let p0: Foo<()> = Foo::Fst;
    recursive(p0);
}

I found that once I add a smaller recursion limit, this does terminate quickly.

Running:

RUST_BACKTRACE=1 cargo build

produces:

error: reached the recursion limit while instantiating `recursive::<((((((..., ...), ...), ...), ...), ...), ...)>`
  --> app\src\main.rs:12:24
   |
12 |         Foo::Snd(f) => recursive(f()),
   |                        ^^^^^^^^^^^^^^
   |
note: `recursive` defined here
  --> app\src\main.rs:9:1
   |
 9 | fn recursive<A>(x: Foo<A>) {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: the full name for the type has been written to 'F:\Coding\rs-projects\lab\target\debug\deps\app.long-type-7065964781721606489.txt'
   = note: consider using `--verbose` to print the full type name to the console

error: could not compile `app` (bin "app") due to 1 previous error

[matthiaskrgr]

might be related to #149289

[naganohara-yoshino]

might be related to #149289

Non-regular recursive types again, I think. 😉

In this example, even dyn wrapping is unnecessary to get rustc hanging when compiling its instantiation.

Only under certain circumstances where there is a "down-grading" (or structural decreasing) of the generic parameter, is it possible to make it really work. Below is a finite, working example. However, as you can see, direct polymorphic recursion via a single fn is still impossible in Rust (since it lacks GADT-style dead-branch elimination), trait-based ad-hoc polymorphism is strictly necessary to prune the AST and stop the monomorphization divergence.

trait Peel {
    type Next: Peel;
}

impl Peel for i32 {
    type Next = i32;
}

impl<T: Peel> Peel for (T, T) {
    type Next = T;
}

enum Foo<A: Peel> {
    Done(i32),
    More(Box<dyn Fn() -> Foo<A::Next>>),
}

trait Eval: Peel + Sized {
    fn eval(x: Foo<Self>) -> i32;
}

impl Eval for i32 {
    fn eval(x: Foo<i32>) -> i32 {
        match x {
            Foo::Done(n) => n,
            Foo::More(_) => panic!("stop"),
        }
    }
}

impl<T: Eval> Eval for (T, T) {
    fn eval(x: Foo<(T, T)>) -> i32 {
        match x {
            Foo::Done(n) => n,
            Foo::More(f) => T::eval(f()),
        }
    }
}

fn main() {
    let x: Foo<((i32, i32), (i32, i32))> =
        Foo::More(Box::new(|| Foo::More(Box::new(|| Foo::Done(1)))));

    println!("{}", <((i32, i32), (i32, i32))>::eval(x));
}

[naganohara-yoshino]

I looked more closely at compiler/rustc_monomorphize/src/collector.rs, and I think the issue is not that the recursion-limit check is missing, but that it only measures recursive instantiation depth.

It appears that check_recursion_limit tracks instantiation depth keyed by DefId, incrementing it by exactly 1 at each recursive call. Since the default recursion_limit is 128, the collector considers early depths to be perfectly safe.

However, for non-regular recursion like A -> (A, A), the type size grows exponentially. By depth ~25, the type tree already contains millions of nodes. The compiler likely hangs while folding, hashing, or interning this massive type tree long before it reaches the 128 depth limit.

---

A potential idea for a fix:
Perhaps the collector could eagerly enforce the type_length_limit on instance.args during the recursion check, rather than relying solely on the linear depth limit. Checking the type's structural size before proceeding with expensive MIR substitutions might successfully catch this exponential blowup and emit a proper limit diagnostic.

Thanks for your time looking into this!

[qaijuang]

@naganohara-yoshino are you putting effort on it, or i should claim it ?

[naganohara-yoshino]

@qaijuang Thanks for offering! I'm currently trying to figure out the best algorithm for fixing this and what diagnostic message should be emitted. I'd like to put some effort into a fix. Any guidance or suggestions from maintainers and the community would be highly appreciated!

[qaijuang]

@naganohara-yoshino great

I'm currently trying to figure out the best algorithm for fixing this and what diagnostic message should be emitted.

There's a RecursionLimit error type used in compiler/rustc_monomorphize/src/collector.rs is it something that could help?

I'm not sure how broad you want to go