#Linear Matching S1

中文标题：线性匹配

#线性匹配

一个 JavaScript 提案，旨在提供正则表达式匹配能力，而无需面临灾难性、不可恢复失败的风险。

阶段： 0

提案发起人： Michael Ficarra, Aurèle Barrière, Clément Pit-Claudel

#动机

由于所有现代 JavaScript 引擎中嵌入的正则表达式引擎都使用了回溯策略，执行正则表达式匹配可能是一项危险的操作。在这些引擎中，根据模式的不同，匹配操作可能（实际上）永远无法完成，从而导致程序进入不可恢复的错误状态。如果可以通过用户输入或环境输入触发此状况的程序，则被认为容易受到 ReDoS 攻击。ReDoS 漏洞多年来在 JavaScript 生态系统中 非常普遍。从 2026 年 1 月到 5 月，ReDoS 漏洞 每 2.7 天就会导致一个 CVE。当前的缓解策略往往要么成本过高，要么限制过多，要么不够充分。

#向委员会提交的演示

• 2026 年 7 月
• 2026 年 5 月

#提案

我们应该为以下用例提供解决方案：

1. 程序员希望使用来自不可信来源（例如用户输入或动态生成模式的函数）的模式进行匹配。
2. 程序员希望使用固定模式对不可信的用户输入进行匹配。
3. 程序员希望在模式无法在合理时间内对给定输入完成匹配时提供回退行为，而不是尝试运行可能（实际上）永远不会完成的匹配。
4. 模式生产者希望确保天真的消费者对该模式使用线性匹配策略。

#考虑的设计空间

由于这是一个早期阶段提案，设计空间仍然非常开放。但我们已经考虑了一些可能在后续阶段提出的解决方案的可能组成部分。

#表明将使用线性实现的指示器

if (re.willMatchlinearly) {
  re.exec(...);
} else {
  // 回退行为
}

在构造 RegExp 之后，可以使用谓词或其他指示器（例如 RegExp.prototype 的 getter）来在引擎无法在线性时间内匹配模式时提供回退行为。

#线性的 exec 变体

try {
  let match = re.execLinear(input);
} catch {
  // 回退行为
}

一个新的 RegExp.prototype 方法，类似于 exec，但选择线性匹配。

#l 标志

try {
  let re = /pattern/l;
} catch {
  // 回退行为
}

一个新的 RegExp l 标志既可以用于向 exec 表明优先使用线性匹配策略，也可以在构造时如果模式无法被引擎线性匹配则抛出错误。

#为 exec 提供超时、输入倍数或燃料参数

let match = re.exec(input, 10e3);

程序员可以通过某种方式传达在某种资源耗尽之前应使用回溯实现，之后应使用线性实现。或者，操作可以抛出一个表示资源耗尽的错误，程序员可以提供回退行为。

#先前工作

#其他语言

• Ruby: 选择性记忆化策略 和 Regexp.linear_time? 谓词
• Rust: regex crate 省略了没有已知线性实现的特性
• C++ 及其他： RE2 库提供了适用于 node.js、OCaml、WebAssembly 等的包装器。
• .NET 语言： RegexOptions.NonBacktracking 将 RegExp 选择为线性匹配策略
• Go: regexp 包 省略了没有已知线性实现的特性

#JS 库

• node-re2: RE2 线性引擎 的 Node.js 绑定
• regolith: 使用 Rust 线性引擎 的 TypeScript/JavaScript 服务端库
• re2js: 移植到 JavaScript 的 RE2
• @iter-tools/regex 和 @bablr/regex-vm：流式正则表达式实现

#V8 实验性引擎

• https://v8.dev/blog/non-backtracking-regexp
• V8 标志 --enable-experimental-regexp-engine
• 不完整且未积极维护

#常见问题解答

#为什么我们不尽可能要求线性？

虽然限制所有可能实现线性化的 RegExp 的最坏情况复杂度听起来很有吸引力，但这实际上可能对大多数 RegExp 匹配产生不可接受的负面影响。尽管回溯实现在最坏情况下复杂度非常差，但在典型情况下，它们会优于线性实现，尤其是更新的、优化较少的线性实现。