Rule to write regular expressions compatible with the linear engine

[ericcornelissen]

Description

This is more of a suggestion than a well-defined rule proposal. I figured someone else might already have the knowledge to say whether this is a great or a terrible idea.

My basic idea is to have a rule that forces you to write regular expressions that are compatible with V8's linear regular expression engine. I haven't looked at it too carefully but it is my understanding that this would just amount to disallow certain features of JavaScript regular expressions because they're not supported by that engine.

For some additional context, I'm trying to figure out how I, as a library author, can write regular expression that are compatible with the linear engine so that application developers actually have a chance of enabling the option (I started a discussion in nodejs/node#51659 (comment)).

[ota-meshi]

Thanks for the suggestion!
That's very interesting and I would like to see that rule 👍
But I'm not sure how to check it. Do you have any ideas?

[ericcornelissen]

I wrote a script (see end of comment) that tries to construct a regular expression with the l flag using (hopefully) very flag and kind-of-pattern. I cross-referenced it with the following from blog post:

• not contain backreferences,
• not contain lookaheads or lookbehinds,
• not contain large or deeply nested finite repetitions, as in e.g. /a{200,500}/, and
• not have the u (Unicode) or i (case insensitive) flags set.

my results largely line up, except that lookbehinds seem to be accepted and the d flag rejected. In particular, the following are rejected:

• d flag
• i flag
• u and v flag
• "large" values for a{n} (n>16)
• "large" values for a{n,} (n>16, greedy or not)
• "large" upper bounds for a{n,m} (m>16, greedy or not)
• positive and negative lookaheads
• numeric and named backreferences

Hence, if we could create a rule that disallows the use of these regex features (ideally based on the exact value for a{n} etc., disallowing if it's dynamic as in RegExp('a{'+x+'}')) then I think this covers everything.

// Usage:
// 1. Create a file `lregex-test.mjs` with this content.
// 3. Run `node --enable-experimental-regexp-engine lregex-test.mjs`.

function test(pattern, flags="") {
  try {
    new RegExp(pattern, `l${flags}`);
    console.log("OK ", `/${pattern}/l${flags}`);
  } catch {
    console.log("ERR", `/${pattern}/l${flags}`);
  }
}

console.log("FLAGS");
const flags = ["d", "g", "i", "m", "s", "u", "v", "y"];
for (const flag of flags) {
  test("foobar", flag);
}

console.log("PATTERNS");
const patterns = [
  "foobar", // basic
  "\\0", "\\r", "\\t", "\\n", // special characters
  ".", // wildcard
  "fo*bar", // zero-or-more (greedy)
  "fo*?bar", // zero-or-more (lazy)
  "fo+bar", // one-or-more (greedy)
  "fo+?bar", // one-or-more (lazy)
  "fo?bar", // zero-or-one (greedy)
  "fo??bar", // zero-or-one (lazy)
  "fo{16}bar", "fo{17}bar", // exactly
  "fo{16,}bar", "fo{17,}bar", // n-or-more (greedy)
  "fo{16,}?bar", "fo{17,}?bar", // n-or-more (lazy)
  "fo{15,16}bar", "fo{16,17}bar", // n-to-m (greedy)
  "fo{15,16}?bar", "fo{16,17}?bar", // n-to-m (lazy)
  "foo|bar", // disjunct
  "\\s", "\\S", "\\d", "\\D", "\\w", "\\W", // character sets
  "\\u1234", "\\x12", // hex character
  "\\045", // octal character
  // "\\p{...}", // unicode category, n/a since 'u' and 'v' flags are unsupported
  // "\\P{...}", // negated unicode category, n/a since 'u' and 'v' flags are unsupported
  "\\cI", // control character
  "\\b", "\\B", // word-boundary
  "[foobar]", // set
  "[a-z]", // set-range
  "[^foobar]", // negated set
  "[^a-z]", // negated set-range
  "[\b]", // backspace
  "(foobar)", // capturing group
  "(?:foobar)", // non-capturing group
  "(?<foo>bar)", // named-capturing group
  "(?=bar)", // positive lookahead
  "(?!bar)", // negative lookahead
  "(?<=foo)", // positive lookbehind
  "(?<!foo)", // negative lookbehind
  "(foo|bar)\\1", // numeric backref
  "(?<foo>bar|baz)\\k<foo>", // named backref
  "^foobar", // start anchor
  "foobar$", // end anchor
];
for (const pattern of patterns) {
  test(pattern);
}

[ericcornelissen]

The above is for Node.js v22.14.0, trying on Node.js v18.3.0 the results are a bit different. In particular, it also disallows:

• smaller values for a{n,} (n>15, greedy or not)
• positive and negative lookbehinds

Hence, we'd either need to be conservative and disallow all or change what is allowed based on the Node.js version which I guess would need to be user provided (ideally we could use the package.json#engines.node field if available, I don't know if ESLint supports that?)

[ota-meshi]

Thank you for compiling the information.

Oh, we can't use the u and v flags...
That would conflict with the recommended preset for this plugin, so I think we'll need to be careful when enabling that rule.

[ota-meshi]

I think it's good to include information about the Node version in the documentation, but since v18 is EOL, I think it's fine as long as rules are designed to work well with the latest version of Node.

[ericcornelissen]

Oh, we can't use the u and v flags... That would conflict with the recommended preset for this plugin, so I think we'll need to be careful when enabling that rule.

I indeed don't think it makes sense to enable this rule by default as it's pretty niche and can be hard(/annoying) to comply with in many scenarios in return for, in all likelihood, little value (as of today, I don't believe the linear regex engine is commonly used). And yea, conflicting rules in the default configuration should definitely not happen 😅

I think it's good to include information about the Node version in the documentation, but since v18 is EOL, I think it's fine as long as rules are designed to work well with the latest version of Node.

That seems reasonable to me.