code:
/*
	MIT License http://www.opensource.org/licenses/mit-license.php
	Author Tobias Koppers @sokra
*/

"use strict";

const AsyncDependencyToInitialChunkError = require("./AsyncDependencyToInitialChunkError");
const { connectChunkGroupParentAndChild } = require("./GraphHelpers");
const ModuleGraphConnection = require("./ModuleGraphConnection");
const { getEntryRuntime, mergeRuntime } = require("./util/runtime");

/** @typedef {import("./AsyncDependenciesBlock")} AsyncDependenciesBlock */
/** @typedef {import("./Chunk")} Chunk */
/** @typedef {import("./ChunkGroup")} ChunkGroup */
/** @typedef {import("./Compilation")} Compilation */
/** @typedef {import("./DependenciesBlock")} DependenciesBlock */
/** @typedef {import("./Dependency")} Dependency */
/** @typedef {import("./Dependency").DependencyLocation} DependencyLocation */
/** @typedef {import("./Entrypoint")} Entrypoint */
/** @typedef {import("./Module")} Module */
/** @typedef {import("./ModuleGraph")} ModuleGraph */
/** @typedef {import("./ModuleGraphConnection").ConnectionState} ConnectionState */
/** @typedef {import("./logging/Logger").Logger} Logger */
/** @typedef {import("./util/runtime").RuntimeSpec} RuntimeSpec */

/**
 * @typedef {object} QueueItem
 * @property {number} action
 * @property {DependenciesBlock} block
 * @property {Module} module
 * @property {Chunk} chunk
 * @property {ChunkGroup} chunkGroup
 * @property {ChunkGroupInfo} chunkGroupInfo
 */

/**
 * @typedef {object} ChunkGroupInfo
 * @property {ChunkGroup} chunkGroup the chunk group
 * @property {RuntimeSpec} runtime the runtimes
 * @property {bigint | undefined} minAvailableModules current minimal set of modules available at this point
 * @property {bigint[]} availableModulesToBeMerged enqueued updates to the minimal set of available modules
 * @property {Set<Module>=} skippedItems modules that were skipped because module is already available in parent chunks (need to reconsider when minAvailableModules is shrinking)
 * @property {Set<[Module, ModuleGraphConnection[]]>=} skippedModuleConnections referenced modules that where skipped because they were not active in this runtime
 * @property {bigint | undefined} resultingAvailableModules set of modules available including modules from this chunk group
 * @property {Set<ChunkGroupInfo> | undefined} children set of children chunk groups, that will be revisited when availableModules shrink
 * @property {Set<ChunkGroupInfo> | undefined} availableSources set of chunk groups that are the source for minAvailableModules
 * @property {Set<ChunkGroupInfo> | undefined} availableChildren set of chunk groups which depend on the this chunk group as availableSource
 * @property {number} preOrderIndex next pre order index
 * @property {number} postOrderIndex next post order index
 * @property {boolean} chunkLoading has a chunk loading mechanism
 * @property {boolean} asyncChunks create async chunks
 */

/**
 * @typedef {object} BlockChunkGroupConnection
 * @property {ChunkGroupInfo} originChunkGroupInfo origin chunk group
 * @property {ChunkGroup} chunkGroup referenced chunk group
 */

/** @typedef {(Module | ConnectionState | ModuleGraphConnection)[]} BlockModulesInTuples */
/** @typedef {(Module | ConnectionState | ModuleGraphConnection[])[]} BlockModulesInFlattenTuples */
/** @typedef {Map<DependenciesBlock, BlockModulesInFlattenTuples>} BlockModulesMap */
/** @typedef {Map<Chunk, bigint>} MaskByChunk */
/** @typedef {Set<DependenciesBlock>} BlocksWithNestedBlocks */
/** @typedef {Map<AsyncDependenciesBlock, BlockChunkGroupConnection[]>} BlockConnections */
/** @typedef {Map<ChunkGroup, ChunkGroupInfo>} ChunkGroupInfoMap */
/** @typedef {Set<ChunkGroup>} AllCreatedChunkGroups */
/** @typedef {Map<Entrypoint, Module[]>} InputEntrypointsAndModules */

const ZERO_BIGINT = BigInt(0);
const ONE_BIGINT = BigInt(1);

/**
 * @param {bigint} mask The mask to test
 * @param {number} ordinal The ordinal of the bit to test
 * @returns {boolean} If the ordinal-th bit is set in the mask
 */
const isOrdinalSetInMask = (mask, ordinal) =>
	BigInt.asUintN(1, mask >> BigInt(ordinal)) !== ZERO_BIGINT;

/**
 * @param {ModuleGraphConnection[]} connections list of connections
 * @param {RuntimeSpec} runtime for which runtime
 * @returns {ConnectionState} connection state
 */
const getActiveStateOfConnections = (connections, runtime) => {
	let merged = connections[0].getActiveState(runtime);
	if (merged === true) return true;
	for (let i = 1; i < connections.length; i++) {
		const c = connections[i];
		merged = ModuleGraphConnection.addConnectionStates(
			merged,
			c.getActiveState(runtime)
		);
		if (merged === true) return true;
	}
	return merged;
};

/**
 * @param {Module} module module
 * @param {ModuleGraph} moduleGraph module graph
 * @param {RuntimeSpec} runtime runtime
 * @param {BlockModulesMap} blockModulesMap block modules map
 */
const extractBlockModules = (module, moduleGraph, runtime, blockModulesMap) => {
	/** @type {DependenciesBlock | undefined} */
	let blockCache;
	/** @type {BlockModulesInTuples | undefined} */
	let modules;

	/** @type {BlockModulesInTuples[]} */
	const arrays = [];

	/** @type {DependenciesBlock[]} */
	const queue = [module];
	while (queue.length > 0) {
		const block = /** @type {DependenciesBlock} */ (queue.pop());
		/** @type {Module[]} */
		const arr = [];
		arrays.push(arr);
		blockModulesMap.set(block, arr);
		for (const b of block.blocks) {
			queue.push(b);
		}
	}

	for (const connection of moduleGraph.getOutgoingConnections(module)) {
		const d = connection.dependency;
		// We skip connections without dependency
		if (!d) continue;
		const m = connection.module;
		// We skip connections without Module pointer
		if (!m) continue;
		// We skip weak connections
		if (connection.weak) continue;

		const block = moduleGraph.getParentBlock(d);
		let index = moduleGraph.getParentBlockIndex(d);

		// deprecated fallback
		if (index < 0) {
			index = /** @type {DependenciesBlock} */ (block).dependencies.indexOf(d);
		}

		if (blockCache !== block) {
			modules =
				/** @type {BlockModulesInTuples} */
				(
					blockModulesMap.get(
						(blockCache = /** @type {DependenciesBlock} */ (block))
					)
				);
		}

		const i = index * 3;
		/** @type {BlockModulesInTuples} */
		(modules)[i] = m;
		/** @type {BlockModulesInTuples} */
		(modules)[i + 1] = connection.getActiveState(runtime);
		/** @type {BlockModulesInTuples} */
		(modules)[i + 2] = connection;
	}

	for (const modules of arrays) {
		if (modules.length === 0) continue;
		let indexMap;
		let length = 0;
		outer: for (let j = 0; j < modules.length; j += 3) {
			const m = modules[j];
			if (m === undefined) continue;
			const state = /** @type {ConnectionState} */ (modules[j + 1]);
			const connection = /** @type {ModuleGraphConnection} */ (modules[j + 2]);
			if (indexMap === undefined) {
				let i = 0;
				for (; i < length; i += 3) {
					if (modules[i] === m) {
						const merged = /** @type {ConnectionState} */ (modules[i + 1]);
						/** @type {ModuleGraphConnection[]} */
						(/** @type {unknown} */ (modules[i + 2])).push(connection);
						if (merged === true) continue outer;
						modules[i + 1] = ModuleGraphConnection.addConnectionStates(
							merged,
							state
						);
						continue outer;
					}
				}
				modules[length] = m;
				length++;
				modules[length] = state;
				length++;
				/** @type {ModuleGraphConnection[]} */
				(/** @type {unknown} */ (modules[length])) = [connection];
				length++;
				if (length > 30) {
					// To avoid worse case performance, we will use an index map for
					// linear cost access, which allows to maintain O(n) complexity
					// while keeping allocations down to a minimum
					indexMap = new Map();
					for (let i = 0; i < length; i += 3) {
						indexMap.set(modules[i], i + 1);
					}
				}
			} else {
				const idx = indexMap.get(m);
				if (idx !== undefined) {
					const merged = /** @type {ConnectionState} */ (modules[idx]);
					/** @type {ModuleGraphConnection[]} */
					(/** @type {unknown} */ (modules[idx + 1])).push(connection);
					if (merged === true) continue outer;
					modules[idx] = ModuleGraphConnection.addConnectionStates(
						merged,
						state
					);
				} else {
					modules[length] = m;
					length++;
					modules[length] = state;
					indexMap.set(m, length);
					length++;
					/** @type {ModuleGraphConnection[]} */
					(
						/** @type {unknown} */
						(modules[length])
					) = [connection];
					length++;
				}
			}
		}
		modules.length = length;
	}
};

/**
 *
 * @param {Logger} logger a logger
 * @param {Compilation} compilation the compilation
 * @param {InputEntrypointsAndModules} inputEntrypointsAndModules chunk groups which are processed with the modules
 * @param {ChunkGroupInfoMap} chunkGroupInfoMap mapping from chunk group to available modules
 * @param {BlockConnections} blockConnections connection for blocks
 * @param {BlocksWithNestedBlocks} blocksWithNestedBlocks flag for blocks that have nested blocks
 * @param {AllCreatedChunkGroups} allCreatedChunkGroups filled with all chunk groups that are created here
 * @param {MaskByChunk} maskByChunk module content mask by chunk
 */
