Rust の新しい正規表現エンジンの設計

Andrew Gallant
2023/7/5
目次

これまで数年にわたって、私は Rust の regex クレートの書き直し (リライト) を行ってきた。この書き直しは構成要素を整理し、正確性を保った最適化を容易にするために行われた。その中で、私は regex クレートが内部で利用する機能を他のプログラムから使えるように API として公開する新しいクレート regex-automata を作成した。私の知る限り、regex-automata と同程度の詳細さで内部の機能を個別のバージョン付きライブラリとして公開する正規表現ライブラリは他に存在しない。

このブログ記事では書き直しのきっかけとなった問題、その問題が書き直しでどのように解決されるか、そして regex-automata の API を解説する。

対象読者: Rust プログラマー、そして有限オートマトンを利用する正規表現エンジンの実装に興味がある人。正規表現の経験が仮定される。

Rust の正規表現ライブラリの簡単な歴史

2012 年 9 月、正規表現ライブラリを Rust ディストリビューションに含めることを要望する issue が Rust レポジトリに作成された。そのスレッドで Graydon Hoare は「RE2 がいいと思う」とコメントしている。知らない読者のために言っておくと、RE2 は有限オートマトンを利用する正規表現エンジンである。Perl 風の構文を採用しつつ、効率的に実装できないことが知られている機能を排除することで \(O(mn)\) の最悪検索時間を保証している。RE2 の設計は作者の Russ Cox が執筆した有限オートマトンを利用する正規表現エンジンの実装に関する一連の記事で解説されている。

2014 年 4 月、私は「RE2 にインスパイアされた正規表現エンジンに取り組んでいる」と正規表現の issue スレッドにコメントした。このエンジンは Cox による記事を参考に作成された。その後、私は「Rust ディストリビューション」に正規表現ライブラリを追加する RFC を公開した。これは Rust 1.0 と Cargo (第二世代のもの、第一世代のものではない) より前のことであり、「Rust ディストリビューション」は rustc, std および様々な補助ライブラリを全てまとめたものを指していた。この RFC は regex を補助ライブラリに追加することを提案した。

10 日後、この RFC は承認された。その翌日、私は正規表現ライブラリを Rust ディストリビューションに追加する pull request (PR) を rust-lang/rust に作成した。当時は物事が素早く進んだものだ。なお、このクレートは元々 regexp と呼ばれていた。Rust レポジトリに対する PR では名前に関する議論も行われ、最終的にクレートの名前は regex となった。

2 年後の 2016 年 5 月、私は regex 1.0 をリリースする RFC を公開した。この RFC は数か月に承認されたものの、regex 1.0 が実際にリリースされたのは 2 年近く後の 2018 年 5 月だった。

regex 1.0 がリリースされるまでの間に、私は regex クレートの完全な再構成に継続して取り組んでいた。2018 年 3 月のコミットメッセージにはこうある:

[regex-syntax の] 書き直しは regex クレート全体をオーバーホールする作業の最初のフェーズとして行われた。

このメッセージを書いたころ、私は自分がこれから何をするかを正確に理解していたわけではなかった。しかし 2020 年 3 月に私は実際のマッチングエンジンを書き直す作業に本腰を入れて取り組み始めた。それから 3 年と少しが経過した 2023 年 7 月、書き直しが完了した regex 1.9 がリリースされた。

regex クレートが抱えていた問題

regex クレートはどのような問題に直面していたために、完全な書き直しが必要になったのだろうか？ また、書き直された内部機能が個別のクレートとして公開されたのはどうしてだろうか？

この疑問に答えるには、様々な話題に言及しなければならない。

問題: 異なる戦略の合成が難しい

RE2 の手法に習い、regex クレートには検索で利用できる戦略がいくつか実装されている。一つの検索処理で複数の戦略が利用されることもあり得る。

それぞれの戦略は、互いに対立することが多い二つの次元で異なる地点に存在する: パフォーマンスと機能である。例えば高速な戦略はマッチの開始地点と終了地点を報告できても、正規表現に含まれる各キャプチャグループに対するオフセットは報告できないかもしれない。逆に、遅い戦略なら各キャプチャグループのオフセットを報告できるだろう。

私が最初に regex クレートを書いたときに実装した戦略は一つだけ (PikeVM) で、全体の設計は他の戦略を取り入れる方法を全く考慮していなかった。その後ライブラリが進化するにつれて、いくつかの新しい戦略が「有機的に」追加された:

(これらの戦略がここに示したトレードオフを持つ理由は記事の後半で説明される)

こういった戦略は次のように合成された:

時が経つにつれ、私は実装される戦略とそれらを合成する手法の両方を増やしたいと思うようになった。しかし「有機的に」成長したインフラストラクチャを持つ regex クレートは、自重に押し潰されつつあった。大まかに言うと、次の点が問題だった:

簡単に言えば、どんなに作業量を少なく見積もっても、戦略の多くは作り直しが必要であり、戦略を組み合わせるインフラストラクチャは書き直しが必要だった。

問題: テストが難しい

これまで議論してきたように、regex クレートは単一の正規表現エンジンとして振る舞うパブリックインターフェースを公開しつつ、内部では与えられた正規表現に応じて複数の戦略を使い分ける。これらの戦略の多くはそれ自身が正規表現エンジンなので、それらが同じ入力に対して同じ振る舞いをすることが絶対不可欠となる。

一つ例を示すと、呼び出し元がマッチに含まれるキャプチャグループのオフセットを要求することがよくある。通常、この状況では最初に lazy DFA を実行してマッチの境界を見つけ、その後 PikeVM や BoundedBacktracker といった低速な正規表現エンジンをマッチの範囲を入力として実行することでキャプチャグループのオフセットを見つける。もし lazy DFA が見つけたマッチが他の戦略によってマッチとみなされなかったらどうなるだろうか？ おっと、これはバグだ。

ここでの問題は、regex 1.9 より前のバージョンにおいて、内部で使われる戦略がパブリック API と関係を持たないために独立してテストするのが難しいことである。パブリック API は当然テストできる。しかし正規表現と内部で使われる正規表現エンジンの間に明確で分かりやすい対応付けがあるほどには正規表現エンジンの選択ロジックが単純でない。さらに、そのロジックが更新されれば対応付けも変化する。そのためパブリック API に対するテストだけで内部の正規表現エンジン全てに対する高いカバレッジを得るのは難しい。加えて、パブリック API を使ってテストを書くと、失敗したテストのデバッグが不必要に難しくなる: 戦略を選択するロジックにも頭を悩ませなければならない。

一つのアプローチとして、テストを全てクレートの中に押し込んで、それぞれの戦略が持つ内部 API にテストからアクセスできるようにする方法が考えられる。同じテストを全てのエンジンで使いたいはずなので、このときはテストを何らかの構造化されたフォーマットで書き、それを読み込んで各エンジンをテストすることになる。テストのインフラストラクチャが個別の戦略をテストするものとして書かれていなかったことから、私はこの方法を採用しなかった。

その代わり、私は既存のテストスイートを動作させるために不道徳なハックをした:

これはハックだらけのごちゃごちゃしたコードであり、明らかに再考が必要だった。内部で使うエンジンを個別のパブリック API として公開することが状況を改善するために絶対に必要なわけではないものの、こうしておけばドキュメントされない API に頼ったりテストをクレートの中に入れたりせずに同じテストスイートを全てのエンジンに対して実行できるようになる。

問題: ニッチな API への要望

regex クレートを公開してから、API を追加してほしいというリクエストが何件かあった。しかし、その中には API を拡張するにはニッチすぎる、あるいは API をどのようにすべきかが明らかでないと感じるリクエストも存在した。

最も頻繁にリクエストされた機能の一つが多パターン検索の改善だった。元々 regex クレートはゼロ個以上の正規表現のマッチを (重なりを許して) 検索する RegexSet という API を提供していた。ただ、この API が「検索対象文字列でマッチしたパターンはどれか」だけしか報告できないことが問題だった。マッチのオフセットやキャプチャグループのオフセットは RegexSet の API では取得できない。そのため RegexSet は便利ではあるものの、Regex と同じだけの API をサポートすればもっと便利になる。

しかし、複数の正規表現エンジンへの対応やそのテストと同様に、RegexSet の API も既存の実装にハックじみた方法で追加されていた。そのためマッチのオフセットを報告可能にするには、既存のエンジン全ての大規模なリファクタリングもしくは書き直しが必要になると思われた。

これとは別に、RegexSet の API が行う重なりを許すマッチの検索の文脈でマッチのオフセットを報告する API をどのように公開すべきかが私には完全に明らかではなかった。他の API (例えば重ならないマッチを検索してマッチのオフセットを報告する検索) に切り替える余地を残す方が、多くの人にとって便利で、regex クレートの API が単純に保たれるかもしれない。

多パターン検索の他にも、次の API の追加が望まれた:

regex クレートの内部機能の大部分をバージョン付きの新しい個別クレートとして公開することで、正規表現のユースケースの圧倒的大部分を解決する汎用の正規表現 API を複雑にすることなく、一部のユーザーが自身の望む特別な API を実装するための「空き部屋」を提供できるだろうと私は考えている。つまり、新しいクレートは「専門的な」ユースケースを対象としたものであり、API を小さく単純に保つことは目標とされない。実際、これから見るように、regex-automata は乱雑で複雑な API を持つ。また、新しいライブラリに個別のバージョンを付ければ、破壊的変更を伴うリリースを regex クレートより格段に速いペースで行えるようになる。

以上の思考の道筋は、regex-syntax クレートを公開するときにたどったものと似ていると言える。このとき、人々 (私を含む) は自身のプロジェクトから正規表現パーサーにアクセスすることを望んでいた。しかし、regex クレートそのものからパーサーを公開するのは絶対に避けたいと私は感じていた。なぜなら、そうするとクレートが複雑になる上に、パーサーの処理やデータ型は regex と独立に進化させたいと私は思っていたからである (つまり、regex-syntax には regex より頻繁に破壊的変更が行われる)。パーサーを個別のクレートとすれば、そのコードを regex の実装詳細として使いながらも、他の人々が利用できるようになる。

問題: fully compiled DFA の構築

厳密に言うと、regex-automata クレートは正規表現ライブラリを書き直す一連の大作業の結果として生まれたものではない。このクレートは fully compiled DFA の構築を可能にするために作成された。この機能があると、正規表現の検索で用いる DFA を事前に完全にコンパイルした上でシリアライズし、実行時にはゼロコピーのデシリアライズで最低限の速度を持った検索が可能な DFA を手に入れることができる。私は bstr で必要になった様々な Unicode アルゴリズムを実装するとき、オリジナルバージョンの regex-automata を使って DFA を構築した。

最初のバージョンの regex-automata を作る中で、NFA のデータ構造と NFA のコンパイラがregex クレートに含まれるものによく似ていることに私は気が付き、コードを共有できるのではないかと考え始めた。NFA に関するコードは興味深い最適化が多く加えられる全く非自明なコードなので、共有する価値はある。

regex と regex-automata の両方が依存する regex-nfa のような名前の新しいクレートを作る選択肢も頭をよぎったものの、少し考えると regex-automata と regex で多くのコードを共有できる事実が明らかになった。例えば、DFA の構築処理は fully compiled DFA と lazy DFA の両方で動作するように一般的に書くことができる。

この時点で新しいクレートは「NFA」というよりは「正規表現エンジン」に関するものになっているように思えた。そこで私はクレートの名前を regex-automata として、そこに含まれるのが純粋な NFA に関するコードではなく正規表現エンジンの一部であることが強調されるようにした。このときの大まかな計画は、正規表現エンジンの全てを regex-automata に移し、regex は regex-automata の薄いラッパーにするというものだった。このようにコードを構成すれば、低レベル API へのアクセスが必要な場合でも regex から regex-automata に移行する手間が削減される。

こうすると、regex クレートが lazy DFA を構築するときに使うのと全く同じコードで fully compiled DFA を構築できる。パースされた正規表現から NFA を構築するコードも同様となる。さらに、regex で fully compiled DFA を利用することさえ可能になる。 (なお、fully compiled DFA は多くのメモリを消費するだけではなく構築に指数的な時間がかかるので、汎用の正規表現エンジンで使ってはいけない。信頼できないパターンをコンパイルする正規表現エンジンでは非常に不適切となる。それどころか、正規表現のコンパイル時間を「それなりに短く」保ちたいと思っているだけの場合でも適切でない。特に Unicode が関係するときは、DFA の構築に非常に長い時間がかかる可能性がある。)

regex-cli の使い方

regex-cli は regex クレートの一部として公開されているプログラムであり、regex-syntax, regex-automata, regex が公開する様々な API に対するコマンドラインを使った簡単なアクセスを提供する。regex-cli には他にも「fully compiled DFA のファイルへのシリアライズと、それを読み込む Rust コードの生成」といった便利なユーティリティも含まれている。

ここからは regex-cli を使って正規表現エンジンの動作を解説する。自分で試したい場合は、次のコマンドでインストールできる:

$ cargo install regex-cli

正規表現 . の検索を行うとき Unicode に対応するかどうかで処理がどれだけ変わるかを示す例を示す。まず、Unicode に対応する場合は次の出力が得られる:

$ regex-cli debug thompson '.' --no-table

thompson::NFA(
>000000: binary-union(2, 1)
000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 10
000003: \x80-\xBF => 11
000004: \xA0-\xBF => 3
000005: \x80-\xBF => 3
000006: \x80-\x9F => 3
000007: \x90-\xBF => 5
000008: \x80-\xBF => 5
000009: \x80-\x8F => 5
000010: sparse(\x00-\t => 11, \x0B-\x7F => 11, \xC2-\xDF => 3, \xE0 => 4, \xE1-\xEC => 5, \xED => 6, \xEE-\xEF => 5, \xF0 => 7, \xF1-\xF3 => 8, \xF4 => 9)
000011: capture(pid=0, group=0, slot=1) => 12
000012: MATCH(0)

transition equivalence classes: ByteClasses(0 => [\x00-\t], 1 => [\n], 2 => [\x0B-\x7F], 3 => [\x80-\x8F], 4 => [\x90-\x9F], 5 => [\xA0-\xBF], 6 => [\xC0-\xC1], 7 => [\xC2-\xDF], 8 => [\xE0], 9 => [\xE1-\xEC], 10 => [\xED], 11 => [\xEE-\xEF], 12 => [\xF0], 13 => [\xF1-\xF3], 14 => [\xF4], 15 => [\xF5-\xFF], 16 => [EOI])
)

次に、Unicode に対応しないと次の出力が得られる:

$ regex-cli debug thompson '(?-u:.)' --no-table --no-utf8-syntax

thompson::NFA(
>000000: binary-union(2, 1)
000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 3
000003: sparse(\x00-\t => 4, \x0B-\xFF => 4)
000004: capture(pid=0, group=0, slot=1) => 5
000005: MATCH(0)

transition equivalence classes: ByteClasses(0 => [\x00-\t], 1 => [\n], 2 => [\x0B-\xFF], 3 => [EOI])
)

