Exponentially expanding type causes monomorphization in compiler to panic or run "forever"

[ntc2]

The below code causes the compiler to panic or run forever, depending on how large the compiler recursion_limit setting is.

Here's a summary of code below: I have a trait S with associated type S::Child: S, and I define a struct A: S with A::Child = (A,A), and I define (X,X)::Child = (X::Child, X::Child). I define a function uhoh<T: S>(x:T) that recurses on uhoh::<T::Child>, and so trying to call uhoh::<A> results in the compiler needing to monomorphize at type A, A::Child = (A,A), A::Child::Child = ((A,A),(A,A)) etc, ad infinitum. Instead of giving an error as I would expect, the compiler panics or runs forever, depending on how large recursion_limit is.

The below code is a minimal reproduction of a real problem I ran into into a private code base.

Code

Single file reproduction, just run with cargo run:

// Outcomes of running `cargo run` for different recursion limits:
//
// 20 => panics quickly.
// 30 => panics after 2 minutes.
// default => runs for hours until I kill it.
#![recursion_limit = "20"]

trait S {
    type Child: S;
    fn children(&self) -> Vec<Self::Child>;
}

impl<X: S> S for (X, X) {
    type Child = (X::Child, X::Child);
    fn children(&self) -> Vec<Self::Child> {
        vec![]
    }
}

impl<X: S> S for Option<Box<X>> {
    type Child = X;
    fn children(&self) -> Vec<Self::Child> {
        vec![]
    }
}

type Data = Option<Box<(A, A)>>;
struct A {
    data: Data,
}
impl S for A {
    // If I manually expand the `Data::Child` type here, then the compilation
    // fails with "reached the recursion limit" error, as it should, instead of
    // panicking. But in my real, non minimized code, manually expanding the
    // `Data::Child` type doesn't help and the compiler still appears to loop :/
    //
    //type Child = (A, A);
    type Child = <Data as S>::Child;
    fn children(&self) -> Vec<Self::Child> {
        self.data.children()
    }
}

// The problem: this function can't be monomorphized when called with an
// argument of type `A`, because it recurses heterogenously on `A::Child =
// (A,A)`, which induces monomorphization at the type `(A,A)`, which recurses on
// `(A,A)::Child = ((A,A),(A,A))`, and so on, ad infinitum.
fn uhoh<T: S>(x: &T) {
    let children = x.children();
    println!("{}", children.len());
    for child in &children {
        uhoh(child);
    }
}

fn main() {
    let a = A { data: None };
    uhoh(&a);
}

Meta

I encountered the real problem on 1.80.1, and tested the minimal reproduction above on 1.80.1, 1.82.0, and 1.84.0-nightly. I.e.

rustc --version --verbose:

rustc 1.80.1 (3f5fd8dd4 2024-08-06)
binary: rustc
commit-hash: 3f5fd8dd41153bc5fdca9427e9e05be2c767ba23
commit-date: 2024-08-06
host: x86_64-unknown-linux-gnu
release: 1.80.1
LLVM version: 18.1.7

and

rustc 1.82.0 (f6e511eec 2024-10-15)
binary: rustc
commit-hash: f6e511eec7342f59a25f7c0534f1dbea00d01b14
commit-date: 2024-10-15
host: x86_64-unknown-linux-gnu
release: 1.82.0
LLVM version: 19.1.1

and

rustc 1.84.0-nightly (b3f75cc87 2024-11-02)
binary: rustc
commit-hash: b3f75cc872cfd306860c3ad76a239e719015f855
commit-date: 2024-11-02
host: x86_64-unknown-linux-gnu
release: 1.84.0-nightly
LLVM version: 19.1.3

Error output

Here's the output of cargo build on 1.84.0-nightly, with backtrace and huge type elided:

thread 'rustc' panicked at /rustc/b3f75cc872cfd306860c3ad76a239e719015f855/compiler/rustc_type_ir/src/ty_kind.rs:797:17:
type variables should not be hashed: ?0t
stack backtrace:
[backtrace, see below]
query stack during panic:
#0 [try_normalize_generic_arg_after_erasing_regions] normalizing `alloc::vec::Vec<<((((((((((((((((((((A, [a lot of `A`s and parens elided ...] as S>::Child>::len
#1 [collect_and_partition_mono_items] collect_and_partition_mono_items
end of query stack

Panic message asked me to attach this:

rustc-ice-2024-11-03T12_59_37-2130395.txt

Backtrace

``` stack backtrace: 0: rust_begin_unwind 1: core::panicking::panic_fmt 2: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 3: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 4: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 5: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 6: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 7: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 8: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 9: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 10: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 11: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 12: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 13: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 14: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 15: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 16: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 17: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 18: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 19: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 20: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 21: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 22: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 23: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 24: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 25: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 26: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 27: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 28: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 29: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 30: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 31: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 32: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 33: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 34: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 35: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 36: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 37: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 38: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 39: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 40: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 41: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable>::hash_stable 42: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 43: > as rustc_data_structures::stable_hasher::HashStable>::hash_stable 44: )>>::call_once 45: rustc_query_system::query::plumbing::try_execute_query::, rustc_middle::query::erase::Erased<[u8; 8]>>, false, false, false>, rustc_query_impl::plumbing::QueryCtxt, true> 46: >::fold_ty 47: rustc_monomorphize::collector::collect_items_rec::{closure#0} 48: rustc_monomorphize::collector::collect_items_rec 49: rustc_monomorphize::collector::collect_items_rec 50: rustc_monomorphize::collector::collect_items_rec 51: rustc_monomorphize::collector::collect_items_rec 52: rustc_monomorphize::collector::collect_items_rec 53: rustc_monomorphize::collector::collect_items_rec 54: rustc_monomorphize::collector::collect_items_rec 55: rustc_monomorphize::collector::collect_items_rec 56: rustc_monomorphize::collector::collect_items_rec 57: rustc_monomorphize::collector::collect_items_rec 58: rustc_monomorphize::collector::collect_items_rec 59: rustc_monomorphize::collector::collect_items_rec 60: rustc_monomorphize::collector::collect_items_rec 61: rustc_monomorphize::collector::collect_items_rec 62: rustc_monomorphize::collector::collect_items_rec 63: rustc_monomorphize::collector::collect_items_rec 64: rustc_monomorphize::collector::collect_items_rec 65: rustc_monomorphize::collector::collect_items_rec 66: rustc_monomorphize::collector::collect_items_rec 67: rustc_monomorphize::collector::collect_items_rec 68: rustc_monomorphize::collector::collect_items_rec 69: rustc_monomorphize::collector::collect_items_rec 70: rustc_monomorphize::partitioning::collect_and_partition_mono_items [... omitted 2 frames ...] 71: ::codegen_crate 72: ::codegen_and_build_linker 73: rustc_interface::interface::run_compiler::, rustc_driver_impl::run_compiler::{closure#0}>::{closure#1} note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace. ```

[workingjubilee]

https://github.com/rust-lang/rust/blob/fbab78289dd8c6e8860034e0048cfb538f217700/compiler/rustc_type_ir/src/ty_kind.rs#L795-L799

interesting.

[matthiaskrgr]

I wonder if this is another duplicate of https://github.com/rust-lang/rust/issues/95134