const visitModules = (
	logger,
	compilation,
	inputEntrypointsAndModules,
	chunkGroupInfoMap,
	blockConnections,
	blocksWithNestedBlocks,
	allCreatedChunkGroups,
	maskByChunk
) => {
	const { moduleGraph, chunkGraph, moduleMemCaches } = compilation;

	const blockModulesRuntimeMap = new Map();

	/** @type {BlockModulesMap | undefined} */
	let blockModulesMap;

	/** @type {Map<Module, number>} */
	const ordinalByModule = new Map();

	/**
	 * @param {Module} module The module to look up
	 * @returns {number} The ordinal of the module in masks
	 */
	const getModuleOrdinal = module => {
		let ordinal = ordinalByModule.get(module);
		if (ordinal === undefined) {
			ordinal = ordinalByModule.size;
			ordinalByModule.set(module, ordinal);
		}
		return ordinal;
	};

	for (const chunk of compilation.chunks) {
		let mask = ZERO_BIGINT;
		for (const m of chunkGraph.getChunkModulesIterable(chunk)) {
			mask |= ONE_BIGINT << BigInt(getModuleOrdinal(m));
		}
		maskByChunk.set(chunk, mask);
	}

	/**
	 *
	 * @param {DependenciesBlock} block block
	 * @param {RuntimeSpec} runtime runtime
	 * @returns {BlockModulesInFlattenTuples} block modules in flatten tuples
	 */
	const getBlockModules = (block, runtime) => {
		blockModulesMap = blockModulesRuntimeMap.get(runtime);
		if (blockModulesMap === undefined) {
			blockModulesMap = new Map();
			blockModulesRuntimeMap.set(runtime, blockModulesMap);
		}
		let blockModules = blockModulesMap.get(block);
		if (blockModules !== undefined) return blockModules;
		const module = /** @type {Module} */ (block.getRootBlock());
		const memCache = moduleMemCaches && moduleMemCaches.get(module);
		if (memCache !== undefined) {
			const map = memCache.provide(
				"bundleChunkGraph.blockModules",
				runtime,
				() => {
					logger.time("visitModules: prepare");
					const map = new Map();
					extractBlockModules(module, moduleGraph, runtime, map);
					logger.timeAggregate("visitModules: prepare");
					return map;
				}
			);
			for (const [block, blockModules] of map)
				blockModulesMap.set(block, blockModules);
			return map.get(block);
		} else {
			logger.time("visitModules: prepare");
			extractBlockModules(module, moduleGraph, runtime, blockModulesMap);
			blockModules =
				/** @type {BlockModulesInFlattenTuples} */
				(blockModulesMap.get(block));
			logger.timeAggregate("visitModules: prepare");
			return blockModules;
		}
	};

	let statProcessedQueueItems = 0;
	let statProcessedBlocks = 0;
	let statConnectedChunkGroups = 0;
	let statProcessedChunkGroupsForMerging = 0;
	let statMergedAvailableModuleSets = 0;
	let statForkedAvailableModules = 0;
	let statForkedAvailableModulesCount = 0;
	let statForkedAvailableModulesCountPlus = 0;
	let statForkedMergedModulesCount = 0;
	let statForkedMergedModulesCountPlus = 0;
	let statForkedResultModulesCount = 0;
	let statChunkGroupInfoUpdated = 0;
	let statChildChunkGroupsReconnected = 0;

	let nextChunkGroupIndex = 0;
	let nextFreeModulePreOrderIndex = 0;
	let nextFreeModulePostOrderIndex = 0;

	/** @type {Map<DependenciesBlock, ChunkGroupInfo>} */
	const blockChunkGroups = new Map();

	/** @type {Map<ChunkGroupInfo, DependenciesBlock>} */
	const blockByChunkGroups = new Map();

	/** @type {Map<string, ChunkGroupInfo>} */
	const namedChunkGroups = new Map();

	/** @type {Map<string, ChunkGroupInfo>} */
	const namedAsyncEntrypoints = new Map();

	/** @type {Set<ChunkGroupInfo>} */
	const outdatedOrderIndexChunkGroups = new Set();

	const ADD_AND_ENTER_ENTRY_MODULE = 0;
	const ADD_AND_ENTER_MODULE = 1;
	const ENTER_MODULE = 2;
	const PROCESS_BLOCK = 3;
	const PROCESS_ENTRY_BLOCK = 4;
	const LEAVE_MODULE = 5;

	/** @type {QueueItem[]} */
	let queue = [];

	/** @type {Map<ChunkGroupInfo, Set<ChunkGroupInfo>>} */
	const queueConnect = new Map();
	/** @type {Set<ChunkGroupInfo>} */
	const chunkGroupsForCombining = new Set();

	// Fill queue with entrypoint modules
	// Create ChunkGroupInfo for entrypoints
	for (const [chunkGroup, modules] of inputEntrypointsAndModules) {
		const runtime = getEntryRuntime(
			compilation,
			/** @type {string} */ (chunkGroup.name),
			chunkGroup.options
		);
		/** @type {ChunkGroupInfo} */
		const chunkGroupInfo = {
			chunkGroup,
			runtime,
			minAvailableModules: undefined,
			availableModulesToBeMerged: [],
			skippedItems: undefined,
			resultingAvailableModules: undefined,
			children: undefined,
			availableSources: undefined,
			availableChildren: undefined,
			preOrderIndex: 0,
			postOrderIndex: 0,
			chunkLoading:
				chunkGroup.options.chunkLoading !== undefined
					? chunkGroup.options.chunkLoading !== false
					: compilation.outputOptions.chunkLoading !== false,
			asyncChunks:
				chunkGroup.options.asyncChunks !== undefined
					? chunkGroup.options.asyncChunks
					: compilation.outputOptions.asyncChunks !== false
		};
		chunkGroup.index = nextChunkGroupIndex++;
		if (chunkGroup.getNumberOfParents() > 0) {
			// minAvailableModules for child entrypoints are unknown yet, set to undefined.
			// This means no module is added until other sets are merged into
			// this minAvailableModules (by the parent entrypoints)
			const skippedItems = new Set(modules);
			chunkGroupInfo.skippedItems = skippedItems;
			chunkGroupsForCombining.add(chunkGroupInfo);
		} else {
			// The application may start here: We start with an empty list of available modules
			chunkGroupInfo.minAvailableModules = ZERO_BIGINT;
			const chunk = chunkGroup.getEntrypointChunk();
			for (const module of modules) {
				queue.push({
					action: ADD_AND_ENTER_MODULE,
					block: module,
					module,
					chunk,
					chunkGroup,
					chunkGroupInfo
				});
			}
		}
		chunkGroupInfoMap.set(chunkGroup, chunkGroupInfo);
		if (chunkGroup.name) {
			namedChunkGroups.set(chunkGroup.name, chunkGroupInfo);
		}
	}
	// Fill availableSources with parent-child dependencies between entrypoints
	for (const chunkGroupInfo of chunkGroupsForCombining) {
		const { chunkGroup } = chunkGroupInfo;
		chunkGroupInfo.availableSources = new Set();
		for (const parent of chunkGroup.parentsIterable) {
			const parentChunkGroupInfo =
				/** @type {ChunkGroupInfo} */
				(chunkGroupInfoMap.get(parent));
			chunkGroupInfo.availableSources.add(parentChunkGroupInfo);
			if (parentChunkGroupInfo.availableChildren === undefined) {
				parentChunkGroupInfo.availableChildren = new Set();
			}
			parentChunkGroupInfo.availableChildren.add(chunkGroupInfo);
		}
	}
	// pop() is used to read from the queue
	// so it need to be reversed to be iterated in
	// correct order
	queue.reverse();

	/** @type {Set<ChunkGroupInfo>} */
	const outdatedChunkGroupInfo = new Set();
	/** @type {Set<ChunkGroupInfo>} */
	const chunkGroupsForMerging = new Set();
	/** @type {QueueItem[]} */
	let queueDelayed = [];

	/** @type {[Module, ModuleGraphConnection[]][]} */
	const skipConnectionBuffer = [];
	/** @type {Module[]} */
	const skipBuffer = [];
	/** @type {QueueItem[]} */
	const queueBuffer = [];

	/** @type {Module} */
	let module;
	/** @type {Chunk} */
	let chunk;
	/** @type {ChunkGroup} */
	let chunkGroup;
	/** @type {DependenciesBlock} */
	let block;
	/** @type {ChunkGroupInfo} */
	let chunkGroupInfo;

	// For each async Block in graph
	/**
	 * @param {AsyncDependenciesBlock} b iterating over each Async DepBlock
	 * @returns {void}
	 */
	const iteratorBlock = b => {
		// 1. We create a chunk group with single chunk in it for this Block
		// but only once (blockChunkGroups map)
		/** @type {ChunkGroupInfo | undefined} */
		let cgi = blockChunkGroups.get(b);
		/** @type {ChunkGroup | undefined} */
		let c;
		/** @type {Entrypoint | undefined} */
		let entrypoint;
		const entryOptions = b.groupOptions && b.groupOptions.entryOptions;
		if (cgi === undefined) {
			const chunkName = (b.groupOptions && b.groupOptions.name) || b.chunkName;
			if (entryOptions) {
				cgi = namedAsyncEntrypoints.get(/** @type {string} */ (chunkName));
				if (!cgi) {
					entrypoint = compilation.addAsyncEntrypoint(
						entryOptions,
						module,
						/** @type {DependencyLocation} */ (b.loc),
						/** @type {string} */ (b.request)
					);
					maskByChunk.set(entrypoint.chunks[0], ZERO_BIGINT);
					entrypoint.index = nextChunkGroupIndex++;
					cgi = {
						chunkGroup: entrypoint,
						runtime: entrypoint.options.runtime || entrypoint.name,
						minAvailableModules: ZERO_BIGINT,
						availableModulesToBeMerged: [],
						skippedItems: undefined,
						resultingAvailableModules: undefined,
						children: undefined,
						availableSources: undefined,
						availableChildren: undefined,
						preOrderIndex: 0,
						postOrderIndex: 0,
						chunkLoading:
							entryOptions.chunkLoading !== undefined
								? entryOptions.chunkLoading !== false
								: chunkGroupInfo.chunkLoading,
						asyncChunks:
							entryOptions.asyncChunks !== undefined
								? entryOptions.asyncChunks
								: chunkGroupInfo.asyncChunks
					};
					chunkGroupInfoMap.set(entrypoint, cgi);

					chunkGraph.connectBlockAndChunkGroup(b, entrypoint);
					if (chunkName) {
						namedAsyncEntrypoints.set(chunkName, cgi);
					}
				} else {
					entrypoint = /** @type {Entrypoint} */ (cgi.chunkGroup);
					// TODO merge entryOptions
					entrypoint.addOrigin(
						module,
						/** @type {DependencyLocation} */ (b.loc),
						/** @type {string} */ (b.request)
					);
					chunkGraph.connectBlockAndChunkGroup(b, entrypoint);
				}

				// 2. We enqueue the DependenciesBlock for traversal
				queueDelayed.push({
					action: PROCESS_ENTRY_BLOCK,
					block: b,
					module,
					chunk: entrypoint.chunks[0],
					chunkGroup: entrypoint,
					chunkGroupInfo: cgi
				});
			} else if (!chunkGroupInfo.asyncChunks || !chunkGroupInfo.chunkLoading) {
				// Just queue the block into the current chunk group
				queue.push({
					action: PROCESS_BLOCK,
					block: b,
					module,
					chunk,
					chunkGroup,
					chunkGroupInfo
				});
			} else {
				cgi = chunkName ? namedChunkGroups.get(chunkName) : undefined;
				if (!cgi) {
					c = compilation.addChunkInGroup(
						b.groupOptions || b.chunkName,
						module,
						/** @type {DependencyLocation} */ (b.loc),
						/** @type {string} */ (b.request)
					);
					maskByChunk.set(c.chunks[0], ZERO_BIGINT);
					c.index = nextChunkGroupIndex++;
					cgi = {
						chunkGroup: c,
						runtime: chunkGroupInfo.runtime,
						minAvailableModules: undefined,
						availableModulesToBeMerged: [],
						skippedItems: undefined,
						resultingAvailableModules: undefined,
						children: undefined,
						availableSources: undefined,
						availableChildren: undefined,
						preOrderIndex: 0,
						postOrderIndex: 0,
						chunkLoading: chunkGroupInfo.chunkLoading,
						asyncChunks: chunkGroupInfo.asyncChunks
					};
					allCreatedChunkGroups.add(c);
					chunkGroupInfoMap.set(c, cgi);
					if (chunkName) {
						namedChunkGroups.set(chunkName, cgi);
					}
				} else {
					c = cgi.chunkGroup;
					if (c.isInitial()) {
						compilation.errors.push(
							new AsyncDependencyToInitialChunkError(
								/** @type {string} */ (chunkName),
								module,
								/** @type {DependencyLocation} */ (b.loc)
							)
						);
						c = chunkGroup;
					} else {
						c.addOptions(b.groupOptions);
					}
					c.addOrigin(
						module,
						/** @type {DependencyLocation} */ (b.loc),
						/** @type {string} */ (b.request)
					);
				}
				blockConnections.set(b, []);
			}
			blockChunkGroups.set(b, /** @type {ChunkGroupInfo} */ (cgi));
			blockByChunkGroups.set(/** @type {ChunkGroupInfo} */ (cgi), b);
		} else if (entryOptions) {
			entrypoint = /** @type {Entrypoint} */ (cgi.chunkGroup);
		} else {
			c = cgi.chunkGroup;
		}

		if (c !== undefined) {
			// 2. We store the connection for the block
			// to connect it later if needed
			/** @type {BlockChunkGroupConnection[]} */
			(blockConnections.get(b)).push({
				originChunkGroupInfo: chunkGroupInfo,
				chunkGroup: c
			});

			// 3. We enqueue the chunk group info creation/updating
			let connectList = queueConnect.get(chunkGroupInfo);
			if (connectList === undefined) {
				connectList = new Set();
				queueConnect.set(chunkGroupInfo, connectList);
			}
			connectList.add(/** @type {ChunkGroupInfo} */ (cgi));

			// TODO check if this really need to be done for each traversal
			// or if it is enough when it's queued when created
			// 4. We enqueue the DependenciesBlock for traversal
			queueDelayed.push({
				action: PROCESS_BLOCK,
				block: b,
				module,
				chunk: c.chunks[0],
				chunkGroup: c,
				chunkGroupInfo: /** @type {ChunkGroupInfo} */ (cgi)
			});
		} else if (entrypoint !== undefined) {
			chunkGroupInfo.chunkGroup.addAsyncEntrypoint(entrypoint);
		}
	};

	/**
	 * @param {DependenciesBlock} block the block
	 * @returns {void}
	 */
	const processBlock = block => {
		statProcessedBlocks++;
		// get prepared block info
		const blockModules = getBlockModules(block, chunkGroupInfo.runtime);

		if (blockModules !== undefined) {
			const minAvailableModules =
				/** @type {bigint} */
				(chunkGroupInfo.minAvailableModules);
			// Buffer items because order need to be reversed to get indices correct
			// Traverse all referenced modules
			for (let i = 0, len = blockModules.length; i < len; i += 3) {
				const refModule = /** @type {Module} */ (blockModules[i]);
				// For single comparisons this might be cheaper
				const isModuleInChunk = chunkGraph.isModuleInChunk(refModule, chunk);

				if (isModuleInChunk) {
					// skip early if already connected
					continue;
				}

				const refOrdinal = /** @type {number} */ getModuleOrdinal(refModule);
				const activeState = /** @type {ConnectionState} */ (
					blockModules[i + 1]
				);
				if (activeState !== true) {
					const connections = /** @type {ModuleGraphConnection[]} */ (
						blockModules[i + 2]
					);
					skipConnectionBuffer.push([refModule, connections]);
					// We skip inactive connections
					if (activeState === false) continue;
				} else if (isOrdinalSetInMask(minAvailableModules, refOrdinal)) {
					// already in parent chunks, skip it for now
					skipBuffer.push(refModule);
					continue;
				}
				// enqueue, then add and enter to be in the correct order
				// this is relevant with circular dependencies
				queueBuffer.push({
					action: activeState === true ? ADD_AND_ENTER_MODULE : PROCESS_BLOCK,
					block: refModule,
					module: refModule,
					chunk,
					chunkGroup,
					chunkGroupInfo
				});
			}
			// Add buffered items in reverse order
			if (skipConnectionBuffer.length > 0) {
				let { skippedModuleConnections } = chunkGroupInfo;
				if (skippedModuleConnections === undefined) {
					chunkGroupInfo.skippedModuleConnections = skippedModuleConnections =
						new Set();
				}
				for (let i = skipConnectionBuffer.length - 1; i >= 0; i--) {
					skippedModuleConnections.add(skipConnectionBuffer[i]);
				}
				skipConnectionBuffer.length = 0;
			}
			if (skipBuffer.length > 0) {
				let { skippedItems } = chunkGroupInfo;
				if (skippedItems === undefined) {
					chunkGroupInfo.skippedItems = skippedItems = new Set();
				}
				for (let i = skipBuffer.length - 1; i >= 0; i--) {
					skippedItems.add(skipBuffer[i]);
				}
				skipBuffer.length = 0;
			}
			if (queueBuffer.length > 0) {
				for (let i = queueBuffer.length - 1; i >= 0; i--) {
					queue.push(queueBuffer[i]);
				}
				queueBuffer.length = 0;
			}
		}

		// Traverse all Blocks
		for (const b of block.blocks) {
			iteratorBlock(b);
		}

		if (block.blocks.length > 0 && module !== block) {
			blocksWithNestedBlocks.add(block);
		}
	};

	/**
	 * @param {DependenciesBlock} block the block
	 * @returns {void}
	 */
	const processEntryBlock = block => {
		statProcessedBlocks++;
		// get prepared block info
		const blockModules = getBlockModules(block, chunkGroupInfo.runtime);

		if (blockModules !== undefined) {
			// Traverse all referenced modules in reverse order
			for (let i = blockModules.length - 3; i >= 0; i -= 3) {
				const refModule = /** @type {Module} */ (blockModules[i]);
				const activeState = /** @type {ConnectionState} */ (
					blockModules[i + 1]
				);
				// enqueue, then add and enter to be in the correct order
				// this is relevant with circular dependencies
				queue.push({
					action:
						activeState === true ? ADD_AND_ENTER_ENTRY_MODULE : PROCESS_BLOCK,
					block: refModule,
					module: refModule,
					chunk,
					chunkGroup,
					chunkGroupInfo
				});
			}
		}

		// Traverse all Blocks
		for (const b of block.blocks) {
			iteratorBlock(b);
		}

		if (block.blocks.length > 0 && module !== block) {
			blocksWithNestedBlocks.add(block);
		}
	};

	const processQueue = () => {
		while (queue.length) {
			statProcessedQueueItems++;
			const queueItem = /** @type {QueueItem} */ (queue.pop());
			module = queueItem.module;
			block = queueItem.block;
			chunk = queueItem.chunk;
			chunkGroup = queueItem.chunkGroup;
			chunkGroupInfo = queueItem.chunkGroupInfo;

			switch (queueItem.action) {
				case ADD_AND_ENTER_ENTRY_MODULE:
					chunkGraph.connectChunkAndEntryModule(
						chunk,
						module,
						/** @type {Entrypoint} */ (chunkGroup)
					);
				// fallthrough
				case ADD_AND_ENTER_MODULE: {
					const isModuleInChunk = chunkGraph.isModuleInChunk(module, chunk);

					if (isModuleInChunk) {
						// already connected, skip it
						break;
					}
					// We connect Module and Chunk
					chunkGraph.connectChunkAndModule(chunk, module);
					const moduleOrdinal = getModuleOrdinal(module);
					let chunkMask = /** @type {bigint} */ (maskByChunk.get(chunk));
					chunkMask |= ONE_BIGINT << BigInt(moduleOrdinal);
					maskByChunk.set(chunk, chunkMask);
				}
				// fallthrough
				case ENTER_MODULE: {
					const index = chunkGroup.getModulePreOrderIndex(module);
					if (index === undefined) {
						chunkGroup.setModulePreOrderIndex(
							module,
							chunkGroupInfo.preOrderIndex++
						);
					}

					if (
						moduleGraph.setPreOrderIndexIfUnset(
							module,
							nextFreeModulePreOrderIndex
						)
					) {
						nextFreeModulePreOrderIndex++;
					}

					// reuse queueItem
					queueItem.action = LEAVE_MODULE;
					queue.push(queueItem);
				}
				// fallthrough
				case PROCESS_BLOCK: {
					processBlock(block);
					break;
				}
				case PROCESS_ENTRY_BLOCK: {
					processEntryBlock(block);
					break;
				}
				case LEAVE_MODULE: {
					const index = chunkGroup.getModulePostOrderIndex(module);
					if (index === undefined) {
						chunkGroup.setModulePostOrderIndex(
							module,
							chunkGroupInfo.postOrderIndex++
						);
					}

					if (
						moduleGraph.setPostOrderIndexIfUnset(
							module,
							nextFreeModulePostOrderIndex
						)
					) {
						nextFreeModulePostOrderIndex++;
					}
					break;
				}
			}
		}
	};

	/**
	 * @param {ChunkGroupInfo} chunkGroupInfo The info object for the chunk group
	 * @returns {bigint} The mask of available modules after the chunk group
	 */
	const calculateResultingAvailableModules = chunkGroupInfo => {
		if (chunkGroupInfo.resultingAvailableModules !== undefined)
			return chunkGroupInfo.resultingAvailableModules;

		let resultingAvailableModules = /** @type {bigint} */ (
			chunkGroupInfo.minAvailableModules
		);

		// add the modules from the chunk group to the set
		for (const chunk of chunkGroupInfo.chunkGroup.chunks) {
			const mask = /** @type {bigint} */ (maskByChunk.get(chunk));
			resultingAvailableModules |= mask;
		}

		return (chunkGroupInfo.resultingAvailableModules =
			resultingAvailableModules);
	};

	const processConnectQueue = () => {
		// Figure out new parents for chunk groups
		// to get new available modules for these children
		for (const [chunkGroupInfo, targets] of queueConnect) {
			// 1. Add new targets to the list of children
			if (chunkGroupInfo.children === undefined) {
				chunkGroupInfo.children = targets;
			} else {
				for (const target of targets) {
					chunkGroupInfo.children.add(target);
				}
			}

			// 2. Calculate resulting available modules
			const resultingAvailableModules =
				calculateResultingAvailableModules(chunkGroupInfo);

			const runtime = chunkGroupInfo.runtime;

			// 3. Update chunk group info
			for (const target of targets) {
				target.availableModulesToBeMerged.push(resultingAvailableModules);
				chunkGroupsForMerging.add(target);
				const oldRuntime = target.runtime;
				const newRuntime = mergeRuntime(oldRuntime, runtime);
				if (oldRuntime !== newRuntime) {
					target.runtime = newRuntime;
					outdatedChunkGroupInfo.add(target);
				}
			}

			statConnectedChunkGroups += targets.size;
		}
		queueConnect.clear();
	};

	const processChunkGroupsForMerging = () => {
		statProcessedChunkGroupsForMerging += chunkGroupsForMerging.size;

		// Execute the merge
		for (const info of chunkGroupsForMerging) {
			const availableModulesToBeMerged = info.availableModulesToBeMerged;
			const cachedMinAvailableModules = info.minAvailableModules;
			let minAvailableModules = cachedMinAvailableModules;

			statMergedAvailableModuleSets += availableModulesToBeMerged.length;

			for (const availableModules of availableModulesToBeMerged) {
				if (minAvailableModules === undefined) {
					minAvailableModules = availableModules;
				} else {
					minAvailableModules &= availableModules;
				}
			}

			const changed = minAvailableModules !== cachedMinAvailableModules;

			availableModulesToBeMerged.length = 0;
			if (changed) {
				info.minAvailableModules = minAvailableModules;
				info.resultingAvailableModules = undefined;
				outdatedChunkGroupInfo.add(info);
			}
		}
		chunkGroupsForMerging.clear();
	};

	const processChunkGroupsForCombining = () => {
		for (const info of chunkGroupsForCombining) {
			for (const source of /** @type {Set<ChunkGroupInfo>} */ (
				info.availableSources
			)) {
				if (source.minAvailableModules === undefined) {
					chunkGroupsForCombining.delete(info);
					break;
				}
			}
		}

		for (const info of chunkGroupsForCombining) {
			let availableModules = ZERO_BIGINT;
			// combine minAvailableModules from all resultingAvailableModules
			for (const source of /** @type {Set<ChunkGroupInfo>} */ (
				info.availableSources
			)) {
				const resultingAvailableModules =
					calculateResultingAvailableModules(source);
				availableModules |= resultingAvailableModules;
			}
			info.minAvailableModules = availableModules;
			info.resultingAvailableModules = undefined;
			outdatedChunkGroupInfo.add(info);
		}
		chunkGroupsForCombining.clear();
	};

	const processOutdatedChunkGroupInfo = () => {
		statChunkGroupInfoUpdated += outdatedChunkGroupInfo.size;
		// Revisit skipped elements
		for (const info of outdatedChunkGroupInfo) {
			// 1. Reconsider skipped items
			if (info.skippedItems !== undefined) {
				const minAvailableModules =
					/** @type {bigint} */
					(info.minAvailableModules);
				for (const module of info.skippedItems) {
					const ordinal = getModuleOrdinal(module);
					if (!isOrdinalSetInMask(minAvailableModules, ordinal)) {
						queue.push({
							action: ADD_AND_ENTER_MODULE,
							block: module,
							module,
							chunk: info.chunkGroup.chunks[0],
							chunkGroup: info.chunkGroup,
							chunkGroupInfo: info
						});
						info.skippedItems.delete(module);
					}
				}
			}

			// 2. Reconsider skipped connections
			if (info.skippedModuleConnections !== undefined) {
				const minAvailableModules =
					/** @type {bigint} */
					(info.minAvailableModules);
				for (const entry of info.skippedModuleConnections) {
					const [module, connections] = entry;
					const activeState = getActiveStateOfConnections(
						connections,
						info.runtime
					);
					if (activeState === false) continue;
					if (activeState === true) {
						const ordinal = getModuleOrdinal(module);
						info.skippedModuleConnections.delete(entry);
						if (isOrdinalSetInMask(minAvailableModules, ordinal)) {
							/** @type {NonNullable<ChunkGroupInfo["skippedItems"]>} */
							(info.skippedItems).add(module);
							continue;
						}
					}
					queue.push({
						action: activeState === true ? ADD_AND_ENTER_MODULE : PROCESS_BLOCK,
						block: module,
						module,
						chunk: info.chunkGroup.chunks[0],
						chunkGroup: info.chunkGroup,
						chunkGroupInfo: info
					});
				}
			}

			// 2. Reconsider children chunk groups
			if (info.children !== undefined) {
				statChildChunkGroupsReconnected += info.children.size;
				for (const cgi of info.children) {
					let connectList = queueConnect.get(info);
					if (connectList === undefined) {
						connectList = new Set();
						queueConnect.set(info, connectList);
					}
					connectList.add(cgi);
				}
			}

			// 3. Reconsider chunk groups for combining
			if (info.availableChildren !== undefined) {
				for (const cgi of info.availableChildren) {
					chunkGroupsForCombining.add(cgi);
				}
			}
			outdatedOrderIndexChunkGroups.add(info);
		}
		outdatedChunkGroupInfo.clear();
	};

	// Iterative traversal of the Module graph
	// Recursive would be simpler to write but could result in Stack Overflows
	while (queue.length || queueConnect.size) {
		logger.time("visitModules: visiting");
		processQueue();
		logger.timeAggregateEnd("visitModules: prepare");
		logger.timeEnd("visitModules: visiting");

		if (chunkGroupsForCombining.size > 0) {
			logger.time("visitModules: combine available modules");
			processChunkGroupsForCombining();
			logger.timeEnd("visitModules: combine available modules");
		}

		if (queueConnect.size > 0) {
			logger.time("visitModules: calculating available modules");
			processConnectQueue();
			logger.timeEnd("visitModules: calculating available modules");

			if (chunkGroupsForMerging.size > 0) {
				logger.time("visitModules: merging available modules");
				processChunkGroupsForMerging();
				logger.timeEnd("visitModules: merging available modules");
			}
		}

		if (outdatedChunkGroupInfo.size > 0) {
			logger.time("visitModules: check modules for revisit");
			processOutdatedChunkGroupInfo();
			logger.timeEnd("visitModules: check modules for revisit");
		}

		// Run queueDelayed when all items of the queue are processed
		// This is important to get the global indexing correct
		// Async blocks should be processed after all sync blocks are processed
		if (queue.length === 0) {
			const tempQueue = queue;
			queue = queueDelayed.reverse();
			queueDelayed = tempQueue;
		}
	}

	for (const info of outdatedOrderIndexChunkGroups) {
		const { chunkGroup, runtime } = info;

		const block = blockByChunkGroups.get(info);

		if (!block) {
			continue;
		}

		let preOrderIndex = 0;
		let postOrderIndex = 0;

		/**
		 * @param {DependenciesBlock} current current
		 * @param {BlocksWithNestedBlocks} visited visited dependencies blocks
		 */
		const process = (current, visited) => {
			const blockModules = getBlockModules(current, runtime);
			if (blockModules === undefined) {
				return;
			}

			for (let i = 0, len = blockModules.length; i < len; i += 3) {
				const activeState = /** @type {ConnectionState} */ (
					blockModules[i + 1]
				);
				if (activeState === false) {
					continue;
				}
				const refModule = /** @type {Module} */ (blockModules[i]);
				if (visited.has(refModule)) {
					continue;
				}

				visited.add(refModule);

				if (refModule) {
					chunkGroup.setModulePreOrderIndex(refModule, preOrderIndex++);
					process(refModule, visited);
					chunkGroup.setModulePostOrderIndex(refModule, postOrderIndex++);
				}
			}
		};

		process(block, new Set());
	}
	outdatedOrderIndexChunkGroups.clear();
	ordinalByModule.clear();

	logger.log(
		`${statProcessedQueueItems} queue items processed (${statProcessedBlocks} blocks)`
	);
	logger.log(`${statConnectedChunkGroups} chunk groups connected`);
	logger.log(
		`${statProcessedChunkGroupsForMerging} chunk groups processed for merging (${statMergedAvailableModuleSets} module sets, ${statForkedAvailableModules} forked, ${statForkedAvailableModulesCount} + ${statForkedAvailableModulesCountPlus} modules forked, ${statForkedMergedModulesCount} + ${statForkedMergedModulesCountPlus} modules merged into fork, ${statForkedResultModulesCount} resulting modules)`
	);
	logger.log(
		`${statChunkGroupInfoUpdated} chunk group info updated (${statChildChunkGroupsReconnected} already connected chunk groups reconnected)`
	);
};

