辞書を作る関数に TypeScript で執拗に型をつける

TypeScript プログラミング 小ネタ

未来人のみなさまご機嫌いかがでしょうか. この記事が書かれた時点の TypeScript のバージョンは 3.6.4 です.

お題

以下の JavaScript の関数に TypeScript で型をつけることを考えます1.

function makeDict(prop, entries) {
  const dict = {};
  for (const entry of entries) {
    dict[entry[prop]] = entry;
  }
  return dict;
}

これは見ての通り, 配列から辞書を作ります2.

const entries = [
  { id: "a", name: "Foo" },
  { id: "b", name: "Bar" },
  { id: "c", name: "Baz" },
];

const dict = makeDict("id", entries);
// dict = {
//   "a": { id: "a", name: "Foo" },
//   "b": { id: "b", name: "Bar" },
//   "c": { id: "c", name: "Baz" },
// }

レベル 1

型をつけるといっても様々な段階があるので, 型によって何を保証したいかを明確にしつつ進めていきましょう.

まずは基本中の基本として, パラメータの prop は文字列, entries は配列であり, 戻り値は辞書であることを保証してみます3. これは簡単な型注釈を書けば良いだけですね.

type Dict = { [key: string]: any };

function makeDict(prop: string, entries: any[]): Dict {
  const dict: Dict = {};
  for (const entry of entries) {
    dict[entry[prop]] = entry;
  }
  return dict;
}

makeDict を使う側は特に変わりません.

const entries = [
  { id: "a", name: "Foo" },
  { id: "b", name: "Bar" },
  { id: "c", name: "Baz" },
];

const dict = makeDict("id", entries);

const a = dict.a;
// a: any = { id: "a", name: "Foo" }

レベル 1 のコード全体はこちら. 変数や式にカーソルを当てると型が表示されて便利です.

レベル 2

レベル 1 で型によって得られる保証は最低限のものなので, いくつか気になる部分があります.

まず, entries の要素が持っていなかったり, 持っていても string 型でなかったりするプロパティ名を prop に指定することができてしまいます. これらは以下のような, おそらく意図しないであろう結果となります.

const dict = makeDict("key", entries);
// dict = { "undefined": { id: "c", name: "Baz" } }

また dict.a のような辞書の中身の参照は any 型になってしまうため, entries の要素が本来どういったプロパティを持っていたのかの情報は失われてしまいます.

const dict = makeDict("id", entries);

const a = dict.a;
a.say(); // runtime error

レベル 2 では, これら 2 つのエラーを型検査で見つけられるようにしてみましょう.

まずは辞書の型を修正して, 具体的な型が得られるようにします. ここでは一般に T 型を持つ辞書の型を定義しておきます.

type Dict<T> = { [key: string]: T };

続いて makeDict に対する型付けは以下のようになります.

type Entry<P extends string> = { [P0 in P]: string };

function makeDict<P extends string, T extends Entry<P>>(
  prop: P, entries: T[],
): Dict<T> {
  const dict: Dict<T> = {};
  for (const entry of entries) {
    dict[entry[prop]] = entry;
  }
  return dict;
}

P は見ての通り prop の型で, "id" のような文字列のリテラル型となることを期待しています4. T は entries の各要素の型で, extends によって欲しい条件 (型の上界) を指定しています.

T の条件を詳しく見てみましょう. Entry<P> = { [P0 in P]: string } は mapped type と呼ばれるもので, 一般的な話は参照先を見てもらえると良いのですが, ここでは P はリテラル型を期待しているので, たとえば P = "id" であったとすると { id: string } が得られます. 条件としてはこれを extends しているので, つまり T は少なくとも id: string を持ち, その他にもプロパティを持ち得る型ということになります.

実際に使ってみると, まず prop に entries に存在しないプロパティを指定すると, 期待通りに型エラーとなることがわかります. ここで makeDict に対する型引数は, 関数に与えられた引数から推論されて, 上記で期待した通り P = "id" や P = "key" となっています.

const entries = [
  { id: "a", name: "Foo" },
  { id: "b", name: "Bar" },
  { id: "c", name: "Baz" },
];

const dict = makeDict("id", entries);   // ok
const dict2 = makeDict("key", entries); // type error

また辞書の中身を参照した場合も, 元々の型がきちんと維持されています.

const a = dict.a;
// a: { id: string, name: string } = { id: "a", name: "Foo" }

よかったですね. レベル 2 のコード全体はこちら.

レベル 3

さてレベル 2 で定義した Dict<T> には key に関する制約がないため, あらゆる文字列を使ってアクセスできてしまいます. このため, 適当なキーを使ってアクセスした場合は, 実際は存在しない (undefined) のに型は T ということになってしまいます5.

const x = dict.x;
// x: { id: string, name: string } = undefined

