re2

RE2は、2006年にGoogleで開発された、効率的かつ原理に基づいた正規表現ライブラリです。その主な設計目標は安全性であり、信頼できないユーザーからの正規表現を、壊滅的なバックトラッキングやサービス拒否攻撃のリスクなしに処理できることを保証します。PCRE、Perl、Pythonのreモジュールなどの従来のエンジンとは異なり、RE2はマッチング時間が入力文字列の長さに対して線形であることを保証します。 主な特徴は以下の通りです： - **安全性**: RE2は再帰を回避し、設定可能な予算でメモリ使用量を制限し、超過した場合は優雅に失敗します。これにより、バックトラッキングエンジンで一般的なスタックオーバーフローや指数関数的な実行時間の問題を防ぎます。 - **パフォーマンス**: 単純なパターンでは並列評価のオーバーヘッドにより他のエンジンより常に速いわけではありませんが、複雑な式では代替案を逐次的ではなく並列に評価することで、一貫したパフォーマンスを提供します。 - **構文サポート**: デフォルトのPerlモードでは、ほとんどのPerl演算子を受け入れますが、バックトラッキングを必要とするもの（例：後方参照、先読みアサーション）は除外します。POSIXモードでは、左最長マッチングを備えた標準POSIX（egrep）構文をサポートします。 - **Unicode処理**: RE2はUnicodeコードポイントを直接操作し、正規化は行いません。必要に応じて、ユーザーは事前に入力とパターンを正規化する必要があります。 このライブラリはC++で実装されており、C++17コンパイラとAbseilライブラリが必要です。GNU make、CMake、またはBazelを使用してビルドできます。C++ネイティブですが、Python（google-re2）用の公式ラッパーが存在し、Node.js、Java（RE2J）、JavaScript（RE2JS）、D、Erlang、OCaml、Perl、R、Ruby、WebAssembly用のコミュニティポートも利用可能です。GoやRustなどの他の言語にも、RE2の原則に従った類似のライブラリがありますが、コードは共有していません。