Allow type aliases to reference themselves in type argument positions

[reverofevil]

TypeScript Version: 3.8.0-dev.20191105

Search Terms:
circular

Code

type A<T> = { x: T }
type R = A<R> // FAIL

type B = { x: B } // OK

Expected behavior:
Both cases throw no error.

Actual behavior:
Type R is rejected due to a circular reference.

Playground Link:
Link

Related Issues:
#33050

Regression: #33050 (comment)

[reverofevil]

Could you please also add this test case into a test suite for this issue? It's closer to the supposed real-world usage of this pattern.

interface A<T> { B: {x: T} }
type C<T extends keyof A<any>, U> = A<U>[T]
type R = C<'B', R>

[AnyhowStep]

I would personally say type B = { x: B } should be an error. What value satisfies type B?

type Turtle = { down : Turtle };

It's turtles all the way down.

---

I guess this is a valid value.

const ouroboros = {} as any;
ouroboros.eating = ouroboros;

[reverofevil]

Well, I could have put original code with several mutually recursive union types over several hundred cases, but I think turtles are fine too.

If such types were banned, there would be no way to implement Typescript in Typescript, because internal representation of B has to include reference to itself in the field describing types of its fields.

[AnyhowStep]

My initial reaction was that the recursion has to stop at some point. And that constructing an infinitely recursive type can't really be performed without as casts at some point.

But I guess there's also,

class SelfRecursive {
 self : SelfRecursive;
 constructor () {
 this.self = this;
 }
}

---

So, I guess I just wasn't open minded enough =P

---

When I first saw the types in the original post, my head started screaming, "WHERE IS THE EXIT CONDITION!?"

[fatcerberus]

type B = { x: B };

While this is a legal type, it's worth noting that it's also a Droste type: every inhabitant of this type contains another instance of the same type, and therefore such types can only represent cyclic data (assuming you never lie to the type system). While this doesn't strike me as a particularly useful constraint, it's a perfectly acceptable type with well-defined semantics. On the other hand...

type R = A<R>;

This is the type that baffles me. In order to know what R is, we have to instantiate A. But we can't instantiate A until we know what R is, which requires instantiating A... unlike with B there's no place where we can stop going down the rabbit hole with R. Even if you lazy-evaluate it, no matter how many times you go around in that circle, you'll never have a concrete type you can use. It's a different kind of circularity than B: you're essentially calling an infinitely recursive function at the type level. R becomes A<R> which becomes A<A<R>> which becomes A<A<A<R>>>, ad infinitum.

[reverofevil]

type Level<V, A> = {type: 'node', left: A, right: A} | {type: 'leaf', value: V}
type Annotated<T> = {note: string, value: T}

type Tree<V> = Level<V, Tree<V>>
type AnnotatedTree<V> = Annotated<Level<V, AnnotatedTree<V>>>

Bruce Pascoe (@fatcerberus) Does it make more sense?

you'll never have a concrete type you can use

1. A<A<...>> is a valid, concrete type.
2. It's the linked code by Anders Hejlsberg (@ahejlsberg) that allows to create infinite loops of (abstract) interface A, while
3. (concrete) type A should be immediately substituted, and R should be no different from B.

[fatcerberus]

I think this comment explains the problem: #33050 (comment)

Specifically:

[...] the recursive reference is an argument to a type alias and is not known to be guarded. TypeScript won't peek inside the type alias to see if it binds an object type.

Emphasis mine. This seems to be a deliberate tradeoff. In Anders Hejlsberg (@ahejlsberg)'s example, he used an interface as the target of the recursive type parameter, not a type alias.

[AnyhowStep]

Writing code on mobile sucks, this is the best I can do,

type TreeBase<V, NodeT> =
 | { type: 'node', left: NodeT, right: NodeT }
 | { type: 'leaf', value: V }
;

type Tree<V> =
 | { type: 'node', left: Tree<V>, right: Tree<V> }
 | { type: 'leaf', value: V }
;

type AnnotatedTree<V> = {
 note: string,
 value: TreeBase<V, AnnotatedTree<V>>,
};

