# 機能設計書 30-文字列検索・置換

## 概要

本ドキュメントは、Julia Base ライブラリが提供する文字列検索・置換機能の設計について記述する。文字列内の文字・部分文字列・正規表現パターンの検索と、パターンマッチングに基づく置換処理を提供する。

### 本機能の処理概要

文字列検索・置換機能は、`contains` / `occursin` / `startswith` / `endswith` による包含判定、`findfirst` / `findlast` / `findnext` / `findprev` によるパターン位置検索、`match` による正規表現マッチング、`replace` によるパターン置換を提供する。内部実装では、memchr ベースの高速バイト検索と、UTF-8 文字の末尾バイトを利用した最適化が行われている。

**業務上の目的・背景**：テキストデータ内の特定パターンの検索と置換は、ログ解析、データ変換、入力バリデーション、テキスト整形など、あらゆるテキスト処理の基盤となる操作である。Julia は文字・文字列・正規表現の3種類のパターンに対して統一的な検索インタフェースを提供し、UTF-8 エンコーディングに最適化された高速実装を持つ。

**機能の利用シーン**：テキスト内のキーワード検索、URLやメールアドレスのパターンマッチング、ログファイルのフィルタリング、テキストの正規化・クリーニング、テンプレート内のプレースホルダー置換、CSV/TSV データの前処理で利用される。

**主要な処理内容**：
1. `contains(haystack, needle)` / `occursin(needle, haystack)` - 包含判定
2. `startswith(s, prefix)` / `endswith(s, suffix)` - 前方・後方一致
3. `findfirst(pattern, s)` / `findlast(pattern, s)` - パターン位置検索
4. `findnext(pattern, s, i)` / `findprev(pattern, s, i)` - 指定位置からの検索
5. `match(r, s)` - 正規表現マッチング（PCRE2）
6. `eachmatch(r, s)` - 正規表現の全マッチイテレータ
7. `replace(s, pattern => replacement)` - パターン置換
8. `split(s, delim)` / `rsplit(s, delim)` - 区切り文字による分割
9. `join(itr, delim)` - 区切り文字による結合
10. `strip` / `lstrip` / `rstrip` - 前後の空白・指定文字の除去
11. `chomp` / `chop` - 末尾改行・文字の除去
12. `uppercase` / `lowercase` / `titlecase` - 大文字小文字変換

**関連システム・外部連携**：PCRE2 ライブラリ（正規表現エンジン）を使用。

**権限による制御**：なし。すべてのユーザーが利用可能である。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| 6 | 履歴検索モード | 主機能 | contains/occursinベースのフィルタリングによる入力パターンに一致する履歴エントリの検索 |
| 7 | プレフィックス検索モード | 主機能 | startswithベースの前方一致による履歴エントリの検索 |

## 機能種別

計算処理（文字列パターンマッチング・変換）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| s / haystack | AbstractString | Yes | 検索対象の文字列 | 有効な文字列 |
| pattern / needle | AbstractString / AbstractChar / Regex | Yes | 検索パターン | 有効なパターン |
| replacement | AbstractString / Function | No | 置換文字列または変換関数 | 有効な文字列/呼び出し可能 |
| i | Integer | No | 検索開始位置 | 有効なバイトインデックス |
| delim | AbstractString / Regex / Chars | No | 区切り文字 | 有効なパターン |
| count | Integer | No | 最大置換/分割回数 | 正の整数 |

### 入力データソース

Julia プログラム内の文字列。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| found | Bool | contains / occursin / startswith / endswith の結果 |
| index | UnitRange{Int} / Int / nothing | 検索パターンの位置（バイト範囲） |
| match | RegexMatch / nothing | 正規表現マッチ結果（キャプチャ含む） |
| result | String | replace の結果文字列 |
| parts | Vector{SubString} | split の結果 |

### 出力先

呼び出し元への戻り値。

## 処理フロー

### 処理シーケンス

