MongoDB 仓库中的 RE2 正则引擎线性时间匹配、C API 与 Bazel 构建全解析【免费下载链接】mongoThe MongoDB Database项目地址: https://gitcode.com/GitHub_Trending/mo/mongoRE2 是一款以安全性为首要目标的正则表达式库自 2006 年起在 Google 及众多公司生产环境中服役其核心承诺是匹配时间与输入长度成线性关系即使面对不可信用户构造的恶意正则也不会发生灾难性回溯。本文以 MongoDB 仓库中随源码分发的 RE2位于 src/third_party/re2/dist/README.md为主体完整讲解其设计哲学、语法边界、C 匹配接口、子匹配提取、预编译对象、Options 配置、Unicode 语义、多引擎实现原理与三种构建方式并对照仓库内的 BUILD.bazel、re2.h 与测试源码给出源码级佐证帮助读者在 MongoDB 工程体系内正确编译、链接与使用 RE2。一、设计哲学为什么说安全是 RE2 的第一目标RE2 的诞生背景是传统回溯型正则引擎如 PCRE/Perl在处理(a|a)*b这类模式与恶意输入组合时匹配耗时可能随输入长度指数级增长即灾难性回溯Catastrophic Backtracking从而成为 DoS 攻击面。RE2 从根上规避了这个问题其保证可以归纳为三条线性时间保证匹配时间与输入字符串长度渐近线性相关不受正则表达式结构的影响受控内存预算解析器、编译器和执行引擎都在一个可配置的内存预算内工作预算耗尽时优雅失败fail gracefully而不是耗尽进程内存杜绝递归实现全程避免递归从根本上防止栈溢出。README 用一句非常精辟的对比总结了 RE2 与回溯引擎的气质差异RE2 是悲观的回溯引擎是乐观的。回溯引擎逐个尝试每个备选分支当第一个分支经常命中时会很快而 RE2并行评估所有分支避免了最后一个分支才命中时的性能惩罚代价是固定开销。正是这种悲观成就了 RE2 的安全。同时 README 也坦诚声明了两个非目标并非在所有场景下都比其他引擎快——更复杂的表达式会带来更大的常数因子更长的表达式会提高安全处理所需的开销并非实现 Perl/PCRE 的全部特性——凡已知只有回溯方案才能实现的构造一律不支持因此反向引用backreferences和环视断言look-around被明确排除子匹配提取仍然支持见下文。仓库中的证据RE2 以第三方库形式随 MongoDB 仓库源码分发目录为src/third_party/re2/dist/包含LICENSE、CONTRIBUTING.md、SECURITY.md、README.md、MODULE.bazelBazel Bzlmod 模块描述以及re2/、util/两个源码子目录。其多引擎实现文件分布在 re2/ 下包括nfa.ccNFA 执行、dfa.ccDFA 执行、onepass.ccOnePass 专用路径、bitstate.cc位状态模拟、parse.cc语法解析、compile.cc程序编译、prog.cc/h编译产物 Prog、simplify.cc正则化简等这些正是线性时间、无递归承诺的具体承载者我们将在多引擎架构一节展开。二、语法支持POSIX 模式与 Perl 模式RE2 支持两套语法模式默认是 Perl 模式模式语法来源匹配语义Perl 模式默认大多数 Perl 操作符与 Perl 选择相同的匹配结果POSIX 模式标准 POSIXegrep语法最左最长leftmost-longest匹配被排除的只有那些需要回溯才能实现、因而可能带来指数级运行时间的构造典型就是反向引用与广义断言generalized assertions。re2.h开头的注释进一步补充了语法速览例如\w单词字符、\d数字、\s空白、\b词边界、(?i)忽略大小写、.*?最小匹配等都是支持的同时明确\Z这类断言也不可用。在 C 字符串字面量中写正则需要双重转义如(\\w):(\\d)而使用 C11 原始字符串字面量则不需要R(hello (\w) world) // \w 匹配单词字符 R(version (\d)) // \d 匹配数字 R((?i)hello) // (?i) 开启忽略大小写 R(/\*(.*?)\*/) // .*? 最小匹配从源码看语法解析集中在 parse.cc它还配套了 mimics_pcre.cc该文件用于判断某个正则是否行为上与 PCRE 相同对应仓库中的mimics_pcre_test这从侧面印证了 RE2 在语法子集上对 PCRE 的刻意对齐与差异化管理。三、C 匹配接口FullMatch 与 PartialMatchRE2 的原生语言是 C核心只有两个基本操作符RE2::FullMatch要求正则与整个输入文本完全匹配RE2::PartialMatch在输入文本的子串中寻找匹配POSIX 模式下返回最左最长匹配Perl 模式下返回与 Perl 相同选择的结果。README 给出的最小示例assert(RE2::FullMatch(hello, h.*o)) assert(!RE2::FullMatch(hello, e)) assert(RE2::PartialMatch(hello, h.*o)) assert(RE2::PartialMatch(hello, e))注意FullMatch(hello, e)失败而PartialMatch(hello, e)成功——这正是两个操作符语义差异的直观体现。re2.h中还给出了提取第一个数字的经典用例int number; ABSL_CHECK(RE2::PartialMatch(x*100 20, (\\d), number)); ABSL_CHECK_EQ(number, 100);错误码枚举re2.h 定义了完整的ErrorCode枚举编译失败后可通过re.error()获取常见值包括ErrorBadEscape非法转义序列ErrorBadCharClass/ErrorBadCharRange字符类或其区间非法ErrorMissingBracket/ErrorMissingParen缺少闭合的]或)ErrorUnexpectedParen多余的闭合)ErrorTrailingBackslash正则末尾孤立的\ErrorRepeatArgument/ErrorRepeatSize/ErrorRepeatOp重复操作符参数缺失、参数非法或操作符非法ErrorBadPerlOp非法 Perl 操作符ErrorBadUTF8正则中含非法 UTF-8ErrorBadNamedCapture命名捕获组非法ErrorPatternTooLarge模式过大编译失败四、子匹配提取string / 整数 / string_view两个匹配函数都接受额外的输出参数用于存放子匹配submatch参数类型可以是string*、整数类型指针或absl::string_view*。README 特别解释absl::string_view与std::string_view非常相似只是出于历史原因 RE2 使用前者它是一个指向原始输入文本的指针 长度行为像字符串但不持有自己的存储因此一旦原始文本被删除或超出作用域就不能再使用这个 view——与裸指针的注意事项一致。README 给出的完整示例保留全部细节// 解析成功。 int i; string s; assert(RE2::FullMatch(ruby:1234, (\\w):(\\d), s, i)); assert(s ruby); assert(i 1234); // 失败ruby 无法被解析为整数。 assert(!RE2::FullMatch(ruby, (.), i)); // 成功不提取数字。 assert(RE2::FullMatch(ruby:1234, (\\w):(\\d), s)); // 成功跳过 NULL 参数。 assert(RE2::FullMatch(ruby:1234, (\\w):(\\d), (void*)NULL, i)); // 失败整数溢出导致 i 中不保存值。 assert(!RE2::FullMatch(ruby:123456789123, (\\w):(\\d), s, i));re2.h对提取语义补充了三条重要细节失败时不改动匹配失败时任何输出对象都不会被修改转换失败即中止匹配成功后按顺序把各子匹配转换并赋给输出对象直到某个转换失败为止对string/string_view这类不检查内容的类型转换不会失败因此常见情况下失败原因就是匹配失败整数溢出算失败目标文本无法被解析为对应整数类型如超出范围时FullMatch/PartialMatch返回false——这正是上面最后一个断言的设计意图。另外re2.h注释给出了一条性能经验请求子匹配会让成功匹配明显变慢目前甚至慢于 PCRE但失败匹配与不提取子匹配的匹配则非常快——这与 RE2并行评估所有分支、快速否决的悲观设计一脉相承。运行时参数个数FullMatchN 与 Arg当参数个数在运行时才能确定例如正则本身是动态计算的时可以改用N系列操作const RE2::Arg* args[10]; int n; // ... 用 RE2::Arg 对象的指针填充 args ... // ... 将 n 设为 RE2::Arg 对象的个数 ... bool match RE2::FullMatchN(input, pattern, args, n);上面的调用等价于RE2::FullMatch(input, pattern, *args[0], ..., *args[n-1])。RE2::Arg类在re2.h中定义是把用户传入的指针包装成特殊 Arg 对象的机制。进制解析Hex / Octal / CRadix默认情况下传入数值指针时对应文本按十进制解析。通过RE2::Hex()、RE2::Octal()、RE2::CRadix()包装指针可以改变进制其中CRadix按 C 风格识别0x十六进制与0前缀八进制无前缀则回退到十进制int a, b, c, d; ABSL_CHECK(RE2::FullMatch(100 40 0100 0x40, (.*) (.*) (.*) (.*), RE2::Octal(a), RE2::Hex(b), RE2::CRadix(c), RE2::CRadix(d)); // 结果a b c d 64五、预编译正则对象RE2 re(...)前面所有示例在每次调用时都重新编译正则。高频路径下应把编译结果缓存为RE2对象编译一次、复用多次RE2 re((\\w):(\\d)); assert(re.ok()); // 编译成功若失败查看 re.error() assert(RE2::FullMatch(ruby:1234, re, s, i)); assert(RE2::FullMatch(ruby:1234, re, s)); assert(RE2::FullMatch(ruby:1234, re, (void*)NULL, i)); assert(!RE2::FullMatch(ruby:123456789123, re, s, i));关键事实来自 re2.hRE2对象即预编译的正则表达式对应一个内部Prog程序见下文编译流水线RE2对象可被多个线程安全地并发使用——这在多线程服务端场景如 MongoDB 这类数据库的查询/校验路径中是重要的可用性保证re.ok()判断编译是否成功re.error()返回失败详情ErrorCode枚举 可读文本。六、OptionsQuiet、Latin1、POSIX 与自定义选项构造函数接受可选的第二个参数用于覆盖默认选项。三个最常用的预置选项预置选项作用RE2::Quiet静默正则解析失败时通常打印到 stderr 的错误信息RE2::Latin1禁用 UTF-8按 Latin-1 解释模式与输入RE2::POSIX使用 POSIX 语法与最左最长匹配Quiet的典型用法——解析非法模式而不污染 stderrRE2 re((ab, RE2::Quiet); // 解析失败时不要写 stderr assert(!re.ok()); // 可通过 re.error() 查看细节完整的可配置项大小写折叠、最大内存、最长匹配、日志级别、encoding、never_nl、dot_nl、one_line、longest_match等定义在RE2::Options类中位于 re2.h 的class Options。README 明确建议可以自行声明一个RE2::Options对象并按需配置例如RE2::Options opts; opts.set_encoding(RE2::Options::EncodingLatin1); // 或 EncodingUTF8 opts.set_log_errors(false); // 等价于 Quiet RE2 re(pattern, opts);上述set_encoding/set_log_errors为Options提供的典型 setter完整清单以 re2.h 为准。七、Unicode 处理基于码点不做归一化RE2 在Unicode 码点code point层面工作不进行任何归一化normalization。README 给出的例子非常典型正则/ü/U00FC带分音符的 u不能匹配输入üU0075 U0308u 后跟组合分音符。因为前者是单个预组合码点后者是两个码点序列二者在码点层面不相等。归一化本身是个庞大复杂的主题涉及 NFC/NFD 等RE2 的立场是不越俎代庖。README 给出的实用建议是如果确实需要这类匹配请在预处理阶段把正则表达式和输入文本都归一化后再交给 RE2。re2.h还补充了一条与 UTF-8 相关的语义使用 UTF-8 编码时忽略大小写匹配执行的是简单大小写折叠simple case folding而非完整折叠full case folding——两者在个别语言字符如涉及多字符映射的情况上行为不同需要精确语义时应查阅 Unicode 标准UAX #15 等资料。八、增量扫描Consume 与 FindAndConsume除了FullMatch/PartialMatchre2.h还记录了两种适合流式/增量解析的操作RE2::Consume把匹配锚定在字符串开头匹配成功后推进absl::string_view越过已匹配文本适合逐行解析var value这类固定格式std::string contents ...; // 填充字符串 absl::string_view input(contents); // 用 string_view 包一层 std::string var; int value; while (RE2::Consume(input, (\\w) (\\d)\n, var, value)) { // ...处理 var/value... }注意若正则可能匹配空串input将不前进推进 0 字节循环体必须检查该情况并手动前进或跳出否则会死循环。RE2::FindAndConsume与Consume类似但不把匹配锚定在开头例如反复提取字符串中的所有单词RE2::FindAndConsume(input, (\\w), word)九、构建与安装make / CMake / Bazel 三条路径RE2 支持 GNU make、CMake、Bazel 三种构建方式。构建 RE2 本身需要 C17 编译器与 Abseil 库构建测试和基准还需要 GoogleTest 与 Google Benchmark。9.1 GNU make 方式最简make make test make benchmark make install make testinstall9.2 依赖获取Linuxapt install libabsl-dev libgtest-dev libbenchmark-devmacOSbrew install abseil googletest google-benchmark pkg-config-wrapperWindowsvcpkg install abseil gtest benchmark或vcpkg add port abseil gtest benchmark9.3 CMake 方式如果标准 Makefile 在查找依赖时遇到问题切换到 CMake 往往能解决rm -rf build cmake -DRE2_TESTON -DRE2_BENCHMARKON -S . -B build cd build make make test make installCMake 相关的几个要点启用 benchmark 时make test会构建并运行测试二进制同时构建regexp_benchmark二进制但不运行它不需要测试/基准时省略对应-D参数即可此时也不需要 GoogleTest/Benchmark 依赖-DRE2_USE_ICUON会引入 ICU Unicode 库依赖同时扩展\p与\P模式可用的属性名列表如更多 Unicode 属性类别CMake 还能生成 Visual Studio、Xcode 工程以及 Cygwin、MinGW、MSYS makefile。Visual Studio 用户需要 2019 或更高版本Cygwin 用户必须从 Cygwin 命令行而非 Windows 命令行运行 CMake。作为依赖集成进自有 CMake 工程时有两种方式add_subdirectory()依赖的源码位于你工程的子目录中与find_package()依赖的二进制已构建并安装到系统。两种方式下target_link_libraries(... re2::re2)都应开箱即用。9.4 Bazel 方式MongoDB 仓库的集成形态独立使用 Bazel 构建 RE2 时Bazel 会自动处理依赖仍需自行下载 Bazel可通过 Bazelisk 管理版本在仓库内执行bazelisk build :all bazelisk test :all在 MongoDB 仓库中RE2 已经通过 Bazel 完整接入见 src/third_party/re2/dist/BUILD.bazel。该文件的核心是一个cc_library(name re2)目标从中可以读出非常具体的集成信息源码清单包含re2/re2.cc、re2/compile.cc、re2/dfa.cc、re2/nfa.cc、re2/onepass.cc、re2/bitstate.cc、re2/parse.cc、re2/prog.cc、re2/regexp.cc、re2/simplify.cc、re2/filtered_re2.cc、re2/set.cc、re2/mimics_pcre.cc、re2/tostring.cc、re2/unicode_casefold.cc、re2/unicode_groups.cc、re2/perl_groups.cc以及util/rune.cc、util/strutil.cc等公共头文件re2/filtered_re2.h、re2/re2.h、re2/set.h、re2/stringpiece.h依赖一组 Abseil 目标abseil-cpp//absl/...包括strings、hash、container:flat_hash_map/set、container:inlined_vector、container:fixed_array、synchronization、types:span、types:optional、log、base等——与 README构建需要 Abseil的说明完全对应平台差异copts/linkopts通过select按平台调整-pthread——macOS 与 WebAssemblywasm32/wasm64/emscripten/wasi以及 Windows 不传-pthread其余平台默认加上注释明确指出WebAssembly 的线程支持在每一层都很棘手可见性visibility [//visibility:public]即仓库内其他 Bazel 目标可以公开依赖该库。依赖方工程若通过 Bazel 使用 RE2需保证编译标准不低于C17README 明确要求并指向.bazelrc作为示例。十、测试体系从单元测试到穷举测试BUILD.bazel中暴露了完整且分层清晰的测试矩阵全部位于 re2/testing/小规模单元测试size smallcharclass_test字符类、compile_test编译、parse_test语法解析、simplify_test正则化简、regexp_test、re2_test核心 API、re2_arg_testArg 参数机制、search_test、set_test批量匹配 Set、filtered_re2_test预过滤、possible_match_test可能的匹配前缀、required_prefix_test必要前缀、mimics_pcre_test与 PCRE 行为对齐度、string_generator_test测试用字符串生成器大规模测试size largedfa_testDFA 引擎专项、exhaustive_test及exhaustive1/2/3_test穷举测试对生成的正则与字符串集合做全量比对这是验证与参考语义一致的关键手段、random_test随机模糊测试基准regexp_benchmarktestonly 1的cc_binary依赖google_benchmark。这套单元 穷举 随机 基准的测试结构正是 RE2 敢在安全敏感场景不可信正则 不可信输入下承诺线性时间的重要底气。另有一个testing库testonly 1把backtrack.cc参考回溯实现用于对照验证、exhaustive_tester.cc、regexp_generator.cc、string_generator.cc与util/pcre.cc组织起来作为参照实现支撑穷举测试。十一、核心实现原理编译流水线与多引擎架构结合 re2/ 目录源码可以把 RE2 的工作方式拆成编译期与执行期两段编译流水线源码级parse.cc把正则字符串解析为 ASTRegexp对象树定义于regexp.h同时执行语法校验并生成上文提到的ErrorCodesimplify.cc对Regexp做等价化简如折叠嵌套、规并字符类、re2内部 normalization缩小后续编译规模compile.cc把化简后的Regexp编译成指令形式的程序Progprog.h/prog.cc这是 NFA/DFA 等执行引擎统一消费的中间表示配套的unicode_casefold.cc/unicode_groups.cc/perl_groups.cc是由make_unicode_casefold.py、make_unicode_groups.py、make_perl_groups.pl等脚本生成的 Unicode 数据表支撑(?i)折叠、\p{...}属性与 Perl 字符类。多引擎执行执行期RE2 内部按输入与正则特征在多个执行器间选择对应文件nfa.ccNFA 模拟、dfa.ccDFA 构造与缓存、onepass.ccOnePass无分支/少分支正则的专用快速路径、bitstate.cc位向量状态集模拟。这种多引擎 自动选择的架构配合前面提到的内存预算预算耗尽时优雅降级/失败与无递归约束共同保证了最坏情况下的线性时间与可控资源占用。pod_array.h、sparse_array.h、sparse_set.h、bitmap256.cc等数据结构文件则是这些引擎高效运行的基础设施。批量与预过滤Set 与 FilteredRE2仓库还提供了两类面向规模化场景的 APIRE2::Setset.cc/set.h把大量正则一次性编译成一个集合对一段输入同时测试匹配了集合中的哪些正则避免逐个编译、逐个匹配的开销FilteredRE2filtered_re2.cc/filtered_re2.h在真正执行匹配前先对所有正则做必要前缀/可能匹配前缀的预计算prefilter.cc、prefilter_tree.cc先用廉价测试快速排除绝大多数不可能命中的正则再对候选集做精确匹配——适合数千条规则对一段文本做路由/分类的服务端场景。十二、多语言生态官方封装与同源移植RE2 原生实现是 C但生态覆盖广泛官方 Python 封装位于 RE2 仓库的python/目录发布在 PyPI 上名为google-re2。README 特别提醒PyPI 上还有一个re2包但那并非 RE2 作者发布、且已不再维护请务必使用google-re2其他语言的非官方封装包括Ccre2、Dre2d、Erlang、Inferno、Node.jsnpm 上的re2、OCamlJane Street 维护、Perlre::engine::RE2CPAN、R、Ruby、WebAssemblyre2-wasm等同源移植RE2J是把 RE2 C 代码移植为纯 Java 的版本RE2JS是 RE2J 到 JavaScript 的移植同原理不同代码Go 的regexp标准包与 Rust 的regexcrate 与 RE2不共享代码但遵循相同原则、接受相同语法、提供相同的效率保证——也就是说即使在其他语言栈中也可以用同一套线性时间、无灾难性回溯的思维模型。十三、在本仓库中的定位与使用建议MongoDB 将 RE2 以随源码分发的第三方库形式放在src/third_party/re2/dist/通过 Bazel 的cc_library(name re2)目标BUILD.bazel对外暴露仓库内其他目标可以直接依赖使用。需要指出的是MongoDB 服务端自身的通用正则表达式功能如$regex查询走的是PCRE2路线——src/mongo/util/pcre.h 明确说明它是为 PCRE2 库封装的 MongoDB C 包装层且刻意通过封装隔离了对 pcre2 头文件的直接依赖。因此在本仓库中RE2 是作为独立、可选、安全优先的正则基础设施随仓库提供的如果你的组件要处理不可信输入上的正则匹配如用户提供的模式做匹配/过滤/校验且能接受 RE2 的语法子集不支持反向引用与环视RE2 的线性时间保证是最合适的选择如果需要 Perl/PCRE 全量语法反向引用、环视等则应使用服务端已有的 PCRE2 封装mongo::pcre无论选择哪条路径本仓库的 Bazel 目标已经就绪构建时只需正确声明依赖并保证 C17 编译标准即可。结语从设计目标到多引擎实现从FullMatch/PartialMatch到Consume/FindAndConsume从 make/CMake 到仓库内现成的 Bazel 目标RE2 用悲观但安全的方式解决了正则引擎最棘手的可用性问题。对照 README.md 与 re2.h、BUILD.bazel 及 re2/testing 的测试源码读者既可以在 MongoDB 的 Bazel 工程内直接复用这一安全正则基础设施也可以把这套线性时间 内存预算 无递归的工程方法论迁移到自己的系统中。【免费下载链接】mongoThe MongoDB Database项目地址: https://gitcode.com/GitHub_Trending/mo/mongo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考