/**
 *
 * @param {Compilation} compilation the compilation
 * @param {BlocksWithNestedBlocks} blocksWithNestedBlocks flag for blocks that have nested blocks
 * @param {BlockConnections} blockConnections connection for blocks
 * @param {MaskByChunk} maskByChunk mapping from chunk to module mask
 */
const connectChunkGroups = (
	compilation,
	blocksWithNestedBlocks,
	blockConnections,
	maskByChunk
) => {
	const { chunkGraph } = compilation;

	/**
	 * Helper function to check if all modules of a chunk are available
	 *
	 * @param {ChunkGroup} chunkGroup the chunkGroup to scan
	 * @param {bigint} availableModules the comparator set
	 * @returns {boolean} return true if all modules of a chunk are available
	 */
	const areModulesAvailable = (chunkGroup, availableModules) => {
		for (const chunk of chunkGroup.chunks) {
			const chunkMask = /** @type {bigint} */ (maskByChunk.get(chunk));
			if ((chunkMask & availableModules) !== chunkMask) return false;
		}
		return true;
	};

	// For each edge in the basic chunk graph
	for (const [block, connections] of blockConnections) {
		// 1. Check if connection is needed
		// When none of the dependencies need to be connected
		// we can skip all of them
		// It's not possible to filter each item so it doesn't create inconsistent
		// connections and modules can only create one version
		// TODO maybe decide this per runtime
		if (
			// TODO is this needed?
			!blocksWithNestedBlocks.has(block) &&
			connections.every(({ chunkGroup, originChunkGroupInfo }) =>
				areModulesAvailable(
					chunkGroup,
					/** @type {bigint} */ (originChunkGroupInfo.resultingAvailableModules)
				)
			)
		) {
			continue;
		}

		// 2. Foreach edge
		for (let i = 0; i < connections.length; i++) {
			const { chunkGroup, originChunkGroupInfo } = connections[i];

			// 3. Connect block with chunk
			chunkGraph.connectBlockAndChunkGroup(block, chunkGroup);

			// 4. Connect chunk with parent
			connectChunkGroupParentAndChild(
				originChunkGroupInfo.chunkGroup,
				chunkGroup
			);
		}
	}
};

