Rust: Rustc overflow its stack when using impl Trait and the struct containing the function itself

[lszxb]

I tried this code:

fn main() {
    test();
}

fn test() -> impl P {
    Lazy { f: test }
}

trait P {}

struct Lazy<F> {
    f: F
}

impl<F> P for Lazy<F> {}

Then I got thread 'rustc' has overflowed its stack.

Meta

rustc --version --verbose:

rustc 1.43.0-nightly (07a34df18 2020-02-08)
binary: rustc
commit-hash: 07a34df18b437319a7ff510077bbab95cf7ec6bc
commit-date: 2020-02-08
host: x86_64-pc-windows-gnu
release: 1.43.0-nightly
LLVM version: 9.0

[lzutao]

Infinite loop I think:

(gdb) bt
#0  0x00007ffff6966e15 in hashbrown::map::RawEntryBuilder<K,V,S>::from_key_hashed_nocheck () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-154376714aaee7fe.so
#1  0x00007ffff6d36f5e in rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-154376714aaee7fe.so
#2  0x00007ffff6a6a0c3 in rustc::ty::structural_impls::fold_list () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-154376714aaee7fe.so
#3  0x00007ffff6d00036 in rustc::ty::normalize_erasing_regions::<impl rustc::ty::context::TyCtxt>::normalize_erasing_late_bound_regions () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-154376714aaee7fe.so
#4  0x00007ffff6fd048a in rustc::ty::print::obsolete::DefPathBasedNames::push_type_name () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-154376714aaee7fe.so
#5  0x00007ffff6fd2d39 in rustc::ty::print::obsolete::DefPathBasedNames::push_generic_params () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-154376714aaee7fe.so
#6  0x00007ffff6fd1739 in rustc::ty::print::obsolete::DefPathBasedNames::push_type_name () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-154376714aaee7fe.so
#7  0x00007ffff6fd2d39 in rustc::ty::print::obsolete::DefPathBasedNames::push_generic_params () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-154376714aaee7fe.so
#8  0x00007ffff6fd1739 in rustc::ty::print::obsolete::DefPathBasedNames::push_type_name () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-154376714aaee7fe.so
#9  0x00007ffff6fd2d39 in rustc::ty::print::obsolete::DefPathBasedNames::push_generic_params () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-154376714aaee7fe.so
...
#182017 0x00007ffff6eddcce in rustc::ty::print::obsolete::DefPathBasedNames::push_type_name () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182018 0x00007ffff6eded19 in rustc::ty::print::obsolete::DefPathBasedNames::push_generic_params () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182019 0x00007ffff50016fc in <rustc_target::abi::TyLayout<&rustc::ty::TyS> as rustc_codegen_llvm::type_of::LayoutLlvmExt>::llvm_type () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182020 0x00007ffff4eb5188 in rustc_codegen_ssa::mir::operand::OperandRef<V>::new_zst () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182021 0x00007ffff4fbd16d in rustc_codegen_ssa::mir::codegen_mir::{{closure}} () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182022 0x00007ffff4fe5216 in <core::iter::adapters::chain::Chain<A,B> as core::iter::traits::iterator::Iterator>::fold () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182023 0x00007ffff4fb23f2 in <alloc::vec::Vec<T> as alloc::vec::SpecExtend<T,I>>::from_iter () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182024 0x00007ffff4fbc205 in rustc_codegen_ssa::mir::codegen_mir () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182025 0x00007ffff4ef2bfc in <rustc::mir::mono::MonoItem as rustc_codegen_ssa::mono_item::MonoItemExt>::define () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182026 0x00007ffff4e6859a in rustc_codegen_llvm::base::compile_codegen_unit::module_codegen () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182027 0x00007ffff4f1c8b0 in rustc::dep_graph::graph::DepGraph::with_task () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182028 0x00007ffff4e68164 in rustc_codegen_llvm::base::compile_codegen_unit () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182029 0x00007ffff4fec61f in rustc_codegen_ssa::base::codegen_crate () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182030 0x00007ffff4f297b5 in <rustc_codegen_llvm::LlvmCodegenBackend as rustc_codegen_utils::codegen_backend::CodegenBackend>::codegen_crate () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182031 0x00007ffff4deeccc in rustc_interface::passes::QueryContext::enter () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182032 0x00007ffff4d120bb in rustc_interface::queries::Queries::ongoing_codegen () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182033 0x00007ffff4bae7d3 in rustc_interface::interface::run_compiler_in_existing_thread_pool () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182034 0x00007ffff4b664bd in scoped_tls::ScopedKey<T>::set () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182035 0x00007ffff4bd3414 in syntax::attr::with_globals () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182036 0x00007ffff4b9df10 in std::sys_common::backtrace::__rust_begin_short_backtrace () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182037 0x00007ffff44ece67 in __rust_maybe_catch_panic () at src/libpanic_unwind/lib.rs:86
#182038 0x00007ffff4bb0c36 in core::ops::function::FnOnce::call_once{{vtable-shim}} () from /home/lzutao/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-d8719fb60c037747.so
#182039 0x00007ffff44b846f in <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once () at /rustc/a1912f2e89b77cfe2a0e64b96f444848fe4e2d49/src/liballoc/boxed.rs:1017
#182040 0x00007ffff44eb770 in <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once () at /rustc/a1912f2e89b77cfe2a0e64b96f444848fe4e2d49/src/liballoc/boxed.rs:1017
#182041 std::sys_common::thread::start_thread () at src/libstd/sys_common/thread.rs:13
#182042 std::sys::unix::thread::Thread::new::thread_start () at src/libstd/sys/unix/thread.rs:80
#182043 0x00007ffff4433fa3 in start_thread (arg=<optimized out>) at pthread_create.c:486
#182044 0x00007ffff43534cf in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95
(gdb)