ここで出力されているのは、regex-automata が正規表現 . をコンパイルして構築した Thompson NFA である。regex-cli debug コマンドは正規表現クレートのエコシステムが持つ様々なデータ型を出力できる:

$ regex-cli debug
Prints the debug representation of various things from regex-automata and
regex-syntax.

This is useful for ad hoc interactions with objects on the command line. In
general, most objects support the full suite of configuration available in code
via the crate.

USAGE:
regex-cli debug <command> ...

COMMANDS:
ast        Print the debug representation of an AST.
dense      Print the debug representation of a dense DFA.
hir        Print the debug representation of an HIR.
literal    Print the debug representation of extracted literals.
onepass    Print the debug representation of a one-pass DFA.
sparse     Print the debug representation of a sparse DFA.
thompson   Print the debug representation of a Thompson NFA.

アドホックに検索を行う regex-cli find コマンドも存在する。例えば、メタ正規表現エンジンを使ったキャプチャグループ付き多パターン検索は次のように行える:

$ regex-cli find capture meta \
    -p '(?<email>[.\w]+@(?<domain>[.\w]+))' \
    -p '(?<phone>(?<areacode>[0-9]{3})-[0-9]{3}-[0-9]{4})' \
    -y 'foo@example.com, 111-867-5309'
parse time:  20.713µs
translate time:  22.116µs
build meta time:  834.731µs
search time:  142.537µs
total matches:  2
0:{ 0: 0..15/foo@example.com, 1/email: 0..15/foo@example.com, 2/domain: 4..15/example.com }
1:{ 0: 17..29/111-867-5309, 1/phone: 17..29/111-867-5309, 2/areacode: 17..20/111 }

その他の例については regex-cli の README を参照してほしい。

データの流れ

詳細に入る前に、用語をいくつか定義して、正規表現エンジンにおけるデータの流れを簡単に説明した方がいいだろう。つまり、パターン文字列を渡して Regex::new を呼び出したとき、パターン文字列を実際に検索で利用する何かに作り変えるまでの間に施される変換をこれから説明する。

こうした要素は本記事を通して一つずつ説明されるのだが、ある要素の説明中にまだ説明されていない他の要素を参照しなければならない場合もある。このため、regex クレートの内部要素に関する非常に大まかな概観をここで与えておいた。

リテラル最適化

この節では、regex クレートの内部要素を巡る旅を始めるにあたって、とある非常に重要な最適化テクニックについて話をする: 正規表現からリテラルを抽出する処理である。例えば、正規表現 (foo|bar|quux)(\s+\w+) が表す正規言語に属する文字列は、全て foo, bar, quux のいずれかで始まる。つまり、この正規表現にマッチする文字列は必ず三つのリテラルのいずれかで始まることが保証される。

リテラル最適化が必要な理由

なぜリテラルが重要なのだろうか？ リテラルに注目する理由として、次の観察がある:

  1. 一つあるいは少数のリテラルを検索する非常に高速なアルゴリズムが知られている。この速度は、飾りのないリテラルを検索するという問題の単純さを活用し、さらにベクトル演算を使って検索対象文字列の複数バイトを一度に処理することで達成される。
  2. 非常に大まかに言って、正規表現のマッチを検索する一般的なアルゴリズムはどれも簡単には高速化できない。

つまり「正規表現エンジンを実装するテクニックには様々なものが存在する (本記事でもいくつか説明される) ものの、ベクトル演算を使う最適化された部分文字列検索と同程度の速度を一貫して達成するものはその中に一つもない」という事実が重要となる。私の経験では、実際の検索で速度の差が一桁かそれ以上になることがよくある。

リテラル抽出

いくつか例を見よう。ここでは regex-cli が利用できる。regex-cli debug literal サブコマンドは正規表現から抽出されたリテラルを表示する。最初は単純な例を試そう:

$ regex-cli debug literal 'bar'
parse time:  13.967µs
translate time:  7.008µs
extraction time:  405ns
optimization time:  1.479µs
len:  Some(1)
is finite?:  true
is exact?:  true
min literal len:  Some(3)
max literal len:  Some(3)
longest common prefix:  Some("bar")
longest common suffix:  Some("bar")

E("bar")

以降では、最後の行以外に示された追加情報を省略する。これらの行の意味は次の通りである:

これらのメタデータの後に、抽出されたリテラル列が示されている。今の例では正規表現がリテラル bar なので、抽出されたリテラル列も完全 (E) なリテラル bar だけからなる。もし bar の後ろに文字が続くなら、抽出される bar は不完全 (I) になる:

$ regex-cli debug literal --no-table 'bar+'
I("bar")

この例では r が一回以上反復されるので、bar は不完全となる。実は、回数に上限の無い反復が空でない文字列に適用されるとき正規表現が表す言語は必ず無限となる。そのため全てのリテラルを枚挙することはできず、抽出される一部のリテラルは必ず不完全となる (リテラルが抽出されない可能性もある)。

ただし、正規表現が表す言語が無限でなくても抽出されるリテラルが不完全になることはある。有限の言語を表す正規表現から不完全なリテラルが抽出される例を次に示す:

$ regex-cli debug literal --no-table 'bar[a-z]'
I("bar")

この例で、リテラル抽出処理はマッチするリテラル bara, barb, barc, …, barz を全て抽出することもできる。しかし実際にはそうなっていない。なぜだろうか？ リテラル抽出は一つの大きなヒューリスティックだから、というのが理由である。「黒魔術」と呼んでもいいかもしれない。この事実を理解するには、リテラル抽出を行うそもそもの理由を思い出す必要がある: 検索対象文字列に含まれるマッチの候補を素早く見つけ、見つかった候補にだけ低速な正規表現エンジンを使うためにリテラル抽出は存在する。

リテラル抽出では、「どのリテラルで検索するか」の選択が「どうやってリテラルを検索するか」の選択と同程度に重要となる。極端なことを言えば、検索する正規表現がリテラル a で検索対象文字列が 100 万個の a のとき、世界で最もスループットの高いリテラル検索アルゴリズムを使っても役には立たない。優れたリテラル最適化は次の特徴を持つ必要がある:

私がリテラル最適化を「黒魔術」と呼んだのは、これら二つの要件を満たす最適なリテラルを検索開始前に選ぶことが不可能だからである。二つの要件はどちらも検索対象文字列に依存しており、検索をする前に検索対象文字列を走査して「知識」を得ようとすれば間違いなく検索時間に悪い影響が出る。そのため、偽陽性の可能性を最小化しつつレイテンシを削減するリテラルは推測するしかない。このためリテラル抽出は「黒魔術」と言える。

しかし幸いにも、次のガイドラインに従っておけば多くの場合で優れた結果が得られる:

リテラル抽出処理は可能な限りこれらのガイドラインに従うものの、異なるヒューリスティックも採用する。例えば、 ASCII の空白文字 U+0020 は他の文字に比べて検索対象文字列に現れる頻度が格段に高い。そのためリテラル列からスペースだけのリテラルを排除できない場合、最適化でリテラル列は「無限」となり、事実上リテラル最適化が無効化される。例えば、正規表現 (?:foo|z|bar)[a-z]+ からは三つの接頭辞リテラルが抽出される:

$ regex-cli debug literal --no-table '(?:foo|z|bar)[a-z]+'
I("foo")
I("z")
I("bar")

これに対して、z をスペース に変えた正規表現からはリテラルが抽出されない:

$ regex-cli debug literal --no-table '(?:foo| |bar)[a-z]+'
Seq[∞]

このヒューリスティックはリテラル列に対する「最適化」パスで実行される。このパスはリテラル列に空白文字だけのリテラルが含まれると偽陽性率が上がると仮定し、リテラル列を無限に変更する。無限のリテラル列は「優れたプリフィルタとして利用できるリテラルの有限集合は存在しない (ように思える)」ことを伝える。最適化を無効にすると、空白文字がリテラル列に含まれることが確認できる:

$ regex-cli debug literal --no-table --no-optimize '(?:foo| |bar)[a-z]+'
I("foo")
I(" ")
I("bar")

さらに処理を複雑にする要素として、少数の完全なリテラルだけからなるリテラル列が抽出される場合には、最適化後のリテラル列に空白文字だけのリテラルが含まれる:

$ regex-cli debug literal --no-table 'foo| |bar'
E("foo")
E(" ")
E("bar")

こうしておけば正規表現エンジンの利用を完全に避けられる。このケースではプリフィルタは必要とならず、多文字列検索のアルゴリズムを使って直接マッチを報告できる。そのためリテラル検索が発見するマッチは全て本当のマッチであり、偽陽性率が高いかどうかは問題とならない。

ここで、リテラル抽出処理の出力をリテラル列 (literal sequence) と呼び、リテラル集合 (literal set) と呼んでこなかった理由を説明する。一言で言えば、抽出されたリテラルの順番に意味があるからである。regex クレートは Perl と同じ正規表現の意味論に従おうとする: つまり、バックトラッキングのアルゴリズムを使ったかのようにマッチを報告する。この意味論は leftmost-first と呼ばれ、この文脈では | 演算子が非可換となる。そのため、次のような現象が発生する:

$ regex-cli debug literal --no-table 'sam|samwise'
E("sam")

$ regex-cli debug literal --no-table 'samwise|sam'
E("samwise")
E("sam")

抽出されたリテラル列は異なり、それぞれは対応する正規表現 sam|samwise と samwise|sam に対応する最小のリテラル列である。前者の正規表現 sam|samwise は sam としかマッチしない: sam は samwise の接頭辞であり、正規表現で sam が samwise より前にあるので優先される。samwise はマッチを生成しないので、sam だけから構成されるリテラル列は正しい。これに対して、後者の samwise|sam は sam と samwise の両方にマッチする。sam は samwise の接頭辞であるものの、正規表現で samwise が先に現れるので、検索対象文字列に samwise があればそれがマッチとして報告される。

(余談: POSIX の正規表現エンジンは正規表現をこのようには実装しない。POSIX の正規表現エンジンは leftmost-longest と呼ばれる意味論を持ち、長いマッチが必ず勝つ。この文脈では、| が可換な演算子となる。正規表現エンジンの中には他にも、例えば Hyperscan のように、「マッチを全て報告する」意味論を採用するものもある。この意味論では、正規表現 abc|a で abc を検索すると、a と abc の両方が報告される。)

最後に、リテラル抽出がいくらか「知的な」処理を行うことが分かる例を示す:

$ regex-cli debug literal --no-table 'abc?de?[x-z]ghi'
I("abcde")
I("abcdx")
I("abcdy")
I("abcdz")
I("abdex")
I("abdey")
I("abdez")
I("abdxg")
I("abdyg")
I("abdzg")

リテラル抽出処理は ? といった演算子や小さな文字クラスの処理方法を知っていることがここから分かる。こういった展開はリテラル列の長さが演算子と操作ごとにヒューリスティックに基づいて決められた閾値に達するまで行われる。この例でリテラル抽出は正規表現 abc?de?[x-z]ghi が表す全てのリテラルを枚挙することもできるものの、ヒューリスティックによる枝刈りが行われている。

もう一つの「知的な」処理に大文字と小文字の同一視がある。特殊な大文字や小文字が Unicode で定義されている場合があるものの、この事実を crate クレートは知っている:

$ regex-cli debug literal --no-table '(?i)She'
E("SHE")
E("SHe")
E("ShE")
E("She")
E("sHE")
E("sHe")
E("shE")
E("she")
E("ſHE")
E("ſHe")
E("ſhE")
E("ſhe")

正確に言うと、この結果が得られるのは Unicode の case folding がリテラル抽出で実装されているためではなく、Ast から Hir への変換で case folding が起こるためである:

$ regex-cli debug hir --no-table '(?i)She'
Concat(
    [
        Class(
            {
                'S'..='S',
                's'..='s',
                'ſ'..='ſ',
            },
        ),
        Class(
            {
                'H'..='H',
                'h'..='h',
            },
        ),
        Class(
            {
                'E'..='E',
                'e'..='e',
            },
        ),
    ],
)

つまり、この正規表現はリテラル抽出処理に渡される時点で [Ssſ][Hh][Ee] に等しい表現であり、この表現を展開する処理に特別なところはない。

リテラル検索

リテラルの抽出が終わると、続いてリテラルを検索する方法が問題となる。

リテラルが一つだけなら、その検索は難しくない: 最速の単一文字列検索アルゴリズムを使えばそれで済む。それ以外に工夫の余地は特にない。リテラルが一つしかないので、その順序を気にする必要もない。このケースで regex クレートは、memchr クレートの memmem モジュールを利用する。

memchr::memmem では、いくつかの異なるアルゴリズムが利用される:

generic SIMD アルゴリズムを使うときは、検索文字列の最初の 2 バイトを決め打ちで選ぶのではなく、事前に用意されたバイトの頻度分布に基づいて「レア」だと判断された 2 バイトを選ぶようになっている。例えば、バイト Z はバイト a より格段に頻度が低いと仮定される。これが常に正しいわけではないものの、そもそも今考えているのはヒューリスティックである: この仮定は十分多くのケースで正しい。検索対象文字列に現れる可能性が低いと思われるバイトを選ぶことで、ベクトル演算でマッチ候補を探す時間を最大化し、完全な検索の回数を最小化することが期待されている。

多文字列検索は多少これより複雑になる。検索するのはリテラルの列なので、前に現れるリテラルのマッチを後に現れるリテラルのマッチより優先しなければならない。一般に多文字列検索は単一文字列検索より低速になる: 単純に多くの処理が必要なためである。regex クレートで使われるメインの多文字列検索アルゴリズムは Teddy と呼ばれる。これは Hyperscan で使われているアルゴリズムであり、私が Rust に移植した。高いレベルで言うと、Teddy はベクトル演算を利用してマッチ候補を素早く見つけ、それからマッチ候補が本当にマッチかどうかを確認する検証ステップを実行する。

一部のケースでは Aho-Corasick が使われる。ただし、Aho-Corasick のパフォーマンスは lazy DFA とあまり変わらないので、正規表現エンジンは lazy DFA の構築を優先することが多い。Aho-Corasick の利点としては、lazy DFA が使えないケースでもプリフィルタとして使えることがある。また、リテラルの個数が極端に多い (数万におよぶ) ときは Aho-Corasick が lazy DFA より高速になる場合が多い。

多文字列検索に関しては、これからやりたいと思っていることが多くある。

NFA を表すデータ型

regex クレートに中心的なデータ型があるとすれば、それはおそらく NFA だろう。具体的に説明すると、NFA は Thompson's NFA を実装する型であり、Thompson の構築アルゴリズムで構築される。このアルゴリズムは正規表現の構造化された表現から NFA を \(O(m)\) 時間で構築する。ここで \(m\) は回数が指定された反復を展開した (例えば a{5} を aaaaa とした) 後の正規表現のサイズを表す。このアルゴリズムでは、正規表現のプリミティブそれぞれに対応するミニ NFA を定義して、正規表現に対応するミニ NFA 列を連結して一つの大きな NFA にすることで構築が行われる。

