Regexp の実装と最適化

Regexp は graphql の実行時間の 3 分の 1 を占め（perf で 33.9 %）、 StringScanner を介して activerecord / rack のパーサ群にも効いてくる （../yjit_bench_slow_investigation_2026-09.md §5.6、§8.1）。

この文書は、正規表現エンジンとコンパイル済みパターンのキャッシュ、$~ と MatchData の置き方、正規表現を使う String メソッドがどこで高速経路を 取り、どこで取らないかをまとめ、最後に CRuby との実装差異を並べる。 String 側の表現（共有部分文字列、code range、regex_view）は string.md が前提になる。共通の前提は README.md。

1. エンジンとコンパイル済みパターン

1.1 onigmo-regex クレート

エンジンは CRuby と同じ Onigmo で、onigmo-regex クレート（git 依存）が 束ねている。Regex は生の re_pattern_buffer ポインタ、コンパイル時の パターンバイト列、オプション語、OnigmoEncoding、コンパイル時の診断 Vec<String> を持ち、unsafe impl Send + Sync なので、プロセス全体で 1 つの Arc<Regex> をグリーンスレッド間で共有できる。

構築は Regex::new_bytes_with_encoding の 1 本に集約され、onig_new を OnigSyntaxRuby で呼び、Onigmo の onig_syntax_warn 出力をフックで拾って warnings に溜める。

照合の入口は 3 つ:

後ろ 2 つは StringScanner のために追加された（§3.6）。Captures は Region と haystack への &str を持ち、グループ参照はレジスタ配列を直接 読むのでグループごとの確保は無い。

1.2 RegexpInner

regex: Arc<Regex>            // 共有されるコンパイル済みパターン
source: Arc<[u8]>            // CRuby から見える #source の生バイト列（\u{} 展開前）
encoding: OnigmoEncoding     // エンジンが実際に使うエンコーディング（UTF8 / ASCII のみ）
declared_encoding: Encoding  // Regexp#encoding
fixed_encoding: bool         // Regexp#fixed_encoding?
initialized: bool            // Regexp.allocate の placeholder だけ false

重いフィールドは両方 Arc なので clone は参照カウント 2 回。PartialEq は Arc::ptr_eq で短絡する。Value を 1 つも持たないことが ObjTy::REGEXP を GC で昇格可能にしている（§2.6）。

1.3 プロセス全体の正規表現キャッシュ REGEX_CACHE

static REGEX_CACHE: LazyLock<RwLock<HashMap<(String, u32, OnigmoEncoding), Arc<Regex>>>>。キーは \u{} 展開後のエンジン向けパターン文字列、Onigmo だけのオプションビット、エンジンエンコーディング。Ruby だけのビット （NOENCODING / FIXEDENCODING / KCODE_*）はキーを作る前に落とすので /x/ と /x/n はコンパイル済み Regex を共有する （ruby_only_option_bits_dont_split_cache テスト）。

探索は RegexpInner::with_option_kcode_source の 1 本に集まっていて、 インタプリタのあらゆる構築経路（with_option / with_option_and_encoding / with_option_kcode / from_escaped）がここを通る。ヒットなら Arc を 複製してコンパイル警告を再キューする（CRuby は同じパターンを コンパイルするたびに警告し直す）。ミスならコンパイルして挿入し、Onigmo の エラーを CRuby の "<msg>: /<source>/" に整形する。

コストの注記: 探索は常に書き込みロックを取り、ヒットでもキーの String を確保する（reg_str.clone()）。マップは決して evict されない ので、Regexp.new で無限に異なるソースを作るプログラムは際限なく育つ。

1.4 第 2 のキャッシュ（native エンコーディング）

RegexpInner::native_regex は NATIVE_CACHE（生ソースバイト列 + オプション

• コーデックがキー）を持ち、被照合文字列が EUC-JP / Windows-31J / ISO-8859-* / KOI8 / Windows-125x のとき、そのコーデックでパターンを再コンパイルする。 こちらは read() の高速経路が先にある。コーデック対応表 onigmo_encoding_for は多バイトの NamedByte コーデック（Big5 / GB18030 / EUC-KR）を意図的に 外している — monoruby の文字イテレータが Onigmo の境界と食い違うため。 これが CRuby の rb_reg_prepare_re のエンコーディング別再コンパイル キャッシュに相当する（§5）。

