# 機能設計書 9-System.Collections.Immutable

## 概要

本ドキュメントは、.NET runtimeプロジェクトにおけるSystem.Collections.Immutableライブラリの機能設計について記述する。System.Collections.Immutableは変更不可能なコレクション型を提供し、スレッドセーフかつ関数型プログラミングスタイルでのデータ操作を可能にする。

### 本機能の処理概要

**業務上の目的・背景**：System.Collections.Immutableは、一度作成されたら変更できないコレクション型を提供する。イミュータブルなデータ構造は、並行処理での安全性、デバッグの容易さ、予測可能な動作を実現する。変更操作は新しいコレクションを返すため、元のデータは常に保持される。

**機能の利用シーン**：
- マルチスレッド環境での安全なデータ共有（ロック不要）
- 関数型プログラミングパターン
- 変更履歴の追跡（各バージョンを保持）
- 設定データや定数データの表現

**主要な処理内容**：
1. ImmutableList<T>：イミュータブルリスト
2. ImmutableDictionary<TKey, TValue>：イミュータブル辞書
3. ImmutableHashSet<T>：イミュータブルハッシュセット
4. ImmutableArray<T>：イミュータブル配列
5. ImmutableQueue<T>/ImmutableStack<T>：イミュータブルキュー/スタック
6. FrozenDictionary/FrozenSet：読み取り専用最適化コレクション

**関連システム・外部連携**：
- LINQ統合
- System.Collections.Generic（IReadOnlyCollectionインターフェース）

**権限による制御**：
- 特になし（汎用ライブラリ）

## 関連画面

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

## 機能種別

データ構造 / イミュータブルコレクション

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| 初期要素 | IEnumerable<T> | No | 初期化時の要素 | null許容 |
| 等価比較器 | IEqualityComparer<T> | No | カスタム比較器 | null許容 |
| キー比較器 | IEqualityComparer<TKey> | No | 辞書用キー比較器 | null許容 |

### 入力データソース

- 既存コレクションからの変換
- ビルダーパターンによる構築

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 新コレクション | ImmutableXxx<T> | 操作結果の新しいイミュータブルコレクション |
| 値 | T | 取得された要素 |

### 出力先

- 呼び出し元への新コレクション返却

## 処理フロー

### 処理シーケンス

```
1. 操作要求（Add/Remove/SetItem）
   └─ 変更操作の受付
2. 構造共有判定
   └─ 既存ノードの再利用可否
3. 新ノード作成
   └─ 差分のみ新規作成
4. 新ルート構築
   └─ 共有ノード + 新ノードで新ツリー
5. 新コレクション返却
   └─ 元のコレクションは不変
```

### フローチャート

