正規表現エンジンの内部をライブラリとして公開

 (blog.burntsushi.net)
1 ポイント 投稿者 GN⁺ 2023-07-06 | 1件のコメント | WhatsAppで共有
  • Rust の regex crate は、数年にわたる再実装を経て、内部エンジンのかなりの部分を別バージョンの regex-automata crate API として公開し、regex 1.9 で移行が完了した
  • 再実装は、検索戦略の組み合わせの難しさ、内部エンジンごとのテストの難しさ、RegexSet より細かなマルチパターン API への要求、完全コンパイル DFA の共有の必要性から始まった
  • regex-automata は、Ast → Hir → リテラル抽出/Prefilter → Thompson NFA → PikeVM・BoundedBacktracker・one-pass DFA・DFA・lazy DFA → meta engine という流れで正規表現処理を構成する
  • 性能は、可能な限りリテラル検索と DFA 系エンジンを先に使い、キャプチャグループや例外的な状況では PikeVM・bounded backtracker・one-pass DFA で補完する形で確保している
  • 公開 API と再利用可能な抽象化によりテストや実験は容易になったが、コード量、バイナリサイズ、コンパイル時間は増加し、完全コンパイル DFA は opt-in とし、regex-lite が軽量な代替として追加された

regex の再実装と regex-automata の公開

  • Rust の regex crate は、内部の組み合わせを改善し、最適化をより容易に追加しつつ正確性を維持するため、数年にわたって再実装された
  • この過程で regex-automata が作られ、regex crate の内部実装のかなりの部分を別 API として公開した
  • regex-automata は、正規表現ライブラリの内部をこの程度まで別バージョンのライブラリとして公開した初の事例として紹介されている
  • regex 1.9 は 2023年7月5日にリリースされ、この再実装を完了した
  • Rust プログラマーと、有限オートマトンベースの正規表現エンジン実装に関心のある人を対象としており、正規表現の経験を前提としている

再実装以前の問題

  • 従来の regex crate は RE2 の流れに従い、複数の検索戦略を内部で使用していたが、戦略が有機的に追加されていった結果、組み合わせが難しくなった
    • PikeVM は最初の戦略として設計されており、lazy DFA と組み合わせる際に必要な、部分スライス検索の開始・中断処理が不足していた
    • どの正規表現にどの戦略が使われるのか推論しにくかった
    • 複数の match 式が同じロジックを繰り返し実装しており、同期がずれやすかった
    • Aho-Corasick だけで済む正規表現でも、使われない Thompson NFA が不要に作られることがあり得た
  • 内部エンジンのテストも難しかった
    • 公開 API は単一の正規表現エンジンのように見えるが、内部には複数の戦略があり、同じ入力に対して同一に動作しなければならない
    • regex 1.9 以前は内部戦略が公開 API ではなかったため、各エンジンを独立してテストするのが難しかった
    • 既存のテストは、内部 API の露出、文書化されていない From 実装、マクロ、エンジン別のテストターゲットに依存する、ハックに近い構造だった
  • 複数のニッチ API の要望も、従来の API 表面に入れるには扱いが難しかった
    • RegexSet は、どのパターンが haystack のどこかにマッチしたかだけを知らせ、マッチオフセットやキャプチャグループのオフセットは提供しない
    • パターンに ^ を入れずに anchored 検索を実行する機能が必要だった
    • 検索中に内部同期なしで mutable scratch space を直接渡す機能が求められた
    • ストリームや rope のような非連続 haystack で正規表現を実行する機能も要望された
  • 別バージョンの crate として内部を公開すれば、汎用目的の regex API を複雑にせず、専門家向け API をより速い breaking change サイクルで実験できる

完全コンパイル DFA が作った抽象化の境界

  • regex-automata の初期の動機は、完全コンパイル DFA を作成してシリアライズし、zero-copy デシリアライズで検索する最小ランタイムを提供することだった
  • 初期の regex-automata は、bstr の Unicode アルゴリズム実装用 DFA を作るために使われた
  • DFA を作っていくと、regex crate と似た NFA データ構造とコンパイラが必要になり、このコードが複雑化するにつれて共有の必要性が高まった
  • 当初は regex-nfa のような別 crate も検討したが、決定化プロセスなど、より多くのコードを regex と regex-automata の間で共有できた
  • 抽象化の境界は「NFA」よりも正規表現エンジンに近く、最終的に regex-automata は複数エンジンの集合として再定義された
  • 長期計画は、すべての正規表現エンジンを regex-automata に置き、regex crate をその上の薄いラッパーにすることだった

