# 機能設計書 64-トポロジカルソート

## 概要

本ドキュメントは、Tailwind CSSにおけるトポロジカルソートユーティリティ関数の機能設計を記述する。有向グラフの依存関係に基づいてノードを順序付けし、依存先が依存元より先に処理されるようソートする。カスタムバリアントの登録順序決定に使用される。

### 本機能の処理概要

**業務上の目的・背景**：Tailwind CSSの`@custom-variant`ディレクティブでは、カスタムバリアント内で`@variant`ディレクティブを使用して他のカスタムバリアントを参照することができる。この場合、参照先のバリアントが先に登録されている必要がある。トポロジカルソートにより、依存関係を解決し正しい登録順序を決定する。また、循環依存を検出してエラーとして報告する機能も備える。

**機能の利用シーン**：`packages/tailwindcss/src/index.ts`のcompile/compileAst処理内で、`@custom-variant`ディレクティブ間の依存関係を解決するために使用される。カスタムバリアントが他のカスタムバリアントを`@variant`で参照している場合に、正しい登録順序を決定する。

**主要な処理内容**：
1. 有向グラフ（隣接リスト表現：`Map<Key, Set<Key>>`）を入力として受け取る
2. 深さ優先探索（DFS）によりグラフを走査する
3. 訪問済みノード（seen）と処理中ノード（wip: work-in-progress）を追跡する
4. 処理中ノードへの再訪問で循環依存を検出し、コールバックで通知する
5. DFS後行順序（post-order）でソート結果を構築する

**関連システム・外部連携**：外部システムとの連携はない。Tailwind CSS内部のグラフ処理ユーティリティとして機能する。

**権限による制御**：権限による制御はない。

## 関連画面

本機能は内部ユーティリティ関数であり、画面に直接関連しない。

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | 補助機能 | カスタムバリアントの依存関係解決として間接的にCSS生成に寄与 |

## 機能種別

計算処理（グラフアルゴリズム・ソート）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| graph | Map<Key, Set<Key>> | Yes | 有向グラフの隣接リスト表現。キーはノード、値は依存先ノードの集合 | 空のMapも許容 |
| options | { onCircularDependency: (path: Key[], start: Key) => void } | Yes | 循環依存検出時のコールバックオブジェクト | コールバック関数を含むオブジェクト |

### 入力データソース

呼び出し元モジュール（index.ts）から、`@custom-variant`間の依存関係グラフが渡される。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| sorted | Key[] | トポロジカル順序でソートされたノードの配列。依存先が依存元より先に出現する |

### 出力先

呼び出し元への戻り値として返却される。

## 処理フロー

### 処理シーケンス

```
1. 初期化
   └─ seen = new Set(), wip = new Set(), sorted = []
2. グラフの全ノードに対してvisit関数を呼び出し
   └─ graph.keys() をイテレート
3. visit関数（深さ優先探索）
   ├─ 3a. グラフにノードが存在しない場合 → return
   ├─ 3b. seen（訪問済み）の場合 → return
   ├─ 3c. wip（処理中）の場合 → 循環依存検出、onCircularDependencyコールバック呼び出し
   ├─ 3d. wipにノードを追加
   ├─ 3e. ノードの全依存先に対してvisitを再帰呼び出し（パスを記録）
   ├─ 3f. seenにノードを追加、wipからノードを削除
   └─ 3g. sortedにノードを追加（後行順序）
4. sortedを返却
```

### フローチャート

