# 機能設計書 96-パターンマッチコンパイル

## 概要

本ドキュメントは、F#コンパイラにおけるパターンマッチコンパイル機能について記述する。F#のmatch式やlet束縛で使用されるパターンを、効率的な決定木（Decision Tree）に変換し、最終的にILコードを生成するための中間表現を構築する。

### 本機能の処理概要

**業務上の目的・背景**：F#は強力なパターンマッチング機能を持ち、判別共用体、レコード、リスト、アクティブパターン等に対するパターンマッチングをサポートする。これらのパターンを効率的に実行するためには、パターンの順序を分析し、最小限のテストで正しい分岐に到達できる決定木を構築する必要がある。

**機能の利用シーン**：
- match式のコンパイル
- let束縛でのパターン分解
- 関数引数のパターンマッチ
- try/with例外ハンドラのパターンマッチ
- コンピュテーション式のパターンマッチ

**主要な処理内容**：
1. パターンの分析 - ガード条件、ネストしたパターン、網羅性の分析
2. 決定木の構築 - 効率的なテスト順序を決定
3. 網羅性チェック - すべてのケースがカバーされているか検証
4. 冗長性チェック - 到達不能なパターンを検出
5. ILコード生成用の中間表現生成

**関連システム・外部連携**：型チェッカー（CheckExpressions.fs）からパターン式を受け取り、型付き構文木（Typed Tree）の一部として決定木を生成する。ILコード生成（IlxGen.fs）で最終的なコードに変換される。

**権限による制御**：該当なし（コンパイラ内部機能）

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | IDE統合 | 参照画面 | 網羅性警告、冗長パターン警告の表示 |

## 機能種別

パターンマッチコンパイル

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| cenv | TcFileState | Yes | 型チェック環境 | - |
| inputExpr | Expr | Yes | マッチ対象の式 | - |
| clauseList | MatchClause list | Yes | パターン句のリスト | 空でないこと |

### 入力データソース

型チェッカーからのパターン式

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| DecisionTree | DecisionTree | コンパイル済み決定木 |
| warnings | Diagnostic list | 網羅性・冗長性の警告 |

### 出力先

型付き構文木、診断メッセージ

## 処理フロー

### 処理シーケンス

```
1. パターン収集
   ├─ 各clause（パターン | ガード -> ボディ）を収集
   └─ パターンの型情報を取得

2. 行列構築
   ├─ パターン行列を構築
   └─ アクション（ボディ式）を関連付け

3. 決定木生成
   ├─ 列選択ヒューリスティックを適用
   ├─ パターンをテストに変換
   └─ 再帰的に部分木を構築

4. 網羅性チェック
   ├─ 残存パターンを計算
   └─ カバーされていないケースを警告

5. 冗長性チェック
   └─ 到達不能なパターンを警告

6. 決定木最適化
   └─ 共通部分木の共有
```

### フローチャート

```mermaid
flowchart TD
    A[パターン句リスト] --> B[パターン行列構築]
    B --> C[決定木生成]
    C --> D[列選択]
    D --> E{テスト種別}
    E -->|定数| F[定数テスト]
    E -->|コンストラクタ| G[コンストラクタテスト]
    E -->|型| H[型テスト]
    F --> I[サブツリー生成]
    G --> I
    H --> I
    I --> J{全パターン処理済?}
    J -->|No| D
    J -->|Yes| K[網羅性チェック]
    K --> L[冗長性チェック]
    L --> M[決定木返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-96-1 | 網羅性 | 判別共用体は全ケースをカバー必須 | 警告有効時 |
| BR-96-2 | 冗長性 | 到達不能パターンは警告 | 常時 |
| BR-96-3 | 順序保持 | パターンは上から順に評価 | 常時 |
| BR-96-4 | ガード評価 | ガード条件は副作用を持つ可能性あり | ガード付きパターン |

### 計算ロジック

**列選択ヒューリスティック**：
```
1. 完全に決定的な列を優先（定数パターンのみ）
2. コンストラクタパターンの列を優先
3. 型テストの列を次に
4. ワイルドカードのみの列は最後
```

## データベース操作仕様

該当なし

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| FS0025 | IncompletePatternMatch | 網羅的でないパターン | ワイルドカードケースを追加 |
| FS0026 | RuleNeverMatched | 到達不能パターン | 冗長なパターンを削除 |

### リトライ仕様

該当なし

## トランザクション仕様

該当なし

## パフォーマンス要件

大規模な判別共用体（100ケース以上）でも効率的にコンパイルできること

## セキュリティ考慮事項

該当なし

## 備考

`--warnaserror:25`で網羅性警告をエラーに昇格できる。`#nowarn "25"`で特定箇所の警告を抑制できる。