```
1. findnext(c::AbstractChar, s::String, i) - 文字検索
   └─ FwCharPosIter で末尾UTF-8バイトを memchr で検索
   └─ 見つかったバイト位置から文字開始位置を逆算
   └─ isvalid チェック + 文字一致確認
2. findnext(t::AbstractString, s::String, i) - 部分文字列検索
   └─ 短いパターン: 逐次比較
   └─ 長いパターン: Boyer-Moore 等のアルゴリズム
3. contains(s, pattern)
   └─ findfirst(pattern, s) !== nothing で判定
4. startswith(s, prefix)
   └─ String/SubString: _memcmp + nextind チェック
   └─ 汎用: iterate による文字ごと比較
5. replace(s, pat => rep)
   └─ パターンの全出現位置を検索
   └─ 各マッチ位置で置換を適用
   └─ 非マッチ部分と置換結果を結合
```

### フローチャート

```mermaid
flowchart TD
    A[文字列検索・置換] --> B{操作種別}
    B -->|findfirst/findnext| C{パターン種別}
    C -->|Char| D[FwCharPosIter + memchr]
    C -->|String| E[バイト列比較]
    C -->|Regex| F[PCRE2 マッチング]
    B -->|contains| G[findfirst != nothing]
    B -->|startswith| H{String型?}
    H -->|Yes| I[_memcmp + nextind]
    H -->|No| J[iterate 逐次比較]
    B -->|replace| K[全マッチ位置検索 + 置換適用]
    B -->|split| L[delim 位置検索 + SubString 分割]
    D --> M[結果返却]
    E --> M
    F --> M
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 末尾バイト検索 | Char 検索では UTF-8 の末尾バイトを memchr で検索し、候補位置を絞り込む | String/SubString でのChar検索 |
| BR-02 | is_standalone_byte | 単独バイト文字（ASCII等、< 0x80 or > 0xf7）は直接 memchr で確定 | 1バイト文字の検索 |
| BR-03 | memcmp最適化 | startswith は String 同士の場合 _memcmp でバイト列直接比較 | String/SubString 間の比較 |
| BR-04 | PCRE2 | 正規表現は PCRE2 ライブラリに委譲 | Regex パターン使用時 |
| BR-05 | replace回数制限 | count パラメータで置換回数を制限可能 | replace 使用時 |

### 計算ロジック

- `FwCharPosIter`: UTF-8 の末尾バイトで memchr → 文字開始位置逆算 → isvalid + 文字一致確認
- `RvCharPosIter`: 同様だが逆方向に _rsearch を使用
- `is_standalone_byte(x)`: `(x < 0x80) | (x > 0xf7)` - 単独バイト文字判定
- `last_utf8_byte(c)`: Char の最終 UTF-8 バイトを取得

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

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

該当なし（インメモリ計算のみ）。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | BoundsError | 範囲外インデックスで findnext | 有効範囲内のインデックスを使用 |
| - | StringIndexError | 無効なバイトインデックスで検索開始 | isvalid で事前確認 |
| - | PCRE2 error | 不正な正規表現パターン | 正しい正規表現構文を使用 |

### リトライ仕様

リトライは不要。

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

該当なし。

## パフォーマンス要件

- Char 検索: memchr ベースで O(n) だが定数倍が非常に小さい
- 部分文字列検索: O(n*m) 最悪ケース（n: テキスト長、m: パターン長）
- startswith(String, String): _memcmp で O(m)（m: プレフィックス長）
- replace: O(n * k)（n: 文字列長、k: マッチ数）
- split: O(n)

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

- 正規表現のバックトラッキングによる ReDoS（正規表現サービス拒否）に注意
- ユーザー入力を正規表現パターンとして使用する場合は適切なエスケープが必要

## 備考

- `contains(s, pattern)` は Julia 1.5 で追加（以前は `occursin(pattern, s)` のみ）
- `startswith` / `endswith` は Chars 型（文字のタプル/ベクトル/集合）にも対応
- `split` の `keepempty` パラメータで空文字列を結果に含めるか制御可能
- `replace` は関数による動的置換にも対応（`replace(s, r"pattern" => m -> transform(m))`)

---

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

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

### 推奨読解順序

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

文字列検索で使用される内部イテレータ型を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | strings/search.jl | `base/strings/search.jl` | FwCharPosIter, RvCharPosIter, AbstractPattern の定義 |

**読解のコツ**: Julia の文字列検索は、UTF-8 の末尾バイトを memchr で検索するという最適化手法を使っている。これは、末尾バイトが最もバリエーションが豊富であるため、誤検出が少なく高速に候補を絞れるためである。`is_standalone_byte` と `last_utf8_byte` がこの最適化の鍵。

- **11行目**: `AbstractPattern` - パターンマッチングの抽象型
- **34-38行目**: `last_utf8_byte(c)` - Char の最終UTF-8バイトを取得
- **42行目**: `is_standalone_byte(x)` - 単独バイト文字判定
- **48-55行目**: `FwCharPosIter` 構造体 - 前方文字位置イテレータ
- **65-96行目**: `iterate(s::FwCharPosIter)` - memchr + 文字確認ループ
- **99-103行目**: `RvCharPosIter` 構造体 - 後方文字位置イテレータ
- **120-139行目**: `iterate(s::RvCharPosIter)` - _rsearch + 文字確認ループ

#### Step 2: findnext を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | strings/search.jl | `base/strings/search.jl` | findnext の Char / String / Regex 各パターン実装 |

**主要処理フロー**:
1. **146-150行目**: `findnext(pred::Fix2{isequal, Char}, s, i)` - FwCharPosIter を使用した最適化パス

#### Step 3: startswith / endswith を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | strings/util.jl | `base/strings/util.jl` | startswith, endswith, contains 等のユーティリティ関数 |

**主要処理フロー**:
- **17-40行目**: `startswith(a, b)` の汎用実装 - iterate による文字ごと比較
- **57-67行目**: `endswith(a, b)` - Iterators.Reverse を使用した逆方向比較
- **69-79行目**: `startswith(String, String)` - _memcmp による高速比較 + nextind チェック

#### Step 4: replace / split を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | strings/util.jl | `base/strings/util.jl` | replace, split, join, strip 等の変換関数 |

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

```
contains(s, pat) / startswith(s, pre) / findnext(pat, s, i) / replace(s, pat=>rep)
    |
    +-- contains(s, pat)
    |       +-- occursin(pat, s)
    |               +-- findfirst(pat, s) !== nothing
    |
    +-- startswith(s::String, pre::String)
    |       +-- _memcmp(s, pre, sizeof(pre))
    |       +-- nextind(s, ncodeunits(pre)) チェック
    |
    +-- findnext(isequal(c), s::String, i)
    |       +-- FwCharPosIter(s, c)
    |       +-- iterate: _search(s, last_char_byte, i)
    |       |   +-- [standalone] memchr で直接検索
    |       |   +-- [multi-byte] memchr + isvalid + 文字一致確認
    |       +-- 結果のインデックスを返す
    |
    +-- replace(s, pat => rep; count)
            +-- パターン位置の逐次検索
            +-- IOBuffer に非マッチ部分 + 置換結果を書き込み
            +-- String(take!(buf))