[Centril]

Godbolt says this regressed in 1.30.0 and used to compile fine in 1.29.0.

[nikomatsakis]

@rustbot ping icebreakers-cleanup-crew

There is already a minimal example here, but it'd be great to figure out the PR (or at least nightly) that caused it regress.

[rustbot]

Hey Cleanup Crew ICE-breakers! This bug has been identified as a good
"Cleanup ICE-breaking candidate". In case it's useful, here are some
[instructions] for tackling these sorts of bugs. Maybe take a look?
Thanks! <3

cc @AminArria @chrissimpkins @DutchGhost @ethanboxx @h-michael @HallerPatrick @hdhoang @hellow554 @matheus-consoli @mental32 @Noah-Kennedy @pard68 @pierreN @robjtede @senden9 @shekohex @sinato @spastorino @turboladen @woshilapin @yerke

[nikomatsakis]

Tagging as P-high since this is a regression, though it might be considered P-medium otherwise (not an active soundness hole, for example).

[eddyb]

Looks like this is in rustc::ty::print::obsolete::DefPathBasedNames, which we want to get rid of anyway, I'm not surprised it's buggy.

More specifically, it looks like it's overflowing the stack while trying to generate a name for a LLVM type.

cc @rust-lang/wg-codegen Should we make LLVM type names respect -Zfewer-names?
(which defaults to true unless --emit=llvm-ir is used)

[nagisa]

Should we make LLVM type names respect -Zfewer-names?

Yes, the whole point of this option is to produce as lean LLVM-IR as possible -- to reduce the peak memory use first and foremost. This means no variable names, no label names and I don't see how type names are in any way unique here that would warrant keeping them.

[chrissimpkins]

Edit: this appears to be an incorrect identification of a regression due to https://github.com/rust-lang/rust/issues/69096#issuecomment-585882046. See @HallerPatrick comment in https://github.com/rust-lang/rust/issues/69096#issuecomment-585965841

---

cargo-bisect-rustc indicates that the stack overflow is first seen on the 2019-07-31 nightly:

cargo bisect-rustc --start 2019-07-30 --end 2019-07-31 --prompt

cargo-bisect-rustc

cargo bisect-rustc --start 2019-07-30 --end 2019-07-31 --prompt
checking nightly-2019-07-30
std for x86_64-unknown-linux-gnu: 170.30 MB / 170.30 MB [====================================] 100.00 % 17.04 MB/s 0s    Compiling bisectit v0.7.0 (/home/chris/rust-testing/bisectit)
error: Unrecognized option: 'json'

