#Linear Matching S1

#Linear Matching

A JavaScript proposal to provide RegExp matching capabilities without the risk of catastrophic, unrecoverable failure.

Stage: 0

Champions: Michael Ficarra, Aurèle Barrière, Clément Pit-Claudel

#Motivation

Due to the use of a backtracking strategy in the RegExp engines embedded in all modern JavaScript engines, performing a RegExp match can be a dangerous operation. In these engines, depending on the pattern, the match operation may (practically) never complete, causing the program to enter an unrecoverable error state. Programs where this condition can be induced through user or environmental inputs are said to be vulnerable to ReDoS. ReDoS vulnerabilities have been highly prevalent in the JavaScript ecosystem for years. From January to May 2026, ReDoS vulnerabilities have resulted in a CVE every 2.7 days. Current mitigation strategies are often either too costly, too limiting, or inadequate.

#Presentations to Committee

• July 2026
• May 2026

#Proposal

We should provide solutions for the following use cases:

1. A programmer wants to match using a pattern that was derived from an untrusted source such as user input or a function that generates patterns dynamically.
2. A programmer wants to match using a fixed pattern against untrusted user input.
3. A programmer wants to provide fallback behaviour in the case that a pattern is unable to be matched in a reasonable amount of time for the given input instead of trying to run a match that may (practically) never complete.
4. A pattern producer wants to ensure that naïve consumers use a linear matching strategy for that pattern.

#Considered Design Space

As this is an early stage proposal, the design space is still very open. But we have thought through some possible components of a solution that may be proposed at a later stage.

#an indicator that a linear implementation will be used for matching

if (re.willMatchlinearly) {
  re.exec(...);
} else {
  // fallback behaviour
}

After constructing a RegExp, a predicate or other indicator (such as a RegExp.prototype getter) can be used to provide fallback behaviour if the engine is unable to match the pattern in linear time.

#linear exec variant

try {
  let match = re.execLinear(input);
} catch {
  // fallback behaviour
}

A new RegExp.prototype method that is like exec but opts in to linear matching.

#l flag

try {
  let re = /pattern/l;
} catch {
  // fallback behaviour
}

A new RegExp l flag could be used both to indicate to exec that a linear matching strategy is preferred as well as to throw on construction if the pattern cannot be matched linearly by the engine.

#a timeout, input multiplier, or fuel parameter for exec

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

Some way for the programmer to communicate that a backtracking implementation should be used until some kind of resource exhaustion, at which point a linear implementation should be used. Alternatively, the operation could throw an error that indicates resource exhaustion and the programmer could provide the fallback behaviour.

#Prior Art

#other languages

• Ruby: selective memoisation strategy and Regexp.linear_time? predicate
• Rust: regex crate omits features with no known linear implementation
• C++ and others: the RE2 library has wrappers available for node.js, OCaml, WebAssembly, etc.
• .NET languages: RegexOptions.NonBacktracking opts a RegExp into a linear matching strategy
• Go: regexp package omits features with no known linear implementation

#JS libraries

• node-re2: Node.js bindings for the RE2 linear engine
• regolith: TypeScript/JavaScript server-side lib using the Rust linear engine
• re2js: RE2 ported to JavaScript
• @iter-tools/regex and @bablr/regex-vm: streaming regex implementation

#V8 experimental engine

• https://v8.dev/blog/non-backtracking-regexp
• V8 flag --enable-experimental-regexp-engine
• Incomplete and not actively maintained

#FAQ

#Why don't we just require linearity whenever possible?

While it may sound appealing to limit worst-case complexity for all RegExps where it is possible to do so, this may actually have an unacceptable negative impact on most RegExp matches. Although backtracking implementations have very bad worst-case complexity, in typical cases, they will outperform linear implementations, especially newer, less-optimised linear implementations.