source: trip-planner-front/node_modules/webpack/lib/util/comparators.js@ e29cc2e

Last change on this file since e29cc2e was 6a3a178, checked in by Ema <ema_spirova@…>, 3 years ago

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