TypeScriptのコンパイラを見てtype-challengesのEqual<X, Y>を完全に理解する

TL;DR

type-challenges　にはEqual<X,Y> 型が用意されており、X と Y の等価判定を行う。

export type Equal<X, Y> =
  (<T>() => T extends X ? 1 : 2) extends
  (<T>() => T extends Y ? 1 : 2) ? true : false

なぜこの定義で等価判定ができるかの説明をする。
理解しやすいように、以下のような等価な変換を行う。

export type Equal<X, Y> =
  (<T>() => (T extends X ? 1 : 2)) extends
  (<U>() => (U extends Y ? 1 : 2)) ? true : false

最終的に T extends X ? 1 : 2 が U extends Y ? 1 : 2 の subtype かが判定されるのだが、Conditional Types 同士の比較は以下のように定義されている。

// Two conditional types 'T1 extends U1 ? X1 : Y1' and 'T2 extends U2 ? X2 : Y2' are related if
// one of T1 and T2 is related to the other, U1 and U2 are identical types, X1 is related to X2,
// and Y1 is related to Y2.

この U1 and U2 are identical types （=U1とU2が一致する）という定義が重要で、このU1とU2にそれぞれ等価判定をしたいXとYを代入して、かつ他の条件を必ず満たすようにすれば、型の等価判定が実現できる。

ではなぜ<T>() => (T extends X ? 1 : 2)のような定義になってるかというと、これは「遅延評価のため」と述べられている。
Equal<X,Y> の実装に必要なのは Conditional Types 同士の比較なのだが、通常 Conditional Types は簡約されるため、Conditional Types 同士の比較になることは少ない。
T extends X ? 1 : 2 の評価をする際、Tは必ず未定である（この定義ではどの段階においてもTが具体的に決まることはない）。コンパイラは Conditional Types (T1 extends U1 ? X1 : Y1) のうち T1 が型パラメータ単体だった場合は必ず遅延評価する。この処理は Distributive Conditional Types のために存在する。

<T>() => ~~~ の表記について説明する。
<T>(x: T) => T 型には、どのようなTを持ってきても代入可能である値しか代入できない。
すなわち、<T>() => (T extends X ? 1 : 2) が <U>() => (U extends Y ? 1 : 2) の subtype であるかどうかは、任意のUを1つ選んだ際に、あるTが存在し、() => (T extends X ? 1 : 2) が () => (U extends Y ? 1 : 2) の subtype とできるかを判定すればよい。

背景

type-challenges という TypeScript の型の問題集がある。
この問題を解いていると、型の実装に「型の等価判定」が欲しくなり、実装方法が分からなかったため type-challenges に用意されていた型である Equal<X,Y> を用いた。

export type Equal<X, Y> =
  (<T>() => T extends X ? 1 : 2) extends
  (<T>() => T extends Y ? 1 : 2) ? true : false

しかし　Equal<X,Y>　の仕組みも分からず実装するのも気味が悪いので調べたところ、以下のような記事を見つけた。

https://zenn.dev/razokulover/articles/890102685d5ea2

見るところによると、どうも TypeScript のリポジトリの issue 内で Equal<X,Y>　の議論があり、その中で挙げられたものらしく、またコンパイラ内部の Conditional Types の比較に用いられる isTypeIdenticalTo によって判定がされるため等価判定ができるようだった。

https://github.com/microsoft/TypeScript/issues/27024

しかし私はこれらを読んだだけではどうも上手く理解に落とし込めなかった。
だが、コンパイラ内部の都合で判定ができていることは分かったので、ともすればコンパイラの中身を見ればよい！ という発想に至った。

そして、TypeScriptのコンパイラを見ることでEqual<X,Y>を完全に理解する旅に出た。

コンパイラの見方

TypeScript のリポジトリの CONTRIBUTING.md の Get Started から環境構築ができる。