NFA が中心的なデータ型とみなせるのは、正規表現エンジンの実装でそのまま使われるためである。ただし、NFA は他のデータ型 (例えば DFA) に変換してから利用する正規表現エンジンも考えられる。現時点において、regex-automata を使って新しい正規表現エンジンを実装するときは NFA の構築から処理を始める必要がある。

NFA の詳細を説明する前に、簡単な例を見てみよう:

簡単な NFA を使った例

リテラル抽出と同様に、regex-cli を使うと特定の正規表現に対して構築される NFA をデバッグに便利な表現で出力できる:

$ regex-cli debug thompson 'a'
parse time:  9.856µs
translate time:  3.005µs
compile nfa time:  18.51µs
memory:  700
states:  6
pattern len:  1
capture len:  1
has empty?:  false
is utf8?:  true
is reverse?:  false
line terminator:  "\n"
lookset any:  ∅
lookset prefix any:  ∅
lookset prefix all:  ∅

thompson::NFA(
>000000: binary-union(2, 1)
000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 3
000003: a => 4
000004: capture(pid=0, group=0, slot=1) => 5
000005: MATCH(0)

transition equivalence classes: ByteClasses(0 => [\x00-`], 1 => [a], 2 => [b-\xFF], 3 => [EOI])
)

以降では NFA を表す部分だけを示し、それ以外の部分を省略する。省略される情報の意味は次の通りである:

これらの情報の他に、regex-cli debug thompson の出力には NFA の持つ状態と遷移が示されている:

>000000: binary-union(2, 1)
000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 3
000003: a => 4
000004: capture(pid=0, group=0, slot=1) => 5
000005: MATCH(0)

状態 000002 の前に付いている ^ は「アンカーが付いた」開始状態を表し、状態 000000 の前に付いている c は「アンカーが付かない」開始状態を表す。前者は NFA の構築に使われた正規表現のアンカー付き検索を行うときに使われ、後者はアンカーを付けない (通常の) 検索で使われる。

アンカーを付けない検索は binary-union(2, 1) の状態から始まる。これは NFA の走査処理が最初に状態 2 からの遷移を最初に試し、このパスが失敗したときに限って状態 1 からの遷移を試すことを意味する。この例では状態 1 が任意のバイトとマッチして状態 0 に遷移する。このため事実上、状態 0 と状態 1 が正規表現の最初に暗黙に付けられた (?s-u:.)*? を表す。これはマッチが検索対象文字列の任意の位置に現れることを意味する。

capture と書かれている状態は無条件のイプシロン遷移を表し、副作用を発生させるためだけに存在する: そういった状態に到達すると、NFA を実行する仮想マシンは現在のオフセットを capture の引数が示すスロットに保存する。VM を使わない NFA の走査では capture 状態は無視され、副作用を持たない無条件のイプシロン遷移となる。例えば、NFA の決定化 (DFA に変換する処理) ではそのように扱われる。

遷移中に状態 3 に達したなら、現在読んでいる位置のバイトが a かどうかを判定し、もしそうなら状態 4 に遷移する。それから状態は 5 に遷移し、この状態が識別子 0 のパターンとのマッチを表す。

NFA の最適化: sparse 命令

Thompson NFA が持つ大きな問題の一つは、Thompson NFA を汎用正規表現の構成要素として適切な選択肢とする特徴から生じる: 構築の最悪計算時間は \(O(m)\) であるものの、構築される NFA にはイプシロン遷移が多く含まれる。イプシロン遷移とは、入力を消費せずに行われる遷移を言う。遷移をシミュレートするとき同時に追跡しなければならない NFA の状態が増える二つの要因の一つがイプシロン遷移である (もう一つの要因は同じシンボルに対する遷移を複数持つ状態)。

どうしてイプシロン遷移が問題なのだろうか？ NFA の走査を (検索のためであれ DFA 構築のためであれ) 行うとき、イプシロン遷移が一つあるごとに必ずコストが増加するからである。特に、全ての NFA 状態に対してはイプシロン閉包 (epsilon closure) と呼ばれる「イプシロン遷移を再帰的に行うことで到達可能な状態の集合」が定義される。^, $, \b といったアンカーアサーションが使われると条件付きのイプシロン遷移が生まれるので、特定の状態のイプシロン閉包は走査中に変化し、再計算が必要になる。

新しい NFA コンパイラで私が実装した比較的単純な最適化を確認してみよう。まず、regex < 1.9 は [A-Za-z0-9] を次のようにコンパイルする:

$ regex-debug compile --bytes '[A-Za-z0-9]'
0000 Save(0) (start)
0001 Split(2, 3)
0002 Bytes(0, 9) (goto: 6)
0003 Split(4, 5)
0004 Bytes(A, Z) (goto: 6)
0005 Bytes(a, z)
0006 Save(1)
0007 Match(0)

(注意: regex-debug は古い雑なバージョンの regex-cli であり、regex-cli と同様にクレートの内部で使われるデータ構造を確認するのに利用できる。最新バージョンに regex-debug は含まれないものの、regex クレートの古いタグをチェックアウトしてビルドすれば利用できる。)

Split は二つのイプシロン遷移を表す命令であり、一つ前の例における binary-union 命令に対応する。Save 命令はグループのキャプチャを行い、Bytes 命令は単一のバイトまたはバイトの連続領域が現在読み込んでいる文字とマッチするかどうかの判定を行う。この例では、文字クラス [A-Za-z0-9] の検索がいくつかの Split 命令で実装されている。Save 命令は一つ後ろの状態へのイプシロン遷移でもあるので、状態 0 のイプシロン閉包は {1, 2, 3, 4, 5} となる。

続いて、新しい NFA コンパイラが同じ正規表現をどのようにコンパイルするかを見よう:

$ regex-cli debug thompson --no-table '[A-Za-z0-9]'
thompson::NFA(
>000000: binary-union(2, 1)
000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 3
000003: sparse(0-9 => 4, A-Z => 4, a-z => 4)
000004: capture(pid=0, group=0, slot=1) => 5
000005: MATCH(0)
)

(マッチが接頭辞かどうかのチェックを行う状態 0 と 1 は無視して構わない。古いバージョンの NFA は接頭辞のチェックを持たないが、この理由は現在の議論に関係ない。)

新しいバージョンでは NFA がイプシロン遷移を持たず、代わりに sparse 命令を持つ状態を一つだけ持つ。sparse という名前は、この命令がバイトの連続領域を複数チェックできる (そして連続領域のそれぞれに遷移先を別々に設定できる) 事実から来ている。sparse が使われるのは、検索対象文字列中の特定のシンボルが (失敗遷移でない) 遷移を持つかどうかの判定を定数時間で行えるように正規表現の表現がなっていないためである (つまり、線形探索または二分探索が必要になる)。sparse 命令は古い NFA におけるいくつかの Bytes 命令を置き換えるものであるものの、イプシロン遷移が使われない。こうすると Split 命令をたどってイプシロン閉包を計算する必要がなくなるので、オーバーヘッドが減少する。この例で状態は一つだけであり、遷移先の状態は現在のシンボルがどの領域に属するか (それともいずれにも属さないか) を確認するだけで決定できる。

この特定の最適化が持つ欠点としては、sparse 命令のサポートに (現在使われている NFA の表現では) 間接参照が必要なことがある。キャッシュヒットが減ってパフォーマンスが低下したり、一部のケースでヒープメモリの使用量が増えたりする可能性がある。しかし実際の検索では、全てのイプシロン遷移を処理するオーバーヘッドがこれらの欠点より重大なことが多い。将来この間接参照が削除される可能性もある。

NFA の最適化: 最小 UTF-8 オートマトン

旧型の NFA コンパイラが持つ興味深い特徴として、二つの異なる NFA を生成できることがある: Unicode の符号位置をアルファベットとする NFA (Unicode NFA) と、任意のバイトをアルファベットとする NFA (バイト指向 NFA) を生成できる (バイト指向 NFA では、正当な UTF-8 文字列に決して現れない \xFF などの UTF-8 の符号単位として無効なバイトもアルファベットに含まれる)。Unicode NFA は NFA ベースの正規表現エンジン (後述する PikeVM や BoundedBacktracker など) で主に利用され、バイト指向 NFA は lazy DFA エンジンが使われるとき必ず利用される。バイト指向 NFA が lazy DFA で必要となるのは、lazy DFA がバイトのアルファベットを要求するためである。アルファベットがバイトでないと、困難なパフォーマンスの問題が発生する。また、NFA ベースの正規表現エンジンでバイト指向 NFA を使うことはできるものの、実際に使われるのは UTF-8 文字列として不当なバイト列を検索するときに限られる。このときは Unicode をアルファベットとする NFA は利用できない。

このとき、少なくとも三つの問題が発生する。第一に、バイト指向 NFA は低速なことが多い。前節で説明したイプシロン遷移に関する問題が悪化するためである。つまり、典型的なケースでバイト指向 NFA は Unicode NFA より多くの Split 命令を持つ。これに対して Unicode NFA は新しい NFA コンパイラにおける sparse と同じような命令を持つことができる。この事実は次の例からも分かる:

$ regex-debug compile '[A-Za-z0-9]'
0000 Save(0) (start)
0001 '0'-'9', 'A'-'Z', 'a'-'z'
0002 Save(1)
0003 Match(0)

一つ前の例と同じ正規表現を Unicode NFA にコンパイルするとき、Split 命令が一つも生成されないことに注目してほしい。

二つ目の問題は一つ目の問題から生じる。バイト指向 NFA は多くの場合で低速なので、メタ正規表現エンジンは Unicode NFA とバイト指向 NFA の両方をコンパイルすることになる。こうすると、 Unicode NFA を NFA ベースの正規表現エンジンで使いつつ、バイト指向 NFA を lazy DFA で使うことができる。これは問題なく動作するものの、無駄が多い。

三つ目の問題は、NFA ベースの正規表現エンジンが Unicode NFA とバイト指向 NFA の両方に対応しなければならないことである。これによってコードが複雑になり、これまでバグの温床となってきた。優れた設計を導入すれば問題を多少は緩和できるかもしれないが、コードが複雑になるのは避けられない。

こういった問題が「UTF-8 オートマトン」と何の関係があるのだろうか？ バイト指向 NFA であっても Unicode クラスを扱える必要がある。しかしアルファベットが符号位置ではなくバイトのとき、どうしているのだろうか？ このときは、UTF-8 オートマトンが NFA に組み込まれる。例えば、次に示すのは任意の Unicode スカラー値をエンコードしたバイト列にマッチする NFA (新しい NFA コンパイラが生成するもの) である:

$ regex-cli debug thompson --no-table '(?s:.)'
thompson::NFA(
>000000: binary-union(2, 1)
000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 10
000003: \x80-\xBF => 11
000004: \xA0-\xBF => 3
000005: \x80-\xBF => 3
000006: \x80-\x9F => 3
000007: \x90-\xBF => 5
000008: \x80-\xBF => 5
000009: \x80-\x8F => 5
000010: sparse(\x00-\x7F => 11, \xC2-\xDF => 3, \xE0 => 4, \xE1-\xEC => 5, \xED => 6, \xEE-\xEF => 5, \xF0 => 7, \xF1-\xF3 => 8, \xF4 => 9)
000011: capture(pid=0, group=0, slot=1) => 12
000012: MATCH(0)
)

この NFA のコンパイルでは Unicode 符号位置の領域を UTF-8 エンコードしたバイト列の集合に変換する処理が行われる。この処理は regex-syntax クレートの utf8 モジュールが行う。例えば、(?s:.) は次のバイト列の集合に等しい:

[0-7F]
[C2-DF][80-BF]
[E0][A0-BF][80-BF]
[E1-EC][80-BF][80-BF]
[ED][80-9F][80-BF]
[EE-EF][80-BF][80-BF]
[F0][90-BF][80-BF][80-BF]
[F1-F3][80-BF][80-BF][80-BF]
[F4][80-8F][80-BF][80-BF]

これを NFA に変換するときは、単純に全てのバイト列の論理和 (alternation) が取られる:

[0-7F]|[C2-DF][80-BF]|...|[F4][80-8F][80-BF][80-BF]

この正規表現を使えば正しくマッチが行える。しかしこの方式には、頻出するケースで非常に大きな NFA が生成される問題がある。つまり、正規表現において Unicode には極端に大きな文字クラスを簡単に書けてしまう問題がある。例えば Unicode の文字クラス \w には (執筆時点で) 139,612 個の異なる符号位置が含まれる。これに対して ASCII バージョンの \w には 63 個の符号位置しか含まれない。この差異は質的であり、63 のような小さい数に対して上手く動作するトリックの多くは、139,612 のような数にまでスケールしない。

古い regex クレートが UTF-8 オートマトンを構築するときに使うのは上述したナイーブなアプローチではない。代わりに、古い regex クレートは utf8 モジュールが生成する文字クラスが持つ冗長な構造を利用し、可能な場合は必ず共通接尾辞を抽出する。しかし、そうしたとしても生成される NFA は巨大になる:

$ regex-debug compile --bytes '\w' | tail -n20
3545 Bytes(\xb0, \xb0) (goto: 3466)
3546 Bytes(\xf0, \xf0) (goto: 3545)
3547 Split(3550, 3551)
3548 Bytes(\x80, \x8c) (goto: 28)
3549 Bytes(\xb1, \xb1) (goto: 3548)
3550 Bytes(\xf0, \xf0) (goto: 3549)
3551 Split(3554, 3555)
3552 Bytes(\x8d, \x8d) (goto: 2431)
3553 Bytes(\xb1, \xb1) (goto: 3552)
3554 Bytes(\xf0, \xf0) (goto: 3553)
3555 Split(3558, 3562)
3556 Bytes(\x84, \x86) (goto: 28)
3557 Bytes(\xa0, \xa0) (goto: 3556)
3558 Bytes(\xf3, \xf3) (goto: 3557)
3559 Bytes(\x80, \xaf) (goto: 3563)
3560 Bytes(\x87, \x87) (goto: 3559)
3561 Bytes(\xa0, \xa0) (goto: 3560)
3562 Bytes(\xf3, \xf3) (goto: 3561)
3563 Save(1)
3564 Match(0)

ここに示したのは出力の最後の 20 行だけであることに注意してほしい。生成された NFA は 3,564 個の状態を持つ。ワオ。イプシロン遷移もそこら中にある。全くのカオスであり、古い regex クレートが絶望的なパフォーマンスを持たない唯一の理由は、多くの場合で lazy DFA が NFA の実際に使われる部分を DFA にコンパイルするために、NFA 全体を利用しないで済むためである。

続いて、新しい NFA コンパイラで何が起こるかを見てみよう:

$ regex-cli debug thompson --no-table '\w' | tail -n20
000292: \xB0-\xB9 => 310
000293: sparse(\x84 => 115, \x85 => 291, \x86 => 210, \xAF => 292)
000294: \x80-\x9F => 310
000295: sparse(\x80-\x9A => 5, \x9B => 294, \x9C-\xBF => 5)
000296: sparse(\x80-\x9B => 5, \x9C => 282, \x9D-\x9F => 5, \xA0 => 55, \xA1-\xBF => 5)
000297: sparse(\x80-\xA1 => 310, \xB0-\xBF => 310)
000298: sparse(\x80-\xB9 => 5, \xBA => 297, \xBB-\xBF => 5)
000299: \x80-\xA0 => 310
000300: sparse(\x80-\xAE => 5, \xAF => 299)
000301: \x80-\x9D => 310
000302: sparse(\xA0-\xA7 => 5, \xA8 => 301)
000303: sparse(\x80-\x8A => 310, \x90-\xBF => 310)
000304: sparse(\x80-\x8C => 5, \x8D => 303, \x8E-\xBF => 5)
000305: sparse(\x80-\x8D => 5, \x8E => 236)
000306: sparse(\x90 => 193, \x91 => 231, \x92 => 235, \x93 => 238, \x94 => 239, \x96 => 247, \x97 => 118, \x98 => 248, \x9A => 250, \x9B => 256, \x9C => 257, \x9D => 276, \x9E => 290, \x9F => 293, \xA0-\xA9 => 118, \xAA => 295, \xAB => 296, \xAC => 298, \xAD => 118, \xAE => 300, \xAF => 302, \xB0 => 118, \xB1 => 304, \xB2 => 305)
000307: sparse(\x84-\x86 => 5, \x87 => 236)
000308: \xA0 => 307
000309: sparse(0-9 => 310, A-Z => 310, _ => 310, a-z => 310, \xC2 => 3, \xC3 => 4, \xC4-\xCA => 5, \xCB => 6, \xCC => 5, \xCD => 7, \xCE => 8, \xCF => 9, \xD0-\xD1 => 5, \xD2 => 10, \xD3 => 5, \xD4 => 11, \xD5 => 12, \xD6 => 13, \xD7 => 14, \xD8 => 15, \xD9 => 16, \xDA => 5, \xDB => 17, \xDC => 18, \xDD => 19, \xDE => 20, \xDF => 21, \xE0 => 53, \xE1 => 93, \xE2 => 109, \xE3 => 116, \xE4 => 117, \xE5-\xE9 => 118, \xEA => 137, \xEB-\xEC => 118, \xED => 140, \xEF => 155, \xF0 => 306, \xF3 => 308)
000310: capture(pid=0, group=0, slot=1) => 311
000311: MATCH(0)

状態の個数がずっと少ないだけではなく、イプシロン遷移は一つも含まれない。これは前節で説明した sparse 命令による最適化が一因であるものの、他にも要因は存在する。

新しい NFA コンパイラは Daciuk のアルゴリズムを使って重複の無いソート済み配列から最小 DFA を構築する。これはまさに utf8 モジュールから渡されるデータそのものである。なお、実際の検索ではメモリ利用量が多くなるために最小 DFA の生成は行わず、厳密な最小性を犠牲にしてメモリ使用量に制限を付ける場合が多い。こうしたとしても DFA は十分小さくなる。

この方法は逆検索では使えない: utf8 モジュールの出力を Daciuk のアルゴリズムから使える形で逆転させる方法が (私の知る限り) 存在しないためである。このワークアラウンドとして、utf8 モジュールの出力を反転し、ソート済みかつ重複の無い形で再分割するための特別なデータ構造 range trie を私は作成した。この処理があれば、Daciuk のアルゴリズムを逆でない検索と同じように実行できる。ただし、こうすると一部のケースで NFA の構築時間が非常に長くなることが問題となる。このため、この処理はオプトインとされている。まず、この圧縮を使わない逆検索を行うときの NFA を示す:

$ regex-cli debug thompson --no-table --no-captures '\w' -r | tail -n20
001367: \xB1 => 722
001368: \x80-\x8C => 1367
001369: \x80-\xBF => 1368
001370: \x8D => 1367
001371: \x80-\x8A => 1370
001372: \x90-\xBF => 1370
001373: \x8E-\xBF => 1367
001374: \x80-\xBF => 1373
001375: \xB2 => 722
001376: \x80-\x8D => 1375
001377: \x80-\xBF => 1376
001378: \x8E => 1375
001379: \x80-\xAF => 1378
001380: \xF3 => 1386
001381: \xA0 => 1380
001382: \x84-\x86 => 1381
001383: \x80-\xBF => 1382
001384: \x87 => 1381
001385: \x80-\xAF => 1384
001386: MATCH(0)

圧縮を行うときの NFA を次に示す:

$ regex-cli debug thompson --no-table --no-captures '\w' -r --shrink | tail -n20
 000469: sparse(\x90 => 2, \x92 => 2, \x97 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488,
 \xEB-\xEC => 488, \xEF => 488)
 000470: sparse(\x97 => 2, \x9A => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488, \xEB-\xEC
=> 488)
 000471: sparse(\x80 => 3, \x81 => 387, \x82 => 6, \x83 => 387, \x84 => 397, \x85 => 451, \x86 => 174, \x87 => 6, \x88 => 100, \x89 => 100, \x8A => 13, \x8B => 348, \x8C => 14, \x8D => 45
2, \x8E => 16, \x8F => 88, \x90 => 19, \x91 => 62, \x92 => 20, \x93 => 343, \x94 => 21, \x95 => 62, \x96 => 23, \x97 => 61, \x98 => 179, \x99 => 27, \x9A => 27, \x9B => 441, \x9C => 446,
\x9D => 236, \x9E => 28, \x9F => 461, \xA0 => 454, \xA1 => 442, \xA2 => 31, \xA3 => 428, \xA4 => 33, \xA5 => 467, \xA6 => 35, \xA7 => 330, \xA8 => 455, \xA9 => 468, \xAA => 388, \xAB => 4
43, \xAC => 43, \xAD => 414, \xAE => 84, \xAF => 447, \xB0 => 438, \xB1 => 416, \xB2 => 363, \xB3 => 457, \xB4 => 67, \xB5 => 340, \xB6 => 199, \xB7 => 141, \xB8 => 465, \xB9 => 374, \xBA
 => 53, \xBB => 417, \xBC => 459, \xBD => 56, \xBE => 469, \xBF => 470, \xC3 => 488, \xC4-\xCA => 488, \xCC => 488, \xCD => 488, \xCE => 488, \xCF => 488, \xD0-\xD1 => 488, \xD2 => 488, \
xD3 => 488, \xD4 => 488, \xD5 => 488, \xD6 => 488, \xD8 => 488, \xD9 => 488, \xDA => 488, \xDC => 488, \xDD => 488, \xDF => 488)
 000472: sparse(\x91 => 2, \x92 => 2, \x93 => 2, \x97 => 2, \x98 => 2, \x9F => 2, \xA0 => 7, \xA1-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xB0 => 2, \xB1 => 2, \
xB2 => 2, \xE1 => 488, \xE2 => 488, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488, \xED => 488)
 000473: sparse(\x92 => 2, \x94 => 2, \x97 => 2, \x98 => 2, \x9D => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xB0 => 2, \xB1 => 2, \xE1 => 488, \xE3 => 48
8, \xE4 => 488, \xE5-\xE9 => 488, \xEB-\xEC => 488, \xED => 488)
 000474: sparse(\x91 => 2, \x97 => 2, \x98 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE2 => 488, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488,
 \xEA => 488, \xEB-\xEC => 488, \xEF => 488)
 000475: sparse(\x90 => 2, \x91 => 2, \x96 => 2, \x97 => 2, \x9C => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE1 => 488, \xE3 =>
488, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488)
 000476: sparse(\x90 => 2, \x96 => 2, \x97 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488,
 \xEA => 488, \xEB-\xEC => 488, \xEF => 488)
 000477: sparse(\x80 => 218, \x81 => 387, \x82 => 6, \x83 => 387, \x84 => 472, \x85 => 451, \x86 => 174, \x87 => 387, \x88 => 12, \x89 => 100, \x8A => 13, \x8B => 348, \x8C => 14, \x8D =>
 452, \x8E => 16, \x8F => 426, \x90 => 19, \x91 => 62, \x92 => 20, \x93 => 473, \x94 => 21, \x95 => 62, \x96 => 23, \x97 => 61, \x98 => 179, \x99 => 157, \x9A => 27, \x9B => 441, \x9C =>
446, \x9D => 236, \x9E => 28, \x9F => 461, \xA0 => 454, \xA1 => 442, \xA2 => 31, \xA3 => 428, \xA4 => 33, \xA5 => 467, \xA6 => 305, \xA7 => 317, \xA8 => 463, \xA9 => 468, \xAA => 388, \xA
B => 443, \xAC => 223, \xAD => 414, \xAE => 43, \xAF => 447, \xB0 => 438, \xB1 => 474, \xB2 => 363, \xB3 => 457, \xB4 => 140, \xB5 => 340, \xB6 => 266, \xB7 => 141, \xB8 => 465, \xB9 => 2
01, \xBA => 108, \xBB => 417, \xBC => 475, \xBD => 476, \xBE => 77, \xBF => 470, \xC3 => 488, \xC4-\xCA => 488, \xCC => 488, \xCE => 488, \xCF => 488, \xD0-\xD1 => 488, \xD2 => 488, \xD3
=> 488, \xD4 => 488, \xD5 => 488, \xD8 => 488, \xD9 => 488, \xDA => 488, \xDC => 488, \xDD => 488)
 000478: sparse(\x97 => 2, \x9D => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xB0 => 2, \xB1 => 2, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488,
 \xEB-\xEC => 488)
 000479: sparse(\x91 => 2, \x96 => 2, \x97 => 2, \x98 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xAF => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE3 => 48
8, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488)
 000480: sparse(\x96 => 2, \x97 => 2, \x98 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xAF => 2, \xB0 => 2, \xB1 => 2, \xE3 => 488, \xE4 => 488, \xE5-\xE
9 => 488, \xEB-\xEC => 488, \xEF => 488)
 000481: sparse(\x90 => 2, \x97 => 2, \x98 => 2, \x9D => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE1 => 488, \xE3 =>
488, \xE4 => 488, \xE5-\xE9 => 488, \xEB-\xEC => 488, \xEF => 488)
 000482: sparse(\x91 => 2, \x97 => 2, \x98 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xAE => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE1 => 488, \xE3 => 488, \xE4 =
> 488, \xE5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488, \xEF => 488)
 000483: sparse(\x91 => 2, \x97 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE1 => 488, \xE2 => 488, \xE3 => 488, \xE4 => 488, \x
E5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488)
 000484: sparse(\x91 => 2, \x97 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE0 => 488, \xE1 => 488, \xE2 => 488, \xE3 => 488, \xE4 => 488, \x
E5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488, \xEF => 488)
 000485: sparse(\x97 => 2, \xA0-\xA9 => 2, \xAA => 2, \xAB => 2, \xAC => 2, \xAD => 2, \xB0 => 2, \xB1 => 2, \xE3 => 488, \xE4 => 488, \xE5-\xE9 => 488, \xEA => 488, \xEB-\xEC => 488)
 000486: sparse(\x80 => 4, \x81 => 396, \x82 => 6, \x83 => 387, \x84 => 472, \x85 => 451, \x86 => 174, \x87 => 387, \x88 => 12, \x89 => 100, \x8A => 195, \x8B => 348, \x8C => 14, \x8D =>
452, \x8E => 16, \x8F => 426, \x90 => 19, \x91 => 62, \x92 => 20, \x93 => 473, \x94 => 114, \x95 => 62, \x96 => 23, \x97 => 61, \x98 => 179, \x99 => 27, \x9A => 27, \x9B => 441, \x9C => 4
46, \x9D => 236, \x9E => 28, \x9F => 478, \xA0 => 462, \xA1 => 442, \xA2 => 31, \xA3 => 479, \xA4 => 33, \xA5 => 467, \xA6 => 305, \xA7 => 480, \xA8 => 481, \xA9 => 399, \xAA => 482, \xAB
 => 443, \xAC => 43, \xAD => 414, \xAE => 43, \xAF => 447, \xB0 => 438, \xB1 => 474, \xB2 => 363, \xB3 => 457, \xB4 => 483, \xB5 => 484, \xB6 => 108, \xB7 => 141, \xB8 => 465, \xB9 => 374
, \xBA => 108, \xBB => 417, \xBC => 71, \xBD => 476, \xBE => 57, \xBF => 485, \xC3 => 488, \xC4-\xCA => 488, \xCC => 488, \xCD => 488, \xCE => 488, \xCF => 488, \xD0-\xD1 => 488, \xD2 =>
488, \xD3 => 488, \xD4 => 488, \xD5 => 488, \xD6 => 488, \xD8 => 488, \xD9 => 488, \xDA => 488, \xDB => 488, \xDC => 488, \xDD => 488)
^000487: sparse(0-9 => 488, A-Z => 488, _ => 488, a-z => 488, \x80 => 58, \x81 => 72, \x82 => 78, \x83 => 86, \x84 => 96, \x85 => 111, \x86 => 123, \x87 => 136, \x88 => 143, \x89 => 153,
\x8A => 165, \x8B => 172, \x8C => 177, \x8D => 186, \x8E => 194, \x8F => 202, \x90 => 217, \x91 => 222, \x92 => 224, \x93 => 227, \x94 => 233, \x95 => 238, \x96 => 244, \x97 => 251, \x98
=> 257, \x99 => 258, \x9A => 269, \x9B => 274, \x9C => 279, \x9D => 285, \x9E => 295, \x9F => 298, \xA0 => 312, \xA1 => 315, \xA2 => 320, \xA3 => 322, \xA4 => 328, \xA5 => 333, \xA6 => 33
8, \xA7 => 341, \xA8 => 345, \xA9 => 351, \xAA => 360, \xAB => 365, \xAC => 368, \xAD => 375, \xAE => 383, \xAF => 385, \xB0 => 395, \xB1 => 402, \xB2 => 408, \xB3 => 411, \xB4 => 418, \x
B5 => 425, \xB6 => 429, \xB7 => 435, \xB8 => 440, \xB9 => 444, \xBA => 450, \xBB => 460, \xBC => 466, \xBD => 471, \xBE => 477, \xBF => 486)
 000488: MATCH(0)

逆検索における圧縮は、少ない状態を持つ小さい NFA を生成する上では大きく役立つ。しかしコンパイル時間が長くなるので、現在デフォルトでは無効化されている。そのため最小 UTF-8 オートマトンの最適化は順方向の NFA でのみ適用される。

NFA の最適化: リテラル検索用のトライ

ここまでの議論で気が付いたかもしれないが、Thompson NFA が持つ最も厄介な問題の一つがイプシロン遷移である。正規表現のサイズに関して Thompson NFA をスケールさせる上でイプシロン遷移の扱いは決定的に重要となる。このため Thompson NFA ベースの正規表現エンジンが使われるとき、正規表現のサイズが検索時間に大きく影響することがある。この欠点を克服するために、Thompson NFA ベースの正規表現エンジンでは別の正規表現エンジンが実装される場合が多い。例えば lazy DFA などが使われる。ただし lazy DFA が使えない状況も存在し、lazy DFA も正規表現が十分大きくなれば検索時間は増加する。

そこで本節では、イプシロン遷移を減らすための NFA 最適化をもう一つ説明する。これからの議論では正規表現がリテラルの論理和 (alternation) であると仮定する。こういった正規表現を古い NFA がどのようにコンパイルするかを次に示す:

$ regex-debug compile 'zap|z|zapper'
0000 Save(0) (start)
0001 Split(2, 5)
0002 'z'
0003 'a'
0004 'p' (goto: 13)
0005 Split(6, 7)
0006 'z' (goto: 13)
0007 'z'
0008 'a'
0009 'p'
0010 'p'
0011 'e'
0012 'r'
0013 Save(1)
0014 Match(0)

ここには正規表現 zap|z|zapper に対して構築される NFA が示されている。入れ子になった Split 命令から構成されているのが分かる。最初に二又のイプシロン遷移 Split(2, 5) がある。状態 2 からは zap とのマッチ判定が始まり、状態 5 では Split(6, 7) でさらにイプシロン遷移が起きる。状態 6 と 7 からはそれぞれ z と zapper のマッチ判定が行われる。この正規表現のマッチを検索するときは、検索対象文字列の文字を一つ読むたびに Split 命令を最後までたどってイプシロン閉包に含まれる状態を枚挙しなければならない。

これに対して、新しい NFA コンパイラが作成する NFA を次に示す:

$ regex-cli debug thompson --no-table 'zap|z|zapper'
>000000: binary-union(2, 1)
000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 11
000003: p => 12
000004: a => 3
000005: r => 12
000006: e => 5
000007: p => 6
000008: p => 7
000009: a => 8
000010: union(4, 12, 9)
000011: z => 10
000012: capture(pid=0, group=0, slot=1) => 13
000013: MATCH(0)

(ここでも、状態 0 と 1 はアンカーを付けない検索で利用される接頭辞 (?s-u:.)*? を表すので、無視して構わない。古い NFA コンパイラはこれらの状態を生成しないが、その理由は今の議論に関係ない。)

ここでは、最初のイプシロン遷移が行われる前に、状態 11 で z とのマッチが確認される。このマッチが確認されて初めて union(4, 12, 9) でイプシロン遷移が行われる (union 命令は古い NFA コンパイラにおける入れ子になった Split 命令に対応し、三つ以上の状態へのイプシロン遷移をまとめて表せる)。この NFA を使って検索を行うとき、検索対象文字列の全ての文字に対してイプシロン閉包を長い時間をかけて計算する必要はない。イプシロン閉包の計算が必要となるのはバイト z を読んだときだけであり、頻度は非常に低い。事実上、NFA コンパイラは正規表現 zap|z|zapper を z(?:ap||apper) に書き換えている。

何が起きているのだろうか？ この特定の例で言えば、NFA コンパイラはリテラルの共通接頭辞を見つけて「くくり出した」ように思える。しかし、ここで行われている最適化はさらに一般的な処理を行える。次は正規表現 abc|xyz を考えよう。この例で二つのリテラル abc, xyz は共通接頭辞を持たない。まず、古い NFA コンパイラは次の NFA を生成する:

$ regex-debug compile 'abc|xyz'
0000 Save(0) (start)
0001 Split(2, 5)
0002 'a'
0003 'b'
0004 'c' (goto: 8)
0005 'x'
0006 'y'
0007 'z'
0008 Save(1)
0009 Match(0)

ここでも Split 命令が最初にあり、分岐後の状態がそれぞれ abc と xyz とのマッチを確認する。

続いて、新しい NFA コンパイラの出力を次に示す:

$ regex-cli debug thompson --no-table 'abc|xyz'
thompson::NFA(
>000000: binary-union(2, 1)
000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 7
000003: c => 8
000004: b => 3
000005: z => 8
000006: y => 5
000007: sparse(a => 4, x => 6)
000008: capture(pid=0, group=0, slot=1) => 9
000009: MATCH(0)
)

生成される NFA はイプシロン遷移を持たない。a または x とのマッチ確認が単一の sparse 命令としてくくり出され、そこからそれぞれの接尾辞 (bc と yz) のマッチ確認に分岐する。

ここで新しい NFA コンパイラはリテラルの論理和 (alternation) を認識し、トライにコンパイルし、そしてイプシロン遷移を最小化する形でトライを直接 NFA に変換している。この最適化では、leftmost-first 意味論が変化しないことの保証が重要となる。例えば、一つ目の例で zap|z|zapper を z(?:ap(?:per)?)? と「最適化」できるのではないかと思ったかもしれない。しかし、この二つの正規表現は同じマッチを生成しない！ 検索対象文字列が zapper のとき、zap|z|zapper は zap とマッチするのに対して、z(?:ap(?:per)?)? は zapper とマッチする。意味論が変化しないことを保証するため、リテラルの集合から生成されるトライでは状態間の遷移がチャンクに分割される。チャンクは「現在マッチしてよいリテラル」を表し、トライの構築時にマッチに対応する状態を作るときに設定される。通常のトライを使うと、トライを NFA に変換するときマッチの優先度が変化して leftmost-first 意味論が失われてしまう。

NFA: 将来

NFA に関して今後行いたいことが二つある。

一つ目は Glushkov NFA の実装である。Glushkov NFA のコンパイルは時間計算量が大きいものの、生成される NFA がイプシロン遷移を持たないという利点がある (イプシロン遷移を持つ代わりに、同一のシンボルに対する遷移が複数定義される)。コンパイルの時間計算量が大きいので、Glushkov NFA を全てのケースで使うことはできないだろう。しかし小さい正規表現に対して試す価値があるのは間違いないと思える。また、現在の regex クレートが残念ながらあまり活用できていない bit parallel というテクニックは Glushkov NFA との相性が良い可能性がある。個人的な疑問としては、巨大な Unicode 文字クラスに対して Glushkov NFA がどのように振る舞うか、というものがある (そういった機能が使われるとき、おそらく Glushkov NFA は利用できないだろう)。

二つ目は NFA を単一アロケーションの連続領域に保存する処理の実装である。これを実装するとアクセスパターンが単純になり、検索処理がキャッシュフレンドリーになる可能性がある。加えて、おそらくこれより重要なこととして、ゼロコピーのシリアライズとデシリアライズが可能になる。これを実装する欠点としてはコードの複雑性の増加、そして場合によっては unsafe が使用されることがある。しかし、それを上回る利点がもたらされる可能性もある。

正規表現エンジン

RE2 と同様、regex クレートはいくつかの異なる正規表現エンジンから構成される。その多くにはこれまでに何らかの形で言及した。この節では、それぞれの正規表現エンジンの特徴や存在する理由を詳しく説明する。最後に、全ての正規表現エンジンを一つに束ねるメタ正規表現エンジンを説明する。

正規表現エンジンがいくつも存在するのはどうしてだろうか？ 理由は本質的に工学的である: 機能の多い正規表現エンジンは機能が少ないものより検索が遅い傾向がある。全ての機能をサポートするエンジン (具体的には PikeVM) だけを使うことはできるものの、そうすると検索のパフォーマンスは多くのユーザーにとって満足いかないものとなる。これが他のエンジンの望まれる基礎的な理由である。なお、PikeVM 以外に regex クレートが提供する全ての機能をサポートするエンジンは存在せず、どんな場合でも PikeVM が「最後の砦」となる。

正規表現エンジンの動作を説明するのに regex-cli を使うのに加えて、これからは簡単な Rust プログラムも例として示していく。示される Rust プログラムを自分で実行したい場合は、次のコマンドで Cargo プロジェクトをセットアップして regex-automata を依存パッケージに追加する必要がある:

$ cargo init --bin
$ cargo add 'regex-automata@0.3'

その後 src/main.rs を作成・編集すれば、cargo run でプログラムを実行できる。

異なる正規表現エンジンに共通する要素

regex-automata クレートには多くの正規表現エンジンが含まれるものの、どれも非常に似た API を持っている。そこで、共通する要素を最初に説明しておく。

重要な型として、Input, Match, MatchError の三つがある。

Input は検索のパラメータを設定する小さな型である。検索対象のバイト列 haystack のみを必須パラメータとして持つ。検索 API の多くは Into<Input> トレイトを実装する任意の型の値を受け取り、&[u8] と &str はどちらも Into<Input> を実装する。その他の省略可能なパラメータは検索対象文字列のどの部分を検索するか、アンカー付き検索を行うかどうか、マッチを一つでも見つけたら検索を止めるか (それとも貪欲に全てのマッチを見つけるか) どうかなどを指定する。

Match は検索対象文字列でマッチが見つかったときに報告されるデータを表す。このデータは二つの要素からなる。一つ目の要素はマッチが見つかった検索対象文字列の領域を表すバイトオフセットの組、二つ目の要素はマッチしたパターンに対応する PatternID である (regex-automata クレートが持つ全ての正規表現エンジンは多パターン検索をファーストクラスでサポートする)。

MatchError は検索中に発生するエラーを表す。エラーが発生するとき、検索対象文字列中にマッチが存在するかどうかは判定できない: 結果は不確定となる。このため、基礎的な検索 API の多くは返り値の型に Result<Option<Match>, MatchError> を持つ。検索中に発生するエラーには様々な種類がある。例えば、特定のバイトを読んだ瞬間に検索を中止するよう DFA を設定できる。また、BoundedBacktracker は検索対象文字列が設定された閾値より長いとき検索に失敗する。後で議論するように、メタ正規表現エンジンの主な機能の一つは、いくつもの正規表現エンジンを組み合わせて使いつつ呼び出し側にエラーを決して返さないようにすることである。

多くの正規表現エンジンに共通する要素は他にもある。例えば、エンジンの構築は Builder 型の値が行い、設定は (一つまたは複数の) Config 型の値が行う場合が多い。詳しくは以降で説明される。regex-automata クレートのドキュメントにある API themes も参照してほしい。

エンジン: PikeVM

上述したように、PikeVM は「最後の砦」である。つまり、PikeVM は regex-syntax がパース可能な正規表現の機能を全てサポートし、任意の長さの文字列に検索を実行できる。他の正規表現エンジンは次に示すような様々な制限を持つ:

Cache 型の値を除けば、PikeVM は NFA から追加の処理をせずに直接構築できる。どういうことかと言えば、PikeVM による検索は NFA をそのまま「シミュレート」することで行われる (紛らわしいことに、この処理を「DFA アルゴリズム」と呼ぶことがある)。実際の実装は仮想マシンと同じような構造を持ち、それぞれの NFA 状態が命令として機能する。PikeVM は一つの NFA 状態から次の NFA 状態に移動することで動作し、イプシロン閉包はその場その場で計算される。同時に複数の NFA 状態が「現在状態」になることがあり得るので、PikeVM はアクティブな状態を全て追跡し、そのそれぞれに対して遷移関数を適用する。PikeVM はキャプチャグループの位置も追跡する。

PikeVM が抱える主な問題はパフォーマンスである。そのパフォーマンスの低さは、大量の状態を追跡しなければならない事実から生じている部分が大きい。\(O(mn)\) の最悪計算時間を保証するには、各時点でアクティブな状態を全て追跡しなければならない。つまりバックトラッキングのアプローチとは対照的に、PikeVM は検索対象文字列の各バイトに対して高々定数個の処理しか行わず、それを保証するためにアクティブな状態を全てロックステップで (まとめて一歩ずつ進む方式で) 計算する。これによって大きなオーバーヘッドが加わり、正規表現から構築された NFA にイプシロン遷移が多く含まれればオーバーヘッドはそれだけ大きくなる (これは本記事の前半で NFA からイプシロン遷移を取り除く最適化について長く語った理由の一つである)。

PikeVM の振る舞いを少し説明したので、いくつか例を見ていこう。次に示すのは PikeVM を使って検索を行う Rust プログラムに簡単な説明をつけたものである:

use regex_automata::{nfa::thompson::pikevm::PikeVM, Match};

fn main() {
    // パターン文字列から PikeVM を構築する。
    // `PikeVM::builder()` を使えば、NFA から直接 PikeVM を構築できる。
    let re = PikeVM::new(r"\b\w+\b").unwrap();

    // regex-automata に含まれる正規表現エンジンの多くは、
    // 検索を行うときに改変可能なスクラッチ空間 (キャッシュ) を必要とする。
    // この事実はメタ正規表現エンジンによってユーザーからは見えないようになっているものの、
    // 内部の正規表現エンジンを使うときはキャッシュを明示的に渡す必要がある。
    let mut cache = re.create_cache();

    let mut it = re.find_iter(&mut cache, "Σέρλοκ Χολμς");
    assert_eq!(Some(Match::must(0, 0..12)), it.next());
    assert_eq!(Some(Match::must(0, 13..23)), it.next());
    assert_eq!(None, it.next());
}

同じ処理は regex-cli コマンドを使っても行える:

$ regex-cli find match pikevm --no-table -p '\b\w+\b' -y 'Σέρλοκ Χολμς'
0:0:12:Σέρλοκ
0:13:23:Χολμς

Unicode 単語境界の機能が非 ASCII の検索対象文字列に対して使われていることに注目してほしい。このケースを扱えるのは PikeVM, BoundedBacktracker, one-pass DFA のみである。lazy DFA と fully compiled DFA を使おうとするとエラーとなる。

もう一つ注目すべき重要な点として、この例で使われている検索 API はエラーを返さない。実は、どんな状況でも PikeVM はエラーを返さない (パニックも起こさない)。これは regex-automata に含まれる正規表現エンジンの中で PikeVM だけが持つ特徴である。他の正規表現エンジンはどれも、様々な理由で検索を途中で停止してエラーを返す場合がある。

次に示すように、キャプチャグループを持った他パターン検索を行うこともできる。これは regex クレートからは行えないものの、regex-automata クレートからなら行える。この処理を RegexSet API に追加してほしいという要望が数多く存在するものの、現時点では追加されていない。次の例はメタ正規表現エンジンを使った場合にも動作する:

use regex_automata::nfa::thompson::pikevm::PikeVM;

fn main() {
    let re = PikeVM::new_many(&[
        r"(?<email>[.\w]+@(?<domain>[.\w]+))",
        r"(?<phone>(?<areacode>[0-9]{3})-[0-9]{3}-[0-9]{4})",
    ])
    .unwrap();
    let mut cache = re.create_cache();

    let hay = "foo@example.com, 111-867-5309";
    let mut it = re.captures_iter(&mut cache, hay);

    let caps = it.next().unwrap();
    assert_eq!(0, caps.pattern().unwrap().as_usize());
    assert_eq!("example.com", &hay[caps.get_group_by_name("domain").unwrap()]);

    let caps = it.next().unwrap();
    assert_eq!(1, caps.pattern().unwrap().as_usize());
    assert_eq!("111", &hay[caps.get_group_by_name("areacode").unwrap()]);

    assert!(it.next().is_none());
}

等価な regex-cli コマンドを次に示す:

$ regex-cli find capture pikevm --no-table \
    -p '(?<email>[.\w]+@(?<domain>[.\w]+))' \
    -p '(?<phone>(?<areacode>[0-9]{3})-[0-9]{3}-[0-9]{4})' \
    -y 'foo@example.com, 111-867-5309'
0:{ 0: 0..15/foo@example.com, 1/email: 0..15/foo@example.com, 2/domain: 4..15/example.com }
1:{ 0: 17..29/111-867-5309, 1/phone: 17..29/111-867-5309, 2/areacode: 17..20/111 }

キャプチャグループの名前がパターンごとに異なることに注目してほしい。マッチしたパターンに対応する正しい名前を使う責任は呼び出し側にある。

エンジン: BoundedBacktracker

BoundedBacktracker はバックトラッキングのアルゴリズムを使って Thompson NFA を直接用いた検索を実行する。このアルゴリズムは (紛らわしいことに) 「NFA アルゴリズム」と呼ばれることもある。regex-automata が実装するバックトラッキングと通常の実装の重要な違いとして、regex-automata の実装はバックトラックしたときに同じ状態をたどるのを避けるために追加の情報を保持することがある。これによって \(O(mn)\) の最悪計算時間が保証されるものの、空間も \(O(mn)\) だけ消費される。

余談: 古典的なバックトラッキングを使う実装の最悪計算時間も何らかの上界で抑えることはできる (bounded である)。しかし、BoundedBacktracker の「bounded」は実装の最悪計算時間が \(O(mn)\) という特定の上界で抑えられることを指している。

BoundedBacktracker の利点は多くのケースで PikeVM より高速なことである。雑な計測では、BoundedBacktracker は多くの場合で PikeVM より二倍程度高速となった。

前の例で PikeVM を使ったのと同じように、BoundedBacktracker を使って検索を行う簡単な Rust プログラムを次に示す:

use regex_automata::{nfa::thompson::backtrack::BoundedBacktracker, Match};

fn main() {
    let re = BoundedBacktracker::new(r"\b\w+\b").unwrap();

    // BoundedBacktracker は PikeVM と同様にキャッシュを必要とする。
    // このキャッシュには完了した処理が書き込まれる。また、バックトラッキングのコールスタック用の
    // スクラッチ空間としてもキャッシュは使われる。キャッシュ自体はヒープに確保される。
    let mut cache = re.create_cache();

    // PikeVM と異なり、BoundedBacktracker は検索に失敗する場合がある。
    // 具体的には、`len(regex) * len(haystack)` が設定された閾値を上回ると検索が失敗する。
    // 失敗する検索の例は後で見る。
    let mut it = re.try_find_iter(&mut cache, "Σέρλοκ Χολμς");
    assert_eq!(Some(Ok(Match::must(0, 0..12))), it.next());
    assert_eq!(Some(Ok(Match::must(0, 13..23))), it.next());
    assert_eq!(None, it.next());
}

等価な regex-cli コマンドを次に示す:

$ regex-cli find match backtrack --no-table -p '\b\w+\b' -y 'Σέρλοκ Χολμς'
0:0:12:Σέρλοκ
0:13:23:Χολμς

これは PikeVM を使う例とほとんど変わらないものの、重要な違いが一つある: re.find_iter(...) ではなく re.try_find_iter(...) が呼ばれている。上述したように、BoundedBacktracker は設定された閾値より多くのメモリを消費すると見込まれるときエラーを返すためである。この閾値は Config::visited_capacity から設定できる。BoundedBacktracker がエラーを出さずに検索できる最大の文字列の長さを取得することもできる:

use regex_automata::nfa::thompson::backtrack::BoundedBacktracker;

fn main() {
    let re = BoundedBacktracker::new(r"\b\w+\b").unwrap();
    println!("{:?}", re.max_haystack_len());
}

執筆時点において、このプログラムを私のマシンで実行すると 6653 が出力される。とても小さな値だと思うかもしれないが、この正規表現はおそらくあなたが想像するよりも大きな言語を表している。具体的には、\w はデフォルトで Unicode を認識するので、100,000 個以上の異なる符号位置とマッチする。もっと長い文字列を検索したい場合は、Config::visited_capacity に大きな値を設定することもできるし、Unicode のサポートを無効化して正規表現が表す言語のサイズを小さくすることもできる:

use regex_automata::nfa::thompson::backtrack::BoundedBacktracker;

fn main() {
    let re = BoundedBacktracker::new(r"(?-u)\b\w+\b").unwrap();
    println!("{:?}", re.max_haystack_len());
}

このプログラムは私のマシンで 233015 を出力した。二桁近い差がある！

一般的に言って、可能な場合は PikeVM より BoundedBacktracker を優先して使うべきである。二つの正規表現エンジンが保証する時間計算量は同じであるものの、実際の検索では BoundedBacktracker の方が高速な場合が多い。

エンジン: one-pass DFA

one-pass DFA そのものについて詳しく話す前に、この正規表現エンジンが存在する理由を説明した方がいいだろう。PikeVM と BoundedBacktracker に共通する重要な特徴として、パターンのマッチに含まれるキャプチャグループのオフセットを報告できることがある。例えば regex-cli で PikeVM を使うと、次の出力が得られる:

$ regex-cli find capture pikevm --no-table \
    -p '(?<year>[0-9]{4})-(?<month>[0-9]{2})-(?<day>[0-9]{2})' \
    -y '2023-07-02'
0:{ 0: 0..10/2023-07-02, 1/year: 0..4/2023, 2/month: 5..7/07, 3/day: 8..10/02 }

キャプチャグループを使うと正規表現にマッチした文字列を独立した部分に分割できるので、この機能は非常に有用である。この例から分かるように、正規表現エンジンは日付を表す文字列を見つけるだけではなく、API を通じて日付の各要素を簡単に利用可能にする。例えば、regex クレートを使えば次のようなプログラムを書ける:

use regex::Regex;

fn main() {
    let pat = r"(?<year>[0-9]{4})-(?<month>[0-9]{2})-(?<day>[0-9]{2})";
    let re = Regex::new(pat).unwrap();
    let Some(caps) = re.captures("2023-07-02") else { return };
    println!(" year: {:?}", &caps["year"]);
    println!("month: {:?}", &caps["month"]);
    println!("  day: {:?}", &caps["day"]);
}

キャプチャグループが無ければ、正規表現の有用性はずっと低くなる。

キャプチャグループの問題として、正規表現と有限オートマトンの理論的モデルにぴったり当てはまらないことがある (tagged finite automata と呼ばれる、表現力の高いモデルが必要となる)。この結果として、キャプチャグループは古典的な NFA のシミュレーションに「後付け」で追加される。そうして出来上がるのが PikeVM である。また、キャプチャグループは古典的な「NFA アルゴリズム」 (バックトラッキング) の一要素でもある: 各グループのオフセットはバックトラックした後に検索対象文字列を読み進む中で記録できる。

この二つの正規表現エンジンを除けば、キャプチャグループは基本的にサポートされない。例えば DFA ベースの正規表現エンジンは一切サポートせず、tagged finited automata といった進化系を使わない限りキャプチャグループを簡単にサポートすることはできない。

しかし、「one-pass NFA」と呼ばれる特殊な NFA からであれば、キャプチャグループのサポートを持つ DFA を構築できる。one-pass NFA とは、DFA に変換したとき DFA の各状態が高々一つの NFA 状態に対応するような NFA を言う。言い換えれば、NFA の状態遷移をシミュレートするとき、検索文字列のシンボルを一つ読んだときの遷移先が必ず高々一つとなる NFA が one-pass NFA である。

この特殊ケースでは、キャプチャグループのコピーを一つだけ保持しておくだけで、それが必ず最終的なマッチに対応するキャプチャグループとなることが保証される。これに対して PikeVM では、キャプチャグループのコピーが最大で len(regex) 個保持され、どれが最終的なマッチの一部となるかは最後まで分からない。one-pass NFA を検出できれば、その NFA から新しい DFA を線形時間で構築でき、その構築された DFA を使えば検索文字列の各文字を定数個の CPU 命令で処理できる高速な検索が行える。

こうして構築されるのが one-pass DFA であり、これは PikeVM と BoundedBacktracker のいずれよりも格段に速く動作する。別の言い方をすれば、マッチに含まれるキャプチャグループのオフセットを報告できる正規表現エンジンとして one-pass DFA は regex クレートの中で最速となる。

one-pass DFA の問題点として、DFA であるためにメモリを多く使用することがある (この問題は one-pass DFA の構築が設定可能なメモリ予算内で行えるときにだけ実行し、予算を超えるときは失敗するようにすれば緩和できる)。また、one-pass でない正規表現も多く存在する。例えば、regex クレートではアンカーを持たない検索が正規表現の先頭に (?s-u:.)*? を付けることで実装される。この接頭辞に空でない正規表現が続くとき、全体の正規表現は one-pass でない。よって、one-pass DFA はアンカー付きの検索しかサポートできない。

「アンカー付きの検索にしか使えない」という制約が one-pass DFA の有用性を大きく制限すると思うかもしれないが、これから詳しく見ていくように、メタ正規表現エンジンはユーザーから受け取った正規表現にアンカーが付いていなくてもアンカー付き検索を非常に頻繁に利用する。例えばユーザーがキャプチャグループのオフセットを要求したときにアンカー付き検索が使われる。この場合、メタ正規表現エンジンは DFA ベースの高速な正規表現エンジンを使って正規表現全体とのマッチを検索し、その検索でマッチが見つかったときに限って、マッチした領域に対するアンカー付き検索でキャプチャグループを計算する。このため、one-pass DFA が使われる頻度は非常に高い。

one-pass DFA を直接使うこともできる。基本的にはこれまでの例と大きくは変わらないものの、one-pass DFA の API はこれまでに見てきた正規表現エンジンの API よりさらに窮屈である:

use regex_automata::{dfa::onepass::DFA, Match};

fn main() {
    let re = DFA::new(r"\b\w+\b").unwrap();
    let mut cache = re.create_cache();

    // one-pass DFA はアンカー付きの検索だけをサポートするので、イテレータ API を公開しない。
    // 仮にイテレータを作ったとしても、隣接するマッチを返すことしかできない。
    // そういったイテレータが便利な場合もあると思われるものの、 regex-automata に含まれる
    // 他のイテレータと異なる意味論になってしまう。
    let Some(m) = re.find(&mut cache, "Σέρλοκ Χολμς") else { return };
    assert_eq!(Match::must(0, 0..12), m);
}

等価な regex-cli コマンドを次に示す:

$ regex-cli find match onepass --no-table --anchored \
    -p '\b\w+\b' \
    -y 'Σέρλοκ Χολμς'
0:0:12:Σέρλοκ

regex-cli に --anchored フラグを渡していることに注目してほしい。このフラグを付けないと、one-pass DFA を使った検索はエラーを返す。

one-pass DFA で複数の検索を実行することもできる。次の例で正規表現そのものにアンカーは付いていないものの、オフセット 0 から検索を開始しなくても構わない:

use regex_automata::{dfa::onepass::DFA, Input, Match};

fn main() {
    let hay = "Σέρλοκ Χολμς";
    let re = DFA::new(r"\b\w+\b").unwrap();
    let mut cache = re.create_cache();

    let Some(m) = re.find(&mut cache, hay) else { return };
    assert_eq!(Match::must(0, 0..12), m);

    let input = Input::new(hay).range(13..);
    let Some(m) = re.find(&mut cache, input) else { return };
    assert_eq!(Match::must(0, 13..23), m);
}

Input による抽象化は他の正規表現エンジンと同じように使うことができる。

特定の正規表現が one-pass かどうかを見定めるのは非常に難しい場合がある。例えば、一部のケースでは Unicode モードを有効にするかどうかで one-pass かどうかが変化する。この例を次に示す:

$ regex-cli find match onepass --no-table --anchored \
    -p '\w+\s+\w+' \
    -y 'Σέρλοκ Χολμς'
failed to compile onepass DFA: one-pass DFA could not be built because pattern is not one-pass: conflicting transition

これに対して、Unicode モードを無効化すると正規表現は one-pass となる:

$ regex-cli find match onepass --no-table --anchored \
    -p '(?-u)\w+\s+\w+' \
    -y 'Sherlock Holmes'
0:0:15:Sherlock\x20Holmes

この現象が起こるのは、Unicode モードが有効なとき \w と \s に「重なり」が生まれるためである。ただし両者は論理的には共通要素を持たない: つまり、\w と \s がそれぞれ表す符号位置の集合の共通部分は空集合となる:

$ regex-cli debug hir --no-table '[\w&&\s]'
Class(
    {},
)

実際の「重なり」はバイトレベルで生じている (one-pass DFA の遷移はバイトレベルで定義される)。この重なりは、Unicode モードが有効なときの \w+\s+\w+ に対する DFA が「全ての DFA 状態が高々一つの NFA 状態に対応する」という one-pass の定義を満たさないことを意味する。具体的に言えば、\w と \s には UTF-8 でエンコードすると同じ符号単位で始まる符号位置が含まれる。

これに対して Unicode モードが無効だと、\w と \s は符号位置が重ならないだけではなく、バイトレベルの重なりも持たなくなる。なぜだろうか？ Unicode モードが無効なとき \w と \s は ASCII に対応する Unicode の符号位置に制限され、そういった符号位置は UTF-8 で必ず 1 バイトで (ASCII と同じバイトに) 符号化されるためである。

one-pass DFA は PikeVM と BoundedBacktracker より高速なので、これらより優先して使われるべきである。ただし one-pass DFA の方が構築にかかる時間が長い可能性があり、消費されるメモリはおそらく多い。また、one-pass DFA を構築できる正規表現がそもそも限られているので、構築に失敗したときに備えて他のエンジンへのフォールバックを用意する必要がある。

エンジン: DFA

正規表現エンジン DFA は二つの fully compiled DFA (完全にコンパイルされた DFA, 別名 dense DFA) から構成される。一つの DFA は文字列を順方向にスキャンしてマッチの終端を見つけ、もう一つの DFA はアンカー付き検索を逆方向に行ってマッチの開始地点を見つける (後者の DFA は Hir に含まれる結合を逆転させ、そこから NFA を構築し、その NFA を決定化することで構築される)。これらの DFA を「dense」と呼ぶのは、sparse DFA と区別するためである。dense DFA は省メモリ性を犠牲にすることで検索速度を最適化するのに対して、sparse DFA は検索速度を犠牲にすることで省メモリ性を最適化する。

fully compiled DFA は構築に必要な時間と空間が最悪ケースで \(O(2^m)\) なので、汎用正規表現エンジンでは使われないことが多い (\(m\) は len(regex) に比例する)。例えば、正規表現 [01]*1[01]{N} はおよそ \(N\) 個の状態を持つ NFA にコンパイルされ、\(N\) が大きくなると NFA は線形に大きくなる。これに対して、この NFA から構築される DFA は \(2^N\) 個の状態を持ち、\(N\) が大きくなると DFA は指数的に大きくなる。

しかし、DFA の問題は理論的最悪ケースにおける振る舞いだけではない。各状態で任意のバイトを読んだときの遷移先を定数時間で計算できなければならないので、DFA (特に dense DFA) は多くのメモリを消費する。定数時間のランダムアクセスを提供するには、本質的に多くのメモリが必要となる。この特徴が巨大な Unicode クラスと組み合わさると、悲惨な結果が生じる。例として、正規表現 \w のサイズが Unicode 対応の有無でどれほど変化するかを見てみよう。まず、NFA だと次のようになる (PikeVM と BoundedBacktracker は NFA を直接利用することを思い出してほしい):

$ regex-cli debug thompson '\w' -q
[.. 省略 ..]
memory:  17668
[.. 省略 ..]

NFA は 17KB のメモリを消費している。特に小さいわけではない。しかし、NFA を DFA に決定化すると何が起こるかを見てほしい:

$ regex-cli debug dense dfa '\w' --start-kind unanchored -q
[.. 省略 ..]
memory:  159296
[.. 省略 ..]

メモリ消費量は 160 KB に急上昇する！ ここではアンカーの付いていない DFA を構築していることに注目してほしい。デフォルトの --start-kind both を使用すると、メモリ消費量はさらに倍になる。時間を長くかけて DFA を最小化するよう指示しても、メモリ消費量は改善しない:

$ regex-cli debug dense dfa '\w' --start-kind unanchored --minimize -q
[.. 省略 ..]
memory:  159296
[.. 省略 ..]

最小化の効果があるケースもある。しかしこのケースでは、Daciuk のアルゴリズムで作った \w に対する NFA から最小 UTF-8 オートマトンを構築しているので、NFA を DFA に決定化した時点で最小の DFA が構築される。本当の問題は dense な表現とバイト単位のアルファベットである。sparse な表現に切り替えるとメモリ消費量が少しだけ減少する:

$ regex-cli debug sparse dfa '\w' --start-kind unanchored -q
[.. 省略 ..]
memory:  102257
[.. 省略 ..]

これでも 100 KB 以上のメモリが必要になる。これらの例から分かるように、Unicode 文字クラスと fully compiled DFA は相性が非常に悪い。また、実際の検索で様々な異なる言語の文字を含む検索対象文字列は稀なので、完全な文字クラスをコンパイルする必要性は薄い。多くの検索では ASCII に対して定義される \w で十分であり、このとき DFA はずっと小さくなる:

$ regex-cli debug thompson '(?-u)\w' -q
[.. 省略 ..]
memory:  732
[.. 省略 ..]

$ regex-cli debug dense dfa '(?-u)\w' --start-kind unanchored -q
[.. 省略 ..]
memory:  384
[.. 省略 ..]

この場合は、dense DFA が対応する NFA より実際に小さくなる。

こういった大きな欠点があるにもかかわらず、汎用正規表現エンジンである regex クレートが DFA エンジンを持つのはどうしてだろうか？ 法外な量のメモリを使用する可能性のある正規表現エンジンはスタートラインにも立てないのでは？ この点に関して言及しておきたい点が二つある。

まず、DFA エンジンはデフォルトでは無効化される。perf-dfa-full フィーチャーを有効化することでオプトインしない限り DFA エンジンは使われない。私がこの選択をしたのは、lazy DFA (次節で説明される) が fully compiled DFA より圧倒的大多数のケースで優れた選択肢となるので、regex クレートにおいて fully compiled DFA はそれほど重要でないと判断したためである。ただし lazy DFA が上手く活用できない最適化の機会を fully compiled DFA が活用できるケースは存在する。例えば正規表現 (?m)^.*$ において、 fully compiled DFA は . が \n にマッチしないことに気が付く: 状態を離れる全ての遷移を確認できるためである。そういった状態が見つかると、DFA は自身でない状態に遷移するバイトを memchr で検索することで状態を「加速」できる。これは regex-cli と使ったアドホックなベンチマークでも実際に確認できる。まず、DFA 状態の「加速」を有効にしたとき (デフォルト) の結果を示す:

$ regex-cli find match dense -bB -q --repeat 1000000 \
    -p '(?m-u)^.*$' \
    -y 'this is a long line about the quick brown fox that jumped over the lazy dog'
[.. 省略 ..]
search time:  56.600473ms
[.. 省略 ..]

続いて DFA 状態の「加速」を無効にしたときの結果を示す:

$ regex-cli find match dense -bB -q --repeat 1000000 --no-accelerate \
    -p '(?m-u)^.*$' \
    -y 'this is a long line about the quick brown fox that jumped over the lazy dog'
[.. 省略 ..]
search time:  199.044059ms
[.. 省略 ..]

「加速」が有効だと検索時間が大きく削減されるのが分かる。このベンチマークでは Unicode モードを無効にしていることに注意してほしい。Unicode モードが有効だと . が任意の Unicode スカラー値を UTF-8 エンコードしたバイト列にマッチする。このとき DFA は複雑になり、「加速」の最適化は適用できなくなる:

$ regex-cli find match dense -q --repeat 1000000 \
    -p '(?m)^.*$' \
    -y 'this is a long line about the quick brown fox that jumped over the lazy dog'
[.. 省略 ..]
search time:  204.897593ms
[.. 省略 ..]

DFA 状態の「加速」は非常に有用であるものの、Unicode が理由の一つとなって、適用できる正規表現は限られる。また、メタ正規表現エンジンは非常に小さい正規表現に対してのみ DFA エンジンを選択するので、この最適化が実際に適用される機会は多くない。一方で、この最適化には法外なメモリ使用量と構築時の指数的振る舞いが付いて来る。regex クレートは正規表現のコンパイルに関しては最速を目指していないものの、コンパイルに指数時間がかかることはどんな理由があっても受け入れられない。

使える場面が限られること、そして DFA エンジンの大規模なコードがコンパイル時間とバイナリサイズを大きく増加させることが理由となって、fully compiled DFA はデフォルトで無効化されている。

fully compiled DFA に関して言及しておきたい二つ目の事項として、fully compiled DFA では検索処理が非常に単純かつ高速となる。regex-automata クレートに含まれる正規表現エンジンの中では fully-copmpiled DFA だけが改変可能なスクラッチ空間を検索中に必要としない。これは次の例からも分かる:

use regex_automata::{
    dfa::{dense, regex::Regex},
    Match,
};

fn main() {
    let re = Regex::builder()
        // ヒューリスティックによる Unicode 単語境界サポートを有効化しないと、
        // 正規表現 `r"\b\w+\b"` はコンパイルに失敗する。
        // なぜかと言えば、デフォルトで \b は Unicode に対応し、DFA エンジンは
        // 検索対象文字列に非 ASCII の符号位置が含まれるとき単語境界をサポートしないためである。
        // ヒューリスティックによる Unicode 単語境界サポートを有効にすればコンパイルは
        // 可能になるものの、検索が失敗する可能性が生まれる。具体的には、DFA が
        // 非 ASCII バイトを読むと、その時点で検索は中断されてエラーが返る。
        .dense(dense::Config::new().unicode_word_boundary(true))
        .build(r"\b\w+\b")
        .unwrap();

    // この `find_iter` は内部で行われる検索がエラーを返すとパニックすることに注意！
    // Regex::try_search などの失敗可能 (fallible) な API を使えばエラーに対処できる。
    let mut it = re.find_iter("Sherlock Holmes");
    assert_eq!(Some(Match::must(0, 0..8)), it.next());
    assert_eq!(Some(Match::must(0, 9..15)), it.next());
    assert_eq!(None, it.next());
}

等価な regex-cli コマンドを次に示す:

$ regex-cli find match dense --no-table --unicode-word-boundary \
    -p '\b\w+\b' \
    -y 'Sherlock Holmes'
0:0:8:Sherlock
0:9:15:Holmes

Cache が必要とされないことに注目してほしい。実は DFA の検索ランタイムは非常に単純なので、そして DFA の内部構造がそのように設計されているので、DFA は生のバイト列にシリアライズできる。シリアライズした DFA を別の場所でデシリアライズすれば、その環境で検索を「そのまま」行える。つまり、Rust の std や alloc は必要とならず、core だけで検索が行える。

(DFA のシリアライズは regex-automata 0.1 リリースの動機となったユースケースだった。現在この機能は bstr クレートで Unicode の segmentation アルゴリズムを実装するために使われている。)

fully compiled DFA は正規表現が Unicode 機能を使わないとき、もしくは低レベル API へのアクセスが必要なとき最も有用となる。例えば、DFA の状態遷移を手動で計算することもできる:

use regex_automata::{
    dfa::{dense::DFA, Automaton},
    Anchored,
};

fn main() {
    let re = DFA::new(r"\W").unwrap();

    // DFA が複数の開始状態を持つことはあるものの、それはルックアラウンドアサーションが
    // 使われるときだけに限られる。ルックアラウンドアサーションが使われていない現在の例の
    // ようなケースでは、検索対象文字列がどんなものであれ開始状態は一意に決定する。
    let mut sid = re.universal_start_state(Anchored::No).unwrap();

    // 💩 は UTF-8 で \xF0\x9F\x92\xA9 とエンコードされる。
    sid = re.next_state(sid, 0xF0);
    sid = re.next_state(sid, 0x9F);
    sid = re.next_state(sid, 0x92);
    sid = re.next_state(sid, 0xA9);
    sid = re.next_eoi_state(sid);
    assert!(re.is_match_state(sid));
}

このプログラムでは検索対象文字列が 1 バイトずつ手動で DFA に与えられている。この例は多少不自然であるものの、低レベルの制御を提供する API がどんなものかを示している。Automaton トレイトのドキュメントには他にも様々な例が載っている。Automaton トレイトは dense DFA と sparse DFA が実装しなければならない低レベル DFA ルーチンを定義する。

エンジン: lazy DFA

「hybrid NFA/DFA」や「lazy DFA」と呼ばれる正規表現エンジンは基本的には DFA エンジンと変わらないものの、遷移テーブルが検索時に構築される点が異なる。別の言い方をすれば、fully compiled DFA は「事前コンパイル」とみなせるのに対して、lazy DFA は「just-in-time (JIT) コンパイル」とみなせる。

(lazy DFA を「JIT」と呼ぶのは多少ミスリーディングである。正規表現の文脈で「JIT」はマッチ判定を行う機械語コードを正規表現から実行時に生成することを指す場合が多い。)

lazy DFA は大まかに言って fully compiled DFA と同じ API を持つ。ただし、他の正規表現エンジンと同様に、検索するときは Cache 引数を渡す必要がある。Cache には構築される遷移テーブルなどが書き込まれる。lazy DFA を使う簡単な Rust プログラムを次に示す:

use regex_automata::{
    hybrid::{dfa, regex::Regex},
    Match,
};

fn main() {
    let re = Regex::builder()
        // fully compiled DFA と同様、lazy DFA でもヒューリスティックによる
        // Unicode 単語境界のサポートを有効化する必要がある。このとき正規表現に Unicode 
        // 単語境界が含まれ、かつ検索対象文字列に非 ASCII 符号位置が含まれると
        // エラーが返される。この点も fully compiled DFA と同様である。
        .dfa(dfa::Config::new().unicode_word_boundary(true))
        .build(r"\b\w+\b")
        .unwrap();
    let mut cache = re.create_cache();

    // この `find_iter` は内部で行われる検索がエラーを返すとパニックすることに注意！
    // Regex::try_search などの失敗可能 (fallible) な API を使えばエラーに対処できる。
    let mut it = re.find_iter(&mut cache, "Sherlock Holmes");
    assert_eq!(Some(Match::must(0, 0..8)), it.next());
    assert_eq!(Some(Match::must(0, 9..15)), it.next());
    assert_eq!(None, it.next());
}

等価な regex-cli コマンドを次に示す:

$ regex-cli find match hybrid --no-table --unicode-word-boundary \
    -p '\b\w+\b' \
    -y 'Sherlock Holmes'
0:0:8:Sherlock
0:9:15:Holmes

この例は Cache パラメータがある点を除けば fully compiled DFA の例とほぼ同じである。両者の低レベル API も似ている:

use regex_automata::{hybrid::dfa::DFA, Input};

fn main() {
    let re = DFA::new(r"\W").unwrap();
    let mut cache = re.create_cache();

    // DFA が複数の開始状態を持つことはあるものの、それはルックアラウンドアサーションが
    // 使われるときだけに限られる。ルックアラウンドアサーションが使われていない現在の例の
    // ようなケースでは、検索対象文字列がどんなものであれ開始状態は一意に決定する。
    // fully compiled DFA では開始状態が検索対象文字列によらず決定するので、
    // 開始状態を取得するための専用ルーチンが存在する。一方 lazy DFA は全ての開始状態を
    // 事前にコンパイルするわけではないので、ダミーの検索対象文字列を与えて (偽の) 開始状態を
    // 取得している。
    let mut sid = re.start_state_forward(&mut cache, &Input::new("")).unwrap();
 
    // 💩 は UTF-8 で \xF0\x9F\x92\xA9 とエンコードされる。
    sid = re.next_state(&mut cache, sid, 0xF0).unwrap();
    sid = re.next_state(&mut cache, sid, 0x9F).unwrap();
    sid = re.next_state(&mut cache, sid, 0x92).unwrap();
    sid = re.next_state(&mut cache, sid, 0xA9).unwrap();
    sid = re.next_eoi_state(&mut cache, sid).unwrap();
    assert!(sid.is_match());
}

Cache を明示的に渡す点を除けば API の見た目はそれほど変わらない。ただし重要な違いとして、lazy DFA の next_state は失敗する可能性がある。具体的には、MatchError や CacheError を返すメソッドがある。MatchError は状態が終端状態に達したために遷移を計算できなくなったときに返る (このとき検索は失敗する。例えば、ヒューリスティックによる Unicode 単語境界サポートが有効なときに非 ASCII バイトを読んだときに MatchError は返される)。CacheError は渡された Cache が使い尽くされたときに返る。

ここで、Cache について詳しく説明しておく。lazy DFA の最も大きな利点と最も大きな欠点は両方とも Cache に関係している。上述したように、lazy DFA は遷移テーブルを検索中に構築することで動作する。具体的には、次の処理が行われる:

この方式では、検索対象文字列から文字 (バイト) を一つ読むたびに高々一つの DFA 状態と遷移が作成される。そのため、lazy DFA が行う検索処理の最悪計算時間は \(O(mn)\) であり、消費される空間量は最悪でも構築時に設定される容量となる。lazy DFA 自体の構築に DFA 状態の構築は (簡単に構築できる「門番」状態を除けば) 必要ないので、lazy DFA は fully compiled DFA が持つ理論的な時間計算量と空間計算量を緩和すると言える。つまり、lazy DFA を使うとき指数的な構築時間は回避される。よくあるケースでは、ほとんどの状態/遷移がキャッシュされ、lazy DFA による検索の実行時間が平均で \(O(n)\) となる。実際の検索で使われる多くの正規表現では、lazy DFA と fully compiled DFA は同程度の検索パフォーマンスを持つ。

さらに、巨大な Unicode 文字クラスを使ったときの法外なメモリ使用量という fully compiled DFA の問題も lazy DFA では緩和される。lazy DFA は実際に読んだバイトに基づいて必要な情報だけを計算するので、Unicode モードが有効な \w を ASCII 文字だけからなる検索対象文字列から検索した場合は、\w の ASCII に関する部分だけが DFA に変換される。この仕組みは実際の検索で非常に上手く動作することが判明している。

lazy DFA は Cache を素早く埋めてクリアを頻発させる正規表現に対しては動作が低速になる。正規表現が大きいこと、ときには検索対象文字列が NFA の大部分の構築を要求することが原因となる (回数指定付きの反復があったりキャプチャグループが多く使用されたりしていると、正規表現はすぐに巨大になる。また、多パターン正規表現に対しては一つの大きな lazy DFA が構築される)。こういったケースでは、その事実をヒューリスティックが検出し、lazy DFA にエラーを返させる。その後メタ正規表現エンジンは lazy DFA による検索を中断し、他の正規表現エンジン (たいていは PikeVM) に切り替える。

メタ正規表現エンジン

メタ正規表現エンジン (meta regex engine) はここまでに説明してきた様々な正規表現エンジンを一つにまとめ、どんな状況でも可能な中で最も優れた動作を試みる単一の失敗不能 (infallible) な API として公開する。この公開される API では、ユーザーが Cache 型の値を明示的に作成して検索の呼び出しに渡す必要はない。メタ正規表現エンジンがスレッドセーフな Cache 型の値のプールを内部に持ち、ユーザーの代わりに管理する (Cache 型の値を明示的に渡す低レベル API も公開する。この API は内部で使われるスレッドセーフなプールの同期コストを避けたいときに有用となる)。

こうして出来上がるメタ正規表現エンジンは regex クレートのトップレベル API と非常によく似た API を持つ。実際、regex::Regex, regex::RegexSet, regex::bytes::Regex, regex::bytes::RegexSet はどれもメタ正規表現エンジンのごく薄いラッパーと言える。これは設計によるものであり、99% のユースケースに対応できる利便性の高い高レベル API から数多くのノブを公開する低レベル API へと「下る」ことを簡単にしている。

大まかに言うと、メタ正規表現エンジンは内部で次のロジックを実装する:

メタ正規表現エンジンの全体的な戦略をまとめるとすれば、次の二点に集約できるだろう:

これだけである。一般に、文字列検索アルゴリズムに費やす時間は長ければ長いほど望ましく、PikeVM に費やす時間は短かければ短いほど望ましい。

多くの正規表現エンジンは regex クレートと同様に何らかのリテラル最適化を行う。さらに言えば、プロダクショングレードの正規表現エンジンはリテラル最適化に相当な労力を費やしている (代表的な例として Hyperscan がある)。しかし、少なくとも私の知る限り、本記事で説明されるほどの規模でリテラル最適化を行う汎用正規表現エンジンは存在しない3。reverse suffix 最適化と reverse inner 最適化は正しく実装するのが特に難しい。一見すると簡単に見えるものの、気が付きにくいパフォーマンスの問題が一つ存在する: それを踏むと、最悪計算時間が (検索対象文字列の長さに対して) 二次関数的になってしまう。

正規表現 [A-Z].*bcdefghijklmnopq を bcdefghijklmnopq を何度も繰り返した文字列から検索する状況を考えよう。この正規表現から抽出できる「優れた」接頭辞リテラル列は存在しないので、上述したロジックに従えば、メタ正規表現エンジンは接尾辞 bcdefghijklmnopq を使った「reverse suffix」最適化を試みる。しかし、今考えている特別に作られた検索対象文字列では、マッチ候補は頻繁に見つかるのに対してマッチは一つも存在しない。ここでの問題は接尾辞のマッチが見つかった後に行われる .* の逆方向検索で、このとき検索対象文字列が先頭まで走査される。この先頭までの走査が大量に見つかるマッチ候補のそれぞれで繰り返されるので、検索ルーチン全体の最悪計算時間が \(O(mn^2)\) となってしまう4。これは良くない。

正規表現を構文的に解析して二次関数的な振る舞いを起こす可能性があるかどうかを調べることもできるものの、確実な判定はできない。今の例では接尾辞 bcdefghijklmnopq が直前の .* に含まれるので、二次関数的な振る舞いが起こる可能性があると判断できる。しかし、それが不可避かどうかは分からない。

そこで、メタ正規表現エンジンは DFA エンジンをベースとした独自の正規表現検索ルーチンを定義して問題を回避する。具体的には、検索対象文字列に対する逆向き走査を特定のオフセットに達した段階で中止する。そのオフセットは最後の接尾辞マッチの終端との距離と定義される。逆向き走査がこのオフセットを超えるケースが頻発すると、二次関数的振る舞いが生じてしまう。メタ正規表現エンジンはこのエラーケースを検出すると上述してきた「コア」の戦略にフォールバックし、時間計算量保証を破ってしまう最適化を放棄する

同様のロジックは「reverse inner」最適化に対しても存在する。

まとめると、典型的なユーザーは個別の正規表現エンジンへの低レベルアクセスを必要としないものの、正規表現エンジンが公開する様々なノブを制御したり多パターンマッチングを行ったりすることはある。そのよう場合にメタ正規表現エンジンは優れた選択肢となる。つまり、上述した個別の正規表現エンジンにはどれも細かな注意点があり、ありとあらゆるケースを扱う正規表現エンジンとしては理想的ではない。

RE2 との違い

Russ Cox が執筆した正規表現に関する一連の記事を読んだことがあるなら、前節の議論の一部には聞き覚えがあるはずである。RE2 は PikeVM (単に "NFA" と呼ばれる)、BoundedBacktracker ("bitstate backtracker" と呼ばれる)、one-pass DFA ("one-pass NFA" と呼ばれる)、そして lazy DFA を持つ。さらに、こういった正規表現エンジンを上述したのと似た方法で組み合わせるメタ正規表現エンジンも (この用語は使われていないものの) RE2 は持っている。本記事で説明した正規表現エンジンの中で RE2 が持っていないのは fully compiled DFA のみである。

では、RE2 と regex クレートの違いは (もしあるなら) 何だろうか？

両者には相違点よりも類似点の方が多いものの、高レベルな違いとしては次の点がある:

将来的には、新しい正規表現エンジンを regex-automata に追加したいと私は思っている。具体的には、Glushkov NFA と bit parallel regex engine を調査するつもりでいる。また、shift DFA も調査したいと思っている。

テスト戦略

本記事の最初で説明したように、以前の regex クレートではテストが問題となっていた。内部で使われる各正規表現エンジンのテストはマクロによるハックを使って書かれており、不穏な雰囲気がただよっていた。また、そういったテストはそもそも書くのが難しく、より重要な点として、理解するのが難しかった。

regex クレートのテストを刷新する上で私が持っていたアイデアは、「メイン」の正規表現エンジンから独立してテストできる独自のファーストクラス API を内部の正規表現エンジンにそれぞれ持たせる、というものだった。また、テストを Rust のソースコードやマクロとして埋め込むのではなく、どんな文脈で使えるようにしたいとも思っていた。こういった考えから、私は次の戦略でテストを行った:

現在の Rust のユニットテストフレームワークは拡張可能でないので、この戦略を動作させるには追加でインフラを少しだけ整える必要があった。具体的には、実行するテストをフィルタリングするために独自の環境変数を定義する必要があった (例えば、特定のテストが失敗するバグの解決に取り組んでいるときは、そのテストだけを実行できた方がいい)。

TOML に書かれるテスト以外にもテストは大量にある。例えば、regex-automata クレートだけで 450 個以上のドキュメンテーションテストが存在する。

最後に、regex 1.9 に向けた作業の中で、たくさんの fuzz テストターゲットが追加された。ここでは Addison Crump から大きな助けを得た。彼がいなければ見つけられなかったであろうバグが少なくとも数個発見されている。

ベンチマーク

この記事は現時点で本サイト最長の記事となっているのに、ベンチマークの議論は始まってすらいない。元々の予定では、regex 1.9 を紹介する記事ではベンチマークについて多くの文面が割かれる予定だった──せっかく最適化についてこんなにも長く語られるのだから。しかし、regex クレートにベンチマークを詰め込むのは現実的ではなかった。

その代わり、私は rebar という正規表現の「バロメーター」を作成した。rebar は regex クレートのベンチマークだけではなく、他の様々な正規表現エンジンのベンチマークも行う。rebar は現在公開されている正規表現ベンチマークの中で最も広範なものだと私は信じている。

242 個のベンチマークを平均すると、regex 1.9 は regex 1.7.3 より約 1.5 倍高速だった (regex 1.8 ではなく regex 1.7 と比較するのは、regex 1.8 は書き直しが進行中だったころのリリースであり、本記事で紹介した最適化の一部が既に含まれているためである。クレートの書き直しは regex 1.9 で完了した)。この事実は次の実行結果から分かる:

$ rebar rank record/all/2023-07-02/*.csv \
    --intersection \
    -M compile \
    -e '^(rust/regex|rust/regexold)$'
Engine         Version  Geometric mean of speed ratios  Benchmark count
------         -------  ------------------------------  ---------------
rust/regex     1.8.4    1.08                            242
rust/regexold  1.7.3    2.61                            242

一方で、正規表現を構築するのにかかる時間は少なからず増加した:

$ rebar rank record/all/2023-07-02/*.csv \
    --intersection \
    -m compile \
    -e '^(rust/regex|rust/regexold)$'
Engine         Version  Geometric mean of speed ratios  Benchmark count
------         -------  ------------------------------  ---------------
rust/regexold  1.7.3    1.07                            28
rust/regex     1.8.4    1.46                            28

(このコマンドは rebar のレポジトリをチェックアウトしたディレクトリで実行する。)

上記の rebar コマンドが報告する幾何学的平均 (geometric mean) は集計方法としては非常に粗雑である。実際の改善の程度をどれほど上手く捉えているのか、私にはよく分からない。個別のベンチマークを見たい場合は rebar rank を rebar cmp に変えると行える:

$ rebar cmp record/all/2023-07-02/*.csv \
    --threshold-min 2 \
    --intersection \
    -M compile \
    -e '^(rust/regex|rust/regexold)$'
benchmark                                            rust/regex            rust/regexold
---------                                            ----------            -------------
captures/contiguous-letters                          10.9 MB/s (1.00x)     1361.4 KB/s (8.21x)
curated/02-literal-alternate/sherlock-ru             6.5 GB/s (1.00x)      3.0 GB/s (2.20x)
curated/02-literal-alternate/sherlock-casei-ru       1528.4 MB/s (1.00x)   448.4 MB/s (3.41x)
[.. 省略 ..]

--threshold-min 2 があるので、このコマンドは二つのエンジンの間で二倍以上のパフォーマンスの差異が計測されたベンチマークを表示する。

コスト

罰を受けない善行は無いNo good deed goes unpunished.。この書き直しで私は何を失っただろうか？

まず何よりも、過去数年間にわたって私の自由時間の圧倒的大部分が regex クレートの書き直しに費やされた。私の自由時間は以前よりもずっと少なくなっているので、ripgrep といったプロジェクトでは新しいバージョンを長い間リリースできていない。

次に、書き直しによってコードがかなり増えた。他のユーザーが使うことを前提とした再利用可能な抽象化を定義する仕事は、regex クレートの内部で使われる (regex クレートのハッカーしか覗かないであろう) 抽象化を定義する仕事と大きく異なる。前者ではコードが長くなり、それによってバイナリサイズが増え、コンパイル時間が長くなる場合が多い。

第三に、こういった抽象化が公開され、個別にバージョンが付けられた。これは内部の正規表現エンジンの API を軽率に変更できず、破壊的変更を含む regex-automata クレートのリリースとして適切に公開しなければならないことを意味する。破壊的変更に関して regex クレートほどに保守的になるつもりはないものの、しようと思えば手間がかかる。この事実はコントリビューターに影響を及ぼすだろう。必要な分だけコードを自由にリファクタリングすることはできず、パブリック API の設計という重圧に耐えなければならない。

regex クレートは書き直し前の時点でもバイナリサイズとコンパイル時間が理想的ではないと言われていた。書き直しによるコードの増加はこの二つの問題を悪化させるので、私は二つの緩和策を実施した:

  1. 先述したように、fully compiled DFA という正規表現エンジンをオプトインにした。このエンジンはコードが多く、検索パフォーマンスに対する影響はそれほど大きくない。
  2. regex クレートのドロップインリプレースメントとして動作する regex-lite クレートを新しく公開した。このクレートの設計は「ほとんどの場合でバイナリサイズとコンパイル時間を優先し、機能 (特に Unicode に関する機能) とパフォーマンスを犠牲にする」を基礎としている。保証される最悪計算時間は \(O(mn)\) で変わらないものの、抜け目の無い Unicode サポートや高速な検索は regex-lite を使っても手に入らない。ただ、バイナリサイズとコンパイル時間は regex クレートより格段に優れている。また、regex-lite は依存パッケージを持たず、regex クレートとコードを全く共有しない──正規表現のパーサーさえ独自のものを利用する。

regex-lite クレートという緩和策は現在でも実験的な面がある。しかし、コードを任意に削減可能な形に書くことが難しいことは示されたと言える: regex クレートが持つ様々なフィーチャーを通して最適化や Unicode 機能を無効化したとしても、バイナリサイズとコンパイル時間は regex-lite クレートのそれに遠く及ばない。

最後に

この記事では、regex クレートの重要な構成要素に関する話をすることに集中した。こういった高レベルな説明は API のドキュメントには載っていないことが多い。ただそうは言っても、この記事は表面をなぞっただけに過ぎない。さらに詳細な説明やサンプルプログラムが必要な場合は、regex-automata の API のドキュメントを熟読することを勧める。

何か少しでも疑問があれば、GitHub Discussions に投稿してほしい。

  1. 訳注: この「言語」は「文字列の集合」の意味で使われている。以降で使われる「言語」も同様。 ↩︎

  2. 訳注: ^XY, XY$, X(?=Y), (?<X)Y といった正規表現で使われる、マッチの前方/後方の文字列に何らかの特徴を要求する機能を総称してルックアラウンドアサーション (look-around assertion) と呼ぶ。 ↩︎

  3. Hyperscan が「汎用」かどうかについては議論の余地がある。私が Hyperscan は汎用でないと考える理由の一つとして、Hyperscan が持つ特殊なマッチ意味論がある。例えば、Hyperscan は見つかったマッチを全て報告するので、\w+ は abc に 3 回マッチする。ただし、これは対象ドメインを考えれば間違いなく正しい選択肢である。 ↩︎

  4. 最悪計算時間が変化したのは質の悪いヒューリスティックが追加されたためであり、正規表現エンジンが保証する \(O(mn)\) の時間検索時間保証が破られているわけではない。 ↩︎

広告
このページの文章はテキストゆれないくんを使って校正されました。