# 機能設計書 37-@jest/diff-sequences

## 概要

本ドキュメントは、@jest/diff-sequencesパッケージの機能設計を記載する。@jest/diff-sequencesは、2つのシーケンスの最長共通部分列（LCS: Longest Common Subsequence）を計算するアルゴリズムを提供する。Eugene W. Myersの「An O(ND) Difference Algorithm and Its Variations」論文に基づく線形空間アルゴリズムを実装している。

### 本機能の処理概要

@jest/diff-sequencesは、2つのシーケンス間の最長共通部分列を効率的に計算し、その結果をコールバック関数で返す低レベルのアルゴリズムライブラリである。

**業務上の目的・背景**：差分表示（diff）を行うためには、2つのシーケンス間の共通部分と異なる部分を特定する必要がある。最長共通部分列アルゴリズムはこの問題を解決する基本的なアルゴリズムであり、git diffやテキストエディタの差分表示などで広く使用されている。jest-diffパッケージは行単位の差分計算にこのアルゴリズムを使用する。

**機能の利用シーン**：
- jest-diff: 行単位のテキスト差分計算
- スナップショットテストの差分検出
- 配列やリストの比較

**主要な処理内容**：
1. diffSequence関数: 2つのシーケンスの最長共通部分列を計算
2. 前方からの共通アイテムのカウント（countCommonItemsF）
3. 後方からの共通アイテムのカウント（countCommonItemsR）
4. 分割統治法による再帰的な部分列探索（divide, findSubsequences）
5. グラフの転置による最適化

**関連システム・外部連携**：
- jest-diff: 差分計算で使用
- 外部依存なし（純粋なTypeScript実装）

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

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 画面に直接関連しない低レベルアルゴリズムライブラリ |

## 機能種別

アルゴリズム / 計算処理

## 入力仕様

### 入力パラメータ

#### diffSequence関数

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| aLength | number | Yes | シーケンスAの長さ | 0以上の安全な整数 |
| bLength | number | Yes | シーケンスBの長さ | 0以上の安全な整数 |
| isCommon | IsCommon | Yes | 2つのインデックスのアイテムが等しいかを判定するコールバック | 関数であること |
| foundSubsequence | FoundSubsequence | Yes | 共通部分列を受け取るコールバック | 関数であること |

#### IsCommon型

| パラメータ名 | 型 | 説明 |
|-------------|-----|------|
| aIndex | number | シーケンスAのインデックス（0 <= aIndex < aLength） |
| bIndex | number | シーケンスBのインデックス（0 <= bIndex < bLength） |
| 戻り値 | boolean | アイテムが等しい場合true |

#### FoundSubsequence型

| パラメータ名 | 型 | 説明 |
|-------------|-----|------|
| nCommon | number | 共通アイテムの連続数（0 < nCommon） |
| aCommon | number | シーケンスAでの開始インデックス |
| bCommon | number | シーケンスBでの開始インデックス |

### 入力データソース

- jest-diff: 行配列の長さと行比較関数

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| - | void | foundSubsequenceコールバックで結果を返す |

### 出力先

foundSubsequenceコールバック関数への呼び出し

## 処理フロー

### 処理シーケンス

```
1. diffSequence関数の呼び出し
   └─ 引数のバリデーション
2. 前方からの共通アイテムをカウント
   └─ countCommonItemsF(0, aLength, 0, bLength, isCommon)
3. 前方共通部分を通知
   └─ foundSubsequence(nCommonF, 0, 0)
4. 後方からの共通アイテムをカウント
   └─ countCommonItemsR(aStart, aLength-1, bStart, bLength-1, isCommon)
5. トリム後の区間で共通部分列を探索
   └─ findSubsequences(...) を再帰呼び出し
6. 後方共通部分を通知
   └─ foundSubsequence(nCommonR, aEnd, bEnd)
```

### フローチャート

