这是一篇关于在 Rust 线性时间正则表达式引擎中添加无捕获环视（captureless lookbehinds）的注释指南，主要内容如下：

• 背景与目标：Erik 曾在 RE2 引擎中实现线性时间匹配算法，本文将在 Rust 语言的官方正则表达式引擎中实现相同功能，即添加对无边界无捕获环视的支持。

• regex 库架构：

  • regex-syntax：负责将原始正则表达式输入处理为可用于正则表达式编译器的表示形式，包括解析为抽象语法树（AST），再转换为更规范化的高级中间表示（HIR），并存储有助于优化和保证正确性的属性。
  • regex-automata：包含多种正则表达式引擎实现，其中修改后的 PikeVM 用于实现环视功能，还有一个重要的元正则引擎（meta-regex）用于选择最佳引擎进行搜索。

• 实现工作：

  • 前端：解析器需接受环视但拒绝前瞻，AST 到 HIR 的翻译要更新属性以考虑环视的不同语义，如设置 HIR 节点的长度属性为零，并添加指示节点是否包含环视的新属性。
  • 元引擎：确保元引擎在正则表达式中存在环视时只考虑 PikeVM，禁用跳过所有引擎使用子字符串搜索，并添加手动条件以在存在环视时跳过回溯器。
  • 环视线程：初始实现中，通过将每个环视的自动机编译为一个大的联合状态来运行多个 NFA 模拟，但发现优先级问题导致不必要的扫描，解决方法是将环视的活动线程与主正则表达式的线程分离，以确保正确的匹配语义。
  • Match-All：在基准测试中发现扫描到字符串末尾的问题导致 Match-All 搜索具有二次运行时复杂度，解决方案是在进行所有匹配搜索时保留环视的活动线程，以避免不必要的“追赶”。
• 评估：添加单元测试和集成测试以确保实现的正确性，使用 rebar 工具比较修改后的引擎与原始引擎及其他引擎的性能，结果显示修改后的引擎在包含环视的搜索中性能合理，与 python-re 相比有一定差距，但通过优化有改善空间。

• 扩展工作：

  • 有界环视优化（Marcin）：计算每个环视的 k 值，k 为周围环视的 k 值之和加上当前环视的最长匹配长度减去前面正则表达式的最短匹配长度，此优化可避免无用工作，在基准测试中可提高速度高达 150 倍。
  • 有界回溯器（Robin）：在回溯器中实现环视支持，包括反向编译环视子表达式、存储环视探索的匹配结果以避免重复探索以及解决 Match-All 搜索中的二次复杂度问题，但仍存在一些未解决的问题。
• 结论：在 Rust 生态系统中实现了环视功能，并通过优化提高了性能，为实际应用做好准备，同时为回溯引擎的进一步扩展奠定了基础，希望能造福 Rust 社区并鼓励其他线性正则表达式引擎实现环视。

附录中提供了不同情况下的基准测试结果对比。