目录

• 
  
• 简要历史
• 问题
• 问题：组合困难
• 问题：测试困难
• 问题：对小众API的请求
• 问题：完全编译的DFAs

--------------

简要历史

2012年9月，有人在Rust仓库提交了一个议题，请求将正则表达式库添加到Rust发行版中。Graydon Hoare后来评论说他们更倾向于使用RE2。对于那些不知道的人，RE2是一个使用有限自动机保证最坏情况下搜索时间为O(m*n)的正则表达式引擎，同时提供类似Perl的语法，不包括那些不知道如何高效实现的特性。RE2的设计由其作者Russ Cox在一系列关于使用有限自动机实现正则表达式引擎的文章中描述。

2014年4月，我出现并说我正在开发一个受RE2启发的正则表达式引擎。我将Cox的文章视为如何构建正则表达式库的蓝图。不久之后，我发布了一个RFC，提议将正则表达式库添加到“Rust发行版”中。这是在Rust 1.0和Cargo（第二版，不是第一版）之前，而“Rust发行版”指的是rustc、std和几个“支持”库，它们都被捆绑在一起。这个RFC提议将一个正则表达式crate添加到支持库的列表中。

十天后，RFC被批准。第二天，我向rust-lang/rust提交了一个pull请求，将其添加到Rust发行版中。那时候事情发展得很快。还要注意，我最初将crate称为regexp。涉及Rust的PR涉及到命名的讨论，最终导致它被称为regex。

两年后的2016年5月，我写了一个RFC来发布regex 1.0。这花了几个月才被批准，但直到几年后的2018年5月，我才真正发布了regex 1.0。

在regex 1.0发布之前，我一直在稳步工作，全面重新构想crate内部。从2018年3月的一个提交消息中：

[regex-syntax]的重写旨在成为彻底改革整个regex crate的第一阶段努力。

那时我并不清楚自己的方向，但在2020年3月，我开始认真重写实际的匹配引擎。三年多后，regex 1.9已经发布了，完成了重写。

问题

正则表达式crate面临的问题是什么，需要全面重写？而且，为什么要将重写的内部作为自己的crate发布？

这里有很多讨论。

问题：组合困难

遵循RE2的传统，正则表达式crate包含许多不同的策略，可以用来实现搜索。有时在单个搜索调用中使用多种策略。

通常有两种维度，常常相互对立，每种策略都有：性能和功能。更快的策略往往在功能上更有限。例如，一个快速策略可能能够报告匹配的开始和结束，但不能报告正则表达式中每个捕获组的偏移量。相反，一个较慢的策略可能需要报告每个捕获组的偏移量。

当我第一次编写正则表达式crate时，我实现了一个策略（PikeVM），并没有为如何结合替代策略做任何深思熟虑的设计工作。最终新策略被有机地添加：

一个BoundedBacktracker，可以像PikeVM一样报告捕获组的偏移量，但是使用回溯策略。其主要限制是用于确保其回溯的内存使用被限制在O(m*n)，所以它只能用于小的haystacks/regexes。其主要优点是通常比PikeVM快。一个混合NFA/DFA（也称为“lazy DFA”），可以非常快速地执行，但只能报告匹配的开始和结束。它完全忽略了捕获组。一个字面策略，其中正则表达式对应于一个既是有限又是小的语言。例子：foo, foo{2}, foo|bar, foo[1-3]。在这种情况下，我们可以使用单一或多字符串搜索算法，而不需要任何正则表达式引擎。

（我们将在后面更详细地讨论这些策略为何有这些权衡。）

随着上述策略的出现，它们的组合也随之而来：

当调用者请求捕获组的偏移量时，通常首先运行lazy DFA以找到匹配的边界，然后只运行PikeVM或BoundedBacktracker来找到捕获组的偏移量会更快。通过这种方式，特别是在匹配相对罕见的情况下，大部分工作由更快的lazy DFA完成。当正则表达式以对应于小有限语言的前缀开始时，我们可以实施一个预过滤器，搜索该语言的出现。每个出现对应于整体正则表达式的候选匹配。对于每个这样的候选匹配，我们运行完整的正则表达式引擎来确认它是否是实际匹配。例如，foo\w+会在haystack中寻找foo的出现，然后在foo出现的位置偏移处运行正则表达式foo\w+。如果匹配，停止并报告它。否则，在上一个foo出现之后重新启动搜索foo。

