# 機能設計書 12-reduce

## 概要

本ドキュメントは、Zigコンパイラに組み込まれたバグレポート最小化ツール「reduce」の設計仕様を記載する。`zig reduce`コマンドは、コンパイラのバグを再現する最小限のソースコードを自動的に生成するデバッグ支援ツールである。

### 本機能の処理概要

**業務上の目的・背景**：コンパイラのバグを報告する際、バグを再現するための最小限のテストケースを作成することは、バグの特定と修正を効率化する上で非常に重要である。しかし、大規模なプロジェクトからバグを再現する最小コードを手動で抽出するのは、時間がかかり困難な作業である。本機能は、デルタデバッギング（Delta Debugging）アルゴリズムに基づいて、バグを再現しながらソースコードを自動的に削減し、開発者とコンパイラメンテナーの両方の作業効率を向上させる。

**機能の利用シーン**：
- コンパイラのバグを発見した際、GitHubイシューに報告するための最小再現コードを作成したい場合
- 大規模プロジェクトでコンパイルエラーやクラッシュが発生し、原因を特定したい場合
- テストケースを簡略化してデバッグ効率を向上させたい場合
- コンパイラ開発者がリグレッションテストケースを作成する場合

**主要な処理内容**：
1. インタレスティングネスチェッカー（interestingness checker）スクリプトの設定
2. ルートソースファイルの読み込みとAST解析
3. AST走査による変換候補（Transformation）の収集
4. 変換候補のランダムシャッフルと優先度付け
5. 二分探索的な変換適用と興味深さ（interestingness）の検証
6. 成功した変換の永続化とASTの再解析
7. 変換候補がなくなるまで繰り返し

**関連システム・外部連携**：
- 外部インタレスティングネスチェッカー（ユーザー提供の実行可能ファイル）
- 標準ライブラリ`std.zig.Ast`モジュール（構文解析・レンダリング）
- `std.zig.AstGen`モジュール（ZIR生成）
- ファイルシステムI/O

**権限による制御**：特に権限制御は実装されていない。外部チェッカーの実行権限とファイルシステムのアクセス権限に依存する。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| 11 | バグレポート最小化画面 | 主機能 | バグレポートを最小化するデバッグ支援処理 |

## 機能種別

データ変換処理 / 自動化ツール / デバッグ支援

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| checker | []const u8 | Yes | インタレスティングネスチェッカーの実行パス | 実行可能ファイルであること |
| root_source_file.zig | []const u8 | Yes | 削減対象のルートソースファイル | 有効なZigソースファイルであること |
| --seed | u32 | No | 乱数シードの指定（デフォルト: 0） | 32bit整数として解析可能 |
| --skip-smoke-test | フラグ | No | 初期インタレスティングネスチェックをスキップ | - |
| --main-mod-path | []const u8 | No | ルートモジュールのディレクトリ（未実装） | - |
| --mod | []const u8 | No | 依存モジュールの指定（未実装） | - |
| --deps | []const u8 | No | ルートパッケージの依存関係（未実装） | - |
| -- [argv] | [][]const u8 | No | チェッカーに転送する追加引数 | - |

### インタレスティングネスチェッカー仕様

| 終了コード | 意味 |
|-----------|------|
| 0 | interesting（バグが再現される） |
| 1 | unknown（無限ループ等の予期しない状態） |
| その他 | not interesting（バグが再現されない） |

### 入力データソース

- ファイルシステム上のZigソースファイル
- ユーザー提供のインタレスティングネスチェッカー（実行可能ファイル）

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| reduced_source | []const u8 | 最小化されたソースコード |
| transformation_log | []const u8 | 適用された変換のログ（標準エラー出力） |

### 出力先

- ルートソースファイル（上書き）
- 標準エラー出力（進捗・デバッグ情報）

## 処理フロー

### 処理シーケンス

```
1. コマンドライン引数の解析
   └─ チェッカーパス、ソースファイル、オプションの取得
2. ソースファイル読み込みとAST解析
   └─ std.zig.Ast.parseでASTを構築
3. スモークテスト（--skip-smoke-test未指定時）
   └─ 未変更の入力でチェッカーを実行し、interestingであることを確認
4. 変換候補の収集
   └─ Walk.findTransformationsでASTを走査
5. 変換候補のシャッフル
   └─ ランダムに並び替え（将来的に優先度付け予定）
6. 変換適用ループ
   └─ サブセットサイズを半減しながら試行
   └─ 変換をfixupsに変換
   └─ AST.renderでソースコード生成
   └─ AstGenで未使用変数検出、discard追加
   └─ ファイル書き込み
   └─ チェッカー実行
7. 結果判定
   └─ interesting: ソース再解析、変換再収集、ループ継続
   └─ boring/unknown: 次のサブセットを試行
8. 終了処理
   └─ 全変換が非interestingになったらソース復元して終了
```

