node_modules/webpack/lib/util/deterministicGrouping.js

   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  */
  33 const 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  */
  50 const 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  */
  79 const 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  */
  90 const 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  */
 100 const 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 const 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
 120 const 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
 132 const 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
 145 const 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
 153 const 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  */
 164 class 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  */
 180 class 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  */
 231 const 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  */
 268 module.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<T>} */
 502                 return {
 503                         key: group.key,
 504                         items: group.nodes.map(node => node.item),
 505                         size: group.size
 506                 };
 507         });
 508 };