好！这么玩是吧？Rust正则库玩坏了谁背锅？--野

目录

• 引擎：Pike VM
• 引擎：有界回溯器
• 引擎：单次DFA
• 引擎：DFA
• 引擎：混合NFA/DFA
• 元正则表达式引擎
• 与RE2的区别
• 测试策略
• 基准测试
• 成本
• 总结

引擎：Pike VM

如上所述，最终归结为PikeVM。也就是说，PikeVM支持regex-syntax解析的全套正则表达式功能，并且支持任何长度的haystack。其他正则表达式引擎有各种限制。例如：

BoundedBacktracker只在len(haystack) * len(regex)低于配置限制的情况下工作。实际上，这通常意味着只能与短haystack一起使用。单次DFA只适用于满足“单次”标准的一小部分NFAs。lazy DFA和完全编译的DFA不能匹配Unicode单词边界。两者都有启发式地将Unicode单词边界视为ASCII单词边界的处理，但一旦发现非ASCII字节，两者都可以退出并返回错误，而不是完成搜索。

除了Cache值之外，PikeVM可以直接从NFA构建，无需额外工作。也就是说，它的搜索工作是通过“模拟”NFA本身来完成的。（令人困惑的是，这有时被称为“DFA算法。”）实际实现结构类似于虚拟机，每个NFA状态作为一个指令。PikeVM通过从一个NFA状态移动到下一个状态，并实时计算epsilon闭包来工作。由于可能同时处于多个NFA状态，PikeVM跟踪每个活动状态。然后转换函数应用于这些状态中的每一个。PikeVM还跟踪捕获组位置。

PikeVM的主要问题在于性能，其性能不佳主要源于必须跟踪如此多的状态。捕获组位置需要报告开始和结束匹配偏移量，而当前活动状态必须被跟踪以保证最坏情况下O(m * n)时间。也就是说，与回溯方法相比，PikeVM通过计算所有可能的活动状态来访问haystack中的每个字节最多恒定次数。这增加了相当多的开销，并且可能因具有许多epsilon转换的正则表达式而加剧。（这是我们之前在博客中花费如此多时间讨论NFA优化以消除epsilon转换的原因之一。）

现在我们已经讨论了PikeVM的工作原理，让我们看一些例子。这里有一个稍微注释的Rust程序，展示了如何使用它进行搜索：

