Compiler hangs indefinitely when using associated types instead of their explicit type.

[y86-dev]

I tried this code:

use std::marker::PhantomData;

pub trait DynQueriable<'a>: Sized
where
    QueryIter<'a, Self::Parts, Self::Raw, Self>: Iterator<Item = Self>,
{
    type Parts;
    type Raw: ?Sized + 'a;
}

pub trait QueryVariant<'a, Component: ?Sized + 'a> {}

pub struct QueryIter<'a, T, C: ?Sized, V: DynQueriable<'a, Raw = C>>
where
    QueryIter<'a, <V as DynQueriable<'a>>::Parts, C, V>: Iterator<Item = V>,
{
    p: PhantomData<fn(T, &'a C, V) -> (T, &'a C, V)>,
}

impl<'a, C: ?Sized, V: QueryVariant<'a, C>> Iterator for QueryIter<'a, &'a V, C, &'a C>
where
    &'a C: DynQueriable<'a, Raw = C>,
    QueryIter<'a, <&'a C as DynQueriable<'a>>::Parts, C, &'a C>: Iterator<Item = &'a C>,
{
    type Item = &'a C;
    fn next(&mut self) -> Option<Self::Item> {
        todo!()
    }
}

trait MyMarker {}

struct A;
impl MyMarker for A {}
impl<'a> QueryVariant<'a, dyn MyMarker + 'a> for A {}

impl<'a> DynQueriable<'a> for &'a dyn MyMarker {
    type Parts = &'a A;
    type Raw = dyn MyMarker + 'a;
}

I expected to see this happen: successful compilation.

Instead, this happened: The compiler hung and did not make any progress (i let it run for at least 5 minutes).

A slight modification of the above code results in it compiling without a problem:
line diffs:

// line 13 
pub struct QueryIter<'a, T, C: ?Sized, V: DynQueriable<'a, Raw = C>>
// replaced by
pub struct QueryIter<'a, T, C: ?Sized, V: DynQueriable<'a, Raw = C, Parts = T>>

// line 15
     QueryIter<'a, <V as DynQueriable<'a>>::Parts, C, V>: Iterator<Item = V>,
// replaced by
     Self: Iterator<Item = V>,

// lines 22-23
     &'a C: DynQueriable<'a, Raw = C>,
     QueryIter<'a, <&'a C as DynQueriable<'a>>::Parts, C, &'a C>: Iterator<Item = &'a C>,
// replaced by
     &'a C: DynQueriable<'a, Raw = C, Parts = &'a V>,

so the total modified code is:

use std::marker::PhantomData;

pub trait DynQueriable<'a>: Sized
where
    QueryIter<'a, Self::Parts, Self::Raw, Self>: Iterator<Item = Self>,
{
    type Parts;
    type Raw: ?Sized + 'a;
}

pub trait QueryVariant<'a, Component: ?Sized + 'a> {}

pub struct QueryIter<'a, T, C: ?Sized, V: DynQueriable<'a, Raw = C, Parts = T>>
where
    Self: Iterator<Item = V>,
{
    p: PhantomData<fn(T, &'a C, V) -> (T, &'a C, V)>,
}

impl<'a, C: ?Sized, V: QueryVariant<'a, C>> Iterator for QueryIter<'a, &'a V, C, &'a C>
where
    &'a C: DynQueriable<'a, Raw = C, Parts = &'a V>,
{
    type Item = &'a C;
    fn next(&mut self) -> Option<Self::Item> {
        todo!()
    }
}

trait MyMarker {}

struct A;
impl MyMarker for A {}
impl<'a> QueryVariant<'a, dyn MyMarker + 'a> for A {}

impl<'a> DynQueriable<'a> for &'a dyn MyMarker {
    type Parts = &'a A;
    type Raw = dyn MyMarker + 'a;
}

And that compiles without issues.

I searched through some issues and found #91498, the problem mentioned in this comment seems related, however in my case the complier does not emit an error.

Meta

rustc --version --verbose:

binary: rustc
commit-hash: 1d9c262eea411ec5230f8a4c9ba50b3647064da4
commit-date: 2022-03-26
host: x86_64-unknown-linux-gnu
release: 1.61.0-nightly
LLVM version: 14.0.0

[LegionMammal978]

I managed to reduce the code down to this:

pub trait Foo: Circular {}

pub trait Circular {
    type Unit;
}

impl<'a> Foo for &'a () {}

impl<'a> Circular for &'a ()
where
    &'a (): Circular<Unit = ()>,
{
    type Unit = ();
}

It seems that the compiler is checking exponentially many obligations at each depth, meaning that the default recursion_limit of 128 will never get hit. Adding #![recursion_limit = "16"] produces an overflow error. Some trivial variations of this (e.g., changing the order of the impl blocks) produce behaviors including overflow errors, error messages followed by the compiler indefinitely hanging, and successful compilations.

[fmease]

Doesn't hang in the next-gen solver (-Znext-solver):

error[E0275]: overflow evaluating the requirement `<QueryIter<'a, <&'a (dyn MyMarker + 'a) as DynQueriable<'a>>::Parts, <&'a (dyn MyMarker + 'a) as DynQueriable<'a>>::Raw, ...> as Iterator>::Item == &'a (dyn MyMarker + 'a)`
  --> hang.rs:37:10
   |
37 | impl<'a> DynQueriable<'a> for &'a dyn MyMarker {
   |          ^^^^^^^^^^^^^^^^
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`hang`)
note: required by a bound in `DynQueriable`
  --> hang.rs:5:59
   |
3  | pub trait DynQueriable<'a>: Sized
   |           ------------ required by a bound in this trait
4  | where
5  |     QueryIter<'a, Self::Parts, Self::Raw, Self>: Iterator<Item = Self>,
   |                                                           ^^^^^^^^^^^ required by this bound in `DynQueriable`

error[E0275]: overflow evaluating the requirement `QueryIter<'a, <&'a (dyn MyMarker + 'a) as DynQueriable<'a>>::Parts, <&'a (dyn MyMarker + 'a) as DynQueriable<'a>>::Raw, ...>: Iterator`
  --> hang.rs:37:10
   |
37 | impl<'a> DynQueriable<'a> for &'a dyn MyMarker {
   |          ^^^^^^^^^^^^^^^^
   |
   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`hang`)
note: required by a bound in `DynQueriable`
  --> hang.rs:5:50
   |
3  | pub trait DynQueriable<'a>: Sized
   |           ------------ required by a bound in this trait
4  | where
5  |     QueryIter<'a, Self::Parts, Self::Raw, Self>: Iterator<Item = Self>,
   |                                                  ^^^^^^^^^^^^^^^^^^^^^ required by this bound in `DynQueriable`

error: aborting due to 2 previous errors