RegExp Backtracking (ReDoS) and Unicode Modes
JavaScript's RegExp engine uses a backtracking NFA: nested quantifiers like (a+)+ explore $2^n$ partitions on a failing suffix, locking the Call Stack into a Long Task. Meanwhile, omitting /u or /v splits 32-bit emoji into broken 16-bit UTF-16 surrogates.
NFA Backtracking Explosion vs Linear Match
Trace how nested quantifiers (a+)+ explore 2^n paths on mismatch while /u handles surrogate pairs.
Pattern /^(a+)+$/ consumes all 'a' characters in 'aaaaaaaaaa!' before hitting '!'.
/^(a+)+$/.test('aaaaaaaaaa!')- pattern
- /^(a+)+$/
- index
- 10
- backtracks
- 0
Under the Hood
V8's Irregexp engine compiles patterns to native code, yet executes a backtracking NFA on the synchronous Call Stack. When nested quantifiers hit a failing suffix, exponential match partitions run without yielding, locking the main thread as a Long Task.
- Synchronous NFA: V8's Irregexp compiles patterns to native code, yet ambiguous quantifiers still backtrack exponentially.
- ReDoS Trigger: Input
"aaaaaaaaaaaaaaaaaaaa!"against/^(a+)+$/stalls the main thread for seconds. - Unicode
/uand/v:/utreats surrogate pairs (🚀) as single code points;/v(unicodeSets) adds set subtraction ([\p{Decimal_Number}--[0-9]]).
// Safe linear check + /v Unicode property & set difference
const SAFE_USER = /^[\p{L}\p{N}_-]{1,64}$/v;
// Dangerous: nested quantifier (a+)+ triggers ReDoS
const UNSAFE = /^([a-z0-9]+)+$/i;
console.log(SAFE_USER.test('ada_42')); // trueProblem Genealogy
- 1999 (ES3 Perl-style NFA): Shipped backtracking
RegExpwithout atomic groups or UTF-16 surrogate awareness. - 2015 (ES6
/uFlag): Added full code-point matching and\p{...}Unicode property escapes. - 2024 (ES2024
/vFlag): Added Unicode string properties (\p{RGI_Emoji}) and character class set operations.
Production Pitfalls
- Stateful
/glastIndexBug: Calling.test()repeatedly on a/gregex mutateslastIndex, causing alternatingtrue/falseresults on identical strings. - ReDoS on User-Supplied Inputs: Validating email or Markdown with nested
+/*groups opens a client-side freeze vector.
- When not to use
RegExp: Never parse nested HTML, JSON, or balanced parentheses with regular expressions, use a proper parser orDOMParser.
Connections & Logical Next Steps
RegExp matching executes synchronously inside the active Call Stack frame without yielding.
Catastrophic O(2^n) RegExp backtracking locks the main thread as an uninterruptible Long Task.
scheduler.yield() pauses between loop iterations, whereas catastrophic regex backtracking stalls a single synchronous call frame.