正規表現エンジン¶

正規表現は、文字列に対するパターン照合を宣言的に書ける便利な道具ですが、その実行はエンジン内部でもっとも計算量が読みにくいコンポーネントの一つです。同じ「照合」という機能でも、内部の実現方式によって、あるパターンが入力長に線形の時間で終わるか、それとも指数関数的に爆発してプロセスを固めてしまうかが変わります。さらに JavaScript の正規表現は後方参照や後読みといった、理論的に扱いにくい機能を含むため、方式の選択には仕様適合と性能の綱引きがあります。この章では、照合エンジンの二大方式とそのトレードオフ、パターンを一度だけコンパイルしてキャッシュする意義、開始位置スキャンの最適化、マッチ結果の割り当てコスト、そして Unicode 対応と、実装で陥りやすい罠を扱います。

二つの方式: バックトラッキングとオートマトン¶

正規表現の照合エンジンは、大きく二つの系統に分かれます。

バックトラッキング型は、パターンを入力に対して素直に試し、選択肢(a|b の分岐や a* の繰り返し回数)で一つの道を選んで進み、行き詰まったら直前の選択に戻って別の道を試す、という探索を行います。人間がパターンを追う手順にもっとも近く、実装も比較的素直です。決定的な利点は、後方参照や先読み・後読みといった、正規言語の枠を超える機能を自然に表現できることです。これらの機能は「これまでに何にマッチしたか」という文脈を照合中に参照するため、探索状態を持つバックトラッキングと相性が良いのです。欠点は、選択肢の組み合わせが入力に応じて爆発しうることで、最悪計算量が入力長に対して指数関数的になります。

オートマトン型(NFA/DFA)は、パターンを有限オートマトンに変換し、入力を一文字ずつ読みながら「現在ありうる状態の集合」を並行して進めます。Thompson の構成法に代表されるこの方式では、選択肢を「戻ってやり直す」のではなく「すべての可能性を同時に保持する」ため、入力の各文字を一度読むだけで済み、最悪でも入力長に線形の時間で照合が完了します。欠点は、後方参照のように正規言語を超える機能を素直には表現できないことです(後方参照つきの照合は一般に NP 困難であることが知られています)。

両者は排他ではありません。多くの実用エンジンは、パターンが正規言語の範囲に収まるならオートマトン系の高速経路に載せ、後方参照などを含む場合だけバックトラッキングに落とす、といったハイブリッド構成をとります。

なぜ JavaScript ではバックトラッキングが多いか¶

ECMA-262 が定める正規表現のセマンティクスは、後方参照(\1)、先読み((?=...) / (?!...))、後読み((?<=...) / (?<!...))を含みます。加えて、キャプチャグループがどの部分文字列を捕捉したか、貪欲・非貪欲(* と *?)でどちらの候補を優先するか、といった「どのマッチを選ぶか」まで仕様が規定しています。仕様の照合アルゴリズム自体が、継続(continuation)を用いた再帰的なバックトラッキングとして記述されており、貪欲量指定子は「まず長く試し、失敗したら一つ譲る」という順序で定義されます。

この「マッチの選び方まで含めた厳密なセマンティクス」を素直に満たそうとすると、実装はバックトラッキング型に寄ります。純粋な DFA は「マッチするか否か」と「最長マッチ」は高速に答えられますが、JavaScript が要求する「仕様どおりのキャプチャ内容」「貪欲・非貪欲の優先順位」「後方参照」までは表現しきれないためです。結果として、JavaScript エンジンの正規表現は後方参照や後読みを含むパターンを扱える必要から、バックトラッキングを基盤に据えることが多くなります。線形時間の恩恵を得たい場合は、機能を限定できると判定したパターンに対してオートマトン系の経路を追加で用意する、という発想になります。

要点は、線形時間と表現力はトレードオフの関係にあることです。JavaScript のように表現力側の要求が仕様で固定されている場合、線形性は「限定された部分集合に対してのみ」得られる最適化として扱うのが現実的です。

パターンのコンパイルとキャッシュ¶

照合の性能を語るとき、まず問うべきは「パターンを何回解析しているか」です。素朴に書かれた照合器は、パターンをバイト列(あるいは文字列)のまま持ち、入力を一文字進めるたびにそのバイト列を先頭から読み直します。たとえば現在位置の原子(atom)が繰り返しかどうかを知るために * や + を探し、選択肢の区切り | を探し、いま照合中の原子の範囲を毎回パターン側から数え直す、といった具合です。