/**
 * Remove all unconnected chunk groups
 * @param {Compilation} compilation the compilation
 * @param {Iterable<ChunkGroup>} allCreatedChunkGroups all chunk groups that where created before
 */
const cleanupUnconnectedGroups = (compilation, allCreatedChunkGroups) => {
	const { chunkGraph } = compilation;

	for (const chunkGroup of allCreatedChunkGroups) {
		if (chunkGroup.getNumberOfParents() === 0) {
			for (const chunk of chunkGroup.chunks) {
				compilation.chunks.delete(chunk);
				chunkGraph.disconnectChunk(chunk);
			}
			chunkGraph.disconnectChunkGroup(chunkGroup);
			chunkGroup.remove();
		}
	}
};

/**
 * This method creates the Chunk graph from the Module graph
 * @param {Compilation} compilation the compilation
 * @param {InputEntrypointsAndModules} inputEntrypointsAndModules chunk groups which are processed with the modules
 * @returns {void}
 */
const buildChunkGraph = (compilation, inputEntrypointsAndModules) => {
	const logger = compilation.getLogger("webpack.buildChunkGraph");

	// SHARED STATE

	/** @type {BlockConnections} */
	const blockConnections = new Map();

	/** @type {AllCreatedChunkGroups} */
	const allCreatedChunkGroups = new Set();

	/** @type {ChunkGroupInfoMap} */
	const chunkGroupInfoMap = new Map();

	/** @type {BlocksWithNestedBlocks} */
	const blocksWithNestedBlocks = new Set();

	/** @type {MaskByChunk} */
	const maskByChunk = new Map();

	// PART ONE

	logger.time("visitModules");
	visitModules(
		logger,
		compilation,
		inputEntrypointsAndModules,
		chunkGroupInfoMap,
		blockConnections,
		blocksWithNestedBlocks,
		allCreatedChunkGroups,
		maskByChunk
	);
	logger.timeEnd("visitModules");

	// PART TWO

	logger.time("connectChunkGroups");
	connectChunkGroups(
		compilation,
		blocksWithNestedBlocks,
		blockConnections,
		maskByChunk
	);
	logger.timeEnd("connectChunkGroups");

	for (const [chunkGroup, chunkGroupInfo] of chunkGroupInfoMap) {
		for (const chunk of chunkGroup.chunks)
			chunk.runtime = mergeRuntime(chunk.runtime, chunkGroupInfo.runtime);
	}

	// Cleanup work

	logger.time("cleanup");
	cleanupUnconnectedGroups(compilation, allCreatedChunkGroups);
	logger.timeEnd("cleanup");
};

module.exports = buildChunkGraph;


code:
/*
	MIT License http://www.opensource.org/licenses/mit-license.php
	Author Tobias Koppers @sokra
*/

"use strict";

/** @typedef {import("../Compiler")} Compiler */

class AddBuildDependenciesPlugin {
	/**
	 * @param {Iterable<string>} buildDependencies list of build dependencies
	 */
	constructor(buildDependencies) {
		this.buildDependencies = new Set(buildDependencies);
	}

	/**
	 * Apply the plugin
	 * @param {Compiler} compiler the compiler instance
	 * @returns {void}
	 */
	apply(compiler) {
		compiler.hooks.compilation.tap(
			"AddBuildDependenciesPlugin",
			compilation => {
				compilation.buildDependencies.addAll(this.buildDependencies);
			}
		);
	}
}

module.exports = AddBuildDependenciesPlugin;

license: mit


code:
/*
	MIT License http://www.opensource.org/licenses/mit-license.php
	Author Tobias Koppers @sokra
*/

"use strict";

/** @typedef {import("../Compiler")} Compiler */

class AddManagedPathsPlugin {
	/**
	 * @param {Iterable<string | RegExp>} managedPaths list of managed paths
	 * @param {Iterable<string | RegExp>} immutablePaths list of immutable paths
	 * @param {Iterable<string | RegExp>} unmanagedPaths list of unmanaged paths
	 */
	constructor(managedPaths, immutablePaths, unmanagedPaths) {
		this.managedPaths = new Set(managedPaths);
		this.immutablePaths = new Set(immutablePaths);
		this.unmanagedPaths = new Set(unmanagedPaths);
	}

	/**
	 * Apply the plugin
	 * @param {Compiler} compiler the compiler instance
	 * @returns {void}
	 */
	apply(compiler) {
		for (const managedPath of this.managedPaths) {
			compiler.managedPaths.add(managedPath);
		}
		for (const immutablePath of this.immutablePaths) {
			compiler.immutablePaths.add(immutablePath);
		}
		for (const unmanagedPath of this.unmanagedPaths) {
			compiler.unmanagedPaths.add(unmanagedPath);
		}
	}
}

module.exports = AddManagedPathsPlugin;


code:
/*
	MIT License http://www.opensource.org/licenses/mit-license.php
	Author Tobias Koppers @sokra
*/

"use strict";

const Cache = require("../Cache");
const ProgressPlugin = require("../ProgressPlugin");

/** @typedef {import("../Compiler")} Compiler */
/** @typedef {import("./PackFileCacheStrategy")} PackFileCacheStrategy */

const BUILD_DEPENDENCIES_KEY = Symbol();

class IdleFileCachePlugin {
	/**
	 * @param {PackFileCacheStrategy} strategy cache strategy
	 * @param {number} idleTimeout timeout
	 * @param {number} idleTimeoutForInitialStore initial timeout
	 * @param {number} idleTimeoutAfterLargeChanges timeout after changes
	 */
	constructor(
		strategy,
		idleTimeout,
		idleTimeoutForInitialStore,
		idleTimeoutAfterLargeChanges
	) {
		this.strategy = strategy;
		this.idleTimeout = idleTimeout;
		this.idleTimeoutForInitialStore = idleTimeoutForInitialStore;
		this.idleTimeoutAfterLargeChanges = idleTimeoutAfterLargeChanges;
	}

	/**
	 * Apply the plugin
	 * @param {Compiler} compiler the compiler instance
	 * @returns {void}
	 */
	apply(compiler) {
		let strategy = this.strategy;
		const idleTimeout = this.idleTimeout;
		const idleTimeoutForInitialStore = Math.min(
			idleTimeout,
			this.idleTimeoutForInitialStore
		);
		const idleTimeoutAfterLargeChanges = this.idleTimeoutAfterLargeChanges;
		const resolvedPromise = Promise.resolve();

		let timeSpendInBuild = 0;
		let timeSpendInStore = 0;
		let avgTimeSpendInStore = 0;

		/** @type {Map<string | typeof BUILD_DEPENDENCIES_KEY, () => Promise<void>>} */
		const pendingIdleTasks = new Map();

		compiler.cache.hooks.store.tap(
			{ name: "IdleFileCachePlugin", stage: Cache.STAGE_DISK },
			(identifier, etag, data) => {
				pendingIdleTasks.set(identifier, () =>
					strategy.store(identifier, etag, data)
				);
			}
		);

		compiler.cache.hooks.get.tapPromise(
			{ name: "IdleFileCachePlugin", stage: Cache.STAGE_DISK },
			(identifier, etag, gotHandlers) => {
				const restore = () =>
					strategy.restore(identifier, etag).then(cacheEntry => {
						if (cacheEntry === undefined) {
							gotHandlers.push((result, callback) => {
								if (result !== undefined) {
									pendingIdleTasks.set(identifier, () =>
										strategy.store(identifier, etag, result)
									);
								}
								callback();
							});
						} else {
							return cacheEntry;
						}
					});
				const pendingTask = pendingIdleTasks.get(identifier);
				if (pendingTask !== undefined) {
					pendingIdleTasks.delete(identifier);
					return pendingTask().then(restore);
				}
				return restore();
			}
		);

		compiler.cache.hooks.storeBuildDependencies.tap(
			{ name: "IdleFileCachePlugin", stage: Cache.STAGE_DISK },
			dependencies => {
				pendingIdleTasks.set(BUILD_DEPENDENCIES_KEY, () =>
					Promise.resolve().then(() =>
						strategy.storeBuildDependencies(dependencies)
					)
				);
			}
		);

		compiler.cache.hooks.shutdown.tapPromise(
			{ name: "IdleFileCachePlugin", stage: Cache.STAGE_DISK },
			() => {
				if (idleTimer) {
					clearTimeout(idleTimer);
					idleTimer = undefined;
				}
				isIdle = false;
				const reportProgress = ProgressPlugin.getReporter(compiler);
				const jobs = Array.from(pendingIdleTasks.values());
				if (reportProgress) reportProgress(0, "process pending cache items");
				const promises = jobs.map(fn => fn());
				pendingIdleTasks.clear();
				promises.push(currentIdlePromise);
				const promise = Promise.all(promises);
				currentIdlePromise = promise.then(() => strategy.afterAllStored());
				if (reportProgress) {
					currentIdlePromise = currentIdlePromise.then(() => {
						reportProgress(1, `stored`);
					});
				}
				return currentIdlePromise.then(() => {
					// Reset strategy
					if (strategy.clear) strategy.clear();
				});
			}
		);

		/** @type {Promise<any>} */
		let currentIdlePromise = resolvedPromise;
		let isIdle = false;
		let isInitialStore = true;
		const processIdleTasks = () => {
			if (isIdle) {
				const startTime = Date.now();
				if (pendingIdleTasks.size > 0) {
					const promises = [currentIdlePromise];
					const maxTime = startTime + 100;
					let maxCount = 100;
					for (const [filename, factory] of pendingIdleTasks) {
						pendingIdleTasks.delete(filename);
						promises.push(factory());
						if (maxCount-- <= 0 || Date.now() > maxTime) break;
					}
					currentIdlePromise = Promise.all(promises);
					currentIdlePromise.then(() => {
						timeSpendInStore += Date.now() - startTime;
						// Allow to exit the process between
						idleTimer = setTimeout(processIdleTasks, 0);
						idleTimer.unref();
					});
					return;
				}
				currentIdlePromise = currentIdlePromise
					.then(async () => {
						await strategy.afterAllStored();
						timeSpendInStore += Date.now() - startTime;
						avgTimeSpendInStore =
							Math.max(avgTimeSpendInStore, timeSpendInStore) * 0.9 +
							timeSpendInStore * 0.1;
						timeSpendInStore = 0;
						timeSpendInBuild = 0;
					})
					.catch(err => {
						const logger = compiler.getInfrastructureLogger(
							"IdleFileCachePlugin"
						);
						logger.warn(`Background tasks during idle failed: ${err.message}`);
						logger.debug(err.stack);
					});
				isInitialStore = false;
			}
		};
		/** @type {ReturnType<typeof setTimeout> | undefined} */
		let idleTimer = undefined;
		compiler.cache.hooks.beginIdle.tap(
			{ name: "IdleFileCachePlugin", stage: Cache.STAGE_DISK },
			() => {
				const isLargeChange = timeSpendInBuild > avgTimeSpendInStore * 2;
				if (isInitialStore && idleTimeoutForInitialStore < idleTimeout) {
					compiler
						.getInfrastructureLogger("IdleFileCachePlugin")
						.log(
							`Initial cache was generated and cache will be persisted in ${
								idleTimeoutForInitialStore / 1000
							}s.`
						);
				} else if (
					isLargeChange &&
					idleTimeoutAfterLargeChanges < idleTimeout
				) {
					compiler
						.getInfrastructureLogger("IdleFileCachePlugin")
						.log(
							`Spend ${Math.round(timeSpendInBuild) / 1000}s in build and ${
								Math.round(avgTimeSpendInStore) / 1000
							}s in average in cache store. This is considered as large change and cache will be persisted in ${
								idleTimeoutAfterLargeChanges / 1000
							}s.`
						);
				}
				idleTimer = setTimeout(
					() => {
						idleTimer = undefined;
						isIdle = true;
						resolvedPromise.then(processIdleTasks);
					},
					Math.min(
						isInitialStore ? idleTimeoutForInitialStore : Infinity,
						isLargeChange ? idleTimeoutAfterLargeChanges : Infinity,
						idleTimeout
					)
				);
				idleTimer.unref();
			}
		);
		compiler.cache.hooks.endIdle.tap(
			{ name: "IdleFileCachePlugin", stage: Cache.STAGE_DISK },
			() => {
				if (idleTimer) {
					clearTimeout(idleTimer);
					idleTimer = undefined;
				}
				isIdle = false;
			}
		);
		compiler.hooks.done.tap("IdleFileCachePlugin", stats => {
			// 10% build overhead is ignored, as it's not cacheable
			timeSpendInBuild *= 0.9;
			timeSpendInBuild +=
				/** @type {number} */ (stats.endTime) -
				/** @type {number} */ (stats.startTime);
		});
	}
}

