TS2589

Type instantiation is excessively deep and possibly infinite.

Broken Code ❌

type BubbleSort<A extends any[], Curr extends number = A['length']> = Curr extends 1
  ? A
  : A extends [infer F, infer S, ...infer Rest]
    ? BubbleSort<
        [
          ...(M.Comparator<M.Num<F>, M.Num<S>> extends true
            ? [S, ...BubbleSort<[F, ...Rest], M.Sub<Curr, 1>>]
            : [F, ...BubbleSort<[S, ...Rest], M.Sub<Curr, 1>>]),
        ],
        M.Sub<Curr, 1>
      >
    : never;
 
type Demo1 = BubbleSort<[9, 8, 2, 6, 5, 4, 1]>;

Solution:

This TypeScript error occurs because the type instantiation for recursive type definitions is too deep for the compiler to handle, leading to an "excessively deep and possibly infinite" error. Recursive type definitions can cause performance issues in the TypeScript compiler, especially when the recursion depth is significant.

To fix this, you can try to simplify the type or reduce the depth of recursion. Here, we'll try to simplify the type definition by reducing the recursion depth and providing an alternative approach that avoids excessive type instantiation.

Solution:

type Swap<A extends any[]> = A extends [infer F, infer S, ...infer Rest]
  ? M.Comparator<M.Num<F>, M.Num<S>> extends true
    ? [S, F, ...Rest]
    : [F, S, ...Rest]
  : A;
 
type BubbleSortOnce<A extends any[]> = A extends [infer F, infer S, ...infer Rest]
  ? [F, ...BubbleSortOnce<Swap<[S, ...Rest]>>]
  : A;
 
type BubbleSort<A extends any[], Curr extends number = A['length']> = Curr extends 1
  ? A
  : BubbleSort<BubbleSortOnce<A>, M.Sub<Curr, 1>>;
 
type Demo1 = BubbleSort<[9, 8, 2, 6, 5, 4, 1]>;