error: could not compile `bisectit`.

To learn more, run the command again with --verbose.


nightly-2019-07-30 finished with exit code Some(101).
please select an action to take:
uninstalling nightly-2019-07-30
verifying the start of the range does not reproduce the regression
std for x86_64-unknown-linux-gnu: 170.30 MB / 170.30 MB [=======================================] 100.00 % 18.00 MB/s    Compiling bisectit v0.7.0 (/home/chris/rust-testing/bisectit)
error: Unrecognized option: 'json'

error: could not compile `bisectit`.

To learn more, run the command again with --verbose.


nightly-2019-07-30 finished with exit code Some(101).
please select an action to take:
uninstalling nightly-2019-07-30
tested nightly-2019-07-30, got No
confirmed the start of the range does not reproduce the regression
verifying the end of the range reproduces the regression
std for x86_64-unknown-linux-gnu: 170.30 MB / 170.30 MB [=======================================] 100.00 % 17.82 MB/s    Compiling bisectit v0.7.0 (/home/chris/rust-testing/bisectit)
warning: field is never used: `f`
  --> src/main.rs:12:5
   |
12 |     f: F
   |     ^^^^
   |
   = note: `#[warn(dead_code)]` on by default


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

Caused by:
  process didn't exit successfully: `rustc --crate-name bisectit --edition=2018 src/main.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type bin --emit=dep-info,link -C debuginfo=2 -C metadata=681c4a9b335b4202 -C extra-filename=-681c4a9b335b4202 --out-dir /home/chris/rust-testing/bisectit/target-bisector-nightly-2019-07-31-x86_64-unknown-linux-gnu/debug/deps -C incremental=/home/chris/rust-testing/bisectit/target-bisector-nightly-2019-07-31-x86_64-unknown-linux-gnu/debug/incremental -L dependency=/home/chris/rust-testing/bisectit/target-bisector-nightly-2019-07-31-x86_64-unknown-linux-gnu/debug/deps` (signal: 6, SIGABRT: process abort signal)


nightly-2019-07-31 finished with exit code Some(101).
please select an action to take:
uninstalling nightly-2019-07-31
tested nightly-2019-07-31, got Yes
confirmed the end of the range reproduces the regression
searched toolchains nightly-2019-07-30 through nightly-2019-07-31
std for x86_64-unknown-linux-gnu: 170.30 MB / 170.30 MB [=======================================] 100.00 % 17.69 MB/s    Compiling bisectit v0.7.0 (/home/chris/rust-testing/bisectit)
warning: field is never used: `f`
  --> src/main.rs:12:5
   |
12 |     f: F
   |     ^^^^
   |
   = note: `#[warn(dead_code)]` on by default


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

Caused by:
  process didn't exit successfully: `rustc --crate-name bisectit --edition=2018 src/main.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type bin --emit=dep-info,link -C debuginfo=2 -C metadata=681c4a9b335b4202 -C extra-filename=-681c4a9b335b4202 --out-dir /home/chris/rust-testing/bisectit/target-bisector-nightly-2019-07-31-x86_64-unknown-linux-gnu/debug/deps -C incremental=/home/chris/rust-testing/bisectit/target-bisector-nightly-2019-07-31-x86_64-unknown-linux-gnu/debug/incremental -L dependency=/home/chris/rust-testing/bisectit/target-bisector-nightly-2019-07-31-x86_64-unknown-linux-gnu/debug/deps` (signal: 6, SIGABRT: process abort signal)