```mermaid
flowchart TD
    A[diffSequence開始] --> B[引数バリデーション]
    B --> C[前方から共通アイテムをカウント]
    C --> D{nCommonF > 0?}
    D -->|Yes| E[foundSubsequence呼び出し]
    D -->|No| F{全て共通?}
    E --> F
    F -->|Yes| G[終了]
    F -->|No| H[後方から共通アイテムをカウント]
    H --> I[トリム後の区間を計算]
    I --> J{区間が空でない?}
    J -->|Yes| K[findSubsequences再帰呼び出し]
    J -->|No| L{nCommonR > 0?}
    K --> L
    L -->|Yes| M[foundSubsequence呼び出し]
    L -->|No| G
    M --> G
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 長さバリデーション | aLength、bLengthは0以上の安全な整数であること | 関数呼び出し時 |
| BR-02 | コールバックバリデーション | isCommon、foundSubsequenceは関数であること | 関数呼び出し時 |
| BR-03 | グラフ転置最適化 | bLength < aLengthの場合、グラフを転置して処理 | findSubsequences内 |
| BR-04 | 分割統治法 | 中間点で分割して再帰的に処理 | divide関数 |

### 計算ロジック

**アルゴリズムの概要（Myers アルゴリズム）**：
- 編集グラフ上で前方パスと後方パスを交互に拡張
- パスがオーバーラップした点が中間変更点
- 中間変更点で区間を分割して再帰処理
- 時間計算量: O(ND) （Nは長さ、Dは差分数）
- 空間計算量: O(N) （線形空間バリエーション）

**対角線のインデックス計算**：
```typescript
// Forward diagonal
kF = 2 * iF - d
// Reverse diagonal
kR = d - 2 * iR
// Relationship
kF = kR - baDeltaLength
```

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

該当なし

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | TypeError | aLength/bLengthが数値でない | 正しい型の値を渡す |
| - | RangeError | aLength/bLengthが安全な整数でない | Number.isSafeIntegerの範囲内の値を使用 |
| - | RangeError | aLength/bLengthが負の値 | 0以上の値を使用 |
| - | TypeError | isCommon/foundSubsequenceが関数でない | 正しい型の関数を渡す |
| - | Error | パスがオーバーラップしない（内部エラー） | 通常発生しない |

### リトライ仕様

該当なし

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

該当なし

## パフォーマンス要件

- 時間計算量: O(ND) （Nはシーケンスの長さ、Dは差分の数）
- 空間計算量: O(N) （線形空間）
- 大きなシーケンスでも効率的に処理できること

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

該当なし（純粋な計算処理）

## 備考

- 参照論文: "An O(ND) Difference Algorithm and Its Variations" by Eugene W. Myers
- 線形空間バリエーションを実装（標準的なMyersアルゴリズムはO(N^2)空間）
- グラフの転置による最適化（常に短いシーケンスを長いシーケンスと比較）

---

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

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

### 推奨読解順序

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

まず、型定義とアルゴリズムの背景を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | index.ts | `packages/diff-sequences/src/index.ts` | 型定義とコメント（9-52行目） |

**読解のコツ**:
- **9-27行目**: Myersアルゴリズムの表記法の対応関係
- **28-52行目**: 編集グラフの概念説明
- **54-57行目**: IsCommon型（比較コールバック）
- **61-65行目**: FoundSubsequence型（結果コールバック）
- **79行目**: Indexes型（対角線上のインデックス配列）
- **83-101行目**: Division型（分割結果）

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | index.ts | `packages/diff-sequences/src/index.ts` | diffSequence関数（782-872行目） |

**主要処理フロー**:
1. **788-791行目**: 引数のバリデーション
2. **794行目**: 前方からの共通アイテムカウント
3. **796-798行目**: 前方共通部分の通知
4. **809-815行目**: 後方からの共通アイテムカウント
5. **826-865行目**: 区間が空でない場合のfindSubsequences呼び出し
6. **868-870行目**: 後方共通部分の通知

#### Step 3: 共通アイテムカウント関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | index.ts | `packages/diff-sequences/src/index.ts` | countCommonItemsF、countCommonItemsR（108-140行目） |

**主要処理フロー**:
- **108-122行目**: countCommonItemsF（前方から共通アイテムをカウント）
- **126-140行目**: countCommonItemsR（後方から共通アイテムをカウント）

#### Step 4: 分割統治法の核心を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | index.ts | `packages/diff-sequences/src/index.ts` | divide関数（530-644行目） |

**主要処理フロー**:
1. **541-556行目**: 初期化（対角線の計算、最大インデックスの設定）
2. **559-560行目**: 前方/後方パスの初期化
3. **562-591行目**: 長さの差が偶数の場合の処理
4. **592-638行目**: 長さの差が奇数の場合の処理
5. **641-643行目**: オーバーラップしない場合のエラー

#### Step 5: パス拡張関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | index.ts | `packages/diff-sequences/src/index.ts` | extendPathsF、extendPathsR（144-252行目） |

**主要処理フロー**:
- **144-193行目**: extendPathsF（前方パスの拡張）
- **197-252行目**: extendPathsR（後方パスの拡張）

#### Step 6: オーバーラップ検出関数を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 6-1 | index.ts | `packages/diff-sequences/src/index.ts` | extendOverlappablePathsF、extendOverlappablePathsR（256-523行目） |

**主要処理フロー**:
- **256-385行目**: extendOverlappablePathsF（前方パスの拡張とオーバーラップ検出）
- **389-523行目**: extendOverlappablePathsR（後方パスの拡張とオーバーラップ検出）

#### Step 7: 再帰的な部分列探索を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 7-1 | index.ts | `packages/diff-sequences/src/index.ts` | findSubsequences（653-757行目） |

**主要処理フロー**:
1. **665-686行目**: グラフの転置処理（最適化）
2. **690-700行目**: divide関数の呼び出し
3. **717-730行目**: 先行区間の再帰処理
4. **734-739行目**: 共通部分列の通知
5. **742-756行目**: 後続区間の再帰処理

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

```
diffSequence (index.ts)
    │
    ├─ validateLength (入力検証)
    ├─ validateCallback (入力検証)
    │
    ├─ countCommonItemsF (前方共通カウント)
    ├─ countCommonItemsR (後方共通カウント)
    │
    └─ findSubsequences (再帰的部分列探索)
           │
           ├─ divide (分割)
           │      ├─ extendPathsF (前方パス拡張)
           │      ├─ extendPathsR (後方パス拡張)
           │      ├─ extendOverlappablePathsF (オーバーラップ検出)
           │      └─ extendOverlappablePathsR (オーバーラップ検出)
           │
           ├─ findSubsequences (再帰: 先行区間)
           │
           ├─ foundSubsequence (コールバック: 共通部分通知)
           │
           └─ findSubsequences (再帰: 後続区間)
