# 機能設計書 48-InternPool

## 概要

本ドキュメントは、Zigコンパイラのインターン化システム（InternPool）について記述する。InternPoolは型、値、文字列などのデータを一意に管理し、効率的なメモリ使用と高速な比較を実現する中核データ構造である。

### 本機能の処理概要

InternPoolは、コンパイラ全体で使用される型と値をインターン化（一意化）して管理する機能である。同じ型や値は同一のインデックスで表現され、比較はインデックスの比較で済むため高速である。

**業務上の目的・背景**：コンパイラでは型や値の比較が頻繁に行われる。構造的な比較は計算コストが高いが、インターン化により同一データは同一インデックスとなるため、比較がO(1)で完了する。また、重複データを排除することでメモリ使用量も削減される。500KB超の大規模モジュールであり、コンパイラの効率性を支える基盤技術である。

**機能の利用シーン**：
- 型定義のインターン化（同じ型は同じIndex）
- 値定義のインターン化（コンパイル時定数）
- 文字列のインターン化（識別子、エラーメッセージ等）
- マルチスレッドコンパイルでの共有データ管理
- インクリメンタルコンパイルの依存関係追跡

**主要な処理内容**：
1. 型のインターン化（getOrPutKey）
2. 値のインターン化
3. 文字列のインターン化（NullTerminatedString）
4. ZIR命令の追跡（TrackedInst）
5. Nav（Named Value）の管理
6. 依存関係グラフの管理

**関連システム・外部連携**：
- Type/Value：インデックスのラッパー
- Sema：型・値の登録
- Zcu：コンパイルユニット管理

**権限による制御**：特になし（コンパイラ内部処理）

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | InternPoolは直接的な画面を持たない内部機能 |

## 機能種別

データ管理 / インターン化 / コンパイラ内部処理

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| key | Key | Yes | インターン対象のデータ | 有効なKey構造 |
| tid | PerThread.Id | Yes | スレッドID | 有効なスレッドID |

### 入力データソース

- Semaからの型・値データ
- AstGenからの文字列データ

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| index | Index | インターン化されたデータのインデックス |
| string | NullTerminatedString | インターン化された文字列 |

### 出力先

Type、Value、Sema等のコンポーネント

## 処理フロー

### 処理シーケンス

```
1. データのハッシュ計算
   └─ Keyからハッシュ値を算出
2. シャードの決定
   └─ ハッシュ値からシャードを選択
3. 既存エントリの検索
   └─ ハッシュテーブルで検索
4. 新規登録（未存在の場合）
   └─ ローカルストレージに追加
5. インデックスの返却
   └─ 既存または新規のインデックス
```

### フローチャート