module.exports = IdleFileCachePlugin;


code:
/*
	MIT License http://www.opensource.org/licenses/mit-license.php
	Author Tobias Koppers @sokra
*/

"use strict";

const Cache = require("../Cache");

/** @typedef {import("webpack-sources").Source} Source */
/** @typedef {import("../Cache").Etag} Etag */
/** @typedef {import("../Compiler")} Compiler */
/** @typedef {import("../Module")} Module */

class MemoryCachePlugin {
	/**
	 * Apply the plugin
	 * @param {Compiler} compiler the compiler instance
	 * @returns {void}
	 */
	apply(compiler) {
		/** @type {Map<string, { etag: Etag | null, data: any } | null>} */
		const cache = new Map();
		compiler.cache.hooks.store.tap(
			{ name: "MemoryCachePlugin", stage: Cache.STAGE_MEMORY },
			(identifier, etag, data) => {
				cache.set(identifier, { etag, data });
			}
		);
		compiler.cache.hooks.get.tap(
			{ name: "MemoryCachePlugin", stage: Cache.STAGE_MEMORY },
			(identifier, etag, gotHandlers) => {
				const cacheEntry = cache.get(identifier);
				if (cacheEntry === null) {
					return null;
				} else if (cacheEntry !== undefined) {
					return cacheEntry.etag === etag ? cacheEntry.data : null;
				}
				gotHandlers.push((result, callback) => {
					if (result === undefined) {
						cache.set(identifier, null);
					} else {
						cache.set(identifier, { etag, data: result });
					}
					return callback();
				});
			}
		);
		compiler.cache.hooks.shutdown.tap(
			{ name: "MemoryCachePlugin", stage: Cache.STAGE_MEMORY },
			() => {
				cache.clear();
			}
		);
	}
}
module.exports = MemoryCachePlugin;


code:
/*
	MIT License http://www.opensource.org/licenses/mit-license.php
	Author Tobias Koppers @sokra
*/

"use strict";

const Cache = require("../Cache");

/** @typedef {import("webpack-sources").Source} Source */
/** @typedef {import("../Cache").Etag} Etag */
/** @typedef {import("../Compiler")} Compiler */
/** @typedef {import("../Module")} Module */

class MemoryWithGcCachePlugin {
	/**
	 * @param {object} options Options
	 * @param {number} options.maxGenerations max generations
	 */
	constructor({ maxGenerations }) {
		this._maxGenerations = maxGenerations;
	}
	/**
	 * Apply the plugin
	 * @param {Compiler} compiler the compiler instance
	 * @returns {void}
	 */
	apply(compiler) {
		const maxGenerations = this._maxGenerations;
		/** @type {Map<string, { etag: Etag | null, data: any } | undefined | null>} */
		const cache = new Map();
		/** @type {Map<string, { entry: { etag: Etag | null, data: any } | null, until: number }>} */
		const oldCache = new Map();
		let generation = 0;
		let cachePosition = 0;
		const logger = compiler.getInfrastructureLogger("MemoryWithGcCachePlugin");
		compiler.hooks.afterDone.tap("MemoryWithGcCachePlugin", () => {
			generation++;
			let clearedEntries = 0;
			let lastClearedIdentifier;
			// Avoid coverage problems due indirect changes
			/* istanbul ignore next */
			for (const [identifier, entry] of oldCache) {
				if (entry.until > generation) break;

				oldCache.delete(identifier);
				if (cache.get(identifier) === undefined) {
					cache.delete(identifier);
					clearedEntries++;
					lastClearedIdentifier = identifier;
				}
			}
			if (clearedEntries > 0 || oldCache.size > 0) {
				logger.log(
					`${cache.size - oldCache.size} active entries, ${
						oldCache.size
					} recently unused cached entries${
						clearedEntries > 0
							? `, ${clearedEntries} old unused cache entries removed e. g. ${lastClearedIdentifier}`
							: ""
					}`
				);
			}
			let i = (cache.size / maxGenerations) | 0;
			let j = cachePosition >= cache.size ? 0 : cachePosition;
			cachePosition = j + i;
			for (const [identifier, entry] of cache) {
				if (j !== 0) {
					j--;
					continue;
				}
				if (entry !== undefined) {
					// We don't delete the cache entry, but set it to undefined instead
					// This reserves the location in the data table and avoids rehashing
					// when constantly adding and removing entries.
					// It will be deleted when removed from oldCache.
					cache.set(identifier, undefined);
					oldCache.delete(identifier);
					oldCache.set(identifier, {
						entry,
						until: generation + maxGenerations
					});
					if (i-- === 0) break;
				}
			}
		});
		compiler.cache.hooks.store.tap(
			{ name: "MemoryWithGcCachePlugin", stage: Cache.STAGE_MEMORY },
			(identifier, etag, data) => {
				cache.set(identifier, { etag, data });
			}
		);
		compiler.cache.hooks.get.tap(
			{ name: "MemoryWithGcCachePlugin", stage: Cache.STAGE_MEMORY },
			(identifier, etag, gotHandlers) => {
				const cacheEntry = cache.get(identifier);
				if (cacheEntry === null) {
					return null;
				} else if (cacheEntry !== undefined) {
					return cacheEntry.etag === etag ? cacheEntry.data : null;
				}
				const oldCacheEntry = oldCache.get(identifier);
				if (oldCacheEntry !== undefined) {
					const cacheEntry = oldCacheEntry.entry;
					if (cacheEntry === null) {
						oldCache.delete(identifier);
						cache.set(identifier, cacheEntry);
						return null;
					} else {
						if (cacheEntry.etag !== etag) return null;
						oldCache.delete(identifier);
						cache.set(identifier, cacheEntry);
						return cacheEntry.data;
					}
				}
				gotHandlers.push((result, callback) => {
					if (result === undefined) {
						cache.set(identifier, null);
					} else {
						cache.set(identifier, { etag, data: result });
					}
					return callback();
				});
			}
		);
		compiler.cache.hooks.shutdown.tap(
			{ name: "MemoryWithGcCachePlugin", stage: Cache.STAGE_MEMORY },
			() => {
				cache.clear();
				oldCache.clear();
			}
		);
	}
}
module.exports = MemoryWithGcCachePlugin;


code:
/*
	MIT License http://www.opensource.org/licenses/mit-license.php
	Author Tobias Koppers @sokra
*/

"use strict";

const FileSystemInfo = require("../FileSystemInfo");
const ProgressPlugin = require("../ProgressPlugin");
const { formatSize } = require("../SizeFormatHelpers");
const SerializerMiddleware = require("../serialization/SerializerMiddleware");
const LazySet = require("../util/LazySet");
const makeSerializable = require("../util/makeSerializable");
const memoize = require("../util/memoize");
const {
	createFileSerializer,
	NOT_SERIALIZABLE
} = require("../util/serialization");

/** @typedef {import("../../declarations/WebpackOptions").SnapshotOptions} SnapshotOptions */
/** @typedef {import("../Cache").Etag} Etag */
/** @typedef {import("../Compiler")} Compiler */
/** @typedef {import("../FileSystemInfo").ResolveBuildDependenciesResult} ResolveBuildDependenciesResult */
/** @typedef {import("../FileSystemInfo").Snapshot} Snapshot */
/** @typedef {import("../logging/Logger").Logger} Logger */
/** @typedef {import("../serialization/ObjectMiddleware").ObjectDeserializerContext} ObjectDeserializerContext */
/** @typedef {import("../serialization/ObjectMiddleware").ObjectSerializerContext} ObjectSerializerContext */
/** @typedef {import("../util/fs").IntermediateFileSystem} IntermediateFileSystem */

/** @typedef {Map<string, string | false>} ResolveResults */
/** @typedef {Set<string>} Items */
/** @typedef {Set<string>} BuildDependencies */
/** @typedef {Map<string, PackItemInfo>} ItemInfo */

class PackContainer {
	/**
	 * @param {object} data stored data
	 * @param {string} version version identifier
	 * @param {Snapshot} buildSnapshot snapshot of all build dependencies
	 * @param {BuildDependencies} buildDependencies list of all unresolved build dependencies captured
	 * @param {ResolveResults} resolveResults result of the resolved build dependencies
	 * @param {Snapshot} resolveBuildDependenciesSnapshot snapshot of the dependencies of the build dependencies resolving
	 */
	constructor(
		data,
		version,
		buildSnapshot,
		buildDependencies,
		resolveResults,
		resolveBuildDependenciesSnapshot
	) {
		this.data = data;
		this.version = version;
		this.buildSnapshot = buildSnapshot;
		this.buildDependencies = buildDependencies;
		this.resolveResults = resolveResults;
		this.resolveBuildDependenciesSnapshot = resolveBuildDependenciesSnapshot;
	}

	/**
	 * @param {ObjectSerializerContext} context context
	 */
	serialize({ write, writeLazy }) {
		write(this.version);
		write(this.buildSnapshot);
		write(this.buildDependencies);
		write(this.resolveResults);
		write(this.resolveBuildDependenciesSnapshot);
		/** @type {NonNullable<ObjectSerializerContext["writeLazy"]>} */
		(writeLazy)(this.data);
	}

	/**
	 * @param {ObjectDeserializerContext} context context
	 */
	deserialize({ read }) {
		this.version = read();
		this.buildSnapshot = read();
		this.buildDependencies = read();
		this.resolveResults = read();
		this.resolveBuildDependenciesSnapshot = read();
		this.data = read();
	}
}

makeSerializable(
	PackContainer,
	"webpack/lib/cache/PackFileCacheStrategy",
	"PackContainer"
);

const MIN_CONTENT_SIZE = 1024 * 1024; // 1 MB
const CONTENT_COUNT_TO_MERGE = 10;
const MIN_ITEMS_IN_FRESH_PACK = 100;
const MAX_ITEMS_IN_FRESH_PACK = 50000;
const MAX_TIME_IN_FRESH_PACK = 1 * 60 * 1000; // 1 min

class PackItemInfo {
	/**
	 * @param {string} identifier identifier of item
	 * @param {string | null} etag etag of item
	 * @param {any} value fresh value of item
	 */
	constructor(identifier, etag, value) {
		this.identifier = identifier;
		this.etag = etag;
		this.location = -1;
		this.lastAccess = Date.now();
		this.freshValue = value;
	}
}

