Read OSS
microsoft/Typescript

型チェッカー：54,000行の型理論、実装の全貌

•上級

前提知識

  • ›第1〜3回：アーキテクチャ、AST、Binder
  • ›型理論の基礎知識（サブタイピング、変性、型推論）
  • ›TypeScript の高度な型機能への理解（ジェネリクス、条件型、マップ型、テンプレートリテラル型）

型チェッカー：54,000行の型理論、実装の全貌

TypeScript がその名に恥じない仕事をするのは、型チェッカーの中です。約54,400行からなる src/compiler/checker.ts は、あらゆるオープンソースプロジェクトの中でも最大級の単一ファイルのひとつです。ジェネリクス、条件型、マップ型、テンプレートリテラル型、制御フロー narrowing、そして数十に及ぶ特殊ケースのルールを備えた構造的型システムを実装しており、型の計算を必要になるまで遅延させ、積極的にキャッシュするオンデマンドアーキテクチャによって動作します。

本稿では、チェッカーの全体像を俯瞰します。初期化の流れ、扱う Type 階層、代入可能性と型推論のコアアルゴリズム、Binder のフローグラフを消費する narrowing の仕組み、そしてすべてをまとめる Program オーケストレーターについて解説します。

createTypeChecker とオンデマンドアーキテクチャ

createTypeChecker(host) はファクトリ関数です。スキャナー、パーサー、Binder と同様に、数百の var ローカル変数をクロージャとして持ちます。

