lRegExp

Transparent linear-time (non-backtracking) regular expressions for libraries.

Usage

This library exports a drop-in replacement for the built-in RegExp (caveats apply).

1. Install

   npm install @ericcornelissen/lregexp

2. Import

   import RegExp from "@ericcornelissen/lregexp";

3. Use

   new RegExp("[linear]{6}");

Runtimes

This library is compatible with Node.js, Deno, Bun, and major browsers. It only takes effect in V8-based runtimes (Node.js, Deno, Chromium-based browsers) when the experiment linear-time engine is enabled. Otherwise it falls back to the default RegExp constructor.

Why

Backtracking regular expressions can take exponential time to evaluate, leading to the dreaded ReDoS vulnerability. Linear-time regular expressions avoid this by not backtracking.

In Node.js, linear-time regular expressions can be created using the l flag provided the --enable-experimental-regexp-engine CLI option is used. This makes it difficult for library authors to tap into. Using this package, a library can use the RegExp constructor as usual and benefit from the linear time regular expression engine when its users enable it. If they don't, it gracefully falls back to the default constructor.

Caveats

Not all valid JavaScript regular expressions are supported when using the --enable-experimental-regexp-engine CLI option. This library won't tell you if your regular expressions are incompatible, unless you run it with that CLI option. If a regular expression is incompatible the constructor will throw a SyntaxError.

To support users of this package in writing compatible regular expressions we're interested in:

• an ESLint plugin to lint regular expressions and raise warnings for the use of regex features not supported by the non-backtracing engine; (#4)
• a tool (CLI/web) to check a given regular expression for compatibility with the non-backtracing engine. (#21)

How

If --enable-experimental-regexp-engine is used, the RegExp constructor from this package automatically adds the l flag to all regular expressions it constructs. If not, the RegExp constructor behavior is unchanged.

Example

A classic example of a ReDoS-vulnerable regular expression is (a*)*b. Using this with vanilla Node.js on a pathological input string takes some time, test it for yourself with (add an a and the runtime doubles):

node -e '/(a*)*b/.test("aaaaaaaaaaaaaaaaaaaaaaaaac")'

When the non-backtracking regular expression engine is enabled, the expression evaluates instantly:

node -e '/(a*)*b/l.test("aaaaaaaaaaaaaaaaaaaaaaaaac")' --enable-experimental-regexp-engine