# 機能設計書 10-チャンクグラフ構築

## 概要

本ドキュメントは、モジュール依存関係に基づきチャンクグラフを構築し、チャンク間の関係を管理する機能の設計を記述する。

### 本機能の処理概要

チャンクグラフ構築は、モジュールグラフ（依存関係グラフ）からチャンクグラフ（出力バンドル構造）を生成する機能である。ChunkGraphクラスがチャンクとモジュールの双方向マッピングを管理し、buildChunkGraph関数がモジュールグラフを走査してチャンクへのモジュール割り当てを決定する。

**業務上の目的・背景**：webpackは、エントリポイントから始まるモジュール依存関係ツリーを解析した後、実際にブラウザに配信するチャンク（JavaScriptファイル）を構成する必要がある。同期的に依存するモジュール群は同じチャンクにまとめ、動的import()による非同期依存は別チャンクとして分割することで、効率的なコード分割を実現する。チャンクグラフ構築は、この分割戦略の根幹を担う。

**機能の利用シーン**：Compilation.seal()処理内でbuildChunkGraph()が呼び出され、モジュールグラフからチャンクグラフを構築する。SplitChunksPlugin等の最適化プラグインは、構築されたチャンクグラフを基に、さらにチャンクの分割・統合を行う。

**主要な処理内容**：
1. ChunkGraphModule/ChunkGraphChunkによるチャンク-モジュール間の双方向マッピング管理
2. visitModules()によるモジュールグラフの走査とチャンクへのモジュール割り当て
3. BigIntビットマスクによる利用可能モジュール集合の高速管理
4. connectChunkGroups()によるチャンクグループ間の親子関係の確立
5. ランタイムモジュール、エントリモジュールの管理
6. モジュールハッシュ、ランタイム要件の追跡
7. チャンクの統合判定（canChunksBeIntegrated/integrateChunks）

**関連システム・外部連携**：Compilation（チャンクグラフ構築の呼び出し元）、ModuleGraph（入力となるモジュール依存関係グラフ）、SplitChunksPlugin（チャンク分割最適化）、ChunkGroup/Entrypoint（チャンクグループ管理）と連携する。

**権限による制御**：特になし。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| 1 | Page A (many-pages) | 補助機能 | 共有モジュールに基づくチャンクグラフの生成・管理 |
| 2 | Page B (many-pages) | 補助機能 | 共有モジュールに基づくチャンクグラフの生成・管理 |
| 3 | Page C (many-pages) | 補助機能 | 共有モジュールに基づくチャンクグラフの生成・管理 |
| 4 | Page D (many-pages) | 補助機能 | 共有モジュールに基づくチャンクグラフの生成・管理 |
| 5 | Page E (many-pages) | 補助機能 | 共有モジュールに基づくチャンクグラフの生成・管理 |
| 6 | Page F (many-pages) | 補助機能 | 共有モジュールに基づくチャンクグラフの生成・管理 |
| 8 | Page A (hybrid-routing) | 補助機能 | 動的チャンクを含むチャンクグラフの構築 |
| 9 | Page B (hybrid-routing) | 補助機能 | 動的チャンクを含むチャンクグラフの構築 |
| 14 | Page A (two-explicit-vendor-chunks) | 補助機能 | vendorチャンクとページチャンクの依存グラフ構築 |
| 15 | Page B (two-explicit-vendor-chunks) | 補助機能 | vendorチャンクとの依存グラフ構築 |
| 16 | Page C (two-explicit-vendor-chunks) | 補助機能 | vendorチャンクとの依存グラフ構築 |

## 機能種別

チャンク生成 / グラフ構築 / データ構造管理

## 入力仕様

### 入力パラメータ

**buildChunkGraph関数**

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| compilation | Compilation | Yes | コンパイルインスタンス（chunkGraph, moduleGraph, chunks等を含む） | - |
| inputEntrypointsAndModules | Map<Entrypoint, Module[]> | Yes | エントリポイントとそのモジュールのマッピング | - |

