Thread 'rustc' has overflowed its stack on dumb program

[AuroransSolis]

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]

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

[nagisa]

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 <alloc::vec::Vec<T> 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 <rustc_ast::ast::Ty as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43962 0x00007f377c3edfa5 in <core::iter::adapters::Cloned<I> 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 <alloc::vec::Vec<T> 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 <rustc_ast::ptr::P<T> 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 <alloc::vec::Vec<T> 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 <rustc_ast::ast::Ty as core::clone::Clone>::clone () from /nix/store/abzy0mhcgwrayp99gas29l3d6dv0f46n-rust-1.47.0-nightly-2020-08-22-663d2f5cd/lib/librustc_driver-74e90dce13cbc5f5.so
#43967 0x00007f377c3edfa5 in <core::iter::adapters::Cloned<I> 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 <alloc::vec::Vec<T> 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 <rustc_ast::ptr::P<T> 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 <alloc::vec::Vec<T> 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 <rustc_ast::ast::Ty as core::clone::Clone>::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::<impl rustc_parse::parser::Parser>::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::<impl rustc_parse::parser::Parser>::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::<impl rustc_parse::parser::Parser>::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::<impl rustc_parse::parser::Parser>::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::<impl rustc_parse::parser::Parser>::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::<impl rustc_parse::parser::Parser>::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::<impl rustc_parse::parser::Parser>::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::<impl rustc_parse::parser::Parser>::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::<impl rustc_parse::parser::Parser>::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::<impl rustc_parse::parser::Parser>::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::<impl rustc_parse::parser::Parser>::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::<impl rustc_parse::parser::Parser>::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::<impl rustc_parse::parser::Parser>::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::<impl rustc_parse::parser::Parser>::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 <rustc_expand::mbe::macro_rules::MacroRulesMacroExpander as rustc_expand::base::TTMacroExpander>::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::<impl rustc_session::session::Session>::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<I,A,R>::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::<impl rustc_interface::interface::Compiler>::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<T>::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 <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once () at /rustc/663d2f5cd3163f17eddb74ee1e028d542255f21a/library/alloc/src/boxed.rs:1042
#44003 <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::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 <rustc_ast::ast::Ty as core::clone::Clone>::clone(). From the source code 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]

Hi. I'd like to work on this issue

[chansuke]

@rustbot claim

[hbina]

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]

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