Trait resolver hangs when evaluating cyclic requirement with lifetimes

[Noratrieb]

I tried this code:
https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=122bc8148cdc1e27553e68ca7c6d6253

use std::marker::PhantomData;

// a fancy trait
pub trait CoolTrait {}

// implement that trait for all reference to someone implementing the trait
impl<'a, D: CoolTrait> CoolTrait for &'a D {}

// a type with a lifetime
pub struct Parent<'a> {
    // We need a lifetime. otherwise, if we remove it, we get:
    // error[E0275]: overflow evaluating the requirement `A: CoolTrait`
    _boo: PhantomData<&'a ()>,
}

// two more types with a lifetime
pub struct A<'a> {
    _boo: PhantomData<&'a ()>,
}

pub struct B<'a> {
    _boo: PhantomData<&'a ()>,
}

// implement CoolTrait only when the two types themselves implement it
impl<'a> CoolTrait for Parent<'a>
where
    A<'a>: CoolTrait,
    B<'a>: CoolTrait,
{
}

// implement CoolTrait for the two types only when the Parent also implements it
// oh no! a cycle!
impl<'a> CoolTrait for A<'a> where Parent<'a>: CoolTrait {}
impl<'a> CoolTrait for B<'a> where Parent<'a>: CoolTrait {}

// now test whether CoolTrait is implemented for
pub fn foo(parent: Parent<'_>) {
    requires_parent_fulfill_cool_trait(parent);
}

pub fn requires_parent_fulfill_cool_trait(_: impl CoolTrait) {}

I expected to see this happen: Code does not compile and error out because of the cyclic requirement

Instead, this happened: rustc hangs

rustc --version --verbose:

rustc 1.62.0-nightly (3f391b845 2022-04-15)
binary: rustc
commit-hash: 3f391b84552f210adec7893b50c5da74f9362ae4
commit-date: 2022-04-15
host: x86_64-unknown-linux-gnu
release: 1.62.0-nightly
LLVM version: 14.0.0

I also tried running the same code with -Zchalk, it ICEs

Backtrace

<p>
error: internal compiler error: no errors encountered even though `delay_span_bug` issued

