fancy-regex

一个用于编译和匹配正则表达式的 Rust 库。它使用混合正则表达式实现，旨在支持相对丰富的功能。特别是，它使用回溯来实现“高级”功能，如先行断言和回溯，这些功能在仅基于 NFA 的实现中不受支持（例如，在 RE2 中，并在 Rust 的 regex Crates 中实现）。

目标是尽可能高效。对于给定的正则表达式，NFA 实现的运行时间与输入长度成线性关系，而在一般情况下，回溯实现的指数级爆炸。在通过子结构逻辑对正则表达式指数级运行时间的静态分析中给出的例子是：

import re
re.compile('(a|b|ab)*bc').match('ab' * 28 + 'ac')

在 Python 中（在 2.7 和 3.5 上测试过），这个匹配需要 91 秒，每次额外重复 'ab' 都会翻倍。

因此，许多支持者 提倡 一种纯粹基于 NFA（非确定性有限自动机）的方法。即便如此，回溯和先行断言确实增加了正则表达式的丰富性，并且在文本编辑器的语法高亮等应用中经常被使用。特别是，基于 Oniguruma 回溯引擎的 TextMate 的 语法定义，现在被许多其他流行编辑器使用，包括 Sublime Text 和 Atom。这些语法定义通常使用回溯和先行断言。例如，以下正则表达式捕获单个 Rust 原始字符串：

r(#*)".*?"\1

没有 NFA 可以表达这个简单而有用的模式。然而，回溯实现可以有效地处理它。

此包是首批同时处理这两种情况良好的包之一。上述指数级爆炸的情况在 258 纳秒内运行。因此，它应该是需要丰富性和性能的应用程序的一个非常有吸引力的替代方案。

关于最坏情况性能的警告

基于NFA的方法为最坏情况性能提供了强有力的保证。对于包含“高级”功能（如反向引用和前瞻）的正则表达式，本模块不提供相应的保证。如果攻击者可以控制将要匹配的正则表达式，他们将能够成功发起拒绝服务攻击。请务必小心。

有关示例，请参阅 PERFORMANCE.md。

混合方法

一种可行的方法是检测“高级”功能的存在，并根据是否使用它们来选择NFA实现或回溯器。

然而，本模块试图更加细致。相反，它实现了一种真正的混合方法。本质上，它是一个回溯虚拟机（正如在 Regular Expression Matching: the Virtual Machine Approach 中详细解释的那样），其中虚拟机中的一个“指令”委托给内部的NFA实现（在本例中是Rust的regex crate，尽管使用RE2或Go的regexp包也可以实现类似的方法）。然后进行一项分析，以确定每个子表达式是否“困难”，或者是否可以委托给NFA匹配器。目前，它是急切的，并将尽可能多的任务委托给NFA引擎。

理论

（本节以较为非正式的风格编写；我希望进一步扩展它）

基本思想是，它是一个类似于PCRE的回溯虚拟机，但它尽可能多地委托给“内部”RE引擎，如RE2（在本例中是Rust的）。对于不使用高级功能的子语言，库变成了一个薄包装。

否则，您将进行一项分析，以确定可以委托什么，以及必须回溯什么。我原以为这可能会很棘手，但实际上相当简单。第一阶段，只需将每个子表达式标记为“困难”（在反向引用、前瞻等中引用的组），并将这个信息传递上去。您还进行了一些额外的分析，主要是确定表达式是否有常量匹配长度和最小长度。

第二阶段是自顶向下的，并且您携带一个上下文，还有一个布尔值表示它是否是“困难”的。直观地说，一个困难上下文是指匹配长度将影响未来回溯的情况。

如果子表达式简单且上下文简单，则在虚拟机中生成一个指令委托给内部的NFA实现。否则，生成类似于回溯引擎的虚拟机代码。大多数表达式节点相当直接；唯一有趣的情况是连接（子表达式的序列）。

即使这个也不是特别复杂。首先，确定一个由常量匹配长度的简单节点的前缀（这不会影响回溯，因此可以安全地委托给NFA）。然后，如果上下文简单，确定一个后缀由简单节点组成。这两个都委托给NFA。对于中间的节点，递归编译。在简单上下文中，这些中的最后一个也获得一个简单上下文；其余的都在困难上下文中生成。因此，从概念上讲，困难上下文是从右到左，从父节点到子节点的流动。

当前状态

仍在开发中，尽管基本思想已经到位。目前，以下功能尚未实现：

• 过程调用和递归表达式

致谢

非常感谢 Andrew Gallant，他的启发性的对话激发了这个方法，以及他创建的优秀regex crate。

作者

主要作者是Raph Levien，Robin Stocker做出了许多贡献。

贡献

我们乐于接受通过GitHub pull请求的贡献。有关更多详细信息，请参阅 CONTRIBUTING.md。

该项目最初是一个Google 20%项目，但由于当前作者都不在Google工作，因此已被分叉并由社区维护。