http://www.typescriptlang.org/play/#code/FAFwngDgpgBAKgJylAQgQwM5QDwDUA0MAcgPYAmUcAfDALzAwwA+MA3jONAFwwDkAduSi9CAGygAzED1IU4hBAEsA5gAtpxIXBgBfBszYdIUHr3FoJImADc0ogK4mYuXcADcwUMfhIcuGvSMLOycTgJCVuJSPIjIeFQKKuoxvvGuQYahpuaWhLYOTi56Hl7QMACC-IIgaCBQZLF+AWz61U4YIEr8yvj6+Y4pyOhYeISV1bX1jfEJwDoeQA

[AnyhowStep]

Stolen from fp-ts,

export interface URItoKind<A> {
 Tree : Tree<A>,
 AnnotatedTree : AnnotatedTree<A>,
}
export type URIS = keyof URItoKind<any>
export type Kind<URI extends URIS, A> = URI extends URIS ? URItoKind<A>[URI] : any


type TreeBase<V, NodeT extends URIS> =
 | { type: 'leaf', value: V }
 | { type: 'node', left: Kind<NodeT, V>, right: Kind<NodeT, V> }
;

type Tree<V> =
 TreeBase<V, "Tree">
;

type AnnotatedTree<V> = {
 note: string,
 value: TreeBase<V, "AnnotatedTree">,
};

const x : Tree<number> = {
 type : "node",
 left : { type : "leaf", value : 1337 },
 right : {
 type : "node",
 left : { type : "leaf", value : 9001 },
 right : { type : "leaf", value : 69 },
 },
}

const y : AnnotatedTree<number> = {
 note : "Stolen",
 value : {
 type : "node",
 left : {
 note : "From",
 value : {
 type : "leaf",
 value : 3,
 },
 },
 right : {
 note : "fp-ts",
 value : {
 type : "leaf",
 value : 4,
 },
 },
 },
}

http://www.typescriptlang.org/play/#code/FAUwHgDg9gTgLgAgJYDs4hgMwIYGMQICqASgJJxQDSqAJgDwCCAfAgN7AIIAqMIBAXN14hGTADQcEDFCihxs6Gjz4JB02fMXKRzCQF9QkWIjgBPCARKkAyggC8CANYhTUTETIVqKethSmmQ2h4BDMLBG96KwRwdB8AZw8bMSkWB2jYkASk2wB+JK9aUQBtKwBdVQQ-U2BasIJtACFseJEANRSAOSgaEC4YsDiaRKtrNMkAHzZQ8xBBAHIAGxBsTHmUgDdsRYBXOYQ2hANOKdYZiwXZXvWEZcw4QUi6bt6uFLbxBBgkAHMACweESKLz67xYBgA3HVZkI+HQPvZJE0Wu0UgAibRowJQ4D1KQyOQKEBKYTwtJsSQafbxODfFA-CScLa7fbI1rw9HqQlaYRY-Q43BQFA0hBgSraOgoHYAWwARhhyexOHjBGiriA0YzbiB7pUziqEGjlqtNQhmXtKgBGADM1oA7Ectd9-ohBErOOcBIb1ZrJJw7q7pgajStMKbzV6AJwABmjlsdfq+vwBes9lRDJs22wtggAbJGE5w9PpaoLhYhTJUuZpiRKpXKFfYKZwqenrBRlihfUzs173cqYaqfVr-TrA-2Pa3VQAxGBQaXdj09ll6xNL4PGsMjpdm3uVa3bovb4uJ50pt1rhBTw2YCAAWjg8UXS4jq53Ho3oefO9fggALIehYeieR7AAYQA

[RyanCavanaugh]

type B = { x: B } is obviously uninhabitable, but the very reasonable type type C = { x?: C } is quite terminable and not meaningfully different.

type R = A<R> when A is an object type is one thing, but A could easily be a conditional type, at which point the declaration becomes immediately truly circular. Whether or not type R = A<R> should be illegal sort of depends on whether you think generic type aliases should have some level of opacity over their definition.

Tagging this as a feature request since this has never "worked" in any meaningful sense and it's unclear why it's a strict necessity.

[fatcerberus]

type B = { x: B } is obviously uninhabitable

Funnily enough, this isn’t actually true. I thought the same for a while, but it turns out that x could be this, or to another instance of B which referred back to the first one, etc. This does mean such a type can only represent cyclic data, however, which is quite an interesting constraint.

There is no way to express the initial instance of such a type as an object literal, however, I’ll freely admit.

[AnyhowStep]

You know how averse someone is to OOP by their initial reaction to B = { x : B } =P