Debugging the tests にデバッグ方法が載っている。launch.json としてリポジトリ内のテンプレートを置き、tests/cases/compiler/ 以下にテストケース（今回であれば Equal<X,Y> の定義を載せた .ts ファイル）を置き、 gulp runtests --tests=<テストケースのファイル名> -i を実行すれば、VSCodeを用いたデバッグができる。

今回は checker.ts とビルド先の run.js を見れば十分だが、checker.ts は2万行以上あり、全てを読んで理解するのは難しい。そのためテストケースを用いて型検査をステップごとに追うと理解が早い。

VSCodeの拡張としてGitLensを入れておくと、各行ごとの変更履歴や関連するissueやPRを辿れるため、各実装の背景が追いやすい。

おことわり

以降の項目では、Equal<X,Y>の挙動について解説する。
説明のしやすさのために、以下のように透過な変換をしたものを用いる。
TやUというワードが出た場合、この定義を参照すること。

export type Equal<X, Y> =
  (<T>() => (T extends X ? 1 : 2)) extends
  (<U>() => (U extends Y ? 1 : 2)) ? true : false

Conditional Types の比較

Conditional Types の比較はどこで行っている？

まずはテストケースを動かして、１ステップずつ見るなどする。元記事を参考に structuredTypeRelatedToWorker にブレークポイントを仕込むと、実際に Conditional Types 同士(T extends X ? 1 : 2 と U extends Y ? 1 : 2)の比較をしていることが分かる。
そして、その比較方法についてのコメントがされていることが見られる。

// Two conditional types 'T1 extends U1 ? X1 : Y1' and 'T2 extends U2 ? X2 : Y2' are related if
// one of T1 and T2 is related to the other, U1 and U2 are identical types, X1 is related to X2,
// and Y1 is related to Y2.

すなわち、TとUは一方がもう一方の subtype であればよく、XとYは型が一致していればよく、1が1の subtype であればよく、2が2の subtype であればよい。

実際に Conditional Types として比較する際は、TにはUが代入されており、必ず条件を満たす（これはどうもコンパイラ内のinferTypesでcontext.inferencesに、TにUを代入する旨を追加する操作を行っている様子）。
後ろ2つの条件は当然満たすので、あとはXとYの型が一致していれば T extends X ? 1 : 2はU extends Y ? 1 : 2の subtype であると判定できる。また、XとYの型が一致していなければT extends X ? 1 : 2はU extends Y ? 1 : 2の subtype ではなくなる。

なるほど、本質的にはU1 と U2 の型の一致で判定していて、その一致判定の実装を見てみると、元記事でも言われていたisTypeIdenticalToも使われているようだ。

元となった PR/issue を探す

ところで完全に理解するためには、このような比較になっている文脈も知らなければいけない。
そこで、元となったPR/issueを探すと以下が見つかる。#22860 を #22869 で対応している。

https://github.com/microsoft/TypeScript/issues/22860
https://github.com/microsoft/TypeScript/pull/22869

issue の内容としては、型パラメータを用いた Conditional Types を key に持つ interface の継承の際にエラーが起きるというもの。これは Conditional Types 同士の比較が実装されていなかったことが原因だったため、ここで Conditional Types 同士の比較が定義され、実装されたとのこと。

Conditional Types 同士の比較はなぜこうなっている？

この節は考察であるため、間違いを含む可能性が普通にあります。

さて、Conditional Types 同士の比較が定義されたPR自体を把握し、元となる issue 自体も見つかったが、「なぜ Conditional Types 同士の比較はこの定義になっているか？」は特に記載はない様子だった。
そのため、Conditional Types 同士の比較がこの定義になっている理由について考察しておく。

このような定義となっている理由は、利便性によるものが大きいのではないか？ と推測している。すなわち、Conditional Types のせいで型エラーが起こりにくいようにする定義にして、Conditional Types 同士の比較で困るタイミングを減らしたいように見える。
T extends U ? X : YのTは共変かつ反変の位置にあり、この部分が特に利便性を高めるための定義のように感じられる。