regex-cli で内部構造を確認する

  • regex-cli は regex crate のリポジトリで管理されているプログラムで、regex-syntax、regex-automata、regex の複数の API にコマンドラインからアクセスできる
  • インストールは次のコマンドで可能
cargo install regex-cli
  • regex-cli debug は AST、HIR、リテラル、Thompson NFA、one-pass DFA、dense DFA、sparse DFA などを出力できる
  • Unicode が有効な . 正規表現は UTF-8 scalar value を処理するため、はるかに複雑な Thompson NFA を作り、Unicode が無効な (?-u:.) はより単純な NFA を作る
  • regex-cli find は一時的な検索を実行でき、meta engine によるマルチパターン検索とキャプチャグループ出力も可能

正規表現処理のデータフロー

  • Regex::new に渡されたパターン文字列は、まず Ast としてパースされる
  • Ast は Hir に変換される
    • Hir は Ast より詳細情報が少なく、Unicode case folding と Unicode character class 参照は変換中に展開される
  • Hir からは 2 つのものが作られる
    • 検索最適化に使われるリテラルシーケンス
    • Thompson NFA
  • NFA は複数のエンジンを作る基盤になる
    • PikeVM: パース可能なすべての正規表現を処理し、キャプチャグループのオフセットを報告する
    • BoundedBacktracker: bounded backtracking によりキャプチャグループのオフセットを報告する
    • one-pass DFA: 制限された正規表現でキャプチャグループのオフセットを高速に報告する
    • dense DFA: 非常に高速だが、マッチ全体の開始・終了だけを報告し、構築には最悪で O(2^m) の時間・空間が必要になる
    • lazy DFA: 検索中に NFA から DFA を作り、通常は full DFA と同程度に高速で、full DFA の指数的な構築コストを避ける
  • これらのエンジンと Prefilter は 1 つの meta regex engine に組み合わされ、regex crate はこの meta engine の薄いラッパーである

リテラル最適化

  • リテラル抽出は regex 内部の中核的な最適化である
    • たとえば (foo|bar|quux)(\s+\w+) のすべてのマッチは、foo、bar、quux のいずれかで始まる
  • リテラルが重要なのは、単一または少数の文字列検索アルゴリズムが非常に高速だからである
    • ベクトル命令で haystack の複数バイトを一度に処理できる
    • 一般的な正規表現マッチングアルゴリズムを同じ方法で一貫して高速化するのは難しい
  • 十分に最適化された substring 検索は、一般的な正規表現エンジンより少なくとも一桁以上速いことがよくあった
  • リテラル抽出はヒューリスティックである
    • 候補マッチの false positive rate を下げる必要がある
    • prefilter が全体のレイテンシに与える影響も低く抑える必要がある
    • どちらの条件も haystack に依存するが、検索前に haystack を分析すると全体の検索時間が悪化する可能性がある
  • リテラルシーケンスは集合ではなく、順序を持つシーケンスである
    • regex crate は Perl-like leftmost-first セマンティクスに従うため、| には交換法則が成り立たない
    • sam|samwise では sam だけが抽出されうるが、samwise|sam では両方が考慮される
  • 単一文字列検索には memchr crate の memmem モジュールが使われる
    • 主アルゴリズムは、最悪 O(n) 時間と定数空間を持つ Two-Way である
    • 短い needle と haystack には Rabin-Karp が使われる
    • x86_64 では generic SIMD 変種が活用される
  • 複数文字列検索には Hyperscan から移植した Teddy が主要アルゴリズムとして使われ、一部の場合には Aho-Corasick も使われる

