一句话：界定了 JavaScript 正则中可线性时间匹配的更大子集，并给出首个非回溯的线性 lookaround 匹配算法。
现代正则语言已远偏离传统正则表达式，其特性从根本上改变了匹配问题，常导致指数级复杂度膨胀，成为 JavaScript 应用中拒绝服务漏洞的常见来源；更糟的是各语言的正则语义存在分歧，这些分歧对算法设计与最坏情况复杂度的影响鲜有研究。本文从 JavaScript 正则语义出发，识别出一个比以往认知更大的、可保证线性时间匹配的子集，并发现现有最先进算法在若干情形下或语义错误、或复杂度超线性、或过度保守地认为某些特性无法线性匹配。作者提出新算法以恢复正确性与线性复杂度，并首次给出非回溯的线性 lookaround 匹配算法：一个适用于任意正则语言的无捕获 lookbehind 方案，另一个利用 JavaScript 特有性质支持无限制 lookahead 与 lookbehind。论文还描述了正则引擎新的时间与空间复杂度权衡。所有算法均在原型实现中验证了实用性，部分已被合入 Chrome 与 Node.js 所使用的 V8 引擎。
Modern regex languages have strayed far from well-understood traditional regular expressions: they include features that fundamentally transform the matching problem. In exchange for these features, modern regex engines at times suffer from exponential complexity blowups, a frequent source of denial-of-service vulnerabilities in JavaScript applications. Worse, regex semantics differ across languages, and the impact of these divergences on algorithmic design and worst-case matching complexity has seldom been investigated. This paper provides a novel perspective on JavaScript’s regex semantics by identifying a larger-than-previously-understood subset of the language that can be matched with linear time guarantees. In the process, we discover several cases where state-of-the-art algorithms were either wrong (semantically incorrect), inefficient (suffering from superlinear complexity) or excessively restrictive (assuming certain features could not be matched linearly). We introduce novel algorithms to restore correctness and linear complexity. We further advance the state-of-the-art in linear regex matching by presenting the first nonbacktracking algorithms for matching lookarounds in linear time: one supporting captureless lookbehinds in any regex language, and another leveraging a JavaScript property to support unrestricted lookaheads and lookbehinds. Finally, we describe new time and space complexity tradeoffs for regex engines. All of our algorithms are practical: we validated them in a prototype implementation, and some have also been merged in the V8 JavaScript implementation used in Chrome and Node.js.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2311-17620,
title = {Linear Matching of JavaScript Regular Expressions},
author = {Aurèle Barrière and Clément Pit-Claudel},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {PLDI},
year = {2024},
doi = {10.1145/3656431}
}