この作りは動きはしますが、照合の各ステップがパターン長に比例した仕事をするため、入力とパターンの積に比例(あるいはそれ以上)のコストがかかります。複雑なパターンほど、一文字進めるたびの再解析が重くのしかかります。

対策は明快で、パターンは照合を始める前に一度だけ解析し、再利用可能な構造へコンパイルしておくことです。解析結果は、たとえば次のような形をとります。

• 各原子(文字・文字クラス・グループ・後方参照など)を、種別と範囲を持つノードとして並べた列。
• 分岐や繰り返しを、ジャンプ・分岐命令を持つ小さな「プログラム」に落としたバイトコード列。

照合ループはこのコンパイル済み構造をたどるだけになり、一ステップの仕事はパターン長ではなく現在ノードのみに依存する定数程度に縮みます。パターン中の | の位置や原子の範囲は、解析時に一度だけ確定させてノードに焼き込んでおけば、照合中に数え直す必要がありません。この「照合ステップの中でパターンを再解析しない」という原則は、正規表現に限らず、繰り返し評価される宣言的記述を扱うコンポーネント全般に通じる基本です。

コンパイル結果は、正規表現オブジェクトに紐づけてキャッシュします。同じ正規表現リテラルやオブジェクトを繰り返し使う典型的な利用パターン(ループ内での test / exec など)では、コンパイルは初回一度きりになり、複雑なパターンほど大きな高速化になります。ここでの注意は、lastIndex などの可変状態はコンパイル結果とは別に扱い、コンパイル済み構造自体は不変にしておくことです。そうすれば同一パターンのキャッシュを安全に共有できます。

開始位置のスキャン最適化¶

g フラグつきの検索や、長い文字列の中からパターンを探す用途では、エンジンは「マッチはこの位置から始まるか?」を先頭から順に試します。素朴には、位置 0 で失敗したら位置 1、また失敗したら位置 2、と全開始位置で照合を試みるため、最悪で入力長の二乗に比例する走査になります。

多くのパターンは、マッチが始まりうる文字をあらかじめ絞り込めるという性質を使うと、これを大幅に削れます。たとえば foo\d+ は必ず f から始まります。ならば、入力中の f 以外の位置は照合を試すまでもなく飛ばせます。より一般には、パターンから「マッチの先頭になりうる文字の集合」や「必須の先頭部分文字列(プレフィックス)」を抽出し、それを高速な文字探索で見つけた位置だけで本体の照合を起動します。先頭文字が一種類なら単純な文字探索、必須プレフィックスがあるなら部分文字列探索を使うことで、多くの開始位置をまとめて読み飛ばせます。

この最適化はコンパイル時に一度だけ行い、抽出したプレフィックス情報をコンパイル結果に添えておきます。重要なのは保守的なフォールバックです。^ を伴わないパターン、先頭が任意文字クラスや選択肢で始まるパターンなど、先頭を単一の文字集合として特徴づけられない場合は、先頭フィルタを諦めて全開始位置を試す従来どおりの走査に戻します。フィルタは「マッチしうる位置を漏れなく含む」ことが正しさの条件なので、少しでも取りこぼす恐れがあるなら適用しない、という安全側の判断を徹底します。フィルタで候補が絞れるときだけ速くなり、絞れないときも遅くならず正しく動く、というのが望ましい設計です。

マッチ結果の割り当てを抑える¶

照合が成功したあと、エンジンは結果を組み立てます。JavaScript の exec の戻り値は配列風のオブジェクトで、マッチ全体とキャプチャ群、index(マッチ開始位置)、そして input(照合対象の文字列そのもの)などのプロパティを持ちます。ここに素朴な実装だと見落としやすいコストがあります。

• input に照合対象の文字列を毎回コピーする: input プロパティに、照合対象の文字列を新しく複製して格納する実装は、マッチのたびに入力全体をコピーします。長い文字列を g フラグで何度もマッチさせると、マッチ回数×入力長ぶんのコピーが積み上がります。文字列はエンジン内部で不変オブジェクトとして扱えるので、既存の照合対象の文字列オブジェクトへの参照をそのまま再利用すれば、コピーは不要です。input はまさに照合した文字列そのものを指すべきものであり、新規複製する理由がありません。
• キャプチャ配列の割り当て: キャプチャの部分文字列も、可能なら照合対象への範囲参照(スライス)として持ち、実体の複製は必要になるまで遅延できます。
• 真偽だけが要るときは結果を組み立てない: test のように「マッチしたか否か」だけを返す経路では、キャプチャ配列も結果オブジェクトもいっさい作らず、照合が最初の成功に達した時点で真を返せば十分です。結果オブジェクトの構築を丸ごと省けるため、test は exec より軽くできます。同様に、置換や分割でも、必要なキャプチャだけを組み立てる経路を用意すると無駄が減ります。

