source: frontend/node_modules/webpack/lib/util/deterministicGrouping.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: 15.5 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
8// Simulations show these probabilities for a single change
9// 93.1% that one group is invalidated
10// 4.8% that two groups are invalidated
11// 1.1% that 3 groups are invalidated
12// 0.1% that 4 or more groups are invalidated
13//
14// And these for removing/adding 10 lexically adjacent files
15// 64.5% that one group is invalidated
16// 24.8% that two groups are invalidated
17// 7.8% that 3 groups are invalidated
18// 2.7% that 4 or more groups are invalidated
19//
20// And these for removing/adding 3 random files
21// 0% that one group is invalidated
22// 3.7% that two groups are invalidated
23// 80.8% that 3 groups are invalidated
24// 12.3% that 4 groups are invalidated
25// 3.2% that 5 or more groups are invalidated
26
27/**
28 * Returns the similarity as number.
29 * @param {string} a key
30 * @param {string} b key
31 * @returns {number} the similarity as number
32 */
33const similarity = (a, b) => {
34 const l = Math.min(a.length, b.length);
35 let dist = 0;
36 for (let i = 0; i < l; i++) {
37 const ca = a.charCodeAt(i);
38 const cb = b.charCodeAt(i);
39 dist += Math.max(0, 10 - Math.abs(ca - cb));
40 }
41 return dist;
42};
43
44/**
45 * Returns the common part and a single char for the difference.
46 * @param {string} a key
47 * @param {string} b key
48 * @param {Set<string>} usedNames set of already used names
49 * @returns {string} the common part and a single char for the difference
50 */
51const getName = (a, b, usedNames) => {
52 const l = Math.min(a.length, b.length);
53 let i = 0;
54 while (i < l) {
55 if (a.charCodeAt(i) !== b.charCodeAt(i)) {
56 i++;
57 break;
58 }
59 i++;
60 }
61 while (i < l) {
62 const name = a.slice(0, i);
63 const lowerName = name.toLowerCase();
64 if (!usedNames.has(lowerName)) {
65 usedNames.add(lowerName);
66 return name;
67 }
68 i++;
69 }
70 // names always contain a hash, so this is always unique
71 // we don't need to check usedNames nor add it
72 return a;
73};
74
75/** @typedef {Record<string, number>} Sizes */
76
77/**
78 * Adds the provided total to this object.
79 * @param {Sizes} total total size
80 * @param {Sizes} size single size
81 * @returns {void}
82 */
83const addSizeTo = (total, size) => {
84 for (const key of Object.keys(size)) {
85 total[key] = (total[key] || 0) + size[key];
86 }
87};
88
89/**
90 * Subtract size from.
91 * @param {Sizes} total total size
92 * @param {Sizes} size single size
93 * @returns {void}
94 */
95const subtractSizeFrom = (total, size) => {
96 for (const key of Object.keys(size)) {
97 total[key] -= size[key];
98 }
99};
100
101/**
102 * Returns total size.
103 * @template T
104 * @param {Iterable<Node<T>>} nodes some nodes
105 * @returns {Sizes} total size
106 */
107const sumSize = (nodes) => {
108 /** @type {Sizes} */
109 const sum = Object.create(null);
110 for (const node of nodes) {
111 addSizeTo(sum, node.size);
112 }
113 return sum;
114};
115
116/**
117 * Checks whether this object is too big.
118 * @param {Sizes} size size
119 * @param {Sizes} maxSize minimum size
120 * @returns {boolean} true, when size is too big
121 */
122const isTooBig = (size, maxSize) => {
123 for (const key of Object.keys(size)) {
124 const s = size[key];
125 if (s === 0) continue;
126 const maxSizeValue = maxSize[key];
127 if (typeof maxSizeValue === "number" && s > maxSizeValue) return true;
128 }
129 return false;
130};
131
132/**
133 * Checks whether this object is too small.
134 * @param {Sizes} size size
135 * @param {Sizes} minSize minimum size
136 * @returns {boolean} true, when size is too small
137 */
138const isTooSmall = (size, minSize) => {
139 for (const key of Object.keys(size)) {
140 const s = size[key];
141 if (s === 0) continue;
142 const minSizeValue = minSize[key];
143 if (typeof minSizeValue === "number" && s < minSizeValue) return true;
144 }
145 return false;
146};
147
148/** @typedef {Set<string>} Types */
149
150/**
151 * Gets too small types.
152 * @param {Sizes} size size
153 * @param {Sizes} minSize minimum size
154 * @returns {Types} set of types that are too small
155 */
156const getTooSmallTypes = (size, minSize) => {
157 /** @type {Types} */
158 const types = new Set();
159 for (const key of Object.keys(size)) {
160 const s = size[key];
161 if (s === 0) continue;
162 const minSizeValue = minSize[key];
163 if (typeof minSizeValue === "number" && s < minSizeValue) types.add(key);
164 }
165 return types;
166};
167
168/**
169 * Gets number of matching size types.
170 * @template {object} T
171 * @param {T} size size
172 * @param {Types} types types
173 * @returns {number} number of matching size types
174 */
175const getNumberOfMatchingSizeTypes = (size, types) => {
176 let i = 0;
177 for (const key of Object.keys(size)) {
178 if (size[/** @type {keyof T} */ (key)] !== 0 && types.has(key)) i++;
179 }
180 return i;
181};
182
183/**
184 * Selective size sum.
185 * @param {Sizes} size size
186 * @param {Types} types types
187 * @returns {number} selective size sum
188 */
189const selectiveSizeSum = (size, types) => {
190 let sum = 0;
191 for (const key of Object.keys(size)) {
192 if (size[key] !== 0 && types.has(key)) sum += size[key];
193 }
194 return sum;
195};
196
197/**
198 * Represents the node runtime component.
199 * @template T
200 */
201class Node {
202 /**
203 * Creates an instance of Node.
204 * @param {T} item item
205 * @param {string} key key
206 * @param {Sizes} size size
207 */
208 constructor(item, key, size) {
209 this.item = item;
210 this.key = key;
211 this.size = size;
212 }
213}
214
215/** @typedef {number[]} Similarities */
216
217/**
218 * Represents the group runtime component.
219 * @template T
220 */
221class Group {
222 /**
223 * Creates an instance of Group.
224 * @param {Node<T>[]} nodes nodes
225 * @param {Similarities | null} similarities similarities between the nodes (length = nodes.length - 1)
226 * @param {Sizes=} size size of the group
227 */
228 constructor(nodes, similarities, size) {
229 this.nodes = nodes;
230 this.similarities = similarities;
231 this.size = size || sumSize(nodes);
232 /** @type {string | undefined} */
233 this.key = undefined;
234 }
235
236 /**
237 * Returns removed nodes.
238 * @param {(node: Node<T>) => boolean} filter filter function
239 * @returns {Node<T>[] | undefined} removed nodes
240 */
241 popNodes(filter) {
242 /** @type {Node<T>[]} */
243 const newNodes = [];
244 /** @type {Similarities} */
245 const newSimilarities = [];
246 /** @type {Node<T>[]} */
247 const resultNodes = [];
248 /** @type {undefined | Node<T>} */
249 let lastNode;
250 for (let i = 0; i < this.nodes.length; i++) {
251 const node = this.nodes[i];
252 if (filter(node)) {
253 resultNodes.push(node);
254 } else {
255 if (newNodes.length > 0) {
256 newSimilarities.push(
257 lastNode === this.nodes[i - 1]
258 ? /** @type {Similarities} */ (this.similarities)[i - 1]
259 : similarity(/** @type {Node<T>} */ (lastNode).key, node.key)
260 );
261 }
262 newNodes.push(node);
263 lastNode = node;
264 }
265 }
266 if (resultNodes.length === this.nodes.length) return;
267 this.nodes = newNodes;
268 this.similarities = newSimilarities;
269 this.size = sumSize(newNodes);
270 return resultNodes;
271 }
272}
273
274/**
275 * Returns similarities.
276 * @template T
277 * @param {Iterable<Node<T>>} nodes nodes
278 * @returns {Similarities} similarities
279 */
280const getSimilarities = (nodes) => {
281 // calculate similarities between lexically adjacent nodes
282 /** @type {Similarities} */
283 const similarities = [];
284 /** @type {undefined | Node<T>} */
285 let last;
286 for (const node of nodes) {
287 if (last !== undefined) {
288 similarities.push(similarity(last.key, node.key));
289 }
290 last = node;
291 }
292 return similarities;
293};
294
295/**
296 * Defines the shared type used by this module.
297 * @template T
298 * @typedef {object} GroupedItems<T>
299 * @property {string} key
300 * @property {T[]} items
301 * @property {Sizes} size
302 */
303
304/**
305 * Defines the options type used by this module.
306 * @template T
307 * @typedef {object} Options
308 * @property {Sizes} maxSize maximum size of a group
309 * @property {Sizes} minSize minimum size of a group (preferred over maximum size)
310 * @property {Iterable<T>} items a list of items
311 * @property {(item: T) => Sizes} getSize function to get size of an item
312 * @property {(item: T) => string} getKey function to get the key of an item
313 */
314
315/**
316 * Returns grouped items.
317 * @template T
318 * @param {Options<T>} options options object
319 * @returns {GroupedItems<T>[]} grouped items
320 */
321module.exports = ({ maxSize, minSize, items, getSize, getKey }) => {
322 /** @type {Group<T>[]} */
323 const result = [];
324
325 const nodes = Array.from(
326 items,
327 (item) => new Node(item, getKey(item), getSize(item))
328 );
329
330 /** @type {Node<T>[]} */
331 const initialNodes = [];
332
333 // lexically ordering of keys
334 nodes.sort((a, b) => {
335 if (a.key < b.key) return -1;
336 if (a.key > b.key) return 1;
337 return 0;
338 });
339
340 // return nodes bigger than maxSize directly as group
341 // But make sure that minSize is not violated
342 for (const node of nodes) {
343 if (isTooBig(node.size, maxSize) && !isTooSmall(node.size, minSize)) {
344 result.push(new Group([node], []));
345 } else {
346 initialNodes.push(node);
347 }
348 }
349
350 if (initialNodes.length > 0) {
351 const initialGroup = new Group(initialNodes, getSimilarities(initialNodes));
352
353 /**
354 * Removes problematic nodes.
355 * @param {Group<T>} group group
356 * @param {Sizes} consideredSize size of the group to consider
357 * @returns {boolean} true, if the group was modified
358 */
359 const removeProblematicNodes = (group, consideredSize = group.size) => {
360 const problemTypes = getTooSmallTypes(consideredSize, minSize);
361 if (problemTypes.size > 0) {
362 // We hit an edge case where the working set is already smaller than minSize
363 // We merge problematic nodes with the smallest result node to keep minSize intact
364 const problemNodes = group.popNodes(
365 (n) => getNumberOfMatchingSizeTypes(n.size, problemTypes) > 0
366 );
367 if (problemNodes === undefined) return false;
368 // Only merge it with result nodes that have the problematic size type
369 const possibleResultGroups = result.filter(
370 (n) => getNumberOfMatchingSizeTypes(n.size, problemTypes) > 0
371 );
372 if (possibleResultGroups.length > 0) {
373 const bestGroup = possibleResultGroups.reduce((min, group) => {
374 const minMatches = getNumberOfMatchingSizeTypes(min, problemTypes);
375 const groupMatches = getNumberOfMatchingSizeTypes(
376 group,
377 problemTypes
378 );
379 if (minMatches !== groupMatches) {
380 return minMatches < groupMatches ? group : min;
381 }
382 if (
383 selectiveSizeSum(min.size, problemTypes) >
384 selectiveSizeSum(group.size, problemTypes)
385 ) {
386 return group;
387 }
388 return min;
389 });
390 for (const node of problemNodes) bestGroup.nodes.push(node);
391 bestGroup.nodes.sort((a, b) => {
392 if (a.key < b.key) return -1;
393 if (a.key > b.key) return 1;
394 return 0;
395 });
396 } else {
397 // There are no other nodes with the same size types
398 // We create a new group and have to accept that it's smaller than minSize
399 result.push(new Group(problemNodes, null));
400 }
401 return true;
402 }
403 return false;
404 };
405
406 if (initialGroup.nodes.length > 0) {
407 const queue = [initialGroup];
408
409 while (queue.length) {
410 const group = /** @type {Group<T>} */ (queue.pop());
411 // only groups bigger than maxSize need to be splitted
412 if (!isTooBig(group.size, maxSize)) {
413 result.push(group);
414 continue;
415 }
416 // If the group is already too small
417 // we try to work only with the unproblematic nodes
418 if (removeProblematicNodes(group)) {
419 // This changed something, so we try this group again
420 queue.push(group);
421 continue;
422 }
423
424 // find unsplittable area from left and right
425 // going minSize from left and right
426 // at least one node need to be included otherwise we get stuck
427 let left = 1;
428 /** @type {Sizes} */
429 const leftSize = Object.create(null);
430 addSizeTo(leftSize, group.nodes[0].size);
431 while (left < group.nodes.length && isTooSmall(leftSize, minSize)) {
432 addSizeTo(leftSize, group.nodes[left].size);
433 left++;
434 }
435 let right = group.nodes.length - 2;
436 /** @type {Sizes} */
437 const rightSize = Object.create(null);
438 addSizeTo(rightSize, group.nodes[group.nodes.length - 1].size);
439 while (right >= 0 && isTooSmall(rightSize, minSize)) {
440 addSizeTo(rightSize, group.nodes[right].size);
441 right--;
442 }
443
444 // left v v right
445 // [ O O O ] O O O [ O O O ]
446 // ^^^^^^^^^ leftSize
447 // rightSize ^^^^^^^^^
448 // leftSize > minSize
449 // rightSize > minSize
450
451 // Perfect split: [ O O O ] [ O O O ]
452 // right === left - 1
453
454 if (left - 1 > right) {
455 // We try to remove some problematic nodes to "fix" that
456 /** @type {Sizes} */
457 let prevSize;
458 if (right < group.nodes.length - left) {
459 subtractSizeFrom(rightSize, group.nodes[right + 1].size);
460 prevSize = rightSize;
461 } else {
462 subtractSizeFrom(leftSize, group.nodes[left - 1].size);
463 prevSize = leftSize;
464 }
465 if (removeProblematicNodes(group, prevSize)) {
466 // This changed something, so we try this group again
467 queue.push(group);
468 continue;
469 }
470 // can't split group while holding minSize
471 // because minSize is preferred of maxSize we return
472 // the problematic nodes as result here even while it's too big
473 // To avoid this make sure maxSize > minSize * 3
474 result.push(group);
475 continue;
476 }
477 if (left <= right) {
478 // when there is a area between left and right
479 // we look for best split point
480 // we split at the minimum similarity
481 // here key space is separated the most
482 // But we also need to make sure to not create too small groups
483 let best = -1;
484 let bestSimilarity = Infinity;
485 let pos = left;
486 const rightSize = sumSize(group.nodes.slice(pos));
487
488 // pos v v right
489 // [ O O O ] O O O [ O O O ]
490 // ^^^^^^^^^ leftSize
491 // rightSize ^^^^^^^^^^^^^^^
492
493 while (pos <= right + 1) {
494 const similarity =
495 /** @type {Similarities} */
496 (group.similarities)[pos - 1];
497 if (
498 similarity < bestSimilarity &&
499 !isTooSmall(leftSize, minSize) &&
500 !isTooSmall(rightSize, minSize)
501 ) {
502 best = pos;
503 bestSimilarity = similarity;
504 }
505 addSizeTo(leftSize, group.nodes[pos].size);
506 subtractSizeFrom(rightSize, group.nodes[pos].size);
507 pos++;
508 }
509 if (best < 0) {
510 // This can't happen
511 // but if that assumption is wrong
512 // fallback to a big group
513 result.push(group);
514 continue;
515 }
516 left = best;
517 right = best - 1;
518 }
519
520 // create two new groups for left and right area
521 // and queue them up
522 /** @type {Node<T>[]} */
523 const rightNodes = [group.nodes[right + 1]];
524 /** @type {Similarities} */
525 const rightSimilarities = [];
526 for (let i = right + 2; i < group.nodes.length; i++) {
527 rightSimilarities.push(
528 /** @type {Similarities} */ (group.similarities)[i - 1]
529 );
530 rightNodes.push(group.nodes[i]);
531 }
532 queue.push(new Group(rightNodes, rightSimilarities));
533
534 /** @type {Node<T>[]} */
535 const leftNodes = [group.nodes[0]];
536 /** @type {Similarities} */
537 const leftSimilarities = [];
538 for (let i = 1; i < left; i++) {
539 leftSimilarities.push(
540 /** @type {Similarities} */ (group.similarities)[i - 1]
541 );
542 leftNodes.push(group.nodes[i]);
543 }
544 queue.push(new Group(leftNodes, leftSimilarities));
545 }
546 }
547 }
548
549 // lexically ordering
550 result.sort((a, b) => {
551 if (a.nodes[0].key < b.nodes[0].key) return -1;
552 if (a.nodes[0].key > b.nodes[0].key) return 1;
553 return 0;
554 });
555
556 // give every group a name
557 /** @type {Set<string>} */
558 const usedNames = new Set();
559 for (let i = 0; i < result.length; i++) {
560 const group = result[i];
561 if (group.nodes.length === 1) {
562 group.key = group.nodes[0].key;
563 } else {
564 const first = group.nodes[0];
565 const last = group.nodes[group.nodes.length - 1];
566 const name = getName(first.key, last.key, usedNames);
567 group.key = name;
568 }
569 }
570
571 // return the results
572 return result.map(
573 (group) =>
574 /** @type {GroupedItems<T>} */
575 ({
576 key: group.key,
577 items: group.nodes.map((node) => node.item),
578 size: group.size
579 })
580 );
581};
Note: See TracBrowser for help on using the repository browser.