# 機能設計書 84-比較・ソートユーティリティ

## 概要

本ドキュメントは、webpackにおける比較・ソートユーティリティ機能の設計を記述する。モジュール、チャンク、ID、文字列等の比較関数群を提供し、ビルドプロセス全体で決定的（deterministic）な処理順序を保証する。WeakMapベースのキャッシュ機構により比較関数のパフォーマンスを最適化する。

### 本機能の処理概要

比較・ソートユーティリティは、webpackの内部データ構造（モジュール、チャンク、チャンクグループ、依存関係等）のソートに使用される標準的な比較関数群を提供するモジュールである。

**業務上の目的・背景**：webpackのビルド結果は決定的（同じ入力から常に同じ出力）であることが求められる。モジュールやチャンクの処理順序がビルドごとに変わると、出力ファイルの内容やハッシュ値が不安定になり、キャッシュの無効化やデプロイの問題が発生する。統一された比較関数群を提供し、すべての内部ソート処理で一貫した順序を保証する。

**機能の利用シーン**：
- モジュールIDによるモジュールのソート
- チャンクの自然順ソート
- 依存関係のソースオーダーソート
- 統計情報出力でのモジュール・チャンク一覧の並び替え
- コード生成時の決定的な出力順序の保証

**主要な処理内容**：
1. 基本比較関数: compareIds、compareNumbers、compareStrings、compareStringsNumeric
2. モジュール比較: compareModulesById、compareModulesByIdentifier、compareModulesByFullName等
3. チャンク比較: compareChunksById、compareChunksNatural、compareChunks
4. その他比較: compareLocations、compareChunkGroupsByIndex
5. 高階関数: compareSelect（セレクタ＋比較関数の合成）、concatComparators（比較関数の連結）
6. ユーティリティ: compareIterables（イテラブルの要素単位比較）、keepOriginalOrder（元の順序を保持する比較関数生成）
7. 依存関係ソート: sortWithSourceOrder（ソースオーダーに基づく依存関係のインプレースソート）
8. キャッシュ: TwoKeyWeakMap、WeakMapベースのキャッシュで比較関数のインスタンスを再利用
9. パラメータ化比較: createCachedParameterizedComparator（引数付き比較関数のキャッシュ付きファクトリ）

**関連システム・外部連携**：lib/ids/IdHelpers.js（getFullModuleName）、lib/util/runtime.js（compareRuntime）

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

## 関連画面

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

## 機能種別

ユーティリティ（比較関数・ソート関数の提供）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| a, b | Module / Chunk / string / number | Yes | 比較対象のオブジェクトペア | 型に依存 |
| chunkGraph | ChunkGraph | Yes（モジュール/チャンク比較時） | チャンクグラフインスタンス | - |
| moduleGraph | ModuleGraph | Yes（モジュール順序比較時） | モジュールグラフインスタンス | - |
| getter | Selector<T, R> | Yes（compareSelect） | 比較対象から値を抽出するセレクタ関数 | - |
| comparator | Comparator<T> | Yes | 比較関数 | -1, 0, 1 を返す関数 |

### 入力データソース

webpackの内部データ構造（ModuleGraph、ChunkGraph、Module、Chunk、ChunkGroup、Dependency等）

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 比較結果 | -1 \| 0 \| 1 | 標準の比較関数戻り値。aが小さい(-1)、等しい(0)、aが大きい(1) |
| Comparator関数 | function | 高階関数から返される新しい比較関数 |

### 出力先

呼び出し元（Array.sort等）に返却。

## 処理フロー

### 処理シーケンス

```
1. 基本比較関数
   ├─ compareIds(a, b): 型比較 → 値比較
   ├─ compareNumbers(a, b): 型比較 → 値比較
   ├─ compareStrings(a, b): 辞書順比較
   └─ compareStringsNumeric(a, b): 数値部分を数値として比較する自然順ソート

2. パラメータ化比較関数（WeakMapキャッシュ付き）
   ├─ compareModulesById(chunkGraph): chunkGraph引数をバインドした比較関数を返す
   ├─ compareModulesByIdOrIdentifier(chunkGraph): ID優先、同一ならidentifier
   ├─ compareModulesByFullName(compiler): コンテキスト相対の完全名で比較
   ├─ compareModulesByPostOrderIndexOrIdentifier(moduleGraph): 後順序 → identifier
   └─ compareModulesByPreOrderIndexOrIdentifier(moduleGraph): 前順序 → identifier

3. 高階関数
   ├─ compareSelect(getter, comparator): セレクタ+比較関数の合成
   ├─ concatComparators(c1, c2, ...cRest): 複数比較関数の連結
   ├─ compareIterables(elementComparator): イテラブルの要素単位比較
   └─ keepOriginalOrder(iterable): 元の順序を保持する比較関数生成

4. sortWithSourceOrder(dependencies, map, callback)
   └─ ソースオーダー付き依存関係をインプレースでソート
```

### フローチャート