随着时间的推移，我想添加更多的策略，并添加更多的组合方式。但在有机成长的基础设施中，正则表达式crate开始承受不住其重量。粗略地说，所有以下都是问题：

不是所有策略都必然被设计为与其他策略组合。例如，PikeVM是第一个策略，它就受到了这个问题的影响。具体来说，它不能处理在子序列的切片中开始和停止搜索，这对于与lazy DFA组合是必要的。例如，在某个时候，PikeVM会说\babc\b在abcxyz中匹配，如果它的搜索从偏移0开始并在偏移3结束。但尾部的\b不应该在c之后匹配，因为后面跟着一个x。很难理解对于任何给定的正则表达式将使用哪种策略。有重复的匹配表达式重新实现各种逻辑，这些逻辑很容易不同步。构建正则表达式并没有全面考虑一些策略根本不需要被构建的事实。例如，我在重写之前（重写之前）向正则表达式crate添加了一个优化（在重写之前），它只使用Aho-Corasick来处理像foo1|foo2|...|fooN这样的正则表达式，但在不也导致一个Thompson NFA被不必要地构建的情况下，以这种方式实现这个优化是非常hacky的。

基本上，至少许多策略需要改头换面，组合它们的基础设施可能需要被重写。

问题：测试困难

虽然正则表达式crate公开了一个作为单个正则表达式引擎的公共接口，正如我们刚刚讨论的，它根据情况内部使用多种策略。这些策略中的许多本身就是正则表达式引擎，确保它们在相同输入上的行为相同是绝对关键的。

作为一个例子，一个常见的情况是当调用者请求每个捕获组的偏移量时。这通常的工作方式是运行lazy DFA来找到匹配的边界，然后在匹配的边界上运行一个较慢的正则表达式引擎，如PikeVM或BoundedBacktracker来报告捕获组的偏移量。那么，如果lazy DFA找到了其他引擎没有找到的匹配怎么办？糟糕，这是一个错误。

这里的问题是，在regex 1.9之前，所有内部使用的策略都不是任何公共API的一部分，这使得它们难以独立测试。当然可以测试公共API，但是选择使用哪个内部正则表达式引擎的逻辑足够复杂，以至于模式本身和将被内部使用的正则表达式引擎之间并不总是有一个清晰和明显的映射。而且，随着逻辑的发展，这种映射可以改变。所以仅针对公共API编写测试并不能清晰地覆盖所有内部引擎。即使可以这样做，也会使调试测试失败变得更加烦人，因为你必须理解选择哪些策略的逻辑。

解决这个问题的一个方法是将所有测试放在crate内部，以便测试可以访问内部API。但你真的想在所有引擎上使用相同的测试，所以这样做需要以某种结构化格式定义测试，遍历它们并在每个引擎上运行它们。由于测试基础设施并非以测试每个单独策略为意图编写的，我最终没有选择这条路。

相反，我做了一些不神圣的hack，使现有的测试套件工作：

我公开了一些内部API，使其成为可能从外部配置和构建内部策略。我使其可以实际使用这些内部API构建主Regex类型，使用一个未记录的From实现。我使用宏编写测试。我为我想要测试的每个内部正则表达式引擎创建了测试目标，每个测试目标负责以我想要测试的正则表达式引擎的方式定义上述宏。

总的来说，这是一个hacky的混乱，真的需要重新思考。公开其自己的公共API并不是严格需要改善情况，但它确实可以运行一个测试套件，涵盖所有引擎，而不必依赖未记录的API或将测试放在crate内部。

问题：对小众API的请求

多年来，对正则表达式crate有一些额外API的请求，但我认为这些请求太小众，不值得扩大API表面，或者我不太清楚API应该是什么。

最受欢迎的这类请求之一是更好的多模式支持。也就是说，正则表达式crate提供了一个RegexSet API，允许搜索零个或多个正则表达式的可能重叠匹配。问题是，API只报告哪些模式在haystack中匹配。无法使用API获取匹配偏移量或捕获组的偏移量。

虽然有用，但如果它支持完整的Regex API，它将更有用。

与添加多个内部正则表达式引擎和测试策略一样，RegexSet API是以相当hacky的方式添加到现有实现中的。使其能够报告匹配偏移量将需要对所有现有引擎进行重大重构，或者重写。