### フローチャート

```mermaid
flowchart TD
    A[開始] --> B[引数解析]
    B --> C[ソースファイル読み込み]
    C --> D[AST解析]
    D --> E{スモークテスト?}
    E -->|Yes| F[チェッカー実行]
    E -->|No| G[変換候補収集]
    F --> H{interesting?}
    H -->|No| I[エラー終了]
    H -->|Yes| G
    G --> J[変換シャッフル]
    J --> K{変換候補あり?}
    K -->|No| L[終了]
    K -->|Yes| M[サブセット選択]
    M --> N[fixups生成]
    N --> O[ソース生成]
    O --> P[未使用変数処理]
    P --> Q[ファイル書き込み]
    Q --> R[チェッカー実行]
    R --> S{結果判定}
    S -->|interesting| T[AST再解析]
    T --> G
    S -->|boring/unknown| U{サブセット=1?}
    U -->|Yes| V[次の変換へ]
    U -->|No| W[サブセット縮小]
    V --> X{全変換試行?}
    W --> M
    X -->|No| M
    X -->|Yes| Y[ソース復元]
    Y --> L
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | サブセット縮小戦略 | サブセットサイズを3/4に縮小（最小1） | 各イテレーション |
| BR-02 | 成功時リスタート | interesting判定で全プロセスを再開 | 変換成功時 |
| BR-03 | 未使用変数自動処理 | ZIR生成でunused検出時、discard追加 | 変換適用後 |
| BR-04 | ランダムシャッフル | 変換候補をランダムに並び替え | 変換収集後 |

### 変換（Transformation）の種類

| 変換種別 | 説明 |
|---------|------|
| gut_function | 関数本体を`@trap()`に置換 |
| delete_node | グローバル宣言を削除 |
| delete_var_decl | ローカル変数宣言を削除し参照を`undefined`に置換 |
| replace_with_undef | 式を`undefined`に置換 |
| replace_with_true | 式を`true`に置換 |
| replace_with_false | 式を`false`に置換 |
| replace_node | ノードを別のノードに置換 |
| inline_imported_file | `@import`をインライン展開 |

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

本機能はデータベースを使用しない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | 引数不足 | チェッカーまたはソースファイルが未指定 | 使用方法を表示してfatal終了 |
| - | スモークテスト失敗 | 未変更入力でboring/unknown | エラーメッセージを表示してfatal終了 |
| - | 構文エラー | ソースファイルに構文エラー | panic発生 |
| - | ファイルアクセスエラー | ファイルの読み書き失敗 | fatal終了 |

### リトライ仕様

変換適用が失敗（boring/unknown）した場合、サブセットサイズを縮小して再試行する。サブセットサイズが1になっても失敗した場合は、次の変換候補に移行する。

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

ソースファイルへの書き込みは直接行われる。変換が成功しなかった場合、処理終了時に元のソースコードに復元される。

## パフォーマンス要件

- 大量の変換候補がある場合でも効率的に処理するため、二分探索的なアプローチを採用
- 乱数シードの指定により再現可能な処理を実現

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

- 外部チェッカーは任意のコマンドを実行可能であるため、信頼できるスクリプトのみを使用すること
- チェッカーの標準エラー出力はそのまま表示される

## 備考

- 本機能はC-Reduceに相当するZig言語用のツールである
- ロードマップに記載されている未実装機能:
  - スレッドプール対応
  - モジュールフラグのパース
  - より高度な変換（`and`/`or`のオペランド置換、if条件の置換等）
  - コンパイラフラグの削減
  - ビルドシステム統合

---

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

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

### 推奨読解順序

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

まず、reduce処理で使用される主要なデータ構造を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | Walk.zig | `lib/compiler/reduce/Walk.zig` | **15-49行目**: Transformation union型の定義。各変換種別の構造を確認 |
| 1-2 | reduce.zig | `lib/compiler/reduce.zig` | **37行目**: Interestingness enum（interesting/unknown/boring） |

**読解のコツ**: `Transformation`はunion型で、各変換種別に応じた異なるペイロード（ASTノードインデックス、参照リスト等）を持つ。

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

処理の起点となる関数を特定する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | main.zig | `src/main.zig` | **368-372行目**: `zig reduce`コマンドのディスパッチ。jitCmdでreduce.zigを呼び出し |
| 2-2 | reduce.zig | `lib/compiler/reduce.zig` | **50-274行目**: main関数がメインエントリーポイント |

**主要処理フロー**:
1. **62-99行目**: コマンドライン引数の解析
2. **101-104行目**: チェッカーとソースファイルパスの取得
3. **117-121行目**: ソースファイルの読み込みとAST解析
4. **123-131行目**: スモークテスト（初期インタレスティングネス確認）
5. **156-159行目**: 変換候補の収集とシャッフル
6. **161-271行目**: メイン変換ループ

#### Step 3: 変換検出層を理解する

ASTを走査して変換候補を見つける処理を読み解く。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | Walk.zig | `lib/compiler/reduce/Walk.zig` | **54-83行目**: findTransformations関数。AST走査のエントリーポイント |
| 3-2 | Walk.zig | `lib/compiler/reduce/Walk.zig` | **85-94行目**: walkMembers関数。グローバル宣言の走査 |

**主要処理フロー**:
- **54-83行目**: Walk構造体の初期化とルート宣言の走査
- **85-94行目**: メンバー宣言の走査ループ
- **78-82行目**: 未参照グローバルの削除変換を追加

#### Step 4: 変換適用層を理解する

収集した変換をソースコードに適用する処理を確認する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | reduce.zig | `lib/compiler/reduce.zig` | **308-391行目**: transformationsToFixups関数。変換をAST.Render.Fixupsに変換 |
| 4-2 | reduce.zig | `lib/compiler/reduce.zig` | **183-226行目**: レンダリングと未使用変数処理 |

**主要処理フロー**:
- **318-339行目**: 各変換種別に応じたfixupsの設定
- **183行目**: tree.renderでフォーマット済みソース生成
- **188-224行目**: AstGenで未使用変数を検出しdiscardを追加

#### Step 5: チェッカー実行層を理解する

外部チェッカーの実行と結果判定を確認する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | reduce.zig | `lib/compiler/reduce.zig` | **301-306行目**: runCheck関数。チェッカープロセスの実行 |
| 5-2 | reduce.zig | `lib/compiler/reduce.zig` | **283-299行目**: termToInteresting関数。終了コードからInterestingnessへの変換 |

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

```
main.zig::mainArgs
    │
    └─ jitCmd (JITコンパイル実行)
           │
           └─ reduce.zig::main (エントリーポイント)
                  │
                  ├─ parse (ソースファイル読み込み・AST解析)
                  │      └─ std.zig.Ast.parse
                  │
                  ├─ runCheck (スモークテスト)
                  │      └─ std.process.run
                  │
                  └─ メイン変換ループ
                         │
                         ├─ Walk.findTransformations
                         │      └─ walkMembers (AST走査)
                         │
                         ├─ sortTransformations (シャッフル)
                         │
                         ├─ transformationsToFixups
                         │
                         ├─ tree.render (ソース生成)
                         │
                         ├─ std.zig.AstGen.generate (未使用変数検出)
                         │
                         ├─ writeFile (ファイル書き込み)
                         │
                         └─ runCheck (インタレスティングネス判定)
                                └─ termToInteresting
