# 機能設計書 77-キャッシュ

## 概要

本ドキュメントは、F#コンパイラ内部で使用するキャッシュ機構の設計を記述する。LRU（Least Recently Used）ベースのキャッシュ実装を提供し、メトリクス収集、複数のエビクションモード、スレッドセーフな操作をサポートする。

### 本機能の処理概要

**業務上の目的・背景**：F#コンパイラは、型チェック、解決済みシンボル、パース結果など、計算コストの高い中間結果を繰り返し使用する。これらの結果をキャッシュすることで、再計算を避け、コンパイル性能を大幅に向上させることができる。本機能は、汎用的で高性能なキャッシュ実装を提供し、コンパイラ全体で一貫したキャッシュ戦略を適用可能にする。

**機能の利用シーン**：コンパイラの各段階（レキシング、パーシング、型チェック、最適化など）で、計算済みの結果をキャッシュする際に使用される。IDE統合では、インクリメンタルコンパイルの効率化に貢献する。

**主要な処理内容**：
1. ConcurrentDictionaryベースのスレッドセーフなキー・バリューストア
2. LinkedListによるLRUエビクション順序管理
3. 3つのエビクションモード（NoEviction、Immediate、MailboxProcessor）
4. .NETメトリクスAPIによる統計情報の収集と公開
5. 容量オーバー時の自動エビクション
6. 参照IDベースのキー比較オプション

**関連システム・外部連携**：System.Collections.Concurrent、System.Diagnostics.Metricsと連携する。

**権限による制御**：本機能に特別な権限制御は存在しない。

## 関連画面

本機能はコンパイラ内部機能であり、直接関連する画面は存在しない。

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | - |

## 機能種別

キャッシュ / メモリ管理 / パフォーマンス最適化

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| TotalCapacity | int | Yes | キャッシュの総容量 | 0以上 |
| HeadroomPercentage | int | Yes | エビクション用のヘッドルーム割合 | 0以上 |
| EvictionMode | EvictionMode | Yes | エビクション方式 | NoEviction/Immediate/MailboxProcessor |
| Comparer | IEqualityComparer<'Key> | Yes | キー比較器 | null不可 |

### 入力データソース

- キャッシュ対象のキー・バリューペア

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| Value | 'Value | キャッシュされた値 |
| bool | bool | 操作の成功/失敗 |

### 出力先

- メモリ（キャッシュ格納）
- メトリクスカウンター

## 処理フロー

### 処理シーケンス

```
【GetOrAdd】
1. ConcurrentDictionary.GetOrAddでエンティティ取得/作成
2. 新規作成時:
   a. CachedEntityを作成
   b. Addメッセージを送信（非同期キューまたは即時）
   c. Missメトリクス記録
3. 既存取得時:
   a. Updateメッセージを送信（LRU順序更新）
   b. Hitメトリクス記録
4. 値を返却

【エビクション処理】
1. Addメッセージ受信
2. LinkedListの末尾にノード追加
3. 容量超過時:
   a. LinkedListの先頭（最古）を取得
   b. ConcurrentDictionaryから削除
   c. 削除成功: Evictionメトリクス
   d. 削除失敗: rebuildStore検討
```

### フローチャート

