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

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

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