**ChunkGraphコンストラクタ**

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| moduleGraph | ModuleGraph | Yes | モジュールグラフ | - |
| hashFunction | HashFunction | No | ハッシュ関数（デフォルト: DEFAULTS.HASH_FUNCTION） | - |

### 入力データソース

- Compilation.seal()内で構築済みのモジュールグラフ（ModuleGraph）
- エントリポイント情報（Entrypoint + Module[]）

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| _modules | WeakMap<Module, ChunkGraphModule> | モジュールからチャンクグラフモジュール情報へのマッピング |
| _chunks | WeakMap<Chunk, ChunkGraphChunk> | チャンクからチャンクグラフチャンク情報へのマッピング |
| _blockChunkGroups | WeakMap<AsyncDependenciesBlock, ChunkGroup> | 非同期ブロックからチャンクグループへのマッピング |
| _runtimeIds | Map<string, RuntimeId> | ランタイム名からランタイムIDへのマッピング |

**ChunkGraphModule内部データ**

| 項目名 | 型 | 説明 |
|--------|-----|------|
| chunks | SortableSet<Chunk> | モジュールが含まれるチャンクの集合 |
| entryInChunks | Set<Chunk> \| undefined | エントリモジュールとしてのチャンク |
| runtimeInChunks | Set<Chunk> \| undefined | ランタイムモジュールとしてのチャンク |
| hashes | RuntimeSpecMap<ModuleHashInfo> \| undefined | ランタイム別のハッシュ情報 |
| id | ModuleId \| null | モジュールID |
| runtimeRequirements | RuntimeSpecMap<Set<string>> \| undefined | ランタイム要件 |

**ChunkGraphChunk内部データ**

| 項目名 | 型 | 説明 |
|--------|-----|------|
| modules | SortableSet<Module> | チャンクに含まれるモジュールの集合 |
| entryModules | Map<Module, Entrypoint> | エントリモジュールとそのEntrypoint |
| runtimeModules | SortableSet<RuntimeModule> | ランタイムモジュールの集合 |
| fullHashModules | Set<RuntimeModule> \| undefined | フルハッシュが必要なモジュール |
| dependentHashModules | Set<RuntimeModule> \| undefined | 依存ハッシュが必要なモジュール |
| runtimeRequirements | Set<string> \| undefined | チャンクのランタイム要件 |
| runtimeRequirementsInTree | Set<string> | ツリーのランタイム要件 |

### 出力先

- Compilation.chunkGraphとして保持される
- SplitChunksPlugin等の最適化プラグインが参照する
- コード生成フェーズで出力チャンクの構成に使用される

## 処理フロー

### 処理シーケンス

```
1. buildChunkGraph(compilation, inputEntrypointsAndModules) 呼び出し
   └─ 共有ステートの初期化（blockConnections, maskByChunk等）

2. PART ONE: visitModules()
   ├─ エントリポイントからキューを作成
   ├─ ChunkGroupInfoの初期化（runtime, minAvailableModules等）
   ├─ メインループ（while queue.length || queueConnect.size）
   │   ├─ processQueue(): キューからアイテムを取り出して処理
   │   │   ├─ ADD_AND_ENTER_ENTRY_MODULE: エントリモジュールの接続
   │   │   ├─ ADD_AND_ENTER_MODULE: モジュールをチャンクに接続
   │   │   ├─ ENTER_MODULE: pre/post order indexの設定
   │   │   ├─ PROCESS_BLOCK: ブロック内のモジュール処理
   │   │   │   └─ extractBlockModules()でブロック内のモジュール抽出
   │   │   ├─ PROCESS_ENTRY_BLOCK: エントリブロックの処理
   │   │   └─ LEAVE_MODULE: ポストオーダーインデックスの設定
   │   ├─ processChunkGroupsForCombining(): 子エントリポイントの結合
   │   ├─ processConnectQueue(): チャンクグループ間の接続
   │   ├─ processChunkGroupsForMerging(): 利用可能モジュールの集合マージ
   │   └─ processOutdatedChunkGroupInfo(): 変更されたチャンクグループの再処理
   └─ queueDelayed処理（非同期ブロック）

3. PART TWO: connectChunkGroups()
   ├─ 各ブロック接続について利用可能モジュールを確認
   ├─ 不要な接続をスキップ（全モジュールが親チャンクで利用可能な場合）
   └─ チャンクグループの親子関係を確立

4. ランタイム情報の伝播
   └─ 各チャンクにチャンクグループのランタイム情報をマージ

5. cleanup: cleanupUnconnectedGroups()
   └─ 親を持たない（接続されていない）チャンクグループを削除
```