```mermaid
flowchart TD
    A[GetOrAdd呼び出し] --> B{キーが存在?}
    B -->|Yes| C[既存エンティティ取得]
    B -->|No| D[valueFactory実行]
    D --> E[CachedEntity作成]
    E --> F[store.GetOrAdd]
    C --> G[Hit記録]
    F --> H[Miss記録]
    G --> I[Update送信]
    H --> J[Add送信]
    I --> K[値返却]
    J --> K

    L[Add受信] --> M[LinkedList末尾に追加]
    M --> N{容量超過?}
    N -->|No| O[完了]
    N -->|Yes| P[先頭エンティティ取得]
    P --> Q[storeから削除]
    Q --> R{削除成功?}
    R -->|Yes| S[Eviction記録]
    R -->|No| T[EvictionFail記録]
    T --> U{deadKeysCount > headroom/2?}
    U -->|Yes| V[rebuildStore]
    U -->|No| O
    S --> O
    V --> O
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-77-01 | LRUエビクション | 最も長く使用されていないエントリを優先的に削除 | 容量超過時 |
| BR-77-02 | ヘッドルーム | TotalCapacityのHeadroomPercentage分をエビクション用に確保 | 常時 |
| BR-77-03 | デッドキー処理 | エビクション失敗が多い場合はストアを再構築 | deadKeysCount > headroom/2 |
| BR-77-04 | 環境変数制御 | FSharp_CacheEvictionImmediate設定でImmediateモード強制 | 環境変数設定時 |
| BR-77-05 | デフォルト容量 | デフォルトのTotalCapacityは1024 | オプション未指定時 |

### 計算ロジック

- 容量計算: `capacity = TotalCapacity - headroom`
- ヘッドルーム計算: `headroom = TotalCapacity * HeadroomPercentage / 100`
- ヒット率計算: `ratio = hits / (hits + misses)`

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

本機能はデータベース操作を行わない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| ArgumentException | 例外 | Capacity < 0 | パラメータ検証 |
| ArgumentException | 例外 | HeadroomPercentage < 0 | パラメータ検証 |
| - | エビクション失敗 | キーの参照同一性が失われた | EvictionFailイベント発火、rebuildStore検討 |

### リトライ仕様

エビクション失敗時は、deadKeysCountがしきい値を超えた場合にストアを再構築する。

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

本機能はトランザクション管理を必要としない。ConcurrentDictionaryによるアトミック操作を使用。

## パフォーマンス要件

- O(1)のキャッシュルックアップ
- MailboxProcessorによるエビクション処理の非同期化
- ConcurrentDictionaryによるロックフリーな読み取り

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

- キャッシュ内容は信頼されたコンパイラ内部データのみ
- メモリ使用量の制限によりDoS攻撃を緩和

## 備考

- DEBUGビルドでは各キャッシュにメトリクスリスナーがアタッチされる
- EvictionMode.MailboxProcessorがデフォルト（パフォーマンス最適）
- キャッシュはIDisposableを実装し、Finalizerでもクリーンアップを保証

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | Caches.fs | `src/Compiler/Utilities/Caches.fs` | CacheOptions、CachedEntity |

**主要処理フロー**:
- **154-158行目**: EvictionMode列挙型 - 3つのエビクション方式
- **160-174行目**: CacheOptions構造体 - キャッシュ設定
- **206-229行目**: CachedEntity - キャッシュエントリの実体

**読解のコツ**: CachedEntityは参照型（classではなくSealedクラス）であることが重要。LinkedListNodeとの相互参照を管理するため。

#### Step 2: メトリクスを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | Caches.fs | `src/Compiler/Utilities/Caches.fs` | CacheMetricsモジュール |

**主要処理フロー**:
- **11-18行目**: カウンター定義（adds、hits、misses等）
- **44-74行目**: Stats クラス - 統計情報の集約
- **81-95行目**: ListenToAll - メトリクスリスナーの設定
- **128-152行目**: CacheMetricsListener - 個別キャッシュ用リスナー

#### Step 3: キャッシュ本体を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | Caches.fs | `src/Compiler/Utilities/Caches.fs` | Cache<'Key, 'Value>クラス |

**主要処理フロー**:
- **238-268行目**: コンストラクタ - 初期化とバリデーション
- **282-313行目**: processEvictionMessage - エビクション処理の中核
- **315-327行目**: startEvictionProcessor - MailboxProcessor起動
- **357-398行目**: TryGetValue、TryAdd、GetOrAdd - 主要API
- **420-431行目**: Dispose、Finalize - リソース解放

**読解のコツ**: `post`変数はエビクションモードに応じて異なる関数を保持する。NoEvictionならignore、Immediateならlock付き処理、MailboxProcessorならPost。

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

```
Cache<'Key, 'Value>
    │
    ├─ GetOrAdd / TryAdd / AddOrUpdate
    │      │
    │      ├─ ConcurrentDictionary操作
    │      │
    │      └─ post (EvictionQueueMessage)
    │             │
    │             ├─ EvictionMode.NoEviction: ignore
    │             │
    │             ├─ EvictionMode.Immediate: lock + processEvictionMessage
    │             │
    │             └─ EvictionMode.MailboxProcessor: evictionProcessor.Post
    │                    │
    │                    └─ async loop → processEvictionMessage
    │
    ├─ processEvictionMessage
    │      │
    │      ├─ LinkedList操作（Add/Update）
    │      │
    │      ├─ 容量チェック
    │      │
    │      └─ エビクション実行
    │             │
    │             ├─ ConcurrentDictionary.TryRemove
    │             │
    │             └─ rebuildStore（必要時）
    │
    └─ CacheMetrics
           │
           ├─ Add / Hit / Miss / Eviction / EvictionFail
           │
           └─ Meter.CreateCounter
```

### データフロー図

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

key, value ─────────────▶ TryAdd ─────────────────────────────▶ bool
    │                        │
    │                        ├─ CachedEntity.Create
    │                        │
    │                        ├─ ConcurrentDictionary.TryAdd
    │                        │
    │                        └─ EvictionQueueMessage.Add送信
    │
key, valueFactory ──────▶ GetOrAdd ───────────────────────────▶ value
    │                        │
    │                        ├─ ConcurrentDictionary.GetOrAdd
    │                        │
    │                        └─ Hit/Miss記録

EvictionQueueMessage ───▶ processEvictionMessage
    │                        │
    │                        ├─ LinkedList更新
    │                        │
    │                        └─ 必要時エビクション
    │
    └──────────────────────────────────────────────────────────▶ Evictedイベント
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| Caches.fs | `src/Compiler/Utilities/Caches.fs` | ソース | キャッシュ機構の主実装 |
| Caches.fsi | `src/Compiler/Utilities/Caches.fsi` | シグネチャ | 公開APIの定義 |
| Metrics.fs | `src/Compiler/Facilities/Diagnostics/Metrics.fs` | ソース | メトリクスMeter定義 |