原則は「照合の本質的な仕事(パターンと入力の突き合わせ)以外の付随コストを、必要なときだけ払う」ことです。とりわけ入力全体のコピーは、マッチ本体が軽いパターンでは相対的に支配的なコストになりうるため、優先して排除する価値があります。

Unicode・大文字小文字・サロゲートの扱い¶

JavaScript の文字列は UTF-16 コード単位の列であり、正規表現の照合もこの前提の上に成り立ちます。ここには照合特有の注意点がいくつかあります。

• サロゲートペアと u / v フラグ: u(Unicode)フラグがない既定のモードでは、照合は UTF-16 コード単位を単位に進みます。この場合、補助面(BMP 外)の文字は上位・下位サロゲートの二つのコード単位として扱われ、. や文字クラスもコード単位単位で動きます。u / v フラグを付けると照合はコードポイント単位になり、. はサロゲートペア全体を一文字として扱い、\u{...} 記法やコードポイント単位の量指定が正しく働きます。エンジンは、フラグに応じて「一文字進める」の意味(コード単位かコードポイントか)を切り替える必要があります。位置を一つ進めるときに、サロゲートペアの途中で止まらないよう境界を意識するのが要点です。
• 大文字小文字を無視する照合(i フラグ): 素朴には照合のたびに両者を畳んで比較しますが、正しさと速度の両面で注意が要ります。正しさの面では、Unicode の大文字小文字対応は単純な一対一ではなく(一部の文字は畳み込み先が複数、あるいは非対称)、ケースフォールディングの規則に従う必要があります。速度の面では、文字クラスの各文字についてフォールド後の集合をコンパイル時に展開しておくと、照合中の変換を減らせます。u / v フラグの有無でフォールディングの規則が変わる点にも注意します。
• 文字クラスと範囲: [a-z] のような範囲や否定クラスは、コンパイル時にコードポイントの区間集合(あるいはビットマップ)へ正規化しておくと、照合中の一文字の判定が区間検索一回で済みます。u/v モードでは範囲もコードポイント基準で解釈します。

いずれも「フラグに応じた照合単位と等価規則を、コンパイル時にできるだけ確定させ、照合ループを軽く保つ」という方針でまとめられます。

実装上の罠¶

正規表現エンジンには、動作はするが特定条件で破綻する、あるいは静かに遅い罠がいくつも潜みます。代表的な三つを挙げます。

破滅的バックトラッキングと ReDoS¶

バックトラッキング型の最大の危険が、破滅的バックトラッキング(catastrophic backtracking)です。ネストした繰り返しや、重なりのある選択肢を含むパターンは、マッチしない入力に対して、失敗を確定するまでに指数関数的な数の分岐を試してしまいます。

古典的な例が (a+)+$ のようなパターンです。これに "aaaa...a!"(末尾がパターンに合わない一文字)を与えると、内側の a+ と外側の + が入力の a 列をどう分割するかの組み合わせを、末尾の不一致で全滅だと判明するまで総当たりします。a の個数を一つ増やすたびに試行回数がおおよそ倍増し、数十文字程度の入力でも実質的に終わらなくなります。悪意ある入力でこれを誘発し、サービスを停止させる攻撃が ReDoS(Regular expression Denial of Service)です。パターンがユーザ入力から来る場合はもちろん、固定パターンでも入力が外部由来なら現実の脅威になります。

flowchart TD
    A["aaa! を照合<br/>外側 + の1周目、内側 a+ は何個取るか"]
    A --> B["3個取る → 残り '!'"]
    A --> C["2個取る → 残り 'a!'"]
    A --> D["1個取る → 残り 'aa!'"]
    B --> B1["$ が '!' に不一致 → 失敗"]
    C --> C1["外側 + をもう1周"]
    C1 --> C2["1個取る → 残り '!' → 失敗"]
    D --> D1["外側 + をもう1周"]
    D1 --> D2["2個取る → 残り '!' → 失敗"]
    D1 --> D3["1個取る → 残り 'a!' → さらに分岐 → 失敗"]