```mermaid
flowchart TD
    A[比較関数呼び出し] --> B{関数タイプ}
    B -->|基本| C[compareIds / compareNumbers / compareStrings]
    B -->|パラメータ化| D[createCachedParameterizedComparator]
    D --> E{WeakMap キャッシュ?}
    E -->|Hit| F[キャッシュ済み比較関数を返す]
    E -->|Miss| G[新しい比較関数を生成しキャッシュ]
    B -->|高階| H[compareSelect / concatComparators]
    H --> I{TwoKeyWeakMap キャッシュ?}
    I -->|Hit| J[キャッシュ済み合成関数を返す]
    I -->|Miss| K[新しい合成関数を生成しキャッシュ]
    C --> L[比較結果 -1 / 0 / 1]
    F --> L
    G --> L
    J --> L
    K --> L
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-84-1 | 型優先比較 | compareIdsとcompareNumbersでは型(typeof)の比較を値の比較より優先する | 異なる型の値比較時 |
| BR-84-2 | 自然順ソート | compareStringsNumericは数字部分を数値として比較し、自然な並び順を実現する（例: "a2" < "a10"） | 文字列に数字が含まれる場合 |
| BR-84-3 | キャッシュ再利用 | 同じ引数で生成された比較関数はWeakMap/TwoKeyWeakMapから再利用される | 高階関数・パラメータ化関数の呼び出し時 |
| BR-84-4 | null/undefined安全 | compareSelectではgetterの結果がnullまたはundefinedの場合、非null値が優先される | セレクタ結果がnullish時 |
| BR-84-5 | ソースオーダー保持 | sortWithSourceOrderはHarmonyImportDependency等のインポート順序を保持するようソートする | 依存関係ソート時 |
| BR-84-6 | concatComparators再帰 | 3つ以上の比較関数が渡された場合、再帰的に2つずつ結合する | 可変長引数の場合 |

### 計算ロジック

- **compareStringsNumeric**: 文字列を1文字ずつ走査し、数字部分（0-9）を検出すると連続する数字を数値として解析して比較する。非数字部分は文字コードで比較する。数字セグメントが短い方が先に来る（例: "a" < "a1"は数字がないaがdigitセグメントより前）。
- **sortWithSourceOrder**: 依存関係リストからsourceOrderプロパティを持つもののみを抽出し、(main, sub)ペアでソートした後、元の位置に書き戻す。

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

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

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | - | 本機能固有のエラーは発生しない | - |

### リトライ仕様

リトライ処理は不要。

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

トランザクション処理は不要。

## パフォーマンス要件

- WeakMap/TwoKeyWeakMapベースのキャッシュにより、同じ引数での比較関数生成コストを排除する
- keepOriginalOrderはMapによるO(1)ルックアップで元の順序を保持する
- compareStringsNumericはO(n)の線形走査で自然順比較を実現する

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

特になし。

## 備考

- keepOriginalOrderのコメントに「Node.js 12以降ではstable sortが標準であるため不要」とあるが、後方互換のため残されている
- TwoKeyWeakMapはconcatComparatorsとcompareSelectのキャッシュに使用されるwebpack固有の2キーWeakMapデータ構造
- sortWithSourceOrderは https://github.com/webpack/webpack/pull/19686 で導入された

---

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

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

### 推奨読解順序

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

比較関数の型定義と補助データ構造を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | comparators.js | `lib/util/comparators.js` | 33-35行目: Comparator<T>型定義。(a: T, b: T) => -1 \| 0 \| 1 |
| 1-2 | comparators.js | `lib/util/comparators.js` | 38-44行目: RawParameterizedComparator/ParameterizedComparator型定義 |
| 1-3 | comparators.js | `lib/util/comparators.js` | 366-402行目: TwoKeyWeakMapクラス。2つのキーで値を管理するWeakMap |
| 1-4 | comparators.js | `lib/util/comparators.js` | 437-440行目: Selector<A, B>型定義。(input: A) => B | undefined | null |

**読解のコツ**: Comparator<T>は標準的なソート比較関数のシグネチャ。ParameterizedComparatorは「引数を受け取って比較関数を返す」高階関数であり、WeakMapでキャッシュされる。

#### Step 2: 基本比較関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | comparators.js | `lib/util/comparators.js` | 75-82行目: compareIds。型比較を優先する汎用ID比較 |
| 2-2 | comparators.js | `lib/util/comparators.js` | 196-203行目: compareNumbers。数値比較 |
| 2-3 | comparators.js | `lib/util/comparators.js` | 347-351行目: compareStrings。辞書順比較 |
| 2-4 | comparators.js | `lib/util/comparators.js` | 210-274行目: compareStringsNumeric。自然順ソート |

**主要処理フロー**:
- **75-82行目**: compareIds - typeof比較を先に行い、型が異なれば型名の辞書順で決定。同型なら値比較
- **210-274行目**: compareStringsNumeric - 文字列を1文字ずつ走査。数字部分（charCode 48-57）を検出すると連続数字を数値化して比較

#### Step 3: パラメータ化比較関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | comparators.js | `lib/util/comparators.js` | 53-68行目: createCachedParameterizedComparator。WeakMapキャッシュ付きファクトリ |
| 3-2 | comparators.js | `lib/util/comparators.js` | 185-189行目: compareModulesById。chunkGraph.getModuleIdで取得したIDを比較 |
| 3-3 | comparators.js | `lib/util/comparators.js` | 312-319行目: compareModulesByIdOrIdentifier。ID優先、同一ならidentifier |
| 3-4 | comparators.js | `lib/util/comparators.js` | 506-521行目: compareChunksNatural。名前→ランタイム→モジュール内容の複合比較 |

**主要処理フロー**:
- **53-68行目**: createCachedParameterizedComparator - WeakMapで引数(arg)をキーに比較関数をキャッシュ。fn.bind(null, arg)で部分適用
- **506-521行目**: compareChunksNatural - concatComparatorsで3つの比較を連結: name比較 → runtime比較 → モジュール内容比較

#### Step 4: 高階関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | comparators.js | `lib/util/comparators.js` | 452-476行目: compareSelect。TwoKeyWeakMapキャッシュ付き。getterで値抽出→comparatorで比較 |
| 4-2 | comparators.js | `lib/util/comparators.js` | 414-435行目: concatComparators。複数比較関数を順次実行し最初の非ゼロ結果を返す |
| 4-3 | comparators.js | `lib/util/comparators.js` | 89-114行目: compareIterables。イテレータの要素を1つずつ比較 |
| 4-4 | comparators.js | `lib/util/comparators.js` | 488-500行目: keepOriginalOrder。Mapに元の順序を記録し比較関数として使用 |

#### Step 5: sortWithSourceOrderを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | comparators.js | `lib/util/comparators.js` | 532-587行目: sortWithSourceOrder。依存関係をソースオーダーでインプレースソート |

**主要処理フロー**:
- **542-566行目**: 第1パス - 依存関係リストからsourceOrderを持つもののインデックスとオーダーを収集
- **572-577行目**: (main, sub)ペアでソート
- **580-586行目**: 第2パス - ソート済みの依存関係を元の位置に書き戻す

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

```
comparators.js (エクスポート関数群)
    |
    +-- 基本比較
    |   +-- compareIds(a, b)
    |   +-- compareNumbers(a, b)
    |   +-- compareStrings(a, b)
    |   +-- compareStringsNumeric(a, b)
    |   +-- compareLocations(a, b)
    |
    +-- パラメータ化比較（createCachedParameterizedComparator経由）
    |   +-- compareModulesById(chunkGraph) → Comparator<Module>
    |   +-- compareModulesByIdOrIdentifier(chunkGraph) → Comparator<Module>
    |   +-- compareModulesByFullName(compiler) → Comparator<Module>
    |   +-- compareModulesByPostOrderIndexOrIdentifier(moduleGraph) → Comparator<Module>
    |   +-- compareModulesByPreOrderIndexOrIdentifier(moduleGraph) → Comparator<Module>
    |   +-- compareChunks(chunkGraph) → Comparator<Chunk>
    |
    +-- 高階関数
    |   +-- compareSelect(getter, comparator) → Comparator<T>
    |   +-- concatComparators(c1, c2, ...cRest) → Comparator<T>
    |   +-- compareIterables(elementComparator) → Comparator<Iterable<T>>
    |   +-- keepOriginalOrder(iterable) → Comparator<T>
    |
    +-- ソート
        +-- sortWithSourceOrder(dependencies, map, callback)
