TypeScriptの型で遊ぶ時、再帰制限を（合法的に）突破する

2024/9/11追記：現在のバージョン(5.6) において、再帰深度上限は1000になっています。多くのケースはこの記事のような手法を使うまでもなく単純な再帰で解決できるはずです

TypeScriptの型の再帰は50が上限です。

先日、 @kgtkr さんがTypeScriptの型で遊ぶ時、再帰制限を無効化するという記事で、 その再帰制限を、ソースコードを書き換えることで突破して、型レベル BrainF**k などで遊んでいるのを見ました。

タイトルで合法的と言っておきながら、別にソースコードを書き換えるのが何らかの法に触れる訳ではないのですが、とは言え @kgtkr さんも記事の中で、

• 当然ですがプロダクトで使うことは想定していません、やめましょう。

と言っている通り、これをプロダクトに採用するわけにはいきません。

というわけで、ソースコード書き換えをせずに再帰制限を突破してやろう、というのがこの記事の趣旨です。

文字列を分割する（再帰制限に引っかかる例）

Template literal types がマージされたので、 typescript@next を使えば文字列リテラル型を分割できます。単純に考えると、こんなコードが思い浮かびますね。

type ToTuple<T extends string> = T extends `${infer U}${infer V}` ? [U, ...ToTuple<V>] : [];
type A = ToTuple<'Nyan'>; // ['N', 'y', 'a', 'n']

-> Playgroundで見る

このまま文字列を長くしていくと、23文字までは大丈夫ですが、

type ToTuple<T extends string> = T extends `${infer U}${infer V}` ? [U, ...ToTuple<V>] : [];
type A = ToTuple<'Nyanyanyanyanyanyanya!!'>;
type B = A['length']; // 23

-> Playgroundで見る

次で死にます。つらい。

type ToTuple<T extends string> = T extends `${infer U}${infer V}` ? [U, ...ToTuple<V>] : [];
type A = ToTuple<'Nyanyanyanyanyanyanya!!!'>; // Type instantiation is excessively deep and possibly infinite.(2589)
type B = A['length'];

-> Playgroundで見る

再帰制限が50なのに23で頭打ちになっているということは1回の ToTuple の再帰の間に内部の再帰カウンタが2回インクリメントされているということになります。コードを追っていないので詳しく分かりませんが、 ...ToTuple<V> で呼び出した結果を展開しているあたりが問題なのかもしれません。
これは比較的簡単に回避できて、少し書き方を変えるだけで、

type ToTuple<T extends string, Result extends string[] = []> = T extends `${infer U}${infer V}` ? ToTuple<V, [...Result, U]> : Result;
type A = ToTuple<'Nyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!'>;
type B = A['length']; // 45

-> Playgroundで見る

とまあこのくらいまで伸ばすことが可能です。
これで上限の50に近付きましたね。しかしこれ以上はこのやり方では無理で、46文字以上にするとエラーになります。

どうすればいいんだ……やはりソースコードをいじるしかないのか……。

と、なる前に、ちょっと考え方を変えてみましょう。

再帰の再帰

再帰制限というのは、つまりスタックの高さに対する制限です。
ToTuple が 46 文字分で引っかかったのは、

---------------
ToTuple<T45>  |
ToTuple<T44>  |
...          50個
ToTuple<T4>   |
ToTuple<T3>   |
ToTuple<T2>   |
ToTuple<T1>   |
...           |
---------------

とまあこんな感じで50個分のスタックがいっぱいになったからです。1文字読む度に1個スタックが高くなるのですから、このままの実装では上限を突破できません。
しかし、再帰制限というのはあくまでスタックの高さに対する制限です。ステップ数の制限ではありません。
天井が低いのでこれ以上皿が積めないなら、横にもう一個山を作ってしまえば良いのです。

----------------------------------
ToTuple<T45>  |   ToTuple<T90>   |  
ToTuple<T44>  |   ToTuple<T89>   |  
...          50個 ...          50個
ToTuple<T4>   |   ToTuple<T49>   |  
ToTuple<T3>   |   ToTuple<T48>   |  
ToTuple<T2>   |   ToTuple<T47>   |  
ToTuple<T1>   |   ToTuple<T46>   |
...           |   ...            |
----------------------------------