class Pack {
	/**
	 * @param {Logger} logger a logger
	 * @param {number} maxAge max age of cache items
	 */
	constructor(logger, maxAge) {
		/** @type {ItemInfo} */
		this.itemInfo = new Map();
		/** @type {(string | undefined)[]} */
		this.requests = [];
		this.requestsTimeout = undefined;
		/** @type {ItemInfo} */
		this.freshContent = new Map();
		/** @type {(undefined | PackContent)[]} */
		this.content = [];
		this.invalid = false;
		this.logger = logger;
		this.maxAge = maxAge;
	}

	/**
	 * @param {string} identifier identifier
	 */
	_addRequest(identifier) {
		this.requests.push(identifier);
		if (this.requestsTimeout === undefined) {
			this.requestsTimeout = setTimeout(() => {
				this.requests.push(undefined);
				this.requestsTimeout = undefined;
			}, MAX_TIME_IN_FRESH_PACK);
			if (this.requestsTimeout.unref) this.requestsTimeout.unref();
		}
	}

	stopCapturingRequests() {
		if (this.requestsTimeout !== undefined) {
			clearTimeout(this.requestsTimeout);
			this.requestsTimeout = undefined;
		}
	}

	/**
	 * @param {string} identifier unique name for the resource
	 * @param {string | null} etag etag of the resource
	 * @returns {any} cached content
	 */
	get(identifier, etag) {
		const info = this.itemInfo.get(identifier);
		this._addRequest(identifier);
		if (info === undefined) {
			return undefined;
		}
		if (info.etag !== etag) return null;
		info.lastAccess = Date.now();
		const loc = info.location;
		if (loc === -1) {
			return info.freshValue;
		} else {
			if (!this.content[loc]) {
				return undefined;
			}
			return /** @type {PackContent} */ (this.content[loc]).get(identifier);
		}
	}

	/**
	 * @param {string} identifier unique name for the resource
	 * @param {string | null} etag etag of the resource
	 * @param {any} data cached content
	 * @returns {void}
	 */
	set(identifier, etag, data) {
		if (!this.invalid) {
			this.invalid = true;
			this.logger.log(`Pack got invalid because of write to: ${identifier}`);
		}
		const info = this.itemInfo.get(identifier);
		if (info === undefined) {
			const newInfo = new PackItemInfo(identifier, etag, data);
			this.itemInfo.set(identifier, newInfo);
			this._addRequest(identifier);
			this.freshContent.set(identifier, newInfo);
		} else {
			const loc = info.location;
			if (loc >= 0) {
				this._addRequest(identifier);
				this.freshContent.set(identifier, info);
				const content = /** @type {PackContent} */ (this.content[loc]);
				content.delete(identifier);
				if (content.items.size === 0) {
					this.content[loc] = undefined;
					this.logger.debug("Pack %d got empty and is removed", loc);
				}
			}
			info.freshValue = data;
			info.lastAccess = Date.now();
			info.etag = etag;
			info.location = -1;
		}
	}

	getContentStats() {
		let count = 0;
		let size = 0;
		for (const content of this.content) {
			if (content !== undefined) {
				count++;
				const s = content.getSize();
				if (s > 0) {
					size += s;
				}
			}
		}
		return { count, size };
	}

	/**
	 * @returns {number} new location of data entries
	 */
	_findLocation() {
		let i;
		for (i = 0; i < this.content.length && this.content[i] !== undefined; i++);
		return i;
	}

	/**
	 * @private
	 * @param {Items} items items
	 * @param {Items} usedItems used items
	 * @param {number} newLoc new location
	 */
	_gcAndUpdateLocation(items, usedItems, newLoc) {
		let count = 0;
		let lastGC;
		const now = Date.now();
		for (const identifier of items) {
			const info = /** @type {PackItemInfo} */ (this.itemInfo.get(identifier));
			if (now - info.lastAccess > this.maxAge) {
				this.itemInfo.delete(identifier);
				items.delete(identifier);
				usedItems.delete(identifier);
				count++;
				lastGC = identifier;
			} else {
				info.location = newLoc;
			}
		}
		if (count > 0) {
			this.logger.log(
				"Garbage Collected %d old items at pack %d (%d items remaining) e. g. %s",
				count,
				newLoc,
				items.size,
				lastGC
			);
		}
	}

	_persistFreshContent() {
		const itemsCount = this.freshContent.size;
		if (itemsCount > 0) {
			const packCount = Math.ceil(itemsCount / MAX_ITEMS_IN_FRESH_PACK);
			const itemsPerPack = Math.ceil(itemsCount / packCount);
			const packs = [];
			let i = 0;
			let ignoreNextTimeTick = false;
			const createNextPack = () => {
				const loc = this._findLocation();
				this.content[loc] = null; // reserve
				const pack = {
					/** @type {Items} */
					items: new Set(),
					/** @type {Map<string, any>} */
					map: new Map(),
					loc
				};
				packs.push(pack);
				return pack;
			};
			let pack = createNextPack();
			if (this.requestsTimeout !== undefined)
				clearTimeout(this.requestsTimeout);
			for (const identifier of this.requests) {
				if (identifier === undefined) {
					if (ignoreNextTimeTick) {
						ignoreNextTimeTick = false;
					} else if (pack.items.size >= MIN_ITEMS_IN_FRESH_PACK) {
						i = 0;
						pack = createNextPack();
					}
					continue;
				}
				const info = this.freshContent.get(identifier);
				if (info === undefined) continue;
				pack.items.add(identifier);
				pack.map.set(identifier, info.freshValue);
				info.location = pack.loc;
				info.freshValue = undefined;
				this.freshContent.delete(identifier);
				if (++i > itemsPerPack) {
					i = 0;
					pack = createNextPack();
					ignoreNextTimeTick = true;
				}
			}
			this.requests.length = 0;
			for (const pack of packs) {
				this.content[pack.loc] = new PackContent(
					pack.items,
					new Set(pack.items),
					new PackContentItems(pack.map)
				);
			}
			this.logger.log(
				`${itemsCount} fresh items in cache put into pack ${
					packs.length > 1
						? packs
								.map(pack => `${pack.loc} (${pack.items.size} items)`)
								.join(", ")
						: packs[0].loc
				}`
			);
		}
	}

	/**
	 * Merges small content files to a single content file
	 */
	_optimizeSmallContent() {
		// 1. Find all small content files
		// Treat unused content files separately to avoid
		// a merge-split cycle
		/** @type {number[]} */
		const smallUsedContents = [];
		/** @type {number} */
		let smallUsedContentSize = 0;
		/** @type {number[]} */
		const smallUnusedContents = [];
		/** @type {number} */
		let smallUnusedContentSize = 0;
		for (let i = 0; i < this.content.length; i++) {
			const content = this.content[i];
			if (content === undefined) continue;
			if (content.outdated) continue;
			const size = content.getSize();
			if (size < 0 || size > MIN_CONTENT_SIZE) continue;
			if (content.used.size > 0) {
				smallUsedContents.push(i);
				smallUsedContentSize += size;
			} else {
				smallUnusedContents.push(i);
				smallUnusedContentSize += size;
			}
		}

		// 2. Check if minimum number is reached
		let mergedIndices;
		if (
			smallUsedContents.length >= CONTENT_COUNT_TO_MERGE ||
			smallUsedContentSize > MIN_CONTENT_SIZE
		) {
			mergedIndices = smallUsedContents;
		} else if (
			smallUnusedContents.length >= CONTENT_COUNT_TO_MERGE ||
			smallUnusedContentSize > MIN_CONTENT_SIZE
		) {
			mergedIndices = smallUnusedContents;
		} else return;

		/** @type {PackContent[] } */
		const mergedContent = [];

		// 3. Remove old content entries
		for (const i of mergedIndices) {
			mergedContent.push(/** @type {PackContent} */ (this.content[i]));
			this.content[i] = undefined;
		}

		// 4. Determine merged items
		/** @type {Items} */
		const mergedItems = new Set();
		/** @type {Items} */
		const mergedUsedItems = new Set();
		/** @type {(function(Map<string, any>): Promise<void>)[]} */
		const addToMergedMap = [];
		for (const content of mergedContent) {
			for (const identifier of content.items) {
				mergedItems.add(identifier);
			}
			for (const identifier of content.used) {
				mergedUsedItems.add(identifier);
			}
			addToMergedMap.push(async map => {
				// unpack existing content
				// after that values are accessible in .content
				await content.unpack(
					"it should be merged with other small pack contents"
				);
				for (const [identifier, value] of content.content) {
					map.set(identifier, value);
				}
			});
		}

		// 5. GC and update location of merged items
		const newLoc = this._findLocation();
		this._gcAndUpdateLocation(mergedItems, mergedUsedItems, newLoc);

		// 6. If not empty, store content somewhere
		if (mergedItems.size > 0) {
			this.content[newLoc] = new PackContent(
				mergedItems,
				mergedUsedItems,
				memoize(async () => {
					/** @type {Map<string, any>} */
					const map = new Map();
					await Promise.all(addToMergedMap.map(fn => fn(map)));
					return new PackContentItems(map);
				})
			);
			this.logger.log(
				"Merged %d small files with %d cache items into pack %d",
				mergedContent.length,
				mergedItems.size,
				newLoc
			);
		}
	}

	/**
	 * Split large content files with used and unused items
	 * into two parts to separate used from unused items
	 */
	_optimizeUnusedContent() {
		// 1. Find a large content file with used and unused items
		for (let i = 0; i < this.content.length; i++) {
			const content = this.content[i];
			if (content === undefined) continue;
			const size = content.getSize();
			if (size < MIN_CONTENT_SIZE) continue;
			const used = content.used.size;
			const total = content.items.size;
			if (used > 0 && used < total) {
				// 2. Remove this content
				this.content[i] = undefined;

				// 3. Determine items for the used content file
				const usedItems = new Set(content.used);
				const newLoc = this._findLocation();
				this._gcAndUpdateLocation(usedItems, usedItems, newLoc);

				// 4. Create content file for used items
				if (usedItems.size > 0) {
					this.content[newLoc] = new PackContent(
						usedItems,
						new Set(usedItems),
						async () => {
							await content.unpack(
								"it should be splitted into used and unused items"
							);
							const map = new Map();
							for (const identifier of usedItems) {
								map.set(identifier, content.content.get(identifier));
							}
							return new PackContentItems(map);
						}
					);
				}

				// 5. Determine items for the unused content file
				const unusedItems = new Set(content.items);
				const usedOfUnusedItems = new Set();
				for (const identifier of usedItems) {
					unusedItems.delete(identifier);
				}
				const newUnusedLoc = this._findLocation();
				this._gcAndUpdateLocation(unusedItems, usedOfUnusedItems, newUnusedLoc);

				// 6. Create content file for unused items
				if (unusedItems.size > 0) {
					this.content[newUnusedLoc] = new PackContent(
						unusedItems,
						usedOfUnusedItems,
						async () => {
							await content.unpack(
								"it should be splitted into used and unused items"
							);
							const map = new Map();
							for (const identifier of unusedItems) {
								map.set(identifier, content.content.get(identifier));
							}
							return new PackContentItems(map);
						}
					);
				}

				this.logger.log(
					"Split pack %d into pack %d with %d used items and pack %d with %d unused items",
					i,
					newLoc,
					usedItems.size,
					newUnusedLoc,
					unusedItems.size
				);

				// optimizing only one of them is good enough and
				// reduces the amount of serialization needed
				return;
			}
		}
	}

	/**
	 * Find the content with the oldest item and run GC on that.
	 * Only runs for one content to avoid large invalidation.
	 */
	_gcOldestContent() {
		/** @type {PackItemInfo | undefined} */
		let oldest = undefined;
		for (const info of this.itemInfo.values()) {
			if (oldest === undefined || info.lastAccess < oldest.lastAccess) {
				oldest = info;
			}
		}
		if (
			Date.now() - /** @type {PackItemInfo} */ (oldest).lastAccess >
			this.maxAge
		) {
			const loc = /** @type {PackItemInfo} */ (oldest).location;
			if (loc < 0) return;
			const content = /** @type {PackContent} */ (this.content[loc]);
			const items = new Set(content.items);
			const usedItems = new Set(content.used);
			this._gcAndUpdateLocation(items, usedItems, loc);

			this.content[loc] =
				items.size > 0
					? new PackContent(items, usedItems, async () => {
							await content.unpack(
								"it contains old items that should be garbage collected"
							);
							const map = new Map();
							for (const identifier of items) {
								map.set(identifier, content.content.get(identifier));
							}
							return new PackContentItems(map);
						})
					: undefined;
		}
	}

	/**
	 * @param {ObjectSerializerContext} context context
	 */
	serialize({ write, writeSeparate }) {
		this._persistFreshContent();
		this._optimizeSmallContent();
		this._optimizeUnusedContent();
		this._gcOldestContent();
		for (const identifier of this.itemInfo.keys()) {
			write(identifier);
		}
		write(null); // null as marker of the end of keys
		for (const info of this.itemInfo.values()) {
			write(info.etag);
		}
		for (const info of this.itemInfo.values()) {
			write(info.lastAccess);
		}
		for (let i = 0; i < this.content.length; i++) {
			const content = this.content[i];
			if (content !== undefined) {
				write(content.items);
				content.writeLazy(lazy => writeSeparate(lazy, { name: `${i}` }));
			} else {
				write(undefined); // undefined marks an empty content slot
			}
		}
		write(null); // null as marker of the end of items
	}