### フローチャート

```mermaid
flowchart TD
    A[buildChunkGraph呼び出し] --> B[共有ステート初期化]
    B --> C[visitModules開始]
    C --> D[エントリポイントからキュー作成]
    D --> E{キュー非空 or queueConnect非空?}
    E -->|Yes| F[processQueue: モジュール走査]
    F --> G{chunkGroupsForCombining?}
    G -->|Yes| H[processChunkGroupsForCombining]
    G -->|No| I{queueConnect非空?}
    H --> I
    I -->|Yes| J[processConnectQueue]
    J --> K{chunkGroupsForMerging?}
    K -->|Yes| L[processChunkGroupsForMerging]
    K -->|No| M{outdatedChunkGroupInfo?}
    L --> M
    I -->|No| M
    M -->|Yes| N[processOutdatedChunkGroupInfo]
    M -->|No| O{queue空?}
    N --> E
    O -->|Yes, swap queueDelayed| E
    O -->|No| E
    E -->|No| P[connectChunkGroups]
    P --> Q[ランタイム情報の伝播]
    Q --> R[cleanupUnconnectedGroups]
    R --> S[チャンクグラフ構築完了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | BigIntビットマスク管理 | モジュールの利用可能性をBigIntのビットマスクで管理。各モジュールに序数を割り当て、ビットの設定/検査で集合演算を高速実行 | visitModules内 |
| BR-02 | 非同期ブロック処理の遅延 | 非同期ブロック（import()等）はqueueDelayedに積まれ、同期ブロックの処理が全て完了した後に処理される | PROCESS_BLOCK時にAsyncDependenciesBlock検出 |
| BR-03 | 利用可能モジュールのマージ | 子チャンクグループのminAvailableModulesは、全親のresultingAvailableModulesのビットAND（共通部分） | processChunkGroupsForMerging |
| BR-04 | チャンク統合可否判定 | preventIntegrationフラグ、ランタイムの有無、エントリモジュールの有無に基づき統合可否を判定 | canChunksBeIntegrated() |
| BR-05 | スキップと再処理 | 親チャンクで既に利用可能なモジュールはskippedItemsに記録し、minAvailableModulesの縮小時に再処理 | processOutdatedChunkGroupInfo |
| BR-06 | チャンク名の決定ルール | チャンク統合時、両方に名前がある場合は短い名前を優先。エントリモジュールを持つチャンクの名前を優先 | integrateChunks() |
| BR-07 | 不要チャンクグループの削除 | 親を持たないチャンクグループは不要と判定し、そのチャンクとチャンクグループを削除 | cleanupUnconnectedGroups |

### 計算ロジック

**チャンクサイズ計算（getChunkSize）**:
```
チャンクサイズ = chunkOverhead(デフォルト10000) + modulesSize * (initialチャンクなら entryChunkMultiplicator(デフォルト10) : 1)
```

**モジュール序数のビットマスク表現**:
```
mask |= BigInt(1) << BigInt(moduleOrdinal)
isInMask = BigInt.asUintN(1, mask >> BigInt(ordinal)) !== BigInt(0)
```

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

該当なし。

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

該当なし。

### テーブル別操作詳細

該当なし。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| AsyncDependencyToInitialChunkError | コンパイルエラー | 非同期依存が初期チャンクグループを参照した場合 | チャンク名の重複回避、構成の修正 |
| Module has no hash info | ランタイムエラー | モジュールハッシュ取得時にハッシュ情報が未設定 | ハッシュ設定処理の順序を確認 |
| No unique hash info entry | ランタイムエラー | 未指定ランタイムで複数のハッシュエントリが存在 | optimization.usedExports: "global"でオプトアウト可能 |

### リトライ仕様

該当なし。visitModulesのメインループは反復的に処理を行うが、これはリトライではなく、グラフ走査アルゴリズムの一部である。

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

該当なし。

## パフォーマンス要件

- BigIntビットマスクによるモジュール集合演算でO(1)の集合演算（AND/OR/テスト）を実現
- SortableSetのキャッシュ機構により、ソート済み配列やサイズ計算の結果をキャッシュ
- WeakMapベースのデータ構造により、不要になったチャンク/モジュールのGCを阻害しない
- extractBlockModulesでインデックスマップ（30要素超で生成）によりO(n)を維持
- moduleMemCachesによるブロックモジュール情報のメモリキャッシュ
- processBlockでの早期スキップ（既接続モジュール、利用可能モジュール）

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

特になし。

## 備考

- ChunkGraphは1969行の大規模クラスで、チャンク-モジュール関係管理の中核を担う
- buildChunkGraph.jsは1393行のアルゴリズムファイルで、6つのアクション種別（ADD_AND_ENTER_ENTRY_MODULE=0, ADD_AND_ENTER_MODULE=1, ENTER_MODULE=2, PROCESS_BLOCK=3, PROCESS_ENTRY_BLOCK=4, LEAVE_MODULE=5）で処理を制御する
- webpack 6で削除予定の後方互換用静的メソッド（getChunkGraphForModule, setChunkGraphForModule等）が存在
- ChunkGraphModule, ChunkGraphChunkはChunkGraphの内部補助クラスとしてモジュールスコープに定義

---

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

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

### 推奨読解順序

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

チャンクグラフの内部データ構造を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | ChunkGraph.js | `lib/ChunkGraph.js` | ModuleHashInfoクラス（66-77行目）でモジュールハッシュの構造を理解する |
| 1-2 | ChunkGraph.js | `lib/ChunkGraph.js` | ChunkGraphModuleクラス（215-234行目）でモジュール側の管理データを理解する |
| 1-3 | ChunkGraph.js | `lib/ChunkGraph.js` | ChunkGraphChunkクラス（239-260行目）でチャンク側の管理データを理解する |
| 1-4 | ChunkGraph.js | `lib/ChunkGraph.js` | ChunkGraphコンストラクタ（270-302行目）で4つのWeakMap/Mapを理解する |

**読解のコツ**: ChunkGraphは「チャンクとモジュールの多対多関係」を管理するクラスである。_modules（WeakMap<Module, ChunkGraphModule>）と_chunks（WeakMap<Chunk, ChunkGraphChunk>）が双方向インデックスとして機能する。

#### Step 2: 基本操作メソッドを理解する

チャンクとモジュールの接続・切断操作を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | ChunkGraph.js | `lib/ChunkGraph.js` | connectChunkAndModule()（368-373行目）で双方向接続を理解する |
| 2-2 | ChunkGraph.js | `lib/ChunkGraph.js` | disconnectChunkAndModule()（380-387行目）で切断処理を理解する |
| 2-3 | ChunkGraph.js | `lib/ChunkGraph.js` | replaceModule()（461-525行目）でモジュール置換の複雑さを理解する |
| 2-4 | ChunkGraph.js | `lib/ChunkGraph.js` | connectChunkAndEntryModule()（1107-1115行目）でエントリモジュール接続を理解する |

**主要メソッドのパターン**:
- **368-373行目**: connectChunkAndModule() - cgm.chunks.add(chunk) + cgc.modules.add(module)の双方向追加
- **380-387行目**: disconnectChunkAndModule() - 逆操作 + sourceTypesByModuleの整合性維持

#### Step 3: buildChunkGraphのアルゴリズムを理解する

モジュールグラフからチャンクグラフを構築するアルゴリズムを理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | buildChunkGraph.js | `lib/buildChunkGraph.js` | 型定義（26-71行目）でQueueItem, ChunkGroupInfoの構造を理解する |
| 3-2 | buildChunkGraph.js | `lib/buildChunkGraph.js` | BigIntビットマスク操作（73-82行目）でモジュール集合管理を理解する |
| 3-3 | buildChunkGraph.js | `lib/buildChunkGraph.js` | extractBlockModules()（109-237行目）でブロック内モジュール抽出を理解する |
| 3-4 | buildChunkGraph.js | `lib/buildChunkGraph.js` | visitModules()（249-1240行目）のメインループ構造を理解する |
| 3-5 | buildChunkGraph.js | `lib/buildChunkGraph.js` | buildChunkGraph()エントリポイント（1333-1392行目）で3段階処理を理解する |

**読解のコツ**: buildChunkGraph.jsはvisitModules()が大部分を占める。まずbuildChunkGraph()（1333行目）から読み始め、3段階（visitModules -> connectChunkGroups -> cleanup）の全体像を把握してから、visitModules内部のキュー処理を詳細に読むとよい。

#### Step 4: チャンク統合とクエリ操作を理解する

チャンクの統合判定やサイズ計算を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | ChunkGraph.js | `lib/ChunkGraph.js` | canChunksBeIntegrated()（983-1009行目）で統合可否判定を理解する |
| 4-2 | ChunkGraph.js | `lib/ChunkGraph.js` | integrateChunks()（1016-1072行目）でチャンク統合の実装を理解する |
| 4-3 | ChunkGraph.js | `lib/ChunkGraph.js` | getChunkSize()（936-949行目）でサイズ計算を理解する |
| 4-4 | ChunkGraph.js | `lib/ChunkGraph.js` | getModuleGraphHash系メソッド（1652-1836行目）でハッシュ計算を理解する |

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

```
Compilation.seal()
    │
    └─ buildChunkGraph(compilation, inputEntrypointsAndModules)
           │
           ├─ visitModules(logger, compilation, ...)
           │      │
           │      ├─ extractBlockModules(module, moduleGraph, runtime, blockModulesMap)
           │      │      └─ moduleGraph.getOutgoingConnections(module)
           │      │
           │      ├─ processQueue()  [メインループ]
           │      │      ├─ ADD_AND_ENTER_ENTRY_MODULE
           │      │      │      └─ chunkGraph.connectChunkAndEntryModule()
           │      │      ├─ ADD_AND_ENTER_MODULE
           │      │      │      └─ chunkGraph.connectChunkAndModule()
           │      │      ├─ ENTER_MODULE
           │      │      │      └─ chunkGroup.setModulePreOrderIndex()
           │      │      ├─ PROCESS_BLOCK → processBlock()
           │      │      │      ├─ getBlockModules(block, runtime)
           │      │      │      └─ iteratorBlock(b)  [非同期ブロック処理]
           │      │      │             ├─ compilation.addAsyncEntrypoint() / addChunkInGroup()
           │      │      │             └─ chunkGraph.connectBlockAndChunkGroup()
           │      │      ├─ PROCESS_ENTRY_BLOCK → processEntryBlock()
           │      │      └─ LEAVE_MODULE
           │      │             └─ chunkGroup.setModulePostOrderIndex()
           │      │
           │      ├─ processChunkGroupsForCombining()
           │      │      └─ calculateResultingAvailableModules()
           │      │
           │      ├─ processConnectQueue()
           │      │      └─ calculateResultingAvailableModules()
           │      │
           │      ├─ processChunkGroupsForMerging()
           │      │      └─ minAvailableModules &= availableModules [BigInt AND]
           │      │
           │      └─ processOutdatedChunkGroupInfo()
           │             └─ [skippedItems/skippedModuleConnections再処理]
           │
           ├─ connectChunkGroups(compilation, blocksWithNestedBlocks, blockConnections, maskByChunk)
           │      ├─ areModulesAvailable()  [BigInt AND比較]
           │      ├─ chunkGraph.connectBlockAndChunkGroup()
           │      └─ connectChunkGroupParentAndChild()
           │
           └─ cleanupUnconnectedGroups(compilation, allCreatedChunkGroups)
                  ├─ chunkGraph.disconnectChunk()
                  └─ chunkGraph.disconnectChunkGroup()