```mermaid
flowchart TD
    A[Key入力] --> B[ハッシュ計算]
    B --> C[シャード選択]
    C --> D{既存エントリ?}
    D -->|Yes| E[既存Index返却]
    D -->|No| F[ロック取得]
    F --> G[再検索]
    G --> H{既存?}
    H -->|Yes| I[ロック解放]
    I --> E
    H -->|No| J[新規登録]
    J --> K[Index生成]
    K --> L[ロック解放]
    L --> M[新規Index返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-48-01 | 一意性保証 | 同一データは同一Index | 全インターン操作 |
| BR-48-02 | スレッドセーフ | マルチスレッドアクセス対応 | 並列コンパイル時 |
| BR-48-03 | シャード分割 | 2のべき乗数のシャードで並列性向上 | ハッシュテーブルアクセス時 |
| BR-48-04 | ローカルストレージ | スレッドごとのローカルストレージ | データ追加時 |

### 計算ロジック

**インデックス構造**:
- 上位ビット: スレッドID（tid）
- 下位ビット: ローカルインデックス
- tid_shift_30/31/32で位置を調整

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

該当なし（メモリ上での処理）

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| OutOfMemory | メモリエラー | メモリ不足 | メモリ解放 |
| InvalidIndex | インデックスエラー | 不正なインデックス | 正しいインデックス使用 |

### リトライ仕様

該当なし

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

該当なし

## パフォーマンス要件

- 比較はO(1)（インデックス比較）
- 検索はO(1)平均（ハッシュテーブル）
- マルチスレッドでスケーラブル

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

特になし（コンパイラ内部処理）

## 備考

InternPool.zigは500KB超のソースコードであり、コンパイラの最大級モジュールの一つ。

---

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

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

### 推奨読解順序

#### Step 1: 基本構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | InternPool.zig | `src/InternPool.zig` | ファイル先頭コメント（1-3行目） |
| 1-2 | InternPool.zig | `src/InternPool.zig` | InternPool構造体フィールド（21-34行目） |

**読解のコツ**:
- `locals: []Local` - スレッドごとのローカルストレージ
- `shards: []Shard` - ハッシュテーブルシャード
- `global_error_set` - グローバルエラーセット
- `tid_width`, `tid_shift_*` - スレッドID関連パラメータ

**主要処理フロー**:
1. **1-3行目**: InternPoolの役割説明
2. **21行目**: localsフィールド
3. **24行目**: shardsフィールド
4. **25行目**: global_error_set

#### Step 2: 依存関係管理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | InternPool.zig | `src/InternPool.zig` | 依存関係フィールド（36-73行目） |

**読解のコツ**:
- `src_hash_deps` - ソースハッシュへの依存
- `nav_val_deps` - Nav値への依存
- `interned_deps` - インターン値への依存
- 増分コンパイルの無効化追跡に使用

**主要処理フロー**:
- **36-41行目**: src_hash_deps説明
- **42-45行目**: nav_val_deps, nav_ty_deps
- **49-53行目**: interned_deps

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | InternPool.zig | `src/InternPool.zig` | TrackedInst構造体（122-214行目） |

**読解のコツ**:
- ZIR命令をコンパイル全体で追跡
- MaybeLostで増分更新時の「lost」を表現
- Index.resolveでZIR命令を解決

**主要処理フロー**:
- **126-129行目**: TrackedInst構造体定義
- **134-155行目**: MaybeLost構造体
- **157-213行目**: Index構造体とメソッド

#### Step 4: trackZir関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | InternPool.zig | `src/InternPool.zig` | trackZir関数（216-300行目） |

**読解のコツ**:
- ZIR命令をInternPoolに登録
- ハッシュベースの重複チェック
- ロックによるスレッドセーフ実装

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

```
Sema.zig / AstGen.zig
    │
    ▼
InternPool ★本機能
    │
    ├─ getOrPutKey() - 型/値のインターン化
    │      │
    │      ├─ ハッシュ計算
    │      ├─ シャード検索
    │      └─ 新規登録
    │
    ├─ trackZir() - ZIR命令追跡
    │
    ├─ getOrPutTrailingString() - 文字列インターン化
    │
    └─ 依存関係管理
           ├─ src_hash_deps
           ├─ nav_val_deps
           └─ interned_deps
```

### データフロー図

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

Key(型/値)  ──────▶  InternPool  ──────▶  Index
                         │
                         ├─ ハッシュ計算
                         ├─ シャード選択
                         ├─ 重複チェック
                         └─ 登録
                              │
                              ▼
                         locals[]に格納
                         shards[]にマップ

文字列  ────────▶  getOrPutTrailingString  ▶  NullTerminatedString
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| InternPool.zig | `src/InternPool.zig` | ソース | インターン化の主実装（500KB超） |
| Type.zig | `src/Type.zig` | ソース | Index.ラッパー（型） |
| Value.zig | `src/Value.zig` | ソース | Indexラッパー（値） |
| Sema.zig | `src/Sema.zig` | ソース | 型・値登録クライアント |
| Zcu.zig | `src/Zcu.zig` | ソース | コンパイルユニット管理 |
