# 機能設計書 100-末尾呼び出しチェック

## 概要

本ドキュメントは、F#コンパイラにおける末尾呼び出しチェック（Tail Call Checks）機能について記述する。`[<TailCall>]`属性が付与された関数の再帰呼び出しが末尾位置にあるかを検証し、末尾呼び出し最適化の適用可能性を静的に確認する。

### 本機能の処理概要

**業務上の目的・背景**：F#は関数型言語として再帰を多用する。末尾再帰は、再帰呼び出しが関数の最後の操作である場合に、スタックを消費せずにループに変換できる最適化を可能にする。`[<TailCall>]`属性を使用することで、開発者は特定の再帰関数が確実に末尾再帰として最適化されることを静的に検証できる。

**機能の利用シーン**：
- 大量の再帰を行う関数のスタックオーバーフロー防止
- アルゴリズムの末尾再帰化の検証
- パフォーマンスクリティカルなコードの最適化保証
- 関数型プログラミングパターンの安全な使用

**主要な処理内容**：
1. TailCall属性の検出 - 対象関数の識別
2. 末尾位置の解析 - 呼び出しが末尾位置にあるかの判定
3. 末尾呼び出しブロッカーの検出 - 最適化を妨げる要因の識別
4. 警告の生成 - 非末尾呼び出しに対する警告

**関連システム・外部連携**：型チェッカーの後、ポスト推論チェックと同様のタイミングで実行される。ILコード生成（IlxGen.fs）での.tail命令の発行判断にも関連する。

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

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | IDE統合 | 参照画面 | 非末尾呼び出し警告の表示 |

## 機能種別

末尾呼び出し検証

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| cenv | cenv | Yes | チェック環境 | - |
| expr | Expr | Yes | チェック対象の式 | - |
| tailCall | TailCall | Yes | 末尾呼び出しコンテキスト | - |

### 入力データソース

型チェッカーからのTAST（型付き抽象構文木）

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| result | unit | チェック完了（警告は副作用として出力） |

### 出力先

コンパイラ診断出力

## 処理フロー

### 処理シーケンス

```
1. TailCall属性付き関数の検出
   └─ mustTailCallセットに追加

2. 関数本体の解析
   ├─ 式をトラバース
   └─ 各再帰呼び出しをチェック

3. 末尾位置判定
   ├─ 関数の最後の操作か
   ├─ 戻り値型が一致するか
   └─ ブロッカーがないか

4. ブロッカー検出
   ├─ byref引数
   ├─ DllImport関数
   ├─ 固定ローカル（pinned locals）
   └─ 部分適用

5. 警告生成
   └─ 非末尾呼び出しに警告
```

### フローチャート

```mermaid
flowchart TD
    A[TailCall属性付き関数] --> B[本体解析]
    B --> C{再帰呼び出し?}
    C -->|Yes| D{末尾位置?}
    C -->|No| E[サブ式解析]
    D -->|Yes| F{ブロッカーあり?}
    D -->|No| G[警告生成]
    F -->|No| H[OK: 末尾呼び出し]
    F -->|Yes| G
    E --> B
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-100-1 | 末尾位置必須 | 呼び出しは関数の最後の操作 | TailCall属性付き関数 |
| BR-100-2 | byref禁止 | byref引数を持つ呼び出しは不可 | TailCall属性付き関数 |
| BR-100-3 | DllImport不可 | DllImport関数は末尾呼び出し不可 | TailCall属性付き関数 |
| BR-100-4 | 戻り値型一致 | void戻りの整合性が必要 | TailCall属性付き関数 |

### 計算ロジック

**末尾位置の判定**：
```fsharp
type TailCallReturnType =
    | MustReturnVoid  // unit戻り、void必須
    | NonVoid         // 非voidの戻り値

type TailCall =
    | Yes of TailCallReturnType
    | No
```

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

該当なし

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| FS3569 | NotTailRecursive | 非末尾位置での再帰呼び出し | コードを末尾再帰に書き換え |

### リトライ仕様

該当なし

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

該当なし

## パフォーマンス要件

末尾呼び出しチェックのオーバーヘッドは全体のコンパイル時間の1%未満であること

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

該当なし

## 備考

`[<TailCall>]`属性はF# 8.0で導入された。`--warnaserror:3569`で警告をエラーに昇格できる。

---

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

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

### 推奨読解順序

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

末尾呼び出しチェックで使用される型を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | TailCallChecks.fs | `src/Compiler/Checking/TailCallChecks.fs` | TailCall型、TailCallReturnType型、cenv型 |

**主要な型定義**:
- **25-31行目**: TailCallReturnType - 戻り値の種類（MustReturnVoid, NonVoid）
- **29-57行目**: TailCall - 末尾呼び出しコンテキスト（Yes, No）
- **68-83行目**: cenv - チェック環境（mustTailCall, hasPinnedLocals）

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

末尾呼び出しチェックの主要な関数を確認。

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

**主要処理フロー**:
- **150-217行目**: CheckForNonTailRecCall - 非末尾呼び出しのチェックと警告
- **220-307行目**: CheckExprLinear - 線形式のチェック
- **309-403行目**: CheckExpr - 式の再帰的チェック

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

末尾呼び出しチェックがどこから使われるかを確認。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | PostInferenceChecks.fs | `src/Compiler/Checking/PostInferenceChecks.fs` | ポスト推論チェックとの関係 |

**読解のコツ**:
- TailCall.Yesは「末尾位置にいる」、TailCall.Noは「末尾位置にいない」を表す
- mustTailCallセットはTailCall属性付き関数の集合
- CheckForNonTailRecCallで呼び出しがmustTailCallに含まれるか確認

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

```
PostInferenceChecks.fs
    │
    └─ TailCallChecks.fs
           │
           ├─ cenv（チェック環境）
           │      ├─ g: TcGlobals
           │      ├─ amap: ImportMap
           │      ├─ mustTailCall: Zset<Val>
           │      └─ hasPinnedLocals: bool
           │
           ├─ TailCall（末尾呼び出しコンテキスト）
           │      ├─ Yes(MustReturnVoid)
           │      ├─ Yes(NonVoid)
           │      └─ No
           │
           ├─ CheckExpr
           │      ├─ CheckForNonTailRecCall: 非末尾検出
           │      ├─ CheckApplication: アプリケーション式
           │      └─ CheckMatch: match式
           │
           └─ 警告出力
                  └─ FS3569: NotTailRecursive
```

### データフロー図

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

TailCall属性付き関数 ───▶ TailCallChecks ───▶ 警告メッセージ
          │                    │
          ▼                    │
    mustTailCallセット         │
          │                    ▼
          │            式トラバーサル
          │                    │
          │                    ├─ 末尾位置判定
          │                    │      ├─ Yes → OK
          │                    │      └─ No → 警告
          │                    │
          │                    └─ ブロッカー検出
          │                           ├─ byref引数
          │                           ├─ DllImport
          │                           └─ 固定ローカル
          │
          └───────────────────────────────────▶ FS3569警告
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| TailCallChecks.fs | `src/Compiler/Checking/TailCallChecks.fs` | ソース | 末尾呼び出しチェック実装 |
| TailCallChecks.fsi | `src/Compiler/Checking/TailCallChecks.fsi` | ソース | 公開シグネチャ |
| PostInferenceChecks.fs | `src/Compiler/Checking/PostInferenceChecks.fs` | ソース | 関連チェック |
| IlxGen.fs | `src/Compiler/CodeGen/IlxGen.fs` | ソース | .tail命令の発行 |
| TypedTree.fs | `src/Compiler/TypedTree/TypedTree.fs` | ソース | TAST型定義 |
