审查视图

node_modules/watchpack/lib/reducePlan.js 3.5 KB
LiYang authored
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
/*
	MIT License http://www.opensource.org/licenses/mit-license.php
	Author Tobias Koppers @sokra
*/
"use strict";

const path = require("path");

/**
 * @template T
 * @typedef {Object} TreeNode
 * @property {string} filePath
 * @property {TreeNode} parent
 * @property {TreeNode[]} children
 * @property {number} entries
 * @property {boolean} active
 * @property {T[] | T | undefined} value
 */

/**
 * @template T
 * @param {Map<string, T[] | T} plan
 * @param {number} limit
 * @returns {Map<string, Map<T, string>>} the new plan
 */
module.exports = (plan, limit) => {
	const treeMap = new Map();
	// Convert to tree
	for (const [filePath, value] of plan) {
		treeMap.set(filePath, {
			filePath,
			parent: undefined,
			children: undefined,
			entries: 1,
			active: true,
			value
		});
	}
	let currentCount = treeMap.size;
	// Create parents and calculate sum of entries
	for (const node of treeMap.values()) {
		const parentPath = path.dirname(node.filePath);
		if (parentPath !== node.filePath) {
			let parent = treeMap.get(parentPath);
			if (parent === undefined) {
				parent = {
					filePath: parentPath,
					parent: undefined,
					children: [node],
					entries: node.entries,
					active: false,
					value: undefined
				};
				treeMap.set(parentPath, parent);
				node.parent = parent;
			} else {
				node.parent = parent;
				if (parent.children === undefined) {
					parent.children = [node];
				} else {
					parent.children.push(node);
				}
				do {
					parent.entries += node.entries;
					parent = parent.parent;
				} while (parent);
			}
		}
	}
	// Reduce until limit reached
	while (currentCount > limit) {
		// Select node that helps reaching the limit most effectively without overmerging
		const overLimit = currentCount - limit;
		let bestNode = undefined;
		let bestCost = Infinity;
		for (const node of treeMap.values()) {
			if (node.entries <= 1 || !node.children || !node.parent) continue;
			if (node.children.length === 0) continue;
			if (node.children.length === 1 && !node.value) continue;
			// Try to select the node with has just a bit more entries than we need to reduce
			// When just a bit more is over 30% over the limit,
			// also consider just a bit less entries then we need to reduce
			const cost =
				node.entries - 1 >= overLimit
					? node.entries - 1 - overLimit
					: overLimit - node.entries + 1 + limit * 0.3;
			if (cost < bestCost) {
				bestNode = node;
				bestCost = cost;
			}
		}
		if (!bestNode) break;
		// Merge all children
		const reduction = bestNode.entries - 1;
		bestNode.active = true;
		bestNode.entries = 1;
		currentCount -= reduction;
		let parent = bestNode.parent;
		while (parent) {
			parent.entries -= reduction;
			parent = parent.parent;
		}
		const queue = new Set(bestNode.children);
		for (const node of queue) {
			node.active = false;
			node.entries = 0;
			if (node.children) {
				for (const child of node.children) queue.add(child);
			}
		}
	}
	// Write down new plan
	const newPlan = new Map();
	for (const rootNode of treeMap.values()) {
		if (!rootNode.active) continue;
		const map = new Map();
		const queue = new Set([rootNode]);
		for (const node of queue) {
			if (node.active && node !== rootNode) continue;
			if (node.value) {
				if (Array.isArray(node.value)) {
					for (const item of node.value) {
						map.set(item, node.filePath);
					}
				} else {
					map.set(node.value, node.filePath);
				}
			}
			if (node.children) {
				for (const child of node.children) {
					queue.add(child);
				}
			}
		}
		newPlan.set(rootNode.filePath, map);
	}
	return newPlan;
};