rust-lang / rust

Empowering everyone to build reliable and efficient software.
https://www.rust-lang.org
Other
98.89k stars 12.78k forks source link

Thread 'rustc' has overflowed its stack on dumb program #75577

Open AuroransSolis opened 4 years ago

AuroransSolis commented 4 years ago

It's me again! Back this time with something that throws a spanner in the works for rustc without it taking multiple hundred gigabytes of memory and several days to compile. It's an Advent of Code challenge once more - and this time I tried to solve everything at compile time with macro abuse and types. Here's a small example using the setup I made in the playground (input is on line 181), and here's the large example that causes the error (as a gist since it times out in the playground). I have just a little bit of a hunch that #![recursion_limit="50000"] basically being required has something to do with the error:

auro@auro-desktop ~/projects/aoc_2018_d5_ct $ time cargo run
   Compiling aoc_2018_d5_ct v0.1.0 (/home/auro/projects/aoc_2018_d5_ct)

thread 'rustc' has overflowed its stack
fatal runtime error: stack overflow
error: could not compile `aoc_2018_d5_ct`.

Caused by:
  process didn't exit successfully: `rustc --crate-name aoc_2018_d5_ct --edition=2018 src/main.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type bin --emit=dep-info,link -Cembed-bitcode=no -C debuginfo=2 -C metadata=8d4922b265418474 -C extra-filename=-8d4922b265418474 --out-dir /home/auro/projects/aoc_2018_d5_ct/target/debug/deps -C incremental=/home/auro/projects/aoc_2018_d5_ct/target/debug/incremental -L dependency=/home/auro/projects/aoc_2018_d5_ct/target/debug/deps --extern paste=/home/auro/projects/aoc_2018_d5_ct/target/debug/deps/libpaste-56ec6c5ce13200bb.so` (signal: 6, SIGABRT: process abort signal)

I feel like an apology is in order for anyone who tries figuring out what's going wrong here, so: I'm deeply, deeply, sorry.

AuroransSolis commented 4 years ago

Oh yeah, also, here's a backtrace of rustc from when I ran it in gdb. https://gist.github.com/AuroransSolis/9f3b7bb1c1a1cdbdc6f9469aa7d0f9df

nagisa commented 4 years ago

This is probably not too hard to fix, so marking it as a E-easy for a contributor to pick up. A well positioned ensure_sufficient_stack should be enough. All that’s left is to find where exactly to put it!

Instructions

The stacktrace posted above is incomplete. So the first thing you will want to do is to compile the provided reproducer program under a debugger and extract the couple dozen of the stack frames at the bottom of the stack. This should inform you as to where exactly in the compiler the recursion is entered. Once you have that information available, you will have to find the corresponding code in the codebase and add a call to ensure_sufficient_stack to break up the recursion.

