Repository navigation
Description
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
acorn8.17.0. - Also observed on current
masterat5b9d16c256b81682d2b26246d86387f1d78633e9. - 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.mjsThe 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 callaltID.separatedFrom(state.branchID)for prior same-name branch ids.acorn/src/regexp.js:separatedFromwalks 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/
Activity
marijnh commentedon Jul 2, 2026
What prompted this issue? Did you run into a real program where this is a problem? Or are you worried about it being used as a denial-of-service vector? Or did you just let loose an agent on the code looking for random quadratic behavior?
Str1ckl4nd commentedon Jul 2, 2026
Thanks for the question.
Yes, this was found through automated exploration, but it was not a scan specifically aimed at denial-of-service reports or at filing arbitrary quadratic behaviors. The issue was manually reviewed before filing, and the reproduction was reduced into a concrete PoC with observed results.
We chose to file this as a public performance/resource-usage bug, not as a security advisory, because the impact depends on downstream usage: it matters mainly when Acorn is used to parse untrusted JavaScript with
ecmaVersion: 2025orlatest. Similar algorithmic-complexity and parser resource-exhaustion issues have been accepted and fixed in other codebases, so we considered it reasonable to report this and let the maintainers decide how it should be classified.That said, we understand that whether this behavior is an expected tradeoff, a normal bug, or a vulnerability is ultimately a maintainer decision. If you consider this within the expected behavior or outside Acorn’s scope to optimize, we will accept that. We will also use your feedback to improve our internal triage process so that we avoid sending reports that are not useful to maintainers.
perf(javascript): read a regexp repeating a capture group name in lin…
perf(javascript): read a regexp repeating a capture group name in lin…
perf(javascript): read a regexp repeating a capture group name in lin…
perf(javascript): read a regexp repeating a capture group name in lin…