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

main
Last change on this file was 79a0317, checked in by stefan toskovski <stefantoska84@…>, 4 days ago

F4 Finalna Verzija
  • Property mode set to 100644
File size: 13.6 KB
RevLine 
[79a0317]1/*
2 MIT License http://www.opensource.org/licenses/mit-license.php
3 Author Tobias Koppers @sokra
4*/
5
6"use strict";
7
8const { compareRuntime } = require("./runtime");
9
10/** @typedef {import("../Chunk")} Chunk */
11/** @typedef {import("../Chunk").ChunkId} ChunkId */
12/** @typedef {import("../ChunkGraph")} ChunkGraph */
13/** @typedef {import("../ChunkGraph").ModuleId} ModuleId */
14/** @typedef {import("../ChunkGroup")} ChunkGroup */
15/** @typedef {import("../Dependency").DependencyLocation} DependencyLocation */
16/** @typedef {import("../Module")} Module */
17/** @typedef {import("../ModuleGraph")} ModuleGraph */
18
19/**
20 * @template T
21 * @typedef {function(T, T): -1|0|1} Comparator
22 */
23/**
24 * @template TArg
25 * @template T
26 * @typedef {function(TArg, T, T): -1|0|1} RawParameterizedComparator
27 */
28/**
29 * @template TArg
30 * @template T
31 * @typedef {function(TArg): Comparator<T>} ParameterizedComparator
32 */
33
34/**
35 * @template T
36 * @param {RawParameterizedComparator<any, T>} fn comparator with argument
37 * @returns {ParameterizedComparator<any, T>} comparator
38 */
39const createCachedParameterizedComparator = fn => {
40 /** @type {WeakMap<object, Comparator<T>>} */
41 const map = new WeakMap();
42 return arg => {
43 const cachedResult = map.get(arg);
44 if (cachedResult !== undefined) return cachedResult;
45 /**
46 * @param {T} a first item
47 * @param {T} b second item
48 * @returns {-1|0|1} compare result
49 */
50 const result = fn.bind(null, arg);
51 map.set(arg, result);
52 return result;
53 };
54};
55
56/**
57 * @param {Chunk} a chunk
58 * @param {Chunk} b chunk
59 * @returns {-1|0|1} compare result
60 */
61module.exports.compareChunksById = (a, b) =>
62 compareIds(/** @type {ChunkId} */ (a.id), /** @type {ChunkId} */ (b.id));
63
64/**
65 * @param {Module} a module
66 * @param {Module} b module
67 * @returns {-1|0|1} compare result
68 */
69module.exports.compareModulesByIdentifier = (a, b) =>
70 compareIds(a.identifier(), b.identifier());
71
72/**
73 * @param {ChunkGraph} chunkGraph the chunk graph
74 * @param {Module} a module
75 * @param {Module} b module
76 * @returns {-1|0|1} compare result
77 */
78const compareModulesById = (chunkGraph, a, b) =>
79 compareIds(
80 /** @type {ModuleId} */ (chunkGraph.getModuleId(a)),
81 /** @type {ModuleId} */ (chunkGraph.getModuleId(b))
82 );
83/** @type {ParameterizedComparator<ChunkGraph, Module>} */
84module.exports.compareModulesById =
85 createCachedParameterizedComparator(compareModulesById);
86
87/**
88 * @param {number} a number
89 * @param {number} b number
90 * @returns {-1|0|1} compare result
91 */
92const compareNumbers = (a, b) => {
93 if (typeof a !== typeof b) {
94 return typeof a < typeof b ? -1 : 1;
95 }
96 if (a < b) return -1;
97 if (a > b) return 1;
98 return 0;
99};
100module.exports.compareNumbers = compareNumbers;
101
102/**
103 * @param {string} a string
104 * @param {string} b string
105 * @returns {-1|0|1} compare result
106 */
107const compareStringsNumeric = (a, b) => {
108 const aLength = a.length;
109 const bLength = b.length;
110
111 let aChar = 0;
112 let bChar = 0;
113
114 let aIsDigit = false;
115 let bIsDigit = false;
116 let i = 0;
117 let j = 0;
118 while (i < aLength && j < bLength) {
119 aChar = a.charCodeAt(i);
120 bChar = b.charCodeAt(j);
121
122 aIsDigit = aChar >= 48 && aChar <= 57;
123 bIsDigit = bChar >= 48 && bChar <= 57;
124
125 if (!aIsDigit && !bIsDigit) {
126 if (aChar < bChar) return -1;
127 if (aChar > bChar) return 1;
128 i++;
129 j++;
130 } else if (aIsDigit && !bIsDigit) {
131 // This segment of a is shorter than in b
132 return 1;
133 } else if (!aIsDigit && bIsDigit) {
134 // This segment of b is shorter than in a
135 return -1;
136 } else {
137 let aNumber = aChar - 48;
138 let bNumber = bChar - 48;
139
140 while (++i < aLength) {
141 aChar = a.charCodeAt(i);
142 if (aChar < 48 || aChar > 57) break;
143 aNumber = aNumber * 10 + aChar - 48;
144 }
145
146 while (++j < bLength) {
147 bChar = b.charCodeAt(j);
148 if (bChar < 48 || bChar > 57) break;
149 bNumber = bNumber * 10 + bChar - 48;
150 }
151
152 if (aNumber < bNumber) return -1;
153 if (aNumber > bNumber) return 1;
154 }
155 }
156
157 if (j < bLength) {
158 // a is shorter than b
159 bChar = b.charCodeAt(j);
160 bIsDigit = bChar >= 48 && bChar <= 57;
161 return bIsDigit ? -1 : 1;
162 }
163 if (i < aLength) {
164 // b is shorter than a
165 aChar = a.charCodeAt(i);
166 aIsDigit = aChar >= 48 && aChar <= 57;
167 return aIsDigit ? 1 : -1;
168 }
169
170 return 0;
171};
172module.exports.compareStringsNumeric = compareStringsNumeric;
173
174/**
175 * @param {ModuleGraph} moduleGraph the module graph
176 * @param {Module} a module
177 * @param {Module} b module
178 * @returns {-1|0|1} compare result
179 */
180const compareModulesByPostOrderIndexOrIdentifier = (moduleGraph, a, b) => {
181 const cmp = compareNumbers(
182 /** @type {number} */ (moduleGraph.getPostOrderIndex(a)),
183 /** @type {number} */ (moduleGraph.getPostOrderIndex(b))
184 );
185 if (cmp !== 0) return cmp;
186 return compareIds(a.identifier(), b.identifier());
187};
188/** @type {ParameterizedComparator<ModuleGraph, Module>} */
189module.exports.compareModulesByPostOrderIndexOrIdentifier =
190 createCachedParameterizedComparator(
191 compareModulesByPostOrderIndexOrIdentifier
192 );
193
194/**
195 * @param {ModuleGraph} moduleGraph the module graph
196 * @param {Module} a module
197 * @param {Module} b module
198 * @returns {-1|0|1} compare result
199 */
200const compareModulesByPreOrderIndexOrIdentifier = (moduleGraph, a, b) => {
201 const cmp = compareNumbers(
202 /** @type {number} */ (moduleGraph.getPreOrderIndex(a)),
203 /** @type {number} */ (moduleGraph.getPreOrderIndex(b))
204 );
205 if (cmp !== 0) return cmp;
206 return compareIds(a.identifier(), b.identifier());
207};
208/** @type {ParameterizedComparator<ModuleGraph, Module>} */
209module.exports.compareModulesByPreOrderIndexOrIdentifier =
210 createCachedParameterizedComparator(
211 compareModulesByPreOrderIndexOrIdentifier
212 );
213
214/**
215 * @param {ChunkGraph} chunkGraph the chunk graph
216 * @param {Module} a module
217 * @param {Module} b module
218 * @returns {-1|0|1} compare result
219 */
220const compareModulesByIdOrIdentifier = (chunkGraph, a, b) => {
221 const cmp = compareIds(
222 /** @type {ModuleId} */ (chunkGraph.getModuleId(a)),
223 /** @type {ModuleId} */ (chunkGraph.getModuleId(b))
224 );
225 if (cmp !== 0) return cmp;
226 return compareIds(a.identifier(), b.identifier());
227};
228/** @type {ParameterizedComparator<ChunkGraph, Module>} */
229module.exports.compareModulesByIdOrIdentifier =
230 createCachedParameterizedComparator(compareModulesByIdOrIdentifier);
231
232/**
233 * @param {ChunkGraph} chunkGraph the chunk graph
234 * @param {Chunk} a chunk
235 * @param {Chunk} b chunk
236 * @returns {-1|0|1} compare result
237 */
238const compareChunks = (chunkGraph, a, b) => chunkGraph.compareChunks(a, b);
239/** @type {ParameterizedComparator<ChunkGraph, Chunk>} */
240module.exports.compareChunks =
241 createCachedParameterizedComparator(compareChunks);
242
243/**
244 * @param {string|number} a first id
245 * @param {string|number} b second id
246 * @returns {-1|0|1} compare result
247 */
248const compareIds = (a, b) => {
249 if (typeof a !== typeof b) {
250 return typeof a < typeof b ? -1 : 1;
251 }
252 if (a < b) return -1;
253 if (a > b) return 1;
254 return 0;
255};
256
257module.exports.compareIds = compareIds;
258
259/**
260 * @param {string} a first string
261 * @param {string} b second string
262 * @returns {-1|0|1} compare result
263 */
264const compareStrings = (a, b) => {
265 if (a < b) return -1;
266 if (a > b) return 1;
267 return 0;
268};
269
270module.exports.compareStrings = compareStrings;
271
272/**
273 * @param {ChunkGroup} a first chunk group
274 * @param {ChunkGroup} b second chunk group
275 * @returns {-1|0|1} compare result
276 */
277const compareChunkGroupsByIndex = (a, b) =>
278 /** @type {number} */ (a.index) < /** @type {number} */ (b.index) ? -1 : 1;
279module.exports.compareChunkGroupsByIndex = compareChunkGroupsByIndex;
280
281/**
282 * @template K1 {Object}
283 * @template K2
284 * @template T
285 */
286class TwoKeyWeakMap {
287 constructor() {
288 /**
289 * @private
290 * @type {WeakMap<any, WeakMap<any, T | undefined>>}
291 */
292 this._map = new WeakMap();
293 }
294
295 /**
296 * @param {K1} key1 first key
297 * @param {K2} key2 second key
298 * @returns {T | undefined} value
299 */
300 get(key1, key2) {
301 const childMap = this._map.get(key1);
302 if (childMap === undefined) {
303 return;
304 }
305 return childMap.get(key2);
306 }
307
308 /**
309 * @param {K1} key1 first key
310 * @param {K2} key2 second key
311 * @param {T | undefined} value new value
312 * @returns {void}
313 */
314 set(key1, key2, value) {
315 let childMap = this._map.get(key1);
316 if (childMap === undefined) {
317 childMap = new WeakMap();
318 this._map.set(key1, childMap);
319 }
320 childMap.set(key2, value);
321 }
322}
323
324/** @type {TwoKeyWeakMap<Comparator<any>, Comparator<any>, Comparator<any>>}} */
325const concatComparatorsCache = new TwoKeyWeakMap();
326
327/**
328 * @template T
329 * @param {Comparator<T>} c1 comparator
330 * @param {Comparator<T>} c2 comparator
331 * @param {Comparator<T>[]} cRest comparators
332 * @returns {Comparator<T>} comparator
333 */
334const concatComparators = (c1, c2, ...cRest) => {
335 if (cRest.length > 0) {
336 const [c3, ...cRest2] = cRest;
337 return concatComparators(c1, concatComparators(c2, c3, ...cRest2));
338 }
339 const cacheEntry = /** @type {Comparator<T>} */ (
340 concatComparatorsCache.get(c1, c2)
341 );
342 if (cacheEntry !== undefined) return cacheEntry;
343 /**
344 * @param {T} a first value
345 * @param {T} b second value
346 * @returns {-1|0|1} compare result
347 */
348 const result = (a, b) => {
349 const res = c1(a, b);
350 if (res !== 0) return res;
351 return c2(a, b);
352 };
353 concatComparatorsCache.set(c1, c2, result);
354 return result;
355};
356module.exports.concatComparators = concatComparators;
357
358/**
359 * @template A, B
360 * @typedef {(input: A) => B | undefined | null} Selector
361 */
362
363/** @type {TwoKeyWeakMap<Selector<any, any>, Comparator<any>, Comparator<any>>}} */
364const compareSelectCache = new TwoKeyWeakMap();
365
366/**
367 * @template T
368 * @template R
369 * @param {Selector<T, R>} getter getter for value
370 * @param {Comparator<R>} comparator comparator
371 * @returns {Comparator<T>} comparator
372 */
373const compareSelect = (getter, comparator) => {
374 const cacheEntry = compareSelectCache.get(getter, comparator);
375 if (cacheEntry !== undefined) return cacheEntry;
376 /**
377 * @param {T} a first value
378 * @param {T} b second value
379 * @returns {-1|0|1} compare result
380 */
381 const result = (a, b) => {
382 const aValue = getter(a);
383 const bValue = getter(b);
384 if (aValue !== undefined && aValue !== null) {
385 if (bValue !== undefined && bValue !== null) {
386 return comparator(aValue, bValue);
387 }
388 return -1;
389 }
390 if (bValue !== undefined && bValue !== null) {
391 return 1;
392 }
393 return 0;
394 };
395 compareSelectCache.set(getter, comparator, result);
396 return result;
397};
398module.exports.compareSelect = compareSelect;
399
400/** @type {WeakMap<Comparator<any>, Comparator<Iterable<any>>>} */
401const compareIteratorsCache = new WeakMap();
402
403/**
404 * @template T
405 * @param {Comparator<T>} elementComparator comparator for elements
406 * @returns {Comparator<Iterable<T>>} comparator for iterables of elements
407 */
408const compareIterables = elementComparator => {
409 const cacheEntry = compareIteratorsCache.get(elementComparator);
410 if (cacheEntry !== undefined) return cacheEntry;
411 /**
412 * @param {Iterable<T>} a first value
413 * @param {Iterable<T>} b second value
414 * @returns {-1|0|1} compare result
415 */
416 const result = (a, b) => {
417 const aI = a[Symbol.iterator]();
418 const bI = b[Symbol.iterator]();
419 while (true) {
420 const aItem = aI.next();
421 const bItem = bI.next();
422 if (aItem.done) {
423 return bItem.done ? 0 : -1;
424 } else if (bItem.done) {
425 return 1;
426 }
427 const res = elementComparator(aItem.value, bItem.value);
428 if (res !== 0) return res;
429 }
430 };
431 compareIteratorsCache.set(elementComparator, result);
432 return result;
433};
434module.exports.compareIterables = compareIterables;
435
436// TODO this is no longer needed when minimum node.js version is >= 12
437// since these versions ship with a stable sort function
438/**
439 * @template T
440 * @param {Iterable<T>} iterable original ordered list
441 * @returns {Comparator<T>} comparator
442 */
443module.exports.keepOriginalOrder = iterable => {
444 /** @type {Map<T, number>} */
445 const map = new Map();
446 let i = 0;
447 for (const item of iterable) {
448 map.set(item, i++);
449 }
450 return (a, b) =>
451 compareNumbers(
452 /** @type {number} */ (map.get(a)),
453 /** @type {number} */ (map.get(b))
454 );
455};
456
457/**
458 * @param {ChunkGraph} chunkGraph the chunk graph
459 * @returns {Comparator<Chunk>} comparator
460 */
461module.exports.compareChunksNatural = chunkGraph => {
462 const cmpFn = module.exports.compareModulesById(chunkGraph);
463 const cmpIterableFn = compareIterables(cmpFn);
464 return concatComparators(
465 compareSelect(
466 chunk => /** @type {string|number} */ (chunk.name),
467 compareIds
468 ),
469 compareSelect(chunk => chunk.runtime, compareRuntime),
470 compareSelect(
471 /**
472 * @param {Chunk} chunk a chunk
473 * @returns {Iterable<Module>} modules
474 */
475 chunk => chunkGraph.getOrderedChunkModulesIterable(chunk, cmpFn),
476 cmpIterableFn
477 )
478 );
479};
480
481/**
482 * Compare two locations
483 * @param {DependencyLocation} a A location node
484 * @param {DependencyLocation} b A location node
485 * @returns {-1|0|1} sorting comparator value
486 */
487module.exports.compareLocations = (a, b) => {
488 const isObjectA = typeof a === "object" && a !== null;
489 const isObjectB = typeof b === "object" && b !== null;
490 if (!isObjectA || !isObjectB) {
491 if (isObjectA) return 1;
492 if (isObjectB) return -1;
493 return 0;
494 }
495 if ("start" in a) {
496 if ("start" in b) {
497 const ap = a.start;
498 const bp = b.start;
499 if (ap.line < bp.line) return -1;
500 if (ap.line > bp.line) return 1;
501 if (/** @type {number} */ (ap.column) < /** @type {number} */ (bp.column))
502 return -1;
503 if (/** @type {number} */ (ap.column) > /** @type {number} */ (bp.column))
504 return 1;
505 } else return -1;
506 } else if ("start" in b) return 1;
507 if ("name" in a) {
508 if ("name" in b) {
509 if (a.name < b.name) return -1;
510 if (a.name > b.name) return 1;
511 } else return -1;
512 } else if ("name" in b) return 1;
513 if ("index" in a) {
514 if ("index" in b) {
515 if (/** @type {number} */ (a.index) < /** @type {number} */ (b.index))
516 return -1;
517 if (/** @type {number} */ (a.index) > /** @type {number} */ (b.index))
518 return 1;
519 } else return -1;
520 } else if ("index" in b) return 1;
521 return 0;
522};
Note: See TracBrowser for help on using the repository browser.