Skip to content

Commit d90540e

Browse files
feat(javascript): hold a syntax tree as a struct of arrays (#22608)
* refactor(javascript): hold a syntax tree as a struct of arrays The first step of moving webpack's JavaScript parser to a struct-of-arrays tree. `JavascriptNodeStore` holds the 73 node types the parser makes: a node is an integer ref, its type, offsets and flags live in typed-array columns, and child lists in one flat span array. `toEstreeObject(ref)` builds the ESTree object a consumer reads, the same object each time; `toEstreeObject(ref, fields)` builds only the fields listed, and a later call adds the rest to that object. Nothing uses the store yet. Every tree parsed from test262, the swc, oxc and terser corpora and five libraries, under the options a build and the minifier parse with, rebuilds identically: 329,224 of 329,228 trees. The other four are swc's deliberately overflowing `1 + 1 + …` chain, which runs out of stack as every recursive consumer of that tree does. Claude-Session: https://claude.ai/code/session_01Tgxgyb4N35ndP6cC4KcrXC * refactor(javascript): move the syntax tree into the parser Drop `JavascriptNodeStore`: the parser's `SyntaxTree` holds the columns, `javascript.syntax.toEstreeObject(tree, node, fields?)` builds ESTree objects from it, and the node field table is generated into `data.js`. Nodes count from 1, with `0` as no node, as in the CSS and HTML trees. Claude-Session: https://claude.ai/code/session_01Tgxgyb4N35ndP6cC4KcrXC * fix(javascript): build a deep syntax tree's objects without recursing `toEstreeObject` recursed once per nested node, so a tree deeper than the call stack threw a `RangeError`. It now builds children from a work stack. Claude-Session: https://claude.ai/code/session_01Tgxgyb4N35ndP6cC4KcrXC
1 parent 5928218 commit d90540e

8 files changed

Lines changed: 1035 additions & 21 deletions

File tree

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
---
2+
"webpack": minor
3+
---
4+
5+
Add `javascript.syntax.toEstreeObject` to build ESTree nodes from a syntax tree.

‎docs/syntax.md‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -102,7 +102,7 @@ Conventions every language keeps, and a new member follows:
102102

103103
- `lib/css/data.js` — every table the CSS minifier looks names up in, plus the arithmetic its math-function descriptors bind to: from `mdn-data` + `color-name` (box shorthands, color-argument and math functions, named colors) and the generator's `SUPPLEMENT` of spec-prose tables and math primitives, by `tooling/generate-css-data.js` — which also holds the value-definition-syntax parser those grammars are read with, and runs generation only as the entry point so its tests can require it.
104104
- `lib/html/data.js` — every table the HTML parser and minifier look names up in: reflected-attribute tables from webref's HTML IDL (`@webref/idl`, `@webref/elements`) plus the generator's `SUPPLEMENT` and `PARSER_TABLES` of §13.2 tree-construction vocabulary, by `tooling/generate-html-data.js` — which also emits the `// #region html entities` block in `lib/html/syntax-parser.js` from the vendored `tooling/html-entities.json` (WHATWG's named character references).
105-
- `lib/javascript/data.js` — the JS parser's and printer's Unicode tables: run-length identifier ranges the tokenizer decodes at its first non-ASCII code point, and per-edition `\p{...}` property names (reached only for a pattern the engine rejected), which `tooling/generate-js-data.js` reads from the pinned acorn devDependency — bumping it moves them; plus the Unicode 8.0 identifier ranges the printer writes unescaped (so older engines read its output), read from terser's own frozen tables.
105+
- `lib/javascript/data.js` — the JS parser's and printer's Unicode tables: run-length identifier ranges the tokenizer decodes at its first non-ASCII code point, and per-edition `\p{...}` property names (reached only for a pattern the engine rejected), which `tooling/generate-js-data.js` reads from the pinned acorn devDependency — bumping it moves them; plus the Unicode 8.0 identifier ranges the printer writes unescaped (so older engines read its output), read from terser's own frozen tables; and `NODE_FIELDS`, each ESTree node type's fields and their slots in a `SyntaxTree`, typed out in the generator.
106106
- `lib/javascript/syntax-printer-data.js` — the tables only the printer reads, in their own module so a build that parses without minifying through the printer never loads them: the native-object tables of pure globals, calls, methods and static properties the compressor reads (`NATIVE_*`, built only when `nativeObjectTables()` is called, so loading the module allocates none), each name with its `unsafe` / `builtins_ecma >= N` conditions in terser's order, parsed with acorn out of terser's `lib/compress/native-objects.js`. Plus the keyword, reserved-word and operator-precedence tables the printer names tokens by (`parserTables()`), parsed out of terser's `lib/parse.js`, and the DOM property names property mangling keeps (`domProperties()`), out of its `tools/domprops.js`. Plus the built-ins `improve` evaluates on literals (`foldedBuiltIns()`): `tooling/generate-js-data.js` places every member `@mdn/browser-compat-data` lists of `Math`, `Number`, `String`, `Array` and the global functions in `FOLDED_BUILT_INS`, `FOLDED_CONSTANTS` or, with the reason, `UNFOLDED_BUILT_INS`, and fails when a bump lists one in neither, or a folded one is missing, misplaced, or newer in Node than `engines.node` (folding it would tie the output to the build's Node). Plus the constructors `improve` calls without `new`, `CONSTRUCTED_WHEN_CALLED`, each one the spec has construct the same when called. Plus the built-ins `improve` drops (`pureBuiltIns()`): every global and standard static member BCD dates to `engines.node`, less the ones `IMPURE_BUILT_INS` and `UNREAD_BUILT_INS` name with the reason (`eval`, a promise combinator that may reject, `Intl`, …); a call is dropped only where running it at build time on its literal arguments does not throw.
107107

108108
## CSS
@@ -115,7 +115,7 @@ Conventions every language keeps, and a new member follows:
115115

116116
## JavaScript
117117

118-
- `syntax.js` reaches `parser` and `printer` through getters: parsing never loads the printer, and the printer loads the parser for its `parse` phase, which reads an asset with it — building the printer's tree as each statement finishes, rather than converting a tree. It is the only parser: a source it refuses is refused, and terser's parse options for what is not a program (`parse.expression`, `parse.strict`, `parse.experimental_typescript`) are refused too.
118+
- `syntax.js` reaches `parser` and `printer` through getters: parsing never loads the printer, and the printer loads the parser for its `parse` phase, which reads an asset with it — building the printer's tree as each statement finishes, rather than converting a tree. It is the only parser: a source it refuses is refused, and terser's parse options for what is not a program (`parse.expression`, `parse.strict`, `parse.experimental_typescript`) are refused too. `toEstreeObject(tree, node, fields?)` builds a `SyntaxTree` node's ESTree object, each call returning the same object: every field, or only those listed and the rest on a later call. It bridges hooks and plugins while the parser moves to that struct-of-arrays tree.
119119
- `syntax-parser.js` — tokenizer, acorn-derived core and every production in one file (any parse reaches the productions, and the coming struct-of-arrays rewrite moves node creation through them). `regexp.js` (pattern validator) is the one on-demand piece, reached only for a pattern the host engine rejected — never `require` it from a build path.
120120
- `syntax-printer.js` — webpack's JavaScript minifier, terser's design ported to write byte for byte what terser writes; `jsMinify.js` is the `minify` the default minimizer dispatches JS to under `experiments.futureDefaults`, and goes through it alone; without that flag the minimizer dispatches to `terserMinify` as `minimizer-webpack-plugin` publishes it, running the user's own terser since webpack lists it only as a devDependency. Neither needs an option to say which, and the printer itself never loads terser. `createModules` builds what terser's modules exported — the node factories (`createAst`), the parser's tables (`createParseTables`), the compressor and the output stream — and each entry of `PHASES` installs one part onto them: add phases there and nowhere else. A node is a plain object without methods, made by a factory `createAst` compiles from `NODE_KINDS` with its fields; its prototype is its kind's, holding its ESTree `type`, the values ESTree fixes for the kind (`prefix`, a name's `role`, a declaration's `kind`), the kind itself, which `ast.kindOf` reads, and its kind bits. A kind's prototype sits below a frozen prototype per terser class, chained as `NODE_KIND_ANCESTRY` gives each kind's classes, and `createAst` names a predicate per class, `is<Class>` (`isLambdaNode`), a bound `isPrototypeOf` of that class's prototype: the phases ask a node what it is through these, never `instanceof`. There are no node methods: every operation terser defined per class (`optimize`, `evaluate`, `has_side_effects`, `drop_side_effect_free`, `size`, scope analysis, …) is a function on `ast` dispatching on `node.type` through a table, a type absent reading the default, and walkers, transformers and the compressor are plain objects (`createWalker`, `createTransformer`, `createCompressor`), with `ast.walkNode` and `ast.transformNode` visiting children by type. A `pure_funcs` function is still handed a call under terser's field names (`args`, `expression`, `print_to_string`) through a read-only view. The parser's ESTree is adopted as the tree (`ast.adoptEstree`, which a `parse.spidermonkey` input goes through too), and `ast.toEstree` writes the SpiderMonkey JSON `format.spidermonkey` hands back, as terser's `to_mozilla_ast` did. `correct` wraps the methods with which terser writes a wrong program and changes only that output; `corrections.enabled` switches it off. `improve` writes less where terser's longer program provably runs the same — after compressing, a statement calling a function in place with nothing passed runs its body there, and a call of an exactly specified built-in on literals (`"abc".charAt(1)`, `Math.max(1, 2)`, `parseInt("ff", 16)`, `100 .toString(16)`, `[1].concat([2])`) is replaced by its value, an array without holes as an array literal, and a `Number` constant by its number where shorter, and an expression nobody reads that only reads a built-in global (`JSON`, `Math.PI`, `Object.prototype.toString`), calls one on literals without throwing (`new Set`, `Object.keys([])`, `new RegExp("a", "i")`) or reads a global a `typeof` proved declared (`typeof x != "undefined" && x`) is dropped, and a shorter spelling of the same is written: `Array` and `Object` constructed as literals (`new Array(1, 2)` as `[1,2]`), `new` dropped where the call constructs the same (`Error`, `Function`, `RegExp` passed no regular expression, …, by `CONSTRUCTED_WHEN_CALLED`), a spread array literal passed as its elements, `typeof x == "undefined"` as `typeof x > "u"`, a `+` beside a number literal in arithmetic dropped, `!(a == b)` as `a != b`, `!!` of a boolean dropped and `Boolean(x)` as `!!x`, `??` after a value never `null` or `undefined` dropped, an integer tested against zero as the integer, `===` between numbers as `==`, an array literal or a bigint concatenated as the string it makes, a string literal's character (`"abc"[1]`), `+[]`, `Number`, `String` and `BigInt` of a literal and `toString` of a boolean or a string as their value, `c ? a = x : a = y` as `a = c ? x : y` (a name no `with` reaches, an undeclared one in sloppy code only, a property of `this` where it is bound or of a name nothing reassigns), `(a = b) === null || a === void 0` as `null == (a = b)`, from ECMAScript 2020 `a == null ? void 0 : a.b` as `a?.b` (and `null == (a = b) ? void 0 : a.c` as `(a = b)?.c`), and from ECMAScript 2021 `a || (a = b)` as `a ||= b` (a name or a property of a name assigned, `&&` and `??` alike) and `a = a || b` as `a ||= b` (a `var`, `let` or parameter, which writing back to itself shows nothing), and `const` as `let` where nothing writes the name, below the top level and where no `eval` or `with` reaches (once names are mangled, so the letters mangling counts stay terser's); `drop_unused` also drops from a declared or parameter pattern the names nothing reads (an array's as holes but for the last, an object's where no rest follows and no getter could run: under `pure_getters`, or reading a literal), a declaration whose object pattern then names nothing and reads a literal (an array pattern still looks up its value's iterator), and from ECMAScript 2019 a `catch` binding nothing reads — taking built-ins as present and as the language defines them, as oxc and swc do — and `improvements.enabled` switches it off. The `parse` phase builds the tree from `syntax-parser.js`; `syntax-printer-estree.unittest.js` holds the adopted tree to terser's own conversion, and `PARSED_DIFFERENTLY` in `syntax-printer.unittest.js` lists where the tree it builds prints otherwise than terser's. `test/specCases/minify-corpora.spectest.js` holds the whole printer to terser's output, a refusal matching any refusal, over each corpus in its `CORPORA` list (add a new one there) under the option sets in `OPTION_SETS`, and runs each output whose test states what its input prints (terser's `expect_stdout`, swc's `expected.stdout` and `exec.rs`) in terser's sandbox. A byte difference is accepted only where switching the `correct` and `improve` phases off gives terser's bytes back, and fails where `improve` writes more than without it, unless the program is shorter and only `const` written as `let` makes it gzip bigger (`improvements.lets.enabled` switches that one off to tell); what it fixes is listed in `CORRECTED` (printing right with the phase, as terser without), and an output misprinting as terser's by an option's own contract in `INHERITED`, each with the reason — an entry that stops matching fails until retired. Where the reference instead refuses a source the spec allows, the parse error it answers with is listed in `REFUSED_BY_REFERENCE` with what makes the source legal; where webpack refuses a source the reference reads, the source is listed in `REFUSED_BY_WEBPACK` with the rule it breaks (a test262 test expecting a parse error needs no entry); where it reads or prints one differently, the case is listed in `REFERENCE_MISPRINTS` with what it gets wrong — a listed one webpack must still run correctly, and one the reference stops differing on fails until retired. Each output is also sized against swc's recorded one, a fixture's `output.js` or, for one of terser's cases, what swc's port of it records (gzip decides, raw breaks a tie): one bigger fails unless `test/helpers/swcSmaller.js` lists it under what swc does that webpack does not yet, and a listed one no longer bigger fails until retired. Under the default minimizer's options each source of every corpus but test262 is also minified by `oxc-minify`, held the same way to `test/helpers/oxcSmaller.js`; an oxc output that misprints is no lead. `JS_MINIFY_REPORT=<file>` tallies where webpack's is worse, the same and better. terser's corpus submodule is pinned to the `terser` devDependency — bump both together, and regenerate `data.js`.
121121
- Printing and mangling read the compressed tree as it is held, by its ESTree types: no conversion step stands between the compressor and the printer, so a tree a caller passes in or `format.ast` hands back is printed and mangled as it is. Where the compressor holds a shape of its own the printer reads it directly — a template's `segments`, two side by side printing as one text; an import's `imported_name` and `imported_names`, an export's `exported_definition`, `exported_value` and `exported_names`, attributes as the object holding them; `import()`'s `args`; a key's or a property read's name as a symbol node; a literal's `role` for a regular expression or a bigint's digits — and a name prints as its `definition` names it (`mangled_name`, else the definition's own name), terser's or the mangler's alike, never renamed in place. Where nobody keeps the tree, `analyzeManglingScopes` and `printProgram` drop what only the compressor read (`COMPRESSOR_ONLY_FIELDS`) off each node they read; every field written is one its kind's factory made. The `estreeMangle` phase mangles that tree as terser's mangler did: `analyzeManglingScopes` resolves its scopes, writing each name's `definition`, `computeEstreeCharFrequency` orders the identifiers, `mangleManglingScopes` gives the definitions their `mangled_name` and `renameMangledEstree` renames `#private` names and properties in one walk, skipped where there are neither. `printEstree` (the `estreePrint` phase) dispatches on `node.type` through three tables — `codegen` (the text), `needsParens` and `sourceMapping` — and asks about a parent through the `kindOf` predicates, never `instanceof`; the stream (`MinifiedOutput`) reads comments through `NodeAccess`. Everything that prints goes through it: `minify`, the mangler's character frequency and the compressor's `printToString`.

0 commit comments

Comments
 (0)