---

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

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

### 推奨読解順序

#### Step 1: データ構造を理解する

決定木とパターン行列の型を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | PatternMatchCompilation.fs | `src/Compiler/Checking/PatternMatchCompilation.fs` | DecisionTree型、Test型の定義 |

**主要な型定義**:
- **DecisionTree**: パターンマッチの決定木
- **DecisionTreeTarget**: 決定木のターゲット（マッチ時の処理）
- **Test**: 各種テスト（定数、コンストラクタ、型等）

#### Step 2: エントリーポイントを理解する

パターンマッチコンパイルの主要な関数を確認。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | PatternMatchCompilation.fs | `src/Compiler/Checking/PatternMatchCompilation.fs` | CompilePatternMatch関数 |

**主要処理フロー**:
- **100-150行目**: パターン行列の構築
- **200-300行目**: 決定木生成アルゴリズム
- **350-400行目**: 網羅性・冗長性チェック

#### Step 3: 呼び出し元を理解する

パターンマッチコンパイルがどこから使われるかを確認。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | CheckExpressions.fs | `src/Compiler/Checking/CheckExpressions.fs` | match式のチェックからの呼び出し |

**読解のコツ**:
- 決定木は再帰的なデータ構造で、各ノードがテストと分岐を持つ
- パターン行列は行がパターン句、列がサブパターンの位置に対応
- 網羅性チェックは「残存パターン」を計算する逆方向のアルゴリズム

### プログラム呼び出し階層図

```
CheckExpressions.fs (TcExprUndelayed)
    │
    └─ PatternMatchCompilation.fs
           │
           ├─ CompilePatternMatch
           │      ├─ パターン行列構築
           │      ├─ 決定木生成
           │      └─ 網羅性/冗長性チェック
           │
           ├─ DecisionTree
           │      ├─ TDSuccess: マッチ成功
           │      ├─ TDBind: バインディング
           │      └─ TDSwitch: テスト分岐
           │
           └─ Test
                  ├─ DecisionTreeTest.Const: 定数テスト
                  ├─ DecisionTreeTest.UnionCase: 共用体ケーステスト
                  ├─ DecisionTreeTest.ArrayLength: 配列長テスト
                  └─ DecisionTreeTest.IsInst: 型テスト
```

### データフロー図

```
[入力]                    [処理]                      [出力]

match expr with        →  CompilePatternMatch  →   DecisionTree
| pat1 -> e1                    │                      │
| pat2 -> e2                    ▼                      ▼
| pat3 -> e3               パターン行列         ┌──────────────┐
                          ┌─────────────┐       │ TDSwitch     │
                          │ pat1 | e1   │  →    │   Test1      │
                          │ pat2 | e2   │       │   ├─ case1   │
                          │ pat3 | e3   │       │   └─ case2   │
                          └─────────────┘       │ TDSuccess(e1)│
                                                └──────────────┘
                                                      │
                                                      ▼
                                                + 警告メッセージ
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| PatternMatchCompilation.fs | `src/Compiler/Checking/PatternMatchCompilation.fs` | ソース | パターンマッチコンパイル実装 |
| PatternMatchCompilation.fsi | `src/Compiler/Checking/PatternMatchCompilation.fsi` | ソース | 公開シグネチャ |
| CheckExpressions.fs | `src/Compiler/Checking/CheckExpressions.fs` | ソース | 呼び出し元（match式チェック） |
| TypedTree.fs | `src/Compiler/TypedTree/TypedTree.fs` | ソース | DecisionTree型定義 |
| IlxGen.fs | `src/Compiler/CodeGen/IlxGen.fs` | ソース | 決定木からILへの変換 |