export function createTypeChecker(host: TypeCheckerHost): TypeChecker {
    // Why var? It avoids TDZ checks in the runtime which can be costly.
    var cancellationToken: CancellationToken | undefined;
    var scanner: Scanner | undefined;
    var Symbol = objectAllocator.getSymbolConstructor();
    var Type = objectAllocator.getTypeConstructor();
    var Signature = objectAllocator.getSignatureConstructor();
    var typeCount = 0;
    var symbolCount = 0;
    var totalInstantiationCount = 0;
    // ... hundreds more ...

チェッカーは host からコンパイラオプションを読み取り、頻繁に参照されるフラグ（strictNullChecks、strictFunctionTypes、noImplicitAny など）をローカル変数にあらかじめ展開しておくことで高速アクセスを実現します。次に、名前解決器、二項式チェッカー、ノードビルダーなどの内部インフラを構築し、グローバルシンボルテーブルを初期化します。

sequenceDiagram
    participant P as Program
    participant TC as TypeChecker
    participant S as Symbol
    participant SL as SymbolLinks

    P->>TC: createTypeChecker(host)
    Note over TC: Initialize 500+ var locals
    P->>TC: getSemanticDiagnostics(sourceFile)
    TC->>TC: checkSourceFile(sourceFile)
    TC->>TC: checkExpression(node)
    TC->>S: getSymbolOfNode(node)
    TC->>SL: getSymbolLinks(symbol)
    alt type not cached
        TC->>TC: getTypeOfSymbol(symbol) → resolve type
        TC->>SL: links.type = resolvedType
    end
    TC-->>P: Diagnostic[]

オンデマンドという点が肝心です。チェッカーはプログラム内のすべてのシンボルの型を起動時に計算するわけではありません。型の解決は必要になったときだけ行われます。式のチェック時、診断情報が型を必要とするとき、あるいは言語サービスが補完候補の型を問い合わせるときです。解決結果は SymbolLinks にキャッシュされるため、同じシンボルへの2回目以降のクエリは即座に返ります。

この遅延評価は実用上も重要な意味を持ちます。ファイルの1行を変更しても、プログラム全体を再チェックする必要はありません。Program はファイルの変更時にキャッシュされたチェッカーを破棄して新しいものを生成しますが、新しいチェッカーは実際に必要な型だけを計算すれば済みます。

ヒント： チェッカーをデバッグするなら、ほとんどの型解決のエントリーポイントは getTypeOfSymbol() です。ここにブレークポイントを置くと、型がオンデマンドで計算される様子を観察できます。式の型チェックを追うなら checkExpression() から始めましょう。

Type 階層

Type インターフェースが基底となり、TypeFlags によって分類されます。

classDiagram
    class Type {
        +flags: TypeFlags
        +id: TypeId
        +symbol: Symbol
    }
    class IntrinsicType {
        +intrinsicName: string
        +objectFlags: ObjectFlags
    }
    class LiteralType {
        +value: string | number | PseudoBigInt
    }
    class ObjectType {
        +objectFlags: ObjectFlags
    }
    class UnionType {
        +types: Type[]
    }
    class IntersectionType {
        +types: Type[]
    }
    class TypeParameter {
        +constraint: Type
        +default: Type
    }
    class ConditionalType {
        +checkType: Type
        +extendsType: Type
        +trueType: Type
        +falseType: Type
    }
    Type <|-- IntrinsicType
    Type <|-- LiteralType
    Type <|-- ObjectType
    Type <|-- UnionType
    Type <|-- IntersectionType
    Type <|-- TypeParameter
    Type <|-- ConditionalType
    LiteralType <|-- StringLiteralType
    LiteralType <|-- NumberLiteralType
    LiteralType <|-- BigIntLiteralType

TypeFlags 列挙型の並び順には意図があります。ソースのコメントにも説明がある通り、この順序が union 型における構成要素の配置を決定します。union の処理は早期に打ち切られることが多いため、型はシンプルなものから複雑なものへと並べられています。プリミティブが先頭に来て、IndexedAccess や Conditional のような再帰的な型は末尾に置かれます。

主な型カテゴリは以下の通りです。

  • 組み込み型 (Intrinsic types)：string、number、boolean、void、undefined、null、never、any、unknown — 構造的な内容を持たないシングルトン
  • リテラル型 (Literal types)："hello"、42、true — 特定の値を持つ型
  • オブジェクト型 (Object types)：クラス、インターフェース、匿名オブジェクト型、マップ型、タプル — ObjectFlags（Class、Interface、Reference、Tuple、Anonymous、Mapped など）でさらに細分化される
  • Union / Intersection 型：T | U と T & U — 構成要素の型を配列で保持
  • 型パラメーター (Type parameters)：オプションの constraint と default を持つジェネリックな T
  • 条件型 (Conditional types)：T extends U ? X : Y — 未解決の型パラメーターがある場合は解決を遅延
  • テンプレートリテラル型 (Template literal types)：`hello${T}` — リテラル文字列と型プレースホルダーを組み合わせた型
  • インデックスアクセス型 (Indexed access types)：T[K] — T と K に基づいて遅延解決される
  • 代入型 (Substitution types)：インスタンス化された型パラメーターのための内部的な管理用型

型推論と代入可能性

代入可能性：構造的互換性

TypeScript は構造的型付けを採用しています。少なくとも同じプロパティとシグネチャを持っていれば互換性があると見なされます。その中核を担うのが isTypeAssignableTo(source, target) で、この関数は特定の関係（代入可能性、比較可能性、またはサブタイプ）を持つ isTypeRelatedTo() へと処理を流します。

flowchart TD
    Start["isTypeAssignableTo(source, target)"] --> Identity{"Same type?"}
    Identity -->|Yes| OK["✓ Compatible"]
    Identity -->|No| Special{"Special cases?<br/>any, never, unions"}
    Special -->|"source = any"| OK
    Special -->|"source = never"| OK
    Special -->|"target = any"| OK
    Special -->|"source = union"| EachSource["Each constituent<br/>must be assignable"]
    Special -->|"target = union"| SomeTarget["At least one target<br/>constituent matches"]
    Special -->|No special case| Structural["Structural comparison:<br/>Check each target property<br/>Check call signatures<br/>Check index signatures"]
    Structural --> ExcessCheck{"Excess property<br/>check?"}
    ExcessCheck -->|"Fresh object literal"| Excess["Check no extra<br/>properties"]
    ExcessCheck -->|No| Done["Return result"]

このアルゴリズムは非常に多くのエッジケースに対応しています。

  • Union と Intersection：source が union の場合はすべての構成要素が代入可能である必要があり、target が union の場合はいずれかの構成要素が一致すれば十分です。
  • ジェネリック型：インスタンス化されたジェネリックは、型引数を適切な変性（読み取り位置では共変、書き込み位置では反変）で比較します。
  • 超過プロパティチェック：新鮮なオブジェクトリテラルにはより厳格なチェックが適用されます。対象の型に存在しないプロパティはエラーになります。
  • 判別 union：union を target とする場合、チェッカーは判別プロパティを使って、どの構成要素に対してチェックするかを絞り込むことができます。

ジェネリクスの型推論

型引数を明示せずにジェネリック関数を呼び出すと、チェッカーが型引数を推論します。チェッカーは各型パラメーターに対して*推論候補 (inference candidate)を持つ推論コンテキスト (inference context)*を生成し、引数の型をパラメーターの型に照らし合わせながら、型パラメーターが現れる各位置で候補を収集します。

たとえば function map<T, U>(arr: T[], fn: (x: T) => U): U[] を map([1, 2], x => x.toString()) と呼び出した場合を考えます。チェッカーは配列の引数から T = number を、コールバックの戻り値から U = string を推論します。推論は優先度順に進み、引数からの直接マッピングが戻り値型からの間接推論よりも優先されます。

チェッカーにおける制御フロー Narrowing

第3回で見たように、Binder はプログラムの制御フローをモデル化した FlowNode グラフを構築します。チェッカーはこのグラフを getFlowTypeOfReference() で消費します。この関数は、コード中の特定の地点における変数の narrowed な型を計算します。

flowchart BT
    Use["Reference to x"] --> FA["FlowAssignment<br/>x = getValue()"]
    FA --> FC["FlowCondition<br/>(TrueCondition)<br/>x !== null"]
    FC --> FL["FlowLabel<br/>(merge point)"]
    FL --> Start["FlowStart"]
    
    style Use fill:#f9f,stroke:#333
    style FC fill:#bbf,stroke:#333

アルゴリズムは参照のフローノードから逆向きに辿っていきます。

  1. FlowAssignment：代入された型が x の新しい型になります。
  2. FlowCondition (TrueCondition)：型ガードを適用します。x !== null は null を除外し、typeof x === "string" は string に絞り込み、x instanceof Foo は Foo に narrowing します。
  3. FlowCondition (FalseCondition)：ガードの逆を適用します。
  4. FlowLabel (BranchLabel)：各先行ノードで narrowed な型を計算し、すべての結果のunionを取ります。
  5. FlowLabel (LoopLabel)：同様ですが、ループを処理するために不動点まで反復します。
  6. FlowCall：アサーション関数（asserts x is T）に対して、対応する narrowing を行います。

重要なパフォーマンス最適化として、各 FlowNode はキャッシュキーとして使われる id を持ちます。チェッカーは (flowNodeId, referenceSymbolId) をキーとするフロー型キャッシュを管理しており、これがなければ多くの分岐を持つ関数での narrowing は指数関数的なコストになりかねません。

ヒント： narrowing の挙動が期待通りでない場合、まずフローグラフを確認しましょう。node.flowNode（FlowContainer ノード上）と先行ノードのチェーンを辿ると、チェッカーが何を見ているかが分かります。

Program オーケストレーター

Program はすべてをまとめるトップレベルのオブジェクトです。createProgram() はルートファイル名とコンパイラオプションを受け取り、以下を行います。

  1. ファイルの解決：ルートファイルを起点にモジュール解決で推移的なインポートを辿り、SourceFile オブジェクトの完全なセットを構築します。
  2. チェッカーの管理：チェッカーは最初に getSemanticDiagnostics や getTypeChecker が呼ばれるまで遅延生成され、キャッシュされます。
  3. emit の提供：program.emit() が emitter パイプラインを起動します。
  4. 診断情報の報告：オプションの診断、構文の診断（パーサー由来）、意味論的な診断（チェッカー由来）、および宣言ファイルの診断（宣言 emit 由来）を提供します。

Program インターフェースが公開するものは以下の通りです。

export interface Program extends ScriptReferenceHost {
    getRootFileNames(): readonly string[];
    getSourceFiles(): readonly SourceFile[];
    emit(...): EmitResult;
    getOptionsDiagnostics(): readonly Diagnostic[];
    getSyntacticDiagnostics(sourceFile?): readonly DiagnosticWithLocation[];
    getSemanticDiagnostics(sourceFile?): readonly Diagnostic[];
    getTypeChecker(): TypeChecker;
    // ...
}

src/compiler/types.ts#L7403 にある CompilerOptions インターフェースはすべてのコンパイラフラグを定義しています。これらの多くがチェッカーの挙動に直接影響します。strictNullChecks は null と undefined を独立した型として扱うかどうかを制御します。strictFunctionTypes は関数パラメーターの変性を制御し、exactOptionalPropertyTypes はオプションプロパティに undefined を含めるかどうかを制御します。

Program はモジュール解決という重要なタスクも担います。import の指定子を受け取り、設定された解決戦略（Node.js、classic、bundler）を使ってファイルパスへと解決します。解決済みモジュールはファイルごとに resolvedModules マップにキャッシュされ、増分ビルドのパフォーマンス向上のために Program インスタンスをまたいでキャッシュを再利用することもできます。

expressionToTypeNode ブリッジ

チェッカーと emitter の境界には、興味深いインフラが存在します。src/compiler/expressionToTypeNode.ts は、内部の Type オブジェクトを AST の TypeNode 構文へと変換するモジュールです。チェッカーが通常行う処理の逆方向です。これは宣言ファイルの生成（第5回）において不可欠な役割を果たします。ソースコードに明示的なアノテーションがない推論された型を、.d.ts 出力の型構文として具体化する必要があるためです。

次回予告

チェッカーが型、診断情報、解決済みの型情報を生成できるようになったところで、コンパイラはいよいよ出力を生成する準備が整いました。第5回では emitter パイプラインを追います。AST から AST へと変換する一連のトランスフォーマーが TypeScript 構文を JavaScript へと段階的に変換していく仕組み、宣言ファイルの生成方法、そしてソースマップが入力と出力のつながりをどのように維持するかを解説します。