fancy-regex

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

目标是尽可能高效。对于给定的正则表达式，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实现或回溯器。

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

理论

（本节采用较为非正式的风格；希望将来能进一步扩展）

基本思想是它类似于PCRE的回溯虚拟机，但在可能的情况下会委托给“内部”的RE引擎，如RE2（在这个案例中，是Rust的RE2）。对于不使用高级特性的子语言，库成为一个薄薄的包装。

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

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

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

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

当前状态

仍在开发中，尽管基本思想已经就位。目前，以下功能尚不可用

• 像find_iter和captures_iter这样的迭代方法
• 命名捕获组（包括在API中）
• 过程调用和递归表达式

致谢

非常感谢Andrew Gallant，他激发了这次方法的灵感，并创建了优秀的regex crate。

作者

主要作者是Raph Levien，得到了Robin Stocker的许多贡献。

贡献

我们乐意通过GitHub拉取请求接收贡献。请参阅CONTRIBUTING.md获取更多详细信息。

该项目最初是Google 20%项目，但当前没有作者在Google工作，因此已被分叉以进行社区维护。