```

### データフロー図

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

s (String), c (Char)    ---->  findnext(isequal(c), s, i)
                               +-- FwCharPosIter
                               +-- memchr(last_utf8_byte)
                               +-- 候補位置の文字確認             ---->  Int / nothing

s, prefix (String)      ---->  startswith(s, prefix)
                               +-- _memcmp(s, prefix, len)        ---->  Bool

s, pat, rep             ---->  replace(s, pat => rep)
                               +-- 全マッチ検索 + IOBuffer
                               +-- 置換適用                       ---->  String (置換後)

s, delim                ---->  split(s, delim)
                               +-- delim位置検索
                               +-- SubString 分割                 ---->  Vector{SubString}
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| strings/search.jl | `base/strings/search.jl` | ソース | 文字列検索の核心実装（FwCharPosIter, findnext, _search, _rsearch） |
| strings/util.jl | `base/strings/util.jl` | ソース | 文字列ユーティリティ（startswith, endswith, contains, replace, split, join, strip等） |
| regex.jl | `base/regex.jl` | ソース | Regex 型と PCRE2 ラッパー |
| pcre.jl | `base/pcre.jl` | ソース | PCRE2 C ライブラリのJuliaバインディング |
| strings/basic.jl | `base/strings/basic.jl` | ソース | AbstractString の基本インタフェース |