1.5 Onigmo に渡す前のソース前処理

• check_regexp_source_valid（builtins/regexp.rs、with_option_kcode_source より手前）: ソースのバイト列がそれ自身の encoding で文字を成さないとき、 Onigmo に渡す前に RegexpError: invalid multibyte character: /…/ を出す。 CRuby の rb_reg_preprocess と同じ位置で、フラグ文字（/\x81/mix、 rb_reg_desc の m-i-x 順）まで含めて描画する。1 バイト 1 文字の BINARY と、 バイト列として読む /…/n（NOENCODING）は対象外。Marshal.load の / ペイロードと Regexp.union の結合後ソースも check_regexp_source_bytes_valid で同じ検査を通る（union が描画するのは メンバ単体ではなく結合後 — Regexp.union("x", eucbad) は /x|a\xA4/）。 なお生バイトではなく \xHH エスケープで書かれた切り詰め （Regexp.new("\\xa4".force_encoding("EUC-JP"))）は前処理を通り抜けて Onigmo が見つけるので、その too short multibyte code string は CRuby に ならって too short escaped multibyte character に言い換える （normalize_onigmo_message）。
• pre_validate_regex: Onigmo が黙って受けてしまう入力に CRuby の文言で RegexpError を出す（末尾の \、桁ゼロの \x、閉じていない \p{）。
• expand_unicode_braces: Onigmo の \u は 4 桁ちょうどしか受けないので \u{XXXX} / \u{XX YY} を \uHHHH（BMP）か生 UTF-8（補助面）に書き換え、 \uXYZ 形のエラーは CRuby の文言で出す。\u を含まなければ即座に抜ける。
• resolve_declared_encoding 系: CRuby のエンコーディング解決の梯子 （n → u/e/s → FIXEDENCODING → 非 ASCII 内容 → US-ASCII 非固定）。

1.6 Executor 無しでのコンパイル時警告

bytecodegen はリテラルを Executor の届かないところでコンパイルするので、 thread_local! PENDING_REGEXP_WARNINGS に溜めて queue_regexp_warnings / drain_pending_warnings で受け渡す。Executor::flush_compile_warnings が Regexp.new / Regexp#initialize / eval / Binding / スクリプトコンパイル 後に流す。

1.7 Regexp.new / .escape / .union / その他

• regexp_new: レシーバが REGEXP_CLASS ちょうどなら直接構築（allocate + initialize の往復無し）。サブクラスは allocate してから #initialize を dispatch し、インスタンスを vm.temp_push で root する。
• Regexp.allocate は空パターンをコンパイルし（必ずキャッシュヒット）、 initialized = false を立てる。#match / #=~ / #options は TypeError、#== / #hash は動く。
• Regexp.escape / .quote はバイト単位の一巡 escape_bytes （rb_reg_quote 相当、Vec::with_capacity(len)）。「壊れた」文字列も raise せずバイト単位でエスケープする。
• Regexp.union: 空 → /(?!)/、Regexp 1 個 → 再コンパイル無しで そのまま返す、to_regexp に応える 1 個 → その regexp。それ以外は parts.join("|") して 1 回コンパイル（キャッシュが効きうる）。 エンコーディング合成の状態機械 UnionEnc / ArgEnc がある。
• Regexp.linear_time? はエンジンに訊く（onig_check_linear_time）。 コンパイル済みプログラムを走査して、match cache がメモ化を跨げない構成 —— 後方参照、部分式呼び出し（\g<…>）、absent operator、push に落ちる look-around 内のキャプチャ、入れ子の repeat —— を探す。ソースの構文走査 ではないので、/.(?=(a))/ は false で /.(?<=(a))/ は true になる （ソースだけ読んでもこの差は出ない）。
• Regexp.timeout / timeout= は強制される。regexp 自身の timeout → グローバル → 無し の順（CRuby と同じ順）で deadline を引き、越えたら Regexp::TimeoutError。deadline は onig_set_interrupt_func フックが 読むスレッドローカルで、ガードがスコープを抜けると元に戻る。

1.8 bytecodegen でのリテラル

• パーサ（prism_backend.rs）は NodeKind::RegExp(parts, flags, is_const) を 作る。フラグ抽出 regex_flags_from_closing は i m x n u e s だけを残し、 o を落とす（§5）。
• 非補間リテラル（is_const）: const_regexp が bytecode 生成時に 1 回だけコンパイルし、結果の Value を frozen にして emit_literal に 渡す。REGEXP_CLASS.is_always_frozen() が真なので命令は FrozenLiteral（Literal ではない）: VM は共有オブジェクトを 複製無しでロードし、JIT の TraceIr::FrozenLiteral は def_lit2gp で GP レジスタへの即値ロードになる。/re/ を回すループは 1 反復あたり 確保ゼロ・エンジン仕事ゼロで、同じサイトの /re/.equal?(/re/) が成り 立つ。リテラルのコンパイルエラーはロード時の構文エラーになる。
• 補間リテラル: gen_regexp が ConcatRegexp 命令を出し、オプション語 は (?imx) のソース接頭辞ではなく先頭の Fixnum オペランドで渡す （(?n) は Onigmo のグループオプションとして無効、かつ Regexp#source に フラグが見えてはいけない）。実行時の runtime::concatenate_regexp は まず通常の "#{}" 結合（concatenate_string_inner、string.md §4.2）で補間 String を組み、そのバイト列と lossy な UTF-8 ビューを with_option_kcode_source に渡す。つまり補間 regexp は評価のたびに 組み直されるが、補間結果が同じなら Onigmo のコンパイルは REGEX_CACHE が 省く。VM / JIT の lowering は素の実行時呼び出し。
• 条件式の裸のリテラル（if /pat/）はパーサが regex =~ $_ に脱糖する。 /(?<name>…)/ =~ str の名前付きキャプチャのローカル束縛は、パーサが Regexp.last_match(:name) の代入列に書き換える。

2. $~ と MatchData

2.1 LFP_SVAR コンテナ

フレームスロット LFP_SVAR（= 16）の 0 は「未確保」の番兵で、非ゼロなら 2 要素の Array [$~, $_]（SVAR_BACKREF = 0 / SVAR_LASTLINE = 1）。 所有するのはメソッドを導入するフレームだけで、ブロックと lambda は outer を辿って LEP に至り、def / クラス本体 / トップレベル / define_method 本体で止まる（Lfp::mfp、 ../stack_frame.md）。

native な builtin フレームは svar スコープを作らない。Executor::current_mfp は動的な CFP 連鎖を is_native() と is_svar_transparent() のフレーム 越しに歩く。is_svar_transparent は monoruby 自身の builtins/*.rb から コンパイルされた全 iseq に立つので、"wawa".to_enum(:scan, /./).map { $& } は monoruby の Enumerable#map が Ruby フレームでも scan の match を見る。

遅延確保: svar_container_of はスロットがゼロなら None を返し、 svar_container_of_create だけが Value::array2(nil, nil) を確保する。 clear_capture_special_variables は nil を格納するためだけにコンテナを 作ったりしない。すべてのフレーム設定コード（VM / JIT / invoker、両アーキ） がゼロの番兵を書く。

GC: Lfp::mark_contents は非ゼロのときだけ mark。c.as_array()[SVAR_BACKREF] = val の格納は Array の DerefMut が write_barrier_bulk() を走らせる のでバリア済み。

実行コンテキストごとの上書き root_lep / root_svar: スレッド／ファイバー 本体は spawner の LEP を持つブロックなので、そこを通して解決すると $~ が 双方向に漏れる。CRuby の ec->root_lep を鏡写しにしていて、 FiberInner::svar_isolated で opt-out できる（Enumerator の内部は意図的に 共有のまま）。

2.2 フックされたグローバル

$~（get / set、nil か MatchData のみ）、$&、$'、$`、$+、 $1..$N（IdentId から桁を読む）、$_ は全部、格納された 1 つの MatchData から導出する読み手で、別の格納は無い。$~ が設定される までは None（defined? が nil）を返し、$~ 自身は常に Some。 stdlib/stringio.rb が rb_lastline_set を真似るための __set_lastline_in_caller もある。

2.3 MatchDataInner — RValue のセルに収める

regex:    Option<Regexp>        // 8
heystack: Value                 // 8   (String のスナップショット)
matches:  SmallVec<[Span; 2]>   // 24
                                 = 40 ≤ RValue の 48 バイト

Span = (u32, u32) で NO_MATCH = (u32::MAX, u32::MAX) が不参加グループ。 usize 対の半分の幅で、inline 容量 2 は「全体一致のみ」と「キャプチャ 1 つ」 を位置の確保無しで賄う。被照合文字列は 4 GiB 未満に制限（構築時に assert）。

コピー無しの haystack スナップショット: MatchDataInner::snapshot は 照合側が被照合 Value を知っていれば、それの共有 copy-on-write 部分文字列 （string_substring）として保持し、知らなければ所有コピーにする。 from_captures_snap が $~ のホットな構築子で、Captures::iter から 中間の位置 Vec 無しで span を組む。アクセサ at_value / pre_match_value / post_match_value / captures_values も CoW 部分文字列を返し、 string_value は毎回同じ frozen スナップショットを返す （md.string.equal?(md.string)）。at は &[u8] を返す — /n のバイト クラス一致で文字境界のスライスをすると extern "C" 境界で abort するため。

2.4 一時の stash と保存経路

• sp_match_regex: 進行中の Regexp。次の save_capture_special_variables が名前付きキャプチャ用に付ける。消費されたら消える。
• sp_match_haystack: 被照合 String の Value。resolve_haystack は照合側 の &str が本当にそのバッファを借りているかをポインタの包含で 検証し、(subject, byte offset) を返す。古い stash は単に None に 解決してコピーに落ちるだけで、誤帰属はしない。
• 両方とも Executor::mark の GC root（MatchData 確保が GC を起こす）。
• save_capture_special_variables / _bytes が MatchData を組み、regexp を 付け、SVAR_BACKREF に格納する。呼び出し側は String#match / =~ / [] 系 / split / sub / gsub / scan、Regexp#=~ / === / match。

2.5 MatchData を確保しない場合

• RegexpInner::match_pred: 真偽だけの照合で、$~ に触れず MatchData も作らない。Regexp#match?、String#match?、Array#grep / Enumerable#grep（grep は $~ を乱してはいけない、CRuby 準拠）。
• captures_from_pos_no_save: 特殊変数の副作用無しの生の照合。gsub + ブロックの先行探索と replace_all_block_inner の走査。
• strscan_match: onig_match / onig_search を再利用 region に、$~ 無し（§3.6）。
• String#match / Regexp#match は保存したばかりの $~ を返り値として 再利用し、別の haystack ビュー上に 2 個目の MatchData を作らない （match_one / rmatch）。str.match(re).equal?($~) が CRuby と同じく 成り立つ。

避けられていないもの: str =~ /x/（どちらのレシーバ順でも）は必ず 確保する。Regexp#=~ → find_one → captures → captures_from_pos → 無条件の save_capture_special_variables。bytecodegen にも JIT にも $~ の死活解析は無いので、JIT されたループ内の if str =~ /x/ は 1 反復あたり MatchData 1 個（+ onig_region_new / free 1 回）を確保する。 Regexp#===（teq）も find_one を通るので case s when /x/ はテストごと に MatchData を確保する — CRuby も同じだが、CRuby は busy でない MatchData オブジェクトを再利用する（§5）。

2.6 GC での昇格

RValue::is_promotable で ObjTy::REGEXP は TIME / UMETHOD とともに 昇格可能（「この 3 つは Value を一切持たない」）。remember-on-promote （young_child_exists）からも参照無しの腕で除外される。効果は ../yjit_bench_slow_investigation_2026-09.md §8.6（minor GC ごとの REGEXP の mark が erubi で 291 → 5）。 ObjTy::MATCHDATA は昇格しない（regexp と haystack の Value を持ち、 _ => false の腕に落ちる）。

3. VM / JIT の経路と正規表現を使う String メソッド

3.0 無いもの

• Regexp にも正規表現駆動の String メソッドにも、インライン生成器・JIT intrinsic・LIR ノードは 1 つも無い。 builtins/regexp.rs に add_inline / inline_gen2! は無く、codegen/ にある regexp 形の機械語は ConcatRegexp の実行時呼び出しだけである。
• Regexp#=== は基本演算表に無い（=== は Integer / Float / Symbol / nil / true / false だけ）。case/when に regexp が来ると Cmp(TEq) → cmp_teq_case_values → cmp_teq_values_impl に Regexp の腕が無く、汎用の invoke_method(_TEQ) でフルの dispatch になる。OptCase（ジャンプ表）は 小さな Integer の when が 8 個以上のときだけで、regexp には効かない。

3.1 regex_view の継ぎ目

RStringInner::regex_view はエンジン向けに UTF-8 として妥当な Cow<str> を 返す: UTF-8 / US-ASCII / ASCII のみの内容なら check_utf8 経由の借用 ビュー、8 ビット内容を持つバイト指向エンコーディングなら各バイト b を U+00bb にした所有の代理像（元の 1 バイト ↔ ビューの 1 文字）。述語 needs_byte_mapping は宣言されたエンコーディングで決め、バイト列が たまたま UTF-8 として妥当かどうかは見ない。逆写像は from_mapped_utf8。 全 String 正規表現メソッドが mapped フラグを持ち回って結果を戻す。 check_utf8 はキャッシュ済み CodeRange が SevenBit か Utf8 + Valid なら O(n) の再検証を飛ばす。

3.2 CodeRange — O(1) の分類キャッシュ

string.md §2 の cr が regexp 経路を安くしている当のもの: is_ascii_only() が「文字添字 == バイト添字」の全ショートカットをゲートし、 char_length() は SevenBit で O(1)、Regexp#match は code_range() != SevenBit で native コーデック経路が要るかを決め、 String#match / #match? は ASCII のみのレシーバで chars().count() を 飛ばす。

3.3 バイト ↔ 文字オフセット変換

文字添字 → バイト添字のキャッシュは無い。 変換は毎回線形走査 （byte_to_char_index は char_indices().enumerate()、char_to_byte_pos は char_indices().nth(cp)、Regexp#match の native 経路は iter_char_bytes().take(cp).map(len).sum()）。ASCII のみのショートカットが 緩和のすべてで、背景と計画は ../encoding_char_iteration_design.md （CharByteIter、「Onigmo coupling」の制限、多エンコーディングの Onigmo 走査は別件という注記）。

3.4 部分文字列の共有と一巡の splice

• string_substring: len > 32 で親がヒープ／共有ならコピー無しの CoW 共有ビュー。全キャプチャ / pre / post 文字列と scan の結果に使う。
• string_snapshot: ユーザーコードが生きたレシーバを書き換えても invoke_block をまたいで &str を借りられる frozen スナップショット。 scan、gsub + ブロック、gsub + Hash。
• check_string_not_modified: CRuby の str_mod_check（長さ基準、 RuntimeError: string modified）。
• EncBuf（rvalue/string.rs）: CRuby の rb_enc_cr_str_buf_cat そのもの。 gsub の結果（str_gsub）と置換テンプレートの展開（rb_reg_regsub）は この追記バッファに前方一巡で片（マッチまでの区間、置換）を追記して 組み立て、結果のエンコーディングは片が来るたびに確定する — 7 bit の片は 何も変えず、バッファが 7 bit しか持たないうちは非 ASCII の片がその エンコーディングを与え、非 ASCII 同士の別エンコーディングは Encoding::CompatibilityError（バッファ側を先に名指し）。UTF-16 / UTF-32 の片は空のバッファだけが受け入れる（"-".gsub(/-/, "a".encode("UTF-16LE")) は UTF-16LE、"-b".gsub(...) は b の追記で拒否、#1634）。ブロック / Hash 形式はループ内で追記するので、受け入れられない片はそれを生んだ yield の直後に拒否される。N 回の末尾シフト bytesplice_with の O(haystack · matches) は O(haystack + Σ replacements)（回帰テスト gsub_many_matches_linear）。splice_all は集めた置換をこの上に流す ラッパ（Hash の plain 経路）。
• RStringInner::sub_splice: 単一一致の sub 用（rb_str_sub_bang）。 受信者と置換を rb_enc_compatible で一度に判定し、判定できなければ マッチの前後が 7 bit のときだけ置換のエンコーディングで生バイトを splice する（"x-".sub(/-/, "a".encode("UTF-16LE")) は UTF-16LE の 3 バイト）。
• bytesplice_with: []= などの単一 splice 用。両側が SevenBit / Valid で splice 端点が UTF-8 境界なら変更後の code range 分類を O(1) に短縮。

3.5 メソッドごとの注記

3.6 StringScanner — 唯一の手調整されたエンジン経路

Ruby 側は stdlib/strscan.rb。_anchored が \A(?:…) で包んだ regexp を 作るのはfallback 経路だけで、サイズ上限 512 の 3 つの Hash （ANCHORED_RE（identity キー）/ ANCHORED_STR / PLAIN_STR）にキャッシュ する。

Rust 側の String#__strscan_match:

• thread_local! STRSCAN_REGION: RefCell<onigmo_regex::Region> — スレッド 全体で 1 つの再利用 region なので、グループ無しのヒットは確保ゼロ。
• String パターンはリテラルバイト列: アンカー時 starts_with、それ以外は windows().position() — Onigmo に入らない。
• Regexp パターンはエンジンビューがバッファそのもの（is_ascii_only() || (Utf8 && valid)）のときだけバイトバッファ上でその場照合し、それ以外は false を返して Ruby 側がコピーに対する String#match に落ちる。
• アンカーは suffix に対する onig_match（strscan_match）で、高速経路では \A(?:…) の包み regexp を決して作らない。
• 返り値は確保を意識している: 走査位置から始まるグループ無しの全体一致は 素の Fixnum、それ以外は平坦な [b0, e0, b1, e1, …] Array。
• $~ は触らない（CRuby の C 実装 strscan もレジスタを自分で持つ）。

計測と経緯は ../yjit_bench_slow_investigation_2026-09.md §5.6、§8.1。

4. エンジンとエンコーディングの相互作用

• 主経路でエンジンに渡るのは UTF-8 か ASCII だけ。より豊かな宣言 エンコーディングは declared_encoding に残り、#encoding / #fixed_encoding? / Regexp.union の互換判定に使われ、走査自体は UTF-8 / 代理ビュー上で走る。
• 例外は非 SevenBit でコーデックのある被照合に対する Regexp#match: onigmo_encoding_for → native_regex（NATIVE_CACHE）→ captures_bytes_from_pos → MatchDataInner::from_captures_bytes。Onigmo が 多エンコーディング照合をするのはここだけ。
• 互換ゲートは CRuby の rb_reg_prepare_enc を写す: check_match_encoding の 3 規則、regexp_encoding_mismatch、check_subject_match_encoding、 warn_binary_regexp_match（「historical binary regexp match /…/n against X string」）、Regexp#match の ArgumentError: invalid byte sequence、String 側の check_pattern_encoding_compat 等。
• 代理写像は多バイトのバイト指向エンコーディングに対する CRuby のエンコー ディング別文字走査のバイト単位の近似である。
• 結果のエンコーディング: apply_template_encoding が sub / gsub の出力を レシーバのエンコーディングに再タグし（置換機構は既定で UTF-8 を組む）、 Regexp#source は fixed_encoding? に従い、補間 regexp は修飾子で固定 されない限り補間内容から取る。

5. CRuby との実装差異

6. 現在の限界

1. REGEX_CACHE と NATIVE_CACHE は上限が無く evict されない。REGEX_CACHE は構築のたびに書き込みロックを取りキー String を確保する。
2. captures_from_pos は照合ごとに OnigRegion を確保・解放する。再利用は StringScanner だけ。
3. $~ の死活解析が無いので str =~ /x/ と case … when /x/ は結果を 使わなくても評価ごとに MatchData を確保する。
4. match cache は入れ子の OP_REPEAT を扱えない。小さい有界反復は Onigmo が展開するので該当しないが（/(?:a{1,2}){1,3}/ は true）、 展開の閾値を越える反復の入れ子 —— /(?:a{10,20})+/、 /(a{100,200})*/ など —— は false になる。CRuby も同じ （count_num_cache_opcodes_inner の “A nested OP_REPEAT is not yet supported”）。Regexp.linear_time? が false を返すものを縛るには Regexp.timeout を使う。
5. Regexp#multiline? は未実装（../plan-activerecord.md）。
6. 非 UTF-8 レシーバに対する Regexp 付き String#slice!、同一エンコーディング の多バイト tr / count 集合は追記予定として string.rs に記録がある。

7. テストと関連文書