# memory: instinct-regex-quadratic-from-forward-progress

正規表現の二乗はバックトラックだけでなく「1開始位置あたりの前進量」でも起きる。絶対最大量指定子や atomic group では直らず、繰り返しを有界にするしかない。

## ポイント
- 正規表現の二乗はバックトラックだけでなく「1開始位置あたりの前進量」でも起きる
- 絶対最大量指定子や atomic group では直らず、繰り返しを有界にするしかない
- 各開始位置で `*` が残り全部を前進で消費し、その後 `[:=]` で失敗する
- 前進が O(n)、開始位置が n 箇所 ⇒ O(n²)
- `*+` / `(?>…)` が消すのは後戻りであって、行った先までの距離ではない
- 繰り返しを `{0,8}` で有界にしたら 0.04 秒（500 倍）
- 「二乗＝カタストロフィックバックトラッキング」と反射的に結びつけると、atomic 化という効かない対策に時間を使う
- 切り分けは簡単で、その量指定子が失敗前にどこまで進むかを見る
- 1開始位置の仕事量が入力長に比例するなら、後戻りを消しても二乗のまま
- 遅い正規表現は、まず繰り返しの前進量が入力長に依存するかを見る
- 依存するなら上限（`{0,N}`）を付ける。atomic 化は次の手段
- ^ アンカー付きの式が速くても安心しない
- 同じ式をアンカー無しで使う枝（1行判定など）は開始位置が n 倍になり、そこだけ二乗になる
- 入れ子の遅延量指定子（`X{0,N}?Y{8,}Z{0,N}?`）は別種の爆発源
- 先読みで存在確認だけして本体は貪欲1本にすると消える（74 秒 → 0.18 秒）
- 性能ガードの対象を「複数行枝だけ」のように名前や接頭辞で選ばない
- 既定で全パターンを測り、遅いと分かっているものだけ Issue 番号付きで免除する

## 関連ページ
[[instinct-perf-guard-must-fail-fast]] [[instinct-oscillating-filter-means-wrong-axis]] [[instinct-fixed-width-rewind-vs-unbounded-patterns]]

## 関連概念（未作成）
`正規表現の最適化` `ReDoS対策` `正規表現のパフォーマンスチューニング`