TypeScript 4.1, released today, comes with an important change: official support for recursive conditional types. This allows us to define recursive types easily, and I expect using recursive types will become much more common than before.
For example, you can define a type Repeat<T, N> that makes a tuple type of length N filled with T as follows.
type Repeat<T, N extends number> = _Repeat<T, N, []>;
type _Repeat<T, N extends number, A extends T[]> =
A["length"] extends N
? A
: _Repeat<T, N, [T, ...A]>;
// XS = ["x", "x", "x", "x", "x"]
type XS = Repeat<"x", 5>;
While it's easy to define, the TypeScript compiler has a tight limit on type instantiation depth (almost equal to the number of recursions here). So if N gets lager, Repeat<T, N> cannot be instantiated.
// Wanted: XS = ["x", ..., "x"] and XS["length"] = 100
// Actual: error (Type instantiation is excessively deep or possibly infinite.)
type XS = Repeat<"x", 100>;
As of TypeScript 4.1, the instantiation depth limit is 50. Perhaps this will not be a problem in common situations, but some people might think this is too strict.
When I implemented a type level Brainfuck interpreter, I faced this limitation. Because every execution step requires some instantiation of types, my interpreter couldn't execute even simple programs like "Hello, world!".
Eventually, I found that we can defer the limit, and types that have over 1,000 recursions can be instantiated. In this post, I'll introduce you how to defer the limit and how it works.
Step 1. Put recursive instantiation into an object property
Even before TypeScript 4.1, some sort of recursive type definitions are supported and used. A notable one is that, since TypeScript 3.7, type definitions that recursively referencing themselves are allowed if the references are in object properties or array elements.
Here is the key of Step 1: types in object properties or array elements will not be immediately instantiated, but their instantiations are deferred. Because of this, by putting recusvie type references into object properties, we can avoid the instantiation depth limit.
(Actually I don't know how the TypeScript compiler exactly works. Please tell me if my understanding is wrong.)
So let's change the definition of _Repeat<T, N, A>, the subroutine of Repeat<T, N>.
type _Repeat<T, N extends number, A extends T[]> =
A["length"] extends N
? A
: { __rec: _Repeat<T, N, [T, ...A]> }; // recurse in an object property
By this change, the tuple type that we want is now wrapped by a deeply nested object type.
// T0 = { __rec: { __rec: { __rec: { __rec: ["x", "x", "x", "x"] } } } }
type T0 = _Repeat<"x", 4, []>;
In exchange for this, we can instantiate it even if N is large.
// No errors
type T = _Repeat<"x", 100, []>;
Next, we want to peel this deeply nested object type to retrieve the tuple type. However, a naïve implementation will require N recursions, which means it will hit the limit there. So we have to use another trick.
Step 2. Peel nested object type in a logarithmic order
The answer is the following.
type _Recurse<T> =
T extends { __rec: never } ? never
: T extends { __rec: { __rec: infer U } } ? { __rec: _Recurse<U> }
: T extends { __rec: infer U } ? U
: T;
This can halve the number of nests in just one step.
// T0 = { __rec: { __rec: { __rec: { __rec: ["x", "x", "x", "x"] } } } }
type T0 = _Repeat<"x", 4, []>;
// T1 = { __rec: { __rec: ["x", "x", "x", "x"] } }
type T1 = _Recurse<T0>;
// T2 = { __rec: ["x", "x", "x", "x"] }
type T2 = _Recurse<T1>;
// T3 = ["x", "x", "x", "x"]
type T3 = _Recurse<T2>;
The third line of the definition of _Recurse<T> is the key: it squashes two __recs into one __rec, and do the same operation on the child recursively. Because this recursive operation is done in an object property as Step 1, the instantiation depth limit is not applied.
Recurse<T> can be defined to repeat the above operation. Because each step halves the number of nests, it only requires about log_2 N steps to peel all N nests.
type Recurse<T> =
T extends { __rec: unknown }
? Recurse<_Recurse<T>>
: T;
(Note that the number of steps here is not the same as the instantiation depth that the TypeScript compiler limits. It seems one step costs more than one instantiation depth for some reason.)
Now we are ready! Let's define the improved version of Repeat<T, N>, and check it works for larger N.
type Repeat<T, N extends number> = Recurse<_Repeat<T, N, []>>;
// XS = ["x", ..., "x"] and XS["length"] = 100
type XS = Repeat<"x", 100>;
🎉
Top comments (1)
really impressed with your work above @susisu just tried it out and works perfectly.
felt I new the recursive types ok, but after following though this I feel like a amature.