liveBook · Manning

Node-re2

As explained in Secrets of the JavaScript Ninja, Third Edition

node-re2 is a Node.js native binding to the RE2 regular-expression engine, which uses deterministic matching without backtracking.

When a JavaScript regex can be driven into catastrophic backtracking, node-re2 offers an alternative: a native Node.js binding to a DFA regex engine that eliminates backtracking and guarantees O(n) execution time for an input of length n. section 12.6.3

The tradeoff is reduced regex features: engines that eliminate backtracking cannot implement features that depend on it, such as backreferences and lookbehind. Consider node-re2 when regex safety is a priority. section 12.6.3

Listing 12.13 A regex with catastrophic backtracking
const rosterRegex = /^(?:\w+\s*)+$/; #A

console.assert( #B
  rosterRegex.test("Hattori Yoshi Fuma"), #B
  "A genuine roster is accepted instantly", #B
); #B

const attack = #C
  "I will erase your existence from this realm!"; #C
const start = performance.now(); #C
rosterRegex.test(attack); #C
const elapsed = performance.now() - start; #C
console.log(
  `Rejecting the attack string took ${elapsed.toFixed(0)}ms`,
);

A roster-matching regex illustrates how a seemingly ordinary pattern can take seconds to reject an attack string. section 12.6.3

How Secrets of the JavaScript Ninja, Third Edition covers it

How deep it goes
Contrasts DFA guarantees with backtracking-dependent features but does not detail the package API.
Examples
Uses a roster-matching regex and an attack string to demonstrate slow rejection from catastrophic backtracking.
What you can do after
Evaluate the safety-versus-feature tradeoff when choosing a regex engine for a Node.js project.
How it connects
Connects regular expressions to catastrophic backtracking, denial-of-service risks, backreferences, and lookbehind.

This explainer was generated by Manning's knowledge graph from the text of Secrets of the JavaScript Ninja, Third Edition. The section links point to the parts of the book it draws on.