# 機能設計書 102-ropes

## 概要

本ドキュメントは、Nim標準ライブラリの`ropes`モジュールの機能設計を記述する。このモジュールは、効率的な文字列連結を実現するロープデータ構造を提供する。

### 本機能の処理概要

`ropes`モジュールは、非常に長い文字列を効率的に扱うためのロープ（Rope）データ構造を実装する。通常の文字列連結がO(n)の計算量を要するのに対し、ロープはO(1)で連結を行える。

**業務上の目的・背景**：大量のテキスト生成（コード生成、HTMLドキュメント生成、ログファイル作成など）において、頻繁な文字列連結は性能のボトルネックとなる。ロープデータ構造を使用することで、連結操作を効率化し、最終的に必要な時点でのみ文字列へのフラット化を行うことで、メモリ使用量と処理時間を削減する。Nimコンパイラ自体のコード生成でも使用されている重要なデータ構造である。

**機能の利用シーン**：コンパイラのコード生成、テンプレートエンジン、大規模テキスト処理、ログ出力の最適化など。

**主要な処理内容**：
1. 文字列からロープへの変換
2. ロープ同士の連結（O(1)）
3. ロープから文字列への変換（フラット化）
4. フォーマット文字列による置換
5. ファイルへの書き込み
6. リーフキャッシュによるメモリ最適化

**関連システム・外部連携**：`streams`モジュールとの連携（ストリームへの書き込み）。

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

## 関連画面

本モジュールは標準ライブラリであり、特定の画面との関連はない。

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | - |

## 機能種別

データ構造 / 文字列処理

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| s | string | Yes | ロープに変換する文字列 | 空文字列も可 |
| i | BiggestInt | Yes | ロープに変換する整数 | - |
| f | BiggestFloat | Yes | ロープに変換する浮動小数点数 | - |
| a, b | Rope | Yes | 連結するロープ | nilも可 |
| frmt | string | Yes | フォーマット文字列 | $n, $#, ${n}形式 |
| args | openArray[Rope] | Yes | フォーマット引数 | - |

### 入力データソース

プログラムコードからの直接呼び出し。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| Rope | ref object | ロープオブジェクト（連結ツリー構造） |
| string | string | フラット化された文字列 |
| int | int | ロープの長さ |
| char | char | 指定位置の文字 |

### 出力先

呼び出し元への戻り値、ファイル、ストリーム。

## 処理フロー

### 処理シーケンス

```
1. ロープ作成 (rope)
   └─ キャッシュが有効なら既存リーフを検索
   └─ なければ新しいリーフノードを作成

2. 連結 (&)
   └─ 新しい内部ノードを作成
   └─ 左右の子として両ロープを設定
   └─ 長さの合計を計算

3. フラット化 ($)
   └─ leavesイテレータで全リーフを走査
   └─ 各リーフの文字列を結合

4. フォーマット (%)
   └─ フォーマット文字列を解析
   └─ 引数を位置に応じて挿入
```

### フローチャート