```mermaid
flowchart TD
    A[Add要求] --> B[既存ツリー走査]
    B --> C[挿入位置特定]
    C --> D[パス上のノードをコピー]
    D --> E[新ノード追加]
    E --> F[新ルート返却]
    F --> G[元のコレクション不変]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 構造共有 | 変更のないサブツリーは共有 | 全操作 |
| BR-02 | Freeze処理 | HashBucketのFreeze処理 | コレクション確定時 |
| BR-03 | ビルダー最適化 | Builderで効率的な連続操作 | 大量変更時 |

### 計算ロジック

- ImmutableList<T>：AVLツリー、O(log n)操作
- ImmutableDictionary<TKey, TValue>：HAMTライクなハッシュツリー
- ImmutableArray<T>：配列コピー、O(n)変更

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

### 操作別データベース影響一覧

| 操作 | 対象テーブル | 操作種別 | 概要 |
|-----|-------------|---------|------|
| - | - | - | コレクションライブラリはデータベースを操作しない |

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| ArgumentNullException | 引数null | nullキー（辞書） | null検証 |
| KeyNotFoundException | キー不在 | 辞書アクセス | TryGetValue使用 |

### リトライ仕様

- 該当なし（同期的操作、イミュータブルのため競合なし）

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

コレクションライブラリはトランザクション管理を行わない。ただし、イミュータブル性により原子的な更新パターンが可能。

## パフォーマンス要件

- ImmutableDictionary読み取り：O(log n)
- ImmutableList操作：O(log n)
- 構造共有によるメモリ効率化

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

- イミュータブル性による並行アクセス安全性
- 防御的コピー不要

## 備考

- .NET Core 2.0でコア統合
- FrozenDictionary/FrozenSetは.NET 8で追加

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | ImmutableDictionary_2.cs | `src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableDictionary_2.cs` | イミュータブル辞書の基本構造 |

**読解のコツ**:
- **ImmutableDictionary_2.cs 12-16行目**: クラス概要コメント - イミュータブル順序なし辞書
- **ImmutableDictionary_2.cs 20行目**: `ImmutableDictionary<TKey, TValue>`クラス定義
- **ImmutableDictionary_2.cs 25行目**: `public static readonly ImmutableDictionary<TKey, TValue> Empty` - 空インスタンス
- **ImmutableDictionary_2.cs 30行目**: `s_FreezeBucketAction` - HashBucketのFreeze処理
- **ImmutableDictionary_2.cs 35行目**: `_count` - 要素数
- **ImmutableDictionary_2.cs 40行目**: `_root` - SortedInt32KeyNode<HashBucket>ルート
- **ImmutableDictionary_2.cs 45行目**: `_comparers` - 比較器

#### Step 2: 構造共有を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | ImmutableDictionary_2.cs (53-61行目) | `src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableDictionary_2.cs` | コンストラクタ |

**主要処理フロー**:
- **53-61行目**: プライベートコンストラクタ - root, comparers, countを受け取り
- **58行目**: `root.Freeze(s_FreezeBucketAction)` - ルートノードのFreeze
- **67-71行目**: 空コレクション用コンストラクタ

#### Step 3: KeyCollisionBehaviorを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | ImmutableDictionary_2.cs (76-80行目) | `src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableDictionary_2.cs` | 衝突時動作 |

**主要処理フロー**:
- **76-80行目**: `KeyCollisionBehavior`列挙 - キー衝突時の動作定義

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

```
ImmutableDictionary<TKey, TValue>
    │
    ├─ Add(key, value)
    │      ├─ _root の変更パスをコピー
    │      ├─ 新 HashBucket 作成
    │      └─ 新 ImmutableDictionary 返却（元は不変）
    │
    ├─ TryGetValue(key, out value)
    │      └─ _root から検索（変更なし）
    │
    └─ SetItem(key, value)
           ├─ 既存キーの値更新
           └─ 新コレクション返却

SortedInt32KeyNode<HashBucket>
    │
    └─ 内部ツリー構造（ハッシュコードでソート）
```

### データフロー図

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

Add(key, value) ──────▶ ハッシュ計算 ──────▶ バケット位置
     │                       │
     │                       ▼
     │               変更パスコピー
     │                       │
     ▼                       ▼
既存ツリー ──────▶ 構造共有 ──────▶ 共有サブツリー
     │                       │
     │                       ▼
     │               新ノード作成
     │                       │
     ▼                       ▼
新コレクション ◀──────── 新ルート構築 ◀─────── 新バケット
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| ImmutableDictionary_2.cs | `src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableDictionary_2.cs` | ソース | イミュータブル辞書 |
| ImmutableList_1.cs | `src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableList_1.cs` | ソース | イミュータブルリスト |
| ImmutableHashSet_1.cs | `src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableHashSet.cs` | ソース | イミュータブルハッシュセット |
| ImmutableArray.cs | `src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableArray.cs` | ソース | イミュータブル配列 |
| ImmutableQueue_1.cs | `src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableQueue_1.cs` | ソース | イミュータブルキュー |
| ImmutableStack.cs | `src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableStack.cs` | ソース | イミュータブルスタック |
| ImmutableSortedDictionary_2.cs | `src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableSortedDictionary.cs` | ソース | イミュータブルソート済み辞書 |
| SortedInt32KeyNode.cs | `src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/SortedInt32KeyNode.cs` | ソース | 内部ツリーノード |
| ImmutableDictionary_2.HashBucket.cs | `src/libraries/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableDictionary_2.HashBucket.cs` | ソース | ハッシュバケット |