横のもう一個の山をどうやって増やすかというと、TypeScriptの型レベル計算にはループ構文はないので、やはり再帰でやらなければなりません。なので上図のように真横に山を増やすことはできない（再帰する時にどうしてもスタックを消費するため）のですが、例えば、
「最大20文字読み取る」という操作Aと、「Aを20回繰り返す」という操作Bを考えてみると、20*20で400文字読み取れることになります。それでいて、スタックの高さは、20回再帰したときのBの高さ+20回再帰したときのAの高さが一番高くなるはずなので、それでも40回で、上限に達しないはずです(フラグ)。

なのでとりあえず、 ToTuple を上限20文字まで読んでTupleにするように改造してみましょう。この後同じようなジェネリクスを何個か作ることになるので、このジェネリクスは ToTuple0 とします。

type First<T extends string> = T extends `${infer U}${infer _}` ? U : never;
type RemoveFirst<T extends string> = T extends `${infer _}${infer U}` ? U : never;

type ToTuple0<T extends string, Result extends string[] = [], Counter extends unknown[] = []> =
    ['', Counter['length']] extends { 0: T } | { 1: 20 } ? [T, Result] :
    ToTuple0<RemoveFirst<T>, [...Result, First<T>], [...Counter, unknown]>;

type A = ToTuple0<'Nyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!'>;
type B = A[1]['length']; // 20

-> Playgroundで見る

一気に複雑になって、謎の判定式が含まれるようになりました。 ['', Counter['length']] extends { 0: T } | { 1: 20 } } ? というのが何かと言うと、 '' extends T もしくは Counter['length'] extends 20 のどちらかを満たしているということを表す条件式です。
どうやらTypeScriptでは再帰の途中でConditional Typesが含まれると、そこで再帰カウンタが増えてしまうようなのですが、 T1 extends U1 と T2 extends U2 のどちらかを満たすという条件を [T1, T2] extends { 0: U1 } | { 1: U2 } という条件に置き換えることで、再帰カウンタの上昇を1回に抑えることができます。
ここでは利用しませんが、 同様に、T1 extends U1 と T2 extends U2 の両方を満たすという条件は、 [T1, T2] extends [U1, U2] と表記することも可能です。

つまり、T が空文字か、 Counter の長さが 20 だった時に [T, Result] を返す、そうでなければ ToTuple0 を再帰的に呼び出す、という処理を行っている訳ですね。
こうすることによって、どんなに長い文字列リテラル型を渡しても再帰制限に引っかからない代わりに、20文字までしか分割しないジェネリクスが作れました。次は、このジェネリクスを再帰的に呼び出すジェネリクスをつくります。

type ToTuple1<T extends string, Result extends string[] = [], Counter extends unknown[] = []> =
    ToTuple0<T, Result> extends [infer T, infer Result] ?
    ['', Counter['length']]  extends { 0: T } | { 1: 19 } ? Result :
    ToTuple1<Extract<T, string>, Extract<Result, string[]>, [...Counter, unknown]> :
    never;

type A = ToTuple1<'Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!!'>;
type B = A['length']; // 100

-> Playgroundで見る

100文字だって読み込める。
やっていることは何かというと、まず ToTuple0 を呼び出して、その結果を型推論を利用して受け取ります。
その後は同じような条件分岐を行って、 Counter が上限に達していなかったら再帰する処理になっています。
先程と違って上限が19になっているのは、判定の前に ToTuple0 の呼び出しが一回挟まるからで、上限に達したと判定された時には ToTuple0 は20回呼び出されたことになります。

これで理論的には400文字まで読めるはずです。やってみましょう。

type A = ToTuple1<`
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
`>; // Type instantiation is excessively deep and possibly infinite.(2589)
type B = A['length'];

-> Playgroundで見る

駄目でした(フラグ回収)

敗因は、Conditional Types を2重に使わないといけないため、再帰カウンタが2回インクリメントされてしまうことです。つまり、 ToTuple0 の再帰一回のコストが1なのに対して、 ToTuple1 の再帰1回のコストは2とカウントする必要があるようです。色々試してみましたが、コストの合計が 46 以下になればエラーが出ないので、その範囲で最も読める文字数が大きい組み合わせは、 ToTuple0 を22回再帰して ToTuple1 を12回再帰するか、 ToTuple0 を24回再帰して ToTuple1 を11回再帰するのどちらかでした。つまり最大264文字まで読み取れることになります。

