# 機能設計書 88-型付き構文木操作

## 概要

本ドキュメントは、F#コンパイラにおける型付き抽象構文木（TAST）の操作ユーティリティ機能の設計について記述する。この機能は、TASTの走査、変換、比較、インスタンス化などの基本操作を提供する。

### 本機能の処理概要

**業務上の目的・背景**：
TypedTreeOps.fsは、TASTを操作するための包括的なユーティリティ関数群を提供する。型のインスタンス化、リマッピング、フォールディング、自由変数の収集など、コンパイラ全体で使用される基本操作を実装している。

**機能の利用シーン**：
- 型推論での型の統一・インスタンス化
- 最適化での式変換
- コード生成での型情報取得
- シンボル情報の取得・比較

**主要な処理内容**：
1. 型のインスタンス化（instType, instTypes）
2. 型のリマッピング（remapTypeAux, remapTypesAux）
3. 式のフォールディング（FoldExpr, FoldImplFile）
4. 自由変数の収集（freeInExpr, freeInType）
5. 型/値マップの管理（TyparMap, TyconRefMap, ValMap）

**関連システム・外部連携**：
- TypedTree: TAST型定義
- TcGlobals: グローバル型情報
- 各種最適化パス

**権限による制御**：
特になし。コンパイラ内部のユーティリティ。

## 関連画面

該当なし（コンパイラ内部機能）

## 機能種別

コンパイラユーティリティ（TAST操作）

## 入力仕様

### 主要な関数

| 関数名 | パラメータ | 説明 |
|--------|----------|------|
| instType | instInfo, ty | 型をインスタンス化 |
| instTypes | instInfo, tys | 型リストをインスタンス化 |
| remapTypeAux | tyenv, ty | 型をリマップ |
| FoldExpr | folder, z, expr | 式をフォールド |
| freeInExpr | opts, expr | 式の自由変数を収集 |

## 出力仕様

各関数は変換後の型、式、または収集結果を返す。

## 処理フロー

### 型のインスタンス化

```
instType (instInfo, ty)
    │
    ├─ ty = TType_var (typar) の場合
    │      └─ TyparMap.tryFind typar → 置換型 or 元の型
    │
    ├─ ty = TType_app (tcref, tys) の場合
    │      └─ TType_app (tcref, instTypes tys)
    │
    ├─ ty = TType_fun (d, r) の場合
    │      └─ TType_fun (instType d, instType r)
    │
    └─ ty = TType_forall (tps, ty) の場合
           └─ TType_forall (tps, instType ty)
```

### 式のフォールディング

```
FoldExpr (folder, z, expr)
    │
    ├─ folder.exprIntercept でインターセプト
    │
    ├─ expr = Expr.Val の場合
    │      └─ folder.valBindingSiteIntercept
    │
    ├─ expr = Expr.Let (bind, body) の場合
    │      └─ FoldExpr body |> FoldBinding bind
    │
    ├─ expr = Expr.Lambda の場合
    │      └─ FoldExpr body
    │
    └─ その他の式
           └─ 再帰的にサブ式をフォールド
```

## データ構造仕様

### TyparMap

型パラメータから型への写像。

```fsharp
type TyparMap<'T> = {
    entries: (Typar * 'T) list
}
```

### TyconRefMap

型コンストラクタ参照から値への写像。

### ValMap

値から値への写像。

### Remap

リマッピング情報を保持する構造体。

```fsharp
type Remap = {
    tpinst: TyparInstantiation
    valRemap: ValMap<ValRef>
    tyconRefRemap: TyconRefRemap
    removeTraitSolutions: bool
}
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-88-01 | 型インスタンス化 | 型パラメータを具体的な型に置換 | ジェネリック関数呼び出し時 |
| BR-88-02 | トレイト解決除去 | removeTraitSolutions=trueでトレイト解決を除去 | ILコード生成時 |
| BR-88-03 | 自由変数収集 | 束縛されていない変数を収集 | クロージャ生成時 |

## 備考

- StackGuard("CollectLocals")で深い再帰を保護
- 型のインスタンス化は遅延評価（必要時のみ計算）
- フォールディングはインターセプトによるカスタマイズが可能

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: マップ構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | TypedTreeOps.fs | `src/Compiler/TypedTree/TypedTreeOps.fs` | TyparMap型 |
| 1-2 | TypedTreeOps.fs | `src/Compiler/TypedTree/TypedTreeOps.fs` | TyconRefMap型 |
| 1-3 | TypedTreeOps.fs | `src/Compiler/TypedTree/TypedTreeOps.fs` | ValMap型 |
| 1-4 | TypedTreeOps.fs | `src/Compiler/TypedTree/TypedTreeOps.fs` | Remap型 |

#### Step 2: 型操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | TypedTreeOps.fs | `src/Compiler/TypedTree/TypedTreeOps.fs` | instType関数 |
| 2-2 | TypedTreeOps.fs | `src/Compiler/TypedTree/TypedTreeOps.fs` | remapTypeAux関数 |

#### Step 3: フォールディングを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | TypedTreeOps.fs | `src/Compiler/TypedTree/TypedTreeOps.fs` | ExprFolder型 |
| 3-2 | TypedTreeOps.fs | `src/Compiler/TypedTree/TypedTreeOps.fs` | FoldExpr関数 |

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| TypedTreeOps.fs | `src/Compiler/TypedTree/TypedTreeOps.fs` | ソース | TAST操作ユーティリティ |
| TypedTree.fs | `src/Compiler/TypedTree/TypedTree.fs` | ソース | TAST型定義 |
| TypedTreeBasics.fs | `src/Compiler/TypedTree/TypedTreeBasics.fs` | ソース | 基本操作 |
| TcGlobals.fs | `src/Compiler/TypedTree/TcGlobals.fs` | ソース | グローバル型情報 |
