TypeScript: Type instantiation is excessively deep and possibly infinite

Question

I am trying to implement a generic split type in TypeScript that is able to 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 %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 %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', ' '>;
type t1_ = Spl<'1 ', ' '>;
type t1__ = Spl<'1', ' '>;
type t1___ = Spl<'', ' '>;
type t3 = SplManyInputs<[' 1 2 3 ', ' 3 4 ', '5 6'], ' '>;
type t3_ = SplManyInputs<[], ' '>;
type t4 = SplManyInputsManyDelimieter<['1 2', '3 4', '5 6'], [' ']>;
type t4_ = SplManyInputsManyDelimieter<['1 2', '3 4', '5 6'], []>;
type t4__ = SplManyInputsManyDelimieter<[], [' ']>;

type test = SplMany<'0_1 0_2 0_3 0_4 0_5 0_6 0_7 0_8 0_9 1_0 1_1 1_2 1_3 1_4 1_5 1_6 1_7 1_8 1_9 2_0 2_1 2_2 2_3 2_4 2_5 2_6 2_7 2_8 2_9 3_0 3_1 3_2 3_3 3_4 3_5 3_6 3_7 3_8 3_9 4_0 4_1 4_2 4_3 4_4 4_5 4_6 4_7 4_8', [' ', '_']> // error!
// Type instantiation is excessively deep and possibly infinite.

See the TS playground link

The code works but when the input gets long enough, I get the error Type instantiation is excessively deep and possibly infinite. ts(2589). I guess splitting this way is not very efficient but I expected the recursion limit to be somewhat higher.

Are there any tricks I can do optimize the code to allow for longer inputs? I also tried to find the part of the TypeScript compiler responsible for the error message but could not find it. Does anyone know where the error is emitted?

Does [this approach](https://tsplay.dev/Nneaow) meet your needs? If so I could write it up as an answer; if not, what am I missing? — jcalz, Dec 01 '22 at 21:18
Oh, so using an accumulator optimizes the type instantation? I think the approach you suggest meets my needs but it's a mystery to me why that works so definitely would appreciate an answer with details! Thanks! — Oleksii Rudenko, Dec 01 '22 at 21:29
Okay I'll write up an answer when I get a chance, but as a preview: [tail recursion elimination on conditional types](https://www.typescriptlang.org/docs/handbook/release-notes/typescript-4-5.html#tail-recursion-elimination-on-conditional-types) — jcalz, Dec 01 '22 at 21:41
so if I get it right, the problem is that recursive calls like `[A, ...Spl]` (or `Char | GetChars` from the documentation example) cannot be optimized because they create intermediate results. But direct calls to itself like `Spl` can be! And usage of the accumulator allows to carry the intermediate state without hitting the limits. — Oleksii Rudenko, Dec 01 '22 at 21:53

jcalz · Accepted Answer · 2022-12-02T00:07:31.867

When you write a deeply recursive conditional type where you intend the recursion to descend more than a few dozen levels, you might run into recursion limits and the "type instantiation is excessively deep and possibly infinite" error message.

If such cases, you can often refactor to use tail recursion elimination on conditional types as implemented in microsoft/TypeScript#45711, and get up to a thousand levels of recursion, which is often good enough for most purposes.

The approach is to make sure any recursive use of the type is tail-recursive, where the result of the recursive type is passed directly as the output and doesn't need additional manipulation. Often this can be done by adding an extra accumulator type parameter to your type function. For Spl and SplManyInputs, it could possibly look like this:

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 cases I made an ACC type parameter to hold the eventual output, which starts off as the empty tuple [], and gradually is filled with the intermediate results. The base case is just returning the accumulator.

You can verify that this gives the same results as your versions, but does not hit recursion limits for the given examples.

Playground link to code

TypeScript: Type instantiation is excessively deep and possibly infinite

1 Answers1

Linked