Repository: rust
Issue: Busy-loop Evaluating Bound on GAT Argument
Labels: A-trait-system,T-compiler,I-compilemem,C-bug,I-hang,fixed-by-next-solver,A-GATs

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](https://godbolt.org/z/aa31vEPPE).

```Rust
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>>` inside `struct FamilyPositionImpl` requires the compiler to check whether the required bounds for `R::Ref` are satisfied, so `TypeFamilyImpl<'a, FamilyPositionImpl>` must implement `SelectableType`.

* In order for `TypeFamilyImpl<'a, R>` to implement `SelectableType`, the condition `&'a Self: DummyTrait<'a, R>` must be met.  (This dummy trait is part of a trait to express that any lifetime `'a` which outlives `Self` must also outlive `R`.  This relies on the trait implementation being on `&'a Self`, where the compiler may assume that `&'a Self` is well-formed.)
  
* The implementation of `DummyTrait` is only made for `&'a T` and not `T`.  If the implementation is made for all `T 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
<!--
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.
-->

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.

<!--
Include a backtrace in the code block by setting `RUST_BACKTRACE=1` in your
environment. E.g. `RUST_BACKTRACE=1 cargo build`.
-->
<details><summary><strong>Backtrace</strong></summary>
<p>

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]
```

</p>
</details>