Repository: rust
Issue: Rustc does not terminate on some inputs
Labels: A-trait-system,A-associated-items,T-compiler,C-bug,I-hang,fixed-by-next-solver

Consider the following piece of code:

```rust
struct A;
trait ALang {}

struct B;
trait BLang {}

trait FormatInto<L> {
    type Z;
}

impl<'a, L: ALang> FormatInto<L> for &'a A
where
    &'a A: FormatInto<L>,
    &'a B: FormatInto<L>,
{
    type Z = ();
}

impl<'a, L: BLang> FormatInto<L> for &'a B where &'a A: FormatInto<L> {
    type Z = ();
}

struct MyLang;

impl ALang for MyLang {}
impl BLang for MyLang {}

fn main() {
    let x: <&A as FormatInto<MyLang>>::Z = todo!();
}
```

On this input, `rustc` does not terminate (or at least not in a few minutes).

I'd expect the compiler to either succeed (although I don't know how that could happen here ;)) or to produce an error instead.

### Meta
<!--
If you're using the stable version of the compiler, you should also check if the
bug also exists in the beta or nightly versions.
-->

`rustc --version --verbose`:
```
rustc 1.60.0 (7737e0b5c 2022-04-04)
binary: rustc
commit-hash: 7737e0b5c4103216d6fd8cf941b7ab9bdbaace7c
commit-date: 2022-04-04
host: x86_64-unknown-linux-gnu
release: 1.60.0
LLVM version: 14.0.0
```
but the problem also happens on:
```
rustc 1.62.0-nightly (f4a7ce997 2022-04-08)
binary: rustc
commit-hash: f4a7ce997a1d7546d2b737f8b87d36907bcea2ad
commit-date: 2022-04-08
host: x86_64-unknown-linux-gnu
release: 1.62.0-nightly
LLVM version: 14.0.0
```

<!--
Include a backtrace in the code block by setting `RUST_BACKTRACE=1` in your
environment. E.g. `RUST_BACKTRACE=1 cargo build`.
-->
<details><summary>Backtrace</summary>
<p>
I couldn't get a backtrace with RUST_BACKTRACE, so I tried to get one with gdb after sending a SIGABRT to rustc

Thread 1:
```
#0  0x00007f541868015a in __futex_abstimed_wait_common () from /usr/lib/libc.so.6
#1  0x00007f54186850e4 in __pthread_clockjoin_ex () from /usr/lib/libc.so.6
#2  0x00007f54188a7dfd in std::sys::unix::thread::Thread::join () at library/std/src/sys/unix/thread.rs:244
#3  0x00007f541af21954 in <std::thread::JoinHandle<core::result::Result<(), rustc_errors::ErrorReported>>>::join ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#4  0x00007f541af1abd1 in rustc_interface::util::run_in_thread_pool_with_globals::<rustc_interface::interface::run_compiler<core::result::Result<(), rustc_errors::ErrorReported>, rustc_driver::run_compiler::{closure#1}>::{closure#0}, core::result::Result<(), rustc_errors::ErrorReported>> ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#5  0x00007f541af1c692 in <rustc_driver::RunCompiler>::run ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#6  0x00007f541aeedfd2 in <core::panic::unwind_safe::AssertUnwindSafe<rustc_driver::main::{closure#0}> as core::ops::function::FnOnce<()>>::call_once ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#7  0x00007f541af20c06 in rustc_driver::main () from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#8  0x00005597c9c05cbd in rustc_main::main ()
#9  0x00005597c9c05cf3 in std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()> ()
#10 0x00005597c9c05ca9 in _RNCINvNtCshCtCELAt55q_3std2rt10lang_startuE0Cs7s29dABgO2O_10rustc_main.llvm.2698179216631376293 ()
#11 0x00007f5418896ec1 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 /rustc/7737e0b5c4103216d6fd8cf941b7ab9bdbaace7c/library/core/src/ops/function.rs:259
#12 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:492
#13 std::panicking::try<i32, &(dyn core::ops::function::Fn<(), Output=i32> + core::marker::Sync + core::panic::unwind_safe::RefUnwindSafe)> ()
    at library/std/src/panicking.rs:456
#14 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:137
#15 std::rt::lang_start_internal::{closure#2} () at library/std/src/rt.rs:128
#16 std::panicking::try::do_call<std::rt::lang_start_internal::{closure_env#2}, isize> () at library/std/src/panicking.rs:492
#17 std::panicking::try<isize, std::rt::lang_start_internal::{closure_env#2}> () at library/std/src/panicking.rs:456
#18 std::panic::catch_unwind<std::rt::lang_start_internal::{closure_env#2}, isize> () at library/std/src/panic.rs:137
#19 std::rt::lang_start_internal () at library/std/src/rt.rs:128
#20 0x00005597c9c05ce1 in main ()
```

