Is it possible to create a custom derive that would prevent cycles between types at compile time?

Question

For example, I want the following code to not compile because Foo can point at a Bar which can point at a Foo.

#[derive(NoCycles)]
struct Foo {
    k: u32,
    p: Option<Rc<Bar>>,
}

#[derive(NoCycles)]
struct Bar {
    s: Option<Rc<Foo>>,
}

#[derive(NoCycles)]
struct Baz {
    s: String,
}

If Bar was changed to have an Option<Rc<Baz>>, compilation should succeed because there is no way for Foo to point at a Foo.

Answer 1

I have no experience with writing procedural macros, but I would try to generate a "parallel universe for the NoCycle versions". I.e. for each struct Foo that should participate in NoCycle, there would be a "parallel" struct Foo_NoCycle that is only used for cycle detection.

Now the idea: The struct Foo_NoCycle would be automatically generated from Foo, and its members would have the NoCycle-parallel types of the members in Foo. I.e. the following struct

struct Foo {
    k: u32,
    p: Option<Rc<Bar>>,
}

would have the parallel NoCycle struct:

struct Foo_NoCycle {
    k: u32_NoCycle,
    p: Option<Rc<Bar>>_NoCycle, // <- not real rust syntax
}

As you see, the above - simpfy appending the suffix _NoCycle - does not lead to valid rust syntax. Thus, you could introduce a trait that serves as a bridge between "normal" and NoCycle-structs:

trait NoCycleT {
    type NoCycleType;
}

Its usage - showcased for Foo_NoCycle - would be like this:

struct Foo_NoCycle {
    k: <u32 as NoCycleT>::NoCycleType,
    p: <Option<Rc<Bar>> as NoCycleT>::NoCycleType
}

Generating a Foo_NoCycle from a Foo should be doable by a macro.

Now comes the trick: You tell rust that for u32 the corresponding NoCycle-type is u32, while Rc<Bar> has NoCycle-type Bar:

impl NoCycleT for u32 {
    type NoCycle=u32;
}
impl<T: NoCycleT> NoCycleT for Rc<T> {
    type NoCycle = T::NoCycleType;
}

This way, the NoCycle-types lead to real circular types, preventing compilation.

For your example, the NoCycle-structs would look like this:

struct Foo_NoCycle {
    k: <u32 as NoCycleT>::NoCycleType, // == u32
    p: <Option<Rc<Bar>> as NoCycleT>::NoCycleType, // == Bar_NoCycle
}
struct Bar_NoCycle {
    s: <Option<Rc<Foo>> as NoCycleT>::NoCycleType, // == Foo_NoCycle
}

Substituting the types shows:

struct Foo_NoCycle {
    k: u32,
    p: Bar_NoCycle,
}
struct Bar_NoCycle {
    s: Foo_NoCycle,
}

This way, the compiler sees that Foo_NoCycle and Bar_NoCycle form a circular type dependency that cannot be compiled.

It's not a solution that works without some effort to define NoCycleT for base types, and to define NoCycleT for things like Box, Rc, Arc, Vec, Mutex, etc. However, I guess the compiler would inform you about missing impls so that you can just implement NoCycleT for types actually needed.