Infinite loop in type inference

konnorandrews commented 2 months ago

I tried this code:

struct F<A, O>(fn(A) -> O);

trait Fun {
    type O;
    type A;
}

impl<A, O> Fun for F<A, O> {
    type O = O;
    type A = A;
}

trait Gen {
    type B;
}

fn a() {
    b(F(c))
}

fn b<G, B>(_: G)
where
    G: Fun<A = B>,
    <G as Fun>::O: Gen<B = B>,
{
}

fn c<T>(_: T) -> impl Gen {}

Rust Explorer

I expected to see this happen: This code should fail to compile with errors.

Instead, this happened: Rustc enters a infinite loop and uses memory until the user or OS kills it.

Meta

rustc --version --verbose:

rustc 1.81.0-nightly (8fcd4dd08 2024-06-18)
binary: rustc
commit-hash: 8fcd4dd08e2ba3e922d917d819ba0be066bdb005
commit-date: 2024-06-18
host: x86_64-unknown-linux-gnu
release: 1.81.0-nightly
LLVM version: 18.1.7

cargo bisect-rustc

Regression in nightly-2023-12-06

The following backtrace was generated by attaching to a running rustc instance and dumping the call stack as it was when the debugger was attached.

Backtrace

``` Thread 3 (Thread 0x7f3869fff6c0 (LWP 14473) "rustc"): #0 0x00007f3873eee2a5 in ::intern_ty () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #1 0x00007f38778b7207 in ::next_ty_var_in_universe () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #2 0x00007f387746420e in >::tys::{closure#0} () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #3 0x00007f3877454d3d in >::tys () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #4 0x00007f38740a7e71 in ::process_obligation () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #5 0x00007f3877408b1f in >::process_obligations:: () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #6 0x00007f38743d03d0 in ::confirm_builtin_call () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #7 0x00007f387803bc7e in ::check_expr_with_expectation_and_args () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #8 0x00007f3878036f14 in ::check_block_with_expected () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #9 0x00007f387803c421 in ::check_expr_with_expectation_and_args () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #10 0x00007f38776da6ee in rustc_hir_typeck[a8fa972dab75dcd1]::check::check_fn () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #11 0x00007f38776d067e in rustc_hir_typeck[a8fa972dab75dcd1]::typeck () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #12 0x00007f38776d00fb in rustc_query_impl[606e62fa16b19c12]::plumbing::__rust_begin_short_backtrace::> () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #13 0x00007f38775bceee in rustc_query_system[ea7bd5a7968c1f8]::query::plumbing::try_execute_query::>, false: bool, false: bool, false: bool>, rustc_query_impl[606e62fa16b19c12]::plumbing::QueryCtxt, false: bool> () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #14 0x00007f38775bb9eb in rustc_query_impl[606e62fa16b19c12]::query_impl::typeck::get_query_non_incr::__rust_end_short_backtrace () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #15 0x00007f38775bb621 in ::par_body_owners::::{closure#0} () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #16 0x00007f38775ba0c7 in rustc_hir_analysis[738c88335a519906]::check_crate () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #17 0x00007f3877e14687 in rustc_interface[98f3030eb7c197c2]::passes::analysis () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #18 0x00007f3877e141c7 in rustc_query_impl[606e62fa16b19c12]::plumbing::__rust_begin_short_backtrace::> () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #19 0x00007f3878238725 in rustc_query_system[ea7bd5a7968c1f8]::query::plumbing::try_execute_query::>, false: bool, false: bool, false: bool>, rustc_query_impl[606e62fa16b19c12]::plumbing::QueryCtxt, false: bool> () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #20 0x00007f387823848f in rustc_query_impl[606e62fa16b19c12]::query_impl::analysis::get_query_non_incr::__rust_end_short_backtrace () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #21 0x00007f38780dc512 in rustc_interface[98f3030eb7c197c2]::interface::run_compiler::, rustc_driver_impl[df262410c7f7944d]::run_compiler::{closure#0}>::{closure#1} () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #22 0x00007f3878091d49 in std[82c32ede93c8c228]::sys::backtrace::__rust_begin_short_backtrace:: for more, q to quit, c to continue without paging-- [98f3030eb7c197c2]::interface::run_compiler, rustc_driver_impl[df262410c7f7944d]::run_compiler::{closure#0}>::{closure#1}, core[4db8349ac6a0c205]::result::Result<(), rustc_span[2c9242bd6e97c416]::ErrorGuaranteed>>::{closure#0}, core[4db8349ac6a0c205]::result::Result<(), rustc_span[2c9242bd6e97c416]::ErrorGuaranteed>>::{closure#0}::{closure#0}, core[4db8349ac6a0c205]::result::Result<(), rustc_span[2c9242bd6e97c416]::ErrorGuaranteed>> () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #23 0x00007f3878091afa in <::spawn_unchecked_, rustc_driver_impl[df262410c7f7944d]::run_compiler::{closure#0}>::{closure#1}, core[4db8349ac6a0c205]::result::Result<(), rustc_span[2c9242bd6e97c416]::ErrorGuaranteed>>::{closure#0}, core[4db8349ac6a0c205]::result::Result<(), rustc_span[2c9242bd6e97c416]::ErrorGuaranteed>>::{closure#0}::{closure#0}, core[4db8349ac6a0c205]::result::Result<(), rustc_span[2c9242bd6e97c416]::ErrorGuaranteed>>::{closure#2} as core[4db8349ac6a0c205]::ops::function::FnOnce<()>>::call_once::{shim:vtable#0} () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #24 0x00007f38797908eb in alloc::boxed::{impl#48}::call_once<(), dyn core::ops::function::FnOnce<(), Output=()>, alloc::alloc::Global> () at library/alloc/src/boxed.rs:2062 #25 alloc::boxed::{impl#48}::call_once<(), alloc::boxed::Box, alloc::alloc::Global>, alloc::alloc::Global> () at library/alloc/src/boxed.rs:2062 #26 std::sys::pal::unix::thread::{impl#2}::new::thread_start () at library/std/src/sys/pal/unix/thread.rs:108 #27 0x00007f3872aae068 in ?? () from /lib64/libc.so.6 #28 0x00007f3872b2f0bc in ?? () from /lib64/libc.so.6 Thread 2 (Thread 0x7f386a7ff6c0 (LWP 14472) "ctrl-c"): #0 0x00007f3872b1d74e in read () from /lib64/libc.so.6 #1 0x00007f38781e2f12 in nix[891d26199dd147b8]::unistd::read () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #2 0x00007f38781e2e36 in std[82c32ede93c8c228]::sys::backtrace::__rust_begin_short_backtrace::::{closure#0}, ()> () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #3 0x00007f38781e2d61 in <::spawn_unchecked_::{closure#0}, ()>::{closure#2} as core[4db8349ac6a0c205]::ops::function::FnOnce<()>>::call_once::{shim:vtable#0} () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #4 0x00007f38797908eb in alloc::boxed::{impl#48}::call_once<(), dyn core::ops::function::FnOnce<(), Output=()>, alloc::alloc::Global> () at library/alloc/src/boxed.rs:2062 #5 alloc::boxed::{impl#48}::call_once<(), alloc::boxed::Box, alloc::alloc::Global>, alloc::alloc::Global> () at library/alloc/src/boxed.rs:2062 #6 std::sys::pal::unix::thread::{impl#2}::new::thread_start () at library/std/src/sys/pal/unix/thread.rs:108 #7 0x00007f3872aae068 in ?? () from /lib64/libc.so.6 #8 0x00007f3872b2f0bc in ?? () from /lib64/libc.so.6 Thread 1 (Thread 0x7f387967f580 (LWP 14471) "rustc"): #0 0x00007f3872aaabd6 in ?? () from /lib64/libc.so.6 #1 0x00007f3872aafa83 in ?? () from /lib64/libc.so.6 #2 0x00007f3879790a41 in std::sys::pal::unix::thread::Thread::join () at library/std/src/sys/pal/unix/thread.rs:272 #3 0x00007f38781fde6a in rustc_driver_impl[df262410c7f7944d]::run_compiler () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #4 0x00007f38781fcbb8 in rustc_driver_impl[df262410c7f7944d]::main () from /home/konnor/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/librustc_driver-802b4aa580d71496.so #5 0x000056535a57ac07 in rustc_main[2a842e528cc0f9db]::main () #6 0x000056535a57abf3 in std[82c32ede93c8c228]::sys::backtrace::__rust_begin_short_backtrace:: () #7 0x000056535a57abe9 in ::{closure#0} as core[4db8349ac6a0c205]::ops::function::FnOnce<()>>::call_once::{shim:vtable#0} () #8 0x00007f3879768662 in core::ops::function::impls::{impl#2}::call_once<(), (dyn core::ops::function::Fn<(), Output=i32> + core::marker::Sync + core::panic::unwind_safe::RefUnwindSafe)> () at library/core/src/ops/function.rs:284 #9 std::panicking::try::do_call<&(dyn core::ops::function::Fn<(), Output=i32> + core::marker::Sync + core::panic::unwind_safe::RefUnwindSafe), i32> () at library/std/src/panicking.rs:553 #10 std::panicking::try + core::marker::Sync + core::panic::unwind_safe::RefUnwindSafe)> () at library/std/src/panicking.rs:517 #11 std::panic::catch_unwind<&(dyn core::ops::function::Fn<(), Output=i32> + core::marker::Sync + core::panic::unwind_safe::RefUnwindSafe), i32> () at library/std/src/panic.rs:350 #12 std::rt::lang_start_internal::{closure#2} () at library/std/src/rt.rs:141 #13 std::panicking::try::do_call () at library/std/src/panicking.rs:553 #14 std::panicking::try () at library/std/src/panicking.rs:517 #15 std::panic::catch_unwind () at library/std/src/panic.rs:350 --Type for more, q to quit, c to continue without paging-- #16 std::rt::lang_start_internal () at library/std/src/rt.rs:141 #17 0x000056535a57ad27 in main () ```

konnorandrews commented 2 months ago

With nightly-2023-12-05 the extra error output is:

error[E0271]: type mismatch resolving `<impl Gen as Gen>::B == _`
  --> src/lib.rs:18:7
   |
18 |     b(F(c))
   |     - ^^^^ cyclic type of infinite size
   |     |
   |     required by a bound introduced by this call
   |
note: required by a bound in `b`
  --> src/lib.rs:24:24
   |
21 | fn b<G, B>(_: G)
   |    - required by a bound in this function
...
24 |     <G as Fun>::O: Gen<B = B>,
   |                        ^^^^^ required by this bound in `b`

veera-sivarajan commented 2 months ago

@rustbot label -needs-triage +T-compiler +A-traits +I-hang

This seems to compile with errors on -Znext-solver

pacak commented 2 months ago

https://github.com/rust-lang/rust/issues/125651#issuecomment-2171697460 - looks similar?

rust-lang / rust

Infinite loop in type inference #126664

Meta