Skip to content

Commit ef7223f

Browse files
perf(javascript): read a regexp repeating a capture group name in linear time (#22187)
* test(javascript): hold the parser to acorn's own test suite acorn ships no tests in its npm tarball, so `WebpackParser.unittest.js` records them itself: it replays every `test/tests*.js` of an acorn checkout against a driver that records rather than parses, and vendors each case's source, options and expected error as `test/fixtures/acorn-corpus.json`. The expected trees are left behind — the run takes those from acorn itself. All 3534 cases go through both parser entry points under three option sets, diffing trees, comments, tokens and error messages against acorn and re-asserting acorn's own recorded verdicts. Where the checkout exists the run also checks the corpus against it, and `WEBPACK_UPDATE_ACORN_CORPUS=1` rewrites it. The tree diff moves to `test/helpers/compareParserOutput.js`, shared with the test262 suite. * perf(javascript): read a regexp repeating a capture group name in linear time Validating a named capture group compares its branch against every branch already recorded for that name, and acorn compares two branches by walking one chain per node of the other — quadratic in the nesting depth, per pair. A pattern of 160 alternatives each nesting a same-named group 160 deep took 7.4s where the same pattern with distinct names took 0.09s. A branch chain holds at most one branch per disjunction, so marking each disjunction the first chain passed answers the comparison in one walk of the second. The same pattern now validates in 0.12s (acornjs/acorn#1445). * test(javascript): ask the engine which regexps it read, not a list The corpus exempted a fixed list of patterns from the verdict comparison: the ones acorn rejects by edition that webpack takes as written because the host engine built them. Which patterns those are is the running V8's answer, so a newer one reads more of them and the list went stale — CI's V8 accepts ES2025 duplicate capture names and modifier groups, and 38 cases diverged there that agree here. The exemption now reads the tree webpack returned: a regexp literal the engine built carries a real RegExp as its value. The ported base parser, which validates every literal, is held to acorn with no exemption at all. * style(javascript): shorten the comment over the branch marking Two lines, as the lib/ review instruction asks, keeping what the code cannot say: a chain holds one branch per disjunction, and acorn nests the walk. * test(javascript): let the runtime decide how deep the corpus may nest acorn records `~Not enough stack space` for its deeply nested case, and the comparison allowed for the two parsers reaching that depth a few frames apart. It did not allow for a runtime reaching it on neither side: under Bun both parse the case, so the recorded expectation goes unmet and the verdicts differ from acorn's on V8. Stack depth is the runtime's answer rather than the parser's, so a verdict or a recorded expectation naming it is left alone on either side.
1 parent d38be99 commit ef7223f

10 files changed

Lines changed: 4317 additions & 98 deletions

File tree

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
---
2+
"webpack": patch
3+
---
4+
5+
Read a regular expression repeating a capture group name in linear time.

‎AGENTS.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -105,7 +105,7 @@ The directory listings below are the canonical map of the repository. **Whenever
105105

106106
**Tests** — see [TESTING_DOCS.md](TESTING_DOCS.md) for directory structure, naming, and how to run a single case.
107107

108-
- `test/` — All test suites (`unitCases/`, `cases/`, `configCases/`, `specCases/`, `watchCases/`, `hotCases/`, `statsCases/`, `typesCases/`, `benchmarkCases/`, `memoryLimitCases/`, etc.). `templates/` holds the suite drivers (`TestCases.js`, `ConfigTestCases.js`, `HotTestCases.js`, `WatchTestCases.js`) that the `*.test.js` / `*.basictest.js` / `*.longtest.js` files at the top of `test/` are thin shims over — each exports `describeCases(config)` and resolves case directories against the `test/` root, never against its own. The option sets those shims pass live together in `templates/variants.js`, re-exported as `variants`, so what differs between the suites reads side by side rather than one file at a time — a shim exists per entry because jest parallelizes per file, not per describe. `harness/` holds what runs those suites rather than what they test — jest's own lifecycle (`globalSetup.js`, `globalTeardown.js`, `setupTestFramework.js`), the `patch-node-env.js` environment, the crash reporter, the case `runner/` and `snapshot/` resolver, and `runtimes/` for the preload and setup files that let jest run under Bun and Deno. Reusable assertions and fixtures stay in `helpers/`. `RoundTripConfigCases` re-bundles the output of `configCases` marked with a `roundTrip.js` file. `external/` holds what webpack does not maintain — every git submodule checked out for testing, today the four spec corpora below, so a directory there is upstream's to change and ours only to pin. `external/wpt/` is web-platform-tests, checked out one commit deep by the `html5lib` and `syntax-equivalence` jobs — it is where the HTML tree-construction corpus lives since html5lib-tests dropped it.
108+
- `test/` — All test suites (`unitCases/`, `cases/`, `configCases/`, `specCases/`, `watchCases/`, `hotCases/`, `statsCases/`, `typesCases/`, `benchmarkCases/`, `memoryLimitCases/`, etc.). `templates/` holds the suite drivers (`TestCases.js`, `ConfigTestCases.js`, `HotTestCases.js`, `WatchTestCases.js`) that the `*.test.js` / `*.basictest.js` / `*.longtest.js` files at the top of `test/` are thin shims over — each exports `describeCases(config)` and resolves case directories against the `test/` root, never against its own. The option sets those shims pass live together in `templates/variants.js`, re-exported as `variants`, so what differs between the suites reads side by side rather than one file at a time — a shim exists per entry because jest parallelizes per file, not per describe. `harness/` holds what runs those suites rather than what they test — jest's own lifecycle (`globalSetup.js`, `globalTeardown.js`, `setupTestFramework.js`), the `patch-node-env.js` environment, the crash reporter, the case `runner/` and `snapshot/` resolver, and `runtimes/` for the preload and setup files that let jest run under Bun and Deno. Reusable assertions and fixtures stay in `helpers/`. `RoundTripConfigCases` re-bundles the output of `configCases` marked with a `roundTrip.js` file. `external/` holds what webpack does not maintain — every git submodule checked out for testing, today the four spec corpora below, so a directory there is upstream's to change and ours only to pin. `external/wpt/` is web-platform-tests, checked out one commit deep by the `html5lib` and `syntax-equivalence` jobs — it is where the HTML tree-construction corpus lives since html5lib-tests dropped it. acorn's own test suite is the one upstream corpus that is vendored instead of pinned, as `fixtures/acorn-corpus.json`, because acorn's npm tarball ships no tests. `unitCases/WebpackParser.unittest.js` holds both of webpack's parser entry points to it, and owns the recording of it too — no generator script and no `package.json` entry: it replays acorn's `test/tests*.js` against a driver that records each case instead of running it, and keeps the sources and options, never the expected trees, which it takes from acorn itself. Bumping the `acorn` devDependency is what moves the corpus, and the same file is what refreshes it: clone acorn at the new version into `node_modules/.cache/acorn-<version>` and re-run it with `WEBPACK_UPDATE_ACORN_CORPUS=1`. Where that checkout exists the run checks the vendored corpus against it; where it does not — CI, and every machine that never cloned — the corpus stands on the version it names, which the run pins to the installed acorn.
109109

110110
**Git submodules** — every submodule lives under `test/external/`, checked out on demand: `yarn setup` does not fetch them, and each CI job fetches only the submodules it needs, one commit deep.
111111

‎cspell.json‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@
88
"absolutify",
99
"accesskey",
1010
"acircular",
11+
"acornjs",
1112
"akait",
1213
"amaro",
1314
"amdmodule",

‎lib/javascript/regexp.js‎

Lines changed: 24 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,10 @@ const hasProp = (obj) => {
3434
return false;
3535
};
3636

37+
// Which comparison last marked a disjunction, so that a walk's marks are
38+
// told apart from the previous walk's without clearing them.
39+
let branchWalk = 0;
40+
3741
/**
3842
* Which disjunction branch a named group sits in, so that the same name in two
3943
* alternatives of one disjunction is allowed and a repeat in one is not.
@@ -47,24 +51,38 @@ class BranchID {
4751
this.parent = parent;
4852
/** @type {BranchID} */
4953
this.base = base || this;
54+
// which walk last marked this disjunction, and with which of its branches
55+
this.walk = 0;
56+
/** @type {BranchID | null} */
57+
this.taken = null;
5058
}
5159

5260
/**
61+
* Two branches are separated when some disjunction they both sit under took
62+
* a different alternative for each, so nothing can match both.
5363
* @param {BranchID} alt the other branch
5464
* @returns {boolean} whether the two are alternatives of one disjunction
5565
*/
5666
separatedFrom(alt) {
67+
// A chain holds one branch per disjunction, so marking this one answers
68+
// the comparison in a single walk of the other — acorn nests two (#1445).
69+
const walk = ++branchWalk;
5770
/** @type {BranchID | null} */
5871
let self = this;
5972
while (self) {
60-
/** @type {BranchID | null} */
61-
let other = alt;
62-
while (other) {
63-
if (self.base === other.base && self !== other) return true;
64-
other = other.parent;
65-
}
73+
self.base.walk = walk;
74+
self.base.taken = self;
6675
self = self.parent;
6776
}
77+
/** @type {BranchID | null} */
78+
let other = alt;
79+
while (other) {
80+
const disjunction = /** @type {BranchID} */ (other.base);
81+
if (disjunction.walk === walk && disjunction.taken !== other) {
82+
return true;
83+
}
84+
other = other.parent;
85+
}
6886
return false;
6987
}
7088

0 commit comments

Comments
 (0)