node_modules/watchpack/lib/reducePlan.js

   1 /*
   2         MIT License http://www.opensource.org/licenses/mit-license.php
   3         Author Tobias Koppers @sokra
   4 */
   5 "use strict";
   6
   7 const path = require("path");
   8
   9 /**
  10  * @template T
  11  * @typedef {Object} TreeNode
  12  * @property {string} filePath
  13  * @property {TreeNode} parent
  14  * @property {TreeNode[]} children
  15  * @property {number} entries
  16  * @property {boolean} active
  17  * @property {T[] | T | undefined} value
  18  */
  19
  20 /**
  21  * @template T
  22  * @param {Map<string, T[] | T} plan
  23  * @param {number} limit
  24  * @returns {Map<string, Map<T, string>>} the new plan
  25  */
  26 module.exports = (plan, limit) => {
  27         const treeMap = new Map();
  28         // Convert to tree
  29         for (const [filePath, value] of plan) {
  30                 treeMap.set(filePath, {
  31                         filePath,
  32                         parent: undefined,
  33                         children: undefined,
  34                         entries: 1,
  35                         active: true,
  36                         value
  37                 });
  38         }
  39         let currentCount = treeMap.size;
  40         // Create parents and calculate sum of entries
  41         for (const node of treeMap.values()) {
  42                 const parentPath = path.dirname(node.filePath);
  43                 if (parentPath !== node.filePath) {
  44                         let parent = treeMap.get(parentPath);
  45                         if (parent === undefined) {
  46                                 parent = {
  47                                         filePath: parentPath,
  48                                         parent: undefined,
  49                                         children: [node],
  50                                         entries: node.entries,
  51                                         active: false,
  52                                         value: undefined
  53                                 };
  54                                 treeMap.set(parentPath, parent);
  55                                 node.parent = parent;
  56                         } else {
  57                                 node.parent = parent;
  58                                 if (parent.children === undefined) {
  59                                         parent.children = [node];
  60                                 } else {
  61                                         parent.children.push(node);
  62                                 }
  63                                 do {
  64                                         parent.entries += node.entries;
  65                                         parent = parent.parent;
  66                                 } while (parent);
  67                         }
  68                 }
  69         }
  70         // Reduce until limit reached
  71         while (currentCount > limit) {
  72                 // Select node that helps reaching the limit most effectively without overmerging
  73                 const overLimit = currentCount - limit;
  74                 let bestNode = undefined;
  75                 let bestCost = Infinity;
  76                 for (const node of treeMap.values()) {
  77                         if (node.entries <= 1 || !node.children || !node.parent) continue;
  78                         if (node.children.length === 0) continue;
  79                         if (node.children.length === 1 && !node.value) continue;
  80                         // Try to select the node with has just a bit more entries than we need to reduce
  81                         // When just a bit more is over 30% over the limit,
  82                         // also consider just a bit less entries then we need to reduce
  83                         const cost =
  84                                 node.entries - 1 >= overLimit
  85                                         ? node.entries - 1 - overLimit
  86                                         : overLimit - node.entries + 1 + limit * 0.3;
  87                         if (cost < bestCost) {
  88                                 bestNode = node;
  89                                 bestCost = cost;
  90                         }
  91                 }
  92                 if (!bestNode) break;
  93                 // Merge all children
  94                 const reduction = bestNode.entries - 1;
  95                 bestNode.active = true;
  96                 bestNode.entries = 1;
  97                 currentCount -= reduction;
  98                 let parent = bestNode.parent;
  99                 while (parent) {
 100                         parent.entries -= reduction;
 101                         parent = parent.parent;
 102                 }
 103                 const queue = new Set(bestNode.children);
 104                 for (const node of queue) {
 105                         node.active = false;
 106                         node.entries = 0;
 107                         if (node.children) {
 108                                 for (const child of node.children) queue.add(child);
 109                         }
 110                 }
 111         }
 112         // Write down new plan
 113         const newPlan = new Map();
 114         for (const rootNode of treeMap.values()) {
 115                 if (!rootNode.active) continue;
 116                 const map = new Map();
 117                 const queue = new Set([rootNode]);
 118                 for (const node of queue) {
 119                         if (node.active && node !== rootNode) continue;
 120                         if (node.value) {
 121                                 if (Array.isArray(node.value)) {
 122                                         for (const item of node.value) {
 123                                                 map.set(item, node.filePath);
 124                                         }
 125                                 } else {
 126                                         map.set(node.value, node.filePath);
 127                                 }
 128                         }
 129                         if (node.children) {
 130                                 for (const child of node.children) {
 131                                         queue.add(child);
 132                                 }
 133                         }
 134                 }
 135                 newPlan.set(rootNode.filePath, map);
 136         }
 137         return newPlan;
 138 };