Thompson NFA と最適化

  • regex crate 内部の中心的なデータ構造は Thompson NFA である
  • Thompson’s construction は正規表現の構造化表現から NFA を O(m) 時間で作り、m は counted repetition 展開後の正規表現サイズに比例する
  • NFA は直接正規表現エンジンとして使うこともでき、DFA のような別の型に変換して他のエンジンの基盤としても使われる
  • 新しい NFA コンパイラの主な最適化は、epsilon transition を減らすことに集中している
    • Thompson NFA は構築時間に優れるが、epsilon transition を多用する
    • epsilon closure の計算は、検索や DFA 構築中に反復コストを生むことがある
  • sparse state 最適化は、複数の範囲遷移を1つの状態で表現し、従来の複数の Split instruction を減らす
    • [A-Za-z0-9] のような正規表現で不要な epsilon transition を取り除く
    • 現在の表現では indirection のため、cache への影響と heap memory 増加の可能性がある
  • 最小 UTF-8 オートマトン最適化は、大きな Unicode class で NFA サイズを大幅に減らす
    • 以前の byte-oriented NFA では \w が 3,564 states を作ることがあった
    • 新しいコンパイラは Daciuk’s algorithm を使い、はるかに少ない状態と zero epsilon transition を持つ構造を作る
    • reverse NFA の shrink は compile time コストのためデフォルトでは無効化されている
  • literal trie 最適化は、zap|z|zapper、abc|xyz のようなリテラル alternation で共通構造を trie にコンパイルし、epsilon transition を減らす
    • leftmost-first セマンティクスを保つため、match が現れる地点ごとに transition chunk を分割する
  • 今後の NFA 作業として Glushkov NFA と単一の contiguous allocation 保存が検討されている
    • Glushkov NFA は epsilon transition がないが、compile time complexity はより悪い
    • contiguous allocation は cache friendliness と zero-copy のシリアライズ・デシリアライズ可能性をもたらし得るが、コードの複雑さと unsafe 使用の可能性がある

個別の正規表現エンジン

  • regex-automata のエンジン群は似た API を共有する
    • Input: haystack、検索範囲、anchored かどうか、early stop するかどうかを設定する
    • Match: マッチした byte span と PatternID を保持する
    • MatchError: 検索結果を決定できないエラーを表す

  • PikeVM

    • regex-syntax がパースできる全機能をサポートし、任意の長さの haystack で動作する
    • キャプチャグループ位置を追跡し、active state 群を lock-step で計算して最悪 O(m * n) 時間を保証する
    • 多くの状態とキャプチャグループ位置を追跡する必要があるため、性能が主な弱点である
    • regex-automata エンジンの中で、検索中にエラーを返さないという固有の特性がある

  • BoundedBacktracker

    • Thompson NFA 上で backtracking を使うが、すでに実行した作業を再度追跡しないよう追加の状態を使う
    • 最悪 O(m * n) 時間を保証するが、O(m * n) 空間を使用する
    • おおまかな実験では、通常 PikeVM より約2倍速い
    • haystack の長さと正規表現サイズが設定された visited capacity を超えると失敗することがある

  • one-pass DFA

    • 制限された one-pass NFA でキャプチャグループのオフセットを非常に高速に報告する
    • キャプチャグループを報告できる最速の方式とされる
    • anchored search のみをサポートし、多くの正規表現は one-pass ではない
    • Unicode モードでは byte level transition overlap のため one-pass でなかった正規表現が、Unicode をオフにすると one-pass になることがある

  • fully compiled DFA

    • forward DFA と reverse DFA の2つで構成され、完全なマッチの終端と開始位置を見つける
    • 構築は最悪 O(2^m) 時間・空間で、dense DFA はメモリを多く使う
    • full DFA エンジンは regex crate でデフォルト無効化されており、perf-dfa-full feature で opt-in する必要がある
    • mutable Cache なしで動作し、raw bytes にシリアライズして core だけの環境でも検索ランタイムを利用できる

  • hybrid NFA/DFA、lazy DFA

    • full DFA と似ているが、transition table を検索中に作る
    • cache にすでに計算済みの transition があれば再利用し、なければ NFA powerset construction でその transition だけを計算する
    • 最悪検索時間は O(m * n)、空間は構築時に定めた cache capacity に制限される
    • 一般的な場合、ほとんどの state と transition がキャッシュされ、平均 O(n) のように動作し、実際に多くの正規表現で full DFA と同程度の検索性能を示す
    • cache が繰り返し満杯になって非効率な場合はエラーを返し、meta engine では通常、別のエンジンで再試行する