```mermaid
flowchart TD
    A[開始: rope作成] --> B{キャッシュ有効?}
    B -->|Yes| C[splayツリーで検索]
    C --> D{見つかった?}
    D -->|Yes| E[既存ノードを返却]
    D -->|No| F[新規ノード作成し挿入]
    B -->|No| F
    F --> G[Ropeを返却]
    E --> G

    H[開始: 連結] --> I{aがnil?}
    I -->|Yes| J[bを返却]
    I -->|No| K{bがnil?}
    K -->|Yes| L[aを返却]
    K -->|No| M[新規内部ノード作成]
    M --> N[left=a, right=b]
    N --> O[length=a.len+b.len]
    O --> G
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 空ロープ | 空文字列のロープはnilで表現 | rope("")呼び出し時 |
| BR-02 | 不変性 | ロープは不変（immutable）で、サブツリーは共有可能 | 常時 |
| BR-03 | キャッシュ | リーフキャッシュはメモリ効率向上のためオプション | enableCache呼び出し時 |
| BR-04 | フォーマット | $識別子や${識別子}形式はサポートしない | `%`演算子使用時 |

### 計算ロジック

**連結の計算量**: O(1)
```nim
result = newRope()
result.length = a.length + b.length
result.left = a
result.right = b
```

**長さ取得**: O(1)
```nim
if a == nil: 0 else: a.length
```

**インデックスアクセス**: O(n) 最悪ケース
- ツリーを辿って目的のリーフを探索

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

本モジュールはデータベース操作を行わない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| ValueError | 実行時例外 | 無効なフォーマット文字列 | 正しい$n, $#, ${n}形式を使用 |

### リトライ仕様

リトライは不要。

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

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

## パフォーマンス要件

- 連結操作: O(1)
- フラット化: O(n)（nは文字列総長）
- インデックスアクセス: O(n)（最悪ケース）
- キャッシュ使用時のリーフ検索: splayツリーにより平均O(log n)

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

特になし。

## 備考

- スレッドローカル変数（threadvar）を使用してキャッシュを管理
- JavaScript/NimScript環境では一部機能（equalsFile）が無効

---

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

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

### 推奨読解順序

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

Rope型の内部構造を理解することが最も重要。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | ropes.nim | `lib/pure/ropes.nim` | 34-39行目: Rope型定義（left, right, length, data） |

**読解のコツ**: Ropeは`{.acyclic.}`プラグマ付きref objectとして定義されている。これは循環参照がないことをGCに伝え、参照カウントによる効率的なメモリ管理を可能にする。

#### Step 2: 基本操作を理解する

ロープの作成と連結のメカニズムを把握する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | ropes.nim | `lib/pure/ropes.nim` | 49-51行目: len関数 |
| 2-2 | ropes.nim | `lib/pure/ropes.nim` | 53-57行目: newRope関数 |
| 2-3 | ropes.nim | `lib/pure/ropes.nim` | 130-147行目: rope(string)関数 |
| 2-4 | ropes.nim | `lib/pure/ropes.nim` | 175-189行目: `&`連結演算子 |

**主要処理フロー**:
- **136行目**: 空文字列の場合はnilを返す
- **143-146行目**: キャッシュ有効時はsplayツリーで検索
- **181-189行目**: 連結時は新しい内部ノードを作成し、左右に子を設定

#### Step 3: キャッシュ機構を理解する

splayツリーによるリーフキャッシュを把握する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | ropes.nim | `lib/pure/ropes.nim` | 59-61行目: キャッシュ用スレッドローカル変数 |
| 3-2 | ropes.nim | `lib/pure/ropes.nim` | 66-102行目: splay関数 |
| 3-3 | ropes.nim | `lib/pure/ropes.nim` | 104-128行目: insertInCache関数 |
| 3-4 | ropes.nim | `lib/pure/ropes.nim` | 165-173行目: enableCache/disableCache関数 |

**主要処理フロー**:
- **66-102行目**: splay関数でツリーを再構成しながら検索
- **112行目**: cmp==0なら既存ノードを再利用（キャッシュヒット）

#### Step 4: 走査とフラット化を理解する

イテレータと文字列変換の仕組みを把握する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | ropes.nim | `lib/pure/ropes.nim` | 257-276行目: leavesイテレータ |
| 4-2 | ropes.nim | `lib/pure/ropes.nim` | 278-281行目: itemsイテレータ |
| 4-3 | ropes.nim | `lib/pure/ropes.nim` | 291-294行目: `$`演算子 |
| 4-4 | ropes.nim | `lib/pure/ropes.nim` | 233-255行目: `[]`インデックスアクセス |

**主要処理フロー**:
- **268-276行目**: スタックを使った深さ優先走査でリーフを訪問
- **293-294行目**: leavesの結果を連結してフラット化

#### Step 5: フォーマット機能を理解する

`%`演算子の置換ロジックを把握する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | ropes.nim | `lib/pure/ropes.nim` | 296-347行目: `%`演算子 |
| 5-2 | ropes.nim | `lib/pure/ropes.nim` | 349-356行目: addf関数 |

**主要処理フロー**:
- **314-341行目**: $n, $#, ${n}の各形式を解析して引数を挿入

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

```
ropes.nim
    │
    ├─ Rope型定義
    │      └─ ref object {left, right, length, data}
    │
    ├─ 作成
    │      ├─ rope(string) ─── insertInCache ─── splay
    │      ├─ rope(BiggestInt)
    │      └─ rope(BiggestFloat)
    │
    ├─ 連結
    │      ├─ `&`(Rope, Rope)
    │      ├─ `&`(Rope, string)
    │      ├─ `&`(string, Rope)
    │      ├─ `&`(openArray[Rope])
    │      └─ add
    │
    ├─ 走査
    │      ├─ leaves ─── スタック走査
    │      ├─ items ─── leaves使用
    │      └─ `[]` ─── ツリー辿り
    │
    ├─ 変換
    │      ├─ `$` ─── leaves使用
    │      └─ len
    │
    ├─ フォーマット
    │      ├─ `%`
    │      └─ addf
    │
    └─ I/O
           ├─ write(File)
           ├─ write(Stream)
           └─ equalsFile
```

### データフロー図

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

string ─────────────────▶ rope() ──────────────────▶ Rope
                              │
                              └─▶ insertInCache (キャッシュ有効時)

Rope + Rope ────────────▶ `&` ─────────────────────▶ Rope (内部ノード)
                              │
                              └─▶ newRope (left=a, right=b)

Rope ───────────────────▶ leaves ──────────────────▶ Iterator[string]
                              │
                              └─▶ スタック走査

Rope ───────────────────▶ `$` ─────────────────────▶ string
                              │
                              └─▶ leaves + add

"fmt" % [Rope] ──────────▶ `%` ─────────────────────▶ Rope
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| ropes.nim | `lib/pure/ropes.nim` | ソース | メインモジュール、全機能の実装 |
| streams.nim | `lib/pure/streams.nim` | 依存 | ストリームへの書き込みサポート |
| system/inclrtl.nim | `lib/system/inclrtl.nim` | 依存 | ランタイムライブラリインクルード |
