# 機能設計書 86-非同期キュー

## 概要

本ドキュメントは、webpackにおける非同期キュー（AsyncQueue）機能の設計を記述する。並列度制御付きの非同期タスク実行キューを提供し、モジュールの解析・ビルド・コード生成等のコンパイルパイプラインにおける非同期処理の実行管理を行う。親子キュー間の優先度制御、キーベースの重複排除、フックシステムによる拡張性を備える。

### 本機能の処理概要

AsyncQueueは、指定された並列度でアイテムを非同期処理するためのジェネリックなキューデータ構造である。

**業務上の目的・背景**：webpackのコンパイルプロセスでは、多数のモジュールの解析・ビルド・コード生成を非同期に並列処理する必要がある。無制限に並列実行するとメモリ消費が爆発し、逆に直列処理ではビルド時間が長くなる。AsyncQueueは適切な並列度制御を提供し、キーベースの重複排除（同一モジュールの重複処理防止）、親子キュー間の優先度（ルートキューが子キューより優先）、完了通知等の機能を統合的に提供する。

**機能の利用シーン**：
- Compilation内でのモジュール処理キュー（factorizeQueue、buildQueue、codeGenerationQueue等）
- モジュールファクトリによるモジュール生成の並列制御
- キャッシュとの連携（アイテムの処理結果をキャッシュし、再処理を回避）

**主要な処理内容**：
1. `add(item, callback)`: アイテムをキューに追加。キーベースで重複検出し、既に処理済みならキャッシュ結果を返し、処理中なら追加コールバックを登録
2. `invalidate(item)`: アイテムのキャッシュを無効化し、キューから削除
3. `waitFor(item, callback)`: 既に開始されたアイテムの完了を待機
4. `stop()`: キューを停止し、未処理アイテムにエラーを返す
5. `increaseParallelism() / decreaseParallelism()`: 実行時に並列度を動的調整
6. `isProcessing(item) / isQueued(item) / isDone(item)`: アイテムの状態照会
7. `_ensureProcessing()`: setImmediateでスケジュールされ、並列度の空きに応じてキューからアイテムを取り出し処理開始
8. `_startProcessing(entry)`: beforeStartフック発火 → processor実行 → startedフック発火
9. `_handleResult(entry, err, result)`: resultフック発火 → コールバック通知 → 次のアイテム処理スケジュール
10. 親子キュー関係: 親キューが優先的にアイテムを処理し、空きがあれば子キューのアイテムを処理

**関連システム・外部連携**：tapableライブラリ（AsyncSeriesHook、SyncHook）、ArrayQueueデータ構造

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

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 本機能に関連する画面はなし |

## 機能種別

データ連携・非同期処理制御（並列度制御付き非同期タスクキュー）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| name | string | No | キュー名（デバッグ・エラーメッセージ用） | - |
| parallelism | number | No | 最大並列数（デフォルト: 1） | 正の整数 |
| context | string | No | 実行コンテキスト（デフォルト: "normal"） | - |
| parent | AsyncQueue | No | 親キュー。並列度を共有し、親が優先 | - |
| getKey | function | No | アイテムからキーを抽出する関数。デフォルトはアイテム自体 | - |
| processor | function | Yes | アイテムを処理する非同期関数 (item, callback) => void | - |

### 入力データソース

- Compilationが生成するモジュール処理パイプライン
- モジュールファクトリの処理結果

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| result | R | processor関数が返す処理結果 |
| error | WebpackError \| null | 処理中に発生したエラー |
| 状態 | QUEUED \| PROCESSING \| DONE | アイテムの処理状態 |

### 出力先

add()のコールバック関数に(error, result)として通知される。

## 処理フロー

### 処理シーケンス

