Recursive trait bounds


#1

Rust currently does not understand recursive trait bounds.

Example (playground):

struct A<T> {
    a: Option<Box<A<T>>>,
    b: T,
}

trait MyTrait {
    fn f(&self);
} 

impl<T> MyTrait for A<T>
    where A<T>: MyTrait
{
    fn f(&self){}
}

fn main() {
    let a = A {
        a: None,
        b: 1u8,
    };
    
    a.f();
}

It fails to compile with overflow evaluating the requirement A<u8>: MyTrait. As I understand it, rustc tries to check if MyTrait is implemented for A<u8>, for that it needs to check the condition where A<u8>: MyTrait and this creates recursion. When checking the conditions in where clause it probably should just assume that the trait it is checking is implemented for the type in question because if checks in where clause succeed this will be true.

So, why would supporting this be useful?

Consider that you are implementing procedural macro:

#[derive(Serialize)]
struct Struct<T, ...> {
    a: A,
    a: B,
    ...
}

In you generated impl you will need to generate bounds. It is tempting to just generate where A: Serialize, B: Serialize, etc. However there are at least two issues with this approach. One of them is the issue described above. Because of no support for recursive bounds naive method could generate invalid bounds and serde needs to use more complex heuristics which also sometime generate incorrect bounds.


#2

I believe this should be fixed by the new strategy we’re experimenting with in chalk. See more info in this GitHub issue.