1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 | "use strict";
|
7 |
|
8 | const AsyncDependencyToInitialChunkError = require("./AsyncDependencyToInitialChunkError");
|
9 | const GraphHelpers = require("./GraphHelpers");
|
10 |
|
11 |
|
12 |
|
13 |
|
14 |
|
15 |
|
16 |
|
17 |
|
18 |
|
19 |
|
20 |
|
21 |
|
22 |
|
23 |
|
24 |
|
25 |
|
26 |
|
27 |
|
28 |
|
29 |
|
30 |
|
31 |
|
32 |
|
33 |
|
34 |
|
35 |
|
36 |
|
37 |
|
38 |
|
39 |
|
40 |
|
41 |
|
42 |
|
43 |
|
44 |
|
45 |
|
46 |
|
47 |
|
48 |
|
49 |
|
50 |
|
51 |
|
52 | const bySetSize = (a, b) => {
|
53 | return b.size - a.size;
|
54 | };
|
55 |
|
56 |
|
57 |
|
58 |
|
59 |
|
60 |
|
61 | const extraceBlockInfoMap = compilation => {
|
62 |
|
63 | const blockInfoMap = new Map();
|
64 |
|
65 | |
66 |
|
67 |
|
68 |
|
69 | const iteratorDependency = d => {
|
70 |
|
71 | const ref = compilation.getDependencyReference(currentModule, d);
|
72 | if (!ref) {
|
73 | return;
|
74 | }
|
75 |
|
76 | const refModule = ref.module;
|
77 | if (!refModule) {
|
78 | return;
|
79 | }
|
80 |
|
81 | if (ref.weak) {
|
82 | return;
|
83 | }
|
84 |
|
85 | blockInfoModules.add(refModule);
|
86 | };
|
87 |
|
88 | |
89 |
|
90 |
|
91 |
|
92 | const iteratorBlockPrepare = b => {
|
93 | blockInfoBlocks.push(b);
|
94 | blockQueue.push(b);
|
95 | };
|
96 |
|
97 |
|
98 | let currentModule;
|
99 |
|
100 | let block;
|
101 |
|
102 | let blockQueue;
|
103 |
|
104 | let blockInfoModules;
|
105 |
|
106 | let blockInfoBlocks;
|
107 |
|
108 | for (const module of compilation.modules) {
|
109 | blockQueue = [module];
|
110 | currentModule = module;
|
111 | while (blockQueue.length > 0) {
|
112 | block = blockQueue.pop();
|
113 | blockInfoModules = new Set();
|
114 | blockInfoBlocks = [];
|
115 |
|
116 | if (block.variables) {
|
117 | for (const variable of block.variables) {
|
118 | for (const dep of variable.dependencies) iteratorDependency(dep);
|
119 | }
|
120 | }
|
121 |
|
122 | if (block.dependencies) {
|
123 | for (const dep of block.dependencies) iteratorDependency(dep);
|
124 | }
|
125 |
|
126 | if (block.blocks) {
|
127 | for (const b of block.blocks) iteratorBlockPrepare(b);
|
128 | }
|
129 |
|
130 | const blockInfo = {
|
131 | modules: blockInfoModules,
|
132 | blocks: blockInfoBlocks
|
133 | };
|
134 | blockInfoMap.set(block, blockInfo);
|
135 | }
|
136 | }
|
137 |
|
138 | return blockInfoMap;
|
139 | };
|
140 |
|
141 |
|
142 |
|
143 |
|
144 |
|
145 |
|
146 |
|
147 |
|
148 |
|
149 |
|
150 | const visitModules = (
|
151 | compilation,
|
152 | inputChunkGroups,
|
153 | chunkGroupInfoMap,
|
154 | chunkDependencies,
|
155 | blocksWithNestedBlocks,
|
156 | allCreatedChunkGroups
|
157 | ) => {
|
158 | const logger = compilation.getLogger("webpack.buildChunkGraph.visitModules");
|
159 | const { namedChunkGroups } = compilation;
|
160 |
|
161 | logger.time("prepare");
|
162 | const blockInfoMap = extraceBlockInfoMap(compilation);
|
163 |
|
164 |
|
165 | const chunkGroupCounters = new Map();
|
166 | for (const chunkGroup of inputChunkGroups) {
|
167 | chunkGroupCounters.set(chunkGroup, {
|
168 | index: 0,
|
169 | index2: 0
|
170 | });
|
171 | }
|
172 |
|
173 | let nextFreeModuleIndex = 0;
|
174 | let nextFreeModuleIndex2 = 0;
|
175 |
|
176 |
|
177 | const blockChunkGroups = new Map();
|
178 |
|
179 | const ADD_AND_ENTER_MODULE = 0;
|
180 | const ENTER_MODULE = 1;
|
181 | const PROCESS_BLOCK = 2;
|
182 | const LEAVE_MODULE = 3;
|
183 |
|
184 | |
185 |
|
186 |
|
187 |
|
188 |
|
189 | const reduceChunkGroupToQueueItem = (queue, chunkGroup) => {
|
190 | for (const chunk of chunkGroup.chunks) {
|
191 | const module = chunk.entryModule;
|
192 | queue.push({
|
193 | action: ENTER_MODULE,
|
194 | block: module,
|
195 | module,
|
196 | chunk,
|
197 | chunkGroup
|
198 | });
|
199 | }
|
200 | chunkGroupInfoMap.set(chunkGroup, {
|
201 | chunkGroup,
|
202 | minAvailableModules: new Set(),
|
203 | minAvailableModulesOwned: true,
|
204 | availableModulesToBeMerged: [],
|
205 | skippedItems: [],
|
206 | resultingAvailableModules: undefined,
|
207 | children: undefined
|
208 | });
|
209 | return queue;
|
210 | };
|
211 |
|
212 |
|
213 |
|
214 | let queue = inputChunkGroups
|
215 | .reduce(reduceChunkGroupToQueueItem, [])
|
216 | .reverse();
|
217 |
|
218 | const queueConnect = new Map();
|
219 |
|
220 | const outdatedChunkGroupInfo = new Set();
|
221 |
|
222 | let queueDelayed = [];
|
223 |
|
224 | logger.timeEnd("prepare");
|
225 |
|
226 |
|
227 | let module;
|
228 |
|
229 | let chunk;
|
230 |
|
231 | let chunkGroup;
|
232 |
|
233 | let block;
|
234 |
|
235 | let minAvailableModules;
|
236 |
|
237 | let skippedItems;
|
238 |
|
239 |
|
240 | |
241 |
|
242 |
|
243 |
|
244 | const iteratorBlock = b => {
|
245 |
|
246 |
|
247 | let c = blockChunkGroups.get(b);
|
248 | if (c === undefined) {
|
249 | c = namedChunkGroups.get(b.chunkName);
|
250 | if (c && c.isInitial()) {
|
251 | compilation.errors.push(
|
252 | new AsyncDependencyToInitialChunkError(b.chunkName, module, b.loc)
|
253 | );
|
254 | c = chunkGroup;
|
255 | } else {
|
256 | c = compilation.addChunkInGroup(
|
257 | b.groupOptions || b.chunkName,
|
258 | module,
|
259 | b.loc,
|
260 | b.request
|
261 | );
|
262 | chunkGroupCounters.set(c, { index: 0, index2: 0 });
|
263 | blockChunkGroups.set(b, c);
|
264 | allCreatedChunkGroups.add(c);
|
265 | }
|
266 | } else {
|
267 |
|
268 | if (c.addOptions) c.addOptions(b.groupOptions);
|
269 | c.addOrigin(module, b.loc, b.request);
|
270 | }
|
271 |
|
272 |
|
273 | let deps = chunkDependencies.get(chunkGroup);
|
274 | if (!deps) chunkDependencies.set(chunkGroup, (deps = []));
|
275 | deps.push({
|
276 | block: b,
|
277 | chunkGroup: c
|
278 | });
|
279 |
|
280 |
|
281 | let connectList = queueConnect.get(chunkGroup);
|
282 | if (connectList === undefined) {
|
283 | connectList = new Set();
|
284 | queueConnect.set(chunkGroup, connectList);
|
285 | }
|
286 | connectList.add(c);
|
287 |
|
288 |
|
289 | queueDelayed.push({
|
290 | action: PROCESS_BLOCK,
|
291 | block: b,
|
292 | module: module,
|
293 | chunk: c.chunks[0],
|
294 | chunkGroup: c
|
295 | });
|
296 | };
|
297 |
|
298 |
|
299 |
|
300 | while (queue.length) {
|
301 | logger.time("visiting");
|
302 | while (queue.length) {
|
303 | const queueItem = queue.pop();
|
304 | module = queueItem.module;
|
305 | block = queueItem.block;
|
306 | chunk = queueItem.chunk;
|
307 | if (chunkGroup !== queueItem.chunkGroup) {
|
308 | chunkGroup = queueItem.chunkGroup;
|
309 | const chunkGroupInfo = chunkGroupInfoMap.get(chunkGroup);
|
310 | minAvailableModules = chunkGroupInfo.minAvailableModules;
|
311 | skippedItems = chunkGroupInfo.skippedItems;
|
312 | }
|
313 |
|
314 | switch (queueItem.action) {
|
315 | case ADD_AND_ENTER_MODULE: {
|
316 | if (minAvailableModules.has(module)) {
|
317 |
|
318 |
|
319 | skippedItems.push(queueItem);
|
320 | break;
|
321 | }
|
322 |
|
323 | if (chunk.addModule(module)) {
|
324 | module.addChunk(chunk);
|
325 | } else {
|
326 |
|
327 | break;
|
328 | }
|
329 | }
|
330 |
|
331 | case ENTER_MODULE: {
|
332 | if (chunkGroup !== undefined) {
|
333 | const index = chunkGroup.getModuleIndex(module);
|
334 | if (index === undefined) {
|
335 | chunkGroup.setModuleIndex(
|
336 | module,
|
337 | chunkGroupCounters.get(chunkGroup).index++
|
338 | );
|
339 | }
|
340 | }
|
341 |
|
342 | if (module.index === null) {
|
343 | module.index = nextFreeModuleIndex++;
|
344 | }
|
345 |
|
346 | queue.push({
|
347 | action: LEAVE_MODULE,
|
348 | block,
|
349 | module,
|
350 | chunk,
|
351 | chunkGroup
|
352 | });
|
353 | }
|
354 |
|
355 | case PROCESS_BLOCK: {
|
356 |
|
357 | const blockInfo = blockInfoMap.get(block);
|
358 |
|
359 |
|
360 | const skipBuffer = [];
|
361 | const queueBuffer = [];
|
362 |
|
363 | for (const refModule of blockInfo.modules) {
|
364 | if (chunk.containsModule(refModule)) {
|
365 |
|
366 | continue;
|
367 | }
|
368 | if (minAvailableModules.has(refModule)) {
|
369 |
|
370 | skipBuffer.push({
|
371 | action: ADD_AND_ENTER_MODULE,
|
372 | block: refModule,
|
373 | module: refModule,
|
374 | chunk,
|
375 | chunkGroup
|
376 | });
|
377 | continue;
|
378 | }
|
379 |
|
380 |
|
381 | queueBuffer.push({
|
382 | action: ADD_AND_ENTER_MODULE,
|
383 | block: refModule,
|
384 | module: refModule,
|
385 | chunk,
|
386 | chunkGroup
|
387 | });
|
388 | }
|
389 |
|
390 | for (let i = skipBuffer.length - 1; i >= 0; i--) {
|
391 | skippedItems.push(skipBuffer[i]);
|
392 | }
|
393 | for (let i = queueBuffer.length - 1; i >= 0; i--) {
|
394 | queue.push(queueBuffer[i]);
|
395 | }
|
396 |
|
397 |
|
398 | for (const block of blockInfo.blocks) iteratorBlock(block);
|
399 |
|
400 | if (blockInfo.blocks.length > 0 && module !== block) {
|
401 | blocksWithNestedBlocks.add(block);
|
402 | }
|
403 | break;
|
404 | }
|
405 | case LEAVE_MODULE: {
|
406 | if (chunkGroup !== undefined) {
|
407 | const index = chunkGroup.getModuleIndex2(module);
|
408 | if (index === undefined) {
|
409 | chunkGroup.setModuleIndex2(
|
410 | module,
|
411 | chunkGroupCounters.get(chunkGroup).index2++
|
412 | );
|
413 | }
|
414 | }
|
415 |
|
416 | if (module.index2 === null) {
|
417 | module.index2 = nextFreeModuleIndex2++;
|
418 | }
|
419 | break;
|
420 | }
|
421 | }
|
422 | }
|
423 | logger.timeEnd("visiting");
|
424 |
|
425 | while (queueConnect.size > 0) {
|
426 | logger.time("calculating available modules");
|
427 |
|
428 |
|
429 |
|
430 | for (const [chunkGroup, targets] of queueConnect) {
|
431 | const info = chunkGroupInfoMap.get(chunkGroup);
|
432 | let minAvailableModules = info.minAvailableModules;
|
433 |
|
434 |
|
435 | const resultingAvailableModules = new Set(minAvailableModules);
|
436 | for (const chunk of chunkGroup.chunks) {
|
437 | for (const m of chunk.modulesIterable) {
|
438 | resultingAvailableModules.add(m);
|
439 | }
|
440 | }
|
441 | info.resultingAvailableModules = resultingAvailableModules;
|
442 | if (info.children === undefined) {
|
443 | info.children = targets;
|
444 | } else {
|
445 | for (const target of targets) {
|
446 | info.children.add(target);
|
447 | }
|
448 | }
|
449 |
|
450 |
|
451 | for (const target of targets) {
|
452 | let chunkGroupInfo = chunkGroupInfoMap.get(target);
|
453 | if (chunkGroupInfo === undefined) {
|
454 | chunkGroupInfo = {
|
455 | chunkGroup: target,
|
456 | minAvailableModules: undefined,
|
457 | minAvailableModulesOwned: undefined,
|
458 | availableModulesToBeMerged: [],
|
459 | skippedItems: [],
|
460 | resultingAvailableModules: undefined,
|
461 | children: undefined
|
462 | };
|
463 | chunkGroupInfoMap.set(target, chunkGroupInfo);
|
464 | }
|
465 | chunkGroupInfo.availableModulesToBeMerged.push(
|
466 | resultingAvailableModules
|
467 | );
|
468 | outdatedChunkGroupInfo.add(chunkGroupInfo);
|
469 | }
|
470 | }
|
471 | queueConnect.clear();
|
472 | logger.timeEnd("calculating available modules");
|
473 |
|
474 | if (outdatedChunkGroupInfo.size > 0) {
|
475 | logger.time("merging available modules");
|
476 |
|
477 | for (const info of outdatedChunkGroupInfo) {
|
478 | const availableModulesToBeMerged = info.availableModulesToBeMerged;
|
479 | let cachedMinAvailableModules = info.minAvailableModules;
|
480 |
|
481 |
|
482 |
|
483 |
|
484 |
|
485 | if (availableModulesToBeMerged.length > 1) {
|
486 | availableModulesToBeMerged.sort(bySetSize);
|
487 | }
|
488 | let changed = false;
|
489 | for (const availableModules of availableModulesToBeMerged) {
|
490 | if (cachedMinAvailableModules === undefined) {
|
491 | cachedMinAvailableModules = availableModules;
|
492 | info.minAvailableModules = cachedMinAvailableModules;
|
493 | info.minAvailableModulesOwned = false;
|
494 | changed = true;
|
495 | } else {
|
496 | if (info.minAvailableModulesOwned) {
|
497 |
|
498 | for (const m of cachedMinAvailableModules) {
|
499 | if (!availableModules.has(m)) {
|
500 | cachedMinAvailableModules.delete(m);
|
501 | changed = true;
|
502 | }
|
503 | }
|
504 | } else {
|
505 | for (const m of cachedMinAvailableModules) {
|
506 | if (!availableModules.has(m)) {
|
507 |
|
508 |
|
509 |
|
510 |
|
511 | const newSet = new Set();
|
512 | const iterator = cachedMinAvailableModules[
|
513 | Symbol.iterator
|
514 | ]();
|
515 |
|
516 | let it;
|
517 | while (!(it = iterator.next()).done) {
|
518 | const module = it.value;
|
519 | if (module === m) break;
|
520 | newSet.add(module);
|
521 | }
|
522 | while (!(it = iterator.next()).done) {
|
523 | const module = it.value;
|
524 | if (availableModules.has(module)) {
|
525 | newSet.add(module);
|
526 | }
|
527 | }
|
528 | cachedMinAvailableModules = newSet;
|
529 | info.minAvailableModulesOwned = true;
|
530 | info.minAvailableModules = newSet;
|
531 |
|
532 |
|
533 |
|
534 | if (chunkGroup === info.chunkGroup) {
|
535 | minAvailableModules = cachedMinAvailableModules;
|
536 | }
|
537 |
|
538 | changed = true;
|
539 | break;
|
540 | }
|
541 | }
|
542 | }
|
543 | }
|
544 | }
|
545 | availableModulesToBeMerged.length = 0;
|
546 | if (!changed) continue;
|
547 |
|
548 |
|
549 | for (const queueItem of info.skippedItems) {
|
550 | queue.push(queueItem);
|
551 | }
|
552 | info.skippedItems.length = 0;
|
553 |
|
554 |
|
555 | if (info.children !== undefined) {
|
556 | const chunkGroup = info.chunkGroup;
|
557 | for (const c of info.children) {
|
558 | let connectList = queueConnect.get(chunkGroup);
|
559 | if (connectList === undefined) {
|
560 | connectList = new Set();
|
561 | queueConnect.set(chunkGroup, connectList);
|
562 | }
|
563 | connectList.add(c);
|
564 | }
|
565 | }
|
566 | }
|
567 | outdatedChunkGroupInfo.clear();
|
568 | logger.timeEnd("merging available modules");
|
569 | }
|
570 | }
|
571 |
|
572 |
|
573 |
|
574 |
|
575 | if (queue.length === 0) {
|
576 | const tempQueue = queue;
|
577 | queue = queueDelayed.reverse();
|
578 | queueDelayed = tempQueue;
|
579 | }
|
580 | }
|
581 | };
|
582 |
|
583 |
|
584 |
|
585 |
|
586 |
|
587 |
|
588 |
|
589 | const connectChunkGroups = (
|
590 | blocksWithNestedBlocks,
|
591 | chunkDependencies,
|
592 | chunkGroupInfoMap
|
593 | ) => {
|
594 |
|
595 | let resultingAvailableModules;
|
596 |
|
597 | |
598 |
|
599 |
|
600 |
|
601 |
|
602 |
|
603 |
|
604 | const areModulesAvailable = (chunkGroup, availableModules) => {
|
605 | for (const chunk of chunkGroup.chunks) {
|
606 | for (const module of chunk.modulesIterable) {
|
607 | if (!availableModules.has(module)) return false;
|
608 | }
|
609 | }
|
610 | return true;
|
611 | };
|
612 |
|
613 |
|
614 | |
615 |
|
616 |
|
617 |
|
618 |
|
619 | const filterFn = dep => {
|
620 | const depChunkGroup = dep.chunkGroup;
|
621 |
|
622 | if (blocksWithNestedBlocks.has(dep.block)) return true;
|
623 | if (areModulesAvailable(depChunkGroup, resultingAvailableModules)) {
|
624 | return false;
|
625 | }
|
626 | return true;
|
627 | };
|
628 |
|
629 |
|
630 | for (const [chunkGroup, deps] of chunkDependencies) {
|
631 | if (deps.length === 0) continue;
|
632 |
|
633 |
|
634 | const info = chunkGroupInfoMap.get(chunkGroup);
|
635 | resultingAvailableModules = info.resultingAvailableModules;
|
636 |
|
637 |
|
638 | for (let i = 0; i < deps.length; i++) {
|
639 | const dep = deps[i];
|
640 |
|
641 |
|
642 |
|
643 | if (!filterFn(dep)) {
|
644 | continue;
|
645 | }
|
646 | const depChunkGroup = dep.chunkGroup;
|
647 | const depBlock = dep.block;
|
648 |
|
649 |
|
650 | GraphHelpers.connectDependenciesBlockAndChunkGroup(
|
651 | depBlock,
|
652 | depChunkGroup
|
653 | );
|
654 |
|
655 |
|
656 | GraphHelpers.connectChunkGroupParentAndChild(chunkGroup, depChunkGroup);
|
657 | }
|
658 | }
|
659 | };
|
660 |
|
661 |
|
662 |
|
663 |
|
664 |
|
665 |
|
666 | const cleanupUnconnectedGroups = (compilation, allCreatedChunkGroups) => {
|
667 | for (const chunkGroup of allCreatedChunkGroups) {
|
668 | if (chunkGroup.getNumberOfParents() === 0) {
|
669 | for (const chunk of chunkGroup.chunks) {
|
670 | const idx = compilation.chunks.indexOf(chunk);
|
671 | if (idx >= 0) compilation.chunks.splice(idx, 1);
|
672 | chunk.remove("unconnected");
|
673 | }
|
674 | chunkGroup.remove("unconnected");
|
675 | }
|
676 | }
|
677 | };
|
678 |
|
679 |
|
680 |
|
681 |
|
682 |
|
683 |
|
684 |
|
685 | const buildChunkGraph = (compilation, inputChunkGroups) => {
|
686 |
|
687 |
|
688 |
|
689 | const chunkDependencies = new Map();
|
690 |
|
691 |
|
692 | const allCreatedChunkGroups = new Set();
|
693 |
|
694 |
|
695 | const chunkGroupInfoMap = new Map();
|
696 |
|
697 |
|
698 | const blocksWithNestedBlocks = new Set();
|
699 |
|
700 |
|
701 |
|
702 | visitModules(
|
703 | compilation,
|
704 | inputChunkGroups,
|
705 | chunkGroupInfoMap,
|
706 | chunkDependencies,
|
707 | blocksWithNestedBlocks,
|
708 | allCreatedChunkGroups
|
709 | );
|
710 |
|
711 |
|
712 |
|
713 | connectChunkGroups(
|
714 | blocksWithNestedBlocks,
|
715 | chunkDependencies,
|
716 | chunkGroupInfoMap
|
717 | );
|
718 |
|
719 |
|
720 |
|
721 | cleanupUnconnectedGroups(compilation, allCreatedChunkGroups);
|
722 | };
|
723 |
|
724 | module.exports = buildChunkGraph;
|