meta regex engineの役割

  • meta regex engineは複数のエンジンを1つにまとめ、呼び出し側にinfallibleなAPIを提供しようとするもの
  • 呼び出し側は検索ごとにCacheを直接作成して渡す必要がない
    • meta engineは内部でthread-safeなcache poolを管理する
    • 同期コストを避けたい場合のために、明示的にCacheを渡すlower-level APIも提供する
  • regex::Regex、regex::RegexSet、regex::bytes::Regex、regex::bytes::RegexSetはいずれもmeta engineの薄いラッパーである
  • meta engineの内部戦略はおおよそ次のとおり
    • 正規表現エンジンなしで単一・複数のsubstring検索だけで処理できるなら、NFAの構築も避ける
    • 可能ならprefixリテラル列を抽出してPrefilterとして使う
    • prefixが適切でなければ、reverse anchored、reverse suffix、reverse inner最適化を試す
    • それ以外はPikeVM、bounded backtracker、one-pass DFA、lazy DFA、full DFAを含むcore strategyへfallbackする
  • 全体戦略は2文に要約できる
    • 可能な限りリテラルを検索する
    • 可能な限りPikeVMの使用を避ける
  • reverse suffixとreverse inner最適化は、誤るとhaystackサイズに対して最悪O(m * n^2)になり得る
    • meta engineはreverse scanが直前のsuffix matchの終端を越えようとする状況を検知し、core strategyへfallbackして時間計算量の保証を維持する

RE2との違い

  • regex crateとRE2には多くの類似点がある
    • RE2にもPikeVMに相当するNFA、bitstate backtracker、one-pass NFA、lazy DFA、複数エンジンを組み合わせる構造がある
    • 上記のエンジンのうちRE2にないものはfully compiled DFAである
  • 主な違いは次のとおり
    • RE2はleftmost-firstに加えて、POSIX式のleftmost-longestセマンティクスをオプションでサポートする
    • RE2はUnicodeサポートがより限定的で、\w、\s、\d、\bをUnicode定義として使うオプションがない
    • RE2はcharacter class set operationのうち、union以外のサポートが限定的である
    • RE2のPikeVMはよりメモリ効率が高い可能性がある
    • RE2のリテラル最適化は限定的で、regex crateの方がより多くのリテラル最適化を行う
    • RE2のlazy DFAは複数threadが同じtransition cacheを共有するため同期が必要だが、regex crateはthreadごとに別々のcacheを要求するため、より多くのメモリを使う
    • regex crateはregex-syntaxとregex-automataを独立したバージョンのライブラリとして公開しているが、RE2はこれをサポートしていない
    • regex-automataはすべてのエンジンでfirst-classなmulti-pattern regexをサポートし、各マッチングパターンのmatchおよびcapture group offsetも報告できる

テスト戦略とベンチマーク

  • 新しいテスト戦略は、内部エンジンを独立したfirst-class APIにし、各エンジンを直接テストする方式である
  • すべての正規表現テストはTOMLファイルで指定される
  • regex-test crateがTOMLテストを読み込み、構造化された表現に変換する
  • 各エンジン構成ごとに1つのRust unit testを置き、そのエンジンに適用可能なすべてのTOMLテストを実行する
  • Rust unit test frameworkは拡張可能ではないため、特定テストのフィルタリング用に独自のenvironment variable基盤が追加された
  • regex-automataだけで450件を超えるdocumentation testがある
  • regex 1.9の準備過程でfuzz testing targetも多数追加され、Addison Crumpの協力によりいくつかのバグを発見した
  • ベンチマークはrebarというregex barometerとして公開されている
    • rebarはregex crateだけでなく、複数の正規表現エンジンをベンチマークする
    • 242件のベンチマークで、regex 1.9は検索時間基準でregex 1.7.3より平均1.5倍高速である
    • 正規表現をビルドする時間はやや後退した
    • 1.8は一部の移行作業を含むtransition releaseのため、比較基準として1.7が使われた

