Quadratic regexp validation for ES2025 duplicate named capture groups

Summary

acorn.parse appears to spend quadratic time in regexp validation for ES2025 duplicate named capture groups when the same group name appears across many disjoint regexp alternatives.

The input is accepted by the ES2025 duplicate-name semantics, but validation compares each later same-name group against all previous same-name groups. With a compact regexp literal, the duplicate-name case becomes much slower than a same-size control that uses unique names.

Affected path

• Observed on acorn 8.17.0.
• Also observed on current master at 5b9d16c256b81682d2b26246d86387f1d78633e9.
• Entry point: acorn.parse(source, { ecmaVersion: "latest" }).
• Relevant path: regexp tokenization and pattern validation, especially acorn/src/regexp.js.

Reproduction

From the source checkout repository root, save this as verify-duplicate-names.mjs and run it with Node. The script imports ./acorn/src/index.js, so it is meant for a repository checkout rather than an installed package:

import {performance} from "node:perf_hooks"
import {parse, version} from "./acorn/src/index.js"

function term(depth, name) {
  return "(?:".repeat(depth) + `(?<${name}>a)` + ")".repeat(depth)
}

function payload(count, depth, duplicateName) {
  const body = Array.from({length: count}, (_, i) => {
    return term(depth, duplicateName ? "x" : `x${i}`)
  }).join("|")

  return `/${body}/v`
}

function measure(label, source) {
  const started = performance.now()
  parse(source, {ecmaVersion: "latest"})
  const elapsedMs = performance.now() - started
  return {label, bytes: source.length, elapsedMs}
}

parse("/a/", {ecmaVersion: "latest"})

const count = Number(process.env.COUNT || 240)
const depth = Number(process.env.DEPTH || 240)

const control = payload(count, depth, false)
const duplicateCase = payload(count, depth, true)

const controlResult = measure("unique capture names control", control)
const duplicateResult = measure("duplicate capture names", duplicateCase)
const ratio = duplicateResult.elapsedMs / Math.max(controlResult.elapsedMs, 1)

const result = {
  acornVersion: version,
  count,
  depth,
  control: {
    bytes: controlResult.bytes,
    elapsedMs: Number(controlResult.elapsedMs.toFixed(3))
  },
  duplicateCase: {
    bytes: duplicateResult.bytes,
    elapsedMs: Number(duplicateResult.elapsedMs.toFixed(3))
  },
  ratio: Number(ratio.toFixed(2))
}

console.log(JSON.stringify(result, null, 2))

if (duplicateResult.elapsedMs < 500) {
  throw new Error(`Expected duplicate-name parsing to take at least 500 ms, got ${duplicateResult.elapsedMs.toFixed(3)} ms`)
}

if (ratio < 20) {
  throw new Error(`Expected duplicate-name parsing to be at least 20x slower than the control, got ${ratio.toFixed(2)}x`)
}

Command:

node verify-duplicate-names.mjs

The example uses the /v flag to exercise the ES2025 path. In local checks, /u showed the same pattern, while omitting a Unicode-style flag made parsing slower because the regexp was validated more than once. The 500 ms and 20x checks are only a coarse oracle for the reproduction script; the printed ratio is the main value to compare across machines.

Observed result

In a Docker-based check using node:22-bookworm-slim against acorn 8.17.0 / 5b9d16c256b81682d2b26246d86387f1d78633e9, the same generation and parse logic produced:

{
  "acornVersion": "8.17.0",
  "count": 240,
  "depth": 240,
  "control": {
    "bytes": 232932,
    "elapsedMs": 36.952
  },
  "duplicateCase": {
    "bytes": 232322,
    "elapsedMs": 3014.735
  },
  "ratio": 81.59
}

The exact numbers vary by machine, but the duplicate-name case consistently takes much longer than the same-size unique-name control.

Expected result

Duplicate named capture groups across disjoint alternatives are valid ES2025 syntax, but validating them should scale much closer to the same-size unique-name control.

Implementation note

The expensive behavior seems to come from the duplicate-name validation path. For each same-name group, regexp_groupSpecifier checks every previous branch id stored for that name. Each separatedFrom check then walks the two branch ancestry chains. With many same-name alternatives, this makes the total validation work grow much faster than input size.

Relevant areas:

• acorn/src/tokenize.js: regexp literals are validated before the token is returned.
• acorn/src/regexp.js: ES2025 branch tracking is enabled for duplicate named capture groups.
• acorn/src/regexp.js: duplicate names call altID.separatedFrom(state.branchID) for prior same-name branch ids.
• acorn/src/regexp.js: separatedFrom walks both branch ancestry chains.

Reporters:

• [email protected] (Liyi), https://lzhou1110.github.io/
• [email protected] (Ziyue), https://zyy0530.github.io/
• [email protected] (Strick), https://str1ckl4nd.github.io/
• [email protected] (Maurice), http://maurice.busystar.org/
• [email protected] (Chenchen), https://7thparkk.github.io/