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:

1. 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?
2. How should recursive types be encoded on the wire? Currently, everything is densely packed with no indirection. We'd have to introduce some kind of "reference" mechanism in the encoding.
3. What optimizations can be done to make it performant? For example, if a user defines a recursive type for linked lists, can we encode that as an array on the wire? How would that interact with schema evolution/compatibility (e.g., what happens if the user adds a third case beyond just the standard empty and nonempty cases)?

I'll leave this issue open for further discussion. To set expectations, I think this will require a large amount of work which means it probably won't be supported in the near future. As a workaround, you can represent cyclic data using an array with indices into the array serving as cyclic references, but of course the ergonomics and safety of that approach are not ideal.