```
1. add(item, callback)
   ├─ _stopped === true → callback(WebpackError) で即エラー
   ├─ hooks.beforeAdd.callAsync(item) → エラー時はcallback(error)
   ├─ key = getKey(item)
   ├─ entries.get(key) でキャッシュ参照
   │   ├─ DONE_STATE → 即座にcallback(error, result)を呼び出す（inHandleResult > 3ならnextTick）
   │   ├─ PROCESSING/QUEUED → callbacks配列にcallbackを追加（完了時に一括通知）
   │   └─ undefined → 新しいエントリを作成
   ├─ entries.set(key, newEntry)
   ├─ queued.enqueue(newEntry)
   ├─ root._needProcessing = true
   ├─ root._willEnsureProcessing === false → setImmediate(root._ensureProcessing)
   └─ hooks.added.call(item)

2. _ensureProcessing()
   ├─ activeTasks < parallelism の間、queued.dequeue()
   │   ├─ activeTasks++
   │   ├─ entry.state = PROCESSING_STATE
   │   └─ _startProcessing(entry)
   ├─ _willEnsureProcessing = false
   └─ 自キューが空の場合、子キューのアイテムも処理

3. _startProcessing(entry)
   ├─ hooks.beforeStart.callAsync(entry.item) → エラー時は_handleResult
   ├─ processor(entry.item, (error, result) => _handleResult(entry, error, result))
   └─ hooks.started.call(entry.item)

4. _handleResult(entry, err, result)
   ├─ hooks.result.callAsync(entry.item, err, result) → hookErrorがあればerrに合流
   ├─ entry.state = DONE_STATE
   ├─ entry.result = result, entry.error = error
   ├─ root._activeTasks--
   ├─ root._needProcessing → setImmediate(root._ensureProcessing)
   ├─ callback(error, result)
   └─ callbacks配列の全コールバックにも(error, result)を通知
```

### フローチャート

