Description
Using GATs, I found a busy-loop that can occur in rustc when using a pair of not-quite-self-referencial traits. When compiling the minimal example below, I've let it run for ~10 minutes, during which rustc was at high CPU usage, and had a steadily increasing memory footprint at about 1 MB/sec.
Code
The reduced example below can reproduce the issue locally, and on compiler explorer.
pub trait DummyTrait<'a, R> {}
impl<'a, T, R> DummyTrait<'a, R> for &'a T {}
pub trait FamilyPosition {
type Ref<Family: SelectableType<FamilyPosition = FamilyPositionImpl>>;
}
pub struct FamilyPositionImpl;
impl FamilyPosition for FamilyPositionImpl {
type Ref<Family> = Family;
}
pub trait SelectableType {
type FamilyPosition;
}
pub struct TypeFamilyImpl<'a, R: FamilyPosition> (
R::Ref<TypeFamilyImpl<'a, FamilyPositionImpl>>
);
impl<'a, R: FamilyPosition> SelectableType for TypeFamilyImpl<'a, R>
where
&'a Self: DummyTrait<'a, R>,
{
type FamilyPosition = R;
}While reducing it to the minimal example, the following elements were necessary to trigger the busy loop.
-
Use of the
R::Ref<TypeFamilyImpl<'a, FamilyPositionImpl>>insidestruct FamilyPositionImplrequires the compiler to check whether the required bounds forR::Refare satisfied, soTypeFamilyImpl<'a, FamilyPositionImpl>must implementSelectableType. -
In order for
TypeFamilyImpl<'a, R>to implementSelectableType, the condition&'a Self: DummyTrait<'a, R>must be met. (This dummy trait is part of a trait to express that any lifetime'awhich outlivesSelfmust also outliveR. This relies on the trait implementation being on&'a Self, where the compiler may assume that&'a Selfis well-formed.) -
The implementation of
DummyTraitis only made for&'a Tand notT. If the implementation is made for allT where T: 'a, instead of&'a T, then the compiler can give an error message instead.
Normally, I would expect the compiler to raise an error, stating that there is a circular dependency. If I replace type Ref<Family: SelectableType<FamilyPosition=FamilyPositionImpl> with type Ref<Family: SelectableType>, this is the error that I get. However, the additional bound on the associated type of the argument to Ref somehow prevents this error from being displayed.
Meta
Version info (current stable version):
rustc --version --verbose:
rustc 1.67.1 (d5a82bbd2 2023-02-07)
binary: rustc
commit-hash: d5a82bbd26e1ad8b7401f6a718a9c57c96905483
commit-date: 2023-02-07
host: x86_64-unknown-linux-gnu
release: 1.67.1
LLVM version: 15.0.6
Also occurs on nightly:
rustc 1.69.0-nightly (246eae2fa 2023-02-21)
binary: rustc
commit-hash: 246eae2fab54a5139365c4e1a08c5724fb385fbf
commit-date: 2023-02-21
host: x86_64-unknown-linux-gnu
release: 1.69.0-nightly
LLVM version: 15.0.7
Error output
While rustc was busy-looping, no error messages or diagnostics were printed.
Backtrace
No backtrace appears when using RUST_BACKTRACE=1, as rustc didn't actually crash during the busy-loop. If I manually send SIGSEGV to the rustc process, I can get a stack trace to print out. Other than the instruction pointer in the third line, which may be (+0x14a79c3) instead of (+0x14a79ba), this manually-triggered backtrace has been consistent across multiple runs.
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x325f1a3)[0x7f9702ce71a3]
/lib/x86_64-linux-gnu/libpthread.so.0(+0x14420)[0x7f96ff8ae420]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x14a79ba)[0x7f9700f2f9ba]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(_RNvMs_NtNtCscJHvE3sHdxM_21rustc_trait_selection6traits6engineNtB4_14ObligationCtxt19select_all_or_error+0xfb)[0x7f97017cfafb]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x22a6ffe)[0x7f9701d2effe]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x2282402)[0x7f9701d0a402]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x146028c)[0x7f9700ee828c]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x145ece0)[0x7f9700ee6ce0]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x2632608)[0x7f97020ba608]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x2632417)[0x7f97020ba417]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x1e0877c)[0x7f970189077c]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x1e0668e)[0x7f970188e68e]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x2602ce3)[0x7f970208ace3]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x175b5e8)[0x7f97011e35e8]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x175b3d3)[0x7f97011e33d3]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(_RNvCs5R0DPq11Fmr_18rustc_hir_analysis11check_crate+0xcd)[0x7f97011e2ced]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(_RNvNtCs8Kd5Bl841Dc_15rustc_interface6passes8analysis+0x6b)[0x7f97011e298b]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x2a1291f)[0x7f970249a91f]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x2a11a17)[0x7f9702499a17]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x2a11470)[0x7f9702499470]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x24241b3)[0x7f9701eac1b3]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x2420733)[0x7f9701ea8733]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x241b788)[0x7f9701ea3788]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x241b275)[0x7f9701ea3275]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x241a862)[0x7f9701ea2862]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/librustc_driver-710574fabae712f8.so(+0x2b13b7a)[0x7f970259bb7a]
/home/username/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/libstd-c6192dd4c4d410ac.so(rust_metadata_std_359ab902947f5f0b+0x10c803)[0x7f96ff9fa803]
/lib/x86_64-linux-gnu/libpthread.so.0(+0x8609)[0x7f96ff8a2609]
/lib/x86_64-linux-gnu/libc.so.6(clone+0x43)[0x7f96ff7c7133]