```

### データフロー図

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

Module / Chunk / ID     ------> 基本比較関数               ----> -1 | 0 | 1
                                compareIds / compareNumbers

ChunkGraph / ModuleGraph ------> パラメータ化比較           ----> Comparator<T>
                                 createCachedParameterizedComparator
                                 WeakMap キャッシュ

Selector + Comparator   ------> compareSelect              ----> Comparator<T>
                                 TwoKeyWeakMap キャッシュ

Comparator[]            ------> concatComparators          ----> Comparator<T>
                                 連鎖実行

Dependency[]            ------> sortWithSourceOrder        ----> Dependency[] (sorted)
                                 sourceOrder 抽出 → ソート → 書き戻し
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| comparators.js | `lib/util/comparators.js` | ソース | 比較・ソートユーティリティの全関数を定義 |
| runtime.js | `lib/util/runtime.js` | ソース | compareRuntime関数を提供（compareChunksNaturalで使用） |
| IdHelpers.js | `lib/ids/IdHelpers.js` | ソース | getFullModuleName関数を提供（compareModulesByFullNameで使用） |
| ChunkGraph.js | `lib/ChunkGraph.js` | ソース | getModuleId/compareChunks等のメソッドを提供 |
| ModuleGraph.js | `lib/ModuleGraph.js` | ソース | getPreOrderIndex/getPostOrderIndex等のメソッドを提供 |