というわけでレベル 3 では, 型の上で辞書のキーの集合を持つようにして, 適当なキーではアクセスできないようにしてみましょう.

これを実現するためには, 当然 entries の各要素が持っている id の中身が型レベルで利用できるようになっている必要があります. このため, entries は const assertion をつけて宣言しておきます.

const entries = [
  { id: "a", name: "Foo" },
  { id: "b", name: "Bar" },
  { id: "c", name: "Baz" },
] as const;
// entries: readonly [
//   { readonly id: "a", readonly name: "Foo" },
//   { readonly id: "b", readonly name: "Bar" },
//   { readonly id: "c", readonly name: "Baz" },
// ]

as const をつけることで, entries は単なる配列ではなく読み取り専用のタプル型となり, 要素ごとの詳細が維持されます.

続いて, この entries の型 (typeof entries) を辞書の型に変換することを考えてみましょう. まずは entries に対応する型を用意します. P はこれまでと同じく "id" といった文字列リテラル型を期待しています.

type Entry<P extends string> = { readonly [P0 in P]: string };
type Entries<P extends string> = readonly Entry<P>[];

次に一般的なユーティリティ型 Elem<T> を定義します. これは配列の要素の型を取得するもので, タプル型が与えられた場合は各要素の union type となります. 定義自体は index type を使っています.

type Elem<T extends readonly unknown[]> = T[number];

これらを使って辞書の型を定義してみます.

type Dict<P extends string, T extends Entries<P>> = {
  readonly [K in Key<P, T>]: Select<P, Elem<T>, K>
};
type Key<P extends string, T extends Entries<P>> = Elem<T>[P];
type Select<P extends string, E, K> =
  E extends { readonly [P0 in P]: K } ? E : never;

はい.

順を追って見ていきましょう. まず Key<P, T> は T に含まれるキーの union type を表します. 具体的には Key<"id", typeof entries> = "a" | "b" | "c" となります.

次に Select<P, E, K> は entries の要素の union type E からキー K を持つものだけを選び出します. この定義は conditional type を使っています.

具体的にどうなるかを P = "id", E = Elem<typeof entries>, K = "a" の場合に見てみましょう. まず E は以下のような union type であることに注意します.

E = { readonly id: "a", readonly name: "Foo" }
  | { readonly id: "b", readonly name: "Bar" }
  | { readonly id: "c", readonly name: "Baz" }

すると conditional type は union type に対して分配されるため, 結果は以下のようになり, 無事 id: "a" となるもののみが選び出されます.

Select<P, E, K>
  = (
      { readonly id: "a", readonly name: "Foo" } extends { readonly id: "a" }
        ? { readonly id: "a", readonly name: "Foo" } : never
    ) | (
      { readonly id: "b", readonly name: "Bar" } extends { readonly id: "a" }
        ? { readonly id: "b", readonly name: "Bar" } : never
    ) | (
      { readonly id: "c", readonly name: "Baz" } extends { readonly id: "a" }
        ? { readonly id: "c", readonly name: "Baz" } : never
    )
  = { readonly id: "a", readonly name: "Foo" } | never | never
  = { readonly id: "a", readonly name: "Foo" }

さて辞書の型 Dict<P, T> の定義に戻ると, T に含まれる各キー K に対して, それぞれ Select<P, Elem<T>, K> を割り当てる mapped type となっています.

type Dict<P extends string, T extends Entries<P>> = {
  readonly [K in Key<P, T>]: Select<P, Elem<T>, K>
};

実際 P = "id", T = typeof entries の場合を見てみると, 以下のように期待した辞書型が得られることがわかります.

Dict<P, T> = {
  "a": { readonly id: "a", readonly name: "Foo" },
  "b": { readonly id: "b", readonly name: "Bar" },
  "c": { readonly id: "c", readonly name: "Baz" },
}

あとは makeDict に適切に型をつければ完成です.

function makeDict<P extends string, T extends Entries<P>>(
  prop: P, entries: T,
): Dict<P, T> {
  const dict: any = {};
  for (const entry of entries) {
    dict[entry[prop]] = entry;
  }
  return dict;
}

any はここでは仕方なく使っていますが, 関数の内部に閉じ込めてあるため makeDict のユーザー側から見れば安全です6.

使い方は as const 以外は特に変わらず以下の通り.

const entries = [
  { id: "a", name: "Foo" },
  { id: "b", name: "Bar" },
  { id: "c", name: "Baz" },
] as const;

const dict = makeDict("id", entries);
const dict2 = makeDict("key", entries); // type error

const a = dict.a;
// a: { readonly id: "a", readonly name: "Foo" } = { id: "a", name: "Foo" }
const x = dict.x; // type error

レベル 3 のコード全体はこちら.

