Repository: rust
Issue: Exponentially expanding type causes monomorphization in compiler to panic or run "forever"
Labels: I-ICE,T-compiler,C-bug,I-monomorphization,A-monomorphization

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.

<!--
Thank you for finding an Internal Compiler Error! 🧊  If possible, try to provide
a minimal verifiable example. You can read "Rust Bug Minimization Patterns" for
how to create smaller examples.
http://blog.pnkfx.org/blog/2019/11/18/rust-bug-minimization-patterns/
-->

### Code

Single file reproduction, just run with `cargo run`:

```Rust
// 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
<!--
If you're using the stable version of the compiler, you should also check if the
bug also exists in the beta or nightly versions.
-->

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](https://github.com/user-attachments/files/17610521/rustc-ice-2024-11-03T12_59_37-2130395.txt)

<!--
Include a backtrace in the code block by setting `RUST_BACKTRACE=1` in your
environment. E.g. `RUST_BACKTRACE=1 cargo build`.
-->
<details><summary><strong>Backtrace</strong></summary>
<p>

```
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.
```

</p>
</details>