JS RuntimeBaseline · Widely

RegExp Backtracking (ReDoS) and Unicode Modes

Mental Model

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.

Interactive Simulator

NFA Backtracking Explosion vs Linear Match

Trace how nested quantifiers (a+)+ explore 2^n paths on mismatch while /u handles surrogate pairs.

aaaaaaaaaa!
NFA Stack (Depth 1)
Main Thread
Step 1 / 3: 1. Greedy Forward Scan

Pattern /^(a+)+$/ consumes all 'a' characters in 'aaaaaaaaaa!' before hitting '!'.

/^(a+)+$/.test('aaaaaaaaaa!')
Internal State / Memory
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.

  1. Synchronous NFA: V8's Irregexp compiles patterns to native code, yet ambiguous quantifiers still backtrack exponentially.
  2. ReDoS Trigger: Input "aaaaaaaaaaaaaaaaaaaa!" against /^(a+)+$/ stalls the main thread for seconds.
  3. Unicode /u and /v: /u treats surrogate pairs (🚀) as single code points; /v (unicodeSets) adds set subtraction ([\p{Decimal_Number}--[0-9]]).
JS
// 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')); // true

Problem Genealogy

  • 1999 (ES3 Perl-style NFA): Shipped backtracking RegExp without atomic groups or UTF-16 surrogate awareness.
  • 2015 (ES6 /u Flag): Added full code-point matching and \p{...} Unicode property escapes.
  • 2024 (ES2024 /v Flag): Added Unicode string properties (\p{RGI_Emoji}) and character class set operations.

Production Pitfalls

Production Pitfall
  • Stateful /g lastIndex Bug: Calling .test() repeatedly on a /g regex mutates lastIndex, causing alternating true/false results 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
  • When not to use RegExp: Never parse nested HTML, JSON, or balanced parentheses with regular expressions, use a proper parser or DOMParser.

Connections & Logical Next Steps

JS RuntimeRegExp Backtracking (ReDoS) and Unicode Modes

Mechanical Comparisons