但除此之外，对我来说，如何在RegexSet API执行的重叠搜索的上下文中暴露报告匹配偏移量的API还不清楚。有更多空间尝试替代API，例如，一个RegexSet，它执行不重叠的搜索并报告匹配偏移量，这将是其他人可以使用的，而不需要复杂化正则表达式crate API。

还有其他的API请求：

执行锚定搜索的能力，而不需要在模式中放置^。这在你知道匹配的haystack部分的上下文中特别有用，但你想提取捕获组。它也适用于只报告相邻匹配的迭代器。正则表达式crate可以增强以支持这一点，但扩展现有API没有容易的方法，要么复制所有搜索例程，要么不必要地使“锚定模式”成为可以传递给正则表达式的选项。（在那个时候，你还不如在模式的开头放置^。）在不进行内部同步的情况下运行正则表达式搜索的能力，以获得用于搜索的可变scratch空间。人们可能希望这样做，以避免某些情况下的同步成本。但为了做到这一点，也需要复制搜索API，并暴露一个表示“可变scratch空间”的新类型。在流和/或非连续haystacks上执行正则表达式。这对于在文本编辑器中经常发现的数据结构，如ropes，特别有用。这是一个大话题，我甚至没有尝试过，但我希望随着更多的正则表达式crate内部暴露，其他人可以更容易地尝试解决这个问题。

通过发布一个包含正则表达式crate内部的新的单独版本控制的crate，它为人们想要的更多API提供了“呼吸空间”，而不需要在服务于绝大多数正则表达式用例的通用正则表达式API中增加混乱。也就是说，通过针对“专家”用例，我们不试图保持API小巧简单。实际上，正如我们将看到的，regex-automata的API是庞大而复杂的。并且通过使其单独版本控制，我们可以比正则表达式crate更快地发布破坏性更改。

这种推理与导致发布regex-syntax crate的推理并不太远。也就是说，人们（包括我自己）想要为他们的项目访问正则表达式解析器。我当然不想在正则表达式crate本身中暴露一个解析器，因为增加了复杂性，而且我想能够独立于正则表达式crate发展解析器及其数据类型。（也就是说，regex-syntax的破坏性更改版本比正则表达式本身更频繁。）通过将其放入一个单独的crate中，我可以同时将其作为正则表达式crate的实现细节使用，同时也使其可供其他人使用。

问题：完全编译的DFAs

regex-automata的诞生实际上不是我重写正则表达式crate的结果。它的诞生与构建完全编译的DFAs、序列化它们，然后提供一个裸机搜索运行时，可以零拷贝反序列化这些DFAs并用它们进行搜索的愿望相吻合。我使用regex-automata的原始版本为在bstr中实现各种Unicode算法构建DFAs。

在构建regex-automata的初始版本过程中，我意识到我需要重建一个NFA数据结构和一个编译器，这与正则表达式crate中发现的一个非常相似。在某个时刻，我开始思考是否可以共享该代码，因为这是相当非平凡的，并且是一个发生许多有趣优化的地方。

我曾短暂考虑过构建一个像regex-nfa这样的新crate，正则表达式crate和regex-automata都可以依赖于它。但经过更多思考，很明显有更多的代码可以在regex-automata和regex之间共享。例如，许多确定化过程可以通用地编写，使其适用于完全编译的DFAs和lazy DFAs。

在那个时候，正确的抽象边界似乎是更接近“正则表达式引擎”，而不是“NFA”。所以我将regex-automata重新定义为不仅仅是DFAs，而是各种正则表达式引擎的集合。计划大致是，将所有的正则表达式引擎都放在regex-automata中，使正则表达式crate本身只是regex-automata的薄包装。通过这种方式，如果有人需要访问较低级别的API，从正则表达式crate迁移到regex-automata的摩擦应该减少。

通过这种方式，我们可以使用与正则表达式crate用于其lazy DFA的完全相同的代码来构建完全编译的DFAs。并且正则表达式crate用于将解析的正则表达式表示转换为NFA的完全相同的代码。嘿，这甚至使得在某些情况下在正则表达式crate中使用完全编译的DFAs成为可能。（这通常在通用正则表达式引擎中是一个大忌，因为完全编译的DFAs不仅相当膨胀，而且它们以最坏情况下指数时间构建。这对于你可能用于编译不受信任的模式的正则表达式引擎，或者甚至在你需要编译时间的正则表达式是“合理”的情况下，是非常不合适的。构建DFA可能是不合理的，特别是当涉及到Unicode时。）

未完待续