レベル 4

まだまだ続きます. ところで entries 内のの id に重複があった場合はどうなるかというと,

const entries = [
  { id: "a", name: "Foo" },
  { id: "b", name: "Bar" },
  { id: "c", name: "Baz" },
  { id: "a", name: "Qux" },
] as const;

const dict = makeDict("id", entries);

const a = dict.a;
// a: { readonly id: "a", readonly name: "Foo" }
//  | { readonly id: "a", readonly name: "Qux" }
//  = { id: "a", name: "Qux" }

となり, 型は間違ってはいないのですが曖昧になってしまいます. というわけでレベル 4 では id の重複を型レベルで検知してみましょう.

まずは一般的なテクニックの紹介です. 以下の ElimUnion<U> は U が union type であった場合は never, そうでなければ U となる型です.

type ElimUnion<U> = ElimUnionSub<U, U>;
type ElimUnionSub<U, V> =
  U extends V ? ([V] extends [U] ? U : never) : never;

具体的に見てみると以下のとおり, 期待したものになっていることがわかります.

ElimUnion<"x">
  = "x" extends "x" ? (["x"] extends ["x"] ? "x" : never) : never
  = ["x"] extends ["x"] ? "x" : never
  = "x"

ElimUnion<"x" | "y">
  = ("x" extends "x" | "y" ? (["x" | "y"] extends ["x"] ? "x" : never) : never)
    | ("y" extends "x" | "y" ? (["x" | "y"] extends ["y"] ? "y" : never) : never)
  = (["x" | "y"] extends ["x"] ? "x" : never)
    | (["x" | "y"] extends ["y"] ? "y" : never)
  = never | never
  = never

既に見た conditional type の union type に対する分配を U に対して使いつつ, V に対しては [V] extends [U] のようにタプル型で包むことで分配を防いでいるところがポイントです.

これを使うと以下のような型が定義できます.

type ElimDuplicateKeyedEntries<P extends string, T extends Entries<P>> =
  ElimDuplicateKeyedEntriesSub<P, Elem<T>, Key<P, T>>;
type ElimDuplicateKeyedEntriesSub<P extends string, E, K> =
  K extends unknown ? ElimUnion<Select<P, E, K>> : never;

ElimDuplicateKeyedEntries<P, T> は T の要素の union type からキーの重複があるものを取り除く型なのですが, やはり何なのかわかりづらいので P = "id", T = typeof entries (重複がある場合) の場合の具体例を見てみましょう.

ElimDuplicateKeyedEntries<P, T>
  = ElimDuplicateKeyedEntriesSub<"id", Elem<typeof entries>, "a" | "b" | "c">
  = ("a" extends unknown ? ElimUnion<Select<"id", Elem<typeof entries>, "a"> : never)
    | ("b" extends unknown ? ElimUnion<Select<"id", Elem<typeof entries>, "b"> : never)
    | ("c" extends unknown ? ElimUnion<Select<"id", Elem<typeof entries>, "c"> : never)
  = ElimUnion<Select<"id", Elem<typeof entries>, "a">
    | ElimUnion<Select<"id", Elem<typeof entries>, "b">
    | ElimUnion<Select<"id", Elem<typeof entries>, "c">
  = ElimUnion<{ readonly id: "a", readonly name: "Foo" } | { readonly id: "a", readonly name: "Qux" }>
    | ElimUnion<{ readonly id: "b", readonly name: "Bar" }>
    | ElimUnion<{ readonly id: "c", readonly name: "Baz" }>
  = never
    | { readonly id: "b", readonly name: "Bar" }
    | { readonly id: "c", readonly name: "Baz" }
  = { readonly id: "b", readonly name: "Bar" }
    | { readonly id: "c", readonly name: "Baz" }

というわけで本当に id が重複している要素が消えることが確認できました. ちなみに ElimDuplicateKeyedEntriesSub<P, E, K> では conditional type を union type の各要素に対するマッピングをするためだけに使っていて, K extends unknown の条件は常に成り立つようになっています (unknown は TypeScript における Top 型).

さて, これを使って id に重複がないことを検証してみましょう. 大まかな方針としては ElimDuplicateKeyedEntries<"id", Elem<typeof entries>> が, id に重複がなければ Elem<typeof entries> そのもの, 重複があれば上で見たように異なる型となることを利用します.

その前にひとつだけ便利な型を定義します.

type TupleWithIndex<T extends readonly unknown[]> = {
  [I in keyof T]: T[I] & { __index: I }
};

これはタプル型に対する mapped type で, TupleWithIndex<["x", "y"]> = ["x" & { __index: 0}, "y" & { __index: 1 }] のようになります. なぜこれが必要かというと, entries 内に id 以外もまったく同一の要素が出現した場合に, それらを互いにを区別するためにインデックスを使いたいからですね.

