Handle circular references

[adwhit]

Hi, thanks for the crate and feel free to close if out of scope.

This crate fails when dealing with circular references. Example:

#[derive(TypeDef)]
enum SelfRef {
    One(u32),
    Many(Vec<SelfRef>),
}

This could result in a (valid) TS type something like:

export type SelfRef = { One: number } | { Many: SelfRef[] };

Instead upon compilation produces error like:

error[E0391]: cycle detected when elaborating drops for `<impl at src/main.rs:343:10: 343:17>::INFO`
   --> src/main.rs:343:10
    |
343 | #[derive(TypeDef)]
    |          ^^^^^^^
    |
note: ...which requires const-evaluating + checking `<impl at src/main.rs:343:10: 343:17>::INFO::promoted[1]`...
   --> src/main.rs:343:10
    |
343 | #[derive(TypeDef)]
    |          ^^^^^^^
note: ...which requires const-evaluating + checking `<impl at src/main.rs:343:10: 343:17>::INFO::promoted[1]`...
   --> src/main.rs:343:10
    |
343 | #[derive(TypeDef)]
    |          ^^^^^^^
note: ...which requires const-evaluating + checking `typescript_type_def::impls::<impl typescript_type_def::emit::TypeDef for alloc::vec::Vec<T>>::INFO`...
   --> /Users/user/.cargo/registry/src/github.com-1ecc6299db9ec823/typescript-type-def-0.5.6/src/impls.rs:158:28
    |
158 |     const INFO: TypeInfo = list_type_info!(T);
    |                            ^^^^^^^^^^^^^^^^^^
note: ...which requires const-evaluating + checking `<impl at src/main.rs:343:10: 343:17>::INFO`...
   --> src/main.rs:343:10
    |
343 | #[derive(TypeDef)]
    |          ^^^^^^^
note: ...which requires caching mir of `<impl at src/main.rs:343:10: 343:17>::INFO` for CTFE...
   --> src/main.rs:343:10
    |
343 | #[derive(TypeDef)]
    |          ^^^^^^^
    = note: ...which again requires elaborating drops for `<impl at src/main.rs:343:10: 343:17>::INFO`, completing the cycle
    = note: cycle used when running analysis passes on this crate
    = note: this error originates in the derive macro `TypeDef` (in Nightly builds, run with -Z macro-backtrace for more info)

My hunch is this might not be possible to fix without significant internal changes.

[dbeckwith]

Thanks for the report! Indeed this seems not trivial to fix, but I have some ideas so I'll give it a shot; supporting self-referential types seems like an important feature.

[fragsalat]

Was there any progress on this yet? I have a struct referencing children of same type which fails here as well.

[dbeckwith]

I did start a branch to tackle this back when this issue was opened and made a bit of progress, then forgot about it. I left a bunch of notes about complicated edge cases in the recursive parts of the code that needed to be updated to handle this. Unfortunately my approach requires a breaking change to the API since the only way I could think of to work around the compiler error from OP was to make TypeExpr::Ref take a thunk instead of a direct reference.

Here's some elaboration of the issue:

• consts cannot reference themselves, even behind a pointer (playground)
• statics can reference themselves (playground)
• however, we're not just using normal statics, we're using them in a trait, but static trait items are not allowed (playground)
• const trait items are allowed, but again cannot reference themselves (playground)
• the only way I could think of to work around this was to add indirection through a function (playground)

A breaking change is not such a big deal for this library I think, especially since it's just in the TypeExpr definitions which most people are not writing by hand.

I will try to revisit my branch in the next week or so and see if I can get it fully working.

[dbeckwith]

I took another shot at this and made slightly more progress, but keep finding more and more gnarly problems to work through...

The biggest one so far is that any algorithm for iterating over the graph of type definitions needs some notion of "type expression identity" in order to be able to tell if a given expression has already been visited in the graph or has been emitted already. The most well-defined way I could think to do this was to compute a structural hash of the expression and compare the hashes. Pretty simple, just use Rust's Hash trait to keep state while recursing through the expression, that should give you a unique value for each unique expression. This worked fine before recursive types. However, once you introduce recursive types, now just computing these structural hashes has a problem because it can recurse forever (resulting in stack overflow). In order to fix this, I need to detect when a cycle has been encountered and bail out, so I thought to keep a stack of expression references (&'static TypeExpr) and use that to check if we've hit a self-referential type. But how do you tell if the current expression is in that stack? We obviously can't use a structural hash, that's what we're in the middle of computing! So we need some other definition of type expression identity. I tried doing pointer-address comparison, but these don't seem stable when you're taking references of consts and it just doesn't work reliably. It's at this point that I was getting really frustrated and lost down this rabbit-hole.

All of this was made even harder to deal with by the fact that making type references into a function (motivation described in my previous comment) means that when you Debug them, all it prints is the address of the function and not its contents. Okay, I can write a custom Debug impl that calls the function so I can see the contents, but of course, if the type definition is self-referential, this will run into infinite recursion again. The only real way around this is to basically make my own Debug trait (including all the nice debug builders like debug_struct, debug_tuple, etc. with pretty-printing and all that) that carries some additional state about what's been printed already so I can bail out when I hit a cycle (of course this would also need a reliable definition of identity for type expressions in order to work, so I'm back at the first problem). So trying to figure out all this without helpful Debug info makes it even harder.

Anyway, I think I might need to take a step back and completely re-think the design of this whole library in order to support this, unless I can think of some other clever way to compare possibly self-referential type expressions.

[Bryley]

Hey guys, for anyone looking for a workaround, it looks like you can create an empty struct type with a custom implementation of TypeDef to specify exactly what type you expect:

#[derive(TypeDef)]
enum SelfRef {
    One(u32),
    Many(#[type_def(type_of="SelfRefTypeDef")] Vec<SelfRef>),
}

struct SelfRefTypeDef;
impl TypeDef for SelfRefTypeDef {
    const INFO: TypeInfo = TypeInfo::Native(NativeTypeInfo {
        r#ref: TypeExpr::ident(Ident("SelfRef[]")),
    });
}

This generates Typescript code like:

export type SelfRef = ({
    "One": U32;
} | {
    "Many": SelfRef[];
});