共変かつ反変にすることで利便性を保つ例はあり、似た/同じ思想が用いられているように感じる。

https://qiita.com/na-o-ys/items/aa56d678cdf0de2bdd79

この関数パラメータの例では、共変かつ反変にした影響で型検査は通るもののランタイムエラーが起こることはあるが、Conditional Types の場合は実際に代入できる値は簡約後のXやYである。XやYは共変なので、特にランタイムエラーが起こることはない様子。
interfaceの継承先と継承元でtrue部とfalse部を分けるような定義は可能だが、これも必要であれば型エラーとなる。以下の例では、false型にtrueを入れようとしてエラーとなる。

interface A<T>{
    hoge: T extends string ? true : false
}

interface B<T> extends A<T>{
    hoge: (T & string) extends string ? true : false
}

const a: A<number> = { hoge: false }
const b: B<number> = { hoge: true }
const c: A<number> = b // Types of property 'hoge' are incompatible.

感想としては、type A = (<T>() => [[T]] extends [[string]] ? 1 : 2) extends (<T>() => [T] extends [string] ? 1 : 2) ? true : false は false になるのだが、これがtrueになる定義になってもおかしくはないよなぁ、という気持ちになった。どのようにTを入れても等価になるはずなので。
とはいえこの Conditional Types の比較の定義がもし変わった場合、Equal<X,Y>の別の実装を探さなくてはいけなくなるため、破壊的変更はしないでほしいなぁ。

型パラメータ付きの関数が型に含まれることについて

<T>()=> ~~~ って何者？

ここまでの議論で、conditonal type の比較ができればEqual<X,Y>の実装ができそうなのは分かった。
しかし、<T>()=> ~~~や<U>()=> ~~~がなぜ必要なのか？ そもそも <T>() => (T extends X ? 1 : 2)　という型は何物なのか？ という疑問にあたる。このような型を普段見ることはないため。

この場合もコンパイラの挙動を辿ったり、PR/issueを辿ったりすれば分かるはずなのだが、この程度であればエラーを起こしてエラーメッセージから辿ったほうが早い（ちなみにコンパイラを辿った結果としては、この辺りで実装されている模様、詳しく読んではいないが）。

実際に const hoge: <T>() => T = () => 1 と書いてみると、以下のようにエラーが出るので、エラーメッセージから調べることができる。

Type 'number' is not assignable to type 'T'.
  'T' could be instantiated with an arbitrary type which could be unrelated to 'number'.(2322)
input.tsx(1, 13): The expected type comes from the return type of this signature.

実際にエラーメッセージで調べてみると、いくつかの記載が見つかる。stackoverflowの回答が一番分かりやすいと思う。

https://github.com/microsoft/TypeScript/issues/29397
https://stackoverflow.com/questions/62623637/r-could-be-instantiated-with-an-arbitrary-type-which-could-be-unrelated-to-re

記事を参考にすれば、<T>(x: T) => Tのように型定義内に型パラメータを含んでいる場合、どのようなTを当てはめても成立するような値しか代入することはできなくなるという話だ。
例えば、(x: string) => x.toUpperCase()のような関数は、確かにTがstringなどであればよいが、そのような保証はなく、例えばTにnumberなどstringでない型を入れると成り立たなくなるため代入することはできない。<T>(x: T) => Tには、例えばx => xはTが何であってもよいため代入できる。

ちなみに、<T extends U>(x: T) => Tのように型制約がある場合は、U の subtype であるような任意の T での判定となる。

Equal<X,Y>に用いられる <T>() => ~~~ の解明

<T>(x: T) => Tのように型定義に型パラメータが用いられていた場合についての挙動を導入したので、Equal<X,Y>での判定に戻る。

Equal<X,Y>では、<T>() => (T extends X ? 1 : 2)が<U>() => (U extends Y ? 1 : 2)の subtype か？ を判定していた。
これらはそれぞれ、任意のTで() => (T extends X ? 1 : 2)を満たすかと、任意のUで() => (U extends Y ? 1 : 2)を満たすかといった型を示す。