解释
use regex_automata::{nfa::thompson::pikevm::PikeVM, Match};fnmain() {// 这直接从一个模式字符串创建一个PikeVM。但你也可以使用`PikeVM::builder()`。letre = PikeVM::new(r"\b\w+\b").unwrap();// regex-automata中的大多数正则表达式引擎都需要一些可以写入的可变scratch空间。letmutcache = re.create_cache();letmutit = re.find_iter(&mut cache,"Σέρλοκ Χολμς");assert_eq!(Some(Match::must(0,0..12)), it.next());assert_eq!(Some(Match::must(0,13..23)), it.next());assert_eq!(None, it.next()); }
















rust
复制代码喽

以及等效的regex-cli命令：

regex-cli find match pikevm --no-table -p '\b\w+\b' -y 'Σέρλοκ Χολμς'



shell
复制代码喽

注意Unicode单词边界在非ASCII haystack上的使用。只有PikeVM、BoundedBacktracker和单次DFA支持这一点。lazy DFA和完全编译的DFA在这种情况下会返回错误。

另一个需要注意的重要事项是，搜索API不会返回错误。实际上，PikeVM在任何情况下都不会返回错误（也不会panic）。这实际上是regex-automata中的正则表达式引擎中独一无二的属性。其他每个正则表达式引擎在搜索期间都可能返回错误。

我们还可以同时使用具有捕获组的多模式支持。（这是正则表达式crate无法做到的，许多人请求其RegexSet API支持这一点。仍然不存在，但您至少可以降到regex-automata并做到这一点。这个示例也适用于元正则表达式引擎。）

解释
use regex_automata::nfa::thompson::pikevm::PikeVM;fnmain() {letre = PikeVM::new_many(&[r"(?<email>[.\w]+@(?<domain>[.\w]+))",r"(?<phone>(?<areacode>[0-9]{3})-[0-9]{3}-[0-9]{4})", ]) .unwrap();letmutcache = re.create_cache();lethay ="foo@example.com, 111-867-5309";letmutit = re.captures_iter(&mut cache, hay);letcaps = it.next().unwrap();assert_eq!(0, caps.pattern().unwrap().as_usize());assert_eq!("example.com", &hay[caps.get_group_by_name("domain").unwrap()])letcaps = it.next().unwrap();assert_eq!(1, caps.pattern().unwrap().as_usize());assert_eq!("111", &hay[caps.get_group_by_name("areacode").unwrap()]);assert!(it.next().is_none()); }





rust
复制代码喽

以及等效的regex-cli命令：

解释
regex-cli find capture pikevm --no-table \ -p '(?<email>[.\w]+@(?<domain>[.\w]+))' \ -p '(?<phone>(?<areacode>[0-9]{3})-[0-9]{3}-[0-9]{4})' \ -y 'foo@example.com, 111-867-5309'






shell
复制代码喽

注意捕获组对于每个模式都是不同的。调用者需要根据匹配的模式使用正确的捕获组名称。

引擎：有界回溯器

有界回溯器使用回溯算法使用Thompson NFA直接执行搜索。这有时也被称为“NFA算法”
。regex-automata中回溯实现与大多数其他实现之间的关键区别在于它使用额外的状态来避免重新追踪回溯期间已经采取的步骤。这使我们能够保证最坏情况下O(m * n)时间，但代价是O(m * n)空间。

（理论上，经典回溯也是理论上有界的，但“有界”在“有界回溯器”中的名称指的是实现中用于保证最坏情况下O(m * n)时间的显式界限。）

有界回溯器的好处纯粹是它通常比PikeVM快。在粗略的实验中，它通常大约快两倍。

这里有一个快速的例子，像之前的PikeVM示例，但使用有界回溯器：

解释
use regex_automata::{nfa::thompson::backtrack::BoundedBacktracker, Match};fnmain() {letre = BoundedBacktracker::new(r"\b\w+\b").unwrap();// 有界回溯器和PikeVM一样需要一个缓存。缓存跟踪已经完成的工作，// 并且包含回溯的调用栈的scratch空间，存储在堆上。letmutcache = re.create_cache();// 与PikeVM不同，有界回溯器可以失败搜索。// 当`len(regex) * len(haystack)`超过配置的访问容量时会发生这种情况。letmutit = re.try_find_iter(&mut cache,"Σέρλοκ Χολμς");assert_eq!(Some(Ok(Match::must(0,0..12))), it.next());assert_eq!(Some(Ok(Match::must(0,13..23))), it.next());assert_eq!(None, it.next()); }


















rust
复制代码喽

以及等效的regex-cli命令：

regex-cli find match backtrack --no-table -p '\b\w+\b' -y 'Σέρλοκ Χολμς'



shell
复制代码喽

这个例子应该看起来和PikeVM示例几乎相同。一个重要的不同是没有调用re.find_iter(..)，而是调用了re.try_find_iter(..)。也就是说，如上所述，有界回溯器可能会在搜索需要的内存超过配置时返回错误。相关配置旋钮是Config::visited_capacity。

我们还可以查询有界回溯器可以在不失败的情况下搜索多大的haystack：

解释
use regex_automata::nfa::thompson::backtrack::BoundedBacktracker;fnmain() {letre = BoundedBacktracker::new(r"\b\w+\b").unwrap();println!("{:?}", re.max_haystack_len()); }








rust
复制代码喽

在撰写本文时，我的机器上的输出是6635。这可能看起来相当短，因为正则表达式可能比您想象的要大。也就是说，由于\w默认支持Unicode，\w匹配超过100,000个不同的代码点。我们可以通过设置Config::visited_capacity更大的值来增加我们可以搜索的haystack的最大长度，我们也可以通过禁用Unicode模式来减小我们的正则表达式大小：

解释
use regex_automata::nfa::thompson::backtrack::BoundedBacktracker;fnmain() {letre = BoundedBacktracker::new(r"(?-u)\b\w+\b").unwrap();println!("{:?}", re.max_haystack_len()); }








rust
复制代码喽

我的机器上的输出现在是233015。这几乎是两个数量级的差异！

总的来说，如果可能的话，应该优先使用有界回溯器而不是PikeVM。它们都有相同的时间复杂度保证，但有界回溯器在实践中往往更快。

引擎：单次DFA

在讨论单次DFA之前，更详细地动机其存在是有意义的。也就是说，PikeVM和有界回溯器的一个重要方面是它们支持报告模式中匹配捕获组的偏移量。例如，使用PikeVM和regex-cli：

regex-cli find capture pikevm --no-table -p '(?<year>[0-9]{4})-(?<month>[0-9]{2})-(?<day>[0-9]{2})' -y '2023-07-02'



shell
复制代码喽

捕获组非常有用，因为它们允许将正则表达式匹配分解为独立有用的组成部分。像上面的例子，我们不仅匹配了一个日期，我们还匹配了该日期的各个组成部分，并通过API轻松地使用这些组成部分。例如，使用正则表达式crate本身：

解释
use regex::Regex;fnmain() {letpat =r"(?<year>[0-9]{4})-(?<month>[0-9]{2})-(?<day>[0-9]{2})";letre = Regex::new(pat).unwrap();ifletSome(caps) = re.captures("2023-07-02") {println!("year: {:?}", &caps["year"]);println!("month: {:?}", &caps["month"]);println!("day: {:?}", &caps["day"]); } }













rust
复制代码喽

没有捕获组，正则表达式变得不那么方便。

捕获组的问题在于，它们并不完全适合正则语言和有限自动机的理论模型。（它们需要一些更具表现力的东西，称为标记有限自动机。）因此，捕获组被添加到经典的NFA模拟中，结果就是PikeVM。捕获组也是经典“NFA算法”或回溯的一部分，因为每个组的匹配偏移量可以在回溯搜索遍历haystack时记录下来。

但通常捕获组就在这里停止被支持。DFA根本不支持它们，并且没有明显的方法可以使它们一般性地支持捕获组，而不会演变成标记有限自动机。

然而，有一个案例我们可以将捕获组添加到像DFA那样执行的东西中：单次NFA。可以认为单次NFA是一个可以转换为DFA的NFA，其中每个DFA状态最多映射到一个NFA状态。也就是说，当使用NFA模拟进行搜索时，然后在haystack的每个可能的字符中，最多有一个NFA状态可以转换。

这种特殊情况背后的直觉是只有一个匹配的捕获组副本需要保留。（在PikeVM中，由于无法知道哪些捕获组最终会成为最终匹配的一部分，因此保留了多达len(regex)个捕获组副本。）如果能够检测到这种情况，那么可以从NFA构建一个新的DFA，这个DFA可以执行搜索，使得处理haystack中的每个字符只使用恒定数量的CPU指令。

最终结果是单次DFA，它通常比PikeVM或有界回溯器运行得快得多。也就是说，它代表了在正则表达式crate中报告匹配捕获组偏移量的最快方式。

单次DFA的问题在于，作为一个DFA，它使用更多的内存。（内存问题通过给单次DFA构造一个可配置的固定预算内存来缓解，如果超出预算，单次DFA构造失败。）此外，许多正则表达式不是单次的。例如，正则表达式crate中的所有未锚定搜索都是通过在正则表达式的开头添加隐式的(?s-u:.)*?前缀来完成的。该前缀本身在跟随任何非空正则表达式时不是单次的。因此，单次DFA只支持锚定搜索。

“仅锚定”搜索限制可能使单次DFA看起来用途有限，但正如我们将更详细地看到的，元正则表达式引擎即使原始正则表达式不是锚定的，也频繁使用锚定搜索。这可能发生在调用者请求匹配捕获组的偏移量时。元正则表达式引擎首先使用DFA引擎寻找整体匹配，然后一旦找到匹配，就在haystack的匹配部分上使用锚定搜索来报告每个匹配捕获组的偏移量。通过这种方式，单次DFA的实用性相当高。

直接使用单次DFA是可能的，看起来与以前的示例相似，但由于单次DFA的更有限的API，有一些小的偏差：

解释
use regex_automata::{dfa::onepass::DFA, Match};fnmain() {letre = DFA::new(r"\b\w+\b").unwrap();letmutcache = re.create_cache();// 单次DFA不直接暴露任何迭代器API，因为它支持锚定匹配。// 因此，返回的任何迭代器只会支持相邻匹配。// 这是一个有效的用例，但不会匹配regex-automata中每个迭代器的语义。letSome(m) = re.find(&mut cache,"Σέρλοκ Χολμς")else {return; }assert_eq!(Match::must(0,0..12), m); }














rust
复制代码喽

以及等效的regex-cli命令：

regex-cli find match onepass --no-table --anchored -p '\b\w+\b' -y 'Σέρλοκ Χολμς'



shell
复制代码喽

注意到我们传递了--anchored标志给regex-cli。没有它，单次DFA
搜索将返回错误。

我们也可以执行多次搜索。即使正则表达式本身不是锚定的，我们也不必限制自己在偏移量0处开始搜索：

解释
use regex_automata::{dfa::onepass::DFA, Input, Match};fnmain() {lethay ="Σέρλοκ Χολμς";letre = DFA::new(r"\b\w+\b").unwrap();letmutcache = re.create_cache();letSome(m) = re.find(&mut cache, hay)else {return; }assert_eq!(Match::must(0,0..12), m);letinput = Input::new(hay).range(13..);letSome(m) = re.find(&mut cache, input)else {return; }assert_eq!(Match::must(0,13..23), m); }
















rust
复制代码喽

Input抽象也可以与任何其他正则表达式引擎以相同的方式使用。

思考一个特定正则表达式是否是单次的可能是相当棘手的。例如，一个正则表达式在禁用Unicode时可能是单次的，在启用Unicode时不是单次的。例如：

regex-cli find match onepass --no-table --anchored -p '\w+\s+\w+' -y 'Σέρλοκ Χολμς'



shell
复制代码喽

但如果我们禁用Unicode模式，那么正则表达式就变成单次的：

regex-cli find match onepass --no-table --anchored -p '(?-u)\w+\s+\w+' -y 'Sherlock Holmes'



shell
复制代码喽

这是因为，当启用Unicode模式时，\w和\s部分重叠。它们当然在逻辑上不重叠，因为取\w和\s的代码点集并将它们相交会产生空集：

regex-cli debug hir --no-table '[\w&&\s]'



shell
复制代码喽

这种重叠实际上是在字节级别上的，而单次DFA中的转换就是定义在字节级别上的。这种重叠意味着当启用Unicode模式时，\w+\s+\w+的DFA不满足每个状态在DFA中最多映射到一个NFA状态的属性。也就是说，存在代码点在\w和\s中都以相同的前导UTF-8代码单元开始。

但当禁用Unicode模式时，不仅代码点集没有任何重叠，而且它们在字节级别上也没有重叠。为什么呢？因为当Unicode被禁用时，\w和\s中的代码点被限制在ASCII代码点，每个ASCII代码点总是被编码为一个对应于ASCII代码点号的UTF-8代码单元。

人们应该优先选择单次DFA而不是PikeVM和有界回溯器，因为它更快，尽管它可能需要更长的构建时间并且可能使用更多的内存。然而，因为它只能从非常有限的正则表达式集合中构建，所以必须准备好处理构建失败并回退到不同的引擎。

引擎：DFA

DFA正则表达式引擎由两个密集DFA组成。一个DFA负责向前扫描以找到匹配的结束，另一个DFA用于从匹配的结束处向后锚定扫描以找到匹配的开始。（这第二个DFA是通过反转Hir中的连接，从该反转Hir构建NFA，然后将该NFA确定化为DFA来构建的。）我们称这些DFA为“密集”，以区分稀疏DFA。密集DFA使用一种表示，优化搜索速度以牺牲更多的内存使用，而稀疏DFA使用一种表示，优化更少的内存使用以牺牲搜索速度。

完全编译的DFA通常不会出现在通用正则表达式引擎中，因为构建它们有最坏情况下O(2^m)的时间和空间（其中m与len(regex)成正比）。例如，[01]*1[01]{N}编译成一个大约有N个状态的NFA，随着N的增长，NFA线性增长。但相应的DFA大约有2^N个状态，随着DFA的增长，状态数量呈指数增长。

但DFA的问题不仅限于其理论上的最坏情况行为。DFA，特别是密集DFA，往往使用大量内存，因为每个状态支持对任何字节进行恒定时间的下一步转换。这根本上需要更多的内存来提供恒定时间的随机访问。当您将这一点与大型Unicode字符类结合起来时，结果可能是灾难性的。例如，让我们比较一下正则表达式\w的大小。首先是NFA（记住，可以直接作为正则表达式引擎使用PikeVM和有界回溯器的情况）：

regex-cli debug thompson '\w' -q



shell
复制代码喽

所以在这里，NFA使用了17KB。这并不小，但看看当我们将NFA确定化为DFA时会发生什么：

regex-cli debug dense dfa '\w' --start-kind unanchored -q



shell
复制代码喽

内存膨胀到约160KB！（我将DFA限制为仅未锚定的DFA。如果使用--start-kind both，即默认设置，那么内存使用量将翻倍。）而且花更多的时间最小化DFA并没有帮助：

regex-cli debug dense dfa '\w' --start-kind unanchored --minimize -q



shell
复制代码喽

有时最小化有帮助，但在这种情况下，由于我们已经使用Daciuk算法在NFA中为\w构建了最小的UTF-8自动机，因此将该NFA确定化为DFA本身已经得到了最小的DFA。真正的问题是我们密集表示和我们的字母表定义在字节上的事实。

我们可以通过切换到稀疏表示来使它变得更好一些：

regex-cli debug sparse dfa '\w' --start-kind unanchored -q



shell
复制代码喽

但我们仍然在100KB以上。Unicode字符类和完全编译的DFA只是不混合得很好。实际上，通常不需要完全编译，因为它在搜索许多不同脚本的haystacks时相当罕见。更关键的是，大多数搜索可能对只有ASCII定义的\w很满意，这要小得多：

regex-cli debug thompson '(?-u)\w' -q



shell
复制代码喽

regex-cli debug dense dfa '(?-u)\w' --start-kind unanchored -q



shell
复制代码喽

在这种情况下，密集DFA实际上比相应的NFA小。

那么，为什么要像regex crate这样的通用正则表达式引擎要有这样一个具有如此巨大缺点的DFA引擎呢？难道巨大的内存使用不会使它成为一个非启动项吗？有两个角度来解释为什么存在完整的DFAs。

首先，DFA引擎实际上默认是禁用的。您必须通过启用perfdfa-full功能来选择加入它。我这样做是因为完全编译的DFAs在regex crate中没有太多的重量，因为lazy DFA（在下一节讨论）在绝大多数情况下是更好的选择。然而，完全编译的DFAs确实提供了一些优化机会，这是lazy DFA难以利用的。例如，在正则表达式(?m)^.*$中，完全编译的DFA会注意到。不匹配\n。它通过查找大多数转换是自转换的状态（转换回同一状态的转换）来了解这一点。因此，离开该状态的方式是有限的。DFA找到这些状态，并通过运行memchr来加速它们，找到haystack中对应非自转换的字节。您可以使用regex-cli进行一些临时基准测试。首先，我们将从DFA状态加速启用开始（默认情况下启用）：

regex-cli find match dense -bB -q --repeat 1000000 -p '(?m-u)^.*$' -y 'this is a long line about the quick brown fox that jumped over the l'



shell
复制代码喽

现在，DFA状态加速被禁用：

regex-cli find match dense -bB -q --repeat 1000000 --no-accelerate -p '(?m-u)^.*$' -y 'this is a long line about the quick brown fox that jumped over the l'



shell
复制代码喽

启用加速的搜索时间要快得多。还要注意，我们禁用了Unicode。当启用Unicode时，。匹配任何Unicode标量值的UTF-8编码。这反过来使DFA更加复杂，并在这种情况下抑制了加速优化：

regex-cli find match dense -q --repeat 1000000 -p '(?m)^.*$' -y 'this is a long line about the quick brown fox that jumped over the l'



shell
复制代码喽

虽然这种DFA状态加速非常有用，但它在可以应用的正则表达式上有所限制，部分原因是Unicode。它也因为元正则表达式引擎只在正则表达式非常小的情况下才选择使用DFA引擎而受到限制。否则，我们就会面临巨大的内存使用和构建正则表达式的指数级时间。regex crate在编译正则表达式方面并不是最快的，但采取指数级时间是一个大禁忌。

由于其有限的实用性，并且由于DFA引擎增加了很多代码，从而显著增加了编译时间和二进制大小，因此完整的DFAs默认是禁用的。

第二个角度是，DFA的搜索运行时间非常基本。它们是regex-automata中唯一不需要任何可变的Cache空间就可以执行搜索的正则表达式引擎。实际上，让我们来看一个例子：

解释
use regex_automata::{dfa::dense, regex::Regex}, Match;fnmain() {letre = Regex::builder() .dense(dense::Config::new().unicode_word_boundary(true)) .build(r"\b\w+\b") .unwrap();// 注意，`find_iter`会在底层搜索返回错误时panic！您可以使用容错API，如Regex::try_search。letmutit = re.find_iter("Sherlock Holmes");assert_eq!(Some(Match::must(0,0..8)), it.next());assert_eq!(Some(Match::must(0,9..15)), it.next());assert_eq!(None, it.next()); }
















rust
复制代码喽

以及等效的regex-cli命令：

regex-cli find match dense --no-table --unicode-word-boundary -p '\b\w+\b' -y 'Sherlock Holmes'



shell
复制代码喽

注意到不需要Cache。实际上，由于DFA的搜索运行时间非常简单，并且DFA内部设计考虑到了这种用例，因此DFA可以序列化为原始字节。同一个DFA可以被反序列化并用于在独立的环境中执行搜索。也就是说，您不需要Rust的std或alloc库。只需要core。

（DFA序列化用例是regex-automata 0.1版本的动机。它目前在bstr crate中用于实现一些Unicode分段算法。）

完全编译的DFAs在您的正则表达式不使用Unicode功能，或者如果您需要访问更低级别的API时最有用。例如，这显示了如何手动计算DFA上的转换：

解释
use regex_automata::{dfa::dense::DFA, Automaton};fnmain() {letre = DFA::new(r"\W").unwrap();// DFA可以有多个起始状态，但只有当有环视断言时。当没有环视断言时，像这个案例，// 我们可以在不提供haystack的情况下请求起始状态。letmutsid = re.universal_start_state(Anchored::No).unwrap();// 💩的UTF-8编码是\xF0\x9F\x92\xA9。 sid = re.next_state(sid,0xF0).unwrap(); sid = re.next_state(sid,0x9F).unwrap(); sid = re.next_state(sid,0x92).unwrap(); sid = re.next_state(sid,0xA9).unwrap(); sid = re.next_eoi_state(sid).unwrap();assert!(re.is_match_state(sid)); }



















rust
复制代码喽

在这个例子中，我们手动遍历了DFA，并一次向DFA提供一个字节。这个例子有点人为，但它展示了提供低级别控制的一些API。还有更多的例子记录在Automaton trait上，它定义了所有低级别的DFA例程，密集和稀疏DFA都实现了。

引擎：混合NFA/DFA

混合NFA/DFA或“lazy DFA”正则表达式引擎与DFA引擎完全相同，除了其转换表是在搜索时构建的。也就是说，虽然完整的DFA是“提前编译”的，但lazy DFA是“即时编译”的。

（称它为JIT可能会引起误解。在这个领域，JIT通常指的是在运行时将正则表达式编译成机器代码，如PCRE2中的JIT。这里不是这种情况。）

lazy DFA通常具有与完全编译的DFA相同的API，除了像其他正则表达式引擎一样，您需要传递一个可变的Cache参数。Cache是转换表存储的地方（以及其他东西）：

解释
use regex_automata::{hybrid::dfa, regex::Regex}, Match;fnmain() {letre = Regex::builder()// 像完全编译的DFA一样，我们需要为lazy DFA启用启发式Unicode单词边界支持。// 如果在包含Unicode单词边界的正则表达式中看到非ASCII代码点，它会返回错误。 .dfa(dfa::Config::new().unicode_word_boundary(true)) .build(r"\b\w+\b") .unwrap();letmutcache = re.create_cache();// 注意，find_iter将在底层搜索返回错误时panic！您可以使用容错API，如Regex::try_search。letmutit = re.find_iter(&mut cache,"Sherlock Holmes");assert_eq!(Some(Match::must(0,0..8)), it.next());assert_eq!(Some(Match::must(0,9..15)), it.next());assert_eq!(None, it.next()); }



















rust
复制代码喽

以及等效的regex-cli命令：

regex-cli find match hybrid --no-table --unicode-word-boundary -p '\b\w+\b' -y 'Sherlock Holmes'



shell
复制代码喽

这个例子几乎与完整的DFA相同，但有一个Cache参数。相似之处扩展到低级API：

解释
use regex_automata::{hybrid::dfa::DFA, Input};fnmain() {letre = DFA::new(r"\W").unwrap();letmutcache = re.create_cache();// DFA可以有多个起始状态，但只有当有环视断言时。当没有环视断言时，像这个案例，// 我们可以在不提供haystack的情况下请求起始状态。letmutsid = re.start_state_forward(&mut cache, &Input::new("")).unwrap();// 💩的UTF-8编码是\xF0\x9F\x92\xA9。 sid = re.next_state(&mut cache, sid,0xF0).unwrap(); sid = re.next_state(&mut cache, sid,0x9F).unwrap(); sid = re.next_state(&mut cache, sid,0x92).unwrap(); sid = re.next_state(&mut cache, sid,0xA9).unwrap(); sid = re.next_eoi_state(&mut cache, sid).unwrap();assert!(sid.is_match()); }




















rust
复制代码喽

除了显式传递Cache之外，这些API几乎相同。主要区别是每个操作可能会失败。也就是说，根据方法，它们可以返回MatchError或CacheError。当无法计算起始状态时会发生MatchError（这意味着搜索必须终止并返回错误。例如，当启用启发式Unicode单词边界支持并且看到非ASCII字节时，lazy DFA会进入一个特殊的状态并退出）。当提供的Cache容量耗尽时会发生CacheError。

此时，值得进一步讨论Cache，因为它既是lazy DFA的最大优势也是其最大弱点。正如提到的，lazy DFA通过在搜索期间构建其转换表来工作。更具体地说，以下发生：

• 配置了最大缓存容量，在构建时。容量不是预先完全分配的。它只是一个数字，建立了可以使用的堆内存的上限。
• 当调用者请求计算当前状态和haystack字符的转换时，lazy DFA会查询其Cache。如果转换已经在Cache中计算并存储，那么它将立即原样返回。否则，转换（仅该转换）通过执行NFA幂集构造来计算。这个过程最坏情况下需要O(m)时间。
• 如果缓存已满，它将被清除，因此之前计算的转换将需要重新计算。
• 可选配置可以设置，以使lazy DFA在Cache使用效率低下时返回错误。效率以搜索的每个DFA状态计算的字节数来衡量。如果与Cache中的DFA状态数量相比，搜索的字节数很少，那么即使是PikeVM也可能更快速地执行搜索。（这里还使用了其他启发式，如Cache被清除的总次数。）

通过这种方式，对于搜索的每个字节的haystack，最多创建一个DFA状态和转换。因此，lazy DFA的最坏情况下搜索时间为O(m * n)，其最坏情况下的空间使用量为构建时设置的固定容量。由于构建lazy DFA本身不需要构建任何DFA状态（除了一些基本的哨兵状态），因此lazy DFA避免了完整DFAs的理论最坏情况下时间和空间复杂度。也就是说，我们避免了指数级的构建时间。在常见情况下，大多数状态/转换都被缓存，因此lazy DFA在平均情况下以O(n)时间运行。实际上，对于大多数正则表达式，lazy DFA和完全编译的DFA具有相同的搜索性能。

lazy DFA在缓存被填满并反复清除时表现不佳。这可能是由于正则表达式很大，或者是由于haystack迫使DFA的很大一部分被构建。（一个正则表达式可以通过计数重复或甚至通过添加许多模式而变得很大。一个lazy DFA为多模式正则表达式构建。）在这些情况下，启发式通常会检测到它，并强制lazy DFA返回错误。此时，在元正则表达式引擎的上下文中，搜索将使用不同的引擎重试（通常是PikeVM）。

元正则表达式引擎

元正则表达式引擎将所有上述正则表达式引擎组合在一起，并公开一个单一的无懈可击的API，在任何给定情况下尝试做最好的事情。它公开的API也使调用者免除了需要显式创建和传递Cache值给每个搜索调用的需要。

相反，元正则表达式引擎为您处理这个问题，通过内部维护一个线程安全的Cache池。（元正则表达式引擎确实公开了允许显式传递Cache的低级API。这些API在想要避免内部使用的线程安全池的同步成本时很有用。）

最终结果是，元正则表达式引擎非常接近regex crate的顶层API。

实际上，regex::Regex、regex::RegexSet、regex::bytes::Regex和regex::bytes::RegexSet都是元正则表达式引擎的非常薄的包装。这是有意为之的，因为它使得从服务于99%用例的高层便捷API下降到暴露更多旋钮的低层API变得更加容易。

在内部，元正则表达式引擎实现了大致以下逻辑：

如果根本不需要正则表达式引擎，并且可以直接使用单字字符串或多字字符串搜索算法执行搜索，则完全避免构建正则表达式（包括NFA）。如果可能，从正则表达式的前缀提取一个小的字面量序列，可以用作预过滤器。如果可能，选择一个“反向”优化：

如果正则表达式通过$锚定在末尾，则可以通过从haystack末尾进行反向扫描来进行搜索。这称为“反向锚定”优化。如果没有找到合适的前缀或后缀字面量序列，但是可以从正则表达式的内部提取一个清晰划分正则表达式的字面量序列，则可以扫描该内部字面量序列的出现。我们在提取内部字面量序列的点将正则表达式一分为二。第一部分编译成反向正则表达式，第二部分编译成正向正则表达式。当找到候选时，我们可以通过向后扫描第一部分来寻找匹配的开始，然后通过向前扫描第二部分来寻找匹配的结束。

否则，退回到“核心”搜索策略。核心策略利用所有可用的正则表达式引擎：PikeVM、有界回溯器、单次DFA、lazy DFA和完整DFA。只有PikeVM是必需的。这些引擎的组合方式大致如下：

只要可能，就使用lazy DFA（或如果可用，则使用完整DFA）来找到匹配的总体边界。如果DFA失败，那么我们退回到PikeVM、有界回溯器或单次DFA。DFA可能因为正则表达式包含Unicode单词边界并且haystack包含非ASCII代码点而失败，或者因为使用了lazy DFA并且其Cache使用效率根据某些启发式不高。当请求捕获组时，那么在找到完整匹配后，使用PikeVM、有界回溯器或单次DFA报告每个匹配捕获组的偏移量。优先顺序是：单次DFA、有界回溯器，然后是PikeVM。

如果总结一下整体策略，它可以被概括为这两点：

尽可能搜索字面量。尽量避免PikeVM。

就是这样。一般来说，我们花在子字符串搜索算法上的时间越多，越好。我们花在PikeVM上的时间越少，越好。

许多正则表达式引擎都进行了某种字面量优化，实际上，大多数流行的生产级正则表达式引擎都在这方面投入了大量的努力。Hyperscan在这方面是黄金标准，但据作者所知，大多数其他通用正则表达式引擎并没有达到上述正则表达式crate所描述的程度。（有人会争论Hyperscan是否是一个“通用”正则表达式引擎。作者个人反对将其视为通用正则表达式引擎的一个论点是其匹配语义。例如，\w+在Hyperscan中匹配abc三次，因为Hyperscan报告它们看到的匹配。鉴于其目标领域，这无疑是一个正确的选择。）反向后缀和反向内部优化特别棘手。它们看起来很容易，但存在一个微妙的性能问题：它们使您面临最坏情况下二次方行为的风险（在haystack的大小上）。

考虑正则表达式[A-Z]。bcdefghijklmnopq在重复的bcdefghijklmnopq上的haystack。没有可以提取的“好”前缀字面量序列，所以根据上述逻辑，元正则表达式引擎将尝试使用bcdefghijklmnopq作为后缀的“反向后缀”优化。这个特定的基准测试被设计为具有最坏情况下的误报率：候选者频繁报告，且它们都不导致匹配。但这只是坏启发式。它本身并不导致违反我们的时间复杂度保证（即O(m * n)）。这里的问题在于，每次后缀匹配时，反向扫描包括.，这反过来扫描整个haystack回到开始。所以每个由后缀匹配报告的候选者导致对haystack的完整重新扫描。这将我们的搜索例程更改为最坏情况下O(m * n^2)时间复杂度。这很糟糕。

虽然可以对正则表达式进行句法分析以确定是否可能发生二次方行为，但它并不完美预测。例如，可以清楚地看到后缀bcdefghijklmnopq与它之前的表达式重叠。*。这意味着某种二次方行为可能是可能的。但这并不意味着它是不可避免的。

相反，元正则表达式引擎通过定义自己的定制正则表达式搜索例程来缓解这个问题，这些例程基于DFA引擎。也就是说，它定义了自己的搜索例程，如果到达haystack的某个特定偏移量，将停止其反向扫描。该偏移量对应于最后一个后缀匹配的结束。所以如果搜索否则会超过该偏移量，那么我们就会面临二次方行为。元正则表达式引擎检测到这个错误情况并退回到上述的“核心”策略，从而放弃优化，否则会牺牲我们的时间复杂度保证。

大致相同的逻辑适用于“反向内部”优化。

总之，如果您不需要对各个正则表达式引擎进行低级访问，但您想要控制regex engine暴露的许多旋钮，或者想要进行多模式匹配，那么元正则表达式引擎是一个不错的选择。也就是说，前面描述的所有正则表达式引擎都有自己的小缺点，使它们在每种情况下都不太理想。

与RE2的区别

如果您已经阅读了Russ Cox关于正则表达式的一系列文章，那么前一节的某些部分可能听起来很熟悉。也就是说，RE2有一个PikeVM（在RE2中称为仅“NFA”），一个有界回溯器（在RE2中称为“bitstate backtracker”），一个单次DFA（在RE2中称为“one-pass NFA”）和一个lazy DFA。它还有一个元正则表达式引擎（尽管没有使用该术语），它以类似于上述的方式组合其内部正则表达式引擎。上述描述的唯一引擎是RE2没有的完整编译DFA。

那么，RE2和正则表达式crate之间有什么区别呢？

它们之间的相似之处远大于差异，但以下是一些高层区别：

RE2支持leftmost-longest语义作为leftmost-first的选项。leftmost-longest语义是POSIX正则表达式引擎使用的。RE2对Unicode的支持较少。对此的完整说明很棘手，因为RE2允许链接ICU以添加对更多Unicode属性的支持。然而，RE2没有选项使\w、\s、\d和\b使用Unicode定义。RE2也不支持除了并集之外的字符类集合操作。例如，在RE2中更难编写像[\pL&&\p{Greek}]这样的内容，它对应于被认为是字母的代码点子集，也在希腊脚本中。（字符类集合操作除了并集之外，并非严格Unicode特定功能，但在大型Unicode字符类的上下文中最有用。）RE2有一个可能更内存高效的PikeVM版本。RE2对字面量优化有一些有限的支持，但总体上不如regex crate做得多。RE2有一个Filtered RE2，允许调用者进行有限形式的自己的字面量优化。RE2在lazy DFA引擎中对多个线程使用相同的转换缓存，这需要同步。相反，regex crate需要每个线程一个单独的缓存，这需要更多的内存。regex crate现在公开了regex-syntax和regex-automata作为单独版本控制的库，提供对其内部的访问。RE2不支持这一点。regex-automata库对所有引擎中的多模式正则表达式有一流的支持。RE2确实有一个“正则表达式集”，但它只报告哪些模式在haystack中匹配。regex-automata则可以报告每个匹配模式的匹配和捕获组偏移量。

将来，作者希望向regex-automata添加更多的引擎。具体来说，他想探索Glushkov NFAs和位并行正则表达式引擎。他还想探索Shift DFAs。

测试策略

正如博客开头所述，测试已经成为正则表达式crate的问题。用于测试每个内部引擎的宏hack变得越来越紧张，它们通常难以使用和理解。

作者对正则表达式crate测试方式的改革想法与每个内部引擎都有自己的一流API，可以独立于“主”正则表达式引擎进行测试的想法相联系。他还希望使测试可以从任何上下文中使用，而不是将它们埋藏在宏或Rust源代码中。为此，他采取了以下策略：

所有正则表达式测试都在TOML文件中指定。他发布了一个名为regex-test的crate，它知道如何将这些TOML文件读入结构化表示。他为每个我想要测试的正则表达式引擎的每个配置定义了一个单独的Rust单元测试。在这个单独的单元测试中，执行所有适用于被测试引擎的TOML文件中的测试。

为了使这个策略易于使用，需要一些额外的基础设施，因为Rust的单元测试框架目前不可扩展。这意味着他不得不定义自己的环境变量来过滤要运行哪些测试。（例如，如果你正在处理一个导致许多测试失败的单一错误，通常很有用只运行这些测试中的一个。）

还有许多其他类型的测试。例如，在regex-automata中就有超过450个文档测试。

最后，在regex 1.9发布之前，他增加了许多额外的模糊测试目标。他得到了Addison Crump的很多帮助，如果没有他，作者就不会发现一些bug。

基准测试

到这一点，这篇博客已经是作者写过的最长的博客了，他甚至还没有开始讨论基准测试。虽然他原本想在这篇博客中花更多时间讨论这个话题——特别是鉴于所有关于优化的讨论——但实际上并不实用。

相反，他发布了一个名为rebar的正则表达式晴雨表。它不仅仅限于基准测试regex crate。它还基准测试了许多其他正则表达式引擎。作者认为这是迄今为止最全面的正则表达式基准测试。

在242个基准测试中，regex 1.9的平均搜索时间比regex 1.7.3快1.5倍。（我与1.7而不是1.8进行比较，因为1.8反映了一个过渡版本，其中包含了本文描述的一些工作。1.9版本只是完成了过渡。）

rebar rank record/all/2023-07-02/*.csv --intersection -M compile -e '^(rust/regex|rust/regexold)$'



shell
复制代码喽

但构建正则表达式所需的时间有所回退：

rebar rank record/all/2023-07-02/*.csv --intersection -m compile -e '^(rust/regex|rust/regexold)$'



shell
复制代码喽

上述报告的几何平均数是一个非常粗略的聚合统计数据。作者不确定它是否真的捕捉到了这里的改进程度。如果你想看个别基准测试的差异，可以将上述命令中的rebar rank替换为rebar cmp。（并从rebar仓库的根目录运行它。）

rebar cmp record/all/2023-07-02/*.csv --threshold-min 2 --intersection -M compile -e '^(rust/regex|rust/regexold)$'



shell
复制代码喽

我添加了--threshold-min 2到上述命令中，以限制至少有2倍差异的比较。

成本

没有好事是不受惩罚的。这次重写让我付出了什么代价？

首先，也是最重要的，它用尽了我过去几年的大部分空闲时间。使问题复杂化的是，我现在的空闲时间比过去少得多。所以像ripgrep这样的项目已经有一段时间没有发布新版本了。

其次，这引入了相当多的代码。为他人构建可重用的抽象与仅供正则表达式crate黑客担心的内部抽象是不同的。它通常会导致更多的代码，这意味着更大的二进制大小和更高的编译时间。

第三，这些抽象现在已发布并单独版本控制。这意味着我不能在不发布regex-automata的适当破坏性更改版本的情况下破坏这些内部引擎的API。我不会像对待regex crate那样保守，但这并不免费。这也将影响到贡献者。与其能够根据需要重构代码，现在必须应对公共API设计的压力。

由于正则表达式crate已经以其不理想的二进制大小和编译时间而闻名，并且由于这些变化将使情况变得更糟，作者决定采取两种不同的缓解措施：

• 如上所述，他使完全编译的DFA正则表达式引擎成为可选的。这个引擎引入了相当多的代码，但其对搜索性能的影响是温和的。
• 他发布了一个新的crate，regex-lite，它几乎是regex crate的直接替代品。它的设计基于几乎专门优化二进制大小和编译时间，以牺牲功能（即Unicode）和性能为代价。您仍然可以获得O(m * n)时间复杂度保证，但您不会获得任何花哨的Unicode支持，也不会获得快速的搜索时间。但二进制大小和编译时间要好得多。regex-lite没有依赖项。它与正则表达式crate共享零代码——包括自己的正则表达式解析器。

regex-lite缓解措施仍然是某种实验，但它只是表明使代码任意可减少是困难的。尽管正则表达式crate有许多功能可以禁用优化和Unicode功能，但它仍然无法接近regex-lite的二进制大小和编译时间。