source: trip-planner-front/node_modules/webpack/lib/util/deterministicGrouping.js@ 59329aa

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

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