(a+)+$ に "aaa!" を与えたときの分割の探索木。全経路が末尾の不一致で失敗し、a を 1 文字増やすごとに枝がおおよそ倍増する。

対策にはいくつかの方向があります。

• バックトラッキングの量に上限を設ける: 探索のステップ数や再帰の深さにしきい値を設け、超えたら照合を打ち切ってハングではなくエラー(あるいは所定の失敗)として返す。プロセスが固まる最悪の事態を、制御された失敗に変えられます。上限は入力とパターンの規模に応じた妥当な値にし、正当なマッチを誤って切らないよう調整します。
• メモ化: 「この位置・この状態で既に失敗した」という組み合わせを記録し、同じ状態の再訪を枝刈りする。指数的な再訪を多項式に抑えられる場合があります。ただし状態の記録にメモリを要し、後方参照が絡むと状態空間が広がるため万能ではありません。
• オートマトンへの退避: 後方参照などを含まず正規言語に収まるパターンは、線形時間のオートマトン系経路に載せて指数爆発そのものを回避する。表現力の要求を満たせる範囲で、もっとも根本的な対策です。

実務では、これらを組み合わせ、「線形経路に載せられるものは載せ、載せられないものはバックトラッキング量を上限で守る」という多層の守りにするのが現実的です。

照合ステップごとのパターン再解析¶

前述のとおり、パターンをコンパイルせず、照合の各ステップでパターン文字列を読み直す実装は、一ステップあたりパターン長に比例する仕事をします。これは破綻こそしないものの、複雑なパターンで静かに、しかし大きく遅くなる罠です。症状は「入力が短いのに遅い」「パターンを複雑にすると急に遅くなる」という形で現れ、原因が照合本体ではなく再解析にあることが見えにくいのが厄介です。パターンを一度だけコンパイルして構造をキャッシュし、照合ループはその構造だけをたどるようにすれば解消します。密なマッチが続く場合はバックトラッキング本体が律速として残りますが、それ以前に再解析コストを払っていないかをまず確認するのが順序です。

マッチごとの過剰な割り当て¶

三つ目は、照合そのものは正しく速いのに、結果の組み立てで無駄を払う罠です。とりわけ、input プロパティに照合対象の文字列全体を毎回コピーする実装は、g フラグでの多数マッチや長い入力で、コピーが積み上がって支配的コストになります。既存の照合対象の文字列オブジェクトを再利用すれば消せます。加えて、真偽判定だけの test 経路でキャプチャ配列や結果オブジェクトを組み立ててしまうのも無駄で、最初の成功で真を返す軽量経路を分けるべきです。「照合は速いのに全体が遅い」ときは、照合本体ではなく結果割り当てを疑うと当たることが多いパターンです。

まとめ¶

• 照合エンジンにはバックトラッキング型とオートマトン型があり、表現力(後方参照・先読み後読み)と線形時間の保証はトレードオフの関係にある。
• JavaScript の正規表現は後方参照・後読みやキャプチャ・貪欲順序まで仕様が定めるため、バックトラッキングを基盤にし、限定できるパターンにオートマトン経路を足すのが現実的。
• バックトラッキングは破滅的バックトラッキング(ReDoS)を招きうる。探索量の上限でハングをエラーに変え、メモ化やオートマトン退避で根本的に抑える。
• パターンは照合前に一度だけコンパイルして構造をキャッシュし、照合ステップの中でパターンを再解析しない。これが複雑なパターンでの大きな高速化になる。
• 開始位置スキャンは、先頭になりうる文字やプレフィックスで候補位置を絞ると二乗走査を避けられる。特徴づけできないパターンでは安全側に全位置走査へフォールバックする。
• マッチ結果の割り当ては最小限に。照合対象の文字列は複製せず再利用し、真偽だけの経路では結果オブジェクトを作らない。
• Unicode 対応は、フラグに応じた照合単位(コード単位かコードポイントか)とケースフォールディング規則を、コンパイル時にできるだけ確定させて照合ループを軽く保つ。

参考文献¶

• ECMA-262: RegExp (Regular Expressions) — 後方参照・先読み後読み・キャプチャ・貪欲順序を含む JavaScript 正規表現の照合セマンティクスの一次資料。