```mermaid
flowchart TD
    A[add item callback] --> B{stopped?}
    B -->|Yes| C[Error callback]
    B -->|No| D[beforeAdd hook]
    D --> E[getKey item]
    E --> F{entries.get key}
    F -->|DONE| G[即座に callback]
    F -->|PROCESSING/QUEUED| H[callbacks に追加]
    F -->|undefined| I[新エントリ作成]
    I --> J[queued.enqueue]
    J --> K[setImmediate ensureProcessing]

    K --> L[_ensureProcessing]
    L --> M{activeTasks < parallelism?}
    M -->|Yes| N[queued.dequeue]
    N --> O[_startProcessing]
    M -->|No| P[待機]

    O --> Q[beforeStart hook]
    Q --> R[processor 実行]
    R --> S[_handleResult]
    S --> T[result hook]
    T --> U[DONE_STATE 設定]
    U --> V[callback 通知]
    V --> W[activeTasks--]
    W --> X{needProcessing?}
    X -->|Yes| K
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-86-1 | キーベース重複排除 | 同一キーのアイテムが既にキュー内にある場合、新しいエントリは作成されず、既存エントリのコールバック配列に追加される | add呼び出し時 |
| BR-86-2 | 並列度制御 | activeTasks < parallelism の条件を満たす場合のみ新しいアイテムの処理を開始する | _ensureProcessing時 |
| BR-86-3 | 親キュー優先 | 親キューのアイテムが先に処理され、空きがある場合のみ子キューのアイテムが処理される | _ensureProcessing時 |
| BR-86-4 | 停止時エラー通知 | stop()後にadd()されたアイテムはWebpackError("Queue was stopped")でコールバックされる | _stopped === true時 |
| BR-86-5 | 再帰防止 | inHandleResult > 3の場合、コールバック呼び出しをprocess.nextTickで遅延し、深い再帰を防止する | _handleResult/add時 |
| BR-86-6 | setImmediateスケジューリング | _ensureProcessingはsetImmediateでスケジュールされ、I/Oイベントの処理を阻害しない | キューにアイテム追加時 |
| BR-86-7 | フックによる拡張 | beforeAdd、added、beforeStart、started、resultの5つのフックでキューの動作を拡張できる | 各処理段階 |
| BR-86-8 | 動的並列度調整 | increaseParallelism/decreaseParallelismで実行時に並列度を変更できる | 実行時 |

### 計算ロジック

- アイテム状態遷移: QUEUED_STATE(0) → PROCESSING_STATE(1) → DONE_STATE(2)
- 並列度判定: `this._activeTasks < this._parallelism` が真の間、キューからアイテムを取り出す
- 親子キューの並列度共有: すべての子キューは`this._root`（最上位の親キュー）の`_activeTasks`と`_parallelism`を共有する

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

本機能にデータベース操作は含まれない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | WebpackError | キューが停止（stop()済み）後にadd()された場合 | "Queue was stopped" エラーがコールバックに通知される |
| - | WebpackError | beforeAddフックでエラーが発生した場合 | makeWebpackErrorでラップされコールバックに通知される |
| - | WebpackError | beforeStartフックでエラーが発生した場合 | makeWebpackErrorでラップされ_handleResultに転送される |
| - | WebpackError | resultフックでエラーが発生した場合 | makeWebpackErrorでラップされ、元のエラーの代わりにコールバックに通知される |
| - | WebpackError | processor実行中に例外がthrowされた場合 | catch句で捕捉され_handleResultに転送される（ただしコールバック実行中の例外は再throw） |
| - | WebpackError | waitForで未開始アイテムを指定した場合 | "waitFor can only be called for an already started item" エラー |

### リトライ仕様

リトライ処理は組み込まれていない。エラー発生時はDONE_STATEに遷移し、エラーがコールバックに通知される。invalidate()でアイテムを無効化し、再度add()することで実質的なリトライが可能。

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

トランザクション処理は不要。ただし、_handleResult内でのコールバック通知は`inHandleResult`カウンタにより再帰深度を制御し、スタックオーバーフローを防止する。

## パフォーマンス要件

- ArrayQueueの効率的なenqueue/dequeue操作（2つの配列を使った反転方式）
- setImmediateによるI/O非阻害スケジューリング
- キーベースの重複排除によるモジュール重複処理の回避
- inHandleResultカウンタによるprocess.nextTick遅延で深い再帰チェーンを分散

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

特になし。

## 備考

- AsyncQueueは3つの型パラメータを持つ: T（アイテム型）、K（キー型）、R（結果型）
- Compilationでは複数のAsyncQueueインスタンスが使用される（factorize, addModule, build, codeGeneration等）
- ArrayQueueは2つの配列（_list, _listReversed）を使った効率的なキューデータ構造で、小さなリスト（16未満）ではshiftを使い、大きなリストでは配列反転方式でO(1)のdequeueを実現する

---

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

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

### 推奨読解順序

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

AsyncQueueEntryとArrayQueueの構造を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | AsyncQueue.js | `lib/util/AsyncQueue.js` | 13-16行目: 状態定数（QUEUED_STATE=0, PROCESSING_STATE=1, DONE_STATE=2） |
| 1-2 | AsyncQueue.js | `lib/util/AsyncQueue.js` | 32-50行目: AsyncQueueEntryクラス。item、state、callback、callbacks、result、errorを保持 |
| 1-3 | ArrayQueue.js | `lib/util/ArrayQueue.js` | 11-104行目: ArrayQueueクラス。_listと_listReversedの2配列によるキューデータ構造 |

**読解のコツ**: AsyncQueueEntryの`callbacks`（複数形）は、同一キーのアイテムが重複add()された場合の追加コールバックを蓄積する配列。`callback`（単数形）は最初のadd()のコールバック。両方ともDONE_STATE遷移時にundefinedにクリアされる。

#### Step 2: コンストラクタとフックシステムを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | AsyncQueue.js | `lib/util/AsyncQueue.js` | 67-119行目: AsyncQueueコンストラクタ。name、parallelism、processor、getKey、entries Map、queued ArrayQueue、親子関係、hooks |

**主要処理フロー**:
- **77-84行目**: 基本パラメータ初期化。parallelismデフォルト1、getKeyデフォルトはidentity関数
- **85-88行目**: _entries Map（キーベースの重複排除用）、_queued ArrayQueue
- **96-103行目**: 親子キュー関係の構築。`this._root = parent ? parent._root : this`で最上位のルートを参照
- **105-116行目**: 5つのフック定義（beforeAdd, added, beforeStart, started, result）

#### Step 3: add/invalidate/waitForを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | AsyncQueue.js | `lib/util/AsyncQueue.js` | 140-185行目: addメソッド。キーベース重複排除、状態チェック、キューイング |
| 3-2 | AsyncQueue.js | `lib/util/AsyncQueue.js` | 191-200行目: invalidateメソッド。エントリ削除とキューからの除去 |
| 3-3 | AsyncQueue.js | `lib/util/AsyncQueue.js` | 208-225行目: waitForメソッド。開始済みアイテムの完了待機 |

**主要処理フロー**:
- **140-185行目**: add
  - 141行目: stopped状態ならWebpackErrorでcallback
  - 142行目: beforeAddフック呼び出し
  - 149行目: getKey(item)でキー取得
  - 150行目: _entries.get(key)でキャッシュ参照
  - 152-158行目: DONE_STATE → 即座にコールバック（inHandleResult > 3ならnextTick遅延）
  - 159-163行目: PROCESSING/QUEUED → callbacks配列に追加
  - 166-183行目: 新規 → エントリ作成、キュー追加、setImmediateでスケジュール

#### Step 4: 処理実行ループを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | AsyncQueue.js | `lib/util/AsyncQueue.js` | 301-324行目: _ensureProcessingメソッド。並列度の空きに応じてキューからアイテムを取り出す |
| 4-2 | AsyncQueue.js | `lib/util/AsyncQueue.js` | 330-351行目: _startProcessingメソッド。processor実行とフック発火 |
| 4-3 | AsyncQueue.js | `lib/util/AsyncQueue.js` | 359-398行目: _handleResultメソッド。結果記録、コールバック通知、次処理スケジュール |

**主要処理フロー**:
- **301-324行目**: _ensureProcessing
  - 302-308行目: ルートキューのアイテムを並列度まで処理開始
  - 311-322行目: ルートキューが空なら子キューのアイテムも処理
  - 323行目: 全キュー空なら_needProcessing = false
- **330-351行目**: _startProcessing
  - 331行目: beforeStartフック
  - 341行目: processor(entry.item, callback)を呼び出し
  - 345-348行目: processor内での同期例外をcatchし、コールバック実行中の例外は再throw
  - 349行目: startedフック
- **359-398行目**: _handleResult
  - 360行目: resultフック
  - 367-371行目: DONE_STATE設定、callback/callbacks/result/errorの記録とクリア
  - 374-378行目: activeTasks減少、次処理スケジュール
  - 380-397行目: inHandleResult > 3ならnextTickでコールバック呼び出し

#### Step 5: 停止・並列度制御を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | AsyncQueue.js | `lib/util/AsyncQueue.js` | 230-245行目: stopメソッド。未処理アイテムをすべてエラーで完了させる |
| 5-2 | AsyncQueue.js | `lib/util/AsyncQueue.js` | 250-258行目: increaseParallelismメソッド。並列度を増加し再スケジュール |
| 5-3 | AsyncQueue.js | `lib/util/AsyncQueue.js` | 263-266行目: decreaseParallelismメソッド。並列度を減少 |
| 5-4 | AsyncQueue.js | `lib/util/AsyncQueue.js` | 401-408行目: clearメソッド。キューを完全にリセット |

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

```
AsyncQueue.add(item, callback)
    |
    +-- hooks.beforeAdd.callAsync(item)
    |
    +-- _getKey(item) → key
    |
    +-- _entries.get(key) → 重複チェック
    |   +-- [DONE] → callback(error, result)
    |   +-- [PROCESSING/QUEUED] → callbacks.push(callback)
    |   +-- [undefined] → new AsyncQueueEntry(item, callback)
    |
    +-- _queued.enqueue(newEntry)
    |
    +-- setImmediate(_ensureProcessing)  ← ルートキューにスケジュール
    |
    +-- hooks.added.call(item)