というわけで entries の id に重複がないことの表明は以下のように書けます.

type EntriesAreUniquelyKeyed<P extends string, T extends Entries<P>> =
  Elem<TupleWithIndex<T>> extends ElimDuplicateKeyedEntries<P, TupleWithIndex<T>> ? true : false;

type Assert<T extends true> = T;
type AssertEntriesAreUniquelyKeyed = Assert<EntriesAreUniquelyKeyed<"id", typeof entries>>;

EntriesAreUniquelyKeyed<P, T> は T 内に重複がなければ true 型, 重複があれば false 型となります7. Assert<T> は型引数 T が true であることを要求するため, ここに false などが入った場合は型エラーとなります. これらを使うことで, 型レベル で id に重複がないことの表明 AssertEntriesAreUniquelyKeyed を書くことができました.

レベル 4 のコード全体はこちら.

レベル 5

ところでレベル 4 は entries 内の id に重複がないということについて, makeDict とは独立に表明を書いたのみでした. レベル 5 ではこの制約を makeDict に組み込んでみましょう.

いきなりですが次のような型を定義します.

type UniquelyKeyedEntries<P extends string, T extends Entries<P>> = {
  [I in keyof T]:
    T[I] extends Omit<ElimDuplicateKeyedEntries<P, TupleWithIndex<T>>, "__index">
      ? T[I] : never
};

これは T 内に重複したキーがなければ T そのもの, 重複したキーがあればそれらに対応する要素を never に変えてしまいます. これが実際そのようになっているのかを確認するのは読者への宿題とします8. Omit<T, K> は TypeScript の標準ライブラリに入っているユーティリティ型の一つです.

ついでにずっと期待していただけで保証はしていなかった, prop の型 P が文字列リテラル型であるということの保証も入れてしまいましょう.

type SingletonString<T extends string> = string extends T ? never : ElimUnion<T>;

これは T が文字列リテラル型であれば T そのもの, そうでないもの (string 型や文字列リテラル型の union type) については never にしてしまいます.

これらを使って引数に対する保証を加えた makeDict は次のようになります.

function makeDict<P extends string, T extends Entries<P>>(
  prop: SingletonString<P>, entries: UniquelyKeyedEntries<P, T>,
): Dict<P, T> {
  const dict: any = {};
  for (const entry of entries) {
    dict[entry[prop]] = entry;
  }
  return dict;
}

使い方はこれまでと変わりません.

const entries = [
  { id: "a", name: "Foo" },
  { id: "b", name: "Bar" },
  { id: "c", name: "Baz" },
  // { id: "a", xxx: "Foo" }, // type error if exists
] as const;

const dict = makeDict("id", entries);
const dict2 = makeDict("id" as string, entries); // type error

ここで makeDict の型引数は P = "id", T = typeof entries と (期待通りかつ予想外に) 推論されています9. 引数が保証を満たさない場合はパラメータの型 (の一部) が never となり, 当然それを満たす値を与えることはできないため型エラーとなります.

レベル 5 のコード全体はこちら. お疲れさまでした.

(実は型パラメータを明示的に渡せばレベル 5 の保証は壊せるのですが, きっとそんなことはしないでしょう...)

あとがき

こんなコードが出てきたらどうしますか? 私だったらレベル 4 以上はふつうにテスト書いた方が良くないですかって言います.

参考文献

  1. entry[prop] に "__proto__" が入ってくるとちょっと微妙ですが本題と関係ないので見て見ぬ振りをしてください.↩

  2. JavaScript のコード自体は別に配列でなくても iterable なら動くのですが, ここでは入力は配列ということにしておいてください.↩

  3. prop は Symbol でも良いのですが, 議論が煩雑になるだけなので割愛.↩

  4. ここでは期待しているだけで特に保証はしていないことに注意.↩

  5. 一応レベル 2 を弁護しておくと, これ自体は配列の境界外アクセスと似たようなもので, 利用側が気をつけて利用するという条件のもとではまったく正しいです.↩

  6. とはいえ関数内部のロジックが間違っていては元も子もないので, 私はこういうとき心の中で はいバリア〜 と宣言して, 型のかわりにテストを書いて正しさを保証したりします.↩

  7. 注意点として, ドキュメントにある通り, conditional type の union type に対する分配は extends の左側が型変数であった場合のみに起こるため, ここではその条件に合わず分配は起こりません.↩

  8. 言いたかっただけ.↩

  9. どうやらパラメータの型と実際に与えられた引数の型を突き合わせてヒントを集め, それらを元に型引数を推論し, さらにそれを元に具体化したパラメータの型と引数の型が合っているかを検証する, という感じになっているようです. なんかすごいけど壊れそうで怖いですね.↩