Hang from infinitely-self-recursive trait alias

[wxie7]

I tried this code:

#![feature(trait_alias)]
#![feature(impl_trait_in_assoc_type)]
trait Foo {
    type Bar: Baz<Self, Self>;
    fn bar(&self) -> Self::Bar;
}
struct X;
impl Foo for X {
    type Bar = impl Baz<Self, Self>;
    fn bar(&self) -> Self::Bar {
        |x| x
    }
}
trait Baz<A: ?Sized, B: ?Sized> = Baz(&A) -> &B;
fn main() {}

It mutates from the following file, but the following code will not cause a hang.

#![feature(trait_alias)]
#![feature(impl_trait_in_assoc_type)]

trait Foo {
    type Bar: Baz<Self, Self>;

    fn bar(&self) -> Self::Bar;
}

struct X;

impl Foo for X {
    type Bar = impl Baz<Self, Self>;

    fn bar(&self) -> Self::Bar {
        |x| x
    }
}

trait Baz<A: ?Sized, B: ?Sized> = Fn(&A) -> &B;

fn main() {}

Also, I used impl_trait_in_assoc_type and Baz as search keywords but didn’t find any related issues with open.

Meta

rustc --version --verbose:

rustc 1.85.0-nightly (acabb5248 2024-12-04)
binary: rustc
commit-hash: acabb5248231987ae1f0c215208d1005a5db402d
commit-date: 2024-12-04
host: x86_64-unknown-linux-gnu
release: 1.85.0-nightly
LLVM version: 19.1.5

Backtrace

<backtrace>

[cyrgani]

Reduced:

trait Foo {
    type Bar: Baz<()>;
}
impl Foo for () {
    type Bar = ();
}
trait Baz<A> = Baz<&'static A>;

[theemathas]

Minimized:

#![feature(trait_alias)]
fn foo<T: Baz<i32>>() {}
trait Baz<A> = Baz<Option<A>>;

