How does Rust type solver handle a self-depending/cyclic type bounds?

[ZhennanWu]

Recently I constructed a very peculiar type pattern. In the pattern, the truthiness of a type bound actually goes all the way back to depending on the truthiness of itself, and no contradiction will be ever created along the chain (If you assume it to be true, then it will cycle back to be true. Also the other way around). And it seems that Rust's type solve just judged it to be falsy, without any "cycle detected" error.

I'm quite curious about how does Rust's type solver handle the case when it seems it should throw a "cycle detected" error. It seems strange that the type solver just outright decided it to be falsy. And I would still want to tweak the pattern to trick the type solver into deciding otherwise, hence this post.

A stripped-down example is shown below

use std::marker::PhantomData;

trait Render {
    type RenderImpl: ImplRender<Render = Self>;
}

trait ImplRender {
    type Render;
}

trait ImplComposite<R> {}

struct RenderImpl<R: Render>(PhantomData<R>);

impl<R: Render> ImplRender for RenderImpl<R>
where
    R::RenderImpl: ImplComposite<R>, //<---------------------------------Site 1
{
    type Render = R;
}

impl<R: Render> ImplComposite<R> for RenderImpl<R> {} //<----------------Site 2

/////////////////////////////////////
///

trait ImplRenderBySuper {
    type Render;
    type Super: ImplRender<Render = Self::Render>;
}

impl<T> ImplRender for T
where
    T: ImplRenderBySuper, //<--------------------------------------------Site 3
{
    type Render = <T::Super as ImplRender>::Render;
}

impl<T> ImplComposite<T::Render> for T where T: ImplRenderBySuper {} //<-Site 4

struct TestRender {}

impl Render for TestRender {
    type RenderImpl = DerivedRenderImpl<Self>; //<-----------------------Site 5
}

struct DerivedRenderImpl<R: Render>(PhantomData<R>);

impl<R: Render> ImplRenderBySuper for DerivedRenderImpl<R> 
    where RenderImpl<R>: ImplRender<Render=R> //<------------------------Site 6
{
    type Render = R;

    type Super = RenderImpl<R>;
}

Explanation:

1. In Site 5, the type solver needs to decide whether DeriveRenderImpl<TestRender>: ImplRender<Render = TestRender>. So, it goes to check impl blocks for ImplRender
2. In Site 3, the type solver founds a possible impl block and needs to decide whether DeriveRenderImpl<TestRender>: ImplRenderBySuper. So, it goes to check impl blocks for ImplRenderBySuper
3. In Site 6, the type solver founds a possible impl block and needs to decide whether RenderImpl<TestRender>: ImplRender<Render = TestRender>. So, it goes to check impl blocks for ImplRender
4. In Site 1, the type solver founds a possible impl block and needs to decide whether TestRender::RenderImpl: ImplComposite<TestRender> (which is equivalent to DerivedRenderImpl<TestRender>: ImplComposite<TestRender>). So, it goes to check impl blocks for ImplComposite
5. In Site 4, the type solver founds a possible impl block and needs to decide whether DerivedRenderImpl<TestRender>: ImplRenderBySuper. We have get back to step two. A cycle is constructed.

If we assume any condition on the cycle to be truthy, then everything along the cycle is true and will have their legitimate implementation. If we assume any condition on the cycle to be falsy, then everything will be false.

The current compiler (1.77.1) generates:

error[E0277]: the trait bound `RenderImpl<TestRender>: ImplRender` is not satisfied
   --> src/main.rs:155:27
    |
155 |         type RenderImpl = DerivedRenderImpl<Self>;
    |                           ^^^^^^^^^^^^^^^^^^^^^^^ the trait `ImplRender` is not implemented for `RenderImpl<TestRender>`, which is required by `DerivedRenderImpl<TestRender>: ImplRenderBySuper`
    |
    = help: the trait `ImplRender` is implemented for `RenderImpl<R>`
note: required for `DerivedRenderImpl<TestRender>` to implement `ImplRenderBySuper`
   --> src/main.rs:160:21
    |
160 |     impl<R: Render> ImplRenderBySuper for DerivedRenderImpl<R> where RenderImpl<R>: ImplRender<Render=R>{
    |                     ^^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^^^^                      -------------------- unsatisfied trait bound introduced here
note: required by a bound in `Render::RenderImpl`
   --> src/main.rs:115:37
    |
115 |         type RenderImpl: ImplRender<Render = Self>;
    |                                     ^^^^^^^^^^^^^ required by this bound in `Render::RenderImpl`

[ZhennanWu]

Well, I found one way to cut the cycle and get the implementation. The way is, in any one of the trait definition on the chain, to convert the "where" clauses on the type parameter to "where" clauses on all trait methods and associated items.

Similar to converting

trait A {
    fn a();
}
impl<T:A> A for T {
    fn a() {}
}
// T:A will be falsy for all types

into

trait A {
    fn a();
}
impl<T> A for T {
    fn a() where Self: A {}
}

[nerditation]

maybe you are interested in:

https://rust-lang.github.io/chalk/book/recursive/inductive_cycles.html

[SkiFire13]

AFAIK all user defined traits are inductive (a cycle is an error), while auto traits are coinductive (a cycle is ok).