error: internal compiler error: broken MIR in DefId(0:33 ~ dilaria[17cd]::foo) (NoSolution): could not prove Binder(TraitPredicate(<Parent<'_> as CoolTrait>, polarity:Positive), [])
  |
  = note: delayed at compiler/rustc_borrowck/src/type_check/canonical.rs:149:13

thread 'rustc' panicked at 'Box<dyn Any>', compiler/rustc_errors/src/lib.rs:1383:13
stack backtrace:
   0:     0x7f2db8b0f84d - std::backtrace_rs::backtrace::libunwind::trace::hce19c90b92bd73af
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/std/src/../../backtrace/src/backtrace/libunwind.rs:93:5
   1:     0x7f2db8b0f84d - std::backtrace_rs::backtrace::trace_unsynchronized::h37e11f7a70fe2e93
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x7f2db8b0f84d - std::sys_common::backtrace::_print_fmt::h9a82c368c968b662
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/std/src/sys_common/backtrace.rs:66:5
   3:     0x7f2db8b0f84d - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h5ba9b1105ba53bd0
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/std/src/sys_common/backtrace.rs:45:22
   4:     0x7f2db8b6af3c - core::fmt::write::ha50f92e7d26c8f8e
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/core/src/fmt/mod.rs:1194:17
   5:     0x7f2db8b00fa1 - std::io::Write::write_fmt::h396eef3c560a16a9
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/std/src/io/mod.rs:1655:15
   6:     0x7f2db8b12565 - std::sys_common::backtrace::_print::h35ed08d4d805d2b3
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/std/src/sys_common/backtrace.rs:48:5
   7:     0x7f2db8b12565 - std::sys_common::backtrace::print::h50e1ed5ca96892de
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/std/src/sys_common/backtrace.rs:35:9
   8:     0x7f2db8b12565 - std::panicking::default_hook::{{closure}}::hc7e9cf4fa3684a1d
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/std/src/panicking.rs:295:22
   9:     0x7f2db8b121d9 - std::panicking::default_hook::h536ad2c4f0ac6e2e
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/std/src/panicking.rs:314:9
  10:     0x7f2db92b44f1 - rustc_driver[eab24f0126444cb8]::DEFAULT_HOOK::{closure#0}::{closure#0}
  11:     0x7f2db8b12d36 - std::panicking::rust_panic_with_hook::hb5f6d16b6f55acfb
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/std/src/panicking.rs:702:17
  12:     0x7f2dba3e7cf1 - std[4370f669910bc83b]::panicking::begin_panic::<rustc_errors[192e17d657890bb]::ExplicitBug>::{closure#0}
  13:     0x7f2dba3e65e6 - std[4370f669910bc83b]::sys_common::backtrace::__rust_end_short_backtrace::<std[4370f669910bc83b]::panicking::begin_panic<rustc_errors[192e17d657890bb]::ExplicitBug>::{closure#0}, !>
  14:     0x7f2dba3ff79f - std[4370f669910bc83b]::panicking::begin_panic::<rustc_errors[192e17d657890bb]::ExplicitBug>
  15:     0x7f2dba402716 - std[4370f669910bc83b]::panic::panic_any::<rustc_errors[192e17d657890bb]::ExplicitBug>
  16:     0x7f2dbbb9a587 - <rustc_errors[192e17d657890bb]::HandlerInner as core[4ac2a939107caa31]::ops::drop::Drop>::drop
  17:     0x7f2dbb2b06c8 - core[4ac2a939107caa31]::ptr::drop_in_place::<rustc_session[2ead2415dc439e52]::parse::ParseSess>
  18:     0x7f2dbb2b33a3 - <alloc[a10ef91e5af977a4]::rc::Rc<rustc_session[2ead2415dc439e52]::session::Session> as core[4ac2a939107caa31]::ops::drop::Drop>::drop
  19:     0x7f2dbb2dd65d - core[4ac2a939107caa31]::ptr::drop_in_place::<rustc_interface[9315513aeaeb57a1]::interface::Compiler>
  20:     0x7f2dbb2dcf54 - rustc_span[97e6a00764b526c]::with_source_map::<core[4ac2a939107caa31]::result::Result<(), rustc_errors[192e17d657890bb]::ErrorGuaranteed>, rustc_interface[9315513aeaeb57a1]::interface::create_compiler_and_run<core[4ac2a939107caa31]::result::Result<(), rustc_errors[192e17d657890bb]::ErrorGuaranteed>, rustc_driver[eab24f0126444cb8]::run_compiler::{closure#1}>::{closure#1}>
  21:     0x7f2dbb2b4dd7 - <scoped_tls[3ac5dbd4828c14b8]::ScopedKey<rustc_span[97e6a00764b526c]::SessionGlobals>>::set::<rustc_interface[9315513aeaeb57a1]::interface::run_compiler<core[4ac2a939107caa31]::result::Result<(), rustc_errors[192e17d657890bb]::ErrorGuaranteed>, rustc_driver[eab24f0126444cb8]::run_compiler::{closure#1}>::{closure#0}, core[4ac2a939107caa31]::result::Result<(), rustc_errors[192e17d657890bb]::ErrorGuaranteed>>
  22:     0x7f2dbb2ca19f - std[4370f669910bc83b]::sys_common::backtrace::__rust_begin_short_backtrace::<rustc_interface[9315513aeaeb57a1]::util::run_in_thread_pool_with_globals<rustc_interface[9315513aeaeb57a1]::interface::run_compiler<core[4ac2a939107caa31]::result::Result<(), rustc_errors[192e17d657890bb]::ErrorGuaranteed>, rustc_driver[eab24f0126444cb8]::run_compiler::{closure#1}>::{closure#0}, core[4ac2a939107caa31]::result::Result<(), rustc_errors[192e17d657890bb]::ErrorGuaranteed>>::{closure#0}, core[4ac2a939107caa31]::result::Result<(), rustc_errors[192e17d657890bb]::ErrorGuaranteed>>
  23:     0x7f2dbb2ca2e9 - <<std[4370f669910bc83b]::thread::Builder>::spawn_unchecked_<rustc_interface[9315513aeaeb57a1]::util::run_in_thread_pool_with_globals<rustc_interface[9315513aeaeb57a1]::interface::run_compiler<core[4ac2a939107caa31]::result::Result<(), rustc_errors[192e17d657890bb]::ErrorGuaranteed>, rustc_driver[eab24f0126444cb8]::run_compiler::{closure#1}>::{closure#0}, core[4ac2a939107caa31]::result::Result<(), rustc_errors[192e17d657890bb]::ErrorGuaranteed>>::{closure#0}, core[4ac2a939107caa31]::result::Result<(), rustc_errors[192e17d657890bb]::ErrorGuaranteed>>::{closure#1} as core[4ac2a939107caa31]::ops::function::FnOnce<()>>::call_once::{shim:vtable#0}
  24:     0x7f2db8b1cbe3 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::hfd8bbde0a7b593d1
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/alloc/src/boxed.rs:1866:9
  25:     0x7f2db8b1cbe3 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h74803de8f8876a22
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/alloc/src/boxed.rs:1866:9
  26:     0x7f2db8b1cbe3 - std::sys::unix::thread::Thread::new::thread_start::h2d9430691b39c114
                               at /rustc/3f391b84552f210adec7893b50c5da74f9362ae4/library/std/src/sys/unix/thread.rs:108:17
  27:     0x7f2db8a3d609 - start_thread
                               at /build/glibc-sMfBJT/glibc-2.31/nptl/pthread_create.c:477:8
  28:     0x7f2db8956163 - clone
  29:                0x0 - <unknown>

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.62.0-nightly (3f391b845 2022-04-15) running on x86_64-unknown-linux-gnu

note: compiler flags: --crate-type lib -C embed-bitcode=no -C debuginfo=2 -C linker=clang -C incremental -Z chalk

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

query stack during panic:
end of query stack
warning: `dilaria` (lib) generated 3 warnings
error: could not compile `dilaria`; 3 warnings emitted

Removing the lifetimes fixes the issue, and compilation fails with a trait resolution overflow. The lifetimes seem to be confusing the overflow checker.

[Noratrieb]

I will minimize this further later

[Noratrieb]

And it's properly minimized now!

[sebschmi]

Possibly related, my crate traitgraph 0.10.0 does not build with current nightly (bed05e9 2022-05-02), failing also with a "cycle detected"

It does build on stable 1.60.0 and beta though.

[Noratrieb]

I don't think it's related, this issue is broken on stable as well.

[Noratrieb]

Bisecting this examples shows that it started hanging in 1.7.0. Before, these lifetime where bounds were not possible and failed to compile. So this has been an issue forever.

[apiraino]

Assigning priority as discussed in the Zulip thread of the Prioritization Working Group.

@rustbot label -I-prioritize +P-medium