(Hangs without producing any errors or warnings. If the foo definition is moved after the Baz definition, then there's a cycle error before the hang.)

[jieyouxu]

Triage notes:

trait Foo {
    type Bar: Baz<()>;
}
impl Foo for () {
    type Bar = ();
}
trait Baz<A> = Baz<&'static A>;

hangs on stable (1.83) without the feature gate, which is a bit different from the other minimization which involves the feature gate

#![feature(trait_alias)]
fn foo<T: Baz<i32>>() {}
trait Baz<A> = Baz<Option<A>>;

[jieyouxu]

I feel like this probably is already reported but I can't find an earlier report.

[lqd]

I feel like this probably is already reported

I had the same feeling, we have many reports of superficially similar looking hangs. It could be interesting to bisect this one though, because this looks like a somewhat recent regression (from 1.78).

[lqd]

bisects to nightly-2024-03-09

• Add arm64ec-pc-windows-msvc target #119199 - dpaoliello:arm64ec, r=petrochenkov
• Rollup of 10 pull requests #122151 - GuillaumeGomez:rollup-hfxr9kv, r=GuillaumeGomez
• Use GEP inbounds for ZST and DST field offsets #122048 - erikdesjardins:inbounds, r=oli-obk
• Optimize write with as_const_str for shorter code #122059 - nyurik:with-as-const-str, r=cuviper
• Replace the default branch with an unreachable branch If it is the last variant #120268 - DianQK:otherwise_is_last_variant_switchs, r=oli-obk
• Rollup of 8 pull requests #122182 - matthiaskrgr:rollup-gzimi4c, r=matthiaskrgr
• Check that return type is WF in typeck #122078 - gurry:121443-ice-layout-is-sized-alt, r=oli-obk
• Merge collect_mod_item_types query into check_well_formed #121500 - oli-obk:track_errors12, r=petrochenkov
• Rollup of 8 pull requests #122190 - matthiaskrgr:rollup-9ol4y30, r=matthiaskrgr
• Rollup of 9 pull requests #122206 - matthiaskrgr:rollup-4txx9wx, r=matthiaskrgr

[lqd]

backtrace looks to be in wf checks so I'll just soft ping @oli-obk for #121500, but other PRs and rollups on that nightly also changed related codepaths in rustc_hir_analysis.

(gdb) bt
#0  0x00007ffff5eb7c5c in _RNvMs1E_NtNtCs19hci70W1NE_12rustc_middle2ty7contextNtB6_6TyCtxt7mk_args () from /checkout/obj/build/x86_64-unknown-linux-gnu/stage1/bin/../lib/librustc_driver-dd95e9de7e099d94.so
#1  0x00007ffff3b299b7 in _RINvXsh_NtNtCs19hci70W1NE_12rustc_middle2ty12generic_argsRINtNtB8_4list7RawListuNtB6_10GenericArgEINtNtCsf5lKsw415YT_13rustc_type_ir4fold12TypeFoldableNtNtB8_7context6TyCtxtE13try_fold_withNtNtNtCsga6qfZtIyPw_21rustc_trait_selection6traits9normalize19AssocTypeNormalizerECshAiFD47KJB4_18rustc_hir_analysis ()
   from /checkout/obj/build/x86_64-unknown-linux-gnu/stage1/bin/../lib/librustc_driver-dd95e9de7e099d94.so
#2  0x00007ffff397225d in _RINvXNvNtCsf5lKsw415YT_13rustc_type_ir14predicate_kinds4_1__INtB5_13PredicateKindNtNtNtCs19hci70W1NE_12rustc_middle2ty7context6TyCtxtEINtNtB7_4fold12TypeFoldableB1h_E13try_fold_withNtNtNtCsga6qfZtIyPw_21rustc_trait_selection6traits9normalize19AssocTypeNormalizerECshAiFD47KJB4_18rustc_hir_analysis ()
   from /checkout/obj/build/x86_64-unknown-linux-gnu/stage1/bin/../lib/librustc_driver-dd95e9de7e099d94.so
#3  0x00007ffff39c8fce in _RINvXsw_NtNtCs19hci70W1NE_12rustc_middle2ty16structural_implsNtNtB8_9predicate9PredicateINtNtCsf5lKsw415YT_13rustc_type_ir4fold17TypeSuperFoldableNtNtB8_7context6TyCtxtE19try_super_fold_withNtNtNtCsga6qfZtIyPw_21rustc_trait_selection6traits9normalize19AssocTypeNormalizerECshAiFD47KJB4_18rustc_hir_analysis ()
   from /checkout/obj/build/x86_64-unknown-linux-gnu/stage1/bin/../lib/librustc_driver-dd95e9de7e099d94.so
#4  0x00007ffff3a95bfc in _RINvNtNtCsga6qfZtIyPw_21rustc_trait_selection6traits9normalize20normalize_with_depthNtNtNtCs19hci70W1NE_12rustc_middle2ty9predicate9PredicateECshAiFD47KJB4_18rustc_hir_analysis ()
   from /checkout/obj/build/x86_64-unknown-linux-gnu/stage1/bin/../lib/librustc_driver-dd95e9de7e099d94.so
#5  0x00007ffff3aef8ec in _RINvXs0_NtNtCsga6qfZtIyPw_21rustc_trait_selection6traits9normalizeNtNtNtCsfBarEMO41MX_11rustc_infer5infer2at2AtNtB6_12NormalizeExt9normalizeNtNtNtCs19hci70W1NE_12rustc_middle2ty9predicate9PredicateECshAiFD47KJB4_18rustc_hir_analysis () from /checkout/obj/build/x86_64-unknown-linux-gnu/stage1/bin/../lib/librustc_driver-dd95e9de7e099d94.so
#6  0x00007ffff3b81fd8 in _RNvNtNtCshAiFD47KJB4_18rustc_hir_analysis5check17compare_impl_item17check_type_bounds ()
   from /checkout/obj/build/x86_64-unknown-linux-gnu/stage1/bin/../lib/librustc_driver-dd95e9de7e099d94.so
#7  0x00007ffff3b700a9 in _RNvNtNtCshAiFD47KJB4_18rustc_hir_analysis5check5check30check_impl_items_against_trait ()
   from /checkout/obj/build/x86_64-unknown-linux-gnu/stage1/bin/../lib/librustc_driver-dd95e9de7e099d94.so
#8  0x00007ffff3b66514 in _RNvNtNtCshAiFD47KJB4_18rustc_hir_analysis5check5check15check_item_type () from /checkout/obj/build/x86_64-unknown-linux-gnu/stage1/bin/../lib/librustc_driver-dd95e9de7e099d94.so
#9  0x00007ffff3aa091d in _RNvNtNtCshAiFD47KJB4_18rustc_hir_analysis5check7wfcheck17check_well_formed ()  

[oli-obk]

Trying to debug locally it got stuck in the debug-assert-only validation happening in Binder::bind_with_vars 😆

[oli-obk]

Ok, so it's not an infinite recursion, just an infinite loop growing a value linearly that is then fully visited a few times. Elaboration goes as follows:

• T: Baz<i32> -> add implied bounds
• T: Baz<Option<A>> -> instantiate -> T: Baz<Option<i32>> -> add implied bounds
• T: Baz<Option<Options<A>>> -> ...