```mermaid
flowchart TD
    A[開始: graph, options] --> B[初期化: seen, wip, sorted]
    B --> C[graph.keys をイテレート]
    C --> D[visit node]
    D --> E{graph.has node?}
    E -->|No| F[return]
    E -->|Yes| G{seen.has node?}
    G -->|Yes| F
    G -->|No| H{wip.has node?}
    H -->|Yes| I[onCircularDependency コールバック]
    H -->|No| J[wip.add node]
    I --> J
    J --> K[依存先を再帰的にvisit]
    K --> L[seen.add node]
    L --> M[wip.delete node]
    M --> N[sorted.push node]
    N --> O{次のノードあり?}
    O -->|Yes| D
    O -->|No| P[return sorted]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-64-01 | 依存順序保証 | 依存先ノードは依存元ノードより先にソート結果に出現する | 常時 |
| BR-64-02 | 循環依存検出 | 処理中(wip)のノードへの再訪問で循環依存を検出する | wip集合にノードが存在する場合 |
| BR-64-03 | 循環依存通知 | 循環依存検出時にonCircularDependencyコールバックを呼び出し、パスと開始ノードを通知する | 循環依存検出時 |
| BR-64-04 | 冪等性 | 既に訪問済み(seen)のノードは再処理しない | seen集合にノードが存在する場合 |
| BR-64-05 | グラフ外ノード無視 | グラフに存在しないノードへの参照は無視する | graph.has(node)がfalseの場合 |

### 計算ロジック

DFS後行順序（post-order）によるトポロジカルソート。ノードの全依存先を再帰的に処理した後にそのノードをソート結果に追加することで、依存関係の順序が保証される。

循環依存の検出は、wip（Work-In-Progress）集合を使用。DFS開始時にwipに追加し、全依存先の処理完了後にwipから削除する。wip内のノードへの再訪問は循環を意味する。

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

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

データベース操作はない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | 循環依存 | グラフに循環が存在する場合 | onCircularDependencyコールバックが呼び出される。index.tsではErrorをスローする |

### リトライ仕様

リトライ処理はない。

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

トランザクション管理はない。

## パフォーマンス要件

- O(V + E)の計算量（V: ノード数、E: エッジ数）
- SeenとWipにSetを使用しO(1)の探索

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

セキュリティ上の考慮事項はない。

## 備考

- TypeScriptジェネリクスにより任意のキー型に対応（Key型パラメータ）
- 実際の利用ではKeyはstring型（カスタムバリアント名）
- 循環依存検出時、index.tsではCSS構文を含むエラーメッセージを生成してスローする

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | topological-sort.ts | `packages/tailwindcss/src/utils/topological-sort.ts` | **1-4行目**: 関数シグネチャ。`Map<Key, Set<Key>>`型のグラフとonCircularDependencyコールバックを受け取る |

**読解のコツ**: TypeScriptのジェネリクス`<Key>`により、任意のキー型に対応する汎用的なトポロジカルソートとなっている。実際にはstring型で使用される。

#### Step 2: エントリーポイントを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | topological-sort.ts | `packages/tailwindcss/src/utils/topological-sort.ts` | **1-36行目**: topologicalSort関数の全体実装 |

**主要処理フロー**:
1. **5-6行目**: seen（訪問済み）とwip（処理中）のSet初期化
2. **8行目**: sorted配列の初期化
3. **10-29行目**: visit関数（再帰的DFS）
   - **11行目**: グラフにノードが存在しない場合return
   - **12行目**: 訪問済みの場合return
   - **15行目**: wip内のノードへの再訪問で循環依存コールバック
   - **17行目**: wipにノードを追加
   - **19-23行目**: 依存先を再帰的にvisit（パスを記録・復元）
   - **25-26行目**: seenに追加、wipから削除
   - **28行目**: sortedにノードを追加（後行順序）
4. **31-33行目**: グラフの全ノードに対してvisitを呼び出し
5. **35行目**: sorted配列を返却

#### Step 3: 利用箇所を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | index.ts | `packages/tailwindcss/src/index.ts` | **629-643行目**: topologicalSortの呼び出し。@custom-variant間の依存関係をソートし、循環依存時にErrorをスロー |

**主要処理フロー**:
- **629行目**: topologicalSort(customVariantDependencies, {...}) の呼び出し
- **630-639行目**: onCircularDependencyコールバック。CSS構文を含むエラーメッセージを生成
- **642行目**: ソート結果の各バリアントに対してdesignSystem.variantsに登録

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

```
index.ts (compileAst)
    │
    └─ topologicalSort(customVariantDependencies, options)
           │
           ├─ visit(node, path)  [再帰]
           │      ├─ graph.has(node) チェック
           │      ├─ seen.has(node) チェック
           │      ├─ wip.has(node) → 循環依存検出
           │      │      └─ options.onCircularDependency(path, start)
           │      │             └─ throw new Error(...)
           │      └─ 依存先ノードへのvisit再帰呼び出し
           │
           └─ return sorted[]
                  │
                  └─ customVariants.get(variant)?.(designSystem)
                         └─ バリアント登録処理
```

### データフロー図

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

customVariantDependencies
(Map<string, Set<string>>)
    │
    └───────────────────▶ topologicalSort(graph, options)
                                │
                                ├─ DFS走査
                                ├─ 循環依存チェック
                                └─ 後行順序で結果構築            ───▶ string[] sorted
                                                                        │
                                                                        └─ バリアント登録順序
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| topological-sort.ts | `packages/tailwindcss/src/utils/topological-sort.ts` | ソース | トポロジカルソート関数の実装 |
| index.ts | `packages/tailwindcss/src/index.ts` | ソース | カスタムバリアントの依存関係解決でtopologicalSortを利用 |
