rust-lang / rust-lang/rust

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

Open
#132,558 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

A-monomorphization C-bug I-ICE I-monomorphization T-compiler
Dominant language
Rust
Stars
119k
Forks
16.1k
PR metrics pending

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.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Run the embedded single-file reproduction with cargo run, varying the recursion_limit as described, and confirm the panic or nontermination. Start from the reported query stack entries, including try_normalize_generic_arg_after_erasing_regions and collect_and_partition_mono_items. Done means the compiler handles this recursively expanding monomorphization case with a diagnostic instead of panicking or running indefinitely.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.