Exponentially expanding type causes monomorphization in compiler to panic or run "forever" #132558
Description
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 { // When the recursion limit is set to 20, manually expanding the `Data::Child` // type here makes the compilation fail with a "reached the recursion limit" error, // as it should. But with the default recursion limit, the compilation hangs whether // I manually expand the type here or not. // //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: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 3: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 4: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 5: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 6: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 7: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 8: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 9: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 10: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 11: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 12: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 13: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 14: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 15: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 16: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 17: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 18: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 19: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 20: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 21: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 22: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 23: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 24: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 25: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 26: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 27: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 28: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 29: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 30: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 31: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 32: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 33: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 34: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 35: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 36: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 37: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 38: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 39: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 40: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 41: <&rustc_middle::ty::list::RawList<(), rustc_middle::ty::Ty> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 42: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 43: <rustc_type_ir::ty_info::WithCachedTypeInfo<rustc_type_ir::ty_kind::TyKind<rustc_middle::ty::context::TyCtxt>> as rustc_data_structures::stable_hasher::HashStable<rustc_query_system::ich::hcx::StableHashingContext>>::hash_stable 44: <rustc_query_impl::query_impl::try_normalize_generic_arg_after_erasing_regions::dynamic_query::{closure#7} as core::ops::function::FnOnce<(&mut rustc_query_system::ich::hcx::StableHashingContext, &rustc_middle::query::erase::Erased<[u8; 8]>)>>::call_once 45: rustc_query_system::query::plumbing::try_execute_query::<rustc_query_impl::DynamicConfig<rustc_query_system::query::caches::DefaultCache<rustc_middle::ty::ParamEnvAnd<rustc_middle::ty::generic_args::GenericArg>, rustc_middle::query::erase::Erased<[u8; 8]>>, false, false, false>, rustc_query_impl::plumbing::QueryCtxt, true> 46: <rustc_middle::ty::normalize_erasing_regions::NormalizeAfterErasingRegionsFolder as rustc_type_ir::fold::TypeFolder<rustc_middle::ty::context::TyCtxt>>::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: <rustc_codegen_llvm::LlvmCodegenBackend as rustc_codegen_ssa::traits::backend::CodegenBackend>::codegen_crate 72: <rustc_interface::queries::Linker>::codegen_and_build_linker 73: rustc_interface::interface::run_compiler::<core::result::Result<(), rustc_span::ErrorGuaranteed>, rustc_driver_impl::run_compiler::{closure#0}>::{closure#1} note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.