Linear Matching

for Stage 1

Michael Ficarra • TC39 • July 2026

​

Champions: Michael Ficarra,

Clément Pit-Claudel, Aurèle Barrière

motivation

• ReDoS vulnerabilities are incredibly common
• it's too easy to fall into super-linearity today
• delayed trigger: not easily discoverable until a specific input is matched
• the program enters an unrecoverable error state (⚠️ THIS IS VERY BAD!)
• static detection is unreliable because the spec makes no perf guarantees
• an alternative user code implementation would be large and very slow

use cases

use case #1: generating patterns dynamically

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.�

new RegExp(userInput).test(...)

or

generatePatternFrom(location.hash).test(...)

use case #2: matching untrusted inputs

A programmer wants to match using a fixed pattern against untrusted user input.�

re.test(userInput)

use case #3: give up and recover instead of stalling

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.�

try {� re.test(...)�} catch {� // we may never get here!� // .test(...) doesn't throw, it just stalls indefinitely�}

use case #4: producer ≠ consumer

A pattern producer wants to ensure that naïve consumers use a linear matching strategy for that pattern.�

function producePossiblyUnsafePattern(input) {� // ...� return markAsShouldBeMatchedLinearly(re);�}

solution exploration

solution exploration part 1: linearity indicator

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.�

if (re.willMatchlinearly) {� re.exec(...);�} else {� // fallback behaviour runs if this engine is� // unable to match this pattern in linear time�}

solution exploration part 2: linear method variants

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

try {� let match = re.execLinear(input);�} catch {� // fallback behaviour runs if this engine is� // unable to match this pattern in linear time�}

solution exploration part 3: new flag

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.�

try {� let re = /pattern/l;�} catch {� // fallback behaviour runs if this engine is� // unable to match this pattern in linear time�}

​

solution exploration part 4: fuel / timeout

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. �

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

�Alternatively, the operation could throw an error that indicates resource exhaustion and the programmer could provide the fallback behaviour.

solution exploration part 5: spec perf requirements

The spec can define a subset of RegExp features that are required to be matched in linear time by all implementations. Patterns that stay within that subset will be guaranteed to match in linear time, avoiding the need for a runtime safety check or defining fallback behaviour. Static analysis tools (linters) can now reliably check for use of features that are not in this subset.

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

​

problem statement

There is no built-in way for programmers to match regular expressions without the risk of catastrophic, unrecoverable failure.

Stage 1?