```

### データフロー図

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

ModuleGraph ────────────▶ buildChunkGraph()
(モジュール依存関係)              │
                          PART 1: visitModules()
Entrypoints ──────────▶  ├─ エントリポイントモジュールをキューに投入
+ Modules                 ├─ BigIntマスクでモジュール集合を管理
                          ├─ processQueue()
                          │   ├─ 同期依存 → 同じチャンクに追加 ──────▶ ChunkGraph._modules
                          │   │                                        (Module→Chunks マッピング)
                          │   └─ 非同期依存 → 新チャンク生成 ────────▶ ChunkGraph._chunks
                          │                                            (Chunk→Modules マッピング)
                          ├─ processConnectQueue()
                          │   └─ 利用可能モジュール計算 ─────────────▶ ChunkGroupInfo.minAvailableModules
                          └─ processOutdatedChunkGroupInfo()
                              └─ スキップモジュールの再処理

                          PART 2: connectChunkGroups()
                          ├─ ブロック-チャンクグループ接続 ──────────▶ ChunkGraph._blockChunkGroups
                          └─ 親子チャンクグループ接続 ────────────────▶ ChunkGroup.parents/children

                          PART 3: cleanup
                          └─ 不要チャンクグループ削除 ────────────────▶ Compilation.chunks更新

                                                                     ▼
                                                              SplitChunksPlugin
                                                              (さらにチャンク分割・統合)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| ChunkGraph.js | `lib/ChunkGraph.js` | ソース | チャンク-モジュール関係管理クラス（1969行） |
| buildChunkGraph.js | `lib/buildChunkGraph.js` | ソース | モジュールグラフからチャンクグラフを構築するアルゴリズム（1393行） |
| Compilation.js | `lib/Compilation.js` | ソース | buildChunkGraphの呼び出し元（seal()内） |
| Chunk.js | `lib/Chunk.js` | ソース | チャンクデータクラス |
| ChunkGroup.js | `lib/ChunkGroup.js` | ソース | チャンクグループ管理 |
| Entrypoint.js | `lib/Entrypoint.js` | ソース | エントリポイント（ChunkGroupの派生） |
| ModuleGraph.js | `lib/ModuleGraph.js` | ソース | 入力となるモジュール依存関係グラフ |
| ModuleGraphConnection.js | `lib/ModuleGraphConnection.js` | ソース | モジュール間の接続情報 |
| AsyncDependenciesBlock.js | `lib/AsyncDependenciesBlock.js` | ソース | 非同期依存ブロック（import()等） |
| GraphHelpers.js | `lib/GraphHelpers.js` | ソース | connectChunkGroupParentAndChild等のヘルパー |
| SortableSet.js | `lib/util/SortableSet.js` | ソース | キャッシュ付きソート可能Set |
| runtime.js | `lib/util/runtime.js` | ソース | RuntimeSpecMap/Set、mergeRuntime等のランタイムユーティリティ |
| findGraphRoots.js | `lib/util/findGraphRoots.js` | ソース | グラフルート検出ユーティリティ |
| comparators.js | `lib/util/comparators.js` | ソース | モジュール/チャンク比較関数 |
| AsyncDependencyToInitialChunkError.js | `lib/AsyncDependencyToInitialChunkError.js` | ソース | 非同期依存の初期チャンクエラー |