Thread 2:
```
#0  0x00007f541acda093 in <rustc_data_structures::obligation_forest::ObligationForest<rustc_trait_selection::traits::fulfill::PendingPredicateObligation>>::process_obligations::<rustc_trait_selection::traits::fulfill::FulfillProcessor, rustc_data_structures::obligation_forest::Outcome<rustc_trait_selection::traits::fulfill::PendingPredicateObligation, rustc_infer::traits::FulfillmentErrorCode>> () from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#1  0x00007f541acbc19b in <rustc_trait_selection::traits::fulfill::FulfillmentContext as rustc_infer::traits::engine::TraitEngine>::select_where_possible ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#2  0x00007f541a46a0c6 in <rustc_typeck::check::fn_ctxt::FnCtxt>::check_argument_types ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#3  0x00007f541a440a7d in <rustc_typeck::check::fn_ctxt::FnCtxt>::confirm_builtin_call ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#4  0x00007f541a43ddc2 in <rustc_typeck::check::fn_ctxt::FnCtxt>::check_call ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#5  0x00007f541a4826a0 in <rustc_typeck::check::fn_ctxt::FnCtxt>::check_expr_kind ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#6  0x00007f541a448c1c in _RNvMNtNtCs2qikOkRJ7XM_12rustc_typeck5check4exprNtNtB4_7fn_ctxt6FnCtxt36check_expr_with_expectation_and_args.llvm.15907926956116380612 ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#7  0x00007f541a46fbe8 in <rustc_typeck::check::fn_ctxt::FnCtxt>::check_decl ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#8  0x00007f541a4708c0 in <rustc_typeck::check::fn_ctxt::FnCtxt>::check_stmt ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#9  0x00007f541a47164d in <rustc_typeck::check::fn_ctxt::FnCtxt>::check_block_with_expected ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#10 0x00007f541a448c1c in _RNvMNtNtCs2qikOkRJ7XM_12rustc_typeck5check4exprNtNtB4_7fn_ctxt6FnCtxt36check_expr_with_expectation_and_args.llvm.15907926956116380612 ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#11 0x00007f541a584df9 in rustc_typeck::check::check::check_fn ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#12 0x00007f541a4f8bc1 in <rustc_infer::infer::InferCtxtBuilder>::enter::<&rustc_middle::ty::context::TypeckResults, <rustc_typeck::check::inherited::InheritedBuilder>::enter<rustc_typeck::check::typeck_with_fallback<rustc_typeck::check::typeck::{closure#0}>::{closure#1}, &rustc_middle::ty::context::TypeckResults>::{closure#0}> ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#13 0x00007f541a4d45c3 in _RNvNtCs2qikOkRJ7XM_12rustc_typeck5check6typeck.llvm.6351951424961696909 ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#14 0x00007f541a971855 in _RINvNtNtCshN7UadgbtaD_18rustc_query_system5query8plumbing17try_execute_queryNtNtCsbavfqmO6ojp_16rustc_query_impl8plumbing9QueryCtxtINtNtB4_6caches12DefaultCacheNtNtCs6sNr1nJAUA5_10rustc_span6def_id10LocalDefIdRNtNtNtCs12ixbLjc5mB_12rustc_middle2ty7context13TypeckResultsEEB1g_.llvm.17253906069082547043 ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#15 0x00007f541a9d05fc in <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::typeck ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#16 0x00007f541a535a7a in <rustc_middle::hir::map::Map>::par_body_owners::<rustc_typeck::check::typeck_item_bodies::{closure#0}> ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#17 0x00007f541b1a9e1c in _RNvNtCs2qikOkRJ7XM_12rustc_typeck5check18typeck_item_bodies.llvm.6351951424961696909 ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#18 0x00007f541b3def44 in _RINvNtNtCshN7UadgbtaD_18rustc_query_system5query8plumbing17try_execute_queryNtNtCsbavfqmO6ojp_16rustc_query_impl8plumbing9QueryCtxtINtNtB4_6caches12DefaultCacheuuEEB1g_.llvm.17253906069082547043 () from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#19 0x00007f541b406bc8 in rustc_query_system::query::plumbing::get_query::<rustc_query_impl::queries::typeck_item_bodies, rustc_query_impl::plumbing::QueryCtxt> ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#20 0x00007f541b1ae309 in <rustc_session::session::Session>::time::<(), rustc_typeck::check_crate::{closure#7}> ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#21 0x00007f541b1a25e3 in rustc_typeck::check_crate () from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#22 0x00007f541af3bed7 in rustc_interface::passes::analysis ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#23 0x00007f541b3d5973 in _RINvNtNtCshN7UadgbtaD_18rustc_query_system5query8plumbing17try_execute_queryNtNtCsbavfqmO6ojp_16rustc_query_impl8plumbing9QueryCtxtINtNtB4_6caches12DefaultCacheuINtNtCs3mGW1eWqUD1_4core6result6ResultuNtCsggHJhvleegr_12rustc_errors13ErrorReportedEEEB1g_.llvm.17253906069082547043 ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#24 0x00007f541b414c05 in rustc_query_system::query::plumbing::get_query::<rustc_query_impl::queries::analysis, rustc_query_impl::plumbing::QueryCtxt> ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#25 0x00007f541af1a608 in <rustc_interface::passes::QueryContext>::enter::<rustc_driver::run_compiler::{closure#1}::{closure#2}::{closure#3}, core::result::Result<(), rustc_errors::ErrorReported>> () from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#26 0x00007f541af08ac5 in rustc_interface::interface::create_compiler_and_run::<core::result::Result<(), rustc_errors::ErrorReported>, rustc_driver::run_compiler::{closure#1}> () from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#27 0x00007f541aeee134 in _RINvNtNtCshCtCELAt55q_3std10sys_common9backtrace28___rust_begin_short_backtraceNCINvNtCsf5CM6ndXTHU_15rustc_interface4util31run_in_thread_pool_with_globalsNCINvNtB1m_9interface12run_compilerINtNtCs3mGW1eWqUD1_4core6result6ResultuNtCsggHJhvleegr_12rustc_errors13ErrorReportedENCNvCs9wpKcMIcLY6_12rustc_driver12run_compilers_0E0B32_E0B32_EB4t_.llvm.15336006795362687796 () from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#28 0x00007f541af213e9 in <<std::thread::Builder>::spawn_unchecked_<rustc_interface::util::run_in_thread_pool_with_globals<rustc_interface::interface::run_compiler<core::result::Result<(), rustc_errors::ErrorReported>, rustc_driver::run_compiler::{closure#1}>::{closure#0}, core::result::Result<(), rustc_errors::ErrorReported>>::{closure#0}, core::result::Result<(), rustc_errors::ErrorReported>>::{closure#1} as core::ops::function::FnOnce<()>>::call_once::{shim:vtable#0} ()
   from /home/luca/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/bin/../lib/librustc_driver-75e5f32fc3580f6c.so
#29 0x00007f54188a7d03 in alloc::boxed::{impl#44}::call_once<(), dyn core::ops::function::FnOnce<(), Output=()>, alloc::alloc::Global> ()
    at /rustc/7737e0b5c4103216d6fd8cf941b7ab9bdbaace7c/library/alloc/src/boxed.rs:1853
#30 alloc::boxed::{impl#44}::call_once<(), alloc::boxed::Box<dyn core::ops::function::FnOnce<(), Output=()>, alloc::alloc::Global>, alloc::alloc::Global> ()
    at /rustc/7737e0b5c4103216d6fd8cf941b7ab9bdbaace7c/library/alloc/src/boxed.rs:1853
#31 std::sys::unix::thread::{impl#2}::new::thread_start () at library/std/src/sys/unix/thread.rs:108
#32 0x00007f54186835c2 in start_thread () from /usr/lib/libc.so.6
#33 0x00007f5418708584 in clone () from /usr/lib/libc.so.6
```

</p>
</details>