```

### データフロー図

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

aLength ────────────────────▶ diffSequence()
bLength ────────────────────▶      │
isCommon ───────────────────▶      │
foundSubsequence ───────────▶      │
                                   │
                                   ├─ 前方トリム
                                   │      └─ countCommonItemsF
                                   │
                                   ├─ 後方トリム
                                   │      └─ countCommonItemsR
                                   │
                                   └─ 分割統治
                                          │
                                          ├─ divide (中間変更点を発見)
                                          │      │
                                          │      ├─ 前方パス拡張
                                          │      └─ 後方パス拡張
                                          │
                                          └─ 再帰処理
                                                 │
                                                 ▼
                                          foundSubsequence呼び出し
                                          (nCommon, aCommon, bCommon)

例：
a = [A, B, C, D]
b = [A, X, C, Y]
         │
         ▼
foundSubsequence(1, 0, 0)  // [A]
foundSubsequence(1, 2, 2)  // [C]
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| index.ts | `packages/diff-sequences/src/index.ts` | ソース | 全アルゴリズムの実装 |
| package.json | `packages/diff-sequences/package.json` | 設定 | パッケージ定義 |
| index.test.ts | `packages/diff-sequences/src/__tests__/index.test.ts` | テスト | 基本テスト |
| index.property.test.ts | `packages/diff-sequences/src/__tests__/index.property.test.ts` | テスト | プロパティベーステスト |
