buildChunkGraph.js 45 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418
  1. /*
  2. MIT License http://www.opensource.org/licenses/mit-license.php
  3. Author Tobias Koppers @sokra
  4. */
  5. "use strict";
  6. const AsyncDependencyToInitialChunkError = require("./AsyncDependencyToInitialChunkError");
  7. const { connectChunkGroupParentAndChild } = require("./GraphHelpers");
  8. const ModuleGraphConnection = require("./ModuleGraphConnection");
  9. const { getEntryRuntime, mergeRuntime } = require("./util/runtime");
  10. /** @typedef {import("./AsyncDependenciesBlock")} AsyncDependenciesBlock */
  11. /** @typedef {import("./Chunk")} Chunk */
  12. /** @typedef {import("./ChunkGroup")} ChunkGroup */
  13. /** @typedef {import("./Compilation")} Compilation */
  14. /** @typedef {import("./DependenciesBlock")} DependenciesBlock */
  15. /** @typedef {import("./Dependency")} Dependency */
  16. /** @typedef {import("./Dependency").DependencyLocation} DependencyLocation */
  17. /** @typedef {import("./Entrypoint")} Entrypoint */
  18. /** @typedef {import("./Module")} Module */
  19. /** @typedef {import("./ModuleGraph")} ModuleGraph */
  20. /** @typedef {import("./ModuleGraphConnection").ConnectionState} ConnectionState */
  21. /** @typedef {import("./logging/Logger").Logger} Logger */
  22. /** @typedef {import("./util/runtime").RuntimeSpec} RuntimeSpec */
  23. /**
  24. * @typedef {Object} QueueItem
  25. * @property {number} action
  26. * @property {DependenciesBlock} block
  27. * @property {Module} module
  28. * @property {Chunk} chunk
  29. * @property {ChunkGroup} chunkGroup
  30. * @property {ChunkGroupInfo} chunkGroupInfo
  31. */
  32. /** @typedef {Set<Module> & { plus: Set<Module> }} ModuleSetPlus */
  33. /**
  34. * @typedef {Object} ChunkGroupInfo
  35. * @property {ChunkGroup} chunkGroup the chunk group
  36. * @property {RuntimeSpec} runtime the runtimes
  37. * @property {ModuleSetPlus | undefined} minAvailableModules current minimal set of modules available at this point
  38. * @property {boolean | undefined} minAvailableModulesOwned true, if minAvailableModules is owned and can be modified
  39. * @property {ModuleSetPlus[]} availableModulesToBeMerged enqueued updates to the minimal set of available modules
  40. * @property {Set<Module>=} skippedItems modules that were skipped because module is already available in parent chunks (need to reconsider when minAvailableModules is shrinking)
  41. * @property {Set<[Module, ConnectionState]>=} skippedModuleConnections referenced modules that where skipped because they were not active in this runtime
  42. * @property {ModuleSetPlus | undefined} resultingAvailableModules set of modules available including modules from this chunk group
  43. * @property {Set<ChunkGroupInfo> | undefined} children set of children chunk groups, that will be revisited when availableModules shrink
  44. * @property {Set<ChunkGroupInfo> | undefined} availableSources set of chunk groups that are the source for minAvailableModules
  45. * @property {Set<ChunkGroupInfo> | undefined} availableChildren set of chunk groups which depend on the this chunk group as availableSource
  46. * @property {number} preOrderIndex next pre order index
  47. * @property {number} postOrderIndex next post order index
  48. * @property {boolean} chunkLoading has a chunk loading mechanism
  49. * @property {boolean} asyncChunks create async chunks
  50. */
  51. /**
  52. * @typedef {Object} BlockChunkGroupConnection
  53. * @property {ChunkGroupInfo} originChunkGroupInfo origin chunk group
  54. * @property {ChunkGroup} chunkGroup referenced chunk group
  55. */
  56. const EMPTY_SET = /** @type {ModuleSetPlus} */ (new Set());
  57. EMPTY_SET.plus = EMPTY_SET;
  58. /**
  59. * @param {ModuleSetPlus} a first set
  60. * @param {ModuleSetPlus} b second set
  61. * @returns {number} cmp
  62. */
  63. const bySetSize = (a, b) => {
  64. return b.size + b.plus.size - a.size - a.plus.size;
  65. };
  66. const extractBlockModules = (module, moduleGraph, runtime, blockModulesMap) => {
  67. let blockCache;
  68. let modules;
  69. const arrays = [];
  70. const queue = [module];
  71. while (queue.length > 0) {
  72. const block = queue.pop();
  73. const arr = [];
  74. arrays.push(arr);
  75. blockModulesMap.set(block, arr);
  76. for (const b of block.blocks) {
  77. queue.push(b);
  78. }
  79. }
  80. for (const connection of moduleGraph.getOutgoingConnections(module)) {
  81. const d = connection.dependency;
  82. // We skip connections without dependency
  83. if (!d) continue;
  84. const m = connection.module;
  85. // We skip connections without Module pointer
  86. if (!m) continue;
  87. // We skip weak connections
  88. if (connection.weak) continue;
  89. const state = connection.getActiveState(runtime);
  90. // We skip inactive connections
  91. if (state === false) continue;
  92. const block = moduleGraph.getParentBlock(d);
  93. let index = moduleGraph.getParentBlockIndex(d);
  94. // deprecated fallback
  95. if (index < 0) {
  96. index = block.dependencies.indexOf(d);
  97. }
  98. if (blockCache !== block) {
  99. modules = blockModulesMap.get((blockCache = block));
  100. }
  101. const i = index << 2;
  102. modules[i] = m;
  103. modules[i + 1] = state;
  104. }
  105. for (const modules of arrays) {
  106. if (modules.length === 0) continue;
  107. let indexMap;
  108. let length = 0;
  109. outer: for (let j = 0; j < modules.length; j += 2) {
  110. const m = modules[j];
  111. if (m === undefined) continue;
  112. const state = modules[j + 1];
  113. if (indexMap === undefined) {
  114. let i = 0;
  115. for (; i < length; i += 2) {
  116. if (modules[i] === m) {
  117. const merged = modules[i + 1];
  118. if (merged === true) continue outer;
  119. modules[i + 1] = ModuleGraphConnection.addConnectionStates(
  120. merged,
  121. state
  122. );
  123. }
  124. }
  125. modules[length] = m;
  126. length++;
  127. modules[length] = state;
  128. length++;
  129. if (length > 30) {
  130. // To avoid worse case performance, we will use an index map for
  131. // linear cost access, which allows to maintain O(n) complexity
  132. // while keeping allocations down to a minimum
  133. indexMap = new Map();
  134. for (let i = 0; i < length; i += 2) {
  135. indexMap.set(modules[i], i + 1);
  136. }
  137. }
  138. } else {
  139. const idx = indexMap.get(m);
  140. if (idx !== undefined) {
  141. const merged = modules[idx];
  142. if (merged === true) continue outer;
  143. modules[idx] = ModuleGraphConnection.addConnectionStates(
  144. merged,
  145. state
  146. );
  147. } else {
  148. modules[length] = m;
  149. length++;
  150. modules[length] = state;
  151. indexMap.set(m, length);
  152. length++;
  153. }
  154. }
  155. }
  156. modules.length = length;
  157. }
  158. };
  159. /**
  160. *
  161. * @param {Logger} logger a logger
  162. * @param {Compilation} compilation the compilation
  163. * @param {Map<Entrypoint, Module[]>} inputEntrypointsAndModules chunk groups which are processed with the modules
  164. * @param {Map<ChunkGroup, ChunkGroupInfo>} chunkGroupInfoMap mapping from chunk group to available modules
  165. * @param {Map<AsyncDependenciesBlock, BlockChunkGroupConnection[]>} blockConnections connection for blocks
  166. * @param {Set<DependenciesBlock>} blocksWithNestedBlocks flag for blocks that have nested blocks
  167. * @param {Set<ChunkGroup>} allCreatedChunkGroups filled with all chunk groups that are created here
  168. */
  169. const visitModules = (
  170. logger,
  171. compilation,
  172. inputEntrypointsAndModules,
  173. chunkGroupInfoMap,
  174. blockConnections,
  175. blocksWithNestedBlocks,
  176. allCreatedChunkGroups
  177. ) => {
  178. const { moduleGraph, chunkGraph, moduleMemCaches } = compilation;
  179. const blockModulesRuntimeMap = new Map();
  180. /** @type {RuntimeSpec | false} */
  181. let blockModulesMapRuntime = false;
  182. /** @type {Map<DependenciesBlock, (Module | ConnectionState)[]>} */
  183. let blockModulesMap;
  184. /**
  185. *
  186. * @param {DependenciesBlock} block block
  187. * @param {RuntimeSpec} runtime runtime
  188. * @returns {(Module | ConnectionState)[]} block modules in flatten tuples
  189. */
  190. const getBlockModules = (block, runtime) => {
  191. if (blockModulesMapRuntime !== runtime) {
  192. blockModulesMap = blockModulesRuntimeMap.get(runtime);
  193. if (blockModulesMap === undefined) {
  194. blockModulesMap = new Map();
  195. blockModulesRuntimeMap.set(runtime, blockModulesMap);
  196. }
  197. }
  198. let blockModules = blockModulesMap.get(block);
  199. if (blockModules !== undefined) return blockModules;
  200. const module = /** @type {Module} */ (block.getRootBlock());
  201. const memCache = moduleMemCaches && moduleMemCaches.get(module);
  202. if (memCache !== undefined) {
  203. const map = memCache.provide(
  204. "bundleChunkGraph.blockModules",
  205. runtime,
  206. () => {
  207. logger.time("visitModules: prepare");
  208. const map = new Map();
  209. extractBlockModules(module, moduleGraph, runtime, map);
  210. logger.timeAggregate("visitModules: prepare");
  211. return map;
  212. }
  213. );
  214. for (const [block, blockModules] of map)
  215. blockModulesMap.set(block, blockModules);
  216. return map.get(block);
  217. } else {
  218. logger.time("visitModules: prepare");
  219. extractBlockModules(module, moduleGraph, runtime, blockModulesMap);
  220. blockModules = blockModulesMap.get(block);
  221. logger.timeAggregate("visitModules: prepare");
  222. return /** @type {(Module | ConnectionState)[]} */ (blockModules);
  223. }
  224. };
  225. let statProcessedQueueItems = 0;
  226. let statProcessedBlocks = 0;
  227. let statConnectedChunkGroups = 0;
  228. let statProcessedChunkGroupsForMerging = 0;
  229. let statMergedAvailableModuleSets = 0;
  230. let statForkedAvailableModules = 0;
  231. let statForkedAvailableModulesCount = 0;
  232. let statForkedAvailableModulesCountPlus = 0;
  233. let statForkedMergedModulesCount = 0;
  234. let statForkedMergedModulesCountPlus = 0;
  235. let statForkedResultModulesCount = 0;
  236. let statChunkGroupInfoUpdated = 0;
  237. let statChildChunkGroupsReconnected = 0;
  238. let nextChunkGroupIndex = 0;
  239. let nextFreeModulePreOrderIndex = 0;
  240. let nextFreeModulePostOrderIndex = 0;
  241. /** @type {Map<DependenciesBlock, ChunkGroupInfo>} */
  242. const blockChunkGroups = new Map();
  243. /** @type {Map<string, ChunkGroupInfo>} */
  244. const namedChunkGroups = new Map();
  245. /** @type {Map<string, ChunkGroupInfo>} */
  246. const namedAsyncEntrypoints = new Map();
  247. const ADD_AND_ENTER_ENTRY_MODULE = 0;
  248. const ADD_AND_ENTER_MODULE = 1;
  249. const ENTER_MODULE = 2;
  250. const PROCESS_BLOCK = 3;
  251. const PROCESS_ENTRY_BLOCK = 4;
  252. const LEAVE_MODULE = 5;
  253. /** @type {QueueItem[]} */
  254. let queue = [];
  255. /** @type {Map<ChunkGroupInfo, Set<ChunkGroupInfo>>} */
  256. const queueConnect = new Map();
  257. /** @type {Set<ChunkGroupInfo>} */
  258. const chunkGroupsForCombining = new Set();
  259. // Fill queue with entrypoint modules
  260. // Create ChunkGroupInfo for entrypoints
  261. for (const [chunkGroup, modules] of inputEntrypointsAndModules) {
  262. const runtime = getEntryRuntime(
  263. compilation,
  264. /** @type {string} */ (chunkGroup.name),
  265. chunkGroup.options
  266. );
  267. /** @type {ChunkGroupInfo} */
  268. const chunkGroupInfo = {
  269. chunkGroup,
  270. runtime,
  271. minAvailableModules: undefined,
  272. minAvailableModulesOwned: false,
  273. availableModulesToBeMerged: [],
  274. skippedItems: undefined,
  275. resultingAvailableModules: undefined,
  276. children: undefined,
  277. availableSources: undefined,
  278. availableChildren: undefined,
  279. preOrderIndex: 0,
  280. postOrderIndex: 0,
  281. chunkLoading:
  282. chunkGroup.options.chunkLoading !== undefined
  283. ? chunkGroup.options.chunkLoading !== false
  284. : compilation.outputOptions.chunkLoading !== false,
  285. asyncChunks:
  286. chunkGroup.options.asyncChunks !== undefined
  287. ? chunkGroup.options.asyncChunks
  288. : compilation.outputOptions.asyncChunks !== false
  289. };
  290. chunkGroup.index = nextChunkGroupIndex++;
  291. if (chunkGroup.getNumberOfParents() > 0) {
  292. // minAvailableModules for child entrypoints are unknown yet, set to undefined.
  293. // This means no module is added until other sets are merged into
  294. // this minAvailableModules (by the parent entrypoints)
  295. const skippedItems = new Set();
  296. for (const module of modules) {
  297. skippedItems.add(module);
  298. }
  299. chunkGroupInfo.skippedItems = skippedItems;
  300. chunkGroupsForCombining.add(chunkGroupInfo);
  301. } else {
  302. // The application may start here: We start with an empty list of available modules
  303. chunkGroupInfo.minAvailableModules = EMPTY_SET;
  304. const chunk = chunkGroup.getEntrypointChunk();
  305. for (const module of modules) {
  306. queue.push({
  307. action: ADD_AND_ENTER_MODULE,
  308. block: module,
  309. module,
  310. chunk,
  311. chunkGroup,
  312. chunkGroupInfo
  313. });
  314. }
  315. }
  316. chunkGroupInfoMap.set(chunkGroup, chunkGroupInfo);
  317. if (chunkGroup.name) {
  318. namedChunkGroups.set(chunkGroup.name, chunkGroupInfo);
  319. }
  320. }
  321. // Fill availableSources with parent-child dependencies between entrypoints
  322. for (const chunkGroupInfo of chunkGroupsForCombining) {
  323. const { chunkGroup } = chunkGroupInfo;
  324. chunkGroupInfo.availableSources = new Set();
  325. for (const parent of chunkGroup.parentsIterable) {
  326. const parentChunkGroupInfo =
  327. /** @type {ChunkGroupInfo} */
  328. (chunkGroupInfoMap.get(parent));
  329. chunkGroupInfo.availableSources.add(parentChunkGroupInfo);
  330. if (parentChunkGroupInfo.availableChildren === undefined) {
  331. parentChunkGroupInfo.availableChildren = new Set();
  332. }
  333. parentChunkGroupInfo.availableChildren.add(chunkGroupInfo);
  334. }
  335. }
  336. // pop() is used to read from the queue
  337. // so it need to be reversed to be iterated in
  338. // correct order
  339. queue.reverse();
  340. /** @type {Set<ChunkGroupInfo>} */
  341. const outdatedChunkGroupInfo = new Set();
  342. /** @type {Set<ChunkGroupInfo>} */
  343. const chunkGroupsForMerging = new Set();
  344. /** @type {QueueItem[]} */
  345. let queueDelayed = [];
  346. /** @type {[Module, ConnectionState][]} */
  347. const skipConnectionBuffer = [];
  348. /** @type {Module[]} */
  349. const skipBuffer = [];
  350. /** @type {QueueItem[]} */
  351. const queueBuffer = [];
  352. /** @type {Module} */
  353. let module;
  354. /** @type {Chunk} */
  355. let chunk;
  356. /** @type {ChunkGroup} */
  357. let chunkGroup;
  358. /** @type {DependenciesBlock} */
  359. let block;
  360. /** @type {ChunkGroupInfo} */
  361. let chunkGroupInfo;
  362. // For each async Block in graph
  363. /**
  364. * @param {AsyncDependenciesBlock} b iterating over each Async DepBlock
  365. * @returns {void}
  366. */
  367. const iteratorBlock = b => {
  368. // 1. We create a chunk group with single chunk in it for this Block
  369. // but only once (blockChunkGroups map)
  370. let cgi = blockChunkGroups.get(b);
  371. /** @type {ChunkGroup | undefined} */
  372. let c;
  373. /** @type {Entrypoint | undefined} */
  374. let entrypoint;
  375. const entryOptions = b.groupOptions && b.groupOptions.entryOptions;
  376. if (cgi === undefined) {
  377. const chunkName = (b.groupOptions && b.groupOptions.name) || b.chunkName;
  378. if (entryOptions) {
  379. cgi = namedAsyncEntrypoints.get(/** @type {string} */ (chunkName));
  380. if (!cgi) {
  381. entrypoint = compilation.addAsyncEntrypoint(
  382. entryOptions,
  383. module,
  384. b.loc,
  385. b.request
  386. );
  387. entrypoint.index = nextChunkGroupIndex++;
  388. cgi = {
  389. chunkGroup: entrypoint,
  390. runtime: entrypoint.options.runtime || entrypoint.name,
  391. minAvailableModules: EMPTY_SET,
  392. minAvailableModulesOwned: false,
  393. availableModulesToBeMerged: [],
  394. skippedItems: undefined,
  395. resultingAvailableModules: undefined,
  396. children: undefined,
  397. availableSources: undefined,
  398. availableChildren: undefined,
  399. preOrderIndex: 0,
  400. postOrderIndex: 0,
  401. chunkLoading:
  402. entryOptions.chunkLoading !== undefined
  403. ? entryOptions.chunkLoading !== false
  404. : chunkGroupInfo.chunkLoading,
  405. asyncChunks:
  406. entryOptions.asyncChunks !== undefined
  407. ? entryOptions.asyncChunks
  408. : chunkGroupInfo.asyncChunks
  409. };
  410. chunkGroupInfoMap.set(entrypoint, cgi);
  411. chunkGraph.connectBlockAndChunkGroup(b, entrypoint);
  412. if (chunkName) {
  413. namedAsyncEntrypoints.set(chunkName, cgi);
  414. }
  415. } else {
  416. entrypoint = /** @type {Entrypoint} */ (cgi.chunkGroup);
  417. // TODO merge entryOptions
  418. entrypoint.addOrigin(module, b.loc, b.request);
  419. chunkGraph.connectBlockAndChunkGroup(b, entrypoint);
  420. }
  421. // 2. We enqueue the DependenciesBlock for traversal
  422. queueDelayed.push({
  423. action: PROCESS_ENTRY_BLOCK,
  424. block: b,
  425. module: module,
  426. chunk: entrypoint.chunks[0],
  427. chunkGroup: entrypoint,
  428. chunkGroupInfo: cgi
  429. });
  430. } else if (!chunkGroupInfo.asyncChunks || !chunkGroupInfo.chunkLoading) {
  431. // Just queue the block into the current chunk group
  432. queue.push({
  433. action: PROCESS_BLOCK,
  434. block: b,
  435. module: module,
  436. chunk,
  437. chunkGroup,
  438. chunkGroupInfo
  439. });
  440. } else {
  441. cgi = chunkName && namedChunkGroups.get(chunkName);
  442. if (!cgi) {
  443. c = compilation.addChunkInGroup(
  444. b.groupOptions || b.chunkName,
  445. module,
  446. b.loc,
  447. b.request
  448. );
  449. c.index = nextChunkGroupIndex++;
  450. cgi = {
  451. chunkGroup: c,
  452. runtime: chunkGroupInfo.runtime,
  453. minAvailableModules: undefined,
  454. minAvailableModulesOwned: undefined,
  455. availableModulesToBeMerged: [],
  456. skippedItems: undefined,
  457. resultingAvailableModules: undefined,
  458. children: undefined,
  459. availableSources: undefined,
  460. availableChildren: undefined,
  461. preOrderIndex: 0,
  462. postOrderIndex: 0,
  463. chunkLoading: chunkGroupInfo.chunkLoading,
  464. asyncChunks: chunkGroupInfo.asyncChunks
  465. };
  466. allCreatedChunkGroups.add(c);
  467. chunkGroupInfoMap.set(c, cgi);
  468. if (chunkName) {
  469. namedChunkGroups.set(chunkName, cgi);
  470. }
  471. } else {
  472. c = cgi.chunkGroup;
  473. if (c.isInitial()) {
  474. compilation.errors.push(
  475. new AsyncDependencyToInitialChunkError(
  476. /** @type {string} */ (chunkName),
  477. module,
  478. b.loc
  479. )
  480. );
  481. c = chunkGroup;
  482. } else {
  483. c.addOptions(b.groupOptions);
  484. }
  485. c.addOrigin(module, b.loc, b.request);
  486. }
  487. blockConnections.set(b, []);
  488. }
  489. blockChunkGroups.set(b, /** @type {ChunkGroupInfo} */ (cgi));
  490. } else if (entryOptions) {
  491. entrypoint = /** @type {Entrypoint} */ (cgi.chunkGroup);
  492. } else {
  493. c = cgi.chunkGroup;
  494. }
  495. if (c !== undefined) {
  496. // 2. We store the connection for the block
  497. // to connect it later if needed
  498. blockConnections.get(b).push({
  499. originChunkGroupInfo: chunkGroupInfo,
  500. chunkGroup: c
  501. });
  502. // 3. We enqueue the chunk group info creation/updating
  503. let connectList = queueConnect.get(chunkGroupInfo);
  504. if (connectList === undefined) {
  505. connectList = new Set();
  506. queueConnect.set(chunkGroupInfo, connectList);
  507. }
  508. connectList.add(/** @type {ChunkGroupInfo} */ (cgi));
  509. // TODO check if this really need to be done for each traversal
  510. // or if it is enough when it's queued when created
  511. // 4. We enqueue the DependenciesBlock for traversal
  512. queueDelayed.push({
  513. action: PROCESS_BLOCK,
  514. block: b,
  515. module: module,
  516. chunk: c.chunks[0],
  517. chunkGroup: c,
  518. chunkGroupInfo: /** @type {ChunkGroupInfo} */ (cgi)
  519. });
  520. } else if (entrypoint !== undefined) {
  521. chunkGroupInfo.chunkGroup.addAsyncEntrypoint(entrypoint);
  522. }
  523. };
  524. /**
  525. * @param {DependenciesBlock} block the block
  526. * @returns {void}
  527. */
  528. const processBlock = block => {
  529. statProcessedBlocks++;
  530. // get prepared block info
  531. const blockModules = getBlockModules(block, chunkGroupInfo.runtime);
  532. if (blockModules !== undefined) {
  533. const { minAvailableModules } = chunkGroupInfo;
  534. // Buffer items because order need to be reversed to get indices correct
  535. // Traverse all referenced modules
  536. for (let i = 0; i < blockModules.length; i += 2) {
  537. const refModule = /** @type {Module} */ (blockModules[i]);
  538. if (chunkGraph.isModuleInChunk(refModule, chunk)) {
  539. // skip early if already connected
  540. continue;
  541. }
  542. const activeState = /** @type {ConnectionState} */ (
  543. blockModules[i + 1]
  544. );
  545. if (activeState !== true) {
  546. skipConnectionBuffer.push([refModule, activeState]);
  547. if (activeState === false) continue;
  548. }
  549. if (
  550. activeState === true &&
  551. (minAvailableModules.has(refModule) ||
  552. minAvailableModules.plus.has(refModule))
  553. ) {
  554. // already in parent chunks, skip it for now
  555. skipBuffer.push(refModule);
  556. continue;
  557. }
  558. // enqueue, then add and enter to be in the correct order
  559. // this is relevant with circular dependencies
  560. queueBuffer.push({
  561. action: activeState === true ? ADD_AND_ENTER_MODULE : PROCESS_BLOCK,
  562. block: refModule,
  563. module: refModule,
  564. chunk,
  565. chunkGroup,
  566. chunkGroupInfo
  567. });
  568. }
  569. // Add buffered items in reverse order
  570. if (skipConnectionBuffer.length > 0) {
  571. let { skippedModuleConnections } = chunkGroupInfo;
  572. if (skippedModuleConnections === undefined) {
  573. chunkGroupInfo.skippedModuleConnections = skippedModuleConnections =
  574. new Set();
  575. }
  576. for (let i = skipConnectionBuffer.length - 1; i >= 0; i--) {
  577. skippedModuleConnections.add(skipConnectionBuffer[i]);
  578. }
  579. skipConnectionBuffer.length = 0;
  580. }
  581. if (skipBuffer.length > 0) {
  582. let { skippedItems } = chunkGroupInfo;
  583. if (skippedItems === undefined) {
  584. chunkGroupInfo.skippedItems = skippedItems = new Set();
  585. }
  586. for (let i = skipBuffer.length - 1; i >= 0; i--) {
  587. skippedItems.add(skipBuffer[i]);
  588. }
  589. skipBuffer.length = 0;
  590. }
  591. if (queueBuffer.length > 0) {
  592. for (let i = queueBuffer.length - 1; i >= 0; i--) {
  593. queue.push(queueBuffer[i]);
  594. }
  595. queueBuffer.length = 0;
  596. }
  597. }
  598. // Traverse all Blocks
  599. for (const b of block.blocks) {
  600. iteratorBlock(b);
  601. }
  602. if (block.blocks.length > 0 && module !== block) {
  603. blocksWithNestedBlocks.add(block);
  604. }
  605. };
  606. /**
  607. * @param {DependenciesBlock} block the block
  608. * @returns {void}
  609. */
  610. const processEntryBlock = block => {
  611. statProcessedBlocks++;
  612. // get prepared block info
  613. const blockModules = getBlockModules(block, chunkGroupInfo.runtime);
  614. if (blockModules !== undefined) {
  615. // Traverse all referenced modules
  616. for (let i = 0; i < blockModules.length; i += 2) {
  617. const refModule = /** @type {Module} */ (blockModules[i]);
  618. const activeState = /** @type {ConnectionState} */ (
  619. blockModules[i + 1]
  620. );
  621. // enqueue, then add and enter to be in the correct order
  622. // this is relevant with circular dependencies
  623. queueBuffer.push({
  624. action:
  625. activeState === true ? ADD_AND_ENTER_ENTRY_MODULE : PROCESS_BLOCK,
  626. block: refModule,
  627. module: refModule,
  628. chunk,
  629. chunkGroup,
  630. chunkGroupInfo
  631. });
  632. }
  633. // Add buffered items in reverse order
  634. if (queueBuffer.length > 0) {
  635. for (let i = queueBuffer.length - 1; i >= 0; i--) {
  636. queue.push(queueBuffer[i]);
  637. }
  638. queueBuffer.length = 0;
  639. }
  640. }
  641. // Traverse all Blocks
  642. for (const b of block.blocks) {
  643. iteratorBlock(b);
  644. }
  645. if (block.blocks.length > 0 && module !== block) {
  646. blocksWithNestedBlocks.add(block);
  647. }
  648. };
  649. const processQueue = () => {
  650. while (queue.length) {
  651. statProcessedQueueItems++;
  652. const queueItem = /** @type {QueueItem} */ (queue.pop());
  653. module = queueItem.module;
  654. block = queueItem.block;
  655. chunk = queueItem.chunk;
  656. chunkGroup = queueItem.chunkGroup;
  657. chunkGroupInfo = queueItem.chunkGroupInfo;
  658. switch (queueItem.action) {
  659. case ADD_AND_ENTER_ENTRY_MODULE:
  660. chunkGraph.connectChunkAndEntryModule(
  661. chunk,
  662. module,
  663. /** @type {Entrypoint} */ (chunkGroup)
  664. );
  665. // fallthrough
  666. case ADD_AND_ENTER_MODULE: {
  667. if (chunkGraph.isModuleInChunk(module, chunk)) {
  668. // already connected, skip it
  669. break;
  670. }
  671. // We connect Module and Chunk
  672. chunkGraph.connectChunkAndModule(chunk, module);
  673. }
  674. // fallthrough
  675. case ENTER_MODULE: {
  676. const index = chunkGroup.getModulePreOrderIndex(module);
  677. if (index === undefined) {
  678. chunkGroup.setModulePreOrderIndex(
  679. module,
  680. chunkGroupInfo.preOrderIndex++
  681. );
  682. }
  683. if (
  684. moduleGraph.setPreOrderIndexIfUnset(
  685. module,
  686. nextFreeModulePreOrderIndex
  687. )
  688. ) {
  689. nextFreeModulePreOrderIndex++;
  690. }
  691. // reuse queueItem
  692. queueItem.action = LEAVE_MODULE;
  693. queue.push(queueItem);
  694. }
  695. // fallthrough
  696. case PROCESS_BLOCK: {
  697. processBlock(block);
  698. break;
  699. }
  700. case PROCESS_ENTRY_BLOCK: {
  701. processEntryBlock(block);
  702. break;
  703. }
  704. case LEAVE_MODULE: {
  705. const index = chunkGroup.getModulePostOrderIndex(module);
  706. if (index === undefined) {
  707. chunkGroup.setModulePostOrderIndex(
  708. module,
  709. chunkGroupInfo.postOrderIndex++
  710. );
  711. }
  712. if (
  713. moduleGraph.setPostOrderIndexIfUnset(
  714. module,
  715. nextFreeModulePostOrderIndex
  716. )
  717. ) {
  718. nextFreeModulePostOrderIndex++;
  719. }
  720. break;
  721. }
  722. }
  723. }
  724. };
  725. const calculateResultingAvailableModules = chunkGroupInfo => {
  726. if (chunkGroupInfo.resultingAvailableModules)
  727. return chunkGroupInfo.resultingAvailableModules;
  728. const minAvailableModules = chunkGroupInfo.minAvailableModules;
  729. // Create a new Set of available modules at this point
  730. // We want to be as lazy as possible. There are multiple ways doing this:
  731. // Note that resultingAvailableModules is stored as "(a) + (b)" as it's a ModuleSetPlus
  732. // - resultingAvailableModules = (modules of chunk) + (minAvailableModules + minAvailableModules.plus)
  733. // - resultingAvailableModules = (minAvailableModules + modules of chunk) + (minAvailableModules.plus)
  734. // We choose one depending on the size of minAvailableModules vs minAvailableModules.plus
  735. let resultingAvailableModules;
  736. if (minAvailableModules.size > minAvailableModules.plus.size) {
  737. // resultingAvailableModules = (modules of chunk) + (minAvailableModules + minAvailableModules.plus)
  738. resultingAvailableModules =
  739. /** @type {Set<Module> & {plus: Set<Module>}} */ (new Set());
  740. for (const module of minAvailableModules.plus)
  741. minAvailableModules.add(module);
  742. minAvailableModules.plus = EMPTY_SET;
  743. resultingAvailableModules.plus = minAvailableModules;
  744. chunkGroupInfo.minAvailableModulesOwned = false;
  745. } else {
  746. // resultingAvailableModules = (minAvailableModules + modules of chunk) + (minAvailableModules.plus)
  747. resultingAvailableModules =
  748. /** @type {Set<Module> & {plus: Set<Module>}} */ (
  749. new Set(minAvailableModules)
  750. );
  751. resultingAvailableModules.plus = minAvailableModules.plus;
  752. }
  753. // add the modules from the chunk group to the set
  754. for (const chunk of chunkGroupInfo.chunkGroup.chunks) {
  755. for (const m of chunkGraph.getChunkModulesIterable(chunk)) {
  756. resultingAvailableModules.add(m);
  757. }
  758. }
  759. return (chunkGroupInfo.resultingAvailableModules =
  760. resultingAvailableModules);
  761. };
  762. const processConnectQueue = () => {
  763. // Figure out new parents for chunk groups
  764. // to get new available modules for these children
  765. for (const [chunkGroupInfo, targets] of queueConnect) {
  766. // 1. Add new targets to the list of children
  767. if (chunkGroupInfo.children === undefined) {
  768. chunkGroupInfo.children = targets;
  769. } else {
  770. for (const target of targets) {
  771. chunkGroupInfo.children.add(target);
  772. }
  773. }
  774. // 2. Calculate resulting available modules
  775. const resultingAvailableModules =
  776. calculateResultingAvailableModules(chunkGroupInfo);
  777. const runtime = chunkGroupInfo.runtime;
  778. // 3. Update chunk group info
  779. for (const target of targets) {
  780. target.availableModulesToBeMerged.push(resultingAvailableModules);
  781. chunkGroupsForMerging.add(target);
  782. const oldRuntime = target.runtime;
  783. const newRuntime = mergeRuntime(oldRuntime, runtime);
  784. if (oldRuntime !== newRuntime) {
  785. target.runtime = newRuntime;
  786. outdatedChunkGroupInfo.add(target);
  787. }
  788. }
  789. statConnectedChunkGroups += targets.size;
  790. }
  791. queueConnect.clear();
  792. };
  793. const processChunkGroupsForMerging = () => {
  794. statProcessedChunkGroupsForMerging += chunkGroupsForMerging.size;
  795. // Execute the merge
  796. for (const info of chunkGroupsForMerging) {
  797. const availableModulesToBeMerged = info.availableModulesToBeMerged;
  798. let cachedMinAvailableModules = info.minAvailableModules;
  799. statMergedAvailableModuleSets += availableModulesToBeMerged.length;
  800. // 1. Get minimal available modules
  801. // It doesn't make sense to traverse a chunk again with more available modules.
  802. // This step calculates the minimal available modules and skips traversal when
  803. // the list didn't shrink.
  804. if (availableModulesToBeMerged.length > 1) {
  805. availableModulesToBeMerged.sort(bySetSize);
  806. }
  807. let changed = false;
  808. merge: for (const availableModules of availableModulesToBeMerged) {
  809. if (cachedMinAvailableModules === undefined) {
  810. cachedMinAvailableModules = availableModules;
  811. info.minAvailableModules = cachedMinAvailableModules;
  812. info.minAvailableModulesOwned = false;
  813. changed = true;
  814. } else {
  815. if (info.minAvailableModulesOwned) {
  816. // We own it and can modify it
  817. if (cachedMinAvailableModules.plus === availableModules.plus) {
  818. for (const m of cachedMinAvailableModules) {
  819. if (!availableModules.has(m)) {
  820. cachedMinAvailableModules.delete(m);
  821. changed = true;
  822. }
  823. }
  824. } else {
  825. for (const m of cachedMinAvailableModules) {
  826. if (!availableModules.has(m) && !availableModules.plus.has(m)) {
  827. cachedMinAvailableModules.delete(m);
  828. changed = true;
  829. }
  830. }
  831. for (const m of cachedMinAvailableModules.plus) {
  832. if (!availableModules.has(m) && !availableModules.plus.has(m)) {
  833. // We can't remove modules from the plus part
  834. // so we need to merge plus into the normal part to allow modifying it
  835. const iterator =
  836. cachedMinAvailableModules.plus[Symbol.iterator]();
  837. // fast forward add all modules until m
  838. /** @type {IteratorResult<Module>} */
  839. let it;
  840. while (!(it = iterator.next()).done) {
  841. const module = it.value;
  842. if (module === m) break;
  843. cachedMinAvailableModules.add(module);
  844. }
  845. // check the remaining modules before adding
  846. while (!(it = iterator.next()).done) {
  847. const module = it.value;
  848. if (
  849. availableModules.has(module) ||
  850. availableModules.plus.has(module)
  851. ) {
  852. cachedMinAvailableModules.add(module);
  853. }
  854. }
  855. cachedMinAvailableModules.plus = EMPTY_SET;
  856. changed = true;
  857. continue merge;
  858. }
  859. }
  860. }
  861. } else if (cachedMinAvailableModules.plus === availableModules.plus) {
  862. // Common and fast case when the plus part is shared
  863. // We only need to care about the normal part
  864. if (availableModules.size < cachedMinAvailableModules.size) {
  865. // the new availableModules is smaller so it's faster to
  866. // fork from the new availableModules
  867. statForkedAvailableModules++;
  868. statForkedAvailableModulesCount += availableModules.size;
  869. statForkedMergedModulesCount += cachedMinAvailableModules.size;
  870. // construct a new Set as intersection of cachedMinAvailableModules and availableModules
  871. const newSet = /** @type {ModuleSetPlus} */ (new Set());
  872. newSet.plus = availableModules.plus;
  873. for (const m of availableModules) {
  874. if (cachedMinAvailableModules.has(m)) {
  875. newSet.add(m);
  876. }
  877. }
  878. statForkedResultModulesCount += newSet.size;
  879. cachedMinAvailableModules = newSet;
  880. info.minAvailableModulesOwned = true;
  881. info.minAvailableModules = newSet;
  882. changed = true;
  883. continue merge;
  884. }
  885. for (const m of cachedMinAvailableModules) {
  886. if (!availableModules.has(m)) {
  887. // cachedMinAvailableModules need to be modified
  888. // but we don't own it
  889. statForkedAvailableModules++;
  890. statForkedAvailableModulesCount +=
  891. cachedMinAvailableModules.size;
  892. statForkedMergedModulesCount += availableModules.size;
  893. // construct a new Set as intersection of cachedMinAvailableModules and availableModules
  894. // as the plus part is equal we can just take over this one
  895. const newSet = /** @type {ModuleSetPlus} */ (new Set());
  896. newSet.plus = availableModules.plus;
  897. const iterator = cachedMinAvailableModules[Symbol.iterator]();
  898. // fast forward add all modules until m
  899. /** @type {IteratorResult<Module>} */
  900. let it;
  901. while (!(it = iterator.next()).done) {
  902. const module = it.value;
  903. if (module === m) break;
  904. newSet.add(module);
  905. }
  906. // check the remaining modules before adding
  907. while (!(it = iterator.next()).done) {
  908. const module = it.value;
  909. if (availableModules.has(module)) {
  910. newSet.add(module);
  911. }
  912. }
  913. statForkedResultModulesCount += newSet.size;
  914. cachedMinAvailableModules = newSet;
  915. info.minAvailableModulesOwned = true;
  916. info.minAvailableModules = newSet;
  917. changed = true;
  918. continue merge;
  919. }
  920. }
  921. } else {
  922. for (const m of cachedMinAvailableModules) {
  923. if (!availableModules.has(m) && !availableModules.plus.has(m)) {
  924. // cachedMinAvailableModules need to be modified
  925. // but we don't own it
  926. statForkedAvailableModules++;
  927. statForkedAvailableModulesCount +=
  928. cachedMinAvailableModules.size;
  929. statForkedAvailableModulesCountPlus +=
  930. cachedMinAvailableModules.plus.size;
  931. statForkedMergedModulesCount += availableModules.size;
  932. statForkedMergedModulesCountPlus += availableModules.plus.size;
  933. // construct a new Set as intersection of cachedMinAvailableModules and availableModules
  934. const newSet = /** @type {ModuleSetPlus} */ (new Set());
  935. newSet.plus = EMPTY_SET;
  936. const iterator = cachedMinAvailableModules[Symbol.iterator]();
  937. // fast forward add all modules until m
  938. /** @type {IteratorResult<Module>} */
  939. let it;
  940. while (!(it = iterator.next()).done) {
  941. const module = it.value;
  942. if (module === m) break;
  943. newSet.add(module);
  944. }
  945. // check the remaining modules before adding
  946. while (!(it = iterator.next()).done) {
  947. const module = it.value;
  948. if (
  949. availableModules.has(module) ||
  950. availableModules.plus.has(module)
  951. ) {
  952. newSet.add(module);
  953. }
  954. }
  955. // also check all modules in cachedMinAvailableModules.plus
  956. for (const module of cachedMinAvailableModules.plus) {
  957. if (
  958. availableModules.has(module) ||
  959. availableModules.plus.has(module)
  960. ) {
  961. newSet.add(module);
  962. }
  963. }
  964. statForkedResultModulesCount += newSet.size;
  965. cachedMinAvailableModules = newSet;
  966. info.minAvailableModulesOwned = true;
  967. info.minAvailableModules = newSet;
  968. changed = true;
  969. continue merge;
  970. }
  971. }
  972. for (const m of cachedMinAvailableModules.plus) {
  973. if (!availableModules.has(m) && !availableModules.plus.has(m)) {
  974. // cachedMinAvailableModules need to be modified
  975. // but we don't own it
  976. statForkedAvailableModules++;
  977. statForkedAvailableModulesCount +=
  978. cachedMinAvailableModules.size;
  979. statForkedAvailableModulesCountPlus +=
  980. cachedMinAvailableModules.plus.size;
  981. statForkedMergedModulesCount += availableModules.size;
  982. statForkedMergedModulesCountPlus += availableModules.plus.size;
  983. // construct a new Set as intersection of cachedMinAvailableModules and availableModules
  984. // we already know that all modules directly from cachedMinAvailableModules are in availableModules too
  985. const newSet = /** @type {ModuleSetPlus} */ (
  986. new Set(cachedMinAvailableModules)
  987. );
  988. newSet.plus = EMPTY_SET;
  989. const iterator =
  990. cachedMinAvailableModules.plus[Symbol.iterator]();
  991. // fast forward add all modules until m
  992. /** @type {IteratorResult<Module>} */
  993. let it;
  994. while (!(it = iterator.next()).done) {
  995. const module = it.value;
  996. if (module === m) break;
  997. newSet.add(module);
  998. }
  999. // check the remaining modules before adding
  1000. while (!(it = iterator.next()).done) {
  1001. const module = it.value;
  1002. if (
  1003. availableModules.has(module) ||
  1004. availableModules.plus.has(module)
  1005. ) {
  1006. newSet.add(module);
  1007. }
  1008. }
  1009. statForkedResultModulesCount += newSet.size;
  1010. cachedMinAvailableModules = newSet;
  1011. info.minAvailableModulesOwned = true;
  1012. info.minAvailableModules = newSet;
  1013. changed = true;
  1014. continue merge;
  1015. }
  1016. }
  1017. }
  1018. }
  1019. }
  1020. availableModulesToBeMerged.length = 0;
  1021. if (changed) {
  1022. info.resultingAvailableModules = undefined;
  1023. outdatedChunkGroupInfo.add(info);
  1024. }
  1025. }
  1026. chunkGroupsForMerging.clear();
  1027. };
  1028. const processChunkGroupsForCombining = () => {
  1029. for (const info of chunkGroupsForCombining) {
  1030. for (const source of /** @type {Set<ChunkGroupInfo>} */ (
  1031. info.availableSources
  1032. )) {
  1033. if (!source.minAvailableModules) {
  1034. chunkGroupsForCombining.delete(info);
  1035. break;
  1036. }
  1037. }
  1038. }
  1039. for (const info of chunkGroupsForCombining) {
  1040. const availableModules = /** @type {ModuleSetPlus} */ (new Set());
  1041. availableModules.plus = EMPTY_SET;
  1042. const mergeSet = set => {
  1043. if (set.size > availableModules.plus.size) {
  1044. for (const item of availableModules.plus) availableModules.add(item);
  1045. availableModules.plus = set;
  1046. } else {
  1047. for (const item of set) availableModules.add(item);
  1048. }
  1049. };
  1050. // combine minAvailableModules from all resultingAvailableModules
  1051. for (const source of /** @type {Set<ChunkGroupInfo>} */ (
  1052. info.availableSources
  1053. )) {
  1054. const resultingAvailableModules =
  1055. calculateResultingAvailableModules(source);
  1056. mergeSet(resultingAvailableModules);
  1057. mergeSet(resultingAvailableModules.plus);
  1058. }
  1059. info.minAvailableModules = availableModules;
  1060. info.minAvailableModulesOwned = false;
  1061. info.resultingAvailableModules = undefined;
  1062. outdatedChunkGroupInfo.add(info);
  1063. }
  1064. chunkGroupsForCombining.clear();
  1065. };
  1066. const processOutdatedChunkGroupInfo = () => {
  1067. statChunkGroupInfoUpdated += outdatedChunkGroupInfo.size;
  1068. // Revisit skipped elements
  1069. for (const info of outdatedChunkGroupInfo) {
  1070. // 1. Reconsider skipped items
  1071. if (info.skippedItems !== undefined) {
  1072. const minAvailableModules =
  1073. /** @type {ModuleSetPlus} */
  1074. (info.minAvailableModules);
  1075. for (const module of info.skippedItems) {
  1076. if (
  1077. !minAvailableModules.has(module) &&
  1078. !minAvailableModules.plus.has(module)
  1079. ) {
  1080. queue.push({
  1081. action: ADD_AND_ENTER_MODULE,
  1082. block: module,
  1083. module,
  1084. chunk: info.chunkGroup.chunks[0],
  1085. chunkGroup: info.chunkGroup,
  1086. chunkGroupInfo: info
  1087. });
  1088. info.skippedItems.delete(module);
  1089. }
  1090. }
  1091. }
  1092. // 2. Reconsider skipped connections
  1093. if (info.skippedModuleConnections !== undefined) {
  1094. const minAvailableModules =
  1095. /** @type {ModuleSetPlus} */
  1096. (info.minAvailableModules);
  1097. for (const entry of info.skippedModuleConnections) {
  1098. const [module, activeState] = entry;
  1099. if (activeState === false) continue;
  1100. if (activeState === true) {
  1101. info.skippedModuleConnections.delete(entry);
  1102. }
  1103. if (
  1104. activeState === true &&
  1105. (minAvailableModules.has(module) ||
  1106. minAvailableModules.plus.has(module))
  1107. ) {
  1108. info.skippedItems.add(module);
  1109. continue;
  1110. }
  1111. queue.push({
  1112. action: activeState === true ? ADD_AND_ENTER_MODULE : PROCESS_BLOCK,
  1113. block: module,
  1114. module,
  1115. chunk: info.chunkGroup.chunks[0],
  1116. chunkGroup: info.chunkGroup,
  1117. chunkGroupInfo: info
  1118. });
  1119. }
  1120. }
  1121. // 2. Reconsider children chunk groups
  1122. if (info.children !== undefined) {
  1123. statChildChunkGroupsReconnected += info.children.size;
  1124. for (const cgi of info.children) {
  1125. let connectList = queueConnect.get(info);
  1126. if (connectList === undefined) {
  1127. connectList = new Set();
  1128. queueConnect.set(info, connectList);
  1129. }
  1130. connectList.add(cgi);
  1131. }
  1132. }
  1133. // 3. Reconsider chunk groups for combining
  1134. if (info.availableChildren !== undefined) {
  1135. for (const cgi of info.availableChildren) {
  1136. chunkGroupsForCombining.add(cgi);
  1137. }
  1138. }
  1139. }
  1140. outdatedChunkGroupInfo.clear();
  1141. };
  1142. // Iterative traversal of the Module graph
  1143. // Recursive would be simpler to write but could result in Stack Overflows
  1144. while (queue.length || queueConnect.size) {
  1145. logger.time("visitModules: visiting");
  1146. processQueue();
  1147. logger.timeAggregateEnd("visitModules: prepare");
  1148. logger.timeEnd("visitModules: visiting");
  1149. if (chunkGroupsForCombining.size > 0) {
  1150. logger.time("visitModules: combine available modules");
  1151. processChunkGroupsForCombining();
  1152. logger.timeEnd("visitModules: combine available modules");
  1153. }
  1154. if (queueConnect.size > 0) {
  1155. logger.time("visitModules: calculating available modules");
  1156. processConnectQueue();
  1157. logger.timeEnd("visitModules: calculating available modules");
  1158. if (chunkGroupsForMerging.size > 0) {
  1159. logger.time("visitModules: merging available modules");
  1160. processChunkGroupsForMerging();
  1161. logger.timeEnd("visitModules: merging available modules");
  1162. }
  1163. }
  1164. if (outdatedChunkGroupInfo.size > 0) {
  1165. logger.time("visitModules: check modules for revisit");
  1166. processOutdatedChunkGroupInfo();
  1167. logger.timeEnd("visitModules: check modules for revisit");
  1168. }
  1169. // Run queueDelayed when all items of the queue are processed
  1170. // This is important to get the global indexing correct
  1171. // Async blocks should be processed after all sync blocks are processed
  1172. if (queue.length === 0) {
  1173. const tempQueue = queue;
  1174. queue = queueDelayed.reverse();
  1175. queueDelayed = tempQueue;
  1176. }
  1177. }
  1178. logger.log(
  1179. `${statProcessedQueueItems} queue items processed (${statProcessedBlocks} blocks)`
  1180. );
  1181. logger.log(`${statConnectedChunkGroups} chunk groups connected`);
  1182. logger.log(
  1183. `${statProcessedChunkGroupsForMerging} chunk groups processed for merging (${statMergedAvailableModuleSets} module sets, ${statForkedAvailableModules} forked, ${statForkedAvailableModulesCount} + ${statForkedAvailableModulesCountPlus} modules forked, ${statForkedMergedModulesCount} + ${statForkedMergedModulesCountPlus} modules merged into fork, ${statForkedResultModulesCount} resulting modules)`
  1184. );
  1185. logger.log(
  1186. `${statChunkGroupInfoUpdated} chunk group info updated (${statChildChunkGroupsReconnected} already connected chunk groups reconnected)`
  1187. );
  1188. };
  1189. /**
  1190. *
  1191. * @param {Compilation} compilation the compilation
  1192. * @param {Set<DependenciesBlock>} blocksWithNestedBlocks flag for blocks that have nested blocks
  1193. * @param {Map<AsyncDependenciesBlock, BlockChunkGroupConnection[]>} blockConnections connection for blocks
  1194. * @param {Map<ChunkGroup, ChunkGroupInfo>} chunkGroupInfoMap mapping from chunk group to available modules
  1195. */
  1196. const connectChunkGroups = (
  1197. compilation,
  1198. blocksWithNestedBlocks,
  1199. blockConnections,
  1200. chunkGroupInfoMap
  1201. ) => {
  1202. const { chunkGraph } = compilation;
  1203. /**
  1204. * Helper function to check if all modules of a chunk are available
  1205. *
  1206. * @param {ChunkGroup} chunkGroup the chunkGroup to scan
  1207. * @param {ModuleSetPlus} availableModules the comparator set
  1208. * @returns {boolean} return true if all modules of a chunk are available
  1209. */
  1210. const areModulesAvailable = (chunkGroup, availableModules) => {
  1211. for (const chunk of chunkGroup.chunks) {
  1212. for (const module of chunkGraph.getChunkModulesIterable(chunk)) {
  1213. if (!availableModules.has(module) && !availableModules.plus.has(module))
  1214. return false;
  1215. }
  1216. }
  1217. return true;
  1218. };
  1219. // For each edge in the basic chunk graph
  1220. for (const [block, connections] of blockConnections) {
  1221. // 1. Check if connection is needed
  1222. // When none of the dependencies need to be connected
  1223. // we can skip all of them
  1224. // It's not possible to filter each item so it doesn't create inconsistent
  1225. // connections and modules can only create one version
  1226. // TODO maybe decide this per runtime
  1227. if (
  1228. // TODO is this needed?
  1229. !blocksWithNestedBlocks.has(block) &&
  1230. connections.every(({ chunkGroup, originChunkGroupInfo }) =>
  1231. areModulesAvailable(
  1232. chunkGroup,
  1233. originChunkGroupInfo.resultingAvailableModules
  1234. )
  1235. )
  1236. ) {
  1237. continue;
  1238. }
  1239. // 2. Foreach edge
  1240. for (let i = 0; i < connections.length; i++) {
  1241. const { chunkGroup, originChunkGroupInfo } = connections[i];
  1242. // 3. Connect block with chunk
  1243. chunkGraph.connectBlockAndChunkGroup(block, chunkGroup);
  1244. // 4. Connect chunk with parent
  1245. connectChunkGroupParentAndChild(
  1246. originChunkGroupInfo.chunkGroup,
  1247. chunkGroup
  1248. );
  1249. }
  1250. }
  1251. };
  1252. /**
  1253. * Remove all unconnected chunk groups
  1254. * @param {Compilation} compilation the compilation
  1255. * @param {Iterable<ChunkGroup>} allCreatedChunkGroups all chunk groups that where created before
  1256. */
  1257. const cleanupUnconnectedGroups = (compilation, allCreatedChunkGroups) => {
  1258. const { chunkGraph } = compilation;
  1259. for (const chunkGroup of allCreatedChunkGroups) {
  1260. if (chunkGroup.getNumberOfParents() === 0) {
  1261. for (const chunk of chunkGroup.chunks) {
  1262. compilation.chunks.delete(chunk);
  1263. chunkGraph.disconnectChunk(chunk);
  1264. }
  1265. chunkGraph.disconnectChunkGroup(chunkGroup);
  1266. chunkGroup.remove();
  1267. }
  1268. }
  1269. };
  1270. /**
  1271. * This method creates the Chunk graph from the Module graph
  1272. * @param {Compilation} compilation the compilation
  1273. * @param {Map<Entrypoint, Module[]>} inputEntrypointsAndModules chunk groups which are processed with the modules
  1274. * @returns {void}
  1275. */
  1276. const buildChunkGraph = (compilation, inputEntrypointsAndModules) => {
  1277. const logger = compilation.getLogger("webpack.buildChunkGraph");
  1278. // SHARED STATE
  1279. /** @type {Map<AsyncDependenciesBlock, BlockChunkGroupConnection[]>} */
  1280. const blockConnections = new Map();
  1281. /** @type {Set<ChunkGroup>} */
  1282. const allCreatedChunkGroups = new Set();
  1283. /** @type {Map<ChunkGroup, ChunkGroupInfo>} */
  1284. const chunkGroupInfoMap = new Map();
  1285. /** @type {Set<DependenciesBlock>} */
  1286. const blocksWithNestedBlocks = new Set();
  1287. // PART ONE
  1288. logger.time("visitModules");
  1289. visitModules(
  1290. logger,
  1291. compilation,
  1292. inputEntrypointsAndModules,
  1293. chunkGroupInfoMap,
  1294. blockConnections,
  1295. blocksWithNestedBlocks,
  1296. allCreatedChunkGroups
  1297. );
  1298. logger.timeEnd("visitModules");
  1299. // PART TWO
  1300. logger.time("connectChunkGroups");
  1301. connectChunkGroups(
  1302. compilation,
  1303. blocksWithNestedBlocks,
  1304. blockConnections,
  1305. chunkGroupInfoMap
  1306. );
  1307. logger.timeEnd("connectChunkGroups");
  1308. for (const [chunkGroup, chunkGroupInfo] of chunkGroupInfoMap) {
  1309. for (const chunk of chunkGroup.chunks)
  1310. chunk.runtime = mergeRuntime(chunk.runtime, chunkGroupInfo.runtime);
  1311. }
  1312. // Cleanup work
  1313. logger.time("cleanup");
  1314. cleanupUnconnectedGroups(compilation, allCreatedChunkGroups);
  1315. logger.timeEnd("cleanup");
  1316. };
  1317. module.exports = buildChunkGraph;