```

### データフロー図

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

ソースファイル ───▶ Ast.parse ───▶ AST構造
                                        │
                                        ▼
                            Walk.findTransformations
                                        │
                                        ▼
                              変換候補リスト
                                        │
                    ┌───────────────────┼───────────────────┐
                    │                   │                   │
                    ▼                   ▼                   ▼
              シャッフル      サブセット選択      fixups生成
                    │                   │                   │
                    └───────────────────┼───────────────────┘
                                        │
                                        ▼
                                  tree.render
                                        │
                                        ▼
                              フォーマット済みソース
                                        │
                                        ▼
                                AstGen.generate
                                        │
                                        ▼
                              未使用変数処理済みソース
                                        │
                          ┌─────────────┴─────────────┐
                          │                           │
                          ▼                           ▼
                   ファイル書き込み              チェッカー実行
                          │                           │
                          │                           ▼
                          │                    Interestingness
                          │                           │
                          │         ┌─────────────────┼─────────────────┐
                          │         │                 │                 │
                          │         ▼                 ▼                 ▼
                          │   interesting         unknown           boring
                          │         │                 │                 │
                          │         ▼                 └────────┬────────┘
                          │   ソース確定                       ▼
                          │   AST再解析                  次のサブセット
                          │         │                         │
                          └─────────┴─────────────────────────┘
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| reduce.zig | `lib/compiler/reduce.zig` | ソース | reduceコマンドのメイン実装 |
| Walk.zig | `lib/compiler/reduce/Walk.zig` | ソース | AST走査と変換候補収集 |
| main.zig | `src/main.zig` | ソース | CLIエントリーポイント |
| Ast.zig | `lib/std/zig/Ast.zig` | ソース | AST定義とレンダリング |
| AstGen.zig | `lib/std/zig/AstGen.zig` | ソース | ZIR生成（未使用変数検出用） |
