source: frontend/node_modules/webpack/lib/util/comparators.js

Last change on this file was 9af201e, checked in by MBK <marija.karapandzova@…>, 13 days ago

Fix frontend appearance
  • Property mode set to 100644
File size: 18.7 KB
Line 
1/*
2 MIT License http://www.opensource.org/licenses/mit-license.php
3 Author Tobias Koppers @sokra
4*/
5
6"use strict";
7
8const { getFullModuleName } = require("../ids/IdHelpers");
9const { compareRuntime } = require("./runtime");
10
11/** @typedef {import("../Chunk")} Chunk */
12/** @typedef {import("../Chunk").ChunkName} ChunkName */
13/** @typedef {import("../Chunk").ChunkId} ChunkId */
14/** @typedef {import("../ChunkGraph")} ChunkGraph */
15/** @typedef {import("../ChunkGraph").ModuleId} ModuleId */
16/** @typedef {import("../ChunkGroup")} ChunkGroup */
17/** @typedef {import("../Compiler")} Compiler */
18/** @typedef {import("../Dependency").DependencyLocation} DependencyLocation */
19/** @typedef {import("../Dependency")} Dependency */
20/** @typedef {import("../dependencies/HarmonyImportSideEffectDependency")} HarmonyImportSideEffectDependency */
21/** @typedef {import("../dependencies/HarmonyImportSpecifierDependency")} HarmonyImportSpecifierDependency */
22/** @typedef {import("../Module")} Module */
23/** @typedef {import("../ModuleGraph")} ModuleGraph */
24/** @typedef {import("../dependencies/ModuleDependency")} ModuleDependency */
25
26/**
27 * Defines the dependency source order type used by this module.
28 * @typedef {object} DependencySourceOrder
29 * @property {number} main the main source order
30 * @property {number} sub the sub source order
31 */
32
33/**
34 * Defines the comparator type used by this module.
35 * @template T
36 * @typedef {(a: T, b: T) => -1 | 0 | 1} Comparator
37 */
38/**
39 * Defines the raw parameterized comparator type used by this module.
40 * @template {object} TArg
41 * @template T
42 * @typedef {(tArg: TArg, a: T, b: T) => -1 | 0 | 1} RawParameterizedComparator
43 */
44/**
45 * Defines the parameterized comparator type used by this module.
46 * @template {object} TArg
47 * @template T
48 * @typedef {(tArg: TArg) => Comparator<T>} ParameterizedComparator
49 */
50
51/**
52 * Creates a cached parameterized comparator.
53 * @template {object} TArg
54 * @template {object} T
55 * @param {RawParameterizedComparator<TArg, T>} fn comparator with argument
56 * @returns {ParameterizedComparator<TArg, T>} comparator
57 */
58const createCachedParameterizedComparator = (fn) => {
59 /** @type {WeakMap<TArg, Comparator<T>>} */
60 const map = new WeakMap();
61 return (arg) => {
62 const cachedResult = map.get(arg);
63 if (cachedResult !== undefined) return cachedResult;
64 /**
65 * Returns compare result.
66 * @param {T} a first item
67 * @param {T} b second item
68 * @returns {-1 | 0 | 1} compare result
69 */
70 const result = fn.bind(null, arg);
71 map.set(arg, result);
72 return result;
73 };
74};
75
76/**
77 * Compares the provided values and returns their ordering.
78 * @param {string | number} a first id
79 * @param {string | number} b second id
80 * @returns {-1 | 0 | 1} compare result
81 */
82const compareIds = (a, b) => {
83 if (typeof a !== typeof b) {
84 return typeof a < typeof b ? -1 : 1;
85 }
86 if (a < b) return -1;
87 if (a > b) return 1;
88 return 0;
89};
90
91/**
92 * Compares iterables.
93 * @template T
94 * @param {Comparator<T>} elementComparator comparator for elements
95 * @returns {Comparator<Iterable<T>>} comparator for iterables of elements
96 */
97const compareIterables = (elementComparator) => {
98 const cacheEntry = compareIteratorsCache.get(elementComparator);
99 if (cacheEntry !== undefined) return cacheEntry;
100 /**
101 * Returns compare result.
102 * @param {Iterable<T>} a first value
103 * @param {Iterable<T>} b second value
104 * @returns {-1 | 0 | 1} compare result
105 */
106 const result = (a, b) => {
107 const aI = a[Symbol.iterator]();
108 const bI = b[Symbol.iterator]();
109 while (true) {
110 const aItem = aI.next();
111 const bItem = bI.next();
112 if (aItem.done) {
113 return bItem.done ? 0 : -1;
114 } else if (bItem.done) {
115 return 1;
116 }
117 const res = elementComparator(aItem.value, bItem.value);
118 if (res !== 0) return res;
119 }
120 };
121 compareIteratorsCache.set(elementComparator, result);
122 return result;
123};
124
125/**
126 * Compare two locations
127 * @param {DependencyLocation} a A location node
128 * @param {DependencyLocation} b A location node
129 * @returns {-1 | 0 | 1} sorting comparator value
130 */
131const compareLocations = (a, b) => {
132 const isObjectA = typeof a === "object" && a !== null;
133 const isObjectB = typeof b === "object" && b !== null;
134 if (!isObjectA || !isObjectB) {
135 if (isObjectA) return 1;
136 if (isObjectB) return -1;
137 return 0;
138 }
139 if ("start" in a) {
140 if ("start" in b) {
141 const ap = a.start;
142 const bp = b.start;
143 if (ap.line < bp.line) return -1;
144 if (ap.line > bp.line) return 1;
145 if (
146 /** @type {number} */ (ap.column) < /** @type {number} */ (bp.column)
147 ) {
148 return -1;
149 }
150 if (
151 /** @type {number} */ (ap.column) > /** @type {number} */ (bp.column)
152 ) {
153 return 1;
154 }
155 } else {
156 return -1;
157 }
158 } else if ("start" in b) {
159 return 1;
160 }
161 if ("name" in a) {
162 if ("name" in b) {
163 if (a.name < b.name) return -1;
164 if (a.name > b.name) return 1;
165 } else {
166 return -1;
167 }
168 } else if ("name" in b) {
169 return 1;
170 }
171 if ("index" in a) {
172 if ("index" in b) {
173 if (/** @type {number} */ (a.index) < /** @type {number} */ (b.index)) {
174 return -1;
175 }
176 if (/** @type {number} */ (a.index) > /** @type {number} */ (b.index)) {
177 return 1;
178 }
179 } else {
180 return -1;
181 }
182 } else if ("index" in b) {
183 return 1;
184 }
185 return 0;
186};
187
188/**
189 * Compares modules by id.
190 * @param {ChunkGraph} chunkGraph the chunk graph
191 * @param {Module} a module
192 * @param {Module} b module
193 * @returns {-1 | 0 | 1} compare result
194 */
195const compareModulesById = (chunkGraph, a, b) =>
196 compareIds(
197 /** @type {ModuleId} */ (chunkGraph.getModuleId(a)),
198 /** @type {ModuleId} */ (chunkGraph.getModuleId(b))
199 );
200
201/**
202 * Compares the provided values and returns their ordering.
203 * @param {number} a number
204 * @param {number} b number
205 * @returns {-1 | 0 | 1} compare result
206 */
207const compareNumbers = (a, b) => {
208 if (typeof a !== typeof b) {
209 return typeof a < typeof b ? -1 : 1;
210 }
211 if (a < b) return -1;
212 if (a > b) return 1;
213 return 0;
214};
215
216/**
217 * Compares strings numeric.
218 * @param {string} a string
219 * @param {string} b string
220 * @returns {-1 | 0 | 1} compare result
221 */
222const compareStringsNumeric = (a, b) => {
223 const aLength = a.length;
224 const bLength = b.length;
225
226 let aChar = 0;
227 let bChar = 0;
228
229 let aIsDigit = false;
230 let bIsDigit = false;
231 let i = 0;
232 let j = 0;
233 while (i < aLength && j < bLength) {
234 aChar = a.charCodeAt(i);
235 bChar = b.charCodeAt(j);
236
237 aIsDigit = aChar >= 48 && aChar <= 57;
238 bIsDigit = bChar >= 48 && bChar <= 57;
239
240 if (!aIsDigit && !bIsDigit) {
241 if (aChar < bChar) return -1;
242 if (aChar > bChar) return 1;
243 i++;
244 j++;
245 } else if (aIsDigit && !bIsDigit) {
246 // This segment of a is shorter than in b
247 return 1;
248 } else if (!aIsDigit && bIsDigit) {
249 // This segment of b is shorter than in a
250 return -1;
251 } else {
252 let aNumber = aChar - 48;
253 let bNumber = bChar - 48;
254
255 while (++i < aLength) {
256 aChar = a.charCodeAt(i);
257 if (aChar < 48 || aChar > 57) break;
258 aNumber = aNumber * 10 + aChar - 48;
259 }
260
261 while (++j < bLength) {
262 bChar = b.charCodeAt(j);
263 if (bChar < 48 || bChar > 57) break;
264 bNumber = bNumber * 10 + bChar - 48;
265 }
266
267 if (aNumber < bNumber) return -1;
268 if (aNumber > bNumber) return 1;
269 }
270 }
271
272 if (j < bLength) {
273 // a is shorter than b
274 bChar = b.charCodeAt(j);
275 bIsDigit = bChar >= 48 && bChar <= 57;
276 return bIsDigit ? -1 : 1;
277 }
278 if (i < aLength) {
279 // b is shorter than a
280 aChar = a.charCodeAt(i);
281 aIsDigit = aChar >= 48 && aChar <= 57;
282 return aIsDigit ? 1 : -1;
283 }
284
285 return 0;
286};
287
288/**
289 * Compares modules by post order index or identifier.
290 * @param {ModuleGraph} moduleGraph the module graph
291 * @param {Module} a module
292 * @param {Module} b module
293 * @returns {-1 | 0 | 1} compare result
294 */
295const compareModulesByPostOrderIndexOrIdentifier = (moduleGraph, a, b) => {
296 const cmp = compareNumbers(
297 /** @type {number} */ (moduleGraph.getPostOrderIndex(a)),
298 /** @type {number} */ (moduleGraph.getPostOrderIndex(b))
299 );
300 if (cmp !== 0) return cmp;
301 return compareIds(a.identifier(), b.identifier());
302};
303
304/**
305 * Compares modules by pre order index or identifier.
306 * @param {ModuleGraph} moduleGraph the module graph
307 * @param {Module} a module
308 * @param {Module} b module
309 * @returns {-1 | 0 | 1} compare result
310 */
311const compareModulesByPreOrderIndexOrIdentifier = (moduleGraph, a, b) => {
312 const cmp = compareNumbers(
313 /** @type {number} */ (moduleGraph.getPreOrderIndex(a)),
314 /** @type {number} */ (moduleGraph.getPreOrderIndex(b))
315 );
316 if (cmp !== 0) return cmp;
317 return compareIds(a.identifier(), b.identifier());
318};
319
320/**
321 * Compares modules by id or identifier.
322 * @param {ChunkGraph} chunkGraph the chunk graph
323 * @param {Module} a module
324 * @param {Module} b module
325 * @returns {-1 | 0 | 1} compare result
326 */
327const compareModulesByIdOrIdentifier = (chunkGraph, a, b) => {
328 const cmp = compareIds(
329 /** @type {ModuleId} */ (chunkGraph.getModuleId(a)),
330 /** @type {ModuleId} */ (chunkGraph.getModuleId(b))
331 );
332 if (cmp !== 0) return cmp;
333 return compareIds(a.identifier(), b.identifier());
334};
335
336/**
337 * Compare modules by their full name. This differs from comparing by identifier in that the values have been normalized to be relative to the compiler context.
338 * @param {{ context: string, root: object }} compiler the compiler, used for context and cache
339 * @param {Module} a module
340 * @param {Module} b module
341 * @returns {-1 | 0 | 1} compare result
342 */
343const compareModulesByFullName = (compiler, a, b) => {
344 const aName = getFullModuleName(a, compiler.context, compiler.root);
345 const bName = getFullModuleName(b, compiler.context, compiler.root);
346 return compareIds(aName, bName);
347};
348
349/**
350 * Compares the provided values and returns their ordering.
351 * @param {ChunkGraph} chunkGraph the chunk graph
352 * @param {Chunk} a chunk
353 * @param {Chunk} b chunk
354 * @returns {-1 | 0 | 1} compare result
355 */
356const compareChunks = (chunkGraph, a, b) => chunkGraph.compareChunks(a, b);
357
358/**
359 * Compares the provided values and returns their ordering.
360 * @param {string} a first string
361 * @param {string} b second string
362 * @returns {-1 | 0 | 1} compare result
363 */
364const compareStrings = (a, b) => {
365 if (a < b) return -1;
366 if (a > b) return 1;
367 return 0;
368};
369
370/**
371 * Compares chunk groups by index.
372 * @param {ChunkGroup} a first chunk group
373 * @param {ChunkGroup} b second chunk group
374 * @returns {-1 | 0 | 1} compare result
375 */
376const compareChunkGroupsByIndex = (a, b) =>
377 /** @type {number} */ (a.index) < /** @type {number} */ (b.index) ? -1 : 1;
378
379/**
380 * Represents TwoKeyWeakMap.
381 * @template {EXPECTED_OBJECT} K1
382 * @template {EXPECTED_OBJECT} K2
383 * @template T
384 */
385class TwoKeyWeakMap {
386 constructor() {
387 /**
388 * @private
389 * @type {WeakMap<K1, WeakMap<K2, T | undefined>>}
390 */
391 this._map = new WeakMap();
392 }
393
394 /**
395 * Returns value.
396 * @param {K1} key1 first key
397 * @param {K2} key2 second key
398 * @returns {T | undefined} value
399 */
400 get(key1, key2) {
401 const childMap = this._map.get(key1);
402 if (childMap === undefined) {
403 return;
404 }
405 return childMap.get(key2);
406 }
407
408 /**
409 * Updates value using the provided key1.
410 * @param {K1} key1 first key
411 * @param {K2} key2 second key
412 * @param {T | undefined} value new value
413 * @returns {void}
414 */
415 set(key1, key2, value) {
416 let childMap = this._map.get(key1);
417 if (childMap === undefined) {
418 childMap = new WeakMap();
419 this._map.set(key1, childMap);
420 }
421 childMap.set(key2, value);
422 }
423}
424
425/** @type {TwoKeyWeakMap<Comparator<EXPECTED_ANY>, Comparator<EXPECTED_ANY>, Comparator<EXPECTED_ANY>>}} */
426const concatComparatorsCache = new TwoKeyWeakMap();
427
428/**
429 * Concat comparators.
430 * @template T
431 * @param {Comparator<T>} c1 comparator
432 * @param {Comparator<T>} c2 comparator
433 * @param {Comparator<T>[]} cRest comparators
434 * @returns {Comparator<T>} comparator
435 */
436const concatComparators = (c1, c2, ...cRest) => {
437 if (cRest.length > 0) {
438 const [c3, ...cRest2] = cRest;
439 return concatComparators(c1, concatComparators(c2, c3, ...cRest2));
440 }
441 const cacheEntry = /** @type {Comparator<T>} */ (
442 concatComparatorsCache.get(c1, c2)
443 );
444 if (cacheEntry !== undefined) return cacheEntry;
445 /**
446 * Returns compare result.
447 * @param {T} a first value
448 * @param {T} b second value
449 * @returns {-1 | 0 | 1} compare result
450 */
451 const result = (a, b) => {
452 const res = c1(a, b);
453 if (res !== 0) return res;
454 return c2(a, b);
455 };
456 concatComparatorsCache.set(c1, c2, result);
457 return result;
458};
459
460/**
461 * Defines the selector type used by this module.
462 * @template A, B
463 * @typedef {(input: A) => B | undefined | null} Selector
464 */
465
466/** @type {TwoKeyWeakMap<Selector<EXPECTED_ANY, EXPECTED_ANY>, Comparator<EXPECTED_ANY>, Comparator<EXPECTED_ANY>>}} */
467const compareSelectCache = new TwoKeyWeakMap();
468
469/**
470 * Compares the provided values and returns their ordering.
471 * @template T
472 * @template R
473 * @param {Selector<T, R>} getter getter for value
474 * @param {Comparator<R>} comparator comparator
475 * @returns {Comparator<T>} comparator
476 */
477const compareSelect = (getter, comparator) => {
478 const cacheEntry = compareSelectCache.get(getter, comparator);
479 if (cacheEntry !== undefined) return cacheEntry;
480 /**
481 * Returns compare result.
482 * @param {T} a first value
483 * @param {T} b second value
484 * @returns {-1 | 0 | 1} compare result
485 */
486 const result = (a, b) => {
487 const aValue = getter(a);
488 const bValue = getter(b);
489 if (aValue !== undefined && aValue !== null) {
490 if (bValue !== undefined && bValue !== null) {
491 return comparator(aValue, bValue);
492 }
493 return -1;
494 }
495 if (bValue !== undefined && bValue !== null) {
496 return 1;
497 }
498 return 0;
499 };
500 compareSelectCache.set(getter, comparator, result);
501 return result;
502};
503
504/** @type {WeakMap<Comparator<EXPECTED_ANY>, Comparator<Iterable<EXPECTED_ANY>>>} */
505const compareIteratorsCache = new WeakMap();
506
507// TODO this is no longer needed when minimum node.js version is >= 12
508// since these versions ship with a stable sort function
509/**
510 * Keep original order.
511 * @template T
512 * @param {Iterable<T>} iterable original ordered list
513 * @returns {Comparator<T>} comparator
514 */
515const keepOriginalOrder = (iterable) => {
516 /** @type {Map<T, number>} */
517 const map = new Map();
518 let i = 0;
519 for (const item of iterable) {
520 map.set(item, i++);
521 }
522 return (a, b) =>
523 compareNumbers(
524 /** @type {number} */ (map.get(a)),
525 /** @type {number} */ (map.get(b))
526 );
527};
528
529/**
530 * Compares chunks natural.
531 * @param {ChunkGraph} chunkGraph the chunk graph
532 * @returns {Comparator<Chunk>} comparator
533 */
534const compareChunksNatural = (chunkGraph) => {
535 const cmpFn = module.exports.compareModulesById(chunkGraph);
536 const cmpIterableFn = compareIterables(cmpFn);
537 return concatComparators(
538 compareSelect((chunk) => /** @type {ChunkName} */ (chunk.name), compareIds),
539 compareSelect((chunk) => chunk.runtime, compareRuntime),
540 compareSelect(
541 /**
542 * Handles the callback logic for this hook.
543 * @param {Chunk} chunk a chunk
544 * @returns {Iterable<Module>} modules
545 */
546 (chunk) => chunkGraph.getOrderedChunkModulesIterable(chunk, cmpFn),
547 cmpIterableFn
548 )
549 );
550};
551
552/**
553 * For HarmonyImportSideEffectDependency and HarmonyImportSpecifierDependency, we should prioritize import order to match the behavior of running modules directly in a JS engine without a bundler.
554 * For other types like ConstDependency, we can instead prioritize usage order.
555 * https://github.com/webpack/webpack/pull/19686
556 * @param {Dependency[]} dependencies dependencies
557 * @param {WeakMap<Dependency, DependencySourceOrder>} dependencySourceOrderMap dependency source order map
558 * @param {((dep: Dependency, index: number) => void)=} onDependencyReSort optional callback to set index for each dependency
559 * @returns {void}
560 */
561const sortWithSourceOrder = (
562 dependencies,
563 dependencySourceOrderMap,
564 onDependencyReSort
565) => {
566 /** @type {{ dep: Dependency, main: number, sub: number }[]} */
567 const withSourceOrder = [];
568 /** @type {number[]} */
569 const positions = [];
570
571 for (let i = 0; i < dependencies.length; i++) {
572 const dep = dependencies[i];
573 const cached = dependencySourceOrderMap.get(dep);
574
575 if (cached) {
576 positions.push(i);
577 withSourceOrder.push({
578 dep,
579 main: cached.main,
580 sub: cached.sub
581 });
582 } else {
583 const sourceOrder = /** @type {number | undefined} */ (
584 /** @type {ModuleDependency} */ (dep).sourceOrder
585 );
586 if (typeof sourceOrder === "number") {
587 positions.push(i);
588 withSourceOrder.push({
589 dep,
590 main: sourceOrder,
591 sub: 0
592 });
593 }
594 }
595 }
596
597 if (withSourceOrder.length <= 1) {
598 return;
599 }
600
601 withSourceOrder.sort((a, b) => {
602 if (a.main !== b.main) {
603 return compareNumbers(a.main, b.main);
604 }
605 return compareNumbers(a.sub, b.sub);
606 });
607
608 // Second pass: place sorted deps back to original positions
609 for (let i = 0; i < positions.length; i++) {
610 const depIndex = positions[i];
611 dependencies[depIndex] = withSourceOrder[i].dep;
612 if (onDependencyReSort) {
613 onDependencyReSort(dependencies[depIndex], depIndex);
614 }
615 }
616};
617
618module.exports.compareChunkGroupsByIndex = compareChunkGroupsByIndex;
619/** @type {ParameterizedComparator<ChunkGraph, Chunk>} */
620module.exports.compareChunks =
621 createCachedParameterizedComparator(compareChunks);
622/**
623 * Returns compare result.
624 * @param {Chunk} a chunk
625 * @param {Chunk} b chunk
626 * @returns {-1 | 0 | 1} compare result
627 */
628module.exports.compareChunksById = (a, b) =>
629 compareIds(/** @type {ChunkId} */ (a.id), /** @type {ChunkId} */ (b.id));
630module.exports.compareChunksNatural = compareChunksNatural;
631
632module.exports.compareIds = compareIds;
633
634module.exports.compareIterables = compareIterables;
635
636module.exports.compareLocations = compareLocations;
637
638/** @type {ParameterizedComparator<Compiler, Module>} */
639module.exports.compareModulesByFullName = createCachedParameterizedComparator(
640 compareModulesByFullName
641);
642
643/** @type {ParameterizedComparator<ChunkGraph, Module>} */
644module.exports.compareModulesById =
645 createCachedParameterizedComparator(compareModulesById);
646/** @type {ParameterizedComparator<ChunkGraph, Module>} */
647module.exports.compareModulesByIdOrIdentifier =
648 createCachedParameterizedComparator(compareModulesByIdOrIdentifier);
649/**
650 * Returns compare result.
651 * @param {Module} a module
652 * @param {Module} b module
653 * @returns {-1 | 0 | 1} compare result
654 */
655module.exports.compareModulesByIdentifier = (a, b) =>
656 compareIds(a.identifier(), b.identifier());
657/** @type {ParameterizedComparator<ModuleGraph, Module>} */
658module.exports.compareModulesByPostOrderIndexOrIdentifier =
659 createCachedParameterizedComparator(
660 compareModulesByPostOrderIndexOrIdentifier
661 );
662/** @type {ParameterizedComparator<ModuleGraph, Module>} */
663module.exports.compareModulesByPreOrderIndexOrIdentifier =
664 createCachedParameterizedComparator(
665 compareModulesByPreOrderIndexOrIdentifier
666 );
667
668module.exports.compareNumbers = compareNumbers;
669module.exports.compareSelect = compareSelect;
670module.exports.compareStrings = compareStrings;
671module.exports.compareStringsNumeric = compareStringsNumeric;
672
673module.exports.concatComparators = concatComparators;
674
675module.exports.keepOriginalOrder = keepOriginalOrder;
676module.exports.sortWithSourceOrder = sortWithSourceOrder;
Note: See TracBrowser for help on using the repository browser.