Object.create(null)

TypeError: Cannot convert object to primitive value

TypeScript の型の再帰上限を突破する裏技

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 が許されても, 個人的には特にやることは変わらないなと思っているのでした. 終わり.

Template String Types でパス文字列を解析してクエリする

※この記事に含まれる内容は TypeScript 4.1 のプレビュー版のものです. 今後仕様が変わり動かなくなる可能性もありますのでご注意ください.

話題の template string types で早速遊んでみます.

ゴール

.foo[1].bar といった形のパス文字列を型レベルで解析してクエリしちゃいます. こういう感じ:

type R1 = Query<{ foo: number }, "">;                                 // R1 = { foo: number }
type R2 = Query<{ foo: number }, ".foo">;                             // R2 = number
type R3 = Query<[number, string, boolean], "[1]">;                    // R3 = string
type R4 = Query<{ foo: { bar: string } }, ".foo.bar">;                // R4 = string
type R5 = Query<[[number, string], [boolean, undefined]], "[1][0]">;  // R5 = boolean
type R6 = Query<[{ foo: [[{ bar: string }]] }], "[0].foo[0][0].bar">; // R6 = string

type RE = Query<{ foo: number }, "[">;                                // RE = never
type RU = Query<{ foo: number }, ".bar">;                             // RU = unknown

.foo.bar のようなドットつなぎのみのパスについては PR でも挙げられていますが, [1] のようなパスにも同時に対応するにはどうしたらよいか, という話.

やっていき

コード全体はここから試せます.

まずはキーによる参照を定義しておきます. わざわざこれを定義するのはキーが存在しなかった場合の扱いを一括で決めておくため. Subtyping のことを考えると undefined ではなく unknown が妥当でしょう.

type Access<T, Key extends string> = Key extends keyof T ? T[Key] : unknown;

続いてクエリ実行部分本体です. ウワー.

type Sep = "." | "[" | "]";
type Query<T, Path extends string> =
    Path extends "" ? T
  : Path extends `.${infer Key}${Sep}${infer Rest}` ? QueryDot<T, Path, Key>
  : Path extends `[${infer Key}]${Sep}${infer Rest}` ? QueryBracket<T, Path, Key>
  : Path extends `.${infer Key}` ? Access<T, Key>
  : Path extends `[${infer Key}]` ? Access<T, Key>
  : never;
type QueryDot<T, Path extends string, Key extends string> =
  Key extends `${infer A}${Sep}${infer B}`
    ? never
    : Query<Access<T, Key>, Path extends `.${Key}${infer Rest}` ? Rest : never>;
type QueryBracket<T, Path extends string, Key extends string> =
  Key extends `${infer A}${Sep}${infer B}`
    ? never
    : Query<Access<T, Key>, Path extends `[${Key}]${infer Rest}` ? Rest : never>;

順番に見ていきましょう. まずは Sep はパス中の区切り文字を定義しています.

type Sep = "." | "[" | "]";

続いて Query. 一行目は空文字列ならそのまま T を返すだけ.

type Query<T, Path extends string> =
    Path extends "" ? T
  : ...;

後ろの三行もまあ簡単で, .foo[1] のようなパスを見てアクセスするだけです.

type Query<T, Path extends string> =
    ...
  : Path extends `.${infer Key}` ? Access<T, Key>
  : Path extends `[${infer Key}]` ? Access<T, Key>
  : never;

問題は真ん中の二つ. まずは .foo のあとにさらにパスが続く場合の処理を見てみましょう.

type Query<T, Path extends string> =
    ...
  : Path extends `.${infer Key}${Sep}${infer Rest}` ? QueryDot<T, Path, Key>
  : ...;

もしここに Path として .foo[1].bar が入ってきた場合, Key"foo" | "foo[1" | "foo[1]" となります. Sep が三種類あるからですね. 一方でこれらの Key のうち正しいもの (最短でマッチしているもの) は "foo" です. ではこれをどう取り出しているかというのが QueryDot の部分.

type QueryDot<T, Path extends string, Key extends string> =
  Key extends `${infer A}${Sep}${infer B}`
    ? never
    : Query<Access<T, Key>, Path extends `.${Key}${infer Rest}` ? Rest : never>;

まず conditional type で union type になっている Key を分解しつつ, Key の中に Sep が含まれるような場合は never を返すことで除いています. そして Sep が含まれない場合は Key を使ってアクセスしつつ, 残りを Path から抜き出して再度 Query に渡しています. 簡単ですね.

[1] のあとにさらにパスが続く場合もほとんど同じ. (追記: これ ] で区切られているのでわざわざこんなことしなくてもよいのでは?)

type Query<T, Path extends string> =
    ...
  : Path extends `[${infer Key}]${Sep}${infer Rest}` ? QueryBracket<T, Path, Key>
  : ...;
type QueryBracket<T, Path extends string, Key extends string> =
  Key extends `${infer A}${Sep}${infer B}`
    ? never
    : Query<Access<T, Key>, Path extends `[${Key}]${infer Rest}` ? Rest : never>;

これで完成.

type R1 = Query<{ foo: number }, "">;                                 // R1 = { foo: number }
type R2 = Query<{ foo: number }, ".foo">;                             // R2 = number
type R3 = Query<[number, string, boolean], "[1]">;                    // R3 = string
type R4 = Query<{ foo: { bar: string } }, ".foo.bar">;                // R4 = string
type R5 = Query<[[number, string], [boolean, undefined]], "[1][0]">;  // R5 = boolean
type R6 = Query<[{ foo: [[{ bar: string }]] }], "[0].foo[0][0].bar">; // R6 = string

type RE = Query<{ foo: number }, "[">;                                // RE = never
type RU = Query<{ foo: number }, ".bar">;                             // RU = unknown

はい.