type First<T extends string> = T extends `${infer U}${infer _}` ? U : never;
type RemoveFirst<T extends string> = T extends `${infer _}${infer U}` ? U : never;

type ToTuple0<T extends string, Result extends string[] = [], Counter extends unknown[] = []> =
    ['', Counter['length']] extends { 0: T } | { 1: 22 } ? [T, Result] :
    ToTuple0<RemoveFirst<T>, [...Result, First<T>], [...Counter, unknown]>;

type ToTuple1<T extends string, Result extends string[] = [], Counter extends unknown[] = []> =
    ToTuple0<T, Result> extends [infer T, infer Result] ?
    ['', Counter['length']]  extends { 0: T } | { 1: 11 } ? Result :
    ToTuple1<Extract<T, string>, Extract<Result, string[]>, [...Counter, unknown]> :
    never;

type A = ToTuple1<`
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
Nyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanyanya!!!
`>;
type B = A['length']; // 264

-> Playgroundで見る

再帰の再帰の再帰

さて。

これでFinish！？な訳無いデショ！

264文字、当初の45文字に比べれば6倍近く読めるようになりましたが、ここで終わっては所詮その程度。英数字なら1ツイートに収まってしまいます。せめて1000文字くらいは行きたい。
どうするか。同じことをします。
つまり、 ToTuple0 を繰り返し呼ぶ ToTuple1 を作ったように、 ToTuple1 を繰り返し呼ぶ ToTuple2 を作るのです。

作りました。なお ToTuple1 も Result ではなく ToTuple0 と同じように [T, Result] を返す仕様に改造してあります。

type ToTuple2<T extends string, Result extends string[] = [], Counter extends unknown[] = []> =
    ToTuple1<T, Result> extends [infer T, infer Result] ?
    ['', Counter['length']]  extends { 0: T } | { 1: 7 } ? Result :
    ToTuple2<Extract<T, string>, Extract<Result, string[]>, [...Counter, unknown]> :
    never;

-> Playgroundで見る

コスト上限は47で、 ToTuple0 を15回、 ToTuple1 を8回、 ToTuple2 を8回繰り返すパターンが最も効率が良く、960文字まで読み取れます。憧れの1000文字まであと少し。

再帰の再帰の再帰の再帰の……

同じようにして ToTuple3, ToTuple4, と追加していきます。それぞれの最適な繰り返し回数の組み合わせは以下のようになります

	繰り返し回数	読み取り可能文字数
ToTuple0	45	45
ToTuple0, ToTuple1	22, 12	264
ToTuple0, ToTuple1, ToTuple2	15, 8, 8	960
ToTuple0, ToTuple1, ToTuple2, ToTuple3	12, 6, 6, 6	2592
ToTuple0, ToTuple1, ToTuple2, ToTuple3, ToTuple4	9, 5, 5, 5, 5	5625
ToTuple0, ToTuple1, ToTuple2, ToTuple3, ToTuple4, ToTuple5	10, 4, 4, 4, 4, 4	10240
ToTuple0, ToTuple1, ToTuple2, ToTuple3, ToTuple4, ToTuple5, ToTuple6	3, 4, 4, 4, 4, 4, 4	12288
ToTuple0, ToTuple1, ToTuple2, ToTuple3, ToTuple4, ToTuple5, ToTuple6, ToTuple7	10, 3, 3, 3, 3, 3, 3, 3	21870
ToTuple0, ToTuple1, ToTuple2, ToTuple3, ToTuple4, ToTuple5, ToTuple6, ToTuple7, ToTuple8	4, 3, 3, 3, 3, 3, 3, 3, 3	26244

DB設計でこんなの書いたら怒られそうな表になってしまった。なお5625から先は理論値です。試してみたらブラウザのV8エンジンが落ちました。4701までは大丈夫だったのでローカルで頑張れば行けるかもしれない。
再帰制限は回避できても、効率的にはかなり良くない計算をやっているので（内部的には再帰1回ごとにサイズを+1した配列が作られる）メモリもCPUもバカ食いしますが、1000文字くらいならなんとかなりそうです。1000文字あればけっこう型遊びができますね、そう、こんな風に。