When discussing algorithms, the documentation here explains that TypeScript's structural type system determines compatibility based on having the same members.
Compatibility between types x and y is determined by checking if y has all the properties of x.
To assign y to x, each property in x is checked to find a corresponding compatible property in y.
Now let's revisit an example:
// LL is equivalent to L unfolded once
type L = [] | { item: number, next: L }
/**
* This is because it goes one level deeper, but the types are essentially the same
*/
type LL = [] | { item: number, next: ({ item: number, next: LL } | []) }
L and LL can both be empty arrays or objects with two properties.
Here's a simple demonstration:
type A = [] | {}
type B = [] | {}
let a: A = []
let b: B = {}
a = b // a can also be an empty object
b = a // b can also be an empty array
L and LL can also be objects with properties item and next.
So, when the TS compiler encounters L, it asks:
TS: Hey L, can I treat you as an object with 2 properties?
L: Certainly, because I am typed as an object with two properties (item & next).
TS: Hello, LL, can I consider you as an object with properties item and next?
LL: Absolutely, that's my type. You can even see me as an empty array too.
TS: Okay, L and LL, would it be alright if I treat you as an empty array?
L,LL: No problem at all 😊
Due to the structural type system, both types are treated equally.
This is my interpretation of this algorithm.
UPDATE for recursion:
I highly recommend referring to the documentation for a detailed explanation about recursive type aliases.
Prior to TypeScript 3.7, there were limitations around referring to the defined type inside the type itself.
With TypeScript 3.7, such limitations have been lifted. The compiler now defers resolving type arguments at the top level of a type alias, enabling complex patterns.
Before TS 3.7, developers had to use interfaces along with types to create recursive types.
For instance:
type ValueOrArray2<T> = T | ArrayOfValueOrArray<T>;
interface ArrayOfValueOrArray<T> extends Array<ValueOrArray2<T>> {}
You can experiment with this concept on the Playground.
In essence, TS creates an alias when indirectly referring to the type itself (recursive references).
To further understand how recursive types operate, review the tests in the TypeScript repository.
I lack deep knowledge of the TS repo to conduct a thorough step-by-step analysis of this algorithm.