TypeScript: The instantiation of types is too deep and may potentially be endless

Question

TypeScript: The instantiation of types is too deep and may potentially be endless

I have been working on implementing a versatile split type in TypeScript that can effectively split a literal string using multiple delimiters.

type Spl<T extends string, D extends string> = T extends `${infer A}${D}${infer B}` ? 
    A extends '' ? [] :
    [A, ...Spl<B, D>] : (T extends '' ? [] : [T]);

type SplMany<T extends string, D extends string[]> = D extends [infer H extends string, ...infer Tail extends string[]]
    ? 
        T extends '' ? [] : SplManyInputsManyDelimieter<[...Spl<T, H>], Tail> 
    : [T];

type SplManyInputs<T extends string[], D extends string> = T extends [infer H extends string, ...infer Tail extends string[]]
    ? [...Spl<H, D>, ...SplManyInputs<Tail, D>] : [];

type SplManyInputsManyDelimieter<T extends string[], D extends string[]> = 
  D extends [infer H extends string, ...infer Tail extends string[]] ?
    SplManyInputsManyDelimieter<[...SplManyInputs<T, H>], Tail>
    : T;    

type t1 = Spl<'1 2 3 4 5 6                            7 8 9 10 11 %test% 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 1 2 3 4 5 6                            7 8 9 10 11 %test% 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 1 2 3 4 5 6                            7 8 9 10 11 %t...

Upon testing the code, it performs well. However, I encountered an error message as the input strings grew longer:

Type instantiation is excessively deep and possibly infinite. ts(2589)

. It appears that the recursion limit was reached earlier than expected, posing challenges for efficiency.

Are there any strategies I could employ to optimize the code and support longer inputs? Additionally, I attempted to locate the source of the error message within the TypeScript compiler but without success. Does anyone know where this specific error is generated?

typescript typescript-generics

Answer 1

Answer №1

When crafting a deeply recursive conditional type, where the intention is for recursion to dive beyond just a few levels, there is a possibility of encountering recursion limits and receiving an error message stating "type instantiation is excessively deep and possibly infinite."

In situations like this, it is possible to refactor the code to apply tail recursion elimination on conditional types, as introduced in microsoft/TypeScript#45711. This approach can allow for up to a thousand levels of recursion, which typically suffices for most use cases.

The strategy involves ensuring that any recursive usage of the type adheres to being tail-recursive, where the output directly passes the result of the recursive type without requiring additional manipulation. This often entails adding an extra accumulator type parameter to the type function. For example, with Spl and SplManyInputs, the implementation could resemble the following:

type Spl<T extends string, D extends string, ACC extends string[] = []> =
    T extends `${infer A}${D}${infer B}` ? A extends '' ? ACC :
    Spl<B, D, [...ACC, A]> : (T extends '' ? ACC : [...ACC, T]);

type SplManyInputs<T extends string[], D extends string, ACC extends string[] = []> =
    T extends [infer H extends string, ...infer Tail extends string[]]
    ? SplManyInputs<Tail, D, [...ACC, ...Spl<H, D>]> : ACC;

In both scenarios, an ACC type parameter is utilized to store the final output, initially set as the empty tuple [], gradually accumulating the intermediate results. The base case involves simply returning the accumulator.

This method provides identical results to previous versions but successfully avoids recursion limitations for the given examples.

Playground link to code

Answer 2

When crafting a deeply recursive conditional type, where the intention is for recursion to dive beyond just a few levels, there is a possibility of encountering recursion limits and receiving an error message stating "type instantiation is excessively deep and possibly infinite."

In situations like this, it is possible to refactor the code to apply tail recursion elimination on conditional types, as introduced in microsoft/TypeScript#45711. This approach can allow for up to a thousand levels of recursion, which typically suffices for most use cases.

The strategy involves ensuring that any recursive usage of the type adheres to being tail-recursive, where the output directly passes the result of the recursive type without requiring additional manipulation. This often entails adding an extra accumulator type parameter to the type function. For example, with Spl and SplManyInputs, the implementation could resemble the following:

type Spl<T extends string, D extends string, ACC extends string[] = []> =
    T extends `${infer A}${D}${infer B}` ? A extends '' ? ACC :
    Spl<B, D, [...ACC, A]> : (T extends '' ? ACC : [...ACC, T]);

type SplManyInputs<T extends string[], D extends string, ACC extends string[] = []> =
    T extends [infer H extends string, ...infer Tail extends string[]]
    ? SplManyInputs<Tail, D, [...ACC, ...Spl<H, D>]> : ACC;

In both scenarios, an ACC type parameter is utilized to store the final output, initially set as the empty tuple [], gradually accumulating the intermediate results. The base case involves simply returning the accumulator.

This method provides identical results to previous versions but successfully avoids recursion limitations for the given examples.

Playground link to code

TypeScript: The instantiation of types is too deep and may potentially be endless

Answer №1

Similar questions

The callback function does not seem to work when using MUI v4 PropFunc

Combine the selected values of two dropdowns and display the result in an input field using Angular

Getting rid of the Chrome default page after a user has logged in - here's how to do

Issues with displaying data in Angular Material table

Establishing the types of object properties prior to performing a destructuring assignment

The specialized middleware in Next.js gets dispatched to the browser

Encountering compilation issues when transitioning from Angular 7 to Angular 8

Angular 12: How to detect when a browser tab is closing and implement a confirmation dialog with MatDialog

Transforming Uint8Array into BigInt using Javascript

What is the best way to identify the data type of elements in an array using TypeScript?

Why isn't this directive registering changes on ion-input in Angular and Ionic?

What is the best way to implement a comprehensive switch case in Typescript using string enums that are referencing other string enums?

What is the best way to include a minified bootstrap file in a TypeScript project?

What is preventing the TypeScript compiler from accepting this code that appears to be valid?

How can I correctly enable the css property in Emotion 11 and Next.js 10 applications?

At a specific duration of inactivity on the website, I am automatically redirected to the login page due to session expiration

Tips for restricting custom number types based on if conditions in TypeScript

The PDF can be accessed from the console but the network tab is not visible

Having trouble locating the error in my Angular and Spring Security application

The value specified as type '{ value: BigNumber; }' cannot be assigned to the parameter type 'Overrides & { from?: string | Promise<string> | undefined; }'