	/**
	 * @param {ObjectDeserializerContext & { logger: Logger }} context context
	 */
	deserialize({ read, logger }) {
		this.logger = logger;
		{
			const items = [];
			let item = read();
			while (item !== null) {
				items.push(item);
				item = read();
			}
			this.itemInfo.clear();
			const infoItems = items.map(identifier => {
				const info = new PackItemInfo(identifier, undefined, undefined);
				this.itemInfo.set(identifier, info);
				return info;
			});
			for (const info of infoItems) {
				info.etag = read();
			}
			for (const info of infoItems) {
				info.lastAccess = read();
			}
		}
		this.content.length = 0;
		let items = read();
		while (items !== null) {
			if (items === undefined) {
				this.content.push(items);
			} else {
				const idx = this.content.length;
				const lazy = read();
				this.content.push(
					new PackContent(
						items,
						new Set(),
						lazy,
						logger,
						`${this.content.length}`
					)
				);
				for (const identifier of items) {
					this.itemInfo.get(identifier).location = idx;
				}
			}
			items = read();
		}
	}
}

makeSerializable(Pack, "webpack/lib/cache/PackFileCacheStrategy", "Pack");

class PackContentItems {
	/**
	 * @param {Map<string, any>} map items
	 */
	constructor(map) {
		this.map = map;
	}

	/**
	 * @param {ObjectSerializerContext & { snapshot: TODO, rollback: TODO, logger: Logger, profile: boolean | undefined  }} context context
	 */
	serialize({ write, snapshot, rollback, logger, profile }) {
		if (profile) {
			write(false);
			for (const [key, value] of this.map) {
				const s = snapshot();
				try {
					write(key);
					const start = process.hrtime();
					write(value);
					const durationHr = process.hrtime(start);
					const duration = durationHr[0] * 1000 + durationHr[1] / 1e6;
					if (duration > 1) {
						if (duration > 500)
							logger.error(`Serialization of '${key}': ${duration} ms`);
						else if (duration > 50)
							logger.warn(`Serialization of '${key}': ${duration} ms`);
						else if (duration > 10)
							logger.info(`Serialization of '${key}': ${duration} ms`);
						else if (duration > 5)
							logger.log(`Serialization of '${key}': ${duration} ms`);
						else logger.debug(`Serialization of '${key}': ${duration} ms`);
					}
				} catch (e) {
					rollback(s);
					if (e === NOT_SERIALIZABLE) continue;
					const msg = "Skipped not serializable cache item";
					if (e.message.includes("ModuleBuildError")) {
						logger.log(`${msg} (in build error): ${e.message}`);
						logger.debug(`${msg} '${key}' (in build error): ${e.stack}`);
					} else {
						logger.warn(`${msg}: ${e.message}`);
						logger.debug(`${msg} '${key}': ${e.stack}`);
					}
				}
			}
			write(null);
			return;
		}
		// Try to serialize all at once
		const s = snapshot();
		try {
			write(true);
			write(this.map);
		} catch (e) {
			rollback(s);

			// Try to serialize each item on it's own
			write(false);
			for (const [key, value] of this.map) {
				const s = snapshot();
				try {
					write(key);
					write(value);
				} catch (e) {
					rollback(s);
					if (e === NOT_SERIALIZABLE) continue;
					logger.warn(
						`Skipped not serializable cache item '${key}': ${e.message}`
					);
					logger.debug(e.stack);
				}
			}
			write(null);
		}
	}

	/**
	 * @param {ObjectDeserializerContext & { logger: Logger, profile: boolean | undefined }} context context
	 */
	deserialize({ read, logger, profile }) {
		if (read()) {
			this.map = read();
		} else if (profile) {
			const map = new Map();
			let key = read();
			while (key !== null) {
				const start = process.hrtime();
				const value = read();
				const durationHr = process.hrtime(start);
				const duration = durationHr[0] * 1000 + durationHr[1] / 1e6;
				if (duration > 1) {
					if (duration > 100)
						logger.error(`Deserialization of '${key}': ${duration} ms`);
					else if (duration > 20)
						logger.warn(`Deserialization of '${key}': ${duration} ms`);
					else if (duration > 5)
						logger.info(`Deserialization of '${key}': ${duration} ms`);
					else if (duration > 2)
						logger.log(`Deserialization of '${key}': ${duration} ms`);
					else logger.debug(`Deserialization of '${key}': ${duration} ms`);
				}
				map.set(key, value);
				key = read();
			}
			this.map = map;
		} else {
			const map = new Map();
			let key = read();
			while (key !== null) {
				map.set(key, read());
				key = read();
			}
			this.map = map;
		}
	}
}

makeSerializable(
	PackContentItems,
	"webpack/lib/cache/PackFileCacheStrategy",
	"PackContentItems"
);

class PackContent {
	/*
		This class can be in these states:
		   |   this.lazy    | this.content | this.outdated | state
		A1 |   undefined    |     Map      |     false     | fresh content
		A2 |   undefined    |     Map      |     true      | (will not happen)
		B1 | lazy () => {}  |  undefined   |     false     | not deserialized
		B2 | lazy () => {}  |  undefined   |     true      | not deserialized, but some items has been removed
		C1 | lazy* () => {} |     Map      |     false     | deserialized
		C2 | lazy* () => {} |     Map      |     true      | deserialized, and some items has been removed

		this.used is a subset of this.items.
		this.items is a subset of this.content.keys() resp. this.lazy().map.keys()
		When this.outdated === false, this.items === this.content.keys() resp. this.lazy().map.keys()
		When this.outdated === true, this.items should be used to recreated this.lazy/this.content.
		When this.lazy and this.content is set, they contain the same data.
		this.get must only be called with a valid item from this.items.
		In state C this.lazy is unMemoized
	*/

	/**
	 * @param {Items} items keys
	 * @param {Items} usedItems used keys
	 * @param {PackContentItems | function(): Promise<PackContentItems>} dataOrFn sync or async content
	 * @param {Logger=} logger logger for logging
	 * @param {string=} lazyName name of dataOrFn for logging
	 */
	constructor(items, usedItems, dataOrFn, logger, lazyName) {
		this.items = items;
		/** @type {(function(): Promise<PackContentItems> | PackContentItems) | undefined} */
		this.lazy = typeof dataOrFn === "function" ? dataOrFn : undefined;
		/** @type {Map<string, any> | undefined} */
		this.content = typeof dataOrFn === "function" ? undefined : dataOrFn.map;
		this.outdated = false;
		this.used = usedItems;
		this.logger = logger;
		this.lazyName = lazyName;
	}

	/**
	 * @param {string} identifier identifier
	 * @returns {string | Promise<string>} result
	 */
	get(identifier) {
		this.used.add(identifier);
		if (this.content) {
			return this.content.get(identifier);
		}

		// We are in state B
		const { lazyName } = this;
		/** @type {string | undefined} */
		let timeMessage;
		if (lazyName) {
			// only log once
			this.lazyName = undefined;
			timeMessage = `restore cache content ${lazyName} (${formatSize(
				this.getSize()
			)})`;
			this.logger.log(
				`starting to restore cache content ${lazyName} (${formatSize(
					this.getSize()
				)}) because of request to: ${identifier}`
			);
			this.logger.time(timeMessage);
		}
		const value = this.lazy();
		if ("then" in value) {
			return value.then(data => {
				const map = data.map;
				if (timeMessage) {
					this.logger.timeEnd(timeMessage);
				}
				// Move to state C
				this.content = map;
				this.lazy = SerializerMiddleware.unMemoizeLazy(this.lazy);
				return map.get(identifier);
			});
		} else {
			const map = value.map;
			if (timeMessage) {
				this.logger.timeEnd(timeMessage);
			}
			// Move to state C
			this.content = map;
			this.lazy = SerializerMiddleware.unMemoizeLazy(this.lazy);
			return map.get(identifier);
		}
	}

	/**
	 * @param {string} reason explanation why unpack is necessary
	 * @returns {void | Promise<void>} maybe a promise if lazy
	 */
	unpack(reason) {
		if (this.content) return;

		// Move from state B to C
		if (this.lazy) {
			const { lazyName } = this;
			/** @type {string | undefined} */
			let timeMessage;
			if (lazyName) {
				// only log once
				this.lazyName = undefined;
				timeMessage = `unpack cache content ${lazyName} (${formatSize(
					this.getSize()
				)})`;
				this.logger.log(
					`starting to unpack cache content ${lazyName} (${formatSize(
						this.getSize()
					)}) because ${reason}`
				);
				this.logger.time(timeMessage);
			}
			const value = this.lazy();
			if ("then" in value) {
				return value.then(data => {
					if (timeMessage) {
						this.logger.timeEnd(timeMessage);
					}
					this.content = data.map;
				});
			} else {
				if (timeMessage) {
					this.logger.timeEnd(timeMessage);
				}
				this.content = value.map;
			}
		}
	}

	/**
	 * @returns {number} size of the content or -1 if not known
	 */
	getSize() {
		if (!this.lazy) return -1;
		const options = /** @type {any} */ (this.lazy).options;
		if (!options) return -1;
		const size = options.size;
		if (typeof size !== "number") return -1;
		return size;
	}

	/**
	 * @param {string} identifier identifier
	 */
	delete(identifier) {
		this.items.delete(identifier);
		this.used.delete(identifier);
		this.outdated = true;
	}

	/**
	 * @template T
	 * @param {function(any): function(): Promise<PackContentItems> | PackContentItems} write write function
	 * @returns {void}
	 */
	writeLazy(write) {
		if (!this.outdated && this.lazy) {
			// State B1 or C1
			// this.lazy is still the valid deserialized version
			write(this.lazy);
			return;
		}
		if (!this.outdated && this.content) {
			// State A1
			const map = new Map(this.content);
			// Move to state C1
			this.lazy = SerializerMiddleware.unMemoizeLazy(
				write(() => new PackContentItems(map))
			);
			return;
		}
		if (this.content) {
			// State A2 or C2
			/** @type {Map<string, any>} */
			const map = new Map();
			for (const item of this.items) {
				map.set(item, this.content.get(item));
			}
			// Move to state C1
			this.outdated = false;
			this.content = map;
			this.lazy = SerializerMiddleware.unMemoizeLazy(
				write(() => new PackContentItems(map))
			);
			return;
		}
		// State B2
		const { lazyName } = this;
		/** @type {string | undefined} */
		let timeMessage;
		if (lazyName) {
			// only log once
			this.lazyName = undefined;
			timeMessage = `unpack cache content ${lazyName} (${formatSize(
				this.getSize()
			)})`;
			this.logger.log(
				`starting to unpack cache content ${lazyName} (${formatSize(
					this.getSize()
				)}) because it's outdated and need to be serialized`
			);
			this.logger.time(timeMessage);
		}
		const value = this.lazy();
		this.outdated = false;
		if ("then" in value) {
			// Move to state B1
			this.lazy = write(() =>
				value.then(data => {
					if (timeMessage) {
						this.logger.timeEnd(timeMessage);
					}
					const oldMap = data.map;
					/** @type {Map<string, any>} */
					const map = new Map();
					for (const item of this.items) {
						map.set(item, oldMap.get(item));
					}
					// Move to state C1 (or maybe C2)
					this.content = map;
					this.lazy = SerializerMiddleware.unMemoizeLazy(this.lazy);

					return new PackContentItems(map);
				})
			);
		} else {
			// Move to state C1
			if (timeMessage) {
				this.logger.timeEnd(timeMessage);
			}
			const oldMap = value.map;
			/** @type {Map<string, any>} */
			const map = new Map();
			for (const item of this.items) {
				map.set(item, oldMap.get(item));
			}
			this.content = map;
			this.lazy = write(() => new PackContentItems(map));
		}
	}
}

/**
 * @param {Buffer} buf buffer
 * @returns {Buffer} buffer that can be collected
 */
const allowCollectingMemory = buf => {
	const wasted = buf.buffer.byteLength - buf.byteLength;
	if (wasted > 8192 && (wasted > 1048576 || wasted > buf.byteLength)) {
		return Buffer.from(buf);
	}
	return buf;
};

