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: https://github.com/microsoft/TypeScript/pull/33050

Regression: https://github.com/microsoft/TypeScript/pull/33050#issuecomment-526637037

[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>>>

@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 @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: https://github.com/microsoft/TypeScript/pull/33050#issuecomment-543365074

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 @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

[reverofevil]

Sorry to put a description of why I think this is unacceptable behaviour on a more formal side, but I have no idea how to explain better.

When we're refactoring code and trying to keep it DRY, it's common to cut a part of a code, make it a function or a type alias, and put a reference to that thing at the call site.

const f = () => ... som = eth + ing; ... 

const f = () => ... something(); ... 
const something = () => som = eth + ing;

type T = .... Som<Eth, Ing> ...

type T = ... Something ...
type Something = Som<Eth, Ing>

The ability to do so without a hassle in lambda calculus is described by a rule called η-conversion. It literally means that you can convert x => f(x) into just f or vice versa. While it's not true for JS/TS runtime, as we perfectly know from the classic example where we have to create IIFE inside of a loop, types do not have any mutable state, and are expected to support η-conversion. Surprisingly, when I do

type T = {x: T}

type T = A<T>
type A<T> = {x: T}

this little refactoring shoots my leg off, and I certainly do not expect that. I'm afraid this has something to do with internal represenation of types in TS that keeps track of type aliases for the purposes other than improved error messages. Probably, someone mistakenly used that representation as if type aliases were not ephemeral, but something that does really exist.

[reverofevil]

This does mean such a type can only represent cyclic data, however, which is quite an interesting constraint.

I don't like to be sidetracked with a discussion of a single arbitrary type from an example, but it's already been started, so I have to mention that it's not just circular: it represents lasso structures.

[AnyhowStep]

He probably meant "cyclic" as in, "contains at least one cycle".

But I can see how that terminology can be confusing. Just to be sure, I looked it up and Wolfram also says "cyclic" can mean "not acyclic", but is a confusing term outside of graph theory.

Since it can be confused with the term "cycle graph".

[AnyhowStep]

Also, regarding η-equivalence, I understand what you mean.

It has also been my experience that, even though there are infinite equivalent ways to express a computation at the type level, some ways are more emit-friendly (easier for developers to read in .d.ts files), others are more Instantiation-friendly (letting you compute more complicated and deeply nested types before hitting the depth error), others are more compile-time friendly (taking milliseconds to compile vs seconds/minutes), others just don't work (despite intuition/math saying it should work), and some hit that sweet spot and do exactly what you want, as you want.

---

If you look at my issue history, a lot of my issues basically boil down to,

I had type F and it didn't do Thing™. I wrote types G, H, I, J, etc. that are η-equivalent to F and they still don't do Thing™.

Out of desperation, I tried type Z that is η-equivalent to F and it works. Type Z is extremely unintuitive and convoluted, despite being equivalent. But it works. I don't know why it works. But it does. Can someone tell me why?

Most of the time, I don't get an answer =P

---

Without an answer, I just copy-paste the issue link to a comment in my code, and hope I'll understand some day.

---

As an example, once, I had the following,

type F<T, U> = G<{
  x : T["x"],
  y : H<T["y"], U>,
}>

And it gave me max depth errors. So, I changed it to,

type F_Impl<X, Y, U> = G<{
  x : X,
  y : H<Y, U>,
}>

type F<T, U> = F_Impl<T["x"], T["y"], U>

Both versions of F are basically equivalent (despite the second implementation being more convoluted) but the second implementation will not get a max depth error while the first one will.

[reverofevil]

Both issues come from the fact there is something called "instantiation", which doesn't really make sense. Type alias is an alias, there is nothing to create an instance of.

[reverofevil]

Without an answer, I just copy-paste the issue link to a comment in my code, and hope I'll understand some day.

@AnyhowStep Thank you, this approach literally changes quality of life. I just started marking places with dangerous casts with references to bugs in compiler, and have so much less anxiety by now.