_ensureProcessing()
    |
    +-- [activeTasks < parallelism]
    |   +-- _queued.dequeue() → entry
    |   +-- _startProcessing(entry)
    |       +-- hooks.beforeStart.callAsync(entry.item)
    |       +-- _processor(entry.item, callback)
    |       +-- hooks.started.call(entry.item)
    |
    +-- [自キュー空] → 子キューのアイテムを処理
    |   +-- child._queued.dequeue() → entry
    |   +-- child._startProcessing(entry)
    |
    +-- _handleResult(entry, err, result)
        +-- hooks.result.callAsync(entry.item, err, result)
        +-- entry.state = DONE_STATE
        +-- callback(error, result)
        +-- callbacks[].forEach(cb => cb(error, result))
        +-- root._activeTasks--
        +-- setImmediate(root._ensureProcessing)  ← 次処理スケジュール
```

### データフロー図

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

item + callback       ------> add()                     -----> キュー登録 or キャッシュ結果
                               getKey() → 重複チェック

キューアイテム        ------> _ensureProcessing()       -----> _startProcessing()
                               並列度チェック                     processor 実行

processor結果         ------> _handleResult()           -----> callback(error, result)
(error, result)                DONE_STATE 記録                    callbacks[] 通知
                               activeTasks 更新                  次アイテム スケジュール
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| AsyncQueue.js | `lib/util/AsyncQueue.js` | ソース | 非同期キューのメインクラス |
| ArrayQueue.js | `lib/util/ArrayQueue.js` | ソース | 2配列方式のキューデータ構造。AsyncQueueの内部キューとして使用 |
| WebpackError.js | `lib/WebpackError.js` | ソース | エラークラス。キュー停止時等のエラー通知に使用 |
| HookWebpackError.js | `lib/HookWebpackError.js` | ソース | makeWebpackError関数。フックエラーのラップに使用 |
| Compilation.js | `lib/Compilation.js` | ソース | AsyncQueueの主要消費者。factorize/addModule/build/codeGeneration等のキューを管理 |