class PackFileCacheStrategy {
	/**
	 * @param {object} options options
	 * @param {Compiler} options.compiler the compiler
	 * @param {IntermediateFileSystem} options.fs the filesystem
	 * @param {string} options.context the context directory
	 * @param {string} options.cacheLocation the location of the cache data
	 * @param {string} options.version version identifier
	 * @param {Logger} options.logger a logger
	 * @param {SnapshotOptions} options.snapshot options regarding snapshotting
	 * @param {number} options.maxAge max age of cache items
	 * @param {boolean | undefined} options.profile track and log detailed timing information for individual cache items
	 * @param {boolean | undefined} options.allowCollectingMemory allow to collect unused memory created during deserialization
	 * @param {false | "gzip" | "brotli" | undefined} options.compression compression used
	 * @param {boolean | undefined} options.readonly disable storing cache into filesystem
	 */
	constructor({
		compiler,
		fs,
		context,
		cacheLocation,
		version,
		logger,
		snapshot,
		maxAge,
		profile,
		allowCollectingMemory,
		compression,
		readonly
	}) {
		this.fileSerializer = createFileSerializer(
			fs,
			compiler.options.output.hashFunction
		);
		this.fileSystemInfo = new FileSystemInfo(fs, {
			managedPaths: snapshot.managedPaths,
			immutablePaths: snapshot.immutablePaths,
			logger: logger.getChildLogger("webpack.FileSystemInfo"),
			hashFunction: compiler.options.output.hashFunction
		});
		this.compiler = compiler;
		this.context = context;
		this.cacheLocation = cacheLocation;
		this.version = version;
		this.logger = logger;
		this.maxAge = maxAge;
		this.profile = profile;
		this.readonly = readonly;
		this.allowCollectingMemory = allowCollectingMemory;
		this.compression = compression;
		this._extension =
			compression === "brotli"
				? ".pack.br"
				: compression === "gzip"
					? ".pack.gz"
					: ".pack";
		this.snapshot = snapshot;
		/** @type {BuildDependencies} */
		this.buildDependencies = new Set();
		/** @type {LazySet<string>} */
		this.newBuildDependencies = new LazySet();
		/** @type {Snapshot | undefined} */
		this.resolveBuildDependenciesSnapshot = undefined;
		/** @type {ResolveResults | undefined} */
		this.resolveResults = undefined;
		/** @type {Snapshot | undefined} */
		this.buildSnapshot = undefined;
		/** @type {Promise<Pack> | undefined} */
		this.packPromise = this._openPack();
		this.storePromise = Promise.resolve();
	}

	/**
	 * @returns {Promise<Pack>} pack
	 */
	_getPack() {
		if (this.packPromise === undefined) {
			this.packPromise = this.storePromise.then(() => this._openPack());
		}
		return this.packPromise;
	}

	/**
	 * @returns {Promise<Pack>} the pack
	 */
	_openPack() {
		const { logger, profile, cacheLocation, version } = this;
		/** @type {Snapshot} */
		let buildSnapshot;
		/** @type {BuildDependencies} */
		let buildDependencies;
		/** @type {BuildDependencies} */
		let newBuildDependencies;
		/** @type {Snapshot} */
		let resolveBuildDependenciesSnapshot;
		/** @type {ResolveResults | undefined} */
		let resolveResults;
		logger.time("restore cache container");
		return this.fileSerializer
			.deserialize(null, {
				filename: `${cacheLocation}/index${this._extension}`,
				extension: `${this._extension}`,
				logger,
				profile,
				retainedBuffer: this.allowCollectingMemory
					? allowCollectingMemory
					: undefined
			})
			.catch(err => {
				if (err.code !== "ENOENT") {
					logger.warn(
						`Restoring pack failed from ${cacheLocation}${this._extension}: ${err}`
					);
					logger.debug(err.stack);
				} else {
					logger.debug(
						`No pack exists at ${cacheLocation}${this._extension}: ${err}`
					);
				}
				return undefined;
			})
			.then(packContainer => {
				logger.timeEnd("restore cache container");
				if (!packContainer) return undefined;
				if (!(packContainer instanceof PackContainer)) {
					logger.warn(
						`Restored pack from ${cacheLocation}${this._extension}, but contained content is unexpected.`,
						packContainer
					);
					return undefined;
				}
				if (packContainer.version !== version) {
					logger.log(
						`Restored pack from ${cacheLocation}${this._extension}, but version doesn't match.`
					);
					return undefined;
				}
				logger.time("check build dependencies");
				return Promise.all([
					new Promise((resolve, reject) => {
						this.fileSystemInfo.checkSnapshotValid(
							packContainer.buildSnapshot,
							(err, valid) => {
								if (err) {
									logger.log(
										`Restored pack from ${cacheLocation}${this._extension}, but checking snapshot of build dependencies errored: ${err}.`
									);
									logger.debug(err.stack);
									return resolve(false);
								}
								if (!valid) {
									logger.log(
										`Restored pack from ${cacheLocation}${this._extension}, but build dependencies have changed.`
									);
									return resolve(false);
								}
								buildSnapshot = packContainer.buildSnapshot;
								return resolve(true);
							}
						);
					}),
					new Promise((resolve, reject) => {
						this.fileSystemInfo.checkSnapshotValid(
							packContainer.resolveBuildDependenciesSnapshot,
							(err, valid) => {
								if (err) {
									logger.log(
										`Restored pack from ${cacheLocation}${this._extension}, but checking snapshot of resolving of build dependencies errored: ${err}.`
									);
									logger.debug(err.stack);
									return resolve(false);
								}
								if (valid) {
									resolveBuildDependenciesSnapshot =
										packContainer.resolveBuildDependenciesSnapshot;
									buildDependencies = packContainer.buildDependencies;
									resolveResults = packContainer.resolveResults;
									return resolve(true);
								}
								logger.log(
									"resolving of build dependencies is invalid, will re-resolve build dependencies"
								);
								this.fileSystemInfo.checkResolveResultsValid(
									packContainer.resolveResults,
									(err, valid) => {
										if (err) {
											logger.log(
												`Restored pack from ${cacheLocation}${this._extension}, but resolving of build dependencies errored: ${err}.`
											);
											logger.debug(err.stack);
											return resolve(false);
										}
										if (valid) {
											newBuildDependencies = packContainer.buildDependencies;
											resolveResults = packContainer.resolveResults;
											return resolve(true);
										}
										logger.log(
											`Restored pack from ${cacheLocation}${this._extension}, but build dependencies resolve to different locations.`
										);
										return resolve(false);
									}
								);
							}
						);
					})
				])
					.catch(err => {
						logger.timeEnd("check build dependencies");
						throw err;
					})
					.then(([buildSnapshotValid, resolveValid]) => {
						logger.timeEnd("check build dependencies");
						if (buildSnapshotValid && resolveValid) {
							logger.time("restore cache content metadata");
							const d = packContainer.data();
							logger.timeEnd("restore cache content metadata");
							return d;
						}
						return undefined;
					});
			})
			.then(pack => {
				if (pack) {
					pack.maxAge = this.maxAge;
					this.buildSnapshot = buildSnapshot;
					if (buildDependencies) this.buildDependencies = buildDependencies;
					if (newBuildDependencies)
						this.newBuildDependencies.addAll(newBuildDependencies);
					this.resolveResults = resolveResults;
					this.resolveBuildDependenciesSnapshot =
						resolveBuildDependenciesSnapshot;
					return pack;
				}
				return new Pack(logger, this.maxAge);
			})
			.catch(err => {
				this.logger.warn(
					`Restoring pack from ${cacheLocation}${this._extension} failed: ${err}`
				);
				this.logger.debug(err.stack);
				return new Pack(logger, this.maxAge);
			});
	}

	/**
	 * @param {string} identifier unique name for the resource
	 * @param {Etag | null} etag etag of the resource
	 * @param {any} data cached content
	 * @returns {Promise<void>} promise
	 */
	store(identifier, etag, data) {
		if (this.readonly) return Promise.resolve();

		return this._getPack().then(pack => {
			pack.set(identifier, etag === null ? null : etag.toString(), data);
		});
	}

	/**
	 * @param {string} identifier unique name for the resource
	 * @param {Etag | null} etag etag of the resource
	 * @returns {Promise<any>} promise to the cached content
	 */
	restore(identifier, etag) {
		return this._getPack()
			.then(pack =>
				pack.get(identifier, etag === null ? null : etag.toString())
			)
			.catch(err => {
				if (err && err.code !== "ENOENT") {
					this.logger.warn(
						`Restoring failed for ${identifier} from pack: ${err}`
					);
					this.logger.debug(err.stack);
				}
			});
	}

	/**
	 * @param {LazySet<string> | Iterable<string>} dependencies dependencies to store
	 */
	storeBuildDependencies(dependencies) {
		if (this.readonly) return;
		this.newBuildDependencies.addAll(dependencies);
	}

	afterAllStored() {
		const packPromise = this.packPromise;
		if (packPromise === undefined) return Promise.resolve();
		const reportProgress = ProgressPlugin.getReporter(this.compiler);
		return (this.storePromise = packPromise
			.then(pack => {
				pack.stopCapturingRequests();
				if (!pack.invalid) return;
				this.packPromise = undefined;
				this.logger.log(`Storing pack...`);
				let promise;
				const newBuildDependencies = new Set();
				for (const dep of this.newBuildDependencies) {
					if (!this.buildDependencies.has(dep)) {
						newBuildDependencies.add(dep);
					}
				}
				if (newBuildDependencies.size > 0 || !this.buildSnapshot) {
					if (reportProgress) reportProgress(0.5, "resolve build dependencies");
					this.logger.debug(
						`Capturing build dependencies... (${Array.from(
							newBuildDependencies
						).join(", ")})`
					);
					promise = new Promise((resolve, reject) => {
						this.logger.time("resolve build dependencies");
						this.fileSystemInfo.resolveBuildDependencies(
							this.context,
							newBuildDependencies,
							(err, result) => {
								this.logger.timeEnd("resolve build dependencies");
								if (err) return reject(err);

								this.logger.time("snapshot build dependencies");
								const {
									files,
									directories,
									missing,
									resolveResults,
									resolveDependencies
								} = /** @type {ResolveBuildDependenciesResult} */ (result);
								if (this.resolveResults) {
									for (const [key, value] of resolveResults) {
										this.resolveResults.set(key, value);
									}
								} else {
									this.resolveResults = resolveResults;
								}
								if (reportProgress) {
									reportProgress(
										0.6,
										"snapshot build dependencies",
										"resolving"
									);
								}
								this.fileSystemInfo.createSnapshot(
									undefined,
									resolveDependencies.files,
									resolveDependencies.directories,
									resolveDependencies.missing,
									this.snapshot.resolveBuildDependencies,
									(err, snapshot) => {
										if (err) {
											this.logger.timeEnd("snapshot build dependencies");
											return reject(err);
										}
										if (!snapshot) {
											this.logger.timeEnd("snapshot build dependencies");
											return reject(
												new Error("Unable to snapshot resolve dependencies")
											);
										}
										if (this.resolveBuildDependenciesSnapshot) {
											this.resolveBuildDependenciesSnapshot =
												this.fileSystemInfo.mergeSnapshots(
													this.resolveBuildDependenciesSnapshot,
													snapshot
												);
										} else {
											this.resolveBuildDependenciesSnapshot = snapshot;
										}
										if (reportProgress) {
											reportProgress(
												0.7,
												"snapshot build dependencies",
												"modules"
											);
										}
										this.fileSystemInfo.createSnapshot(
											undefined,
											files,
											directories,
											missing,
											this.snapshot.buildDependencies,
											(err, snapshot) => {
												this.logger.timeEnd("snapshot build dependencies");
												if (err) return reject(err);
												if (!snapshot) {
													return reject(
														new Error("Unable to snapshot build dependencies")
													);
												}
												this.logger.debug("Captured build dependencies");

												if (this.buildSnapshot) {
													this.buildSnapshot =
														this.fileSystemInfo.mergeSnapshots(
															this.buildSnapshot,
															snapshot
														);
												} else {
													this.buildSnapshot = snapshot;
												}

												resolve();
											}
										);
									}
								);
							}
						);
					});
				} else {
					promise = Promise.resolve();
				}
				return promise.then(() => {
					if (reportProgress) reportProgress(0.8, "serialize pack");
					this.logger.time(`store pack`);
					const updatedBuildDependencies = new Set(this.buildDependencies);
					for (const dep of newBuildDependencies) {
						updatedBuildDependencies.add(dep);
					}
					const content = new PackContainer(
						pack,
						this.version,
						/** @type {Snapshot} */ (this.buildSnapshot),
						updatedBuildDependencies,
						this.resolveResults,
						this.resolveBuildDependenciesSnapshot
					);
					return this.fileSerializer
						.serialize(content, {
							filename: `${this.cacheLocation}/index${this._extension}`,
							extension: `${this._extension}`,
							logger: this.logger,
							profile: this.profile
						})
						.then(() => {
							for (const dep of newBuildDependencies) {
								this.buildDependencies.add(dep);
							}
							this.newBuildDependencies.clear();
							this.logger.timeEnd(`store pack`);
							const stats = pack.getContentStats();
							this.logger.log(
								"Stored pack (%d items, %d files, %d MiB)",
								pack.itemInfo.size,
								stats.count,
								Math.round(stats.size / 1024 / 1024)
							);
						})
						.catch(err => {
							this.logger.timeEnd(`store pack`);
							this.logger.warn(`Caching failed for pack: ${err}`);
							this.logger.debug(err.stack);
						});
				});
			})
			.catch(err => {
				this.logger.warn(`Caching failed for pack: ${err}`);
				this.logger.debug(err.stack);
			}));
	}

	clear() {
		this.fileSystemInfo.clear();
		this.buildDependencies.clear();
		this.newBuildDependencies.clear();
		this.resolveBuildDependenciesSnapshot = undefined;
		this.resolveResults = undefined;
		this.buildSnapshot = undefined;
		this.packPromise = undefined;
	}
}

module.exports = PackFileCacheStrategy;