TypeScriptコンパイラの基本

# TypeScriptコンパイラの基本

🚨 警告：この記事は決してTypeScriptの入門ではないため、型システムなどの説明は一切しない。型システムに興味のある方にぜひ「型理論」や「非変性」を検索していただきたい。

世界屈指の知名度と利用者数を誇るJavaScriptの対になっているTypeScriptをご存知ない方は少ないだろう。それに対し、TypeScriptの基盤となるコンパイラを本気で研究してみる方は（比喩的に）片手でしか数えられないのではないだろうか。
<details></details>
「TypeScriptの型システムだけで手一杯だから、コンパイラとか実装とかに構えるものか！」と文字通り思われる方は一人もいないと思うが、「面白そうだけどこんな大量のコードを分析する時間がない」ならどうだろう？

この記事ではそのような人のためにTSコンパイラの基本を簡単に紹介する。だがまず、個人的にTypeScriptコンパイラ（以下tsc）が面白いと思う理由を挙げよう。

## TypeScriptコンパイラの特徴

### コンパイラだけでなく、トランスコンパイラだ

当たり前ながらTypeScriptはJavaScriptへコンパイルされる。というと、JavaScript言語の規則に従わないとバグは簡単に起こる。次の[バグの例]をご覧にいれよう：

``` rust
  let Infinity = 3;

  enum A {
    X = 1 / 0 // ゼロで割ってしまった、Infinity…よね？
  }

  console.log(A.X) // 3？！
```

コードを見れば、このバグの原因は上の`let Infinity = 3`と何らかの関係があると思われたら正解だ。このコードをJavaScriptにコンパイルすると次のようになる：

``` rust
let Infinity = 3;
let A;
(function (A) {
    A[A["X"] = Infinity] = "X";
})(A || (A = {}));
console.log(A.X);
```

ご覧の通り、enumメンバーを１/0で初期化すると、1/0の結果であるInfinityはそのまま出力される。それを「[定数畳み込み]最適化」と呼び、一般的な局所最適化方法の一つである。普段なら出力される定数は数字なので問題ないが、無限なら文字列が出力され、冒頭に定義されたInfinity変数と錯覚される。

JavaScriptへのコンパイルが故のエラーだと言える。

### TypeScriptの型システム

数行前にTypeScriptの型システムは本記事の範囲に含まれないと宣言したが、やはり例をひとつだけ見ておこう。

``` ts
type MutableStringOnly<Type> = {
  -readonly [Property in keyof Type as `get${Capitalize<string & Property>}`]-?:
    Type[Property] extends string 
        ? Type[Property] 
        : never;
};
```

ほんの数行ながら、TypeScriptが提供してくれる機能の塊になっている。上から：

1. ジェネリック型パラメーターの`<Type>`
2. 読み取り専用のルールを取り消す`-readonly`（`readonly`か`+readonly`だと逆に読み取り専用になる）
3. `Type`型からプロパティを取り出し、`Property`に代入する`Property in keyof Type`
4. `Property`を元にプロパティ名を変更する``as `...` ``
5. 元プロパティ名が文字列である場合のみ、頭文字を大文字にしてから"get"とくっつけるテンプレートリテラル型の`` `get${Capitalize<string & Property>}` ``
6. 省略可能プロパティを取り除く`-?`
7. `Type`の選択中のプロパティ方が文字列かどうか判明する`Type[Property] extends string`
8. 上記の条件が真であれば`Type[Property]`型を返すか
9. 偽であれば「起こらない値の型」を表す`never`が返される（つまり、そのプロパティは無効となる）

この型の用例：

``` ts
type BaseType = {
  a: number;
  b: string;
  c: string;
  d: number;
}

type ResultType = MutableStringOnly<BaseType>;
// type ResultType = {
//     getA: never;
//     getB: string;
//     getC: string;
//     getD: never;
// }
```

要するに、TypeScriptの型システムは奥が深い。

では、tscの流れを解説する前に、コンパイラの"普通"の流れを簡単に復習しておこう。

## コンパイラの普通の流れ

