Supporting recursive types

[JQuezada0]

First off, great framework! As someone who hasn't worked a lot with data interchange formats, I was surprised that the first formats I ran into didn't have both strict support for non-nullable types and ADTs.

Description
I'm trying to define a recursive type, but it looks like it's not supported.

[Error] Cycle detected: types.Foo → types.FooOrBar → types.Foo.

Schema:

struct Foo {
    a: String = 0
    b: FooOrBar = 1 
}

struct Bar {
    a: String = 0
}

choice FooOrBar {
    foo: Foo = 0
    bar: Bar = 1
}

I was hoping that making the field optional, or replacing a directly recursive field with a choice that allows the recursion to end would allow the codegen to succeed, but it looks like recursive types in any form will trigger the error.

Are there any thoughts / plans on supporting this? I could imagine having some ability to limit the depth, like Rust's ![recursion_limit = "512"].

This would have to result in a Box on the rust side: Playground

Typescript

Alternatives considered
The actual situation I'm working with is in modeling a type-check diagnostic result from typescript's compiler api. As a workaround, I've added another type which omits the recursive field, and will have to flatten out the data into a plain array

Typical

struct Diagnostic {
    source: String = 0
    information: [DiagnosticInformation] = 1
}

struct DiagnosticInformation {
    category: DiagnosticCategory = 0
    code: S64 = 1
    optional file: File = 2
    optional start: U64 = 3
    optional length: U64 = 4
    message: DiagnosticMessage = 5
}

choice DiagnosticCategory {
    warning = 0
    error = 1
    suggestion = 2
    message = 3
}

choice DiagnosticMessage {
    text: String = 0
    chain: DiagnosticMessageChain = 1
}

struct DiagnosticMessageChain {
    text: String = 0
    category: DiagnosticCategory = 1
    code: S64 = 2
    # Recursive in typescript's compiler API definition. Flatten out before sending
    optional next: [DiagnosticMessageChainFlat] = 3
}

struct DiagnosticMessageChainFlat {
    text: String = 0
    category: DiagnosticCategory = 1
    code: S64 = 2
}

Taken from typescript 4.7.4 source code

export interface Diagnostic extends DiagnosticRelatedInformation {
        /** May store more in future. For now, this will simply be `true` to indicate when a diagnostic is an unused-identifier diagnostic. */
        reportsUnnecessary?: {};
        reportsDeprecated?: {};
        source?: string;
        relatedInformation?: DiagnosticRelatedInformation[];
    }

 export interface DiagnosticRelatedInformation {
        category: DiagnosticCategory;
        code: number;
        file: SourceFile | undefined;
        start: number | undefined;
        length: number | undefined;
        messageText: string | DiagnosticMessageChain;
    }

 /**
     * A linked list of formatted diagnostic messages to be used as part of a multiline message.
     * It is built from the bottom up, leaving the head to be the "main" diagnostic.
     * While it seems that DiagnosticMessageChain is structurally similar to DiagnosticMessage,
     * the difference is that messages are all preformatted in DMC.
     */
    export interface DiagnosticMessageChain {
        messageText: string;
        category: DiagnosticCategory;
        code: number;
        next?: DiagnosticMessageChain[];
    }

[stepchowfun]

Hi @JQuezada0, thank you for opening this issue! As you've discovered, Typical does not currently support recursive types, and the schema validator actively detects and forbids them.

It would be nice to remove this restriction at some point, but supporting recursive types would require answers to some subtle questions. For example, in languages like Rust, where should the Box be inserted? In your example, we could box either Foo.b or FooOrBar.foo, and it's not clear (to me) why one should be preferred over the other. Perhaps the user would need to explicitly annotate their decision in the schema?

I'll leave this issue open for further discussion.

[bbqsrc]

One could perhaps borrow from the ML family and use a rec keyword to declare the point at which recursion is accepted, and use that to determine the implementation-specific solution to allowing the recursion?

[stepchowfun]

Yes!