Build Tool Truths: Benchmarks from a Handwritten Mini Bundler
Build Tools
1. Technical Difficulties
Previous 34 articles have been measuring things in the browser: rendering pipeline, loading, network, SSR, runtime, bundle, images/fonts, Worker, WASM, performance monitoring. This one goes back to the upstream of all that — how artifacts are produced.
Build tools are the most "black box" layer in frontend engineering. They run hundreds of times a day, but most people's understanding of them stops at three phrases: vite build, tree-shaking, and "the hash changed, need to re-upload". When builds get slow, artifacts come out weird, or caches mysteriously invalidate, the only response is guessing.
So I built a mini bundler from scratch with zero third-party dependencies: scan.mjs (tokenizer + module syntax scanner), build.mjs (module graph + tree-shaking + scope-hoisting linking + chunking + content hashing), plus test-bundler.mjs (33 assertions all green, with 5 groups doing differential comparison against native ESM on real disk) and bench.mjs (13 measured groups). Environment: Node 22.23.3 / darwin-arm64 / V8 12.4.
I'll lay out the conclusions first. Each line below is measured on this machine, not derived:
| Common belief | Measured result | Where it differs |
|---|---|---|
"Scanning dependencies is just finding import with regex" |
3 disguised samples (multi-line template / block comment / regex literal each hiding a fake import) 3/3 all false-positive as real edges; but it is 43.7x faster than the real tokenizer (0.35ms vs 15.22ms / 500 modules) | Fast is real, wrong is also real. Wrong dependency edges = over-bundling or under-bundling, and only explode at runtime |
| "Tree-shaking is just deleting unused exports" | Same 300-module source, with entry reference ratios 10%/30%/60%/100%, artifact reduction 96.5% / 88.8% / 78.2% / 64.6% | The reduction is almost entirely decided by "how many modules never enter the graph" (270/301 never enter), not by how smart the shaking algorithm is |
| "Finner chunking = higher cache hit rate" | Change one line of live code: single chunk invalidates 100%; shared two chunks 61.1%; per-module 141 chunks only invalidate 89B = 0.4% | But per-module is 141 requests. Trade size for request count. No free lunch |
| "Including dependencies in chunk hash is safer" | Change 1 leaf module: hash only self invalidates 89B (0.4%); chained hash invalidates 18.6KB (91.8%), affecting 124 chunks | Blast radius amplified 214.40x. What is safe is "never serve stale artifacts", not "cache is efficient" |
| "Slow build? Rewrite in another language" | Full pipeline 114.9ms: graph building (incl. parsing) 58.5%, tree-shaking 14.8%, linking 18.2%, hashing 8.4%; pure lexing alone is 31.5% | Measure first. My linking stage originally was O(statements × tokens), after single-pass it went 65.9ms → 21.1ms (3.13x), cheaper than switching languages |
| "Writing my own hash is faster than sha256" | BigInt FNV-1a 16.26 MB/s; Math.imul dual-channel 344.38 MB/s; native sha256 478.39 MB/s |
Hand-written BigInt hash is 29.4x slower than native sha256. "JS must be slower than C" is wrong here |
1.1 Difficulty One: Scanning is not "finding strings", it's "avoiding treating strings as real edges"
The real difficulty isn't finding import, but knowing what context you're in before you find it. The same four letters import have completely different semantics inside a string, a comment, a regex literal, or a template interpolation:
const tricky = [
'const t = `\nimport x from "./fake-tpl.mjs"\n`;',
'/*\nimport y from "./fake-block.mjs"\n*/',
'const re = /\nimport z from "\\/fake-re.mjs"\n/;',
];
More subtle is the ambiguity of /: if (a) /re/.test(b) is a regex, (a + b) / 2 / c is division, both have the same token sequence length before them. The industry solution is to maintain a "control-statement bracket stack": ( after if/while/for/with/switch/catch is marked ctrl, and the matching )allows a regex; normal(pairs yield)` that expects division. That one detail is 30 lines of code; missing it, the tokenizer will start slicing the whole file wrong from some point.
1.2 Difficulty Two: Renaming is not string replacement, it's "scope + context"
When a bundler does scope hoisting, it renames each module's top-level bindings to globally unique names (that's what Rollup does). Lexical-level renaming seems to work, but there are two mandatory pitfalls:
Pit A: Template interpolation. `${name}` inside a template is a reference and must be renamed; but it sits in the nested parts of a tpl token, invisible to a flat token-stream traversal. Measured: of 400 modules, 197 use template interpolation; missing recursion makes the entire output throw ReferenceError (0/400 pass). A 40-line function-level oversight explodes across 197 modules simultaneously, and only at runtime—the build is all green.
Pit B: Rename-position determination. The same identifier token appears in obj.name (property, must not rename), { name: 1 } (key, must not rename), { name } (shorthand property, must rename to name: mN$name), and return name (reference, must rename). Each requires a different treatment.
1.3 Difficulty Three: The correctness boundary of tree-shaking
The hard part is "when cannot you delete":
- Top-level side effects: if a module has
globalThis.x = 1, the whole module cannot be dropped. - Fake-live import statements: if import statements participate in the "live statement" set, then all
import {a, b, c}in the entry will mark a/b/c as live—my first version did that, and the output kept all 3 exports when only 1 was actually used. - Default export naming:
export default function fmt(){}has exported namedefaultand local namefmt. Using the exported name for liveness analysis makes named default exports never shakeable. - Re-export edges:
export { x } from './y.mjs'is also a dependency edge. Miss it,./y.mjsnever enters the graph, and the output references a nonexistent name.
1.4 Difficulty Four: Chunking, hashing, and "blast radius"
Caching is not about whether a hash exists, but how many bytes are invalidated by one change. That depends on two independent choices: chunk granularity (in §2's table, 100% → 0.4%) and whether the hash is chained on dependencies (0.4% → 91.8%). Many people tune only the former, then stay stuck in "why did a change to utils break the whole site's cache"—that's the latter's fault.
1.5 Difficulty Five: Determinism
Same repo, same source, two builds must produce byte-identical results (otherwise the CDN gets artifacts with the same content but different filenames, and cache hit rate drops to zero). This can't be guaranteed by "being careful"; it needs a fixed traversal order: this implementation uses a post-order DFS (topoOrder) where dependencies come before dependents, plus Tarjan cycle detection. The counterexample is direct: using file enumeration order instead, shuffling 5 times yields 5 different hashes.
1.6 Difficulty Six: Performance, and "the bottleneck you think you have"
bench.mjs §9 breaks down a 3000-module cold start: graph building (incl. parsing) 67.3ms / tree-shaking 17.0ms / linking 20.9ms / hashing 9.71ms, total 114.9ms, of which pure lexing is 36.2ms = 31.5%. This distribution says two things: first, lexing/parsing is the lower bound of the whole pipeline; to get an order-of-magnitude improvement you'd have to switch parsers (esbuild/SWC use Go/Rust to replace that 31.5%); second, my linking stage was originally O(statements × tokens)—for each statement, linearly scan all tokens to mark deletion ranges. At 3000 modules it was 65.9ms; changed to "single token pass + statement pointer advance", it's 21.1ms, 3.13x faster and byte-identical output.
This 3.13x is cheaper than any "rewrite in Rust". Measure first, then switch.
2. Complete Solution
2.1 Tokenizer: Regex ambiguity + template recursion
The core has two states: the parens stack (decides whether a ) can be followed by regex) and parts (nested tokens of template interpolations).
const CONTROL_KW = new Set(['if', 'while', 'for', 'with', 'switch', 'catch']);
const REGEX_PREV_KW = new Set(['return', 'typeof', 'instanceof', 'in', 'of', 'new', 'delete', 'void', 'throw', 'case', 'do', 'else', 'yield', 'await']);
function regexAllowed(prev) {
if (!prev) return true; // file start
if (prev.t === 'num' || prev.t === 'str' || prev.t === 'tpl' || prev.t === 're') return false;
if (prev.t === 'id') return REGEX_PREV_KW.has(prev.v);
if (prev.t === 'punc') {
if (prev.v === ')') return prev.ctrl === true; // ) of if(...) → regex allowed
if (prev.v === ']') return false;
if (prev.v === '++' || prev.v === '--') return false;
return true;
}
return true;
}
The ctrl mark is recorded when hitting (: "is the previous token a control keyword", and when ) is encountered, that flag comes out. Template strings recursively tokenize the expression inside ${...} into parts, and store absolute offsets es/ee—later renaming relies on them to restore positions.
Measured performance: 500 modules / 196.3KB, tokenize 13.28ms (14.43 MB/s), scanModule 15.22ms (12.59 MB/s). The 14 MB/s is low, for a concrete reason—see §2.6.
2.2 Module Syntax Scanner: Statement ranges are the foundation of everything after
The scanner not only answers "what is imported", but also gives character ranges for each statement (statements). Tree-shaking deletes by statement, and linking deletes wrappers by statement:
const stmtEnd = (k, groupAt = -1) => {
let d = 0;
let openedBlock = false;
for (let m = k; m < toks.length; m++) {
const t = toks[m];
if (t.t !== 'punc') continue;
if (t.v === '(' || t.v === '[') d++;
else if (t.v === ')' || t.v === ']') { d--; if (d < 0) return m; }
else if (t.v === '{') { if (m !== groupAt && d === 0) openedBlock = true; d++; }
else if (t.v === '}') {
d--;
if (d < 0) return m;
if (d === 0 && openedBlock) return m;
} else if (t.v === ';' && d === 0) return m;
}
return toks.length - 1;
};
This 18-line function hit two real pitfalls, both worth adding to any bundler's code-review checklist:
Pit 1: export function f(){} has no semicolon. If you only look for ';', stmtEnd will swallow dozens of following lines until the next semicolon. The test 无分号的 export function 不会吞掉后续语句 guards exactly this.
Pit 2: The braces in a specifier list are not a block. The { a } in import { a } from './x' is at the same bracket depth as a function body. So stmtEnd takes a groupAt parameter: the caller passes in the index of the specifier's {, and that pair of braces doesn't participate in "statement block" detection. Without it, the import statement ends at the }, and from './x' becomes a top-level statement—and gets flagged as a side effect.
2.3 Module Graph: Tarjan for cycles + post-order for ordering
export function topoOrder(modules, entryId) {
const out = [];
const state = new Map(); // 1=in stack 2=done
const walk = (id) => {
if (state.get(id) === 2) return;
if (state.get(id) === 1) return; // cycle: skip, no infinite loop
state.set(id, 1);
for (const d of modules[id].deps) walk(d.targetId);
state.set(id, 2);
out.push(id);
};
walk(entryId);
return out;
}
Cycles are identified separately with Tarjan (returns all strongly connected components with length > 1 plus self-loops). Execution order uses post-order DFS to guarantee "dependencies before dependents"; cycle detection uses Tarjan to guarantee nothing is missed—they're done separately because their correctness conditions differ.
One easily missed point: export { x } from './y.mjs' is also a dependency edge. When building the graph, items in scan.exports that have a source property must also be visited, or the re-exported module never enters the graph, and byPath.get(path) returns undefined.
Measured graph building: 200 / 1000 / 3000 modules = 3.4ms / 16.8ms / 52.3ms, amortized per module 0.017 / 0.017 / 0.017ms, approximately linear.
An unintuitive bonus: with a 3000-module project, there are 3001 files on disk, but only 1201 enter the graph and get parsed. Modules not referenced by the entry don't even get lexed—that's the real reason "the project is large but the build is still fine", and it makes "total source size" a nearly worthless metric.
2.4 Tree-shaking: Two-level liveness analysis
Module-level liveness (statement-level: export declarations + top-level declaration reachability propagation) and module-level liveness (a module is dropped whole if no live statement references it and it has no side effects).
const markUsedExport = (modId, name) => {
const cur = usedExports.get(modId);
if (cur === '*') return false;
const set = cur ?? new Set();
if (set.has(name)) return false;
set.add(name);
usedExports.set(modId, set);
return true;
};
The key is a consistent naming convention: usedExports always stores local binding names (local), not exported names (exported). export default function fmt(){} records fmt; export { hidden as viaList } records hidden. That rule fixed my "named default export never shakes" bug.
Reference propagation uses a fixed point: a statement is live → the local declarations it references become live → recursively. import statements do not participate in this set (they produce no code); they only decide whether to request an export from the target module based on which local names are actually referenced by live statements.
The measured cost of sideEffects determination (§11): same 100-module project, all clean gives a 4.0KB output; adding one top-level side-effect statement to each module gives 10.2KB, amplified 2.55x. That's the real value of "sideEffects": false in package.json—and the reason it can cause production failures if set on a module that actually has side effects.
2.5 Linking: Scope hoisting + renaming (with template recursion)
Renaming tables are built per module: local declarations → m{id}${name}, imported local names → the target's global name. Rendering uses a single token pass:
const rewriteToken = (t, toks, k, renames) => {
if (t.t !== 'id') return t.v;
const prevV = toks[k - 1] ? toks[k - 1].v : undefined;
const nextV = toks[k + 1] ? toks[k + 1].v : undefined;
if (prevV === '.' || prevV === '?.') return t.v; // property access
if (nextV === ':' && (prevV === '{' || prevV === ',')) return t.v; // object key
const target = renames.get(t.v);
if (!target) return t.v;
const prevIsOpen = prevV === '{' || prevV === ',';
const nextIsClose = nextV === '}' || nextV === ',';
if (prevIsOpen && nextIsClose) return `${t.v}: ${target}`; // shorthand property
return target;
};
Template tokens are passed to a recursive renamer, which slices each ${...} segment using parts' absolute offsets:
export function renameSnippet(text, renames) {
if (!renames.size) return text;
const toks = tokenizeSnippet(text);
let out = '';
let prevEnd = 0;
for (let k = 0; k < toks.length; k++) {
const t = toks[k];
out += text.slice(prevEnd, t.s);
if (t.t === 'tpl' && t.parts) {
let rebuilt = '';
let last = t.s;
for (const part of t.parts) {
if (part.expr) {
rebuilt += text.slice(last, part.es) + renameSnippet(text.slice(part.es, part.ee), renames);
last = part.ee;
}
}
rebuilt += text.slice(last, t.e);
out += rebuilt;
} else {
out += rewriteToken(t, toks, k, renames);
}
prevEnd = t.e;
}
out += text.slice(prevEnd);
return out;
}
Namespace imports (import * as ns) generate an object literal that aggregates the target module's exports. There's a pit I actually stepped in: this shim must be attached as the importing module's prelude, not just concatenated at the top of the final code string—otherwise after chunking, chunkCode() reassembles from pieces and it disappears. Single-chunk builds look normal; once multi-chunk, you get Cannot read properties of undefined.
2.6 Performance: Three measured optimizations
① Character classification via charCode, not regex. The tokenizer is only 14 MB/s; this is the hot path:
const isIdPartCode = (c) => {
const x = c.charCodeAt(0);
return (x >= 48 && x <= 57) || (x >= 65 && x <= 90) || (x >= 97 && x <= 122) || x === 95 || x === 36;
};
2 million checks: regex .test() 39.3ms, charCode compare 8.0ms, 4.9x faster. Every character creates a new regex matching context—that's where the 14 MB/s comes from.
② Don't write linking as a double loop. See §1.6: 65.9ms → 21.1ms (3.13x), byte-identical output. The test uses lF.code === lN.code to guard this equivalence—an optimization without an equivalence assertion is a rewrite.
③ Stop hand-rolling BigInt hashes. Three implementations (200KB / 200 chunks):
| Implementation | Time | Throughput |
|---|---|---|
| FNV-1a 64 (BigInt per char) | 12.04ms | 16.26 MB/s |
FNV-1a ×2 32 (Math.imul dual-channel) |
0.57ms | 344.38 MB/s |
| sha256 (native OpenSSL) | 0.41ms | 478.39 MB/s |
The Math.imul version is 21.2x faster than BigInt, but native sha256 is still 1.4x faster than that, and 29.4x faster than BigInt. In production, choosing xxhash is never about "being faster than sha256"; it's about cross-language consistency, incremental hashing, and collision resistance. If you're writing a hash in JS, "my own is faster" is mostly an illusion.
2.7 Tests: 33 assertions + 5 real-ESM differential groups
Unit assertions guard edges but cannot guard semantics. The key technique is differential testing: write the same fixture to a real temp directory, run it with native import(), then run the bundled output, and compare each export.
const native = await import(pathToFileURL(path.join(dir, 'src/main.mjs')).href);
const bundled = new Function('__ex', r.chunks[0].code + '\nreturn __ex;')({});
for (const k of Object.keys(native)) {
const nv = native[k], bv = bundled[k];
if (typeof nv === 'function') {
assert.equal(String(bv()), String(nv()), `export ${k}() result differs`);
continue;
}
assert.deepEqual(bv, nv, `export ${k} differs from native`);
}
5 differential groups cover: a normal project (shadow variables / destructuring / templates / namespace / side effects), a re-export chain (export {} from + export * through two levels), side-effect statement order, a 120-module synthetic project, and four forms of default exports (expression / named class / named function / list renaming).
These 5 groups caught 4 bugs I wrote: references inside template interpolations not visible, named default exports never shaken, re-export edges not in the graph, and the re-export target module not being included. Every one of them keeps the build green but produces wrong output.
Among the remaining assertions, three are the most valuable:
// 1) Determinism: shuffle file-enumeration order, output hash must stay the same
assert.equal(a.chunks[0].hash, b.chunks[0].hash, 'output nondeterministic → caches keep failing in CI');
// 2) Chunk granularity: change one module, per-module invalidates exactly one chunk
assert.equal(changed, 1, `should invalidate 1 chunk, actually ${changed}`);
// 3) A semicolon-less export function must swallow subsequent statements
assert.ok(scanModule("export function f(){}\nexport const K = 1;").exports.some((e) => e.exported === 'K'));
3. Application Scenarios
3.1 First locate "which stage is slow", then choose a tool
Use this article's full-pipeline breakdown as a ruler to map common phenomena:
| Phenomenon | Corresponding stage | Where to act |
|---|---|---|
| Slow cold start, slow HMR but normal output | Graph building (incl. parsing) 58.5%, lexing 31.5% | Switch parser (esbuild/SWC for transform, Vite's default combo); or add scanning cache |
| A one-line change takes seconds | Linking/chunk granularity | Go dev without bundling (Vite's ESM dev server); or chunk-level incremental (Turbopack) |
| Build isn't slow, but users still re-download several MB after each change | Chunking + hash propagation | Tune chunk strategy, split stable vendor, check whether the hash chain includes dependencies |
| Output much larger than expected | Tree-shaking boundary | Check sideEffects config, top-level side-effect statements, export default naming |
| Yesterday's and today's artifacts identical but hash changed | Determinism | Check whether traversal order depends on readdir/Object.keys/timestamps |
3.2 "How fine to split" is a question with one unique answer
The four strategies in §4 under the same one-line change:
| Strategy | Chunks | Total bytes | Must re-download | Ratio |
|---|---|---|---|---|
| single | 1 | 20.4KB | 20.4KB | 100.0% |
| vendor | 1 | 20.4KB | 20.4KB | 100.0% |
| shared | 2 | 20.4KB | 12.5KB | 61.1% |
| per-module | 141 | 20.3KB | 89B | 0.4% |
Note that vendor degenerates to 1 chunk here (the synthetic project has no real node_modules), which exactly proves the strategy must match the project structure. And per-module's 0.4% is not "free"—it's 141 HTTP requests, which under HTTP/1.1 gets eaten by head-of-line blocking, and under HTTP/2 still hits the server's concurrent-stream limit.
Engineering answer: use a "reference count" layer (the shared path): modules referenced by ≥2 entries and changed infrequently go into a long-term cache chunk; business code that changes often is split by route. The criterion is not "smaller is better", it's a two-dimensional clustering of change frequency × sharing degree.
3.3 Hash chaining: The direct conflict between safety and cache hit rate
The numbers in §5 are worth remembering separately: one leaf change, hashing only itself invalidates 89B (0.4%), chained hashing invalidates 18.6KB (91.8%), affecting 124 chunks, blast radius amplified 214.40x.
Chained hashing (including a chunk's dependency hashes into its own) buys the hard guarantee that "if dependencies changed, you can't get stale artifacts", at the cost of cache hit rate. So:
- Runtime dependencies between artifacts (A chunk references names/indexes from B chunk's exports) → must chain, otherwise runtime mismatch.
- Only "logically related" (A and B both import utils) → should not chain.
Distinguishing these two is the only line between "changed utils and the whole site's cache broke" and "white screen on deploy, 404 on assets".
3.4 When you should actually write your own bundler
Not for "reinventing the wheel", but three concrete scenarios:
- Library authors: you need to output the
esm+cjs+.d.tstrio, with precise control overexternal,preserveModules,sideEffects—these behaviors must be explainable at source level, not discovered by trial. - Private syntax / DSL: internal
definePage()or custom template directives need transform plugins, and writing a correct plugin requires knowing how the scanner tokenizes and how side effects are judged. - Build bottlenecks must be located yourself: an 8-minute CI build, and the vendor will only say "upgrade the version". This article's breakdown (graph/shake/link/hash + lexer share) can point out which stage overruns its budget in an hour.
3.5 How this article interlocks with previous/next ones
- Day25 Rendering / Day29 Runtime / Day34 Monitoring: this article's artifacts directly determine the metrics those three measure. The performance budget's choke point should be set here—capping the first-screen chunk bytes at build time costs two orders of magnitude less than looking at LCP after deploy.
- Day26 Loading / Day30 Bundle Optimization: the code splitting, preload, and manifest from Day30 have their upstream in this article's
planChunksandcontentHash. If the chunking strategy is wrong, all of Day30's optimizations are wasted. - Day28 SSR/SSG/ISR: SSR outputs also go through the build, and "server chunks / client chunks" are two separate graphs. This article's determinism requirement is a hard constraint on them (otherwise every build produces new files).
- Day33 WASM: how WASM resources enter chunks, are hashed, and stream-compiled falls under this article's chunking and hashing.
- Day36 Monorepo / Day38 Pipelines: the foundation of incremental builds and remote caching is this article's §10—scanning cache saves parsing (198ms → 131ms, 1.5x), but does not save graph traversal; to go further you need chunk-level incremental.
- Day40 Observability: build instrumentation (each stage's time, cache hit rate, output size diff) should be linked with runtime correlation IDs to answer "is this slowdown a code change or a build change?".
4. Summary
First, the core of build tools is not "bundling", it's "precise context judgment". Finding import takes 5 minutes; determining whether that import is real code or a literal in a comment is 500 lines. Three disguised samples all false-positive, and the regex approach is 43.7x faster—the fast part is exactly the part you don't need.
Second, the benefit of tree-shaking mainly comes from "not entering the graph", not from "deleting cleverly". 96.5% reduction includes 270/301 modules that were never parsed. The places that truly need algorithms are the counterexamples: top-level side effects, named default exports, re-export edges. (The 2.55x side-effect cost is the best footnote.)
Third, caching is two independent knobs; don't turn only one. Chunk granularity manages 100% → 0.4%; hash chaining manages 0.4% → 91.8% (214.40x). The former is a trade-off between size and request count; the latter is a trade-off between safety and hit rate. Confusing them makes you bounce between "cache not working" and "404 on deploy".
Fourth, determinism is a hard build metric, and it can be guarded by assertions. Five different hashes after shuffling enumeration order—this bug doesn't fail the build; it just silently dismisses CDN caches. One assert.equal(hash1, hash2) fixes it forever.
Fifth, performance optimization must measure first, and align the baseline before measuring. When I first measured "what share is lexing in the whole pipeline", I got the absurd conclusion that graph building was faster than pure lexing—because the lexing benchmark ran all 3001 files, while graph building only parsed the reachable 1201. If baselines aren't aligned, every optimization decision is wrong. After aligning, the truth is clear: lexing 31.5%, linking 18.2% (originally 46%, a double loop pushed it up).
Last: 33 assertions plus 5 real-ESM differential groups caught 4 bugs that keep the build green but output wrong—missed recursion in template interpolation, named default exports never shaken, re-export edges not in the graph, and the namespace shim disappearing when chunked. The quality of a build tool is not that it can bundle; it's that it refuses to bundle things incorrectly. Next, Day36 goes into Monorepo, and every pain point of that topic (dependency deduping, phantom dependencies, incremental builds, cross-package references) will return to this module graph.
All code and measurement scripts:
day35-assets/(scan.mjs/build.mjs/fixtures.mjs/test-bundler.mjs/bench.mjs/bench-log.txt). Reproduce:node test-bundler.mjs(33 assertions, exit 0),node bench.mjs(13 measured groups, all numbers measured on site).
Appendix: Complete Code
The scripts below are all from
day35-assets/(full source). Run:node test-bundler.mjsto verify bundler semantics;node bench.mjsfor benchmarks;node extract-and-test.mjsto extract code blocks from the article and self-check each one.
build.mjs — Hand-written bundler core (dependency graph, transform, bundling, chunk splitting, 837 lines)
// build.mjs — Zero-dependency mini bundler: module graph → tree-shaking → scope-hoisting linking → chunking → content hashing
import { scanModule, hasSideEffects, tokenize as tokenizeSnippet } from './scan.mjs';
const EXTS = ['.mjs', '.js'];
let uid = 0;
/* ============ 1. Virtual filesystem and parsing ============ */
export function createFS(files) {
// files: Map<path, source> or plain object; always converted to Map, paths normalized without leading ./
const map = new Map();
const src = files instanceof Map ? [...files.entries()] : Object.entries(files);
for (const [k, v] of src) map.set(norm(k), v);
return {
get: (p) => map.get(norm(p)),
has: (p) => map.has(norm(p)),
keys: () => [...map.keys()],
size: () => map.size,
set: (p, v) => map.set(norm(p), v),
clone: () => createFS(new Map(map)),
raw: map,
};
}
function norm(p) {
const parts = p.replace(/\\/g, '/').split('/');
const out = [];
for (const seg of parts) {
if (seg === '' || seg === '.') continue;
if (seg === '..') { out.pop(); continue; }
out.push(seg);
}
return out.join('/');
}
function dirname(p) {
const i = p.lastIndexOf('/');
return i === -1 ? '' : p.slice(0, i);
}
/**
* Resolve a module specifier. A real bundler would have the npm resolution algorithm (exports field / conditions / self-reference...).
* Here only relative path + extension probing + directory index, enough to cover ESM semantic differences.
*/
export function resolveSpec(fs, fromPath, spec) {
if (!spec.startsWith('.')) {
// Bare module: treat as path under node_modules
const base = `node_modules/${spec}`;
for (const cand of probe(fs, base)) return cand;
return null;
}
const base = norm(`${dirname(fromPath)}/${spec}`);
for (const cand of probe(fs, base)) return cand;
return null;
}
function* probe(fs, base) {
if (fs.has(base) && !isDirish(fs, base)) { yield base; return; }
for (const e of EXTS) {
if (fs.has(base + e)) { yield base + e; return; }
}
for (const e of EXTS) {
const idx = `${base}/index${e}`;
if (fs.has(idx)) { yield idx; return; }
}
}
// In virtual FS, paths ending with "/" represent directory placeholders; just ignore them
const isDirish = (fs, p) => p.endsWith('/');
/* ============ 2. Module graph ============ */
export function buildGraph(fs, entryPath, opts = {}) {
fs = fs.raw ? fs : createFS(fs);
const entry = norm(entryPath);
const byPath = new Map();
const modules = [];
const unresolved = [];
// Scan cache: key=path, value={source, scan}. If the source string matches, reuses the previous lexical/syntax result — this is the entire reason "incremental build" works.
const cache = opts.cache ?? null;
let cacheHit = 0, cacheMiss = 0;
const addModule = (path) => {
const source = fs.get(path);
if (source === undefined) throw new Error(`Module does not exist: ${path}`);
let scan;
const cached = cache ? cache.get(path) : undefined;
if (cached && cached.source === source) { scan = cached.scan; cacheHit++; }
else { scan = scanModule(source); cacheMiss++; if (cache) cache.set(path, { source, scan }); }
const mod = {
id: modules.length,
path,
source,
scan,
bytes: source.length,
// Static dependencies (participate in tree-shaking and execution order)
deps: [],
// Dynamic imports (chunked separately, do not participate in tree-shaking)
dynamicDeps: [],
sideEffects: hasSideEffects(scan),
};
modules.push(mod);
byPath.set(path, mod);
return mod;
};
const visit = (path) => {
if (byPath.has(path)) return byPath.get(path);
const mod = addModule(path);
for (const imp of mod.scan.imports) {
const target = resolveSpec(fs, path, imp.source);
if (!target) { unresolved.push({ from: path, spec: imp.source }); continue; }
mod.deps.push({ spec: imp.source, targetPath: target });
}
// `export {x} from './y'` / `export * from './y'` are also dependency edges; missing them means the re-exported module never enters the graph (I stepped on this: byPath.get() got undefined)
for (const ex of mod.scan.exports) {
if (!ex.source) continue;
const target = resolveSpec(fs, path, ex.source);
if (!target) { unresolved.push({ from: path, spec: ex.source }); continue; }
if (!mod.deps.some((d) => d.targetPath === target)) mod.deps.push({ spec: ex.source, targetPath: target });
}
for (const spec of mod.scan.dynamicImports) {
if (spec == null) { mod.dynamicDeps.push({ spec: null, targetPath: null }); continue; }
const target = resolveSpec(fs, path, spec);
if (!target) { unresolved.push({ from: path, spec }); continue; }
mod.dynamicDeps.push({ spec, targetPath: target });
}
if (mod.sideEffects) mod.sideEffectDeps = mod.deps.length; // just for recording
for (const d of mod.deps) visit(d.targetPath);
for (const d of mod.dynamicDeps) if (d.targetPath) visit(d.targetPath);
return mod;
};
const entryMod = visit(entry);
// Backfill targetId (ids may not yet be allocated during visit)
for (const mod of modules) {
for (const d of mod.deps) d.targetId = byPath.get(d.targetPath).id;
for (const d of mod.dynamicDeps) d.targetId = d.targetPath ? byPath.get(d.targetPath).id : null;
}
const cycles = findCycles(modules);
const order = topoOrder(modules, entryMod.id);
return {
fs, entry, entryId: entryMod.id, modules, byPath, order, cycles, unresolved,
scanStats: { cacheHit, cacheMiss },
};
}
/** Tarjan strongly connected components: returns all cycles of length > 1 (including self-loops) */
export function findCycles(modules) {
const index = new Map();
const low = new Map();
const onStack = new Set();
const stack = [];
const comps = [];
let counter = 0;
const strong = (v) => {
index.set(v, counter); low.set(v, counter); counter++;
stack.push(v); onStack.add(v);
for (const d of modules[v].deps) {
const w = d.targetId;
if (!index.has(w)) { strong(w); low.set(v, Math.min(low.get(v), low.get(w))); }
else if (onStack.has(w)) low.set(v, Math.min(low.get(v), index.get(w)));
}
if (low.get(v) === index.get(v)) {
const comp = [];
let w;
do { w = stack.pop(); onStack.delete(w); comp.push(w); } while (w !== v);
comps.push(comp);
}
};
for (const m of modules) if (!index.has(m.id)) strong(m.id);
return comps.filter((c) => {
if (c.length > 1) return true;
// self-loop
const v = c[0];
return modules[v].deps.some((d) => d.targetId === v);
});
}
/** Post-order DFS: dependencies before dependents (break cycles by discovery order) */
export function topoOrder(modules, entryId) {
const out = [];
const state = new Map(); // 0=unvisited 1=in stack 2=done
const walk = (id) => {
if (state.get(id) === 2) return;
if (state.get(id) === 1) return; // cycle: skip to avoid infinite loop
state.set(id, 1);
for (const d of modules[id].deps) walk(d.targetId);
state.set(id, 2);
out.push(id);
};
walk(entryId);
return out;
}
/* ============ 3. Export resolution (including re-export traversal) ============ */
/**
* Resolve "export name 'name' of module M" into "some module's local binding".
* Needs to traverse `export {x} from './y'` and `export * from './y'`, and prevent cycles.
*/
export function resolveExport(graph, modId, name, seen = new Set()) {
const key = `${modId}#${name}`;
if (seen.has(key)) return null;
seen.add(key);
const mod = graph.modules[modId];
for (const e of mod.scan.exports) {
if (e.exported !== name) continue;
if (e.source) {
const target = resolveSpec(graph.fs, mod.path, e.source);
if (!target) return null;
const tid = graph.byPath.get(target).id;
return resolveExport(graph, tid, e.imported, seen);
}
return { modId, local: e.local };
}
// export * traversal
for (const e of mod.scan.exports) {
if (e.exported !== '*' || !e.source) continue;
const target = resolveSpec(graph.fs, mod.path, e.source);
if (!target) continue;
const tid = graph.byPath.get(target).id;
const r = resolveExport(graph, tid, name, seen);
if (r) return r;
}
return null;
}
/** All export names exposed by module (including those via re-export) */
export function allExportNames(graph, modId, seen = new Set()) {
if (seen.has(modId)) return [];
seen.add(modId);
const mod = graph.modules[modId];
const names = [];
for (const e of mod.scan.exports) {
if (e.exported === '*') {
const target = resolveSpec(graph.fs, mod.path, e.source);
if (target) names.push(...allExportNames(graph, graph.byPath.get(target).id, seen));
} else if (!names.includes(e.exported)) {
names.push(e.exported);
}
}
return names;
}
/* ============ 4. Tree-shaking ============ */
/**
* Two things:
* A. Statement-level liveness analysis (within module: export declarations + top-level declarations reachability propagation)
* B. Module-level liveness analysis (a module with no side effects and not referenced by any live statement is dropped entirely)
*/
export function treeShake(graph) {
const M = graph.modules;
const stmtCount = (m) => m.scan.statements.length;
// ---- Per-module statement metadata ----
for (const mod of M) {
mod.stmtInfo = mod.scan.statements.map((st, i) => ({
i, kind: st.kind, names: st.names, start: st.start, end: st.end,
}));
// Top-level non import/export statements = potential side-effect statements (roughly judged by scan's topLevelStmts)
mod.declStmt = new Map(); // name -> stmt index
for (const si of mod.stmtInfo) {
if (si.kind === 'export-decl' || si.kind === 'export-list' || si.kind === 'export-default') {
for (const nm of si.names) mod.declStmt.set(nm, si.i);
}
}
}
const included = new Set(); // whole module included
const usedExports = new Map(); // modId -> Set<name> | '*'
const keptStmts = new Map(); // modId -> Set<stmtIndex>
const markUsedExport = (modId, name) => {
const cur = usedExports.get(modId);
if (cur === '*') return false;
const set = cur ?? new Set();
if (set.has(name)) return false;
set.add(name);
usedExports.set(modId, set);
return true;
};
// Entry: the whole module is included
included.add(graph.entryId);
usedExports.set(graph.entryId, '*');
let changed = true;
const guard = 10000;
let iter = 0;
while (changed) {
changed = false;
if (++iter > guard) throw new Error('tree-shake did not converge');
for (const mod of M) {
const whole = usedExports.get(mod.id) === '*';
if (!included.has(mod.id)) continue;
// ---- Statement-level liveness ----
const kept = new Set();
// A module with side effects: all statements must be kept (order preserved too)
const keepAll = mod.sideEffects || whole;
if (keepAll) {
// import statements don't produce code, so they cannot participate in liveness propagation;
// otherwise all imported local names in the entry become falsely live (I stepped on this)
for (const si of mod.stmtInfo) { if (si.kind !== 'import') kept.add(si.i); }
} else {
const used = usedExports.get(mod.id) ?? new Set();
for (const si of mod.stmtInfo) {
if (si.kind === 'statement') { kept.add(si.i); continue; }
if (si.kind === 'import') continue; // handled separately
const hit = si.names.some((n) => used.has(n));
if (hit) kept.add(si.i);
}
}
// ---- Reference propagation: referenced declarations of live statements must also be live ----
const localRefs = collectStmtRefs(mod);
let grew = true;
while (grew) {
grew = false;
for (const si of mod.stmtInfo) {
if (!kept.has(si.i)) continue;
for (const nm of localRefs.get(si.i) ?? []) {
const declSi = mod.declStmt.get(nm);
if (declSi !== undefined && !kept.has(declSi)) { kept.add(declSi); grew = true; }
}
}
}
const prev = keptStmts.get(mod.id);
keptStmts.set(mod.id, kept);
if (!prev || prev.size !== kept.size) changed = true;
// ---- Module-level: only imports referenced by live statements are needed ----
const liveRefs = new Set();
for (const si of mod.stmtInfo) {
if (!kept.has(si.i)) continue;
for (const nm of localRefs.get(si.i) ?? []) liveRefs.add(nm);
}
// Decide only by "which local names are actually referenced by live statements".
// (For a side-effectful module, all statements are live, so liveRefs naturally covers everything; no special case needed)
const needAllImports = false;
for (const imp of mod.scan.imports) {
if (imp.sideEffectOnly) {
const t = resolveSpec(graph.fs, mod.path, imp.source);
if (!t) continue;
const tid = graph.byPath.get(t).id;
if (!included.has(tid)) { included.add(tid); changed = true; }
continue;
}
for (const sp of imp.specifiers) {
if (!needAllImports && !liveRefs.has(sp.local)) continue;
const r = resolveExport(graph, mod.id, sp.imported === '*' ? '__ns__' : sp.imported);
const t = resolveSpec(graph.fs, mod.path, imp.source);
if (!t) continue;
const tid = graph.byPath.get(t).id;
if (!included.has(tid)) { included.add(tid); changed = true; }
if (sp.imported === '*') {
if (usedExports.get(tid) !== '*') { usedExports.set(tid, '*'); changed = true; }
} else {
const target = resolveExport(graph, tid, sp.imported);
if (target) {
if (!included.has(target.modId)) { included.add(target.modId); changed = true; }
if (markUsedExport(target.modId, target.local)) changed = true;
}
void r;
}
}
}
// Re-export edges: `export {x} from` / `export * from` targets must be included
for (const ex of mod.scan.exports) {
if (!ex.source) continue;
const tt = resolveSpec(graph.fs, mod.path, ex.source);
if (!tt) continue;
const tid2 = graph.byPath.get(tt).id;
if (!included.has(tid2)) { included.add(tid2); changed = true; }
}
// Dynamic imports: always included (separate chunk), not shaken
for (const d of mod.dynamicDeps) {
if (d.targetId != null && !included.has(d.targetId)) { included.add(d.targetId); changed = true; }
}
}
}
// Stats
const includedMods = M.filter((m) => included.has(m.id));
const totalBytes = M.reduce((a, m) => a + m.bytes, 0);
const keptBytes = includedMods.reduce((a, m) => a + moduleEmittedSize(m, keptStmts.get(m.id)), 0);
return {
included, usedExports, keptStmts,
stats: {
modulesTotal: M.length,
modulesIncluded: includedMods.length,
modulesDropped: M.length - includedMods.length,
bytesTotal: totalBytes,
bytesKept: keptBytes,
},
};
}
/** Estimate the source bytes a module will actually output (sum over kept statements; module shell overhead is 0) */
function moduleEmittedSize(mod, kept) {
if (!kept) return 0;
let n = 0;
const stmts = mod.scan.statements;
for (const si of mod.stmtInfo) {
if (!kept.has(si.i)) continue;
n += si.end - si.start;
}
return n;
}
/** Identifiers referenced by each statement (excluding property names and object keys), sliced by token range */
function collectStmtRefs(mod) {
if (mod._stmtRefs) return mod._stmtRefs;
const map = new Map();
// Template interpolations are nested token arrays: without flattening, you don't see `${importedName}`
const flatten = (list, base = 0, out = []) => {
for (const tk of list) {
if (tk.t === 'tpl' && tk.parts) {
for (const pt of tk.parts) {
// Interpolation token offsets are relative to the slice; must add the slice start to restore absolute offsets
if (pt.expr) flatten(pt.expr, pt.es, out);
}
continue;
}
out.push(base === 0 ? tk : { ...tk, s: tk.s + base, e: tk.e + base });
}
return out;
};
const toks = flatten(mod.scan.toks);
for (const si of mod.stmtInfo) {
const refs = new Set();
for (let k = 0; k < toks.length; k++) {
const t = toks[k];
if (t.t !== 'id') continue;
if (t.s < si.start || t.e > si.end) continue;
const prevV = toks[k - 1] ? toks[k - 1].v : undefined;
const nextV = toks[k + 1] ? toks[k + 1].v : undefined;
if (prevV === '.' || prevV === '?.') continue;
if (nextV === ':' && (prevV === '{' || prevV === ',')) continue;
refs.add(t.v);
}
map.set(si.i, refs);
}
mod._stmtRefs = map;
return map;
}
/* ============ 5. Linking (scope hoisting + renaming) ============ */
const g = (modId, name) => `m${modId}$${name}`;
export function link(graph, shake, opts = {}) {
const emit = opts.emitter === 'naive' ? emitModuleNaive : emitModule;
const M = graph.modules;
const pieces = [];
const renamesByMod = new Map();
let nsShimBytes = 0;
// Build renaming table per module: local name → global name
for (const mod of M) {
if (!shake.included.has(mod.id)) continue;
const rn = new Map();
for (const d of mod.scan.decls) rn.set(d, g(mod.id, d));
for (const imp of mod.scan.imports) {
for (const sp of imp.specifiers) {
if (sp.imported === '*') { rn.set(sp.local, g(mod.id, sp.local)); continue; }
const t = resolveSpec(graph.fs, mod.path, imp.source);
if (!t) continue;
const tid = graph.byPath.get(t).id;
const target = resolveExport(graph, tid, sp.imported);
if (target) rn.set(sp.local, g(target.modId, target.local));
}
}
renamesByMod.set(mod.id, rn);
}
// Namespace import: generate an object literal that aggregates the target module's exports.
// Must be attached as the importing module's prelude, otherwise it gets lost during chunking (I actually stepped on this:
// single-chunk builds look fine, but once chunkCode reassembles, the ns declaration disappears).
const nsDeclsByMod = new Map();
for (const mod of M) {
if (!shake.included.has(mod.id)) continue;
const kept = shake.keptStmts.get(mod.id);
if (!kept) continue;
for (const imp of mod.scan.imports) {
const t = resolveSpec(graph.fs, mod.path, imp.source);
if (!t) continue;
const tid = graph.byPath.get(t).id;
for (const sp of imp.specifiers) {
if (sp.imported !== '*') continue;
const fields = allExportNames(graph, tid)
.map((n) => {
const r = resolveExport(graph, tid, n);
return r ? `${JSON.stringify(n)}: ${g(r.modId, r.local)}` : null;
})
.filter(Boolean);
const line = `const ${g(mod.id, sp.local)} = { ${fields.join(', ')} };`;
nsShimBytes += line.length + 1;
const arr = nsDeclsByMod.get(mod.id) ?? [];
arr.push(line);
nsDeclsByMod.set(mod.id, arr);
}
}
}
// Dependencies before dependents
for (const id of graph.order) {
if (!shake.included.has(id)) continue;
const mod = M[id];
const kept = shake.keptStmts.get(id) ?? new Set();
const code = emit(mod, kept, renamesByMod.get(id), mod.scan);
const prelude = (nsDeclsByMod.get(id) ?? []).join('\n');
const full = [prelude, code].filter((x) => x && x.trim()).join('\n');
if (!full.trim()) continue;
pieces.push({ modId: id, path: mod.path, code: full });
}
const code = pieces.map((p) => p.code).join('\n');
return {
code, pieces, nsShimBytes,
stats: { bytes: code.length, pieces: pieces.length },
};
}
/**
* Emit one module according to kept statements: strip import/export wrappers + rename.
*
* This is the easiest spot in the whole pipeline to accidentally write O(n²):
* the first version linearly scanned all tokens for each statement to mark deletion ranges,
* complexity = statements × tokens. At 3000 modules, linking was 46% of the whole pipeline,
* more expensive than lex+parse. After a single token pass + statement pointer advance, it's O(token).
*/
function emitModule(mod, kept, renames, scan) {
const src = mod.source;
const toks = scan.toks;
const stmts = (mod.stmtInfo ?? scanStatements(mod, scan)).slice()
.sort((a, b) => a.start - b.start);
const action = new Uint8Array(toks.length); // 1 = delete
const insertBefore = new Map();
const firstTok = new Map(); // stmtIndex -> first token index
let ptr = 0;
for (let k = 0; k < toks.length; k++) {
const t = toks[k];
while (ptr < stmts.length && stmts[ptr].end <= t.s) ptr++;
if (ptr >= stmts.length) break;
const si = stmts[ptr];
if (t.s < si.start || t.e > si.end) continue; // outside statement
if (!firstTok.has(si.i)) firstTok.set(si.i, k);
const k0 = firstTok.get(si.i);
if (!kept.has(si.i)) { action[k] = 1; continue; }
if (si.kind === 'import' || si.kind === 'export-list' || si.kind === 'export-star') {
action[k] = 1;
continue;
}
if (si.kind === 'export-decl') {
// strip only the export keyword, keep the declaration body
if (k === k0) action[k] = 1;
continue;
}
if (si.kind === 'export-default') {
// named function/class → delete default together; otherwise prepend `const mN$__default = `
const namedFnClass = toks[k0 + 2] && ['function', 'class', 'async'].includes(toks[k0 + 2].v)
&& toks[k0 + 3] && toks[k0 + 3].t === 'id';
if (k === k0 || k === k0 + 1) action[k] = 1;
else if (k === k0 + 2 && !namedFnClass) insertBefore.set(k, `const ${g(mod.id, '__default')} = `);
}
}
let out = '';
let prevEnd = 0;
for (let k = 0; k < toks.length; k++) {
const t = toks[k];
const gap = src.slice(prevEnd, t.s);
if (action[k] === 1) {
const nl = countNewlines(gap);
out += nl ? '\n'.repeat(nl) : ' ';
prevEnd = t.e;
continue;
}
out += gap;
if (insertBefore.has(k)) out += insertBefore.get(k);
let rep;
if (t.t === 'tpl' && t.parts) rep = renameSnippet(t.v, renames);
else rep = rewriteToken(t, toks, k, renames);
out += rep;
prevEnd = t.e;
}
out += src.slice(prevEnd);
return clean(out);
}
/** First version O(statements×tokens) implementation, kept only for bench's "before/after" comparison */
export function emitModuleNaive(mod, kept, renames, scan) {
const src = mod.source;
const toks = scan.toks;
const action = new Map();
const insertBefore = new Map();
for (const si of (mod.stmtInfo ?? scanStatements(mod, scan))) {
if (!kept.has(si.i)) {
for (let k = 0; k < toks.length; k++) {
const t = toks[k];
if (t.s >= si.start && t.e <= si.end) action.set(k, 1);
}
continue;
}
if (si.kind === 'import' || si.kind === 'export-list' || si.kind === 'export-star') {
for (let k = 0; k < toks.length; k++) {
const t = toks[k];
if (t.s >= si.start && t.e <= si.end) action.set(k, 1);
}
continue;
}
let k0 = -1;
for (let k = 0; k < toks.length; k++) if (toks[k].s === si.start) { k0 = k; break; }
if (k0 < 0) continue;
if (toks[k0].v === 'export') {
if (si.kind === 'export-default') {
const namedFnClass = toks[k0 + 2] && ['function', 'class', 'async'].includes(toks[k0 + 2].v)
&& toks[k0 + 3] && toks[k0 + 3].t === 'id';
action.set(k0, 1); action.set(k0 + 1, 1);
if (!namedFnClass) insertBefore.set(k0 + 2, `const ${g(mod.id, '__default')} = `);
} else {
action.set(k0, 1);
}
}
}
let out = '';
let prevEnd = 0;
for (let k = 0; k < toks.length; k++) {
const t = toks[k];
const gap = src.slice(prevEnd, t.s);
if (action.get(k) === 1) {
const nl = countNewlines(gap);
out += nl ? '\n'.repeat(nl) : ' ';
prevEnd = t.e;
continue;
}
out += gap;
if (insertBefore.has(k)) out += insertBefore.get(k);
out += (t.t === 'tpl' && t.parts) ? renameSnippet(t.v, renames) : rewriteToken(t, toks, k, renames);
prevEnd = t.e;
}
out += src.slice(prevEnd);
return clean(out);
}
function countNewlines(s) {
let n = 0;
for (let i = 0; i < s.length; i++) if (s.charCodeAt(i) === 10) n++;
return n;
}
function clean(s) {
// Collapse extra blank lines to avoid deleting statements leaving large whitespace that inflates size
return s.replace(/[ \t]+\n/g, '\n').replace(/\n{3,}/g, '\n\n').trim();
}
function scanStatements(mod, scan) {
return scan.statements.map((st, i) => ({
i, kind: st.kind, names: st.names, start: st.start, end: st.end,
}));
}
/**
* Rename a standalone source snippet (used for template string interpolations).
* Lexical renaming most often misses interpolations: `${value}` without this recursion leaves the original name → ReferenceError.
*/
export function renameSnippet(text, renames) {
if (!renames.size) return text;
const toks = tokenizeSnippet(text);
let out = '';
let prevEnd = 0;
for (let k = 0; k < toks.length; k++) {
const t = toks[k];
out += text.slice(prevEnd, t.s);
if (t.t === 'tpl' && t.parts) {
let rebuilt = '';
let last = t.s;
for (const part of t.parts) {
if (part.expr) {
rebuilt += text.slice(last, part.es) + renameSnippet(text.slice(part.es, part.ee), renames);
last = part.ee;
}
}
rebuilt += text.slice(last, t.e);
out += rebuilt;
} else {
out += rewriteToken(t, toks, k, renames);
}
prevEnd = t.e;
}
out += text.slice(prevEnd);
return out;
}
/** Single-token renaming: handle property access, object keys, shorthand properties */
function rewriteToken(t, toks, k, renames) {
if (t.t !== 'id') return t.v;
const prevV = toks[k - 1] ? toks[k - 1].v : undefined;
const nextV = toks[k + 1] ? toks[k + 1].v : undefined;
if (prevV === '.' || prevV === '?.') return t.v;
if (nextV === ':' && (prevV === '{' || prevV === ',')) return t.v; // object key
const target = renames.get(t.v);
if (!target) return t.v;
// shorthand property { foo } → { foo: m0$foo }
const prevIsOpen = prevV === '{' || prevV === ',';
const nextIsClose = nextV === '}' || nextV === ',';
if (prevIsOpen && nextIsClose) return `${t.v}: ${target}`;
return target;
}
/* ============ 6. Chunking ============ */
/**
* Four chunking strategies, used to compare "how many bytes a one-byte change invalidates".
* - single: all in one chunk
* - vendor: node_modules separate
* - shared: modules referenced by ≥2 entries go into shared chunk
* - per-module: one module one chunk (extreme case)
*/
export function planChunks(graph, shake, strategy) {
const includedIds = [...shake.included];
const isVendor = (m) => m.path.startsWith('node_modules/');
if (strategy === 'single') {
return [{ name: 'bundle', modIds: includedIds }];
}
if (strategy === 'vendor') {
const v = includedIds.filter((id) => isVendor(graph.modules[id]));
const a = includedIds.filter((id) => !isVendor(graph.modules[id]));
const chunks = [];
if (a.length) chunks.push({ name: 'app', modIds: a });
if (v.length) chunks.push({ name: 'vendor', modIds: v });
return chunks;
}
if (strategy === 'per-module') {
return includedIds.map((id) => ({ name: `m${id}`, modIds: [id] }));
}
// shared: count how many modules reference each module (approximating reference count)
const refCount = new Map();
for (const mod of graph.modules) {
if (!shake.included.has(mod.id)) continue;
for (const d of mod.deps) {
if (d.targetId == null) continue;
refCount.set(d.targetId, (refCount.get(d.targetId) ?? 0) + 1);
}
}
const shared = [];
const own = [];
for (const id of includedIds) {
if (id === graph.entryId) { own.push(id); continue; }
if ((refCount.get(id) ?? 0) >= 2) shared.push(id); else own.push(id);
}
const chunks = [];
if (own.length) chunks.push({ name: 'entry', modIds: own });
if (shared.length) chunks.push({ name: 'shared', modIds: shared });
return chunks;
}
/** Concatenate a chunk's module code (for size and hash) */
export function chunkCode(linkResult, chunk) {
const set = new Set(chunk.modIds);
return linkResult.pieces.filter((p) => set.has(p.modId)).map((p) => p.code).join('\n');
}
/* ============ 7. Content hash ============ */
const FNV_OFFSET = 0xcbf29ce484222325n;
const FNV_PRIME = 0x100000001b3n;
const MASK64 = (1n << 64n) - 1n;
/** FNV-1a 64, per UTF-16 code unit (real tools use xxhash/content hash; idea is the same) */
export function contentHash(str) {
let h = FNV_OFFSET;
for (let i = 0; i < str.length; i++) {
h ^= BigInt(str.charCodeAt(i) & 0xff);
h = (h * FNV_PRIME) & MASK64;
h ^= BigInt(str.charCodeAt(i) >> 8);
h = (h * FNV_PRIME) & MASK64;
}
return h.toString(16).padStart(16, '0');
}
/** Dual-channel FNV-1a 32-bit (Math.imul) combined into 64 bits: an order of magnitude faster than BigInt */
export function contentHashFast(str) {
let h1 = 0x811c9dc5, h2 = 0x01000193;
for (let i = 0; i < str.length; i++) {
const c = str.charCodeAt(i);
h1 = Math.imul(h1 ^ (c & 0xff), 0x01000193);
h2 = Math.imul(h2 ^ (c >>> 8), 0x01000193);
}
return ((h1 >>> 0).toString(16).padStart(8, '0')) + ((h2 >>> 0).toString(16).padStart(8, '0'));
}
/* ============ 8. One-call build ============ */
export function build(files, entry, opts = {}) {
const fs = createFS(files);
const graph = buildGraph(fs, entry, { cache: opts.cache });
const shake = treeShake(graph);
const linked = link(graph, shake);
// Attach the entry's exports to a caller-provided variable, so tests can do differential comparisons directly.
// Note: must be attached at the tail of the chunk containing the entry module; adding to linked.code would be lost during chunking.
const exposeTail = opts.expose
? (() => {
const fields = allExportNames(graph, graph.entryId).map((n) => {
const r = resolveExport(graph, graph.entryId, n);
return r ? `${JSON.stringify(n)}: ${g(r.modId, r.local)}` : null;
}).filter(Boolean);
return `\n;${opts.expose} = { ${fields.join(', ')} };`;
})()
: '';
const strategy = opts.strategy ?? 'single';
const chunks = planChunks(graph, shake, strategy);
const emitted = chunks.map((c) => {
let code = chunkCode(linked, c);
if (exposeTail && c.modIds.includes(graph.entryId)) code += exposeTail;
return { name: c.name, modIds: c.modIds, code, bytes: code.length, hash: contentHash(code) };
});
return { graph, shake, linked, chunks: emitted, unresolved: graph.unresolved };
}
export { norm, dirname, uid };
scan.mjs — Static analysis (dependency scanning, tree-shaking reachability analysis)
// scan.mjs — Zero-dependency ESM tokenizer + module syntax scanner
// Goal: no full AST, but precisely extract the syntax that determines bundling results
// import/export statements, top-level bindings, dynamic import, top-level side effects
/* ============ 1. Tokenizer ============ */
const PUNC3 = ['...', '===', '!==', '**=', '<<=', '>>=', '>>>', '&&=', '||=', '??='];
const PUNC2 = [
'=>', '==', '!=', '<=', '>=', '&&', '||', '??', '?.', '++', '--',
'+=', '-=', '*=', '/=', '%=', '&=', '|=', '^=', '**', '<<', '>>',
];
// After these keywords, a / is always a regex, never division
const REGEX_PREV_KW = new Set([
'return', 'typeof', 'instanceof', 'in', 'of', 'new', 'delete', 'void',
'throw', 'case', 'do', 'else', 'yield', 'await',
]);
// After these keywords, ( ... ) is a "control condition parenthesis"; its ) allows regex
const CONTROL_KW = new Set(['if', 'while', 'for', 'with', 'switch', 'catch']);
const isIdStart = (c) => /[A-Za-z_$#]/.test(c) || c > '\x7f';
const isIdPart = (c) => /[A-Za-z0-9_$]/.test(c) || c > '\x7f';
const isDigit = (c) => c >= '0' && c <= '9';
/**
* Tokenize source into tokens.
* token: { t, v, s, e }
* t: 'id' | 'num' | 'str' | 'tpl' | 're' | 'punc'
* tpl also carries parts: [{ s, e } | { expr: token[] }]
* A global parenStack is maintained to decide if a ) can be followed by regex.
*/
export function tokenize(src) {
const toks = [];
const n = src.length;
let i = 0;
// paren stack: records whether each ( belongs to a control statement
const parens = [];
// records the last "significant" token, for regex-ambiguity resolving
let prev = null;
const push = (tok) => {
toks.push(tok);
prev = tok;
return tok;
};
// read-only lookahead: find previous non-whitespace char
const lastSignificant = () => prev;
const regexAllowed = () => {
const p = lastSignificant();
if (!p) return true; // file start
if (p.t === 'num' || p.t === 'str' || p.t === 'tpl' || p.t === 're') return false;
if (p.t === 'id') return REGEX_PREV_KW.has(p.v);
if (p.t === 'punc') {
if (p.v === ')') return p.ctrl === true; // ) of if(...)/for(...) → allowed
if (p.v === ']') return false;
if (p.v === '}') return true; // block end, permissive
if (p.v === '++' || p.v === '--') return false;
return true;
}
return true;
};
// Scan a template string, recursively tokenizing the expression inside ${ }
function scanTemplate(start) {
// start points to the backtick
let j = start + 1;
const parts = [];
let segStart = j;
while (j < n) {
const c = src[j];
if (c === '\\') { j += 2; continue; }
if (c === '`') {
parts.push({ s: segStart, e: j });
return { end: j + 1, parts };
}
if (c === '$' && src[j + 1] === '{') {
parts.push({ s: segStart, e: j });
// recursively tokenize the expression part
const exprStart = j + 2;
let depth = 1, k = exprStart;
while (k < n && depth > 0) {
const ch = src[k];
if (ch === '\\') { k += 2; continue; }
if (ch === '{') depth++;
else if (ch === '}') depth--;
if (depth === 0) break;
// skip strings so } inside strings don't affect balancing
if (ch === '"' || ch === "'" || ch === '`') {
k = skipStringLike(k);
continue;
}
k++;
}
const inner = src.slice(exprStart, k);
// record absolute ranges; renaming must handle recursively within interpolations (most easily missed)
parts.push({ expr: tokenize(inner), es: exprStart, ee: k });
j = k + 1;
segStart = j;
continue;
}
j++;
}
throw new SyntaxError('Unclosed template string');
}
// Return index after closing quote
function skipStringLike(k) {
const q = src[k];
if (q === '`') {
// roughly skip a template
let m = k + 1;
while (m < n) {
if (src[m] === '\\') { m += 2; continue; }
if (src[m] === '`') return m + 1;
m++;
}
return m;
}
let m = k + 1;
while (m < n) {
const ch = src[m];
if (ch === '\\') { m += 2; continue; }
if (ch === q) return m + 1;
if (ch === '\n') return m; // unclosed, stop loss
m++;
}
return m;
}
while (i < n) {
const c = src[i];
// whitespace
if (c === ' ' || c === '\t' || c === '\r' || c === '\n' || c === '\uFEFF') { i++; continue; }
// comments
if (c === '/' && src[i + 1] === '/') {
while (i < n && src[i] !== '\n') i++;
continue;
}
if (c === '/' && src[i + 1] === '*') {
const end = src.indexOf('*/', i + 2);
i = end === -1 ? n : end + 2;
continue;
}
// template string
if (c === '`') {
const { end, parts } = scanTemplate(i);
push({ t: 'tpl', v: src.slice(i, end), s: i, e: end, parts });
i = end;
continue;
}
// normal string
if (c === '"' || c === "'") {
let j = i + 1;
while (j < n) {
const ch = src[j];
if (ch === '\\') { j += 2; continue; }
if (ch === c) { j++; break; }
j++;
}
push({ t: 'str', v: src.slice(i, j), s: i, e: j });
i = j;
continue;
}
// number
if (isDigit(c) || (c === '.' && isDigit(src[i + 1]))) {
let j = i;
if (c === '0' && /[xXbBoO]/.test(src[i + 1] || '')) {
j = i + 2;
while (j < n && /[0-9a-fA-F_]/.test(src[j])) j++;
} else {
while (j < n && /[0-9_]/.test(src[j])) j++;
if (src[j] === '.') { j++; while (j < n && /[0-9_]/.test(src[j])) j++; }
if (/[eE]/.test(src[j] || '')) {
const save = j; j++;
if (/[+-]/.test(src[j] || '')) j++;
if (isDigit(src[j] || '')) { while (j < n && /[0-9_]/.test(src[j])) j++; }
else j = save;
}
}
if (src[j] === 'n') j++;
push({ t: 'num', v: src.slice(i, j), s: i, e: j });
i = j;
continue;
}
// identifier / keyword
if (isIdStart(c)) {
let j = i + 1;
while (j < n && isIdPart(src[j])) j++;
push({ t: 'id', v: src.slice(i, j), s: i, e: j });
i = j;
continue;
}
// regex literal (after ambiguity resolution)
if (c === '/' && regexAllowed()) {
let j = i + 1;
let inClass = false;
while (j < n) {
const ch = src[j];
if (ch === '\\') { j += 2; continue; }
if (ch === '[') inClass = true;
else if (ch === ']') inClass = false;
else if (ch === '/' && !inClass) { j++; break; }
else if (ch === '\n') break;
j++;
}
while (j < n && /[a-z]/.test(src[j])) j++; // flags
push({ t: 're', v: src.slice(i, j), s: i, e: j });
i = j;
continue;
}
// punctuation (longest match)
let matched = null;
for (const p of PUNC3) if (src.startsWith(p, i)) { matched = p; break; }
if (!matched) for (const p of PUNC2) if (src.startsWith(p, i)) { matched = p; break; }
if (!matched) matched = c;
if (matched === '(') {
const p = lastSignificant();
parens.push(p && p.t === 'id' && CONTROL_KW.has(p.v));
push({ t: 'punc', v: '(', s: i, e: i + 1, ctrl: parens[parens.length - 1] });
} else if (matched === ')') {
const ctrl = parens.length ? parens.pop() : false;
push({ t: 'punc', v: ')', s: i, e: i + 1, ctrl });
} else {
push({ t: 'punc', v: matched, s: i, e: i + matched.length });
}
i += matched.length;
}
return toks;
}
/* ============ 2. Module syntax scanner ============ */
/**
* Extract module-level facts from a token stream.
* Only recognizes top-level (brace depth 0) import/export/declarations.
*/
export function scanModule(src) {
const toks = tokenize(src);
const imports = []; // { source, specifiers:[{imported:'default'|'*'|name, local}], sideEffectOnly }
const exports = []; // { exported, local?|expression?|source?|imported? }
const decls = []; // bare names of top-level declarations (for building the module's binding table)
const dynamicImports = [];
const topLevelStmts = []; // first token classification of top-level statements, for side-effect detection
const statements = []; // { kind, start, end, names } character ranges, used to delete whole segments during bundling
let depth = 0;
let i = 0;
const at = (k) => toks[k];
const v = (k) => (toks[k] ? toks[k].v : undefined);
// dynamic import can appear at any nesting, and might be inside statements that get skipped entirely,
// so do a separate full pre-scan (cheap, only looks for import followed by ( and not .meta).
for (let k = 0; k < toks.length; k++) {
const tk = toks[k];
if (tk.t !== 'id' || tk.v !== 'import') continue;
const nx = toks[k + 1];
if (!nx || nx.t !== 'punc' || nx.v !== '(') continue;
const arg = toks[k + 2];
if (arg && arg.t === 'str') dynamicImports.push(unquote(arg.v));
else dynamicImports.push(null); // non-literal: in a real build it's not statically analyzable, must be separate chunk
}
const pushStmt = (kind, sIdx, eIdx, names = []) => {
const a = toks[sIdx], b = toks[eIdx];
if (!a || !b) return;
statements.push({ kind, start: a.s, end: b.e, names });
};
// Find the end of a statement starting at k.
// Key pitfall: `export function f(){}` has no semicolon; if you only look for ';', it will swallow the next dozen lines until the next semicolon.
// So track whether a top-level brace was opened; once the brace depth returns to 0, consider it the end.
// groupAt: the { ... } specifier list in import/export is not a statement block; must be excluded,
// otherwise `import {a} from 'x'` would be misjudged as ending at '}' (a real pit I hit).
const stmtEnd = (k, groupAt = -1) => {
let d = 0;
let openedBlock = false;
for (let m = k; m < toks.length; m++) {
const t = toks[m];
if (t.t !== 'punc') continue;
if (t.v === '(' || t.v === '[') d++;
else if (t.v === ')' || t.v === ']') { d--; if (d < 0) return m; }
else if (t.v === '{') { if (m !== groupAt && d === 0) openedBlock = true; d++; }
else if (t.v === '}') {
d--;
if (d < 0) return m;
if (d === 0 && openedBlock) return m;
} else if (t.v === ';' && d === 0) return m;
}
return toks.length - 1;
};
// Parse { a, b as c } → [[imported, local], ...]
const parseSpecList = (k) => {
// k points to {
const out = [];
let m = k + 1;
while (m < toks.length && v(m) !== '}') {
if (at(m).t === 'id') {
const imported = at(m).v;
let local = imported;
if (v(m + 1) === 'as' && at(m + 2)) { local = at(m + 2).v; m += 2; }
out.push({ imported, local });
}
m++;
}
return { list: out, next: m + 1 };
};
while (i < toks.length) {
const t = toks[i];
if (t.t === 'punc') {
if ('({['.includes(t.v)) depth++;
else if (')}]'.includes(t.v)) depth--;
i++;
continue;
}
// dynamic import(...) at any depth
if (t.t === 'id' && t.v === 'import' && v(i + 1) === '(') {
const arg = at(i + 2);
// import.meta is not dynamic import
if (v(i + 1) === '.' && v(i + 2) === 'meta') { i += 3; continue; }
if (arg && arg.t === 'str') dynamicImports.push(unquote(arg.v));
i += 2;
continue;
}
if (depth !== 0) { i++; continue; }
// ---- top-level import ----
if (t.t === 'id' && t.v === 'import' && v(i + 1) !== '.' && v(i + 1) !== '(') {
const start = i;
let m = i + 1;
const specifiers = [];
let braceAt = -1;
// import 'x'
if (at(m) && at(m).t === 'str') {
imports.push({ source: unquote(at(m).v), specifiers: [], sideEffectOnly: true });
pushStmt('import', start, stmtEnd(start));
i = stmtEnd(start) + 1;
continue;
}
// default import
if (at(m) && at(m).t === 'id' && at(m).v !== 'from') {
specifiers.push({ imported: 'default', local: at(m).v });
m++;
if (v(m) === ',') m++;
} else if (at(m) && at(m).t === 'id' && at(m).v === 'from') {
// shouldn't happen
}
// namespace or named
if (v(m) === '*') {
const asName = v(m + 2);
specifiers.push({ imported: '*', local: asName });
m += 3;
} else if (v(m) === '{') {
braceAt = m;
const { list, next } = parseSpecList(m);
specifiers.push(...list.map((x) => ({ imported: x.imported, local: x.local })));
m = next;
}
const end = stmtEnd(start, braceAt);
// from 'x'
while (m <= end && v(m) !== 'from') m++;
const srcTok = at(m + 1);
if (srcTok && srcTok.t === 'str') {
imports.push({ source: unquote(srcTok.v), specifiers, sideEffectOnly: false });
}
pushStmt('import', start, end);
i = end + 1;
continue;
}
// ---- top-level export ----
if (t.t === 'id' && t.v === 'export') {
let m = i + 1;
// export default
if (v(m) === 'default') {
let defaultLocal = null;
const end = stmtEnd(i);
// export default function foo(){} / class Foo{}
const nx = at(m + 1);
if (nx && nx.t === 'id' && (nx.v === 'function' || nx.v === 'class')) {
let p = m + 2;
if (v(p) === '*') p++;
if (at(p) && at(p).t === 'id') {
decls.push(at(p).v);
exports.push({ exported: 'default', local: at(p).v });
defaultLocal = at(p).v;
} else {
// anonymous default export: synthesize a local name for linking-time reference
decls.push('__default');
exports.push({ exported: 'default', local: '__default', anonymous: true });
defaultLocal = '__default';
}
} else if (nx && nx.t === 'id' && nx.v === 'async') {
let p = m + 3;
if (at(p) && at(p).t === 'id') {
decls.push(at(p).v);
exports.push({ exported: 'default', local: at(p).v });
defaultLocal = at(p).v;
} else { decls.push('__default'); exports.push({ exported: 'default', local: '__default', anonymous: true }); }
} else {
exports.push({ exported: 'default', local: '__default', expression: toks.slice(m + 1, end).map((x) => x.v).join(' ') });
decls.push('__default');
defaultLocal = '__default';
}
pushStmt('export-default', i, end, [defaultLocal ?? '__default']);
i = end + 1;
continue;
}
// export * from 'x' / export * as ns from 'x'
if (v(m) === '*') {
if (v(m + 1) === 'as') {
const ns = v(m + 2);
const end = stmtEnd(i);
let p = m + 3;
while (p <= end && v(p) !== 'from') p++;
const s = at(p + 1);
if (s && s.t === 'str') exports.push({ exported: ns, source: unquote(s.v), imported: '*' });
pushStmt('export-star', i, end, [ns]);
i = end + 1;
continue;
}
const end = stmtEnd(i);
const s = at(m + 2);
if (s && s.t === 'str') exports.push({ exported: '*', source: unquote(s.v), imported: '*' });
pushStmt('export-star', i, end, ['*']);
i = end + 1;
continue;
}
// export { ... } [from 'x']
if (v(m) === '{') {
const braceAt = m;
const { list, next } = parseSpecList(m);
const end = stmtEnd(i, braceAt);
let p = next;
while (p <= end && v(p) !== 'from') p++;
if (v(p) === 'from') {
const s = at(p + 1);
const source = s && s.t === 'str' ? unquote(s.v) : null;
for (const x of list) exports.push({ exported: x.local, imported: x.imported, source });
} else {
for (const x of list) exports.push({ exported: x.local, local: x.imported });
}
pushStmt('export-list', i, end, list.map((x) => x.imported));
i = end + 1;
continue;
}
// export const/let/var/function/class/async function
const kw = v(m);
if (kw === 'const' || kw === 'let' || kw === 'var') {
// only take the first/simplest identifier; destructuring declarations need an AST to be accurate, record the capability boundary here
let p = m + 1;
const names = [];
let d = 0;
const end = stmtEnd(i);
while (p <= end) {
const tk = at(p);
if (tk.t === 'punc') {
if ('([{'.includes(tk.v)) d++;
else if (')]}'.includes(tk.v)) d--;
} else if (tk.t === 'id' && d === 0) {
// identifier at the start of a declarator
const prevV = v(p - 1);
if (p === m + 1 || prevV === ',') names.push(tk.v);
}
p++;
}
for (const nm of names) {
decls.push(nm);
exports.push({ exported: nm, local: nm });
}
pushStmt('export-decl', i, end, names);
i = end + 1;
continue;
}
if (kw === 'function' || kw === 'class') {
let p = m + 1;
if (v(p) === '*') p++;
if (at(p) && at(p).t === 'id') {
decls.push(at(p).v);
exports.push({ exported: at(p).v, local: at(p).v });
}
const end = stmtEnd(i);
pushStmt('export-decl', i, end, at(p) && at(p).t === 'id' ? [at(p).v] : []);
i = end + 1;
continue;
}
if (kw === 'async') {
let p = m + 3;
if (at(p) && at(p).t === 'id') {
decls.push(at(p).v);
exports.push({ exported: at(p).v, local: at(p).v });
}
const end = stmtEnd(i);
i = end + 1;
continue;
}
i = m;
continue;
}
// ---- top-level declarations (non-export) ----
if (t.t === 'id' && (t.v === 'function' || t.v === 'class')) {
let p = i + 1;
if (v(p) === '*') p++;
if (at(p) && at(p).t === 'id') decls.push(at(p).v);
i++;
continue;
}
if (t.t === 'id' && t.v === 'async' && v(i + 1) === 'function') {
let p = i + 2;
if (v(p) === '*') p++;
if (at(p) && at(p).t === 'id') decls.push(at(p).v);
i += 2;
continue;
}
if (t.t === 'id' && (t.v === 'const' || t.v === 'let' || t.v === 'var')) {
const end = stmtEnd(i);
let p = i + 1;
let d = 0;
while (p <= end) {
const tk = at(p);
if (tk.t === 'punc') {
if ('([{'.includes(tk.v)) d++;
else if (')]}'.includes(tk.v)) d--;
} else if (tk.t === 'id' && d === 0) {
const prevV = v(p - 1);
if (p === i + 1 || prevV === ',') decls.push(tk.v);
}
p++;
}
i = end + 1;
continue;
}
// other top-level statements → side-effect mark + register as statement (must emit, otherwise side effects lost)
topLevelStmts.push(t ? t.v : '');
{
const end = stmtEnd(i);
pushStmt('statement', i, end);
i = end + 1;
}
}
// Identifiers referenced within this module (excluding declaration sites); tree-shaking liveness uses this.
// Two pitfalls:
// 1) Template strings' ${...} are nested token arrays; flat traversal misses references inside them;
// 2) declaration sites (const x / function f / destructuring bindings) are not references.
// Here we intentionally err conservative (over-count references = fewer deletions = cannot delete incorrectly).
const referenced = new Set();
{
const flatten = (list, out = []) => {
for (const tk of list) {
if (tk.t === 'tpl' && tk.parts) {
for (const pt of tk.parts) if (pt.expr) flatten(pt.expr, out);
continue;
}
out.push(tk);
}
return out;
};
const flat = flatten(toks);
const DECL_KW = new Set(['const', 'let', 'var']);
let inDeclarator = false;
for (let k = 0; k < flat.length; k++) {
const t = flat[k];
if (t.t === 'punc' && t.v === ';') { inDeclarator = false; continue; }
if (t.t !== 'id') continue;
const prevV = flat[k - 1] ? flat[k - 1].v : undefined;
const nextV = flat[k + 1] ? flat[k + 1].v : undefined;
if (DECL_KW.has(t.v)) { inDeclarator = true; continue; }
if (prevV === '.' || prevV === '?.') continue; // property access is not a reference
if (nextV === ':' && (prevV === '{' || prevV === ',')) continue; // object literal key
const isDeclName = prevV === 'function' || prevV === 'class' ||
prevV === 'async' || prevV === '*' ||
(inDeclarator && (prevV === ',' || DECL_KW.has(prevV ?? '') || flat[k - 1]?.t === 'id'));
if (isDeclName) continue;
referenced.add(t.v);
}
}
return { toks, imports, exports, decls, dynamicImports, topLevelStmts, statements, referenced };
}
function unquote(s) {
// only handle common no-escape cases; the rest delegate to JSON/native parsing
if (s[0] === '"' || s[0] === "'") {
const body = s.slice(1, -1);
if (!body.includes('\\')) return body;
return body.replace(/\\(.)/g, (_, c) => ({ n: '\n', t: '\t', r: '\r' }[c] ?? c));
}
return s;
}
/* ============ 3. Top-level side-effect determination ============ */
const BENIGN_TOP = new Set([';', 'const', 'let', 'var', 'function', 'class', 'async', 'import', 'export']);
/**
* Whether a module has top-level side effects (used for deciding if tree-shaking can drop the whole module).
* In the real world this is equivalent to the package.json sideEffects field, but can be derived from source.
*/
export function hasSideEffects(scan) {
for (const s of scan.topLevelStmts) {
if (!BENIGN_TOP.has(s)) return true;
}
return false;
}
fixtures.mjs — Test fixtures (multiple module-graph scenarios)
// fixtures.mjs — Fixture generators: deterministic synthetic projects + real ESM on disk (for differential comparison with native import)
export function mulberry32(seed) {
let a = seed >>> 0;
return () => {
a = (a + 0x6d2b79f5) >>> 0;
let t = a;
t = Math.imul(t ^ (t >>> 15), t | 1);
t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
/**
* Synthetic project:
* - N modules, each exports live_<i> / dead_<i>
* - Entry references only a fraction → the rest should be tree-shaken
* - Dependencies point to smaller indices (ensures no cycles, optionally create cycles)
*/
export function genProject({ modules = 100, liveRatio = 0.3, withCycles = false, seed = 7 } = {}) {
const rnd = mulberry32(seed);
const files = {};
const liveCount = Math.max(1, Math.round(modules * liveRatio));
for (let i = 0; i < modules; i++) {
const deps = [];
// each module references 1~3 smaller modules
const fanout = 1 + Math.floor(rnd() * 3);
for (let k = 0; k < fanout && i > 0; k++) {
const target = Math.floor(rnd() * i);
if (!deps.includes(target)) deps.push(target);
}
const lines = [];
for (const d of deps) lines.push(`import { live_${d} } from './m${d}.mjs';`);
lines.push(`export function live_${i}(x){`);
if (deps.length) {
lines.push(` let acc = x;`);
for (const d of deps) lines.push(` acc = acc + live_${d}(x | ${d});`);
lines.push(` return acc + ${i};`);
} else {
lines.push(` return x + ${i};`);
}
lines.push(`}`);
// dead code: an export never referenced, and not small
lines.push(`export function dead_${i}(x){`);
lines.push(` // this segment should disappear after bundling`);
lines.push(` const table = [${Array.from({ length: 8 }, (_, k) => `${i * 31 + k}`).join(', ')}];`);
lines.push(` return table.map((v) => v * x + ${i}).reduce((a, b) => a + b, 0);`);
lines.push(`}`);
files[`src/m${i}.mjs`] = lines.join('\n');
}
// entry: only reference the first liveCount modules
const entry = [];
const used = [];
for (let i = 0; i < liveCount; i++) {
entry.push(`import { live_${i} } from './m${i}.mjs';`);
used.push(i);
}
entry.push(`export const total = [${used.map((i) => `live_${i}(${i})`).join(', ')}].reduce((a, b) => a + b, 0);`);
files['src/main.mjs'] = entry.join('\n');
if (withCycles) {
// a ↔ b mutual import: function declarations hoist, valid at runtime
files['src/cyc/a.mjs'] = `import { b } from './b.mjs';\nexport function a(n){ return n <= 0 ? 'a' : 'a' + b(n - 1); }`;
files['src/cyc/b.mjs'] = `import { a } from './a.mjs';\nexport function b(n){ return n <= 0 ? 'b' : 'b' + a(n - 1); }`;
}
return files;
}
/** Small "real shape" project: for semantic differential comparison */
export function genSemanticProject() {
return {
'src/main.mjs': `
import { add, mul, ZERO } from './math.mjs';
import { label, PREFIX } from './str.mjs';
import * as all from './math.mjs';
import fmt from './fmt.mjs';
import './effect.mjs';
const composed = add(mul(2, 3), ZERO);
export const out1 = composed;
export const out2 = label(composed);
export const out3 = \`\${PREFIX}:\${fmt(composed)}\`;
export const out4 = all.mul(4, 5);
export const out5 = (() => {
// shadow variable: inner value shadows the same-name import
const value = 999;
return value;
})();
export const out6 = add(value0(), ZERO);
function value0(){ return 41; }
`,
'src/math.mjs': `
export const ZERO = 0;
export function add(a, b){ return a + b; }
export function mul(a, b){ return a * b; }
export function dead(){ return 'should be shaken'; }
`,
'src/str.mjs': `
import { add } from './math.mjs';
export const PREFIX = 'v';
export function label(n){
const { a, b } = { a: n, b: add(n, 1) };
return \`\${PREFIX}-\${a}-\${b}\`;
}
export function unusedLabel(){ return 'nope'; }
`,
'src/fmt.mjs': `
export default function fmt(n){ return '[' + n + ']'; }
`,
'src/effect.mjs': `
export const ignored = 1;
globalThis.__EFFECT_RAN__ = (globalThis.__EFFECT_RAN__ ?? 0) + 1;
`,
};
}
/** Re-export chains: export {} from / export * through multiple levels */
export function genReexportProject() {
return {
'src/main.mjs': `
import { add, real, deep } from './barrel.mjs';
export const r1 = add(1, 2);
export const r2 = real;
export const r3 = deep();
`,
'src/barrel.mjs': `
export { add } from './core.mjs';
export * from './extra.mjs';
export { deep } from './depth1.mjs';
`,
'src/core.mjs': `export function add(a, b){ return a + b; }`,
'src/extra.mjs': `export const real = 'REAL'; export const nope = 'NOPE';`,
'src/depth1.mjs': `export * from './depth2.mjs';`,
'src/depth2.mjs': `export function deep(){ return 'deep-value'; }`,
};
}
/** Modules with only side effects: their execution order must be preserved */
export function genSideEffectProject() {
return {
'src/main.mjs': `
import './a.mjs';
import './b.mjs';
import { read } from './store.mjs';
export const order = read();
`,
'src/a.mjs': `import { push } from './store.mjs';\npush('a');`,
'src/b.mjs': `import { push } from './store.mjs';\npush('b');`,
'src/store.mjs': `
const log = [];
export function push(x){ log.push(x); }
export function read(){ return log.join(','); }
`,
};
}
/** Various default-export forms + dynamic import */
export function genDefaultFormsProject() {
return {
'src/main.mjs': `
import expr, { cls, named, viaList } from './forms.mjs';
export const d1 = expr;
export const d2 = new cls(3).get();
export const d3 = named();
export const d4 = viaList;
`,
'src/forms.mjs': `
const base = { cls: class C { constructor(n){ this.n = n; } get(){ return this.n * 2; } } };
export default 6 * 7;
export const cls = base.cls;
export function named(){ return 'named-value'; }
function hidden(){ return 'via-list'; }
export { hidden as viaList };
`,
};
}
/** Write to a real file tree, for native import use */
export async function materialize(files, fsMod, pathMod, osMod) {
const dir = await fsMod.promises.mkdtemp(pathMod.join(osMod.tmpdir(), 'day35-'));
for (const [p, content] of Object.entries(files)) {
const full = pathMod.join(dir, p);
await fsMod.promises.mkdir(pathMod.dirname(full), { recursive: true });
await fsMod.promises.writeFile(full, content, 'utf8');
}
return dir;
}
/** Shuffle the write order of the virtual FS (simulate uncontrollable readdir order) */
export function shuffleEntries(files, seed = 1) {
const rnd = mulberry32(seed);
const arr = Object.entries(files);
for (let i = arr.length - 1; i > 0; i--) {
const j = Math.floor(rnd() * (i + 1));
[arr[i], arr[j]] = [arr[j], arr[i]];
}
return Object.fromEntries(arr);
}
test-bundler.mjs — Bundler assertions (artifact semantic equivalence, tree-shaking correctness)
// test-bundler.mjs — Assertions + differential comparison against native ESM
import assert from 'node:assert/strict';
import fs from 'node:fs';
import path from 'node:path';
import os from 'node:os';
import { pathToFileURL } from 'node:url';
import { tokenize, scanModule, hasSideEffects } from './scan.mjs';
import {
build, buildGraph, treeShake, planChunks, contentHash, createFS, resolveSpec, findCycles, topoOrder,
} from './build.mjs';
import {
genProject, genSemanticProject, genReexportProject, genSideEffectProject,
genDefaultFormsProject, materialize, shuffleEntries,
} from './fixtures.mjs';
let pass = 0, fail = 0;
const t = (name, fn) => {
try { fn(); pass++; }
catch (e) { fail++; console.error(`✗ ${name}\n ${e.message}`); }
};
const ta = async (name, fn) => {
try { await fn(); pass++; }
catch (e) { fail++; console.error(`✗ ${name}\n ${e.message}`); }
};
/* ---------- §1 Tokenizer ---------- */
t('regex vs division: / after if condition paren is regex', () => {
const tk = tokenize('if (a) /x/.test(y)');
assert.ok(tk.some((x) => x.t === 're' && x.v === '/x/'));
});
t('regex vs division: / after normal paren is division', () => {
const tk = tokenize('const r = (a + b) / 2 / c');
assert.ok(!tk.some((x) => x.t === 're'));
});
t('} inside regex does not break comment/string splitting', () => {
const tk = tokenize('function f(){ return /}/.test("}") }');
assert.equal(tk.filter((x) => x.t === 're').length, 1);
});
t('nested template interpolations are fully collected', () => {
const tk = tokenize('`a${ `b${c}` }d`');
const tpl = tk.find((x) => x.t === 'tpl');
assert.ok(tpl, 'not recognized as tpl');
// outer 1 interpolation + inner 1 nested
const count = (list) => list.reduce((n, tk) => {
if (tk.t !== 'tpl' || !tk.parts) return n;
return n + tk.parts.filter((p) => p.expr).length +
tk.parts.reduce((m, p) => m + (p.expr ? count(p.expr) : 0), 0);
}, 0);
assert.equal(count(tk), 2);
});
t('bigint / numeric separators', () => {
assert.equal(tokenize('1_000_000n')[0].v, '1_000_000n');
});
t('division followed by / comment is not misjudged as regex', () => {
const tk = tokenize('const a = b / c; // comment\n');
assert.equal(tk.filter((x) => x.t === 're').length, 0);
});
/* ---------- §2 Module syntax scanner ---------- */
t('import six forms', () => {
const m = scanModule(`
import d from './a.mjs';
import * as ns from './b.mjs';
import { x, y as z } from './c.mjs';
import d2, { p } from './d.mjs';
import d3, * as ns2 from './e.mjs';
import './f.mjs';`);
assert.equal(m.imports.length, 6);
assert.deepEqual(m.imports[0].specifiers, [{ imported: 'default', local: 'd' }]);
assert.deepEqual(m.imports[1].specifiers, [{ imported: '*', local: 'ns' }]);
assert.equal(m.imports[2].specifiers.length, 2);
assert.equal(m.imports[3].specifiers.length, 2);
assert.equal(m.imports[4].specifiers.length, 2);
assert.equal(m.imports[5].sideEffectOnly, true);
});
t('export seven forms', () => {
const m = scanModule(`
export const a = 1, b = 2;
export function f(){}
export class C {}
export default function g(){}
export { x as y };
export * from './r.mjs';
export * as ns from './s.mjs';`);
const names = m.exports.map((e) => e.exported);
assert.ok(names.includes('a') && names.includes('b'));
assert.ok(names.includes('f') && names.includes('C'));
assert.ok(names.includes('default') && names.includes('y'));
assert.ok(names.includes('*') && names.includes('ns'));
});
t('semicolon-less export function does not swallow subsequent statements', () => {
const m = scanModule("export function f(){}\nexport const K = 1;");
assert.ok(m.exports.some((e) => e.exported === 'K'), 'K lost → stmtEnd treated {} as a block');
});
t('the {} in import {a} from is not treated as a block', () => {
const m = scanModule("import { a } from './x.mjs';\nexport const K = 1;");
assert.equal(m.topLevelStmts.length, 0, `topLevelStmts=${JSON.stringify(m.topLevelStmts)}`);
});
t('dynamic import at any depth is caught', () => {
const m = scanModule(`function f(){ return import('./lazy.mjs'); }`);
assert.deepEqual(m.dynamicImports, ['./lazy.mjs']);
});
t('import.meta is not a dynamic import', () => {
const m = scanModule(`const u = import.meta.url;`);
assert.equal(m.dynamicImports.length, 0);
});
t('side-effect detection: assignment counts as side effect', () => {
assert.equal(hasSideEffects(scanModule('globalThis.x = 1;')), true);
assert.equal(hasSideEffects(scanModule('export const x = 1;')), false);
});
/* ---------- §3 Resolver ---------- */
t('extension probing + directory index', () => {
const fsm = createFS({ 'a/b.mjs': '', 'a/c/index.mjs': '', 'a/d.js': '' });
assert.equal(resolveSpec(fsm, 'a/main.mjs', './b'), 'a/b.mjs');
assert.equal(resolveSpec(fsm, 'a/main.mjs', './c'), 'a/c/index.mjs');
assert.equal(resolveSpec(fsm, 'a/main.mjs', './d'), 'a/d.js');
assert.equal(resolveSpec(fsm, 'a/main.mjs', './nope'), null);
});
t('.. path normalization', () => {
const fsm = createFS({ 'src/x.mjs': '' });
assert.equal(resolveSpec(fsm, 'src/deep/main.mjs', '../x.mjs'), 'src/x.mjs');
});
/* ---------- §4 Cycle detection and execution order ---------- */
t('Tarjan finds a↔b cycle', () => {
const files = genProject({ modules: 5, withCycles: true });
files['src/main.mjs'] += `\nimport { a } from './cyc/a.mjs';\nexport const cyc = a(3);`;
const g = buildGraph(createFS(files), 'src/main.mjs');
assert.equal(g.cycles.length, 1);
assert.equal(g.cycles[0].length, 2);
});
t('no-cycle project: dependencies come before dependents', () => {
const g = buildGraph(createFS(genProject({ modules: 8 })), 'src/main.mjs');
const pos = new Map(g.order.map((id, i) => [id, i]));
for (const m of g.modules) {
for (const d of m.deps) {
assert.ok(pos.get(d.targetId) < pos.get(m.id), `${m.path} should be after ${g.modules[d.targetId].path}`);
}
}
});
t('self-loop is also detected', () => {
const g = buildGraph(createFS({ 'a.mjs': `import { f } from './a.mjs'; export function f(){}` }), 'a.mjs');
assert.equal(g.cycles.length, 1);
});
/* ---------- §5 Tree-shaking ---------- */
t('unused exports are deleted', () => {
const r = build(genProject({ modules: 30, liveRatio: 0.2 }), 'src/main.mjs');
const code = r.chunks[0].code;
assert.ok(!/dead_0\b/.test(code), 'dead_0 should be removed');
assert.ok(/live_0/.test(code), 'live_0 should remain');
});
t('size actually drops (>=30%)', () => {
const r = build(genProject({ modules: 60, liveRatio: 0.25 }), 'src/main.mjs');
const drop = 1 - r.shake.stats.bytesKept / r.shake.stats.bytesTotal;
assert.ok(drop > 0.3, `drop only ${(drop * 100).toFixed(1)}%`);
});
t('side-effect module cannot be shaken', () => {
const r = build(genSideEffectProject(), 'src/main.mjs');
assert.ok(r.chunks[0].code.includes(`push('a')`), 'side-effect statement was removed');
});
/* ---------- §6 Differential: native ESM vs bundled output ---------- */
async function differential(name, files, opts = {}) {
const dir = await materialize(files, fs, path, os);
const native = await import(pathToFileURL(path.join(dir, 'src/main.mjs')).href + `?v=${Math.random()}`);
const r = build(files, 'src/main.mjs', { strategy: 'single', expose: '__ex' });
const bundled = new Function('__ex', r.chunks[0].code + '\nreturn __ex;')({});
const keysNative = Object.keys(native).filter((k) => k !== 'default');
const keysBundle = Object.keys(bundled);
for (const k of keysNative) {
const nv = native[k], bv = bundled[k];
// functions compared by reference is meaningless (two realms are two objects); compare the result of zero-arg call instead
if (typeof nv === 'function') {
assert.equal(typeof bv, 'function', `export ${k} should be function`);
let nr, br, nErr = null, bErr = null;
try { nr = String(nv()); } catch (e) { nErr = e.constructor.name; }
try { br = String(bv()); } catch (e) { bErr = e.constructor.name; }
assert.equal(bErr, nErr, `export ${k} throwing behavior differs`);
if (!nErr) assert.equal(br, nr, `export ${k}() result differs: bundled=${br} native=${nr}`);
continue;
}
assert.deepEqual(bv, nv, `export ${k} differs from native: bundled=${JSON.stringify(bv)} native=${JSON.stringify(nv)}`);
}
assert.deepEqual(keysBundle.sort(), keysNative.filter((k) => keysBundle.includes(k)).sort());
await fs.promises.rm(dir, { recursive: true, force: true });
void name; void opts;
return { native, bundled };
}
await ta('differential: normal project (shadow vars/destructuring/templates/namespace/side effects)', async () => {
await differential('semantic', genSemanticProject());
});
await ta('differential: re-export chain (export{} from + export * through two levels)', async () => {
const { native, bundled } = await differential('reexport', genReexportProject());
assert.equal(bundled.r3, native.r3);
assert.equal(bundled.r3, 'deep-value');
});
await ta('differential: side-effect order', async () => {
const { native, bundled } = await differential('side', genSideEffectProject());
assert.equal(bundled.order, native.order);
assert.equal(bundled.order, 'a,b');
});
await ta('differential: synthetic project 120 modules', async () => {
const files = genProject({ modules: 120, liveRatio: 0.3 });
const dir = await materialize(files, fs, path, os);
const native = await import(pathToFileURL(path.join(dir, 'src/main.mjs')).href + `?v=${Math.random()}`);
const r = build(files, 'src/main.mjs', { strategy: 'single', expose: '__ex' });
const bundled = new Function('__ex', r.chunks[0].code + '\nreturn __ex;')({});
assert.equal(bundled.total, native.total);
await fs.promises.rm(dir, { recursive: true, force: true });
});
await ta('differential: four forms of default export (expression/named class/named function/list renaming)', async () => {
const { native, bundled } = await differential('defaults', genDefaultFormsProject());
assert.equal(bundled.d1, 42);
assert.equal(bundled.d1, native.d1);
assert.equal(bundled.d2, 6);
assert.equal(bundled.d4(), 'via-list');
assert.equal(bundled.d3, 'named-value');
});
t('dynamic import is separately identified', () => {
const files = {
'src/main.mjs': `export const load = () => import('./lazy.mjs');`,
'src/lazy.mjs': `export const x = 1;`,
};
const r = build(files, 'src/main.mjs');
assert.deepEqual(r.graph.modules[0].scan.dynamicImports, ['./lazy.mjs']);
});
/* ---------- §7 Determinism ---------- */
t('shuffling file enumeration order does not change output hash', () => {
const files = genProject({ modules: 40 });
const a = build(files, 'src/main.mjs', { strategy: 'single' });
const b = build(shuffleEntries(files, 99), 'src/main.mjs', { strategy: 'single' });
assert.equal(a.chunks[0].hash, b.chunks[0].hash, 'output nondeterministic → caches keep failing in CI');
});
t('changing one byte always changes hash (no collision)', () => {
const files = genProject({ modules: 10 });
const a = build(files, 'src/main.mjs');
const files2 = { ...files };
files2['src/m0.mjs'] = files2['src/m0.mjs'].replace('x + 0', 'x + 1');
const b = build(files2, 'src/main.mjs');
assert.notEqual(a.chunks[0].hash, b.chunks[0].hash);
});
/* ---------- §8 Chunking and cache invalidation ---------- */
t('per-module strategy: changing one module invalidates only one chunk', () => {
const files = genProject({ modules: 20, liveRatio: 1 });
const before = build(files, 'src/main.mjs', { strategy: 'per-module' });
const files2 = { ...files };
files2['src/m0.mjs'] = files2['src/m0.mjs'].replace('x + 0', 'x + 1000');
const after = build(files2, 'src/main.mjs', { strategy: 'per-module' });
const changed = before.chunks.filter((c, i) => c.hash !== after.chunks[i]?.hash).length;
assert.equal(changed, 1, `should invalidate 1 chunk, actually ${changed}`);
});
t('single strategy: changing any module invalidates the whole chunk', () => {
const files = genProject({ modules: 20, liveRatio: 1 });
const before = build(files, 'src/main.mjs', { strategy: 'single' });
const files2 = { ...files };
files2['src/m0.mjs'] = files2['src/m0.mjs'].replace('x + 0', 'x + 1000');
const after = build(files2, 'src/main.mjs', { strategy: 'single' });
assert.notEqual(before.chunks[0].hash, after.chunks[0].hash);
});
/* ---------- §9 Hash itself ---------- */
t('contentHash known value + length', () => {
assert.equal(contentHash('').length, 16);
assert.equal(contentHash('abc'), contentHash('abc'));
assert.notEqual(contentHash('abc'), contentHash('abd'));
});
t('contentHash is per-char sensitive (FNV two-byte mixing)', () => {
assert.notEqual(contentHash('a\u0100'), contentHash('a\u0001'));
});
console.log(`\n${fail === 0 ? '✅' : '❌'} ${pass} passed / ${fail} failed`);
process.exit(fail === 0 ? 0 : 1);
bench.mjs — Benchmark main program (build time / output size comparison)
// bench.mjs — All numbers come from here. Pure measured on this machine (Node 22.23.3 / darwin-arm64)
import crypto from 'node:crypto';
import { tokenize, scanModule } from './scan.mjs';
import {
build, buildGraph, treeShake, link, planChunks, chunkCode,
contentHash, contentHashFast, createFS,
} from './build.mjs';
import { genProject, shuffleEntries, mulberry32 } from './fixtures.mjs';
const out = [];
const log = (s = '') => { out.push(s); console.log(s); };
const hr = () => Number(process.hrtime.bigint()) / 1e6;
function benchMs(fn, { warm = 3, runs = 9 } = {}) {
for (let i = 0; i < warm; i++) fn();
const xs = [];
for (let i = 0; i < runs; i++) { const t0 = hr(); fn(); xs.push(hr() - t0); }
xs.sort((a, b) => a - b);
return xs[Math.floor(xs.length / 2)];
}
const fmtB = (n) => (n >= 1024 * 1024 ? `${(n / 1024 / 1024).toFixed(2)}MB` : n >= 1024 ? `${(n / 1024).toFixed(1)}KB` : `${n}B`);
const pct = (a, b) => (b === 0 ? 'n/a' : `${((a / b) * 100).toFixed(1)}%`);
const mbps = (bytes, ms) => (ms === 0 ? 'inf' : (bytes / 1048576 / (ms / 1000)).toFixed(2));
const sizeOf = (files) => Object.values(files).reduce((a, s) => a + s.length, 0);
log(`# Day35 Build Tools · Measured data`);
log(`Environment: Node ${process.version} / ${process.platform}-${process.arch} / V8 ${process.versions.v8}`);
log('');
/* ================= §1 Scanning throughput and accuracy: real tokenizer vs regex approximation ================= */
log('## §1 Scanning throughput and accuracy: real tokenizer vs regex approximation');
function regexScan(src) {
const imports = [];
const re = /(?:^|\n)\s*import\s+([^'"`]*?)from\s*['"]([^'"]+)['"]/g;
let m;
while ((m = re.exec(src))) imports.push(m[2]);
const din = /import\s*\(\s*['"]([^'"]+)['"]\s*\)/g;
while ((m = din.exec(src))) imports.push(m[1]);
return { imports };
}
// disguised samples: fake import at "line start", and a stateless regex will take it as real
const tricky = [
["inside string (multi-line template)", "const t = `\nimport x from './fake-tpl.mjs'\n`;"],
["inside block comment", "/*\nimport y from './fake-block.mjs'\n*/"],
["inside regex literal", "const re = /\nimport z from '\\/fake-re.mjs'\n/;"],
].map(([label, src]) => [label, src]);
let trickyRegex = 0, trickyTok = 0, trickyTotal = 0;
for (const [label, src] of tricky) {
const r = regexScan(src).imports.length;
const t = scanModule(src).imports.length;
trickyRegex += r; trickyTok += t; trickyTotal++;
log(` ${label.padEnd(18)} regex reports ${r} fake edges, tokenizer reports ${t} edges`);
}
const realSrc = `import { a } from './a.mjs';\nexport function f(){ return a; }`;
log(` real sample regex ${regexScan(realSrc).imports.length} edges, tokenizer ${scanModule(realSrc).imports.length} edges (both correct)`);
log(` → regex's failure mode is not "slow", it's "treating text in comments/strings/regex as real edges", and it hits ${trickyRegex}/${trickyTotal} samples`);
log('');
const proj500 = genProject({ modules: 500, liveRatio: 0.3 });
const bytes500 = sizeOf(proj500);
const nMod = Object.keys(proj500).length;
const tTok = benchMs(() => { for (const src of Object.values(proj500)) tokenize(src); });
const tScan = benchMs(() => { for (const src of Object.values(proj500)) scanModule(src); });
const tRegex = benchMs(() => { for (const src of Object.values(proj500)) regexScan(src); });
log(` 500 modules / ${fmtB(bytes500)}:`);
log(` tokenize ${tTok.toFixed(2)}ms ${mbps(bytes500, tTok)} MB/s ${(nMod / (tTok / 1000)).toFixed(0)} modules/s`);
log(` scanModule ${tScan.toFixed(2)}ms ${mbps(bytes500, tScan)} MB/s ${(nMod / (tScan / 1000)).toFixed(0)} modules/s`);
log(` regex approx ${tRegex.toFixed(2)}ms ${mbps(bytes500, tRegex)} MB/s (fast ${(tScan / tRegex).toFixed(1)}x, cost above)`);
log('');
/* ---- §1b The tokenizer's true hot path: character classification ---- */
log('## §1b Tokenizer hot path: regex .test() vs charCode comparison');
{
const N = 2_000_000;
const sample = 'const abcdefg_123 = foo.bar(baz, 42);'.repeat(Math.ceil(N / 39)).slice(0, N);
const isIdPartRe = (c) => /[A-Za-z0-9_$]/.test(c);
const isIdPartCode = (c) => {
const x = c.charCodeAt(0);
return (x >= 48 && x <= 57) || (x >= 65 && x <= 90) || (x >= 97 && x <= 122) || x === 95 || x === 36;
};
const tRe = benchMs(() => { let k = 0; for (let i = 0; i < sample.length; i++) if (isIdPartRe(sample[i])) k++; return k; });
const tCode = benchMs(() => { let k = 0; for (let i = 0; i < sample.length; i++) if (isIdPartCode(sample[i])) k++; return k; });
log(` ${(N / 1e6).toFixed(0)}M char checks: regex .test() ${tRe.toFixed(1)}ms, charCode compare ${tCode.toFixed(1)}ms → fast ${(tRe / tCode).toFixed(1)}x`);
log(` → the 16 MB/s tokenizer bottleneck is here: each char creates a new regex matching context`);
}
log('');
/* ================= §2 Module graph size ================= */
log('## §2 Module graph build vs scale');
const graphRows = [];
for (const n of [200, 1000, 3000]) {
const files = genProject({ modules: n, liveRatio: 0.3 });
const bytes = sizeOf(files);
const ms = benchMs(() => buildGraph(createFS(files), 'src/main.mjs'), { warm: 1, runs: 5 });
const g = buildGraph(createFS(files), 'src/main.mjs');
const edges = g.modules.reduce((a, m) => a + m.deps.length, 0);
graphRows.push({ n, ms });
log(` ${String(n).padStart(4)} modules / ${fmtB(bytes).padStart(8)}: graph ${ms.toFixed(1)}ms, edges ${edges}, cycles ${g.cycles.length}`);
}
const per = graphRows.map((r) => r.ms / r.n);
log(` per-module amortized ${per.map((x) => x.toFixed(3)).join(' / ')} ms → ${per[2] < per[0] * 1.8 ? 'approximately linear (hash table + single DFS)' : 'superlinear'}`);
log('');
/* ================= §3 Tree-shaking gains ================= */
log('## §3 Tree-shaking: how much is removed');
for (const ratio of [0.1, 0.3, 0.6, 1.0]) {
const files = genProject({ modules: 300, liveRatio: ratio });
const r = build(files, 'src/main.mjs', { strategy: 'single' });
const naive = sizeOf(files);
const reach = r.graph.modules.length;
const present = Object.keys(files).filter((k) => k.startsWith('src/m')).length;
log(` liveRatio=${ratio.toFixed(1)} disk source ${fmtB(naive).padStart(8)} → output ${fmtB(r.chunks[0].code.length).padStart(7)} drop ${(100 - (r.chunks[0].code.length / naive) * 100).toFixed(1)}% (reachable ${reach}/${present} modules, not in graph ${present - reach})`);
}
log('');
/* ================= §4 Chunking strategy and cache invalidation blast radius ================= */
log('## §4 Changing one line of "live code" invalidates how many bytes of cache');
const baseFiles = genProject({ modules: 200, liveRatio: 0.7 });
const mutatedFiles = { ...baseFiles };
// Must change "live code that gets output": previously I mistakenly changed a literal in dead_3,
// output didn't change, and all strategies showed 0B invalidation — the kind of "looks like testing but isn't" pit most likely to get written into an article.
mutatedFiles['src/m3.mjs'] = mutatedFiles['src/m3.mjs'].replace('return acc + 3;', 'return acc + 3000;');
if (mutatedFiles['src/m3.mjs'] === baseFiles['src/m3.mjs']) throw new Error('mutation did not take effect');
for (const strategy of ['single', 'vendor', 'shared', 'per-module']) {
const a = build(baseFiles, 'src/main.mjs', { strategy });
const b = build(mutatedFiles, 'src/main.mjs', { strategy });
const total = a.chunks.reduce((x, c) => x + c.bytes, 0);
const byName = new Map(b.chunks.map((c) => [c.name, c]));
let invalidated = 0;
for (const c of a.chunks) {
const nc = byName.get(c.name);
if (!nc || nc.hash !== c.hash) invalidated += c.bytes;
}
log(` ${strategy.padEnd(11)} chunks ${String(a.chunks.length).padStart(3)} total ${fmtB(total).padStart(8)} must re-download ${fmtB(invalidated).padStart(8)} = ${pct(invalidated, total)}`);
}
log('');
/* ================= §5 Hash chaining ================= */
log('## §5 Hash: should it chain dependencies? (own-content vs chained)');
{
const a = build(baseFiles, 'src/main.mjs', { strategy: 'per-module' });
const b = build(mutatedFiles, 'src/main.mjs', { strategy: 'per-module' });
let ownBytes = 0;
for (let i = 0; i < a.chunks.length; i++) if (a.chunks[i].hash !== b.chunks[i]?.hash) ownBytes += a.chunks[i].bytes;
const gA = buildGraph(createFS(baseFiles), 'src/main.mjs');
const gB = buildGraph(createFS(mutatedFiles), 'src/main.mjs');
const chained = (chunks, mods) => {
const idx = new Map(chunks.map((c) => [Number(c.name.slice(1)), c]));
const memo = new Map();
const h = (id) => {
if (memo.has(id)) return memo.get(id);
const c = idx.get(id);
if (!c) return '';
const deps = [...new Set((mods[id]?.deps ?? []).map((d) => d.targetId).filter((x) => x != null))].sort((x, y) => x - y);
const v = contentHash(c.code + '|' + deps.map(h).join(''));
memo.set(id, v);
return v;
};
return h;
};
const hA = chained(a.chunks, gA.modules);
const hB = chained(b.chunks, gB.modules);
let chainBytes = 0;
const affected = [];
for (const c of a.chunks) {
const id = Number(c.name.slice(1));
if (hA(id) !== hB(id)) { chainBytes += c.bytes; affected.push(id); }
}
const total = a.chunks.reduce((x, c) => x + c.bytes, 0);
log(` change 1 leaf m3 → hash own only: invalidate ${fmtB(ownBytes)} (${pct(ownBytes, total)})`);
log(` chained hash: invalidate ${fmtB(chainBytes)} (${pct(chainBytes, total)}), affect ${affected.length} chunks`);
log(` blast radius amplified ${ownBytes ? (chainBytes / ownBytes).toFixed(2) : 'n/a'}x — chained hash buys "never serve stale artifacts", costs cache hit rate`);
}
log('');
/* ================= §6 Determinism ================= */
log('## §6 Determinism: does enum order change output');
{
const files = genProject({ modules: 200, liveRatio: 0.7 });
const runs = [1, 2, 3, 4, 5].map((seed) => build(shuffleEntries(files, seed), 'src/main.mjs').chunks[0].hash);
log(` this implementation (topo order) shuffle 5 times: ${new Set(runs).size === 1 ? 'hashes completely identical ✅' : 'hashes differ ❌'} ${runs[0]}`);
// counterexample: concatenate by "file enumeration order" (many hand-written build scripts do this)
const naive = (files2) => {
const fsx = createFS(files2);
const g = buildGraph(fsx, 'src/main.mjs');
const s = treeShake(g);
const l = link(g, s);
// note: use fsx.keys() (caller-provided insertion order) not g.order
const order = fsx.keys().map((p) => g.byPath.get(p)?.id).filter((id) => id != null && s.included.has(id));
return contentHash(order.map((id) => l.pieces.find((p) => p.modId === id)?.code ?? '').join('\n'));
};
const nruns = [1, 2, 3, 4, 5].map((seed) => naive(shuffleEntries(files, seed)));
log(` counterexample (by enum order): ${new Set(nruns).size} different hashes → content unchanged but filenames all change, CDN cache all invalid`);
}
log('');
/* ================= §7 Lexical renaming pit: template interpolation ================= */
log('## §7 Lexical renaming: not recursing template interpolation breaks how many');
{
const rnd = mulberry32(42);
const N = 400;
const files = {};
let withTpl = 0;
for (let i = 0; i < N; i++) {
const useTpl = rnd() < 0.5;
if (useTpl) withTpl++;
files[`src/m${i}.mjs`] = [
`export const name_${i} = 'v${i}';`,
useTpl
? `export function fmt_${i}(){ return \`<\${name_${i}}>\`; }`
: `export function fmt_${i}(){ return '<' + name_${i} + '>'; }`,
].join('\n');
}
const entry = [];
for (let i = 0; i < N; i++) entry.push(`import { fmt_${i} } from './m${i}.mjs';`);
entry.push(`export const all = [${Array.from({ length: N }, (_, i) => `fmt_${i}()`).join(', ')}];`);
files['src/main.mjs'] = entry.join('\n');
const r = build(files, 'src/main.mjs', { expose: '__ex' });
const ok = new Function('__ex', r.chunks[0].code + '\nreturn __ex;')({});
const good = ok.all.filter((s, i) => s === `<v${i}>`).length;
const brokenCode = r.chunks[0].code.replace(/\$\{m\d+\$(name_\d+)\}/g, '${$1}');
let brokenOk = 0, brokenErr = '';
try {
const b = new Function('__ex', brokenCode + '\nreturn __ex;')({});
brokenOk = b.all.filter((s, i) => s === `<v${i}>`).length;
} catch (e) { brokenOk = -1; brokenErr = e.constructor.name; }
log(` ${N} modules, ${withTpl} use template interpolation: correct implementation ${good}/${N} pass`);
log(` not recursing interpolation (\${name} stays original) → ${brokenOk === -1 ? `entire output throws ${brokenErr} (0/${N})` : `${brokenOk}/${N} pass`}`);
log(` → a 40-line function-level oversight explodes across ${withTpl} modules simultaneously, and only at runtime`);
}
log('');
/* ================= §8 Hash algorithms and speed ================= */
log('## §8 Content hashes: three implementations');
{
const payloads = Array.from({ length: 200 }, (_, i) => 'x'.repeat(1024) + i);
const bytes = payloads.reduce((a, p) => a + p.length, 0);
const tFnvBig = benchMs(() => { for (const p of payloads) contentHash(p); });
const tFnvFast = benchMs(() => { for (const p of payloads) contentHashFast(p); });
const tSha = benchMs(() => { for (const p of payloads) crypto.createHash('sha256').update(p).digest('hex'); });
log(` ${(bytes / 1024).toFixed(0)}KB / 200 chunks:`);
log(` FNV-1a 64 (BigInt per char) ${tFnvBig.toFixed(2)}ms ${mbps(bytes, tFnvBig)} MB/s`);
log(` FNV-1a ×2 32 (Math.imul) ${tFnvFast.toFixed(2)}ms ${mbps(bytes, tFnvFast)} MB/s ← fast ${(tFnvBig / tFnvFast).toFixed(1)}x`);
log(` sha256 (native OpenSSL) ${tSha.toFixed(2)}ms ${mbps(bytes, tSha)} MB/s ← again ${(tFnvFast / tSha).toFixed(1)}x faster than imul`);
log(` → hand-written BigInt hash is ${(tFnvBig / tSha).toFixed(1)}x slower than native sha256. "My own is faster" is an illusion`);
const base = 'a'.repeat(20000);
const variants = Array.from({ length: 2000 }, (_, i) => base + String.fromCharCode(97 + (i % 26)) + i);
log(` 2000 variants differing only at the end: BigInt version ${new Set(variants.map(contentHash)).size} different hashes, imul version ${new Set(variants.map(contentHashFast)).size}`);
}
log('');
/* ================= §9 Full pipeline time breakdown ================= */
log('## §9 Full pipeline time breakdown (3000 modules)');
{
const files = genProject({ modules: 3000, liveRatio: 0.4 });
const bytes = sizeOf(files);
// 3000 modules single run ~170ms, need enough warm and runs to avoid GC noise
const OPT = { warm: 3, runs: 15 };
const reachable = (() => {
const g0 = buildGraph(createFS(files), 'src/main.mjs');
return g0.modules.map((m) => m.source);
})();
// baseline alignment: lex benchmark only runs reachable modules, otherwise comparing all 3001 files against 1201 is meaningless
const tLex = benchMs(() => { for (const src of reachable) tokenize(src); }, OPT);
const tGraph = benchMs(() => buildGraph(createFS(files), 'src/main.mjs'), OPT);
const g = buildGraph(createFS(files), 'src/main.mjs');
const tShake = benchMs(() => treeShake(g), OPT);
const s = treeShake(g);
const tLink = benchMs(() => link(g, s), OPT);
const l = link(g, s);
const tHash = benchMs(() => contentHash(l.code), OPT);
const total = tGraph + tShake + tLink + tHash;
log(` source ${fmtB(bytes)} → output ${fmtB(l.stats.bytes)}`);
log(` graph (incl scan) ${tGraph.toFixed(1)}ms (${pct(tGraph, total)}) shake ${tShake.toFixed(1)}ms (${pct(tShake, total)}) link ${tLink.toFixed(1)}ms (${pct(tLink, total)}) hash ${tHash.toFixed(2)}ms (${pct(tHash, total)})`);
log(` total ${total.toFixed(1)}ms; of which pure lexing ${tLex.toFixed(1)}ms = ${pct(tLex, total)} of whole pipeline`);
log(` baseline: entry references only 40% modules, so among ${Object.keys(files).length} files on disk only ${reachable.length} enter the graph and get parsed`);
log(` self-consistency check (same ${reachable.length} modules): graph ${tGraph.toFixed(1)}ms >= pure lex ${tLex.toFixed(1)}ms ? ${tGraph >= tLex ? '✅ graph = lex + parse + resolve deps' : '❌ noisy sample'}`);
log(` → lex/parse is the lower bound; only a faster parser gives an order-of-magnitude gain`);
}
log('');
/* ---- §9b Linking stage: one O(statements×tokens) to O(token) ---- */
log('## §9b Linking stage: statements×tokens double loop vs single pass');
{
const files = genProject({ modules: 3000, liveRatio: 0.4 });
const g = buildGraph(createFS(files), 'src/main.mjs');
const sh = treeShake(g);
const OPT2 = { warm: 2, runs: 11 };
const tFast = benchMs(() => link(g, sh), OPT2);
const tNaive = benchMs(() => link(g, sh, { emitter: 'naive' }), OPT2);
const lF = link(g, sh), lN = link(g, sh, { emitter: 'naive' });
log(` single pass (current) ${tFast.toFixed(1)}ms`);
log(` statements×tokens double loop ${tNaive.toFixed(1)}ms → slow ${(tNaive / tFast).toFixed(2)}x`);
log(` outputs identical? ${lF.code === lN.code ? '✅ byte-identical' : '❌ differ (optimization changed behavior, unacceptable)'}`);
log(` → semantics exactly same, only because "rescan all tokens for each statement", it goes from ${tFast.toFixed(0)}ms to ${tNaive.toFixed(0)}ms`);
}
log('');
/* ================= §10 Incremental rebuild ================= */
log('## §10 Incremental: change 1 file, full rescan vs scan cache');
{
const N = 3000;
const files = genProject({ modules: N, liveRatio: 0.4 });
const cached = new Map();
const files2 = { ...files };
files2['src/m3.mjs'] = files2['src/m3.mjs'].replace('return acc + 3;', 'return acc + 3000;');
// cold start: cache empty → rescan everything
const coldMs = benchMs(() => {
const c = new Map();
build(files2, 'src/main.mjs', { cache: c });
}, { warm: 2, runs: 7 });
// incremental: cache warmed to "only m3 changed"
const warmMs = benchMs(() => {
const c = new Map();
build(files, 'src/main.mjs', { cache: c }); // prewarm
build(files2, 'src/main.mjs', { cache: c }); // only rescan m3
}, { warm: 1, runs: 7 }) - coldMs;
const coldStat = (() => { const c = new Map(); return build(files2, 'src/main.mjs', { cache: c }).graph.scanStats; })();
const warmStat = (() => { const c = new Map(); build(files, 'src/main.mjs', { cache: c }); return build(files2, 'src/main.mjs', { cache: c }).graph.scanStats; })();
log(` cold start ${coldMs.toFixed(0)}ms (scan ${coldStat.cacheMiss} modules, hit ${coldStat.cacheHit})`);
log(` incremental ${warmMs.toFixed(0)}ms (scan ${warmStat.cacheMiss} modules, hit ${warmStat.cacheHit})`);
log(` speedup ${(coldMs / warmMs).toFixed(1)}x — but note the remaining time does not go to zero`);
log(` remaining ${warmMs.toFixed(0)}ms all spent on "traverse whole graph for shake + reassemble + rehash": module-level cache can save parsing, but cannot save graph traversal`);
log(` → to get truly O(change) incremental, you need to make linking incremental too (Vite uses ESM to avoid bundling entirely, Turbopack uses chunk-level incremental)`);
void N;
}
log('');
/* ================= §11 Side-effect cost ================= */
log('## §11 Side-effect modules: conservative judgment cost');
{
const mk = (withEffect) => {
const files2 = genProject({ modules: 100, liveRatio: 0.3 });
if (withEffect) {
for (const k of Object.keys(files2)) {
if (k === 'src/main.mjs') continue;
files2[k] += `\nglobalThis.__t = (globalThis.__t ?? 0) + 1;`;
}
}
return files2;
};
const clean = build(mk(false), 'src/main.mjs');
const dirty = build(mk(true), 'src/main.mjs');
log(` clean modules (can shake entire module) output ${fmtB(clean.chunks[0].bytes)}`);
log(` each module adds one top-level side effect → output ${fmtB(dirty.chunks[0].bytes)}, amplified ${(dirty.chunks[0].bytes / clean.chunks[0].bytes).toFixed(2)}x`);
log(` → that's the real value of package.json "sideEffects": false, and the reason misconfiguring it causes production failures`);
}
log('');
log('---');
log(`total ${out.length} lines. Every number above is measured live by this file, none hand-filled.`);
extract-and-test.mjs — Extract code blocks from article and self-check
// extract-and-test.mjs — Pull out each ```js block from the article and syntax-check it
// Purpose: article code must not be "looks like code". Every extracted block must be parseable by Node.
import fs from 'node:fs';
import path from 'node:path';
import os from 'node:os';
import { execFileSync } from 'node:child_process';
// compatible with two layouts: md in same dir (dev) or md in parent (after publishing, md and day35-assets/ are separate)
const here = path.dirname(new URL(import.meta.url).pathname);
const candidates = [
path.join(here, 'Day35-构建工具.md'),
path.join(here, '..', 'Day35-构建工具.md'),
process.argv[2],
].filter(Boolean);
const mdPath = candidates.find((p) => fs.existsSync(p));
if (!mdPath) {
console.error('Cannot find Day35-构建工具.md, tried: ', candidates.join(', '));
process.exit(1);
}
const md = fs.readFileSync(mdPath, 'utf8');
console.log(`article: ${mdPath}`);
// extract ```js / ```javascript fences
const blocks = [];
const re = /```(?:js|javascript)\n([\s\S]*?)```/g;
let m;
while ((m = re.exec(md))) {
const before = md.slice(0, m.index);
const line = before.split('\n').length;
blocks.push({ code: m[1], line });
}
const dir = fs.mkdtempSync(path.join(os.tmpdir(), 'day35-extract-'));
let ok = 0, bad = 0;
blocks.forEach((b, i) => {
const file = path.join(dir, `block${i}.mjs`);
fs.writeFileSync(file, b.code, 'utf8');
try {
execFileSync(process.execPath, ['--check', file], { stdio: 'pipe' });
ok++;
console.log(`✓ block#${i} (line ${b.line} in article, ${b.code.split('\n').length} lines)`);
} catch (e) {
bad++;
console.error(`✗ block#${i} (line ${b.line} in article)`);
console.error(String(e.stderr ?? e.message).split('\n').slice(0, 6).join('\n'));
}
});
fs.rmSync(dir, { recursive: true, force: true });
// also check the article's self-declared number baselines
const zh = (md.match(/[\u4e00-\u9fa5]/g) ?? []).length;
const tables = md.split('\n').filter((l) => l.trim().startsWith('|')).length;
console.log('');
console.log(`article: ${zh} Chinese chars / ${md.length} bytes / ${md.split('\n').length} lines / ${blocks.length} js blocks / ${tables} table lines`);
console.log(`code block syntax check: ${ok} passed / ${bad} failed`);
console.log(zh >= 1500 ? `✅ article meets 1500-char requirement (${zh})` : `❌ article below 1500 chars (${zh})`);
process.exit(bad === 0 && zh >= 1500 ? 0 : 1);