参考資料：近畿大学、「[コンパイラ](https://www.info.kindai.ac.jp/compiler/lecture/Compiler01.pdf)」

1. 字句解析と構文解析
    > 原始コードを読み込み、文法上の間違いがないかチェックする。その後、プログラムの流れを表すASTを出力。
2. 識別子と値の結合、識別子の問題の検査など
    > 変数名・関数名を値とともに保存し、まだ定義されていない識別子などの使用をチェック。
3. 任意：静的型チェック
    > TypeScriptのような静的型付け言語であれば、ここで型の確認を施行。
4. 任意：中間コード生成
    > 主に最適化の準備段階として、プログラムを表すデータ構造を処理しやすい形に変換。
5. 任意：最適化
    > 実行時間か使用メモリ量を最小化。
6. 目的コード生成
    > 目的の機械（CPUかJVMのような仮想マシン）が処理できる形態にコードを変換。

最初と最後のステップはどの言語でも同じですが、言語によって２番から５番の有無・順番が変わるところがある。また、この流れは主にC系言語で用いられるので、Haskellのように違うパラダイムを元にしている言語ならステップが追加されたり削除されたりすることが多い。

もちろん、TypeScriptもC系言語なので、以上と大体同じ流れになるだろう。それを確認するために[tscの開発チームによるメモ集]を見ていただければ結構である。

ただ、その流れを深く理解していきたければ、私とともにmini-TypeScriptを見てみよう。

## mini-TypeScriptとは

[mini-TypeScript]とは名の通り、tscの縮図である。したがって、機能の数といい、アルゴリズムの形といい初心者でも頭で簡単に処理できる実装になっている。
だがそれよりも、貴重な練習問題を用意してくれる。簡潔に表現された実装でも、読むだけではなかなか覚えにくい。そして、内容を覚えたところそれぞれのコンポーネントはどのふうに関わり合っているのか理解したとは限らない。そこで、この記事を読み終えたらぜひそれらの練習問題に取り組んでいただきたい。というと、この記事は主に練習問題を解く気がない人に対して書かれたものだと考えていただいて差し支えない。

## mini-TypeScriptコンパイラ：実行の流れ

では、mini-TypeScriptという素晴らしい教材を解説する。早速だが、mini-TypeScriptの中心となる関数はこちら：

``` ts
function compile(s: string): [Module, Error[], string] {
    const tree = parse(lex(s))
    bind(tree)
    check(tree)
    const js = emit(transform(tree.statements))
    return [tree, Array.from(errors.values()), js]
}
```

以上の流れを説明しよう。

### 字句解析

まず、ソースファイルの中身を`lex`（[字句解析器]）に読み込ませる。

`lex`は以下ののようになる：

``` ts
function lex(s: string): Lexer {
    let pos = 0
    let text = ""
    let token = Token.BOF
    return {
        scan,
        token: () => token,  // 今見ているトークン
        pos: () => pos,      // 元の文字列における位置
        text: () => text,    // トークンに該当する文字列、Token.Commaなら','
    }
...
```

よく見ると、即座に`Lexer`を返すので、実は次の段階（構文解析）で呼び出されるまで何もしない。

では、`lex`の動作の核である`scan`関数の中身だが、多少長いので普通の言葉で解説する：

1. 冒頭のスペースやタブをスキップ
1. ファイルの終わりだったらEOFトークンを返す
1. ファイルの終わりでなければ、文字の種類に応じて適切なトークンを返す


**トークン**というのは、識別子・数字・括弧文字など言語の文法からして重要なものの通称である。

トークン化の利点は、タブや五つのスペースなどの雑音になる部分を全て排除できることだ。
あとはレクサーだが、トークン化のステップから得られたトークンの連なりの操作を行うインターフェースのようなものだ。

``` ts
{
    scan,               // 次のトークンへ行く
    token: () => token, // 今見ているトークン
    pos: () => pos,     // 元の文字列における位置
    text: () => text,   // トークンに該当する文字列、Token.Commaなら','
}
```

このレクサーをもって、ようやく本番に移る：構文の解析。

### 構文解析

`parse`関数はまず文ごとに解析していく。

``` ts
const statements = parseSeparated(parseStatement, () => tryParseToken(Token.Semicolon))
```

そして解析した文をモジュールとして返す。

``` ts
function parseModule(): Module {
    ...
    // locals: ローカル変数、次のステップに出場する
    return { statements, locals: new Map() } 
}
```

解析される内容に従って違う解析関数が使用される：

- `parseStatement`: 変数・型・関数の代入などを解析する
- `parseExpression`: 数式や文字列、変数に代入できるもの
- `parseIdentifier`: 変数名、型名とその他の識別子
- などなど

この時点では、文法エラーが全て検出されている。

``` ts
let hoge = ;         // エラー
let hoge: string = 3 // （まだ）問題ない
```

文法を確認した上でプログラムを表すASTを出力する。

### 識別子と値の結合

次に`bind`はASTを読み取り、変数・関数などの宣言か定義を見つけたら、代入先となる識別子と代入される値を繋ぐ（バインド）。

``` ts
// parser.ts
const module: Module = { 
    statements: [], 
    locals: new Map()
}

// bind.ts
export function bind(m: Module) {
    for (const statement of module.statements) {
        // localsはローカル変数を指す
        bindStatement(module, module.locals, statement) 
    }
...
```

ご覧の通り、モジュールの文をそれぞれ読み込み、変数などを保管するために用意された`module.locals`を渡す。
こちらは`bindStatement`：

``` ts
function bindStatement(locals: Table, statement: Statement) {
        // 結合できる文のみ
        if (statement.kind === Node.Var || statement.kind === Node.TypeAlias) {
            // テーブルから同じ識別子を使うシンボル（宣言・定義を保管するオブジェクト）を取り出す
            const symbol = locals.get(statement.name.text)
            if (symbol) {
                // すでに宣言されたか確認する
                const other = symbol.declarations.find(d => d.kind === statement.kind)
                if (other) {
                    // 重複宣言を検出
                    error(statement.pos, `Cannot redeclare ${statement.name.text}; first declared at ${other.pos}`)
                }
                else {
                    //　宣言・定義を識別子に結合
                    symbol.declarations.push(statement)
                    if (statement.kind === Node.Var) {
                        // 変数である場合、メインの宣言として保存
                        // 宣言の型を確認したら便利になる
                        symbol.valueDeclaration = statement
                    }
                }
            }
            else {
                // 初めて見た識別子なので、テーブルに記録
                locals.set(statement.name.text, {
                    declarations: [statement], 
                    // 
                    valueDeclaration: statement.kind === Node.Var ? statement : undefined
                })
            }
        }
    }
```

この段階で重複宣言などの問題が報告される。

``` ts
let hoge = ;         // 依然としてパーサーエラー
let hoge: string = 3 // エラー：重複宣言
```

次は、それぞれの識別子の方を確かめる番だ。

### 静的型チェック

次に`check`がそれぞれの識別子とともに型アノテーション（`...: type =`のこと）が来たか確認し、あった場合はその型が値のと同じか判明する。

``` ts
function checkStatement(statement: Statement): Type {
    switch (statement.kind) {
        case Node.Var:
            // 初期化値の型を判明
            const i = checkExpression(statement.init)
            // 識別子のそばに型アノテーションがなければ、初期化値の型を返す
            if (!statement.typename) {
                return i
            }
            // アノテーションがあれば、初期化値の型と一致しているかどうか確認する
            const t = checkType(statement.typename)
            // 一致していないければ、エラー
            if (t !== i && t !== errorType)
                error(statement.init.pos, `Cannot assign initialiser of type '${typeToString(i)}' to variable with declared type '${typeToString(t)}'.`)
            return t
        case Node.TypeAlias:
            // 型宣言の型確認は比較的に簡単
            return checkType(statement.typename)
    }
}
```

この時点でお馴染みの型エラーは全て記録された。あとはコードとともに出力するだけ。

### コード生成

コード生成まできたが問題はまだ一つ残っている：型宣言など、JavaScriptに存在しない構文と生成したいコードが入り混じっていることだ。
そこで、トランスフォーマーを使う：

``` ts
// transform.ts
function transformStatement(statement: Statement): Statement[] {
        switch (statement.kind) {
            case Node.ExpressionStatement:
                // 式なら問題ないのでそのまま渡す
                return [statement]
            case Node.Var:
                // 型アノテーションを削除
                return [{ ...statement, typename: undefined }]
            case Node.TypeAlias:
                // 型宣言を削除
                return []
        }
    }
```

型情報を削除すれば次は出力のフォーマットなどを考える：

``` ts
function emitStatement(statement: Statement): string {
    switch (statement.kind) {
        case Node.Var:
            return `var ${statement.name.text} = ${emitExpression(statement.init)}`
        case Node.TypeAlias:
            // Node.TypeAliasはstatement.kindの一つなので、やむをえずこの行を追加する
            // だがトランスフォーマーの方で型宣言を削除したからこのswitchケースが絶対に選択されない
            return `type ${statement.name.text} = ${statement.typename.text}`
    }
}
```

以上で、TypeScriptコードを確認してからJavaScriptに変換することができた。

## 最後の一言

これで読者さんにTypeScriptコンパイラの大まかな流れをご理解いただけただければと思う。上述した通り、[mini-TypeScript]を隅から隅まで理解するには練習問題を通じ、自分でその流れを築いていくしかないと考える。

また、上記の流れとtscのに大きな違いがない（tscの[開発チームによるメモ集]を見る限り）と言いつつも、やはりこれだけの機能を収めているtscでは単純なことでさえ複雑に見えるところがある。

tscをより深く理解していきたい方のためにいくつかの参考資料を取り上げよう（英語のみ）：

- [Basaratさんによるガイド]
- [tscをデバッグする方法]

[バグの例]: https://github.com/microsoft/TypeScript/issues/55091
[定数畳み込み]: https://www.wikiwand.com/ja/%E5%AE%9A%E6%95%B0%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF
[mini-TypeScript]: https://github.com/sandersn/mini-typescript
[字句解析器]: https://www.wikiwand.com/ja/%E5%AD%97%E5%8F%A5%E8%A7%A3%E6%9E%90#%E5%AD%97%E5%8F%A5%E8%A7%A3%E6%9E%90%E5%99%A8
[Basaratさんによるガイド]: https://basarat.gitbook.io/typescript/overview
[tscの開発チームによるメモ集]: https://github.com/microsoft/TypeScript-Compiler-Notes
[tscをデバッグする方法]: https://dev.to/andrewbranch/debugging-the-typescript-codebase-576o