🌀

TypeScriptにおける型の再帰回数の限界

2020/12/11に公開

ナイーブに再帰すると40-50回くらいですが、その制限を突破するテクが知られています。じゃあ第一の限界を突破したらどうなるの?というのが気になって調べてみました。

上記記事で実装例になっているRepeat2型の上限は3000回程度ですが、これは再帰回数の限界というより、長さNの配列を生成するため呼び出しごとに [T, ...A] を実行しているため計算量が ${\rm O}(N^2)$ になっているのが原因っぽい。N=3000を超えたあたりでTS Playgroundが不安定になります。

純粋な再帰回数の限界を探るため、以下のようなコードで検証しました。TSは整数型の扱いが苦手なので、ループ回数は二進数にデコードしてbooleanのタプルとして表現し、加算はconditional typesで頑張る。

// 整数の二進数表現Nを取り、次の数を返す
type Inc<N extends boolean[]> =
  N extends [false, ...infer N2] ? [true, ...N2]
  : N extends [true, false, ...infer N2] ? [false, true, ...N2]
  : N extends [true, true, false, ...infer N2] ? [false, false, true, ...N2]
  : N extends [true, true, true, false, ...infer N2] ? [false, false, false, true, ...N2]
  : N extends [true, true, true, true, false, ...infer N2] ? [false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, false, false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, true, true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, false, false, false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, true, true, true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, false, false, false, false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, true, true, true, true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, false, false, false, false, false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, true, true, true, true, true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, ...N2]
  : N extends [true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, false, ...infer N2] ? [false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, ...N2]
  : []

type RecurseSub<T> =
    T extends { __rec: never } ? never
  : T extends { __rec: { __rec: infer U } } ? { __rec: RecurseSub<U> }
  : T extends { __rec: infer U } ? U
  : T;
type Recurse<T, H extends "__hack" = "__hack"> =
  T extends { __rec: unknown }
    ? { [H0 in H]: Recurse<RecurseSub<T>> }[H]
    : T;

type Loop<I extends boolean[], N extends boolean[]> =
  I extends N ? 'ok' : {__rec: Loop<Inc<I>, N>}

type F<I extends boolean[], N extends boolean[]> =
  I['length'] extends N['length'] ? Recurse<Loop<I, N>> : 'error'

type B0 = false
type B1 = true

// OK
type X14 = F<
[
  B0, B0, B0, B0, B0, 
  B0, B0, B0, B0, B0, 
  B0, B0, B0, B0
],[
  B1, B1, B1, B1, B1,
  B1, B1, B1, B1, B1,
  B1, B1, B1, B1
]>

// TS 4.0.5: OK
// TS 4.1.2: Type instantiation is excessively deep and possibly infinite.(2589)
type X15 = F<
[
  B0, B0, B0, B0, B0, 
  B0, B0, B0, B0, B0, 
  B0, B0, B0, B0, B0, 
],[
  B1, B1, B1, B1, B1,
  B1, B1, B1, B1, B1,
  B1, B1, B1, B1, B1,
]>

// 15を超えたあたりでplaygroundが不安定になる

Playground

わかったこと:

再帰回数の上限は $2^{15}$ 回くらい
TSのバージョンによって最大値は微妙に違う。最新版でちょっと減ったぞ！！！

再帰上限のチェックについては複数の条件があるようで、現実的に10k回オーダーの再帰が可能だとは限りません。筆者は非常に複雑な型を書いたら再帰300回程度でTS2589エラーになったという事象を経験しています。

Discussion