regex-automata

这个crate暴露了由regex crate使用的各种正则表达式引擎。它为每个正则表达式引擎提供了一套庞大、复杂且“专家级”的API。这个crate提供的正则表达式引擎着重于有限自动机实现，并特别保证所有搜索的worst case O(m * n)时间复杂度。（其中 m ~ len(regex) 和 n ~ len(haystack)。）

文档

https://docs.rs/regex-automata

示例

此示例展示了如何搜索多个正则表达式的匹配项，其中每个正则表达式使用相同的捕获组名称来解析不同的键值格式。

use regex_automata::{meta::Regex, PatternID};

let re = Regex::new_many(&[
    r#"(?m)^(?<key>[[:word:]]+)=(?<val>[[:word:]]+)$"#,
    r#"(?m)^(?<key>[[:word:]]+)="(?<val>[^"]+)"$"#,
    r#"(?m)^(?<key>[[:word:]]+)='(?<val>[^']+)'$"#,
    r#"(?m)^(?<key>[[:word:]]+):\s*(?<val>[[:word:]]+)$"#,
]).unwrap();
let hay = r#"
best_album="Blow Your Face Out"
best_quote='"then as it was, then again it will be"'
best_year=1973
best_simpsons_episode: HOMR
"#;
let mut kvs = vec![];
for caps in re.captures_iter(hay) {
    // N.B. One could use capture indices '1' and '2' here
    // as well. Capture indices are local to each pattern.
    // (Just like names are.)
    let key = &hay[caps.get_group_by_name("key").unwrap()];
    let val = &hay[caps.get_group_by_name("val").unwrap()];
    kvs.push((key, val));
}
assert_eq!(kvs, vec![
    ("best_album", "Blow Your Face Out"),
    ("best_quote", "\"then as it was, then again it will be\""),
    ("best_year", "1973"),
    ("best_simpsons_episode", "HOMR"),
]);

安全性

我欢迎对unsafe代码的审计。

此crate在尽可能保守地使用unsafe的同时，也使用了它的一些地方。总的来说，我非常开放，如果使用unsafe不会导致可衡量的性能下降，并且不会导致代码显著复杂化，我将非常乐意移除使用unsafe。

以下是此crate中使用unsafe的概述。

• util::pool::Pool使用unsafe来实现池中访问元素的高速路径。高速路径适用于第一个使用池的线程。实际上，高速路径之所以快速，是因为它避免了互斥锁。在Pool的无std版本中，也使用了unsafe来实现自旋锁以进行同步。
• util::lazy::Lazy 使用 unsafe 实现了在无标准环境下的 once_cell::sync::Lazy 变体。同时提供了一个不使用分配的实现，这也需要使用 unsafe。
• 《code>dfa 模块广泛使用 unsafe 来支持 DFA 的零拷贝反序列化。核心问题是需要在不做任何复制的情况下，从 &[u8] 获取到 DFA 的内部表示。这在无标准无分配环境中是必需的，同时也使反序列化变得极为高效。
• 《code>dfa 和 hybrid 模块使用 unsafe 明确省略了核心搜索循环中的边界检查。这使得代码生成更紧凑，并且在某些工作负载上通常会导致 5-10% 的一致性能提升。

总的来说，上述内容反映了整个 regex 仓库中 unsafe 的唯一用法。目前，没有计划有意义地扩展 unsafe 的使用。尽管如此，人们一直在询问的一个问题是高效地反序列化 regex::Regex。我的感觉是，这个特性将需要在多个地方使用更多的 unsafe 来支持零拷贝反序列化。目前还不清楚是否会追求这个目标。

动机

我开始构建这个 crate，是因为我想重新设计 regex crate 的内部结构，使其更适合优化。实际上，构建正则表达式引擎有无数种方法，组合它们的方法也更多。此外，启发式文本优化往往很难正确实现，但它们带来的成果却很吸引人。所有这些都在没有引入更多错误的风险下难以扩展。因此，我决定推倒重来。

在这个过程中，我最终设计了每个组件之间的强大边界，这样每个组件都可以独立地进行推理和测试。这也使得将组件作为库本身暴露出来变得多少有些自然。也就是说，人们已经很久以来一直要求在正则表达式 crate 中添加更多功能，但这些功能通常伴随着额外的 API 复杂性，我不希望在 regex crate 中引入这些复杂性。但是，在像 regex-automata 这样的“专家级”crate 中暴露它们似乎相当合适。

最终，我仍然多少认为这个 crate 是一个实验。组件之间的强大边界是否会成为持续发展的障碍尚不清楚。在我的经验中，解耦往往会导致开发速度减慢，而且当混合进不经常引入破坏性变更的额外成本时，事情会变得相当复杂。但是，我并不认为有人曾经将正则表达式引擎的内部结构作为库发布过。因此，看到它的结果将会很有趣！