node_modules/webpack/lib/util/smartGrouping.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 /**
   9  * @typedef {Object} GroupOptions
  10  * @property {boolean=} groupChildren
  11  * @property {boolean=} force
  12  * @property {number=} targetGroupCount
  13  */
  14
  15 /**
  16  * @template T
  17  * @template R
  18  * @typedef {Object} GroupConfig
  19  * @property {function(T): string[]} getKeys
  20  * @property {function(string, (R | T)[], T[]): R} createGroup
  21  * @property {function(string, T[]): GroupOptions=} getOptions
  22  */
  23
  24 /**
  25  * @template T
  26  * @template R
  27  * @typedef {Object} ItemWithGroups
  28  * @property {T} item
  29  * @property {Set<Group<T, R>>} groups
  30  */
  31
  32 /**
  33  * @template T
  34  * @template R
  35  * @typedef {{ config: GroupConfig<T, R>, name: string, alreadyGrouped: boolean, items: Set<ItemWithGroups<T, R>> | undefined }} Group
  36  */
  37
  38 /**
  39  * @template T
  40  * @template R
  41  * @param {T[]} items the list of items
  42  * @param {GroupConfig<T, R>[]} groupConfigs configuration
  43  * @returns {(R | T)[]} grouped items
  44  */
  45 const smartGrouping = (items, groupConfigs) => {
  46         /** @type {Set<ItemWithGroups<T, R>>} */
  47         const itemsWithGroups = new Set();
  48         /** @type {Map<string, Group<T, R>>} */
  49         const allGroups = new Map();
  50         for (const item of items) {
  51                 /** @type {Set<Group<T, R>>} */
  52                 const groups = new Set();
  53                 for (let i = 0; i < groupConfigs.length; i++) {
  54                         const groupConfig = groupConfigs[i];
  55                         const keys = groupConfig.getKeys(item);
  56                         if (keys) {
  57                                 for (const name of keys) {
  58                                         const key = `${i}:${name}`;
  59                                         let group = allGroups.get(key);
  60                                         if (group === undefined) {
  61                                                 allGroups.set(
  62                                                         key,
  63                                                         (group = {
  64                                                                 config: groupConfig,
  65                                                                 name,
  66                                                                 alreadyGrouped: false,
  67                                                                 items: undefined
  68                                                         })
  69                                                 );
  70                                         }
  71                                         groups.add(group);
  72                                 }
  73                         }
  74                 }
  75                 itemsWithGroups.add({
  76                         item,
  77                         groups
  78                 });
  79         }
  80         /**
  81          * @param {Set<ItemWithGroups<T, R>>} itemsWithGroups input items with groups
  82          * @returns {(T | R)[]} groups items
  83          */
  84         const runGrouping = itemsWithGroups => {
  85                 const totalSize = itemsWithGroups.size;
  86                 for (const entry of itemsWithGroups) {
  87                         for (const group of entry.groups) {
  88                                 if (group.alreadyGrouped) continue;
  89                                 const items = group.items;
  90                                 if (items === undefined) {
  91                                         group.items = new Set([entry]);
  92                                 } else {
  93                                         items.add(entry);
  94                                 }
  95                         }
  96                 }
  97                 /** @type {Map<Group<T, R>, { items: Set<ItemWithGroups<T, R>>, options: GroupOptions | false | undefined, used: boolean }>} */
  98                 const groupMap = new Map();
  99                 for (const group of allGroups.values()) {
 100                         if (group.items) {
 101                                 const items = group.items;
 102                                 group.items = undefined;
 103                                 groupMap.set(group, {
 104                                         items,
 105                                         options: undefined,
 106                                         used: false
 107                                 });
 108                         }
 109                 }
 110                 /** @type {(T | R)[]} */
 111                 const results = [];
 112                 for (;;) {
 113                         /** @type {Group<T, R>} */
 114                         let bestGroup = undefined;
 115                         let bestGroupSize = -1;
 116                         let bestGroupItems = undefined;
 117                         let bestGroupOptions = undefined;
 118                         for (const [group, state] of groupMap) {
 119                                 const { items, used } = state;
 120                                 let options = state.options;
 121                                 if (options === undefined) {
 122                                         const groupConfig = group.config;
 123                                         state.options = options =
 124                                                 (groupConfig.getOptions &&
 125                                                         groupConfig.getOptions(
 126                                                                 group.name,
 127                                                                 Array.from(items, ({ item }) => item)
 128                                                         )) ||
 129                                                 false;
 130                                 }
 131
 132                                 const force = options && options.force;
 133                                 if (!force) {
 134                                         if (bestGroupOptions && bestGroupOptions.force) continue;
 135                                         if (used) continue;
 136                                         if (items.size <= 1 || totalSize - items.size <= 1) {
 137                                                 continue;
 138                                         }
 139                                 }
 140                                 const targetGroupCount = (options && options.targetGroupCount) || 4;
 141                                 let sizeValue = force
 142                                         ? items.size
 143                                         : Math.min(
 144                                                         items.size,
 145                                                         (totalSize * 2) / targetGroupCount +
 146                                                                 itemsWithGroups.size -
 147                                                                 items.size
 148                                           );
 149                                 if (
 150                                         sizeValue > bestGroupSize ||
 151                                         (force && (!bestGroupOptions || !bestGroupOptions.force))
 152                                 ) {
 153                                         bestGroup = group;
 154                                         bestGroupSize = sizeValue;
 155                                         bestGroupItems = items;
 156                                         bestGroupOptions = options;
 157                                 }
 158                         }
 159                         if (bestGroup === undefined) {
 160                                 break;
 161                         }
 162                         const items = new Set(bestGroupItems);
 163                         const options = bestGroupOptions;
 164
 165                         const groupChildren = !options || options.groupChildren !== false;
 166
 167                         for (const item of items) {
 168                                 itemsWithGroups.delete(item);
 169                                 // Remove all groups that items have from the map to not select them again
 170                                 for (const group of item.groups) {
 171                                         const state = groupMap.get(group);
 172                                         if (state !== undefined) {
 173                                                 state.items.delete(item);
 174                                                 if (state.items.size === 0) {
 175                                                         groupMap.delete(group);
 176                                                 } else {
 177                                                         state.options = undefined;
 178                                                         if (groupChildren) {
 179                                                                 state.used = true;
 180                                                         }
 181                                                 }
 182                                         }
 183                                 }
 184                         }
 185                         groupMap.delete(bestGroup);
 186
 187                         const key = bestGroup.name;
 188                         const groupConfig = bestGroup.config;
 189
 190                         const allItems = Array.from(items, ({ item }) => item);
 191
 192                         bestGroup.alreadyGrouped = true;
 193                         const children = groupChildren ? runGrouping(items) : allItems;
 194                         bestGroup.alreadyGrouped = false;
 195
 196                         results.push(groupConfig.createGroup(key, children, allItems));
 197                 }
 198                 for (const { item } of itemsWithGroups) {
 199                         results.push(item);
 200                 }
 201                 return results;
 202         };
 203         return runGrouping(itemsWithGroups);
 204 };
 205
 206 module.exports = smartGrouping;