nightly-2019-07-31 finished with exit code Some(101).
please select an action to take:
uninstalling nightly-2019-07-31
regression in nightly-2019-07-31
fetching https://static.rust-lang.org/dist/2019-07-31/channel-rust-nightly-git-commit-hash.txt
nightly manifest 2019-07-31: 40 B / 40 B [=====================================================] 100.00 % 266.46 KB/s converted 2019-07-31 to dddb7fca09dc817ba275602b950bb81a9032fb6d
fetching https://static.rust-lang.org/dist/2019-07-30/channel-rust-nightly-git-commit-hash.txt
nightly manifest 2019-07-30: 40 B / 40 B [=====================================================] 100.00 % 473.40 KB/s converted 2019-07-30 to 04b88a9eba8abbac87eddcb2998beea09589c2c9
looking for regression commit between 2019-07-31 and 2019-07-30
fetching commits from 04b88a9eba8abbac87eddcb2998beea09589c2c9 to dddb7fca09dc817ba275602b950bb81a9032fb6d
opening existing repository at "rust.git"
refreshing repository
looking up first commit
looking up second commit
checking that commits are by bors and thus have ci artifacts...
finding bors merge commits
found 4 bors merge commits in the specified range
opening existing repository at "rust.git"
refreshing repository
no commits between 04b88a9eba8abbac87eddcb2998beea09589c2c9 and dddb7fca09dc817ba275602b950bb81a9032fb6d within last 167 days

~ from 04b88a9eba8abbac87eddcb2998beea09589c2c9 to dddb7fca09dc817ba275602b950bb81a9032fb6d

I am seeing an error: Unrecognized option: 'json' error before that date but no stack overflow.

Source: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=3bd1c7e14f0d4cccccf9429346c0be5b

[eddyb]

I am seeing an error: Unrecognized option: 'json' error before that date but no stack overflow.

That suggests that you're using a Cargo too new or somehow back-compat logic was removed (or never present?) in Cargo (not sure what our policy is).

You need an older Cargo to go back past the addition of --json.

But also it would be nice if Cargo didn't need to be involved in the bisection process, because it IMO unnecessarily complicates it.

[chrissimpkins]

But also it would be nice if Cargo didn't need to be involved in the bisection process, because it IMO unnecessarily complicates it.

https://github.com/rust-lang/cargo-bisect-rustc/issues/49

[HallerPatrick]

So I tried to reproduce the overflow manually by going back to see where it firstly regressed, due to the rust-lang/cargo-bisect-rustc#49.

But couldn't find a working build yet...

The latest (youngest) build I tested now was 1.14.0-nightly, which is from 2016 and I was still able to reproduce the error. Had to add #![feature(conservative_impl_trait)] as impl Trait was experimental back then.

I don't think there is a build (nightly) that will compile this code correctly.

❯ rustc main.rs

warning: field is never used: `f`, #[warn(dead_code)] on by default
  --> main.rs:13:5
   |
13 |     f: F,
   |     ^^^^


thread 'rustc' has overflowed its stack
fatal runtime error: stack overflow
[1]    77863 abort      rustc main.rs

Meta

rustc --version --verbose:

rustc 1.14.0-nightly (a7bfb1aba 2016-10-09)
binary: rustc
commit-hash: a7bfb1aba9d089a0464c03b3841e889c6ee7c4f1
commit-date: 2016-10-09
host: x86_64-apple-darwin
release: 1.14.0-nightly

[eddyb]

@Centril Any chance you forgot to add pub? godbolt is always in library mode IIRC so there might not be enough codegen to reach the infinite recursion (and maybe we changed the rules when some things are codegen'd, especially around impl Trait)

[Centril]

@eddyb I copy pasted the code into godbolt so I didn't add pub.

[eddyb]

Godbolt says this regressed in 1.30.0 and used to compile fine in 1.29.0.

Just checked, this is what that looks like: https://godbolt.org/z/vc3D35

PSA: seeing <No assembly generated> in godbolt is a big warning sign.
It means you're accidentally not testing anything (at least codegen-wise).

Making main pub fn on 1.29.0 (keep in mind, godbolt always compiles a lib crate, not a bin one) results in this: https://godbolt.org/z/icX4pU (thread 'main' has overflowed its stack).

And it's the same on 1.26.0 (first stable w/ -> impl Trait): https://godbolt.org/z/WyuNsB.

This fits with https://github.com/rust-lang/rust/issues/69096#issuecomment-585965841, and I wish godbolt had nightly versions matching stable ones, or at least a way to pass env vars (because there's no real protection against abusing stable compilers).

[pnkfelix]

nominating for discussion as part of attempt to burn down set of unassigned P-high issues at an otherwise light triage meeting.

[pnkfelix]

discussed at T-compiler meeting. Reprioritizing as P-medium, since its not a true regression and not an active soundness hole.