🌀

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

2020/12/10に公開

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

// 整数の二進数表現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のバージョンによって最大値は微妙に違う。最新版でちょっと減ったぞ！！！

ログインするとコメントできます