Spoiler: bottom frames of stack ``` #43960 0x00007f377c420ee9 in as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43961 0x00007f377c3f8c1f in ::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43962 0x00007f377c3edfa5 in as core::iter::traits::iterator::Iterator>::fold () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43963 0x00007f377c41fa9b in as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43964 0x00007f377c4008d9 in as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43965 0x00007f377c420ee9 in as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43966 0x00007f377c3f8c1f in ::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43967 0x00007f377c3edfa5 in as core::iter::traits::iterator::Iterator>::fold () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43968 0x00007f377c41fa9b in as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43969 0x00007f377c4008d9 in as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43970 0x00007f377c420ee9 in as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43971 0x00007f377c3f8c1f in ::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43972 0x00007f377c3d0881 in rustc_parse::parser::ty::::parse_ty_common () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43973 0x00007f377c3cbc82 in rustc_parse::parser::path::::parse_generic_arg () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43974 0x00007f377c3cae9b in rustc_parse::parser::path::::parse_angle_args () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43975 0x00007f377c3c87bd in rustc_parse::parser::path::::parse_path_segment () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43976 0x00007f377c3c7f01 in rustc_parse::parser::path::::parse_path_segments () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43977 0x00007f377c3c7d63 in rustc_parse::parser::path::::parse_path () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43978 0x00007f377c3d3b28 in rustc_parse::parser::ty::::parse_ty_common () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43979 0x00007f377c3cbc82 in rustc_parse::parser::path::::parse_generic_arg () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43980 0x00007f377c3cae9b in rustc_parse::parser::path::::parse_angle_args () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43981 0x00007f377c3c87bd in rustc_parse::parser::path::::parse_path_segment () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43982 0x00007f377c3c7f01 in rustc_parse::parser::path::::parse_path_segments () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43983 0x00007f377c3c7d63 in rustc_parse::parser::path::::parse_path () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43984 0x00007f377c3d3b28 in rustc_parse::parser::ty::::parse_ty_common () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43985 0x00007f377c3bc351 in rustc_parse::parser::nonterminal::::parse_nonterminal () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43986 0x00007f377c2f335c in rustc_expand::mbe::macro_parser::parse_tt () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43987 0x00007f377c2f6726 in ::expand () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43988 0x00007f377c30b6da in rustc_expand::expand::MacroExpander::fully_expand_fragment () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43989 0x00007f377c30a860 in rustc_expand::expand::MacroExpander::expand_crate () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43990 0x00007f377a5de07c in rustc_session::utils::::time () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43991 0x00007f377a62da4e in rustc_interface::passes::configure_and_expand_inner () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43992 0x00007f377a5f6469 in rustc_interface::passes::configure_and_expand::{{closure}} () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43993 0x00007f377a5eb97f in rustc_data_structures::box_region::PinnedGenerator::new () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43994 0x00007f377a62ca45 in rustc_interface::passes::configure_and_expand () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43995 0x00007f377a677b78 in rustc_interface::queries::Queries::expansion () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43996 0x00007f377a32ac07 in rustc_interface::queries::::enter () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43997 0x00007f377a2c0da7 in rustc_span::with_source_map () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43998 0x00007f377a32c893 in rustc_interface::interface::create_compiler_and_run () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #43999 0x00007f377a30b14a in scoped_tls::ScopedKey::set () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #44000 0x00007f377a31f633 in std::sys_common::backtrace::__rust_begin_short_backtrace () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #44001 0x00007f377a2ab3ae in core::ops::function::FnOnce::call_once{{vtable-shim}} () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so #44002 0x00007f3779a5b0da in as core::ops::function::FnOnce>::call_once () at /rustc/663d2f5cd3163f17eddb74ee1e028d542255f21a/library/alloc/src/boxed.rs:1042 #44003 as core::ops::function::FnOnce>::call_once () at /rustc/663d2f5cd3163f17eddb74ee1e028d542255f21a/library/alloc/src/boxed.rs:1042 #44004 std::sys::unix::thread::Thread::new::thread_start () at library/std/src/sys/unix/thread.rs:87 #44005 0x00007f3779999ead in start_thread () from /nix/store/aqq6367snc1zh3fs1pc4j4zm5h80vkkz-glibc-2.31/lib/libpthread.so.0 #44006 0x00007f37798b9d2f in clone () from /nix/store/aqq6367snc1zh3fs1pc4j4zm5h80vkkz-glibc-2.31/lib/libc.so.6 ```
Spoiler: where in the code change needs to be made Looking at the stack trace you will see that the recursion begins with a call to `::clone()`. From the [source code](https://github.com/rust-lang/rust/blob/e482c86b9de32c6392cb83aa97d72e22425163f9/src/librustc_ast/ast.rs#L1852) for `ast::Ty` it can be seen that `Clone` is derived and that `Ty` contains a `TyKind`. `TyKind` is then recursive and also derives a `Clone`, so for deeply nested types this will indeed trigger a stack overflow. Manually implementing `Clone` to introuce the necessary break-up is then probably the most appropriate quick solution.

I encourage you to ping me here or on Zulip if you need additional help.

chansuke commented 4 years ago

Hi. I'd like to work on this issue

chansuke commented 4 years ago

@rustbot claim

hbina commented 4 years ago

I am literally unable to test if my changes fix this problem because 13.6 GB RAM and 2GB swap is not enough to test it....But if I understood this correctly, the solution is to simply implement Clone and execute the clone as a lambda inside ensure_sufficient_stack.

tesuji commented 4 years ago

@hbina Please remove the close/fix keyword from #76985 body until we have tests for this issue.

estebank commented 4 years ago

@AuroransSolis could you test this again in your environment with the latest nightly?

AuroransSolis commented 4 years ago

I tried briefly and it quickly claimed 25GB of memory (10GB of RAM and 15GB of swap), causing my displays to freeze and forcing me to use a teletype to kill it. I'll try again overnight tonight and see what happens.

AuroransSolis commented 4 years ago

Attempted again. Turns out my 16GB of memory and 256GB of swap wasn't enough. It ate up all of it and the kernel sent it a SIGKILL. I suppose this just further confirms my categorizing this as a dumb program.

Update: friend of mine will be loaning me a 2TB drive to use as a swap disk. Once I get that I'll try again to make sure there's no further issues.

AuroransSolis commented 4 years ago

That's a possibility. I'll try again with about half the input later this evening and update here after doing so.

BlackHoleFox commented 4 years ago

I attempted to reproduce this on my Windows system but it looks like Windows won't give it enough page space to continue:

cargo +nightly run
   Compiling paste v1.0.3
   Compiling macro_testing v0.1.0 (C:\Users\user\Downloads\macro_testing)
thread 'rustc' panicked at 'unable to allocate fiber: The paging file is too small for this operation to complete. (os error 1455)', C:\Users\runneradmin\.cargo\registry\src\github.com-1ecc6299db9ec823\stacker-0.1.12\src\lib.rs:352:21
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

error: internal compiler error: unexpected panic

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/issues/new?labels=C-bug%2C+I-ICE%2C+T-compiler&template=ice.md

note: rustc 1.50.0-nightly (fe982319a 2020-11-19) running on x86_64-pc-windows-msvc

note: compiler flags: -C embed-bitcode=no -C debuginfo=2 -C incremental --crate-type bin

note: some of the compiler flags provided by cargo are hidden

query stack during panic:
end of query stack

thread 'rustc' has overflowed its stack
error: could not compile `macro_testing`

Caused by:
  process didn't exit successfully: `rustc --crate-name macro_testing --edition=2018 src\main.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type bin --emit=dep-info,link -C embed-bitcode=no -C debuginfo=2 -C metadata=4f528d08987c48f9 --out-dir C:\Users\user\Downloads\macro_testing\target\debug\deps -C incremental=C:\Users\user\Downloads\macro_testing\target\debug\incremental -L dependency=C:\Users\user\Downloads\macro_testing\target\debug\deps --extern paste=C:\Users\user\Downloads\macro_testing\target\debug\deps\paste-4388445a40bd90ce.dll` (exit code: 0xc00000fd, STATUS_STACK_OVERFLOW)

This ended up taking ~130GB of swap space and 64GB of RAM before ICEing.

LegionMammal978 commented 3 years ago

@nagisa, I did some testing on this and have come up with a minimal example. As written, it produces the same stack trace as the original program using a debug build of nightly-2020-08-15. However, it only requires ~16 GB of RAM on a modern nightly build and builds for ~30 s on my machine before overflowing the stack.

#![recursion_limit = "1000000000"]

pub struct Test<T>(T);

macro_rules! big_type {
    (0, $ty:ty, $t1:tt) => { Test<$ty> };
    (0, $ty:ty, $t1:tt, $($t:tt),+) => { big_type!(0, Test<$ty>, $($t),+) };
    (1, $($t:tt),+) => { big_type!(0, (), $($t, $t),+) };
    (2, $($t:tt),+) => { big_type!(1, $($t, $t),+) };
    (3, $($t:tt),+) => { big_type!(2, $($t, $t),+) };
    (4, $($t:tt),+) => { big_type!(3, $($t, $t),+) };
    (5, $($t:tt),+) => { big_type!(4, $($t, $t),+) };
    (6, $($t:tt),+) => { big_type!(5, $($t, $t),+) };
    (7, $($t:tt),+) => { big_type!(6, $($t, $t),+) };
    (8, $($t:tt),+) => { big_type!(7, $($t, $t),+) };
    (9, $($t:tt),+) => { big_type!(8, $($t, $t),+) };
    (10, $($t:tt),+) => { big_type!(9, $($t, $t),+) };
    (11, $($t:tt),+) => { big_type!(10, $($t, $t),+) };
    (12, $($t:tt),+) => { big_type!(11, $($t, $t),+) };
    (13, $($t:tt),+) => { big_type!(12, $($t, $t),+) };
    (14, $($t:tt),+) => { big_type!(13, $($t, $t),+) };
    (15, $($t:tt),+) => { big_type!(14, $($t, $t),+) };
    (16, $($t:tt),+) => { big_type!(15, $($t, $t),+) };
}

pub fn test(_: big_type!(13, _)) {}

As you suspected, the original issue was in <Ty as Clone>::clone(), which has since been fixed by #76985. In the ad-hoc notation I've been using to debug this issue, the recursive loop looked like this:

[compiler/rustc_ast/src/ast.rs] <Ty as Clone>::clone()
[compiler/rustc_ast/src/ast.rs] <TyKind as Clone>::clone()
[compiler/rustc_ast/src/ast.rs] <Path as Clone>::clone()
[library/alloc/src/vec.rs] <Vec<PathSegment> as Clone>::clone()
[...]
[compiler/rustc_ast/src/ast.rs] <PathSegment as Clone>::clone()
[library/core/src/option.rs] <Option<P<GenericArgs>> as Clone>::clone()
[compiler/rustc_ast/src/ptr.rs] <P<GenericArgs> as Clone>::clone()
[compiler/rustc_ast/src/ast.rs] <GenericArgs as Clone>::clone()
[compiler/rustc_ast/src/ast.rs] <AngleBracketedArgs as Clone>::clone()
[library/alloc/src/vec.rs] <Vec<AngleBracketedArg> as Clone>::clone()
[...]
[compiler/rustc_ast/src/ast.rs] <AngleBracketedArg as Clone>::clone()
[compiler/rustc_ast/src/ast.rs] <GenericArg as Clone>::clone()
[compiler/rustc_ast/src/ptr.rs] <P<Ty> as Clone>::clone()
[compiler/rustc_ast/src/ast.rs] <Ty as Clone>::clone()

However, if we want the compiler to support deeply nested types such as these, there are several other recursive loops which need to be broken up with ensure_sufficient_stack(). To begin, I tested the remainder of these loops with a more direct macro recursion:

#![recursion_limit = "1000000000"]

pub struct Test<T>(T);

macro_rules! big_type {
    (0, $t:ty) => { Test<$t> };
    (1, $t:ty) => { big_type!(0, big_type!(0, $t)) };
    (2, $t:ty) => { big_type!(1, big_type!(1, $t)) };
    (3, $t:ty) => { big_type!(2, big_type!(2, $t)) };
    (4, $t:ty) => { big_type!(3, big_type!(3, $t)) };
    (5, $t:ty) => { big_type!(4, big_type!(4, $t)) };
    (6, $t:ty) => { big_type!(5, big_type!(5, $t)) };
    (7, $t:ty) => { big_type!(6, big_type!(6, $t)) };
    (8, $t:ty) => { big_type!(7, big_type!(7, $t)) };
    (9, $t:ty) => { big_type!(8, big_type!(8, $t)) };
    (10, $t:ty) => { big_type!(9, big_type!(9, $t)) };
    (11, $t:ty) => { big_type!(10, big_type!(10, $t)) };
    (12, $t:ty) => { big_type!(11, big_type!(11, $t)) };
    (13, $t:ty) => { big_type!(12, big_type!(12, $t)) };
    (14, $t:ty) => { big_type!(13, big_type!(13, $t)) };
    (15, $t:ty) => { big_type!(14, big_type!(14, $t)) };
    (16, $t:ty) => { big_type!(15, big_type!(15, $t)) };
}

pub fn test(_: big_type!(12, ())) {}

For whatever reason, this didn't trigger the original <Ty as Clone>::clone() crash. However, it did cause rustc to crash on this loop:

[compiler/rustc_ast_lowering/src/lib.rs] LoweringContext::lower_ty_direct()
[compiler/rustc_ast_lowering/src/lib.rs] LoweringContext::lower_path_ty()
[compiler/rustc_ast_lowering/src/path.rs] LoweringContext::lower_qpath()
[...]
[compiler/rustc_ast_lowering/src/path.rs] LoweringContext::lower_qpath::{closure@37}()
[compiler/rustc_ast_lowering/src/path.rs] LoweringContext::lower_path_segment()
[compiler/rustc_ast_lowering/src/path.rs] LoweringContext::lower_angle_bracketed_parameter_data()
[...]
[compiler/rustc_ast_lowering/src/path.rs] LoweringContext::lower_angle_bracketed_parameter_data::{closure@381}()
[compiler/rustc_ast_lowering/src/lib.rs] LoweringContext::lower_generic_arg()
[compiler/rustc_ast_lowering/src/lib.rs] LoweringContext::lower_ty_direct()

When I added ensure_sufficient_stack() to LoweringContext::lower_ty_direct(), rustc crashed on this loop:

[compiler/rustc_resolve/src/late/lifetimes.rs] <LifetimeContext as Visitor>::visit_ty()
[compiler/rustc_resolve/src/late/lifetimes.rs] <LifetimeContext as Visitor>::visit_path()
[compiler/rustc_resolve/src/late/lifetimes.rs] LifetimeContext::visit_segment_args()
[compiler/rustc_resolve/src/late/lifetimes.rs] LifetimeContext::with<LifetimeContext::visit_segment_args::{closure@2544}>()
[compiler/rustc_resolve/src/late/lifetimes.rs] LifetimeContext::visit_segment_args::{closure@2544}()
[compiler/rustc_resolve/src/late/lifetimes.rs] <LifetimeContext as Visitor>::visit_ty()

When I added ensure_sufficient_stack() to <LifetimeContext as Visitor>::visit_ty(), rustc crashed on this loop:

[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::ast_ty_to_ty()
[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::ast_ty_to_ty_inner()
[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::res_to_ty()
[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::ast_path_to_ty()
[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::ast_path_substs_for_ty()
[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::create_substs_for_ast_path()
[compiler/rustc_typeck/src/astconv/generics.rs] <dyn AstConv>::create_substs_for_generic_args()
[compiler/rustc_typeck/src/astconv/mod.rs] <<dyn AstConv>::create_substs_for_ast_path::SubstsForAstPathCtxt as CreateSubstsForGenericArgsCtxt>::provided_kind()
[compiler/rustc_typeck/src/astconv/mod.rs] <dyn AstConv>::ast_ty_to_ty()

When I added ensure_sufficient_stack() to <dyn AstConv>::ast_ty_to_ty_inner(), rustc crashed on this loop:

[compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs] metadata::type_metadata()
[compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs] RecursiveTypeDescription::finalize()
[compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs] MemberDescriptionFactory::create_member_descriptions()
[compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs] StructMemberDescriptionFactory::create_member_descriptions()
[...]
[compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs] StructMemberDescriptionFactory::create_member_descriptions::{closure@1223}()
[compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs] metadata::type_metadata()

When I added ensure_sufficient_stack() to metadata::type_metadata(), rustc crashed on this loop:

[compiler/rustc_query_system/src/dep_graph/graph.rs] DepGraph::<DepKind>::try_mark_previous_green::<QueryCtxt>()
[compiler/rustc_query_system/src/dep_graph/graph.rs] DepGraph::<DepKind>::try_mark_parent_green::<QueryCtxt>()
[compiler/rustc_query_system/src/dep_graph/graph.rs] DepGraph::<DepKind>::try_mark_previous_green::<QueryCtxt>()

When I added ensure_sufficient_stack() to DepGraph::try_mark_parent_green(), rustc crashed on this loop:

[compiler/rustc_codegen_ssa/src/debuginfo/type_names.rs] type_names::push_debuginfo_type_name()
[compiler/rustc_codegen_ssa/src/debuginfo/type_names.rs] type_names::push_generic_params_internal()
[compiler/rustc_codegen_ssa/src/debuginfo/type_names.rs] type_names::push_debuginfo_type_name()

When I added ensure_sufficient_stack() to type_names::push_debuginfo_type_name(), rustc crashed on this loop:

[compiler/rustc_middle/src/ty/print/mod.rs] <Ty as Print<FmtPrinter<&mut Formatter>>>::print()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as PrettyPrinter>::pretty_print_type()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as Printer>::print_def_path()
[compiler/rustc_middle/src/ty/print/mod.rs] <FmtPrinter<&mut Formatter> as Printer>::default_print_def_path()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as Printer>::path_generic_args()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as PrettyPrinter>::generic_delimiters()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as Printer>::path_generic_args::{closure@1568}()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as PrettyPrinter>::path_generic_args::{closure@1568}()
[compiler/rustc_middle/src/ty/print/pretty.rs] <FmtPrinter<&mut Formatter> as PrettyPrinter>::comma_sep<FmtPrinter<&mut Formatter>, GenericArg, Filter<Cloned<Iter<GenericArg>>, <FmtPrinter<&mut Formatter> as Printer>::path_generic_args::{closure@1568}>>()
[compiler/rustc_middle/src/ty/print/pretty.rs] <GenericArgs as Print<FmtPrinter<&mut Formatter>>>::print()
[compiler/rustc_middle/src/ty/print/mod.rs] <Ty as Print<FmtPrinter<&mut Formatter>>>::print()

When I added ensure_sufficient_stack() to PrettyPrinter::pretty_print_type(), rustc crashed on this loop:

[compiler/rustc_codegen_llvm/src/type_of.rs] <TyAndLayout as LayoutLlvmExt>::llvm_type()
[compiler/rustc_codegen_llvm/src/type_of.rs] type_of::struct_llfields()
[compiler/rustc_codegen_llvm/src/type_of.rs] <TyAndLayout as LayoutLlvmExt>::llvm_type()

When I added ensure_sufficient_stack() to <TyAndLayout as LayoutLlvmExt>::llvm_type(), rustc crashed on this loop in LLVM:

[src/llvm-project/llvm/lib/IR/Verifier.cpp] Verifier::visitMDNode()
[src/llvm-project/llvm/lib/IR/Verifier.cpp] Verifier::visitMDNode()

This loop would be tricky to fix; as a quick hack, I re-exported the stacker crate as rustc_data_structures::stack::stacker and added stacker::grow(16 * 1024 * 1024, ...) around the call to llvm::LLVMRustWriteOutputFile() in rustc_codegen_llvm::back::write::write_output_file(). When I did that, rustc was able to successfully build the library.


I also tested some variations on the second program. Most of them hit the same recursive loops as the original, but two of them revealed some new problematic loops. The first was this one:

#![recursion_limit = "1000000000"]

pub trait Trait { type Type; }
impl<T> Trait for T { type Type = Self; }

macro_rules! big_type {
    (0, $t:ty) => { <$t as Trait>::Type };
    (1, $t:ty) => { big_type!(0, big_type!(0, $t)) };
    (2, $t:ty) => { big_type!(1, big_type!(1, $t)) };
    (3, $t:ty) => { big_type!(2, big_type!(2, $t)) };
    (4, $t:ty) => { big_type!(3, big_type!(3, $t)) };
    (5, $t:ty) => { big_type!(4, big_type!(4, $t)) };
    (6, $t:ty) => { big_type!(5, big_type!(5, $t)) };
    (7, $t:ty) => { big_type!(6, big_type!(6, $t)) };
    (8, $t:ty) => { big_type!(7, big_type!(7, $t)) };
    (9, $t:ty) => { big_type!(8, big_type!(8, $t)) };
    (10, $t:ty) => { big_type!(9, big_type!(9, $t)) };
    (11, $t:ty) => { big_type!(10, big_type!(10, $t)) };
    (12, $t:ty) => { big_type!(11, big_type!(11, $t)) };
    (13, $t:ty) => { big_type!(12, big_type!(12, $t)) };
    (14, $t:ty) => { big_type!(13, big_type!(13, $t)) };
    (15, $t:ty) => { big_type!(14, big_type!(14, $t)) };
    (16, $t:ty) => { big_type!(15, big_type!(15, $t)) };
}

pub fn test(_: big_type!(13, ())) {}

When I attempted to compile it with the fixes above, rustc crashed on this loop:

[compiler/rustc_trait_selection/src/traits/project.rs] <AssocTypeNormalizer as TypeFolder>::fold_ty()
[compiler/rustc_middle/src/ty/structural_impls.rs] <Ty as TypeFoldable>::super_fold_with::<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/fold.rs] <ProjectionTy as TypeFoldable>::fold_with<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/sty.rs] <ProjectionTy as TypeFoldable>::super_fold_with<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/fold.rs] <SubstsRef as TypeFoldable>::fold_with<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/subst.rs] <SubstsRef as TypeFoldable>::super_fold_with<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/fold.rs] <GenericArg as TypeFoldable>::fold_with<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/subst.rs] <GenericArg as TypeFoldable>::super_fold_with<AssocTypeNormalizer>()
[compiler/rustc_middle/src/ty/structural_impls.rs] <Ty as TypeFoldable>::fold_with::<AssocTypeNormalizer>()
[compiler/rustc_trait_selection/src/traits/project.rs] <AssocTypeNormalizer as TypeFolder>::fold_ty()

This was fixed when I added ensure_sufficient_stack() to <AssocTypeNormalizer as TypeFolder>::fold_ty().


After that, I tried a variation with deeply nested expressions, which was the second variation that yielded new recursive loops:

#![recursion_limit = "1000000000"]

macro_rules! big_expr {
    (0, $e:expr) => { ($e) };
    (1, $e:expr) => { big_expr!(0, big_expr!(0, $e)) };
    (2, $e:expr) => { big_expr!(1, big_expr!(1, $e)) };
    (3, $e:expr) => { big_expr!(2, big_expr!(2, $e)) };
    (4, $e:expr) => { big_expr!(3, big_expr!(3, $e)) };
    (5, $e:expr) => { big_expr!(4, big_expr!(4, $e)) };
    (6, $e:expr) => { big_expr!(5, big_expr!(5, $e)) };
    (7, $e:expr) => { big_expr!(6, big_expr!(6, $e)) };
    (8, $e:expr) => { big_expr!(7, big_expr!(7, $e)) };
    (9, $e:expr) => { big_expr!(8, big_expr!(8, $e)) };
    (10, $e:expr) => { big_expr!(9, big_expr!(9, $e)) };
    (11, $e:expr) => { big_expr!(10, big_expr!(10, $e)) };
    (12, $e:expr) => { big_expr!(11, big_expr!(11, $e)) };
    (13, $e:expr) => { big_expr!(12, big_expr!(12, $e)) };
    (14, $e:expr) => { big_expr!(13, big_expr!(13, $e)) };
    (15, $e:expr) => { big_expr!(14, big_expr!(14, $e)) };
    (16, $e:expr) => { big_expr!(15, big_expr!(15, $e)) };
}

pub const TEST: () = big_expr!(16, ());

It caused rustc to crash on this loop:

[compiler/rustc_ast_passes/src/ast_validation.rs] <AstValidator as Visitor>::visit_expr()
[compiler/rustc_ast/src/visit.rs] visit::walk_expr::<AstValidator>()
[compiler/rustc_ast_passes/src/ast_validation.rs] <AstValidator as Visitor>::visit_expr()

When I added ensure_sufficient_stack() to visit::walk_expr(), rustc crashed on this loop:

[library/core/src/ptr/mod.rs] ptr::drop_in_place<Expr>()
[library/core/src/ptr/mod.rs] ptr::drop_in_place<ExprKind>()
[library/core/src/ptr/mod.rs] ptr::drop_in_place<P<Expr>>()
[library/core/src/ptr/mod.rs] ptr::drop_in_place<Box<Expr>>()
[library/core/src/ptr/mod.rs] ptr::drop_in_place<Expr>()

This loop was a real pain to fix, since one can't just add ensure_sufficient_stack() to a Drop::drop() implementation. I eventually decided that I needed to wrap one of the offending fields in a ManuallyDrop<_>, then call ensure_sufficient_stack(|| unsafe { ManuallyDrop::drop(&mut self.field) }) within a drop() implementation. Since P<_> is the only type of the three that isn't regularly destructured, I decided to replace its ptr: Box<T> with a ptr: ManuallyDrop<Box<T>> and implement <P<_> as Drop>::drop(). This required some additional unsafe code in functions that extract the contained value. Once I did that, rustc successfully compiled the library.


I plan on putting these fixes into a PR, but I have a few questions I'd like to ask first.