コストと軽量な代替案

  • 書き直しには過去数年にわたる作者の自由時間の大半が費やされ、ripgrepのようなプロジェクトはしばらくリリースできなかった
  • 再利用可能な公開抽象化は、内部専用の抽象化よりコード量が多くなりがちである
    • その結果、バイナリサイズとコンパイル時間が増加する
  • 内部エンジンAPIが別バージョンとして公開されたことで、APIを壊すにはregex-automataの適切なbreaking change releaseが必要になる
  • コスト軽減のため、2つの措置が適用された
    • fully compiled DFAエンジンはデフォルトで無効化し、opt-in featureとする
    • regex-liteを新しいcrateとして公開する
  • regex-liteはregex crateのほぼdrop-in replacementを目指すが、バイナリサイズとコンパイル時間の最適化に集中する
    • Unicodeと性能面の機能を諦める
    • O(m * n)の時間計算量保証は維持する
    • 依存関係は0個で、独自の正規表現パーサーを含み、regex crateとはコードを共有しない
  • regex-liteはまだ実験的な緩和策だが、regex crateのfeatureで最適化やUnicode機能をオフにしても、regex-liteのバイナリサイズとコンパイル時間には近づきにくいことを示している

関連記事

1件のコメント

 
GN⁺ 2023-07-06
Hacker Newsのコメント

  • ざっと目を通しただけでも、Rustのregexクレートは本当に印象的
    BurntSushiが作った素晴らしいものは多いが、Rustのregexクレートは伝説的で、Rustエコシステムがかなり前から高性能で使いやすい正規表現ライブラリを備えていたのは、コミュニティにとって大きな恩恵
    Russ Coxの正規表現に関する記事シリーズも素晴らしく、正規表現が理論と実務の完璧な交差点のように感じられ始めたとき、夏の間に正規表現エンジンを作る際の参考にした
    今回の記事にある、より踏み込んだテスト変更の話も興味深く、エコシステムの中核を担うクレートだけに、こうした深いテーマの説明はありがたい
    正規表現はときに読みにくく、メール検証のような場面で乱用されることもあるが、ほぼすべての言語において最も密度の高いツールの1つ
    実用書としてはJeffrey FriedlのMastering Regular Expressionsくらいしかよく知らず、理論面はコンパイラ本が扱っていて、Dragon Bookも実装の観点から悪くなかった。他におすすめの正規表現本があれば知りたい

    • https://www.cs.princeton.edu/courses/archive/fall19/cos226/l... と https://kean.blog/post/lets-build-regex は、単純化した正規表現エンジン実装の入門として素晴らしい
      正規表現について非決定性有限オートマトンを作り、その結果得られる有向グラフを探索して、終了状態に対応する頂点へ到達可能ならマッチとみなす、という方式
      正規表現を使う人なら、この演習で思ったほど魔法ではないことが理解できるし、NFAの上をボールが跳ね回る様子を思い浮かべれば、本番で結局出会うことになる破滅的バックトラッキングのバグにも物理的な意味が生まれる
      元記事との関連では、https://github.com/rust-lang/regex/issues/822 の最後のBurntSushiのコメントが、ニッチなAPIの段落 https://blog.burntsushi.net/regex-internals/#problem-request... に有用な文脈を加えてくれる。複数の正規表現をテキストに対して同時に検索するのは非常に複雑だが非常に有用で、このパターンでコミュニティが何を作るのか楽しみ
    • 正規表現がパースに近い作業で真価を発揮する代表例は、区切り文字が多様な形式を扱うとき
      たとえば header:field1,field2,field3\"data\"hash のようにフィールド数が固定された形式や、suite~split/test1,test2@opt1:opt2^hw1^hw2#flags1#flags2 のように大半の要素が任意である形式では、split のような基本ツールでは足りず、正規表現がうまくはまる
      正規表現がすぐに読みにくくなる理由もここにある。1つの正規表現の中に、フィールド間の区切り文字、各フィールドの妥当性、どのフィールドが任意かがすべて混ざる
      これは本来3つの別個の関心事なのに、たいていの正規表現APIはそれを段階的に分離できず、全部を結合した1本の文字列しか受け取れない
    • このRegExライブラリは、多くのJavaScript実装のようにJITを使っているのだろうか。そうでないなら、JavaScriptがRustに勝つケースかもしれない
    • 最近RegExの作業を少ししていてこの記事をざっと見たが、使われている言語は他のエンジンと違ってエラーを返さないようなので、PikeVMを使っているように見えた
      言語上の制約と著作権保護の状況のため、RegEx機能を自前で新たに作らなければならず、正規表現は本当にブードゥーのように感じられることがある
      他のエンジンがどのくらい頻繁に使われているのかは分からないが、多くのプログラミング言語がPikeVMを使っているのなら、Googleがサーバー向けに独自OSを作り、特定の状況でより高速なエンジンを持ち出して数クロックサイクルでも節約しようとした理由も理解できる
      検索文字列に文字を数個追加するだけでパターンマッチングが大幅に遅くなることはよく知られている。「小銭を大事にすれば大金は自然とついてくる」ということわざは、RegExとクロックサイクルにもよく当てはまるし、毎秒数百万件のレコードを処理していた90年代の話を振り返ると、これでかなり裕福になったコーダーもいたのだろう
    • 最大の不満は、正規表現方言のちょっとした違い
      とくに方言や文脈ごとに引用符の扱いや式の終わらせ方があまりにも違うので、覚えようとするのは諦めて、必要になるたびに例を検索している

  • ActiveStateで、学校を出たばかりの同僚と一緒にKomodoエディタ用の正規表現デバッガを作れという仕事を任された
    伝説的なPerlの達人であるMark Jason Dominusを雇ってPerl正規表現エンジンにフックを入れてもらい、そのフックをUIに露出して、ユーザーが正規表現の実行をステップごとに見られるようにした
    今ではWebベースのツールのほうが優れているが、2001年当時のKomodoのRx Debuggerは最先端で、作業もとても楽しかった

    • 以前、オフライン正規表現デバッガが必要だったことがある
      エアギャップネットワークを扱っていたため、ツールを使う必要がある人たちはオンラインサイトにアクセスできず、どんな設計であっても作業データをオンラインツールに投入すること自体がまったく許されなかった
      ところが、ほとんどの努力はオンラインツールに集中していて、オフラインツールは https://regex101.com/ のようなものに比べると珍しく、機能も不足している
    • この用途で使える具体的なWebベースツールのおすすめが知りたい

  • 文字列ではないリストにもこれを使えるのか気になる
    文字のリストを検索して修正する強力な仕組みはあるのに、数値や日付のリストになった瞬間にすべて消えてしまうのがいつももどかしかった
    たとえばログイン試行日時のリストで、失敗5回以上のあとに成功が来るすべてのシーケンスを見つけたいなら、正規表現なら簡単だが、実際には自分でループ、フラグ、一時リストを作らなければならない
    リストを文字列に変換して処理してから戻すこともできるだろうが、欠点は明らかだ。文字列ベースの正規表現ほど速くなくても、任意のリスト型のための正規表現がなぜあってはいけないのかわからない
    以前作ったPythonプロトタイプも見つけた: https://github.com/boppreh/listregex
    とても遅いが、APIの実験としては満足できるし、パターン反転・交差・対応付けのような、正規表現にはない道具も提供している

    • できない。この regex ライブラリは文字列検索に強く結び付いており、それは意図的な設計判断だ
      この種の正規表現エンジンにジェネリックなアルファベットを持たせるのは、最初から無理がある。特に、API設計や主要ユースケースの性能を損なわない形で実現するのは現実的に非常に難しい
      性能を気にしないその手の正規表現エンジンを作ること自体は難しくない。たとえば公開している regex-lite クレートを持ってきて、望むだけジェネリックに書き換えることもできるし、その過程で興味深い難所に出会うだろう
      こういうものがまったく存在しないわけでもない。作ろうとする人はいる[1]。ただ、一般的な有用性をやや誇張しがちで、そのため普通は大きな traction を得られないようだ :-)
      [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html
    • C++ 標準ライブラリの std::basic_regex は、ユーザー定義の文字型に対するテンプレートクラスを公開することで、こうした試みをしている: https://en.cppreference.com/w/cpp/regex/basic_regex
      ユーザー定義の「文字」に必要な動作を定義する trait クラスを提供できる
      ただし性能は大きく落ち、任意の非文字オブジェクトをユーザー定義 std::basic_string に入れるのと同程度にしかうまく動かない可能性が高い
    • 値のスライディングウィンドウに対してマッチさせる API を何らかの形で定義する必要がある
      不可能ではないが、ほとんどの言語はそのための良いインターフェースを持っていない

  • コードやテキストファイルで何かを探すときは毎日 Ripgrep を使っていて、Windows、Linux、Mac、VSCode、Vim のどこで使うときも感謝している
    自分の人生と働き方を変えたソフトウェアの一つだ
    grep を無理やり使わなければならないと、すべてがシングルコア CPU で動き、データは遅い PATA/IDE の回転式ハードディスク上にある時代に戻ったような気分になる
    BurntSushi は偉大なプログラマーたちの間で十分に敬意を払われるべきだ

    • ripgrep には系譜がある。その前には ag、さらにその前には ack があり、どれも単なる grep よりはるかに優れたインターフェースを提供しようとしていた

  • 業務上の問題で、非常に長い正規表現1000万個以上から RegexSet を作る必要があった
    どのエンジンもデフォルトの状態では対処できず、Rust の RegexSet も標準設定では不十分だった
    それでも regex-automata と regex-syntax を使い、コードを読み進める過程は 2018 年当時でも非常に有益な学習材料だった
    結局、業務プロジェクトは Lucene API をモデルにしたが、その基礎は regex クレート群から学んだおかげで築けた

    • 正規表現1000万個はとてつもない規模だ。Aho-Corasick でもリテラル1000万個をかろうじて扱える程度だ
      今後の作業は、正規表現エンジンをより多くのパターンに対して、よりうまくスケールするようにすることだ。現状では1000万正規表現よりずっと手前で破綻するだろうし、その目標自体が本当に可能なのかも確信しにくい
      それでも今よりは確実に良くできる
      もちろん多パターン検索では Hyperscan が事実上のゴールドスタンダードだ。ただ、パターン1000万個をどこまでうまく処理できるかはわからない
    • 最初から詳しく書いていないところを見ると答えは「いいえ」なのだろうが、もし可能なら、その問題やプロジェクトが何だったのかもう少し共有してもらえるとうれしい

  • 以前 regex-automata クレートを試したことがあるが、内部 DFA に直接アクセスできるので、テキストエディタで使える唯一のライブラリだった
    一般的な正規表現ライブラリ API は入力が1つの連続した文字列であることを前提にしているが、この方式ならどんなテキストデータ構造とも両立できる

  • regex-automata クレート、それも初期の 0.2.0 リリースを使うコードを書いていたところにこの記事が出てきた
    新しい内部構造をまた掘り直す必要があるのか確認する時期のようだ
    まだ記事は読めていないが、とても興味深く、タイミングも絶妙な記事に見える
    数分後に見たところ、答えは「そうかもしれない」に近かったが、正式リリースになったことで、むしろコードを大きく単純化できそうだった
    さらに10分ほど後にはかなり painless で、新しい Builder::patch メソッドは完全なアップグレードだった
    追記すると、今でもあなたのすべての GitHub リポジトリでブロックされていて、多くのクレートが広く使われていることを考えると、少し不公平だと思う。元の出来事は覚えていない。regex クレート自体はいまや rust-lang 組織の配下にあるようだが、それでもまだやり取りできないものがある

    • regex-automata 0.2.0 のドキュメントにはこの件について大きな警告があり、0.1 を使うよう強く勧めていた: https://docs.rs/regex-automata/0.2.0/regex_automata/
      私も元の出来事は覚えていない。いろいろな理由で多くの人をブロックしているが、いまは解除しておいた

  • BioJulia は、コンパイル時に任意の Julia コードを挿入できる純粋な Julia 製正規表現エンジン Automa.jl を公開した。
    Rust の regex が Automa よりはるかに進歩している点を貶めたいわけではないが、正規表現の内部をライブラリとして公開した最初の事例という表現には賛同しがたい。

    • これは別の二つの話に聞こえる。
      たとえば PCRE2 には、言っていることに近く聞こえる「callout」サポートがある: https://www.pcre.org/current/doc/html/pcre2callout.html
      ragel や re2c のようなものも、似たことをしてきた。
      このブログで述べているのは、正規表現ライブラリ自体の内部を取り出して別個にバージョン管理されるライブラリにし、他の人が組み合わせられるようにすることだ。
      バックトラッカーは通常、エンジンがバックトラッカー一つだけなのでこのやり方はあまり自然ではないが、オートマトンベースのライブラリでは複数のエンジンをさまざまな形で組み合わせることが多い。
      それでもバックトラッカーでも、実際には公開していない正規表現パーサーや AST のようなものを公開することはできる。