TypeScript 4.1 で再帰的な conditional type の定義に制限がなくなり (ref), 今後ますます再帰的な型定義をする / 触れることが多くなろうかと思います. 一方で TypeScript が型をインスタンス化する際の再帰の上限はそこそこ厳しく, ちょっと複雑なことをするとすぐに頭を打ってしまいます. 困りましたね.
ということで裏技を使ってこの再帰上限を突破する方法を紹介します. 実は以前に型レベル Brainfuck インタプリタを実装した時にも使っていたのですが, あまり知られていないようなので改めて.
ちなみにこちらの記事のように TypeScript 自体のコードに手を入れたりはしません.
以下使用している TypeScript のバージョンは 4.1.0-dev.20200911 です.
上限を突破する例
まずは実際に再帰的な型定義を行い, 上限を突破する様子を見てみましょう.
以下は長さ N のタプル型を作る型です.
type Repeat<T, N extends number> = RepeatSub<T, N, []>; type RepeatSub<T, N extends number, A extends T[]> = A["length"] extends N ? A : RepeatSub<T, N, [T, ...A]>;
これは N が小さいときは上手く動くのですが, 例えば N = 100 のように N が大きくなると先述の上限に当たり, エラーとなってしまいます.
// Expected: XS = ["x", ..., "x"] and XS["length"] = 100 // Actual: Type instantiation is excessively deep or possibly infinite. type XS = Repeat<"x", 100>;
ということで上限を回避する方法を探っていきましょう.
回避策 1. オブジェクトのプロパティ内で再帰する
さて TypeScript 4.1 では任意の再帰的な conditional type が許されるようになりましたが, それ以前に TypeScript 3.7 から, 再帰的に使用している型がオブジェクトのプロパティに含まれる場合などについては, この制限が緩和されていました (ref). そして注目したいのは, この場合は先程の再帰の上限の対象からは外れるということです (インスタンス化が遅延されるため?).
ということで以下のように RepeatSub の変形版を定義してみましょう. これを使用した場合は N = 100 でもエラーとならないことが確認できます. やったね.
type RepeatSub2<T, N extends number, A extends T[]> = A["length"] extends N ? A : { __rec: RepeatSub2<T, N, [T, ...A]> }; // No errors type T = RepeatSub2<"x", 100, []>;
一方で結果は __rec というプロパティを持つオブジェクトの中に多重にネストされた形となってしまいました.
// T0 = { __rec: { __rec: { __rec: { __rec: ["x", "x", "x", "x"] } } } } type T0 = RepeatSub2<"x", 4, []>;
続いてここから欲しかった型を取り出したいわけですが, 素朴にやるとやはり N 回の再帰を行うことになり, そこで再帰の上限に当たってしまいます. ではどうすれば...?
回避策 2. ネストされたオブジェクトから対数オーダーで型を取り出す
答えとなるのが以下の定義.
type RecurseSub<T> = T extends { __rec: never } ? never : T extends { __rec: { __rec: infer U } } ? { __rec: RecurseSub<U> } : T extends { __rec: infer U } ? U : T;
この定義は 3 行目がキモで, 2 つ連続した __rec を 1 つの __rec にし, さらに下位についても再帰的に同じ操作を行います. そしてこの再帰もオブジェクトのプロパティの中なので, やはり問題となっていた再帰上限は適用されません.
つまり何が言いたいかというと, これを使うと 1 ステップでオブジェクトのネストを半分まで減らすことができます.
// T0 = { __rec: { __rec: { __rec: { __rec: ["x", "x", "x", "x"] } } } } type T0 = RepeatSub2<"x", 4, []>; // T1 = { __rec: { __rec: ["x", "x", "x", "x"] } } type T1 = RecurseSub<T0>; // T2 = { __rec: ["x", "x", "x", "x"] } type T2 = RecurseSub<T1>; // T3 = ["x", "x", "x", "x"] type T3 = RecurseSub<T2>;
ということで, これを繰り返す部分を (素朴に) 再帰的に定義すれば, 元々は N に対して上限がかかっていたところを, N の対数に対して上限がかかるようにすることができてしまいます.
type Recurse<T> = T extends { __rec: unknown } ? Recurse<RecurseSub<T>> : T;
これを使って Repeat の改良版を定義すると, 無事 N = 100 の場合でもタプル型を生成することが出来ました. よかったですね.
type Repeat2<T, N extends number> = Recurse<RepeatSub2<T, N, []>>; // XS2 = ["x", ..., "x"] and XS2["length"] = 100 type XS2 = Repeat2<"x", 100>;
ちなみにざっと試したところ, 時間はかかりますが N = 3000 くらいまでは大丈夫でした.
コード全体はこちら.
おまけ
このテクニックを使った再帰的な型定義は, Recurse の定義のみを少し変更するだけで現行の最新安定版である TypeScript 4.0 でも使用することができます.
type Recurse<T, H extends "__hack" = "__hack"> = T extends { __rec: unknown } ? { [H0 in H]: Recurse<RecurseSub<T>> }[H] : T;
なので TypeScript 4.1 で再帰的な conditional type が許されても, 特にやることは変わらないなと思っているのでした. 終わり.
