Circular recursive types in a mapped-type and conditional-type world

[krryan]

In attempting to produce a reasonable facsimile of the desired PathIn type from #23398, I ran into this issue with the block on circular type references that I don't think has a workaround, unlike previous issues raised on the subject. #14174 seems closest, and the discussion there identified a related use-case for allowing circular references on types, but I think it makes more sense to raise these concerns as a separate issue rather than extend that discussion (which isn't that closely related to the original issue anyway).

The issue, in short, is that types cannot handle circular references, while classes and interfaces (which can) don't support distribution over a union or being a union.

TypeScript Version: 2.9.0-dev.20180412

Search Terms: circular reference

Code
(strange type Blah<A extends string> = A extends string ? /*...*/ : never; used to force distribution)

type PathBase<A extends string> = A extends string ? {
    node: A;
}: never;
export type Leaf<A extends string> = A extends string ? {
    kind: 'leaf';
    node: A;
}: never;
export type Branch<A extends string, B extends PathBase<string>> = A extends string ? {
    kind: 'branch',
    node: A;
    next: B;
}: never;

export type PathIn<Obj extends {}> =
/*          ^^^^^^
[ts] Type alias 'PathIn' circularly references itself. */
    Obj[keyof Obj] extends {}
        ? Leaf<keyof Obj> | Branch<keyof Obj, PathIn<Obj[keyof Obj]>>
/*                                            ^^^^^^^^^^^^^^^^^^^^^^
[ts] Type 'PathIn' is not generic. */
        : Leaf<keyof Obj>;

Expected behavior:
Compiles without error. PathIn produces a wild and crazy union of linked lists using Leaf and Branch for every path in Obj.

Actual behavior:
Type alias 'PathIn' circularly references itself.

Related Issues: #14174, #23398

[mhegazy]

The error message is self explanatory, i feel. #14174 tracks allowing type aliases to be recursive.
As for the underlying PathIn definition, i think you need Varidic types (#5453) to be able to model this API. truculently using a set of overloads is the way to go.

[krryan]

The error message is fine, I just don't think it should be an error.

As for this and #14174, while the discussion of #14174 got into allowing types to be recursive, that doesn't seem to be the original issue raised in that. It seemed clearer to have a dedicated issue for it. Also, that discussion took place prior to mapped types and conditional types, which make the feature far more desirable—it isn't clear to me that separate issues/use cases that would be solved by the same solution should be duplicates (that's totally a organization call you guys get to make, so let me know if that is how you want things to go and it may save me from making such duplicates in the future).

Finally, the other reason to bring it up as a new issue is to validate my claim that this is a case without a workaround (as the examples discussed in #14174 have), which brings me to your last point—how do overloads assist in this situation?

[mhegazy]

Also, that discussion took place prior to mapped types and conditional types, which make the feature far more desirable

the design limitation that dictates this still the issue. type alias are just aliases, and not named types, the compiler inlines them aggressively, and recursion is not possible in this model.

it isn't clear to me that separate issues/use cases that would be solved by the same solution should be duplicates (that's totally a organization call you guys get to make, so let me know if that is how you want things to go and it may save me from making such duplicates in the future).

I believe it is the same underlying issue and more or less the same changes are needed. We would like to keep one ticket per issue. So i suggest moving this discussion to #14174.

[mhegazy]

Finally, the other reason to bring it up as a new issue is to validate my claim that this is a case without a workaround (as the examples discussed in #14174 have), which brings me to your last point—how do overloads assist in this situation?

Depending on what you are looking for. i am assuming you have a function takes an object and a path in this object.. if that is the case, then you can model this as a set of overloads:

declare function readPath<T, K1 extends keyof T, K2 extends keyof T[K1], K3 extends keyof T[K1][K2]>(obj: T, k1: K1, k2: K2, k3: K3): T[K1][K2][K3];
declare function readPath<T, K1 extends keyof T, K2 extends keyof T[K1]>(obj: T, k1: K1, k2: K2): T[K1][K2];
declare function readPath<T, K1 extends keyof T>(obj: T, k1: K1): T[K1];

With #5453 you should be able to write this as one signature.

[krryan]

the design limitation that dictates this still the issue. type alias are just aliases, and not named types, the compiler inlines them aggressively, and recursion is not possible in this model.

Sure, I get it, I'm just saying that the model is looking more and more inappropriate as types get used for more and more, and are no longer really just used as aliases.

I believe it is the same underlying issue and more or less the same changes are needed. We would like to keep one ticket per issue. So i suggest moving this discussion to #14174.

Right then, will do, and close this.

Depending on what you are looking for. i am assuming you have a function takes an object and a path in this object.. if that is the case, then you can model this as a set of overloads:

Oh, yeah, I think it was implicit in #23398 that anything with a hard-coded list of parameters (and thus a hard-coded limit on how many you could have) wouldn't be sufficient.

With #5453 you should be able to write this as one signature.

True, but we seem closer to circular recursive types than we are to variadic types?