Skip to content

Commit 902123d

Browse files
test(js): compare the parser's tree with acorn's over all of test262 (#21996)
* test(js): compare the parser's tree with acorn's over all of test262 The rewritten parser is an acorn subclass that reimplements most of the tokenizer and much of the parser, so its contract is that the tree it builds is acorn's. Nothing checked that wholesale: this parses each of the 53k test262 files with both, in each of the option sets a caller can ask for, and reports the first node that differs. Its own job runs it without coverage, which makes the parser about five times slower. * test(js): bound the parity job and drop its per-node key allocation The comparison walked every node through a fresh Set and a sorted array; the longer key list already covers both sides. Bound the CI job so a stall cannot hold a runner for the six hour default.
1 parent 9cb49ef commit 902123d

3 files changed

Lines changed: 320 additions & 0 deletions

File tree

‎.github/workflows/test.yml‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -221,6 +221,44 @@ jobs:
221221
env:
222222
CODECOV_TOKEN: ${{ secrets.CODECOV_TOKEN }}
223223

224+
# Parses all of test262 with webpack's parser and with acorn, and compares the
225+
# trees. Coverage instrumentation makes the parser ~5x slower, so this one job
226+
# runs without it — every line it reaches is covered by the suites that upload.
227+
test262-parser:
228+
needs: basic
229+
runs-on: ubuntu-latest
230+
# Bounded: the suite allows ten minutes per area per mode, so a stall
231+
# would otherwise hold a runner for the 6h default.
232+
timeout-minutes: 60
233+
steps:
234+
- uses: actions/checkout@3d3c42e5aac5ba805825da76410c181273ba90b1 # v7.0.1
235+
236+
- name: Check out the test262 corpus
237+
run: git submodule update --init --depth 1 test/test262-cases
238+
239+
- name: Use Node.js
240+
uses: actions/setup-node@820762786026740c76f36085b0efc47a31fe5020 # v7.0.0
241+
with:
242+
node-version: lts/*
243+
cache: yarn
244+
245+
- run: yarn --frozen-lockfile
246+
247+
- run: yarn link --frozen-lockfile || true
248+
249+
- run: yarn link webpack --frozen-lockfile
250+
251+
- name: Cache jest result
252+
uses: actions/cache@55cc8345863c7cc4c66a329aec7e433d2d1c52a9 # v6.1.0
253+
with:
254+
path: .jest-cache
255+
key: jest-test262-parser-${{ runner.os }}-${{ hashFiles('**/yarn.lock', '**/jest.config.js') }}-${{ github.sha }}
256+
restore-keys: |
257+
jest-test262-parser-${{ runner.os }}-${{ hashFiles('**/yarn.lock', '**/jest.config.js') }}-
258+
jest-test262-parser-${{ runner.os }}-
259+
260+
- run: yarn test:test262-parser --ci --cacheDirectory .jest-cache
261+
224262
html5lib:
225263
needs: basic
226264
runs-on: ubuntu-latest

‎package.json‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,6 +67,7 @@
6767
"test:integration:a": "yarn test:base --testMatch \"<rootDir>/test/*.{basictest,test}.js\"",
6868
"test:integration:b": "yarn test:base --testMatch \"<rootDir>/test/*.longtest.js\"",
6969
"test:test262": "yarn test:base --testMatch \"<rootDir>/test/test262.spectest.js\"",
70+
"test:test262-parser": "yarn test:base --testMatch \"<rootDir>/test/test262-parser.spectest.js\"",
7071
"test:html5lib": "yarn test:base --testMatch \"<rootDir>/test/html5lib.spectest.js\"",
7172
"test:syntax-equivalence": "yarn test:base --testMatch \"<rootDir>/test/syntaxEquivalence.spectest.js\"",
7273
"test:css-parsing": "yarn test:base --testMatch \"<rootDir>/test/cssParsing-webpack.spectest.js\"",

‎test/test262-parser.spectest.js‎

Lines changed: 281 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,281 @@
1+
"use strict";
2+
3+
const fs = require("fs");
4+
const path = require("path");
5+
const acorn = require("acorn");
6+
const JavascriptParser = require("../lib/javascript/JavascriptParser");
7+
8+
/** @typedef {{ file: string, at: string, ours: string, acorn: string }} TreeDifference */
9+
/** @typedef {{ file: string, parsedBy: string, message: string }} VerdictDifference */
10+
/** @typedef {{ ranges?: boolean, locations?: boolean, comments?: boolean }} Mode */
11+
/** @typedef {import("acorn").Program} Program */
12+
/** @typedef {import("acorn").Comment} Comment */
13+
/** @typedef {import("../lib/javascript/JavascriptParser").ParseResult} ParseResult */
14+
15+
const corpusDir = path.resolve(__dirname, "./test262-cases/test");
16+
const hasCorpus =
17+
fs.existsSync(corpusDir) && fs.readdirSync(corpusDir).length > 0;
18+
19+
// Every area is parsed twice per mode, and coverage instrumentation makes the
20+
// parser several times slower, so jest's default 30s is far too tight.
21+
const AREA_TIMEOUT = 600000;
22+
// Enough of a regression to see its shape without flooding the log.
23+
const MAX_REPORTED = 10;
24+
25+
// The option sets a caller can hand `JavascriptParser._parse`. `ranges` is the
26+
// one webpack itself uses: it switches on the lazy-node path.
27+
/** @type {[string, Mode][]} */
28+
const MODES = [
29+
["without ranges or comments", {}],
30+
["with ranges and comments", { ranges: true, comments: true }],
31+
["with locations", { locations: true }]
32+
];
33+
34+
/**
35+
* The `sourceType` a test262 file is written for, which its `flags` declare.
36+
* @param {string} code the file's source
37+
* @returns {"module" | "script"} the goal symbol to parse it as
38+
*/
39+
const sourceTypeOf = (code) => {
40+
const meta = /\/\*---([\s\S]*?)---\*\//.exec(code);
41+
if (!meta) return "script";
42+
const flags = /flags:\s*\[([^\]]*)\]/.exec(meta[1]);
43+
if (!flags) return "script";
44+
return flags[1].split(",").some((flag) => flag.trim() === "module")
45+
? "module"
46+
: "script";
47+
};
48+
49+
/**
50+
* A value as it reads in a difference report, kept short enough to scan.
51+
* @param {unknown} value either parser's value at the differing path
52+
* @returns {string} how the value prints
53+
*/
54+
const show = (value) => {
55+
if (typeof value === "bigint") return `${value}n`;
56+
if (value instanceof RegExp) return String(value);
57+
if (typeof value === "object" && value !== null) {
58+
return Array.isArray(value)
59+
? `[${value.length} items]`
60+
: `{${Object.keys(value).sort().join(",")}}`;
61+
}
62+
return JSON.stringify(value) || String(value);
63+
};
64+
65+
/**
66+
* The first place two parse trees disagree, or null when they match. Key
67+
* presence is asked with `in`, since the lazy path serves `range` from a
68+
* prototype getter rather than an own property.
69+
* @param {unknown} ours what webpack's parser built
70+
* @param {unknown} theirs what acorn built
71+
* @param {string} at the path walked so far
72+
* @returns {{ at: string, ours: string, acorn: string } | null} the difference
73+
*/
74+
const firstDifference = (ours, theirs, at) => {
75+
if (ours === theirs) return null;
76+
const report = { at, ours: show(ours), acorn: show(theirs) };
77+
if (typeof ours !== typeof theirs) return report;
78+
if (typeof ours === "number") {
79+
return Number.isNaN(ours) && Number.isNaN(/** @type {number} */ (theirs))
80+
? null
81+
: report;
82+
}
83+
if (typeof ours === "bigint") {
84+
return String(ours) === String(theirs) ? null : report;
85+
}
86+
if (typeof ours !== "object" || ours === null || theirs === null) {
87+
return report;
88+
}
89+
if (ours instanceof RegExp || theirs instanceof RegExp) {
90+
return String(ours) === String(theirs) ? null : report;
91+
}
92+
if (Array.isArray(ours) !== Array.isArray(theirs)) return report;
93+
if (Array.isArray(ours)) {
94+
const other = /** @type {unknown[]} */ (theirs);
95+
if (ours.length !== other.length) return report;
96+
for (let i = 0; i < ours.length; i++) {
97+
const difference = firstDifference(ours[i], other[i], `${at}[${i}]`);
98+
if (difference) return difference;
99+
}
100+
return null;
101+
}
102+
const left = /** @type {Record<string, unknown>} */ (ours);
103+
const right = /** @type {Record<string, unknown>} */ (theirs);
104+
const ourKeys = Object.keys(left);
105+
const theirKeys = Object.keys(right);
106+
// Whichever side owns more keys covers the other: two same-sized key sets
107+
// that differ must each hold a key the other lacks.
108+
for (const key of ourKeys.length >= theirKeys.length ? ourKeys : theirKeys) {
109+
if (!(key in left)) {
110+
return { at: `${at}.${key}`, ours: "absent", acorn: show(right[key]) };
111+
}
112+
if (!(key in right)) {
113+
return { at: `${at}.${key}`, ours: show(left[key]), acorn: "absent" };
114+
}
115+
const difference = firstDifference(left[key], right[key], `${at}.${key}`);
116+
if (difference) return difference;
117+
}
118+
return null;
119+
};
120+
121+
/**
122+
* Whether acorn only got through the file because the host engine cannot build
123+
* one of its regexp literals, which acorn records as a null value and webpack
124+
* (validating with `new RegExp`) reports as a parse error instead.
125+
* @param {Error} error what webpack's parser threw
126+
* @param {Program} ast the program acorn built
127+
* @returns {boolean} true when the engine, not the pattern, is the difference
128+
*/
129+
const isHostRegExpLimit = (error, ast) => {
130+
if (!error.message.startsWith("Invalid regular expression:")) {
131+
return false;
132+
}
133+
/** @type {unknown[]} */
134+
const queue = [ast];
135+
while (queue.length > 0) {
136+
const node = queue.pop();
137+
if (typeof node !== "object" || node === null) continue;
138+
const record = /** @type {Record<string, unknown>} */ (node);
139+
if (record.regex !== undefined && record.value === null) return true;
140+
for (const key of Object.keys(record)) queue.push(record[key]);
141+
}
142+
return false;
143+
};
144+
145+
/**
146+
* Parse one file with both parsers and record how they disagreed.
147+
* @param {string} file absolute path of the test262 file
148+
* @param {Mode} mode the options both parsers are given
149+
* @param {TreeDifference[]} trees where tree differences are collected
150+
* @param {VerdictDifference[]} verdicts where accept/reject differences are collected
151+
* @returns {void}
152+
*/
153+
const compareFile = (file, mode, trees, verdicts) => {
154+
const code = fs.readFileSync(file, "utf8");
155+
const sourceType = sourceTypeOf(code);
156+
const name = path.relative(corpusDir, file);
157+
const options = {
158+
sourceType,
159+
ecmaVersion: /** @type {const} */ ("latest"),
160+
allowHashBang: true,
161+
...mode
162+
};
163+
164+
/** @type {ParseResult | undefined} */
165+
let ours;
166+
/** @type {Error | undefined} */
167+
let ourError;
168+
try {
169+
ours = JavascriptParser._parse(code, { ...options });
170+
} catch (err) {
171+
ourError = /** @type {Error} */ (err);
172+
}
173+
174+
/** @type {Comment[]} */
175+
const comments = [];
176+
/** @type {Program | undefined} */
177+
let theirs;
178+
/** @type {Error | undefined} */
179+
let theirError;
180+
try {
181+
theirs = acorn.parse(code, {
182+
...options,
183+
// `_parse` sets this from the goal symbol, so acorn has to match
184+
allowReturnOutsideFunction: sourceType === "script",
185+
...(mode.comments === true ? { onComment: comments } : {})
186+
});
187+
} catch (err) {
188+
theirError = /** @type {Error} */ (err);
189+
}
190+
191+
if (ourError !== undefined || theirError !== undefined) {
192+
if (ourError !== undefined && theirError !== undefined) return;
193+
if (
194+
ourError !== undefined &&
195+
theirs !== undefined &&
196+
isHostRegExpLimit(ourError, theirs)
197+
) {
198+
return;
199+
}
200+
verdicts.push({
201+
file: name,
202+
parsedBy: ourError === undefined ? "webpack" : "acorn",
203+
message: /** @type {Error} */ (ourError || theirError).message
204+
});
205+
return;
206+
}
207+
208+
const tree = firstDifference(
209+
/** @type {ParseResult} */ (ours).ast,
210+
theirs,
211+
"program"
212+
);
213+
if (tree) trees.push({ file: name, ...tree });
214+
if (mode.comments !== true) return;
215+
const commentDifference = firstDifference(
216+
/** @type {ParseResult} */ (ours).comments,
217+
comments,
218+
"comments"
219+
);
220+
if (commentDifference) trees.push({ file: name, ...commentDifference });
221+
};
222+
223+
/**
224+
* The first few differences, with a count when more were found.
225+
* @template T
226+
* @param {T[]} differences everything the run collected
227+
* @returns {(T | string)[]} what the assertion prints
228+
*/
229+
const reportable = (differences) =>
230+
differences.length > MAX_REPORTED
231+
? [
232+
...differences.slice(0, MAX_REPORTED),
233+
`…and ${differences.length - MAX_REPORTED} more`
234+
]
235+
: differences;
236+
237+
const areas = hasCorpus
238+
? fs
239+
.readdirSync(corpusDir, { withFileTypes: true })
240+
.filter((entry) => entry.isDirectory())
241+
.map((entry) => entry.name)
242+
.sort()
243+
: [];
244+
245+
describe("test262 parser parity", () => {
246+
if (!hasCorpus) {
247+
it("submodule not initialized (run `git submodule update --init --depth 1 test/test262-cases`)", () => {
248+
// No-op: the conformance corpus is an optional git submodule.
249+
});
250+
251+
return;
252+
}
253+
254+
for (const area of areas) {
255+
describe(area, () => {
256+
const files = fs
257+
.globSync(`${corpusDir}/${area}/**/*.js`)
258+
.filter((file) => !/_FIXTURE\.js$/i.test(file))
259+
.sort();
260+
261+
for (const [modeName, mode] of MODES) {
262+
it(
263+
`builds acorn's tree ${modeName}`,
264+
() => {
265+
/** @type {TreeDifference[]} */
266+
const trees = [];
267+
/** @type {VerdictDifference[]} */
268+
const verdicts = [];
269+
for (const file of files) {
270+
compareFile(file, mode, trees, verdicts);
271+
}
272+
expect(files.length).toBeGreaterThan(0);
273+
expect(reportable(trees)).toEqual([]);
274+
expect(reportable(verdicts)).toEqual([]);
275+
},
276+
AREA_TIMEOUT
277+
);
278+
}
279+
});
280+
}
281+
});

0 commit comments

Comments
 (0)