この subtype の判定については、 subtype とはどういう概念かについて立ち返ると納得しやすい。X が Y の subtype であるということは、任意の Y を満たす値を選んだ時に、あるXを満たす値を選べば、それらの値が一致するようにできることと言い換えられる。
この発想を用いてみると、<T>() => (T extends X ? 1 : 2) が <U>() => (U extends Y ? 1 : 2) の subtype かを判定するには、任意の U を選んで () => (U extends Y ? 1 : 2) を作った時、ある T を選んで () => (T extends X ? 1 : 2) を作り、これが () => (U extends Y ? 1 : 2) の subtype とすることができるかどうかを判定すればよくなる。

遅延評価と言われる所以

ここまで説明したが、Conditional Types 同士の比較をするためには、そもそも T extends X ? 1 : 2 が 1 や 2 に簡約されない理由を説明しなければならない。
普段は型パラメータには具体的な型を指定することが多く、その場合は簡約されることがほとんどである。

簡約されない理由は Distributive Conditional Types の定義によるもので、T extends U ? X : Y の T が型パラメータ単体で存在していた場合、必ず遅延評価をすることになっている。

（10/5 追記: X と Y が一致する場合は、Conditional Types 単体で見ると簡約されないが、Conditional Types 同士の比較という分岐に入る前に評価できてしまうという流れになる。・・・という挙動だったはず）

<T>() => (T extends X ? 1 : 2) となっているように、Tは型パラメータであり、具体的な型が定まっているわけではないため、T extends X ? 1 : 2 は遅延評価がなされる。

まとめ：仕組みの説明

ここまで説明すれば、以下のようにEqual<X,Y>の仕組みを解明できる。

1. まず、<T>() => (T extends X ? 1 : 2) が簡約できるかを判定する
2. () => (T extends X ? 1 : 2) の返り値である T extends X ? 1 : 2 を見ると、T は型パラメータであるから、Distributive Conditional Types の定義に則り遅延評価される
3. <U>() => (U extends Y ? 1 : 2) も同様に遅延評価される
4. 遅延評価の結果、(<T>() => (T extends X ? 1 : 2)) extends (<U>() => (U extends Y ? 1 : 2)) ? true : false の判定に移る
5. () => (T extends X ? 1 : 2) が () => (U extends Y ? 1 : 2) の subtype であるかを判定したい
6. 引数は0個で一致してるため、返り値の T extends X ? 1 : 2 が U extends Y ? 1 : 2 の subtype であるかの判定となる
7. これは Conditional Types 同士の比較であるため、定義をもとに判定する
   1. T と U の一方がもう一方の subtype となるかは、任意のUを選んだ時に、あるTとしてUを選べば、当然 subtype となるためOK
   2. X と Y は型が一致すればOK（Equal<X,Y>の本質）
   3. 1　同士や 2 同士に関しては明らかに subtype なのでOK
8. 7. での比較の結果、「X と Y は型が一致」 と 「Equal<X,Y> が true」　　が同値であることが分かる

今後の課題とか

• 「conditonal type 同士の比較」の正確な理由は不明のまま
• isTypeIdenticalTo でなぜ等価判定が行えるかは調べていない
• この定義以外に Equal<X,Y> の実装ができるのか？
  • isTypeIdenticalTo を用いた別の判定を使えそうですよね
• 「TにUを代入する旨」などと濁しているが、これは挙動を辿った結果として正確な挙動を把握できなかったため。悲しいね
• 「X が Y の subtype であるということは、任意の Y を満たす値を選んだ時に、あるXを満たす値を選べば、それらの値が一致するようにできることと言い換えられる。」←もっと言い方ない？
• もう少し型パラメータあたりでコンパイラの中身の話ができたら面白いかもしれなくて、私は中身を知らない