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

"use strict";

const TOMBSTONE = Symbol("tombstone");
const UNDEFINED_MARKER = Symbol("undefined");

/**
 * @template T
 * @typedef {T | undefined} Cell<T>
 */

/**
 * @template T
 * @typedef {T | typeof TOMBSTONE | typeof UNDEFINED_MARKER} InternalCell<T>
 */

/**
 * @template K
 * @template V
 * @param {[K, InternalCell<V>]} pair the internal cell
 * @returns {[K, Cell<V>]} its “safe” representation
 */
const extractPair = pair => {
	const key = pair[0];
	const val = pair[1];
	if (val === UNDEFINED_MARKER || val === TOMBSTONE) {
		return [key, undefined];
	} else {
		return /** @type {[K, Cell<V>]} */ (pair);
	}
};

/**
 * @template K
 * @template V
 */
class StackedMap {
	/**
	 * @param {Map<K, InternalCell<V>>[]=} parentStack an optional parent
	 */
	constructor(parentStack) {
		/** @type {Map<K, InternalCell<V>>} */
		this.map = new Map();
		/** @type {Map<K, InternalCell<V>>[]} */
		this.stack = parentStack === undefined ? [] : parentStack.slice();
		this.stack.push(this.map);
	}

	/**
	 * @param {K} item the key of the element to add
	 * @param {V} value the value of the element to add
	 * @returns {void}
	 */
	set(item, value) {
		this.map.set(item, value === undefined ? UNDEFINED_MARKER : value);
	}

	/**
	 * @param {K} item the item to delete
	 * @returns {void}
	 */
	delete(item) {
		if (this.stack.length > 1) {
			this.map.set(item, TOMBSTONE);
		} else {
			this.map.delete(item);
		}
	}

	/**
	 * @param {K} item the item to test
	 * @returns {boolean} true if the item exists in this set
	 */
	has(item) {
		const topValue = this.map.get(item);
		if (topValue !== undefined) {
			return topValue !== TOMBSTONE;
		}
		if (this.stack.length > 1) {
			for (let i = this.stack.length - 2; i >= 0; i--) {
				const value = this.stack[i].get(item);
				if (value !== undefined) {
					this.map.set(item, value);
					return value !== TOMBSTONE;
				}
			}
			this.map.set(item, TOMBSTONE);
		}
		return false;
	}

	/**
	 * @param {K} item the key of the element to return
	 * @returns {Cell<V>} the value of the element
	 */
	get(item) {
		const topValue = this.map.get(item);
		if (topValue !== undefined) {
			return topValue === TOMBSTONE || topValue === UNDEFINED_MARKER
				? undefined
				: topValue;
		}
		if (this.stack.length > 1) {
			for (let i = this.stack.length - 2; i >= 0; i--) {
				const value = this.stack[i].get(item);
				if (value !== undefined) {
					this.map.set(item, value);
					return value === TOMBSTONE || value === UNDEFINED_MARKER
						? undefined
						: value;
				}
			}
			this.map.set(item, TOMBSTONE);
		}
		return undefined;
	}

	_compress() {
		if (this.stack.length === 1) return;
		this.map = new Map();
		for (const data of this.stack) {
			for (const pair of data) {
				if (pair[1] === TOMBSTONE) {
					this.map.delete(pair[0]);
				} else {
					this.map.set(pair[0], pair[1]);
				}
			}
		}
		this.stack = [this.map];
	}

	asArray() {
		this._compress();
		return Array.from(this.map.keys());
	}

	asSet() {
		this._compress();
		return new Set(this.map.keys());
	}

	asPairArray() {
		this._compress();
		return Array.from(this.map.entries(), extractPair);
	}

	asMap() {
		return new Map(this.asPairArray());
	}

	get size() {
		this._compress();
		return this.map.size;
	}

	createChild() {
		return new StackedMap(this.stack);
	}
}

module.exports = StackedMap;


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

"use strict";

/** @typedef {import("../util/Hash")} Hash */

/**
 * StringXor class provides methods for performing
 * [XOR operations](https://en.wikipedia.org/wiki/Exclusive_or) on strings. In this context
 * we operating on the character codes of two strings, which are represented as
 * [Buffer](https://nodejs.org/api/buffer.html) objects.
 *
 * We use [StringXor in webpack](https://github.com/webpack/webpack/commit/41a8e2ea483a544c4ccd3e6217bdfb80daffca39)
 * to create a hash of the current state of the compilation. By XOR'ing the Module hashes, it
 * doesn't matter if the Module hashes are sorted or not. This is useful because it allows us to avoid sorting the
 * Module hashes.
 *
 * @example
 * ```js
 * const xor = new StringXor();
 * xor.add('hello');
 * xor.add('world');
 * console.log(xor.toString());
 * ```
 *
 * @example
 * ```js
 * const xor = new StringXor();
 * xor.add('foo');
 * xor.add('bar');
 * const hash = createHash('sha256');
 * hash.update(xor.toString());
 * console.log(hash.digest('hex'));
 * ```
 */
class StringXor {
	constructor() {
		/** @type {Buffer|undefined} */
		this._value = undefined;
	}

	/**
	 * Adds a string to the current StringXor object.
	 *
	 * @param {string} str string
	 * @returns {void}
	 */
	add(str) {
		const len = str.length;
		const value = this._value;
		if (value === undefined) {
			/**
			 * We are choosing to use Buffer.allocUnsafe() because it is often faster than Buffer.alloc() because
			 * it allocates a new buffer of the specified size without initializing the memory.
			 */
			const newValue = (this._value = Buffer.allocUnsafe(len));
			for (let i = 0; i < len; i++) {
				newValue[i] = str.charCodeAt(i);
			}
			return;
		}
		const valueLen = value.length;
		if (valueLen < len) {
			const newValue = (this._value = Buffer.allocUnsafe(len));
			let i;
			for (i = 0; i < valueLen; i++) {
				newValue[i] = value[i] ^ str.charCodeAt(i);
			}
			for (; i < len; i++) {
				newValue[i] = str.charCodeAt(i);
			}
		} else {
			for (let i = 0; i < len; i++) {
				value[i] = value[i] ^ str.charCodeAt(i);
			}
		}
	}

	/**
	 * Returns a string that represents the current state of the StringXor object. We chose to use "latin1" encoding
	 * here because "latin1" encoding is a single-byte encoding that can represent all characters in the
	 * [ISO-8859-1 character set](https://en.wikipedia.org/wiki/ISO/IEC_8859-1). This is useful when working
	 * with binary data that needs to be represented as a string.
	 *
	 * @returns {string} Returns a string that represents the current state of the StringXor object.
	 */
	toString() {
		const value = this._value;
		return value === undefined ? "" : value.toString("latin1");
	}

	/**
	 * Updates the hash with the current state of the StringXor object.
	 *
	 * @param {Hash} hash Hash instance
	 */
	updateHash(hash) {
		const value = this._value;
		if (value !== undefined) hash.update(value);
	}
}

module.exports = StringXor;

license: mit


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

"use strict";

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

/**
 * @template {any[]} T
 */
class TupleQueue {
	/**
	 * @param {Iterable<T>=} items The initial elements.
	 */
	constructor(items) {
		/**
		 * @private
		 * @type {TupleSet<T>}
		 */
		this._set = new TupleSet(items);
		/**
		 * @private
		 * @type {Iterator<T>}
		 */
		this._iterator = this._set[Symbol.iterator]();
	}

	/**
	 * Returns the number of elements in this queue.
	 * @returns {number} The number of elements in this queue.
	 */
	get length() {
		return this._set.size;
	}

	/**
	 * Appends the specified element to this queue.
	 * @param {T} item The element to add.
	 * @returns {void}
	 */
	enqueue(...item) {
		this._set.add(...item);
	}

	/**
	 * Retrieves and removes the head of this queue.
	 * @returns {T | undefined} The head of the queue of `undefined` if this queue is empty.
	 */
	dequeue() {
		const result = this._iterator.next();
		if (result.done) {
			if (this._set.size > 0) {
				this._iterator = this._set[Symbol.iterator]();
				const value = this._iterator.next().value;
				this._set.delete(...value);
				return value;
			}
			return undefined;
		}
		this._set.delete(...result.value);
		return result.value;
	}
}

module.exports = TupleQueue;


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

"use strict";

/**
 * @template {any[]} T
 */
class TupleSet {
	constructor(init) {
		this._map = new Map();
		this.size = 0;
		if (init) {
			for (const tuple of init) {
				this.add(...tuple);
			}
		}
	}

	/**
	 * @param  {T} args tuple
	 * @returns {void}
	 */
	add(...args) {
		let map = this._map;
		for (let i = 0; i < args.length - 2; i++) {
			const arg = args[i];
			const innerMap = map.get(arg);
			if (innerMap === undefined) {
				map.set(arg, (map = new Map()));
			} else {
				map = innerMap;
			}
		}

		const beforeLast = args[args.length - 2];
		let set = map.get(beforeLast);
		if (set === undefined) {
			map.set(beforeLast, (set = new Set()));
		}

		const last = args[args.length - 1];
		this.size -= set.size;
		set.add(last);
		this.size += set.size;
	}

	/**
	 * @param  {T} args tuple
	 * @returns {boolean} true, if the tuple is in the Set
	 */
	has(...args) {
		let map = this._map;
		for (let i = 0; i < args.length - 2; i++) {
			const arg = args[i];
			map = map.get(arg);
			if (map === undefined) {
				return false;
			}
		}

		const beforeLast = args[args.length - 2];
		let set = map.get(beforeLast);
		if (set === undefined) {
			return false;
		}

		const last = args[args.length - 1];
		return set.has(last);
	}

	/**
	 * @param {T} args tuple
	 * @returns {void}
	 */
	delete(...args) {
		let map = this._map;
		for (let i = 0; i < args.length - 2; i++) {
			const arg = args[i];
			map = map.get(arg);
			if (map === undefined) {
				return;
			}
		}

		const beforeLast = args[args.length - 2];
		let set = map.get(beforeLast);
		if (set === undefined) {
			return;
		}

		const last = args[args.length - 1];
		this.size -= set.size;
		set.delete(last);
		this.size += set.size;
	}

	/**
	 * @returns {Iterator<T>} iterator
	 */
	[Symbol.iterator]() {
		const iteratorStack = [];
		const tuple = [];
		let currentSetIterator = undefined;

		const next = it => {
			const result = it.next();
			if (result.done) {
				if (iteratorStack.length === 0) return false;
				tuple.pop();
				return next(iteratorStack.pop());
			}
			const [key, value] = result.value;
			iteratorStack.push(it);
			tuple.push(key);
			if (value instanceof Set) {
				currentSetIterator = value[Symbol.iterator]();
				return true;
			} else {
				return next(value[Symbol.iterator]());
			}
		};

		next(this._map[Symbol.iterator]());

		return {
			next() {
				while (currentSetIterator) {
					const result = currentSetIterator.next();
					if (result.done) {
						tuple.pop();
						if (!next(iteratorStack.pop())) {
							currentSetIterator = undefined;
						}
					} else {
						return {
							done: false,
							value: /** @type {T} */ (tuple.concat(result.value))
						};
					}
				}
				return { done: true, value: undefined };
			}
		};
	}
}

module.exports = TupleSet;


code:
/*
	MIT License http://www.opensource.org/licenses/mit-license.php
	Author Ivan Kopeykin @vankop
*/

"use strict";

/** @typedef {import("./fs").InputFileSystem} InputFileSystem */
/** @typedef {(error: Error|null, result?: Buffer) => void} ErrorFirstCallback */

const backSlashCharCode = "\\".charCodeAt(0);
const slashCharCode = "/".charCodeAt(0);
const aLowerCaseCharCode = "a".charCodeAt(0);
const zLowerCaseCharCode = "z".charCodeAt(0);
const aUpperCaseCharCode = "A".charCodeAt(0);
const zUpperCaseCharCode = "Z".charCodeAt(0);
const _0CharCode = "0".charCodeAt(0);
const _9CharCode = "9".charCodeAt(0);
const plusCharCode = "+".charCodeAt(0);
const hyphenCharCode = "-".charCodeAt(0);
const colonCharCode = ":".charCodeAt(0);
const hashCharCode = "#".charCodeAt(0);
const queryCharCode = "?".charCodeAt(0);
/**
 * Get scheme if specifier is an absolute URL specifier
 * e.g. Absolute specifiers like 'file:///user/webpack/index.js'
 * https://tools.ietf.org/html/rfc3986#section-3.1
 * @param {string} specifier specifier
 * @returns {string|undefined} scheme if absolute URL specifier provided
 */
function getScheme(specifier) {
	const start = specifier.charCodeAt(0);

	// First char maybe only a letter
	if (
		(start < aLowerCaseCharCode || start > zLowerCaseCharCode) &&
		(start < aUpperCaseCharCode || start > zUpperCaseCharCode)
	) {
		return undefined;
	}

	let i = 1;
	let ch = specifier.charCodeAt(i);

	while (
		(ch >= aLowerCaseCharCode && ch <= zLowerCaseCharCode) ||
		(ch >= aUpperCaseCharCode && ch <= zUpperCaseCharCode) ||
		(ch >= _0CharCode && ch <= _9CharCode) ||
		ch === plusCharCode ||
		ch === hyphenCharCode
	) {
		if (++i === specifier.length) return undefined;
		ch = specifier.charCodeAt(i);
	}

	// Scheme must end with colon
	if (ch !== colonCharCode) return undefined;

	// Check for Windows absolute path
	// https://url.spec.whatwg.org/#url-miscellaneous
	if (i === 1) {
		const nextChar = i + 1 < specifier.length ? specifier.charCodeAt(i + 1) : 0;
		if (
			nextChar === 0 ||
			nextChar === backSlashCharCode ||
			nextChar === slashCharCode ||
			nextChar === hashCharCode ||
			nextChar === queryCharCode
		) {
			return undefined;
		}
	}

	return specifier.slice(0, i).toLowerCase();
}

/**
 * @param {string} specifier specifier
 * @returns {string | null | undefined} protocol if absolute URL specifier provided
 */
function getProtocol(specifier) {
	const scheme = getScheme(specifier);
	return scheme === undefined ? undefined : scheme + ":";
}

exports.getScheme = getScheme;
exports.getProtocol = getProtocol;


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

"use strict";

/**
 * @template {any[]} T
 * @template V
 * @typedef {Map<object, WeakTupleMap<T, V>>} M
 */
/**
 * @template {any[]} T
 * @template V
 * @typedef {WeakMap<object, WeakTupleMap<T, V>>} W
 */

/**
 * @param {any} thing thing
 * @returns {boolean} true if is weak
 */
const isWeakKey = thing => typeof thing === "object" && thing !== null;

/**
 * @template {any[]} T
 * @template V
 */
class WeakTupleMap {
	constructor() {
		/** @private */
		this.f = 0;
		/**
		 * @private
		 * @type {any}
		 */
		this.v = undefined;
		/**
		 * @private
		 * @type {M<T, V> | undefined}
		 */
		this.m = undefined;
		/**
		 * @private
		 * @type {W<T, V> | undefined}
		 */
		this.w = undefined;
	}

	/**
	 * @param {[...T, V]} args tuple
	 * @returns {void}
	 */
	set(...args) {
		/** @type {WeakTupleMap<T, V>} */
		let node = this;
		for (let i = 0; i < args.length - 1; i++) {
			node = node._get(args[i]);
		}
		node._setValue(args[args.length - 1]);
	}

	/**
	 * @param {T} args tuple
	 * @returns {boolean} true, if the tuple is in the Set
	 */
	has(...args) {
		/** @type {WeakTupleMap<T, V> | undefined} */
		let node = this;
		for (let i = 0; i < args.length; i++) {
			node = node._peek(args[i]);
			if (node === undefined) return false;
		}
		return node._hasValue();
	}

	/**
	 * @param {T} args tuple
	 * @returns {V | undefined} the value
	 */
	get(...args) {
		/** @type {WeakTupleMap<T, V> | undefined} */
		let node = this;
		for (let i = 0; i < args.length; i++) {
			node = node._peek(args[i]);
			if (node === undefined) return undefined;
		}
		return node._getValue();
	}

	/**
	 * @param {[...T, function(): V]} args tuple
	 * @returns {V} the value
	 */
	provide(...args) {
		/** @type {WeakTupleMap<T, V>} */
		let node = this;
		for (let i = 0; i < args.length - 1; i++) {
			node = node._get(args[i]);
		}
		if (node._hasValue()) return node._getValue();
		const fn = args[args.length - 1];
		const newValue = fn(...args.slice(0, -1));
		node._setValue(newValue);
		return newValue;
	}

	/**
	 * @param {T} args tuple
	 * @returns {void}
	 */
	delete(...args) {
		/** @type {WeakTupleMap<T, V> | undefined} */
		let node = this;
		for (let i = 0; i < args.length; i++) {
			node = node._peek(args[i]);
			if (node === undefined) return;
		}
		node._deleteValue();
	}

	/**
	 * @returns {void}
	 */
	clear() {
		this.f = 0;
		this.v = undefined;
		this.w = undefined;
		this.m = undefined;
	}

	_getValue() {
		return this.v;
	}

	_hasValue() {
		return (this.f & 1) === 1;
	}

	/**
	 * @param {any} v value
	 * @private
	 */
	_setValue(v) {
		this.f |= 1;
		this.v = v;
	}

	_deleteValue() {
		this.f &= 6;
		this.v = undefined;
	}

	/**
	 * @param {any} thing thing
	 * @returns {WeakTupleMap<T, V> | undefined} thing
	 * @private
	 */
	_peek(thing) {
		if (isWeakKey(thing)) {
			if ((this.f & 4) !== 4) return undefined;
			return /** @type {W<T, V>} */ (this.w).get(thing);
		} else {
			if ((this.f & 2) !== 2) return undefined;
			return /** @type {M<T, V>} */ (this.m).get(thing);
		}
	}

	/**
	 * @private
	 * @param {any} thing thing
	 * @returns {WeakTupleMap<T, V>} value
	 */
	_get(thing) {
		if (isWeakKey(thing)) {
			if ((this.f & 4) !== 4) {
				const newMap = new WeakMap();
				this.f |= 4;
				const newNode = new WeakTupleMap();
				(this.w = newMap).set(thing, newNode);
				return newNode;
			}
			const entry =
				/** @type {W<T, V>} */
				(this.w).get(thing);
			if (entry !== undefined) {
				return entry;
			}
			const newNode = new WeakTupleMap();
			/** @type {W<T, V>} */
			(this.w).set(thing, newNode);
			return newNode;
		} else {
			if ((this.f & 2) !== 2) {
				const newMap = new Map();
				this.f |= 2;
				const newNode = new WeakTupleMap();
				(this.m = newMap).set(thing, newNode);
				return newNode;
			}
			const entry =
				/** @type {M<T, V>} */
				(this.m).get(thing);
			if (entry !== undefined) {
				return entry;
			}
			const newNode = new WeakTupleMap();
			/** @type {M<T, V>} */
			(this.m).set(thing, newNode);
			return newNode;
		}
	}
}

module.exports = WeakTupleMap;


code:
/*
	MIT License http://www.opensource.org/licenses/mit-license.php
	Author Mikola Lysenko @mikolalysenko
*/

"use strict";

/* cspell:disable-next-line */
// Refactor: Peter Somogyvari @petermetz

/** @typedef {">=" | "<=" | "<" | ">" | "-" } BinarySearchPredicate */
/** @typedef {"GE" | "GT" | "LT" | "LE" | "EQ" } SearchPredicateSuffix */

/**
 * Helper function for compiling binary search functions.
 *
 * The generated code uses a while loop to repeatedly divide the search interval
 * in half until the desired element is found, or the search interval is empty.
 *
 * The following is an example of a generated function for calling `compileSearch("P", "c(x,y)<=0", true, ["y", "c"], false)`:
 *
 * ```js
 * function P(a,l,h,y,c){var i=l-1;while(l<=h){var m=(l+h)>>>1,x=a[m];if(c(x,y)<=0){i=m;l=m+1}else{h=m-1}}return i};
 * ```
 *
 * @param {string} funcName The name of the function to be compiled.
 * @param {string} predicate The predicate / comparison operator to be used in the binary search.
 * @param {boolean} reversed Whether the search should be reversed.
 * @param {string[]} extraArgs Extra arguments to be passed to the function.
 * @param {boolean=} earlyOut Whether the search should return as soon as a match is found.
 * @returns {string} The compiled binary search function.
 */
const compileSearch = (funcName, predicate, reversed, extraArgs, earlyOut) => {
	const code = [
		"function ",
		funcName,
		"(a,l,h,",
		extraArgs.join(","),
		"){",
		earlyOut ? "" : "var i=",
		reversed ? "l-1" : "h+1",
		";while(l<=h){var m=(l+h)>>>1,x=a[m]"
	];

	if (earlyOut) {
		if (predicate.indexOf("c") < 0) {
			code.push(";if(x===y){return m}else if(x<=y){");
		} else {
			code.push(";var p=c(x,y);if(p===0){return m}else if(p<=0){");
		}
	} else {
		code.push(";if(", predicate, "){i=m;");
	}
	if (reversed) {
		code.push("l=m+1}else{h=m-1}");
	} else {
		code.push("h=m-1}else{l=m+1}");
	}
	code.push("}");
	if (earlyOut) {
		code.push("return -1};");
	} else {
		code.push("return i};");
	}
	return code.join("");
};

/**
 * This helper functions generate code for two binary search functions:
 * A(): Performs a binary search on an array using the comparison operator specified.
 * P(): Performs a binary search on an array using a _custom comparison function_
 * `c(x,y)` **and** comparison operator specified by `predicate`.
 *
 * @param {BinarySearchPredicate} predicate The predicate / comparison operator to be used in the binary search.
 * @param {boolean} reversed Whether the search should be reversed.
 * @param {SearchPredicateSuffix} suffix The suffix to be used in the function name.
 * @param {boolean=} earlyOut Whether the search should return as soon as a match is found.
 * @returns {Function} The compiled binary search function.
 */
const compileBoundsSearch = (predicate, reversed, suffix, earlyOut) => {
	const arg1 = compileSearch(
		"A",
		"x" + predicate + "y",
		reversed,
		["y"],
		earlyOut
	);

	const arg2 = compileSearch(
		"P",
		"c(x,y)" + predicate + "0",
		reversed,
		["y", "c"],
		earlyOut
	);

	const fnHeader = "function dispatchBinarySearch";

	const fnBody =
		"(a,y,c,l,h){\
if(typeof(c)==='function'){\
return P(a,(l===void 0)?0:l|0,(h===void 0)?a.length-1:h|0,y,c)\
}else{\
return A(a,(c===void 0)?0:c|0,(l===void 0)?a.length-1:l|0,y)\
}}\
return dispatchBinarySearch";

	const fnArgList = [arg1, arg2, fnHeader, suffix, fnBody, suffix];
	const fnSource = fnArgList.join("");
	const result = new Function(fnSource);
	return result();
};

/**
 * These functions are used to perform binary searches on arrays.
 *
 * @example
 * ```js
 * const { gt, le} = require("./binarySearchBounds");
 * const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
 *
 * // Find the index of the first element greater than 5
 * const index1 = gt(arr, 5); // index1 === 3
 *
 * // Find the index of the first element less than or equal to 5
 * const index2 = le(arr, 5); // index2 === 4
 * ```
 */
module.exports = {
	ge: compileBoundsSearch(">=", false, "GE"),
	gt: compileBoundsSearch(">", false, "GT"),
	lt: compileBoundsSearch("<", true, "LT"),
	le: compileBoundsSearch("<=", true, "LE"),
	eq: compileBoundsSearch("-", true, "EQ", true)
};


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

"use strict";

/** @typedef {import("../Dependency")} Dependency */
/** @typedef {import("../Module")} Module */
/** @typedef {import("../ModuleGraph")} ModuleGraph */
/** @typedef {import("../javascript/JavascriptParser").Range} Range */

/**
 * @summary Get the subset of ids and their corresponding range in an id chain that should be re-rendered by webpack.
 * Only those in the chain that are actually referring to namespaces or imports should be re-rendered.
 * Deeper member accessors on the imported object should not be re-rendered.  If deeper member accessors are re-rendered,
 * there is a potential loss of meaning with rendering a quoted accessor as an unquoted accessor, or vice versa,
 * because minifiers treat quoted accessors differently.  e.g. import { a } from "./module"; a["b"] vs a.b
 * @param {string[]} untrimmedIds chained ids
 * @param {Range} untrimmedRange range encompassing allIds
 * @param {Range[] | undefined} ranges cumulative range of ids for each of allIds
 * @param {ModuleGraph} moduleGraph moduleGraph
 * @param {Dependency} dependency dependency
 * @returns {{trimmedIds: string[], trimmedRange: Range}} computed trimmed ids and cumulative range of those ids
 */
exports.getTrimmedIdsAndRange = (
	untrimmedIds,
	untrimmedRange,
	ranges,
	moduleGraph,
	dependency
) => {
	let trimmedIds = trimIdsToThoseImported(
		untrimmedIds,
		moduleGraph,
		dependency
	);
	let trimmedRange = untrimmedRange;
	if (trimmedIds.length !== untrimmedIds.length) {
		// The array returned from dep.idRanges is right-aligned with the array returned from dep.names.
		// Meaning, the two arrays may not always have the same number of elements, but the last element of
		// dep.idRanges corresponds to [the expression fragment to the left of] the last element of dep.names.
		// Use this to find the correct replacement range based on the number of ids that were trimmed.
		const idx =
			ranges === undefined
				? -1 /* trigger failure case below */
				: ranges.length + (trimmedIds.length - untrimmedIds.length);
		if (idx < 0 || idx >= /** @type {Range[]} */ (ranges).length) {
			// cspell:ignore minifiers
			// Should not happen but we can't throw an error here because of backward compatibility with
			// external plugins in wp5.  Instead, we just disable trimming for now.  This may break some minifiers.
			trimmedIds = untrimmedIds;
			// TODO webpack 6 remove the "trimmedIds = ids" above and uncomment the following line instead.
			// throw new Error("Missing range starts data for id replacement trimming.");
		} else {
			trimmedRange = /** @type {Range[]} */ (ranges)[idx];
		}
	}

	return { trimmedIds, trimmedRange };
};

/**
 * @summary Determine which IDs in the id chain are actually referring to namespaces or imports,
 * and which are deeper member accessors on the imported object.
 * @param {string[]} ids untrimmed ids
 * @param {ModuleGraph} moduleGraph moduleGraph
 * @param {Dependency} dependency dependency
 * @returns {string[]} trimmed ids
 */
function trimIdsToThoseImported(ids, moduleGraph, dependency) {
	/** @type {string[]} */
	let trimmedIds = [];
	let currentExportsInfo = moduleGraph.getExportsInfo(
		/** @type {Module} */ (moduleGraph.getModule(dependency))
	);
	for (let i = 0; i < ids.length; i++) {
		if (i === 0 && ids[i] === "default") {
			continue; // ExportInfo for the next level under default is still at the root ExportsInfo, so don't advance currentExportsInfo
		}
		const exportInfo = currentExportsInfo.getExportInfo(ids[i]);
		if (exportInfo.provided === false) {
			// json imports have nested ExportInfo for elements that things that are not actually exported, so check .provided
			trimmedIds = ids.slice(0, i);
			break;
		}
		const nestedInfo = exportInfo.getNestedExportsInfo();
		if (!nestedInfo) {
			// once all nested exports are traversed, the next item is the actual import so stop there
			trimmedIds = ids.slice(0, i + 1);
			break;
		}
		currentExportsInfo = nestedInfo;
	}
	// Never trim to nothing.  This can happen for invalid imports (e.g. import { notThere } from "./module", or import { anything } from "./missingModule")
	return trimmedIds.length ? trimmedIds : ids;
}


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

"use strict";

/** @type {WeakMap<object, WeakMap<object, object>>} */
const mergeCache = new WeakMap();
/** @type {WeakMap<object, Map<string, Map<string|number|boolean, object>>>} */
const setPropertyCache = new WeakMap();
const DELETE = Symbol("DELETE");
const DYNAMIC_INFO = Symbol("cleverMerge dynamic info");

/**
 * Merges two given objects and caches the result to avoid computation if same objects passed as arguments again.
 * @template T
 * @template O
 * @example
 * // performs cleverMerge(first, second), stores the result in WeakMap and returns result
 * cachedCleverMerge({a: 1}, {a: 2})
 * {a: 2}
 *  // when same arguments passed, gets the result from WeakMap and returns it.
 * cachedCleverMerge({a: 1}, {a: 2})
 * {a: 2}
 * @param {T} first first object
 * @param {O} second second object
 * @returns {T & O | T | O} merged object of first and second object
 */
const cachedCleverMerge = (first, second) => {
	if (second === undefined) return first;
	if (first === undefined) return second;
	if (typeof second !== "object" || second === null) return second;
	if (typeof first !== "object" || first === null) return first;

	let innerCache = mergeCache.get(first);
	if (innerCache === undefined) {
		innerCache = new WeakMap();
		mergeCache.set(first, innerCache);
	}
	const prevMerge = /** @type {T & O} */ (innerCache.get(second));
	if (prevMerge !== undefined) return prevMerge;
	const newMerge = _cleverMerge(first, second, true);
	innerCache.set(second, newMerge);
	return /** @type {T & O} */ (newMerge);
};

/**
 * @template T
 * @param {Partial<T>} obj object
 * @param {string} property property
 * @param {string|number|boolean} value assignment value
 * @returns {T} new object
 */
const cachedSetProperty = (obj, property, value) => {
	let mapByProperty = setPropertyCache.get(obj);

	if (mapByProperty === undefined) {
		mapByProperty = new Map();
		setPropertyCache.set(obj, mapByProperty);
	}

	let mapByValue = mapByProperty.get(property);

	if (mapByValue === undefined) {
		mapByValue = new Map();
		mapByProperty.set(property, mapByValue);
	}

	let result = mapByValue.get(value);

	if (result) return /** @type {T} */ (result);

	result = {
		...obj,
		[property]: value
	};
	mapByValue.set(value, result);

	return /** @type {T} */ (result);
};

/**
 * @typedef {object} ObjectParsedPropertyEntry
 * @property {any | undefined} base base value
 * @property {string | undefined} byProperty the name of the selector property
 * @property {Map<string, any>} byValues value depending on selector property, merged with base
 */

/**
 * @typedef {object} ParsedObject
 * @property {Map<string, ObjectParsedPropertyEntry>} static static properties (key is property name)
 * @property {{ byProperty: string, fn: Function } | undefined} dynamic dynamic part
 */

/** @type {WeakMap<object, ParsedObject>} */
const parseCache = new WeakMap();

/**
 * @param {object} obj the object
 * @returns {ParsedObject} parsed object
 */
const cachedParseObject = obj => {
	const entry = parseCache.get(obj);
	if (entry !== undefined) return entry;
	const result = parseObject(obj);
	parseCache.set(obj, result);
	return result;
};

/**
 * @param {object} obj the object
 * @returns {ParsedObject} parsed object
 */
const parseObject = obj => {
	const info = new Map();
	let dynamicInfo;
	const getInfo = p => {
		const entry = info.get(p);
		if (entry !== undefined) return entry;
		const newEntry = {
			base: undefined,
			byProperty: undefined,
			byValues: undefined
		};
		info.set(p, newEntry);
		return newEntry;
	};
	for (const key of Object.keys(obj)) {
		if (key.startsWith("by")) {
			const byProperty = key;
			const byObj = obj[byProperty];
			if (typeof byObj === "object") {
				for (const byValue of Object.keys(byObj)) {
					const obj = byObj[byValue];
					for (const key of Object.keys(obj)) {
						const entry = getInfo(key);
						if (entry.byProperty === undefined) {
							entry.byProperty = byProperty;
							entry.byValues = new Map();
						} else if (entry.byProperty !== byProperty) {
							throw new Error(
								`${byProperty} and ${entry.byProperty} for a single property is not supported`
							);
						}
						entry.byValues.set(byValue, obj[key]);
						if (byValue === "default") {
							for (const otherByValue of Object.keys(byObj)) {
								if (!entry.byValues.has(otherByValue))
									entry.byValues.set(otherByValue, undefined);
							}
						}
					}
				}
			} else if (typeof byObj === "function") {
				if (dynamicInfo === undefined) {
					dynamicInfo = {
						byProperty: key,
						fn: byObj
					};
				} else {
					throw new Error(
						`${key} and ${dynamicInfo.byProperty} when both are functions is not supported`
					);
				}
			} else {
				const entry = getInfo(key);
				entry.base = obj[key];
			}
		} else {
			const entry = getInfo(key);
			entry.base = obj[key];
		}
	}
	return {
		static: info,
		dynamic: dynamicInfo
	};
};

/**
 * @param {Map<string, ObjectParsedPropertyEntry>} info static properties (key is property name)
 * @param {{ byProperty: string, fn: Function } | undefined} dynamicInfo dynamic part
 * @returns {object} the object
 */
const serializeObject = (info, dynamicInfo) => {
	const obj = {};
	// Setup byProperty structure
	for (const entry of info.values()) {
		if (entry.byProperty !== undefined) {
			const byObj = (obj[entry.byProperty] = obj[entry.byProperty] || {});
			for (const byValue of entry.byValues.keys()) {
				byObj[byValue] = byObj[byValue] || {};
			}
		}
	}
	for (const [key, entry] of info) {
		if (entry.base !== undefined) {
			obj[key] = entry.base;
		}
		// Fill byProperty structure
		if (entry.byProperty !== undefined) {
			const byObj = (obj[entry.byProperty] = obj[entry.byProperty] || {});
			for (const byValue of Object.keys(byObj)) {
				const value = getFromByValues(entry.byValues, byValue);
				if (value !== undefined) byObj[byValue][key] = value;
			}
		}
	}
	if (dynamicInfo !== undefined) {
		obj[dynamicInfo.byProperty] = dynamicInfo.fn;
	}
	return obj;
};

const VALUE_TYPE_UNDEFINED = 0;
const VALUE_TYPE_ATOM = 1;
const VALUE_TYPE_ARRAY_EXTEND = 2;
const VALUE_TYPE_OBJECT = 3;
const VALUE_TYPE_DELETE = 4;

/**
 * @param {any} value a single value
 * @returns {VALUE_TYPE_UNDEFINED | VALUE_TYPE_ATOM | VALUE_TYPE_ARRAY_EXTEND | VALUE_TYPE_OBJECT | VALUE_TYPE_DELETE} value type
 */
const getValueType = value => {
	if (value === undefined) {
		return VALUE_TYPE_UNDEFINED;
	} else if (value === DELETE) {
		return VALUE_TYPE_DELETE;
	} else if (Array.isArray(value)) {
		if (value.lastIndexOf("...") !== -1) return VALUE_TYPE_ARRAY_EXTEND;
		return VALUE_TYPE_ATOM;
	} else if (
		typeof value === "object" &&
		value !== null &&
		(!value.constructor || value.constructor === Object)
	) {
		return VALUE_TYPE_OBJECT;
	}
	return VALUE_TYPE_ATOM;
};

/**
 * Merges two objects. Objects are deeply clever merged.
 * Arrays might reference the old value with "...".
 * Non-object values take preference over object values.
 * @template T
 * @template O
 * @param {T} first first object
 * @param {O} second second object
 * @returns {T & O | T | O} merged object of first and second object
 */
const cleverMerge = (first, second) => {
	if (second === undefined) return first;
	if (first === undefined) return second;
	if (typeof second !== "object" || second === null) return second;
	if (typeof first !== "object" || first === null) return first;

	return /** @type {T & O} */ (_cleverMerge(first, second, false));
};

/**
 * Merges two objects. Objects are deeply clever merged.
 * @param {object} first first object
 * @param {object} second second object
 * @param {boolean} internalCaching should parsing of objects and nested merges be cached
 * @returns {object} merged object of first and second object
 */
const _cleverMerge = (first, second, internalCaching = false) => {
	const firstObject = internalCaching
		? cachedParseObject(first)
		: parseObject(first);
	const { static: firstInfo, dynamic: firstDynamicInfo } = firstObject;

	// If the first argument has a dynamic part we modify the dynamic part to merge the second argument
	if (firstDynamicInfo !== undefined) {
		let { byProperty, fn } = firstDynamicInfo;
		const fnInfo = fn[DYNAMIC_INFO];
		if (fnInfo) {
			second = internalCaching
				? cachedCleverMerge(fnInfo[1], second)
				: cleverMerge(fnInfo[1], second);
			fn = fnInfo[0];
		}
		const newFn = (...args) => {
			const fnResult = fn(...args);
			return internalCaching
				? cachedCleverMerge(fnResult, second)
				: cleverMerge(fnResult, second);
		};
		newFn[DYNAMIC_INFO] = [fn, second];
		return serializeObject(firstObject.static, { byProperty, fn: newFn });
	}

	// If the first part is static only, we merge the static parts and keep the dynamic part of the second argument
	const secondObject = internalCaching
		? cachedParseObject(second)
		: parseObject(second);
	const { static: secondInfo, dynamic: secondDynamicInfo } = secondObject;
	/** @type {Map<string, ObjectParsedPropertyEntry>} */
	const resultInfo = new Map();
	for (const [key, firstEntry] of firstInfo) {
		const secondEntry = secondInfo.get(key);
		const entry =
			secondEntry !== undefined
				? mergeEntries(firstEntry, secondEntry, internalCaching)
				: firstEntry;
		resultInfo.set(key, entry);
	}
	for (const [key, secondEntry] of secondInfo) {
		if (!firstInfo.has(key)) {
			resultInfo.set(key, secondEntry);
		}
	}
	return serializeObject(resultInfo, secondDynamicInfo);
};

/**
 * @param {ObjectParsedPropertyEntry} firstEntry a
 * @param {ObjectParsedPropertyEntry} secondEntry b
 * @param {boolean} internalCaching should parsing of objects and nested merges be cached
 * @returns {ObjectParsedPropertyEntry} new entry
 */
const mergeEntries = (firstEntry, secondEntry, internalCaching) => {
	switch (getValueType(secondEntry.base)) {
		case VALUE_TYPE_ATOM:
		case VALUE_TYPE_DELETE:
			// No need to consider firstEntry at all
			// second value override everything
			// = second.base + second.byProperty
			return secondEntry;
		case VALUE_TYPE_UNDEFINED:
			if (!firstEntry.byProperty) {
				// = first.base + second.byProperty
				return {
					base: firstEntry.base,
					byProperty: secondEntry.byProperty,
					byValues: secondEntry.byValues
				};
			} else if (firstEntry.byProperty !== secondEntry.byProperty) {
				throw new Error(
					`${firstEntry.byProperty} and ${secondEntry.byProperty} for a single property is not supported`
				);
			} else {
				// = first.base + (first.byProperty + second.byProperty)
				// need to merge first and second byValues
				const newByValues = new Map(firstEntry.byValues);
				for (const [key, value] of secondEntry.byValues) {
					const firstValue = getFromByValues(firstEntry.byValues, key);
					newByValues.set(
						key,
						mergeSingleValue(firstValue, value, internalCaching)
					);
				}
				return {
					base: firstEntry.base,
					byProperty: firstEntry.byProperty,
					byValues: newByValues
				};
			}
		default: {
			if (!firstEntry.byProperty) {
				// The simple case
				// = (first.base + second.base) + second.byProperty
				return {
					base: mergeSingleValue(
						firstEntry.base,
						secondEntry.base,
						internalCaching
					),
					byProperty: secondEntry.byProperty,
					byValues: secondEntry.byValues
				};
			}
			let newBase;
			const intermediateByValues = new Map(firstEntry.byValues);
			for (const [key, value] of intermediateByValues) {
				intermediateByValues.set(
					key,
					mergeSingleValue(value, secondEntry.base, internalCaching)
				);
			}
			if (
				Array.from(firstEntry.byValues.values()).every(value => {
					const type = getValueType(value);
					return type === VALUE_TYPE_ATOM || type === VALUE_TYPE_DELETE;
				})
			) {
				// = (first.base + second.base) + ((first.byProperty + second.base) + second.byProperty)
				newBase = mergeSingleValue(
					firstEntry.base,
					secondEntry.base,
					internalCaching
				);
			} else {
				// = first.base + ((first.byProperty (+default) + second.base) + second.byProperty)
				newBase = firstEntry.base;
				if (!intermediateByValues.has("default"))
					intermediateByValues.set("default", secondEntry.base);
			}
			if (!secondEntry.byProperty) {
				// = first.base + (first.byProperty + second.base)
				return {
					base: newBase,
					byProperty: firstEntry.byProperty,
					byValues: intermediateByValues
				};
			} else if (firstEntry.byProperty !== secondEntry.byProperty) {
				throw new Error(
					`${firstEntry.byProperty} and ${secondEntry.byProperty} for a single property is not supported`
				);
			}
			const newByValues = new Map(intermediateByValues);
			for (const [key, value] of secondEntry.byValues) {
				const firstValue = getFromByValues(intermediateByValues, key);
				newByValues.set(
					key,
					mergeSingleValue(firstValue, value, internalCaching)
				);
			}
			return {
				base: newBase,
				byProperty: firstEntry.byProperty,
				byValues: newByValues
			};
		}
	}
};

/**
 * @param {Map<string, any>} byValues all values
 * @param {string} key value of the selector
 * @returns {any | undefined} value
 */
const getFromByValues = (byValues, key) => {
	if (key !== "default" && byValues.has(key)) {
		return byValues.get(key);
	}
	return byValues.get("default");
};

/**
 * @param {any} a value
 * @param {any} b value
 * @param {boolean} internalCaching should parsing of objects and nested merges be cached
 * @returns {any} value
 */
const mergeSingleValue = (a, b, internalCaching) => {
	const bType = getValueType(b);
	const aType = getValueType(a);
	switch (bType) {
		case VALUE_TYPE_DELETE:
		case VALUE_TYPE_ATOM:
			return b;
		case VALUE_TYPE_OBJECT: {
			return aType !== VALUE_TYPE_OBJECT
				? b
				: internalCaching
					? cachedCleverMerge(a, b)
					: cleverMerge(a, b);
		}
		case VALUE_TYPE_UNDEFINED:
			return a;
		case VALUE_TYPE_ARRAY_EXTEND:
			switch (
				aType !== VALUE_TYPE_ATOM
					? aType
					: Array.isArray(a)
						? VALUE_TYPE_ARRAY_EXTEND
						: VALUE_TYPE_OBJECT
			) {
				case VALUE_TYPE_UNDEFINED:
					return b;
				case VALUE_TYPE_DELETE:
					return b.filter(item => item !== "...");
				case VALUE_TYPE_ARRAY_EXTEND: {
					const newArray = [];
					for (const item of b) {
						if (item === "...") {
							for (const item of a) {
								newArray.push(item);
							}
						} else {
							newArray.push(item);
						}
					}
					return newArray;
				}
				case VALUE_TYPE_OBJECT:
					return b.map(item => (item === "..." ? a : item));
				default:
					throw new Error("Not implemented");
			}
		default:
			throw new Error("Not implemented");
	}
};

/**
 * @template {object} T
 * @param {T} obj the object
 * @param {(keyof T)[]=} keysToKeepOriginalValue keys to keep original value
 * @returns {T} the object without operations like "..." or DELETE
 */
const removeOperations = (obj, keysToKeepOriginalValue = []) => {
	const newObj = /** @type {T} */ ({});
	for (const key of Object.keys(obj)) {
		const value = obj[/** @type {keyof T} */ (key)];
		const type = getValueType(value);
		if (
			type === VALUE_TYPE_OBJECT &&
			keysToKeepOriginalValue.includes(/** @type {keyof T} */ (key))
		) {
			newObj[/** @type {keyof T} */ (key)] = value;
			continue;
		}
		switch (type) {
			case VALUE_TYPE_UNDEFINED:
			case VALUE_TYPE_DELETE:
				break;
			case VALUE_TYPE_OBJECT:
				newObj[key] = removeOperations(
					/** @type {TODO} */ (value),
					keysToKeepOriginalValue
				);
				break;
			case VALUE_TYPE_ARRAY_EXTEND:
				newObj[key] =
					/** @type {any[]} */
					(value).filter(i => i !== "...");
				break;
			default:
				newObj[/** @type {keyof T} */ (key)] = value;
				break;
		}
	}
	return newObj;
};

/**
 * @template T
 * @template {string} P
 * @param {T} obj the object
 * @param {P} byProperty the by description
 * @param  {...any} values values
 * @returns {Omit<T, P>} object with merged byProperty
 */
const resolveByProperty = (obj, byProperty, ...values) => {
	if (typeof obj !== "object" || obj === null || !(byProperty in obj)) {
		return obj;
	}
	const { [byProperty]: _byValue, ..._remaining } = /** @type {object} */ (obj);
	const remaining = /** @type {T} */ (_remaining);
	const byValue = /** @type {Record<string, T> | function(...any[]): T} */ (
		_byValue
	);
	if (typeof byValue === "object") {
		const key = values[0];
		if (key in byValue) {
			return cachedCleverMerge(remaining, byValue[key]);
		} else if ("default" in byValue) {
			return cachedCleverMerge(remaining, byValue.default);
		} else {
			return /** @type {T} */ (remaining);
		}
	} else if (typeof byValue === "function") {
		const result = byValue.apply(null, values);
		return cachedCleverMerge(
			remaining,
			resolveByProperty(result, byProperty, ...values)
		);
	}
};

exports.cachedSetProperty = cachedSetProperty;
exports.cachedCleverMerge = cachedCleverMerge;
exports.cleverMerge = cleverMerge;
exports.resolveByProperty = resolveByProperty;
exports.removeOperations = removeOperations;
exports.DELETE = DELETE;


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

"use strict";

const { compareRuntime } = require("./runtime");

/** @typedef {import("../Chunk")} Chunk */
/** @typedef {import("../Chunk").ChunkId} ChunkId */
/** @typedef {import("../ChunkGraph")} ChunkGraph */
/** @typedef {import("../ChunkGroup")} ChunkGroup */
/** @typedef {import("../Dependency").DependencyLocation} DependencyLocation */
/** @typedef {import("../Module")} Module */
/** @typedef {import("../ModuleGraph")} ModuleGraph */

/** @template T @typedef {function(T, T): -1|0|1} Comparator */
/** @template TArg @template T @typedef {function(TArg, T, T): -1|0|1} RawParameterizedComparator */
/** @template TArg @template T @typedef {function(TArg): Comparator<T>} ParameterizedComparator */

/**
 * @template T
 * @param {RawParameterizedComparator<any, T>} fn comparator with argument
 * @returns {ParameterizedComparator<any, T>} comparator
 */
const createCachedParameterizedComparator = fn => {
	/** @type {WeakMap<object, Comparator<T>>} */
	const map = new WeakMap();
	return arg => {
		const cachedResult = map.get(arg);
		if (cachedResult !== undefined) return cachedResult;
		/**
		 * @param {T} a first item
		 * @param {T} b second item
		 * @returns {-1|0|1} compare result
		 */
		const result = fn.bind(null, arg);
		map.set(arg, result);
		return result;
	};
};

/**
 * @param {Chunk} a chunk
 * @param {Chunk} b chunk
 * @returns {-1|0|1} compare result
 */
exports.compareChunksById = (a, b) => {
	return compareIds(
		/** @type {ChunkId} */ (a.id),
		/** @type {ChunkId} */ (b.id)
	);
};

/**
 * @param {Module} a module
 * @param {Module} b module
 * @returns {-1|0|1} compare result
 */
exports.compareModulesByIdentifier = (a, b) => {
	return compareIds(a.identifier(), b.identifier());
};

/**
 * @param {ChunkGraph} chunkGraph the chunk graph
 * @param {Module} a module
 * @param {Module} b module
 * @returns {-1|0|1} compare result
 */
const compareModulesById = (chunkGraph, a, b) => {
	return compareIds(chunkGraph.getModuleId(a), chunkGraph.getModuleId(b));
};
/** @type {ParameterizedComparator<ChunkGraph, Module>} */
exports.compareModulesById =
	createCachedParameterizedComparator(compareModulesById);

/**
 * @param {number} a number
 * @param {number} b number
 * @returns {-1|0|1} compare result
 */
const compareNumbers = (a, b) => {
	if (typeof a !== typeof b) {
		return typeof a < typeof b ? -1 : 1;
	}
	if (a < b) return -1;
	if (a > b) return 1;
	return 0;
};
exports.compareNumbers = compareNumbers;

/**
 * @param {string} a string
 * @param {string} b string
 * @returns {-1|0|1} compare result
 */
const compareStringsNumeric = (a, b) => {
	const aLength = a.length;
	const bLength = b.length;

	let aChar = 0;
	let bChar = 0;

	let aIsDigit = false;
	let bIsDigit = false;
	let i = 0;
	let j = 0;
	while (i < aLength && j < bLength) {
		aChar = a.charCodeAt(i);
		bChar = b.charCodeAt(j);

		aIsDigit = aChar >= 48 && aChar <= 57;
		bIsDigit = bChar >= 48 && bChar <= 57;

		if (!aIsDigit && !bIsDigit) {
			if (aChar < bChar) return -1;
			if (aChar > bChar) return 1;
			i++;
			j++;
		} else if (aIsDigit && !bIsDigit) {
			// This segment of a is shorter than in b
			return 1;
		} else if (!aIsDigit && bIsDigit) {
			// This segment of b is shorter than in a
			return -1;
		} else {
			let aNumber = aChar - 48;
			let bNumber = bChar - 48;

			while (++i < aLength) {
				aChar = a.charCodeAt(i);
				if (aChar < 48 || aChar > 57) break;
				aNumber = aNumber * 10 + aChar - 48;
			}

			while (++j < bLength) {
				bChar = b.charCodeAt(j);
				if (bChar < 48 || bChar > 57) break;
				bNumber = bNumber * 10 + bChar - 48;
			}

			if (aNumber < bNumber) return -1;
			if (aNumber > bNumber) return 1;
		}
	}

	if (j < bLength) {
		// a is shorter than b
		bChar = b.charCodeAt(j);
		bIsDigit = bChar >= 48 && bChar <= 57;
		return bIsDigit ? -1 : 1;
	}
	if (i < aLength) {
		// b is shorter than a
		aChar = a.charCodeAt(i);
		aIsDigit = aChar >= 48 && aChar <= 57;
		return aIsDigit ? 1 : -1;
	}

	return 0;
};
exports.compareStringsNumeric = compareStringsNumeric;

/**
 * @param {ModuleGraph} moduleGraph the module graph
 * @param {Module} a module
 * @param {Module} b module
 * @returns {-1|0|1} compare result
 */
const compareModulesByPostOrderIndexOrIdentifier = (moduleGraph, a, b) => {
	const cmp = compareNumbers(
		/** @type {number} */ (moduleGraph.getPostOrderIndex(a)),
		/** @type {number} */ (moduleGraph.getPostOrderIndex(b))
	);
	if (cmp !== 0) return cmp;
	return compareIds(a.identifier(), b.identifier());
};
/** @type {ParameterizedComparator<ModuleGraph, Module>} */
exports.compareModulesByPostOrderIndexOrIdentifier =
	createCachedParameterizedComparator(
		compareModulesByPostOrderIndexOrIdentifier
	);

/**
 * @param {ModuleGraph} moduleGraph the module graph
 * @param {Module} a module
 * @param {Module} b module
 * @returns {-1|0|1} compare result
 */
const compareModulesByPreOrderIndexOrIdentifier = (moduleGraph, a, b) => {
	const cmp = compareNumbers(
		/** @type {number} */ (moduleGraph.getPreOrderIndex(a)),
		/** @type {number} */ (moduleGraph.getPreOrderIndex(b))
	);
	if (cmp !== 0) return cmp;
	return compareIds(a.identifier(), b.identifier());
};
/** @type {ParameterizedComparator<ModuleGraph, Module>} */
exports.compareModulesByPreOrderIndexOrIdentifier =
	createCachedParameterizedComparator(
		compareModulesByPreOrderIndexOrIdentifier
	);

/**
 * @param {ChunkGraph} chunkGraph the chunk graph
 * @param {Module} a module
 * @param {Module} b module
 * @returns {-1|0|1} compare result
 */
const compareModulesByIdOrIdentifier = (chunkGraph, a, b) => {
	const cmp = compareIds(chunkGraph.getModuleId(a), chunkGraph.getModuleId(b));
	if (cmp !== 0) return cmp;
	return compareIds(a.identifier(), b.identifier());
};
/** @type {ParameterizedComparator<ChunkGraph, Module>} */
exports.compareModulesByIdOrIdentifier = createCachedParameterizedComparator(
	compareModulesByIdOrIdentifier
);

/**
 * @param {ChunkGraph} chunkGraph the chunk graph
 * @param {Chunk} a chunk
 * @param {Chunk} b chunk
 * @returns {-1|0|1} compare result
 */
const compareChunks = (chunkGraph, a, b) => {
	return chunkGraph.compareChunks(a, b);
};
/** @type {ParameterizedComparator<ChunkGraph, Chunk>} */
exports.compareChunks = createCachedParameterizedComparator(compareChunks);

/**
 * @param {string|number} a first id
 * @param {string|number} b second id
 * @returns {-1|0|1} compare result
 */
const compareIds = (a, b) => {
	if (typeof a !== typeof b) {
		return typeof a < typeof b ? -1 : 1;
	}
	if (a < b) return -1;
	if (a > b) return 1;
	return 0;
};

exports.compareIds = compareIds;

/**
 * @param {string} a first string
 * @param {string} b second string
 * @returns {-1|0|1} compare result
 */
const compareStrings = (a, b) => {
	if (a < b) return -1;
	if (a > b) return 1;
	return 0;
};

exports.compareStrings = compareStrings;

/**
 * @param {ChunkGroup} a first chunk group
 * @param {ChunkGroup} b second chunk group
 * @returns {-1|0|1} compare result
 */
const compareChunkGroupsByIndex = (a, b) => {
	return /** @type {number} */ (a.index) < /** @type {number} */ (b.index)
		? -1
		: 1;
};

exports.compareChunkGroupsByIndex = compareChunkGroupsByIndex;

/**
 * @template K1 {Object}
 * @template K2
 * @template T
 */
class TwoKeyWeakMap {
	constructor() {
		/**
		 * @private
		 * @type {WeakMap<any, WeakMap<any, T | undefined>>}
		 */
		this._map = new WeakMap();
	}

	/**
	 * @param {K1} key1 first key
	 * @param {K2} key2 second key
	 * @returns {T | undefined} value
	 */
	get(key1, key2) {
		const childMap = this._map.get(key1);
		if (childMap === undefined) {
			return undefined;
		}
		return childMap.get(key2);
	}

	/**
	 * @param {K1} key1 first key
	 * @param {K2} key2 second key
	 * @param {T | undefined} value new value
	 * @returns {void}
	 */
	set(key1, key2, value) {
		let childMap = this._map.get(key1);
		if (childMap === undefined) {
			childMap = new WeakMap();
			this._map.set(key1, childMap);
		}
		childMap.set(key2, value);
	}
}

/** @type {TwoKeyWeakMap<Comparator<any>, Comparator<any>, Comparator<any>>}} */
const concatComparatorsCache = new TwoKeyWeakMap();

/**
 * @template T
 * @param {Comparator<T>} c1 comparator
 * @param {Comparator<T>} c2 comparator
 * @param {Comparator<T>[]} cRest comparators
 * @returns {Comparator<T>} comparator
 */
const concatComparators = (c1, c2, ...cRest) => {
	if (cRest.length > 0) {
		const [c3, ...cRest2] = cRest;
		return concatComparators(c1, concatComparators(c2, c3, ...cRest2));
	}
	const cacheEntry = /** @type {Comparator<T>} */ (
		concatComparatorsCache.get(c1, c2)
	);
	if (cacheEntry !== undefined) return cacheEntry;
	/**
	 * @param {T} a first value
	 * @param {T} b second value
	 * @returns {-1|0|1} compare result
	 */
	const result = (a, b) => {
		const res = c1(a, b);
		if (res !== 0) return res;
		return c2(a, b);
	};
	concatComparatorsCache.set(c1, c2, result);
	return result;
};
exports.concatComparators = concatComparators;

/**
 * @template A, B
 * @typedef {(input: A) => B | undefined | null} Selector
 */

/** @type {TwoKeyWeakMap<Selector<any, any>, Comparator<any>, Comparator<any>>}} */
const compareSelectCache = new TwoKeyWeakMap();

/**
 * @template T
 * @template R
 * @param {Selector<T, R>} getter getter for value
 * @param {Comparator<R>} comparator comparator
 * @returns {Comparator<T>} comparator
 */
const compareSelect = (getter, comparator) => {
	const cacheEntry = compareSelectCache.get(getter, comparator);
	if (cacheEntry !== undefined) return cacheEntry;
	/**
	 * @param {T} a first value
	 * @param {T} b second value
	 * @returns {-1|0|1} compare result
	 */
	const result = (a, b) => {
		const aValue = getter(a);
		const bValue = getter(b);
		if (aValue !== undefined && aValue !== null) {
			if (bValue !== undefined && bValue !== null) {
				return comparator(aValue, bValue);
			}
			return -1;
		} else {
			if (bValue !== undefined && bValue !== null) {
				return 1;
			}
			return 0;
		}
	};
	compareSelectCache.set(getter, comparator, result);
	return result;
};
exports.compareSelect = compareSelect;

/** @type {WeakMap<Comparator<any>, Comparator<Iterable<any>>>} */
const compareIteratorsCache = new WeakMap();

/**
 * @template T
 * @param {Comparator<T>} elementComparator comparator for elements
 * @returns {Comparator<Iterable<T>>} comparator for iterables of elements
 */
const compareIterables = elementComparator => {
	const cacheEntry = compareIteratorsCache.get(elementComparator);
	if (cacheEntry !== undefined) return cacheEntry;
	/**
	 * @param {Iterable<T>} a first value
	 * @param {Iterable<T>} b second value
	 * @returns {-1|0|1} compare result
	 */
	const result = (a, b) => {
		const aI = a[Symbol.iterator]();
		const bI = b[Symbol.iterator]();
		while (true) {
			const aItem = aI.next();
			const bItem = bI.next();
			if (aItem.done) {
				return bItem.done ? 0 : -1;
			} else if (bItem.done) {
				return 1;
			}
			const res = elementComparator(aItem.value, bItem.value);
			if (res !== 0) return res;
		}
	};
	compareIteratorsCache.set(elementComparator, result);
	return result;
};
exports.compareIterables = compareIterables;

// TODO this is no longer needed when minimum node.js version is >= 12
// since these versions ship with a stable sort function
/**
 * @template T
 * @param {Iterable<T>} iterable original ordered list
 * @returns {Comparator<T>} comparator
 */
exports.keepOriginalOrder = iterable => {
	/** @type {Map<T, number>} */
	const map = new Map();
	let i = 0;
	for (const item of iterable) {
		map.set(item, i++);
	}
	return (a, b) =>
		compareNumbers(
			/** @type {number} */ (map.get(a)),
			/** @type {number} */ (map.get(b))
		);
};

/**
 * @param {ChunkGraph} chunkGraph the chunk graph
 * @returns {Comparator<Chunk>} comparator
 */
exports.compareChunksNatural = chunkGraph => {
	const cmpFn = exports.compareModulesById(chunkGraph);
	const cmpIterableFn = compareIterables(cmpFn);
	return concatComparators(
		compareSelect(
			chunk => /** @type {string|number} */ (chunk.name),
			compareIds
		),
		compareSelect(chunk => chunk.runtime, compareRuntime),
		compareSelect(
			/**
			 * @param {Chunk} chunk a chunk
			 * @returns {Iterable<Module>} modules
			 */
			chunk => chunkGraph.getOrderedChunkModulesIterable(chunk, cmpFn),
			cmpIterableFn
		)
	);
};

/**
 * Compare two locations
 * @param {DependencyLocation} a A location node
 * @param {DependencyLocation} b A location node
 * @returns {-1|0|1} sorting comparator value
 */
exports.compareLocations = (a, b) => {
	let isObjectA = typeof a === "object" && a !== null;
	let isObjectB = typeof b === "object" && b !== null;
	if (!isObjectA || !isObjectB) {
		if (isObjectA) return 1;
		if (isObjectB) return -1;
		return 0;
	}
	if ("start" in a) {
		if ("start" in b) {
			const ap = a.start;
			const bp = b.start;
			if (ap.line < bp.line) return -1;
			if (ap.line > bp.line) return 1;
			if (/** @type {number} */ (ap.column) < /** @type {number} */ (bp.column))
				return -1;
			if (/** @type {number} */ (ap.column) > /** @type {number} */ (bp.column))
				return 1;
		} else return -1;
	} else if ("start" in b) return 1;
	if ("name" in a) {
		if ("name" in b) {
			if (a.name < b.name) return -1;
			if (a.name > b.name) return 1;
		} else return -1;
	} else if ("name" in b) return 1;
	if ("index" in a) {
		if ("index" in b) {
			if (/** @type {number} */ (a.index) < /** @type {number} */ (b.index))
				return -1;
			if (/** @type {number} */ (a.index) > /** @type {number} */ (b.index))
				return 1;
		} else return -1;
	} else if ("index" in b) return 1;
	return 0;
};


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

"use strict";

/**
 * @param {string} str string
 * @returns {string} quoted meta
 */
const quoteMeta = str => {
	return str.replace(/[-[\]\\/{}()*+?.^$|]/g, "\\$&");
};

/**
 * @param {string} str string
 * @returns {string} string
 */
const toSimpleString = str => {
	if (`${+str}` === str) {
		return str;
	}
	return JSON.stringify(str);
};

/**
 * @param {Record<string|number, boolean>} map value map
 * @returns {boolean|(function(string): string)} true/false, when unconditionally true/false, or a template function to determine the value at runtime
 */
const compileBooleanMatcher = map => {
	const positiveItems = Object.keys(map).filter(i => map[i]);
	const negativeItems = Object.keys(map).filter(i => !map[i]);
	if (positiveItems.length === 0) return false;
	if (negativeItems.length === 0) return true;
	return compileBooleanMatcherFromLists(positiveItems, negativeItems);
};

/**
 * @param {string[]} positiveItems positive items
 * @param {string[]} negativeItems negative items
 * @returns {function(string): string} a template function to determine the value at runtime
 */
const compileBooleanMatcherFromLists = (positiveItems, negativeItems) => {
	if (positiveItems.length === 0) return () => "false";
	if (negativeItems.length === 0) return () => "true";
	if (positiveItems.length === 1)
		return value => `${toSimpleString(positiveItems[0])} == ${value}`;
	if (negativeItems.length === 1)
		return value => `${toSimpleString(negativeItems[0])} != ${value}`;
	const positiveRegexp = itemsToRegexp(positiveItems);
	const negativeRegexp = itemsToRegexp(negativeItems);
	if (positiveRegexp.length <= negativeRegexp.length) {
		return value => `/^${positiveRegexp}$/.test(${value})`;
	} else {
		return value => `!/^${negativeRegexp}$/.test(${value})`;
	}
};

/**
 * @param {Set<string>} itemsSet items set
 * @param {(str: string) => string | false} getKey get key function
 * @param {(str: Array<string>) => boolean} condition condition
 * @returns {Array<Array<string>>} list of common items
 */
const popCommonItems = (itemsSet, getKey, condition) => {
	/** @type {Map<string, Array<string>>} */
	const map = new Map();
	for (const item of itemsSet) {
		const key = getKey(item);
		if (key) {
			let list = map.get(key);
			if (list === undefined) {
				/** @type {Array<string>} */
				list = [];
				map.set(key, list);
			}
			list.push(item);
		}
	}
	/** @type {Array<Array<string>>} */
	const result = [];
	for (const list of map.values()) {
		if (condition(list)) {
			for (const item of list) {
				itemsSet.delete(item);
			}
			result.push(list);
		}
	}
	return result;
};

/**
 * @param {Array<string>} items items
 * @returns {string} common prefix
 */
const getCommonPrefix = items => {
	let prefix = items[0];
	for (let i = 1; i < items.length; i++) {
		const item = items[i];
		for (let p = 0; p < prefix.length; p++) {
			if (item[p] !== prefix[p]) {
				prefix = prefix.slice(0, p);
				break;
			}
		}
	}
	return prefix;
};

/**
 * @param {Array<string>} items items
 * @returns {string} common suffix
 */
const getCommonSuffix = items => {
	let suffix = items[0];
	for (let i = 1; i < items.length; i++) {
		const item = items[i];
		for (let p = item.length - 1, s = suffix.length - 1; s >= 0; p--, s--) {
			if (item[p] !== suffix[s]) {
				suffix = suffix.slice(s + 1);
				break;
			}
		}
	}
	return suffix;
};

/**
 * @param {Array<string>} itemsArr array of items
 * @returns {string} regexp
 */
const itemsToRegexp = itemsArr => {
	if (itemsArr.length === 1) {
		return quoteMeta(itemsArr[0]);
	}
	/** @type {Array<string>} */
	const finishedItems = [];

	// merge single char items: (a|b|c|d|ef) => ([abcd]|ef)
	let countOfSingleCharItems = 0;
	for (const item of itemsArr) {
		if (item.length === 1) {
			countOfSingleCharItems++;
		}
	}
	// special case for only single char items
	if (countOfSingleCharItems === itemsArr.length) {
		return `[${quoteMeta(itemsArr.sort().join(""))}]`;
	}
	const items = new Set(itemsArr.sort());
	if (countOfSingleCharItems > 2) {
		let singleCharItems = "";
		for (const item of items) {
			if (item.length === 1) {
				singleCharItems += item;
				items.delete(item);
			}
		}
		finishedItems.push(`[${quoteMeta(singleCharItems)}]`);
	}

	// special case for 2 items with common prefix/suffix
	if (finishedItems.length === 0 && items.size === 2) {
		const prefix = getCommonPrefix(itemsArr);
		const suffix = getCommonSuffix(
			itemsArr.map(item => item.slice(prefix.length))
		);
		if (prefix.length > 0 || suffix.length > 0) {
			return `${quoteMeta(prefix)}${itemsToRegexp(
				itemsArr.map(i => i.slice(prefix.length, -suffix.length || undefined))
			)}${quoteMeta(suffix)}`;
		}
	}

	// special case for 2 items with common suffix
	if (finishedItems.length === 0 && items.size === 2) {
		/** @type {Iterator<string>} */
		const it = items[Symbol.iterator]();
		const a = it.next().value;
		const b = it.next().value;
		if (a.length > 0 && b.length > 0 && a.slice(-1) === b.slice(-1)) {
			return `${itemsToRegexp([a.slice(0, -1), b.slice(0, -1)])}${quoteMeta(
				a.slice(-1)
			)}`;
		}
	}

	// find common prefix: (a1|a2|a3|a4|b5) => (a(1|2|3|4)|b5)
	const prefixed = popCommonItems(
		items,
		item => (item.length >= 1 ? item[0] : false),
		list => {
			if (list.length >= 3) return true;
			if (list.length <= 1) return false;
			return list[0][1] === list[1][1];
		}
	);
	for (const prefixedItems of prefixed) {
		const prefix = getCommonPrefix(prefixedItems);
		finishedItems.push(
			`${quoteMeta(prefix)}${itemsToRegexp(
				prefixedItems.map(i => i.slice(prefix.length))
			)}`
		);
	}

	// find common suffix: (a1|b1|c1|d1|e2) => ((a|b|c|d)1|e2)
	const suffixed = popCommonItems(
		items,
		item => (item.length >= 1 ? item.slice(-1) : false),
		list => {
			if (list.length >= 3) return true;
			if (list.length <= 1) return false;
			return list[0].slice(-2) === list[1].slice(-2);
		}
	);
	for (const suffixedItems of suffixed) {
		const suffix = getCommonSuffix(suffixedItems);
		finishedItems.push(
			`${itemsToRegexp(
				suffixedItems.map(i => i.slice(0, -suffix.length))
			)}${quoteMeta(suffix)}`
		);
	}

	// TODO further optimize regexp, i. e.
	// use ranges: (1|2|3|4|a) => [1-4a]
	const conditional = finishedItems.concat(Array.from(items, quoteMeta));
	if (conditional.length === 1) return conditional[0];
	return `(${conditional.join("|")})`;
};

compileBooleanMatcher.fromLists = compileBooleanMatcherFromLists;
compileBooleanMatcher.itemsToRegexp = itemsToRegexp;
module.exports = compileBooleanMatcher;


code:
/*
	MIT License http://www.opensource.org/licenses/mit-license.php
	Author Gengkun He @ahabhgk
*/

"use strict";

/** @typedef {import("../../declarations/WebpackOptions").CssGeneratorExportsConvention} CssGeneratorExportsConvention */

/**
 * @param {string} input input
 * @param {CssGeneratorExportsConvention | undefined} convention convention
 * @returns {Set<string>} results
 */
exports.cssExportConvention = (input, convention) => {
	const set = new Set();
	if (typeof convention === "function") {
		set.add(convention(input));
	} else {
		switch (convention) {
			case "camel-case": {
				set.add(input);
				set.add(exports.camelCase(input));
				break;
			}
			case "camel-case-only": {
				set.add(exports.camelCase(input));
				break;
			}
			case "dashes": {
				set.add(input);
				set.add(exports.dashesCamelCase(input));
				break;
			}
			case "dashes-only": {
				set.add(exports.dashesCamelCase(input));
				break;
			}
			case "as-is": {
				set.add(input);
				break;
			}
		}
	}
	return set;
};

// Copy from css-loader
/**
 * @param {string} input input
 * @returns {string} result
 */
exports.dashesCamelCase = input => {
	return input.replace(/-+(\w)/g, (match, firstLetter) =>
		firstLetter.toUpperCase()
	);
};

// Copy from css-loader
/**
 * @param {string} input input
 * @returns {string} result
 */
exports.camelCase = input => {
	let result = input.trim();

	if (result.length === 0) {
		return "";
	}

	if (result.length === 1) {
		return result.toLowerCase();
	}

	const hasUpperCase = result !== result.toLowerCase();

	if (hasUpperCase) {
		result = preserveCamelCase(result);
	}

	return result
		.replace(/^[_.\- ]+/, "")
		.toLowerCase()
		.replace(/[_.\- ]+([\p{Alpha}\p{N}_]|$)/gu, (_, p1) => p1.toUpperCase())
		.replace(/\d+([\p{Alpha}\p{N}_]|$)/gu, m => m.toUpperCase());
};

// Copy from css-loader
/**
 * @param {string} string string
 * @returns {string} result
 */
const preserveCamelCase = string => {
	let result = string;
	let isLastCharLower = false;
	let isLastCharUpper = false;
	let isLastLastCharUpper = false;

	for (let i = 0; i < result.length; i++) {
		const character = result[i];

		if (isLastCharLower && /[\p{Lu}]/u.test(character)) {
			result = `${result.slice(0, i)}-${result.slice(i)}`;
			isLastCharLower = false;
			isLastLastCharUpper = isLastCharUpper;
			isLastCharUpper = true;
			i += 1;
		} else if (
			isLastCharUpper &&
			isLastLastCharUpper &&
			/[\p{Ll}]/u.test(character)
		) {
			result = `${result.slice(0, i - 1)}-${result.slice(i - 1)}`;
			isLastLastCharUpper = isLastCharUpper;
			isLastCharUpper = false;
			isLastCharLower = true;
		} else {
			isLastCharLower =
				character.toLowerCase() === character &&
				character.toUpperCase() !== character;
			isLastLastCharUpper = isLastCharUpper;
			isLastCharUpper =
				character.toUpperCase() === character &&
				character.toLowerCase() !== character;
		}
	}

	return result;
};


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

"use strict";

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

const getValidate = memoize(() => require("schema-utils").validate);

const createSchemaValidation = (check, getSchema, options) => {
	getSchema = memoize(getSchema);
	return value => {
		if (check && !check(value)) {
			getValidate()(getSchema(), value, options);
			if (check) {
				require("util").deprecate(
					() => {},
					"webpack bug: Pre-compiled schema reports error while real schema is happy. This has performance drawbacks.",
					"DEP_WEBPACK_PRE_COMPILED_SCHEMA_INVALID"
				)();
			}
		}
	};
};

module.exports = createSchemaValidation;


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

"use strict";

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

const BULK_SIZE = 2000;

// We are using an object instead of a Map as this will stay static during the runtime
// so access to it can be optimized by v8
/** @type {{[key: string]: Map<string, string>}} */
const digestCaches = {};

/** @typedef {function(): Hash} HashFactory */

class BulkUpdateDecorator extends Hash {
	/**
	 * @param {Hash | HashFactory} hashOrFactory function to create a hash
	 * @param {string=} hashKey key for caching
	 */
	constructor(hashOrFactory, hashKey) {
		super();
		this.hashKey = hashKey;
		if (typeof hashOrFactory === "function") {
			this.hashFactory = hashOrFactory;
			this.hash = undefined;
		} else {
			this.hashFactory = undefined;
			this.hash = hashOrFactory;
		}
		this.buffer = "";
	}

	/**
	 * Update hash {@link https://nodejs.org/api/crypto.html#crypto_hash_update_data_inputencoding}
	 * @param {string|Buffer} data data
	 * @param {string=} inputEncoding data encoding
	 * @returns {this} updated hash
	 */
	update(data, inputEncoding) {
		if (
			inputEncoding !== undefined ||
			typeof data !== "string" ||
			data.length > BULK_SIZE
		) {
			if (this.hash === undefined)
				this.hash = /** @type {HashFactory} */ (this.hashFactory)();
			if (this.buffer.length > 0) {
				this.hash.update(this.buffer);
				this.buffer = "";
			}
			this.hash.update(data, inputEncoding);
		} else {
			this.buffer += data;
			if (this.buffer.length > BULK_SIZE) {
				if (this.hash === undefined)
					this.hash = /** @type {HashFactory} */ (this.hashFactory)();
				this.hash.update(this.buffer);
				this.buffer = "";
			}
		}
		return this;
	}

	/**
	 * Calculates the digest {@link https://nodejs.org/api/crypto.html#crypto_hash_digest_encoding}
	 * @param {string=} encoding encoding of the return value
	 * @returns {string|Buffer} digest
	 */
	digest(encoding) {
		let digestCache;
		const buffer = this.buffer;
		if (this.hash === undefined) {
			// short data for hash, we can use caching
			const cacheKey = `${this.hashKey}-${encoding}`;
			digestCache = digestCaches[cacheKey];
			if (digestCache === undefined) {
				digestCache = digestCaches[cacheKey] = new Map();
			}
			const cacheEntry = digestCache.get(buffer);
			if (cacheEntry !== undefined) return cacheEntry;
			this.hash = /** @type {HashFactory} */ (this.hashFactory)();
		}
		if (buffer.length > 0) {
			this.hash.update(buffer);
		}
		const digestResult = this.hash.digest(encoding);
		const result =
			typeof digestResult === "string" ? digestResult : digestResult.toString();
		if (digestCache !== undefined) {
			digestCache.set(buffer, result);
		}
		return result;
	}
}

/* istanbul ignore next */
class DebugHash extends Hash {
	constructor() {
		super();
		this.string = "";
	}

	/**
	 * Update hash {@link https://nodejs.org/api/crypto.html#crypto_hash_update_data_inputencoding}
	 * @param {string|Buffer} data data
	 * @param {string=} inputEncoding data encoding
	 * @returns {this} updated hash
	 */
	update(data, inputEncoding) {
		if (typeof data !== "string") data = data.toString("utf-8");
		const prefix = Buffer.from("@webpack-debug-digest@").toString("hex");
		if (data.startsWith(prefix)) {
			data = Buffer.from(data.slice(prefix.length), "hex").toString();
		}
		this.string += `[${data}](${
			/** @type {string} */ (new Error().stack).split("\n", 3)[2]
		})\n`;
		return this;
	}

	/**
	 * Calculates the digest {@link https://nodejs.org/api/crypto.html#crypto_hash_digest_encoding}
	 * @param {string=} encoding encoding of the return value
	 * @returns {string|Buffer} digest
	 */
	digest(encoding) {
		return Buffer.from("@webpack-debug-digest@" + this.string).toString("hex");
	}
}

/** @type {typeof import("crypto") | undefined} */
let crypto = undefined;
/** @type {typeof import("./hash/xxhash64") | undefined} */
let createXXHash64 = undefined;
/** @type {typeof import("./hash/md4") | undefined} */
let createMd4 = undefined;
/** @type {typeof import("./hash/BatchedHash") | undefined} */
let BatchedHash = undefined;

/**
 * Creates a hash by name or function
 * @param {string | typeof Hash} algorithm the algorithm name or a constructor creating a hash
 * @returns {Hash} the hash
 */
module.exports = algorithm => {
	if (typeof algorithm === "function") {
		return new BulkUpdateDecorator(() => new algorithm());
	}
	switch (algorithm) {
		// TODO add non-cryptographic algorithm here
		case "debug":
			return new DebugHash();
		case "xxhash64":
			if (createXXHash64 === undefined) {
				createXXHash64 = require("./hash/xxhash64");
				if (BatchedHash === undefined) {
					BatchedHash = require("./hash/BatchedHash");
				}
			}
			return new /** @type {typeof import("./hash/BatchedHash")} */ (
				BatchedHash
			)(createXXHash64());
		case "md4":
			if (createMd4 === undefined) {
				createMd4 = require("./hash/md4");
				if (BatchedHash === undefined) {
					BatchedHash = require("./hash/BatchedHash");
				}
			}
			return new /** @type {typeof import("./hash/BatchedHash")} */ (
				BatchedHash
			)(createMd4());
		case "native-md4":
			if (crypto === undefined) crypto = require("crypto");
			return new BulkUpdateDecorator(
				() => /** @type {typeof import("crypto")} */ (crypto).createHash("md4"),
				"md4"
			);
		default:
			if (crypto === undefined) crypto = require("crypto");
			return new BulkUpdateDecorator(
				() =>
					/** @type {typeof import("crypto")} */ (crypto).createHash(algorithm),
				algorithm
			);
	}
};


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

"use strict";

const util = require("util");

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

/**
 * @typedef {object} FakeHookMarker
 * @property {true} _fakeHook it's a fake hook
 */

/** @template T @typedef {T & FakeHookMarker} FakeHook<T> */

/**
 * @param {string} message deprecation message
 * @param {string} code deprecation code
 * @returns {Function} function to trigger deprecation
 */
const createDeprecation = (message, code) => {
	const cached = deprecationCache.get(message);
	if (cached !== undefined) return cached;
	const fn = util.deprecate(
		() => {},
		message,
		"DEP_WEBPACK_DEPRECATION_" + code
	);
	deprecationCache.set(message, fn);
	return fn;
};

const COPY_METHODS = [
	"concat",
	"entry",
	"filter",
	"find",
	"findIndex",
	"includes",
	"indexOf",
	"join",
	"lastIndexOf",
	"map",
	"reduce",
	"reduceRight",
	"slice",
	"some"
];

const DISABLED_METHODS = [
	"copyWithin",
	"entries",
	"fill",
	"keys",
	"pop",
	"reverse",
	"shift",
	"splice",
	"sort",
	"unshift"
];

/**
 * @param {any} set new set
 * @param {string} name property name
 * @returns {void}
 */
exports.arrayToSetDeprecation = (set, name) => {
	for (const method of COPY_METHODS) {
		if (set[method]) continue;
		const d = createDeprecation(
			`${name} was changed from Array to Set (using Array method '${method}' is deprecated)`,
			"ARRAY_TO_SET"
		);
		/**
		 * @deprecated
		 * @this {Set<any>}
		 * @returns {number} count
		 */
		set[method] = function () {
			d();
			const array = Array.from(this);
			return Array.prototype[method].apply(array, arguments);
		};
	}
	const dPush = createDeprecation(
		`${name} was changed from Array to Set (using Array method 'push' is deprecated)`,
		"ARRAY_TO_SET_PUSH"
	);
	const dLength = createDeprecation(
		`${name} was changed from Array to Set (using Array property 'length' is deprecated)`,
		"ARRAY_TO_SET_LENGTH"
	);
	const dIndexer = createDeprecation(
		`${name} was changed from Array to Set (indexing Array is deprecated)`,
		"ARRAY_TO_SET_INDEXER"
	);
	/**
	 * @deprecated
	 * @this {Set<any>}
	 * @returns {number} count
	 */
	set.push = function () {
		dPush();
		for (const item of Array.from(arguments)) {
			this.add(item);
		}
		return this.size;
	};
	for (const method of DISABLED_METHODS) {
		if (set[method]) continue;
		set[method] = () => {
			throw new Error(
				`${name} was changed from Array to Set (using Array method '${method}' is not possible)`
			);
		};
	}
	/**
	 * @param {number} index index
	 * @returns {any} value
	 */
	const createIndexGetter = index => {
		/**
		 * @this {Set<any>} a Set
		 * @returns {any} the value at this location
		 */
		const fn = function () {
			dIndexer();
			let i = 0;
			for (const item of this) {
				if (i++ === index) return item;
			}
			return undefined;
		};
		return fn;
	};
	/**
	 * @param {number} index index
	 */
	const defineIndexGetter = index => {
		Object.defineProperty(set, index, {
			get: createIndexGetter(index),
			set(value) {
				throw new Error(
					`${name} was changed from Array to Set (indexing Array with write is not possible)`
				);
			}
		});
	};
	defineIndexGetter(0);
	let indexerDefined = 1;
	Object.defineProperty(set, "length", {
		get() {
			dLength();
			const length = this.size;
			for (indexerDefined; indexerDefined < length + 1; indexerDefined++) {
				defineIndexGetter(indexerDefined);
			}
			return length;
		},
		set(value) {
			throw new Error(
				`${name} was changed from Array to Set (writing to Array property 'length' is not possible)`
			);
		}
	});
	set[Symbol.isConcatSpreadable] = true;
};

exports.createArrayToSetDeprecationSet = name => {
	let initialized = false;
	class SetDeprecatedArray extends Set {
		constructor(items) {
			super(items);
			if (!initialized) {
				initialized = true;
				exports.arrayToSetDeprecation(SetDeprecatedArray.prototype, name);
			}
		}
	}
	return SetDeprecatedArray;
};

/**
 * @template T
 * @param {object} obj object
 * @param {string} name property name
 * @param {string} code deprecation code
 * @param {string} note additional note
 * @returns {object} frozen object with deprecation when modifying
 */
exports.soonFrozenObjectDeprecation = (obj, name, code, note = "") => {
	const message = `${name} will be frozen in future, all modifications are deprecated.${
		note && `\n${note}`
	}`;
	return new Proxy(obj, {
		set: util.deprecate(
			(target, property, value, receiver) =>
				Reflect.set(target, property, value, receiver),
			message,
			code
		),
		defineProperty: util.deprecate(
			(target, property, descriptor) =>
				Reflect.defineProperty(target, property, descriptor),
			message,
			code
		),
		deleteProperty: util.deprecate(
			(target, property) => Reflect.deleteProperty(target, property),
			message,
			code
		),
		setPrototypeOf: util.deprecate(
			(target, proto) => Reflect.setPrototypeOf(target, proto),
			message,
			code
		)
	});
};

/**
 * @template T
 * @param {T} obj object
 * @param {string} message deprecation message
 * @param {string} code deprecation code
 * @returns {T} object with property access deprecated
 */
const deprecateAllProperties = (obj, message, code) => {
	const newObj = {};
	const descriptors = Object.getOwnPropertyDescriptors(obj);
	for (const name of Object.keys(descriptors)) {
		const descriptor = descriptors[name];
		if (typeof descriptor.value === "function") {
			Object.defineProperty(newObj, name, {
				...descriptor,
				value: util.deprecate(descriptor.value, message, code)
			});
		} else if (descriptor.get || descriptor.set) {
			Object.defineProperty(newObj, name, {
				...descriptor,
				get: descriptor.get && util.deprecate(descriptor.get, message, code),
				set: descriptor.set && util.deprecate(descriptor.set, message, code)
			});
		} else {
			let value = descriptor.value;
			Object.defineProperty(newObj, name, {
				configurable: descriptor.configurable,
				enumerable: descriptor.enumerable,
				get: util.deprecate(() => value, message, code),
				set: descriptor.writable
					? util.deprecate(v => (value = v), message, code)
					: undefined
			});
		}
	}
	return /** @type {T} */ (newObj);
};
exports.deprecateAllProperties = deprecateAllProperties;

/**
 * @template T
 * @param {T} fakeHook fake hook implementation
 * @param {string=} message deprecation message (not deprecated when unset)
 * @param {string=} code deprecation code (not deprecated when unset)
 * @returns {FakeHook<T>} fake hook which redirects
 */
exports.createFakeHook = (fakeHook, message, code) => {
	if (message && code) {
		fakeHook = deprecateAllProperties(fakeHook, message, code);
	}
	return Object.freeze(
		Object.assign(fakeHook, { _fakeHook: /** @type {true} */ (true) })
	);
};


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

"use strict";

// Simulations show these probabilities for a single change
// 93.1% that one group is invalidated
// 4.8% that two groups are invalidated
// 1.1% that 3 groups are invalidated
// 0.1% that 4 or more groups are invalidated
//
// And these for removing/adding 10 lexically adjacent files
// 64.5% that one group is invalidated
// 24.8% that two groups are invalidated
// 7.8% that 3 groups are invalidated
// 2.7% that 4 or more groups are invalidated
//
// And these for removing/adding 3 random files
// 0% that one group is invalidated
// 3.7% that two groups are invalidated
// 80.8% that 3 groups are invalidated
// 12.3% that 4 groups are invalidated
// 3.2% that 5 or more groups are invalidated

/**
 *
 * @param {string} a key
 * @param {string} b key
 * @returns {number} the similarity as number
 */
const similarity = (a, b) => {
	const l = Math.min(a.length, b.length);
	let dist = 0;
	for (let i = 0; i < l; i++) {
		const ca = a.charCodeAt(i);
		const cb = b.charCodeAt(i);
		dist += Math.max(0, 10 - Math.abs(ca - cb));
	}
	return dist;
};

/**
 * @param {string} a key
 * @param {string} b key
 * @param {Set<string>} usedNames set of already used names
 * @returns {string} the common part and a single char for the difference
 */
const getName = (a, b, usedNames) => {
	const l = Math.min(a.length, b.length);
	let i = 0;
	while (i < l) {
		if (a.charCodeAt(i) !== b.charCodeAt(i)) {
			i++;
			break;
		}
		i++;
	}
	while (i < l) {
		const name = a.slice(0, i);
		const lowerName = name.toLowerCase();
		if (!usedNames.has(lowerName)) {
			usedNames.add(lowerName);
			return name;
		}
		i++;
	}
	// names always contain a hash, so this is always unique
	// we don't need to check usedNames nor add it
	return a;
};

/**
 * @param {Record<string, number>} total total size
 * @param {Record<string, number>} size single size
 * @returns {void}
 */
const addSizeTo = (total, size) => {
	for (const key of Object.keys(size)) {
		total[key] = (total[key] || 0) + size[key];
	}
};

/**
 * @param {Record<string, number>} total total size
 * @param {Record<string, number>} size single size
 * @returns {void}
 */
const subtractSizeFrom = (total, size) => {
	for (const key of Object.keys(size)) {
		total[key] -= size[key];
	}
};

/**
 * @template T
 * @param {Iterable<Node<T>>} nodes some nodes
 * @returns {Record<string, number>} total size
 */
const sumSize = nodes => {
	const sum = Object.create(null);
	for (const node of nodes) {
		addSizeTo(sum, node.size);
	}
	return sum;
};

/**
 * @param {Record<string, number>} size size
 * @param {Record<string, number>} maxSize minimum size
 * @returns {boolean} true, when size is too big
 */
const isTooBig = (size, maxSize) => {
	for (const key of Object.keys(size)) {
		const s = size[key];
		if (s === 0) continue;
		const maxSizeValue = maxSize[key];
		if (typeof maxSizeValue === "number") {
			if (s > maxSizeValue) return true;
		}
	}
	return false;
};

/**
 * @param {Record<string, number>} size size
 * @param {Record<string, number>} minSize minimum size
 * @returns {boolean} true, when size is too small
 */
const isTooSmall = (size, minSize) => {
	for (const key of Object.keys(size)) {
		const s = size[key];
		if (s === 0) continue;
		const minSizeValue = minSize[key];
		if (typeof minSizeValue === "number") {
			if (s < minSizeValue) return true;
		}
	}
	return false;
};

/**
 * @param {Record<string, number>} size size
 * @param {Record<string, number>} minSize minimum size
 * @returns {Set<string>} set of types that are too small
 */
const getTooSmallTypes = (size, minSize) => {
	const types = new Set();
	for (const key of Object.keys(size)) {
		const s = size[key];
		if (s === 0) continue;
		const minSizeValue = minSize[key];
		if (typeof minSizeValue === "number") {
			if (s < minSizeValue) types.add(key);
		}
	}
	return types;
};

/**
 * @template T
 * @param {TODO} size size
 * @param {Set<string>} types types
 * @returns {number} number of matching size types
 */
const getNumberOfMatchingSizeTypes = (size, types) => {
	let i = 0;
	for (const key of Object.keys(size)) {
		if (size[key] !== 0 && types.has(key)) i++;
	}
	return i;
};

/**
 * @param {Record<string, number>} size size
 * @param {Set<string>} types types
 * @returns {number} selective size sum
 */
const selectiveSizeSum = (size, types) => {
	let sum = 0;
	for (const key of Object.keys(size)) {
		if (size[key] !== 0 && types.has(key)) sum += size[key];
	}
	return sum;
};

/**
 * @template T
 */
class Node {
	/**
	 * @param {T} item item
	 * @param {string} key key
	 * @param {Record<string, number>} size size
	 */
	constructor(item, key, size) {
		this.item = item;
		this.key = key;
		this.size = size;
	}
}

/**
 * @template T
 */
class Group {
	/**
	 * @param {Node<T>[]} nodes nodes
	 * @param {number[] | null} similarities similarities between the nodes (length = nodes.length - 1)
	 * @param {Record<string, number>=} size size of the group
	 */
	constructor(nodes, similarities, size) {
		this.nodes = nodes;
		this.similarities = similarities;
		this.size = size || sumSize(nodes);
		/** @type {string | undefined} */
		this.key = undefined;
	}

	/**
	 * @param {function(Node<T>): boolean} filter filter function
	 * @returns {Node<T>[] | undefined} removed nodes
	 */
	popNodes(filter) {
		const newNodes = [];
		const newSimilarities = [];
		const resultNodes = [];
		let lastNode;
		for (let i = 0; i < this.nodes.length; i++) {
			const node = this.nodes[i];
			if (filter(node)) {
				resultNodes.push(node);
			} else {
				if (newNodes.length > 0) {
					newSimilarities.push(
						lastNode === this.nodes[i - 1]
							? /** @type {number[]} */ (this.similarities)[i - 1]
							: similarity(lastNode.key, node.key)
					);
				}
				newNodes.push(node);
				lastNode = node;
			}
		}
		if (resultNodes.length === this.nodes.length) return undefined;
		this.nodes = newNodes;
		this.similarities = newSimilarities;
		this.size = sumSize(newNodes);
		return resultNodes;
	}
}

/**
 * @template T
 * @param {Iterable<Node<T>>} nodes nodes
 * @returns {number[]} similarities
 */
const getSimilarities = nodes => {
	// calculate similarities between lexically adjacent nodes
	/** @type {number[]} */
	const similarities = [];
	let last = undefined;
	for (const node of nodes) {
		if (last !== undefined) {
			similarities.push(similarity(last.key, node.key));
		}
		last = node;
	}
	return similarities;
};

/**
 * @template T
 * @typedef {object} GroupedItems<T>
 * @property {string} key
 * @property {T[]} items
 * @property {Record<string, number>} size
 */

/**
 * @template T
 * @typedef {object} Options
 * @property {Record<string, number>} maxSize maximum size of a group
 * @property {Record<string, number>} minSize minimum size of a group (preferred over maximum size)
 * @property {Iterable<T>} items a list of items
 * @property {function(T): Record<string, number>} getSize function to get size of an item
 * @property {function(T): string} getKey function to get the key of an item
 */

/**
 * @template T
 * @param {Options<T>} options options object
 * @returns {GroupedItems<T>[]} grouped items
 */
module.exports = ({ maxSize, minSize, items, getSize, getKey }) => {
	/** @type {Group<T>[]} */
	const result = [];

	const nodes = Array.from(
		items,
		item => new Node(item, getKey(item), getSize(item))
	);

	/** @type {Node<T>[]} */
	const initialNodes = [];

	// lexically ordering of keys
	nodes.sort((a, b) => {
		if (a.key < b.key) return -1;
		if (a.key > b.key) return 1;
		return 0;
	});

	// return nodes bigger than maxSize directly as group
	// But make sure that minSize is not violated
	for (const node of nodes) {
		if (isTooBig(node.size, maxSize) && !isTooSmall(node.size, minSize)) {
			result.push(new Group([node], []));
		} else {
			initialNodes.push(node);
		}
	}

	if (initialNodes.length > 0) {
		const initialGroup = new Group(initialNodes, getSimilarities(initialNodes));

		/**
		 * @param {Group<T>} group group
		 * @param {Record<string, number>} consideredSize size of the group to consider
		 * @returns {boolean} true, if the group was modified
		 */
		const removeProblematicNodes = (group, consideredSize = group.size) => {
			const problemTypes = getTooSmallTypes(consideredSize, minSize);
			if (problemTypes.size > 0) {
				// We hit an edge case where the working set is already smaller than minSize
				// We merge problematic nodes with the smallest result node to keep minSize intact
				const problemNodes = group.popNodes(
					n => getNumberOfMatchingSizeTypes(n.size, problemTypes) > 0
				);
				if (problemNodes === undefined) return false;
				// Only merge it with result nodes that have the problematic size type
				const possibleResultGroups = result.filter(
					n => getNumberOfMatchingSizeTypes(n.size, problemTypes) > 0
				);
				if (possibleResultGroups.length > 0) {
					const bestGroup = possibleResultGroups.reduce((min, group) => {
						const minMatches = getNumberOfMatchingSizeTypes(min, problemTypes);
						const groupMatches = getNumberOfMatchingSizeTypes(
							group,
							problemTypes
						);
						if (minMatches !== groupMatches)
							return minMatches < groupMatches ? group : min;
						if (
							selectiveSizeSum(min.size, problemTypes) >
							selectiveSizeSum(group.size, problemTypes)
						)
							return group;
						return min;
					});
					for (const node of problemNodes) bestGroup.nodes.push(node);
					bestGroup.nodes.sort((a, b) => {
						if (a.key < b.key) return -1;
						if (a.key > b.key) return 1;
						return 0;
					});
				} else {
					// There are no other nodes with the same size types
					// We create a new group and have to accept that it's smaller than minSize
					result.push(new Group(problemNodes, null));
				}
				return true;
			} else {
				return false;
			}
		};

		if (initialGroup.nodes.length > 0) {
			const queue = [initialGroup];

			while (queue.length) {
				const group = /** @type {Group<T>} */ (queue.pop());
				// only groups bigger than maxSize need to be splitted
				if (!isTooBig(group.size, maxSize)) {
					result.push(group);
					continue;
				}
				// If the group is already too small
				// we try to work only with the unproblematic nodes
				if (removeProblematicNodes(group)) {
					// This changed something, so we try this group again
					queue.push(group);
					continue;
				}

				// find unsplittable area from left and right
				// going minSize from left and right
				// at least one node need to be included otherwise we get stuck
				let left = 1;
				let leftSize = Object.create(null);
				addSizeTo(leftSize, group.nodes[0].size);
				while (left < group.nodes.length && isTooSmall(leftSize, minSize)) {
					addSizeTo(leftSize, group.nodes[left].size);
					left++;
				}
				let right = group.nodes.length - 2;
				let rightSize = Object.create(null);
				addSizeTo(rightSize, group.nodes[group.nodes.length - 1].size);
				while (right >= 0 && isTooSmall(rightSize, minSize)) {
					addSizeTo(rightSize, group.nodes[right].size);
					right--;
				}

				//      left v   v right
				// [ O O O ] O O O [ O O O ]
				// ^^^^^^^^^ leftSize
				//       rightSize ^^^^^^^^^
				// leftSize > minSize
				// rightSize > minSize

				// Perfect split: [ O O O ] [ O O O ]
				//                right === left - 1

				if (left - 1 > right) {
					// We try to remove some problematic nodes to "fix" that
					let prevSize;
					if (right < group.nodes.length - left) {
						subtractSizeFrom(rightSize, group.nodes[right + 1].size);
						prevSize = rightSize;
					} else {
						subtractSizeFrom(leftSize, group.nodes[left - 1].size);
						prevSize = leftSize;
					}
					if (removeProblematicNodes(group, prevSize)) {
						// This changed something, so we try this group again
						queue.push(group);
						continue;
					}
					// can't split group while holding minSize
					// because minSize is preferred of maxSize we return
					// the problematic nodes as result here even while it's too big
					// To avoid this make sure maxSize > minSize * 3
					result.push(group);
					continue;
				}
				if (left <= right) {
					// when there is a area between left and right
					// we look for best split point
					// we split at the minimum similarity
					// here key space is separated the most
					// But we also need to make sure to not create too small groups
					let best = -1;
					let bestSimilarity = Infinity;
					let pos = left;
					let rightSize = sumSize(group.nodes.slice(pos));

					//       pos v   v right
					// [ O O O ] O O O [ O O O ]
					// ^^^^^^^^^ leftSize
					// rightSize ^^^^^^^^^^^^^^^

					while (pos <= right + 1) {
						const similarity = /** @type {number[]} */ (group.similarities)[
							pos - 1
						];
						if (
							similarity < bestSimilarity &&
							!isTooSmall(leftSize, minSize) &&
							!isTooSmall(rightSize, minSize)
						) {
							best = pos;
							bestSimilarity = similarity;
						}
						addSizeTo(leftSize, group.nodes[pos].size);
						subtractSizeFrom(rightSize, group.nodes[pos].size);
						pos++;
					}
					if (best < 0) {
						// This can't happen
						// but if that assumption is wrong
						// fallback to a big group
						result.push(group);
						continue;
					}
					left = best;
					right = best - 1;
				}

				// create two new groups for left and right area
				// and queue them up
				const rightNodes = [group.nodes[right + 1]];
				/** @type {number[]} */
				const rightSimilarities = [];
				for (let i = right + 2; i < group.nodes.length; i++) {
					rightSimilarities.push(
						/** @type {number[]} */ (group.similarities)[i - 1]
					);
					rightNodes.push(group.nodes[i]);
				}
				queue.push(new Group(rightNodes, rightSimilarities));

				const leftNodes = [group.nodes[0]];
				/** @type {number[]} */
				const leftSimilarities = [];
				for (let i = 1; i < left; i++) {
					leftSimilarities.push(
						/** @type {number[]} */ (group.similarities)[i - 1]
					);
					leftNodes.push(group.nodes[i]);
				}
				queue.push(new Group(leftNodes, leftSimilarities));
			}
		}
	}

	// lexically ordering
	result.sort((a, b) => {
		if (a.nodes[0].key < b.nodes[0].key) return -1;
		if (a.nodes[0].key > b.nodes[0].key) return 1;
		return 0;
	});

	// give every group a name
	const usedNames = new Set();
	for (let i = 0; i < result.length; i++) {
		const group = result[i];
		if (group.nodes.length === 1) {
			group.key = group.nodes[0].key;
		} else {
			const first = group.nodes[0];
			const last = group.nodes[group.nodes.length - 1];
			const name = getName(first.key, last.key, usedNames);
			group.key = name;
		}
	}

	// return the results
	return result.map(group => {
		/** @type {GroupedItems<T>} */
		return {
			key: group.key,
			items: group.nodes.map(node => node.item),
			size: group.size
		};
	});
};


code:
/*
	MIT License http://www.opensource.org/licenses/mit-license.php
	Author Sam Chen @chenxsan
*/

"use strict";

/**
 * @param {string} urlAndGlobal the script request
 * @returns {string[]} script url and its global variable
 */
module.exports = function extractUrlAndGlobal(urlAndGlobal) {
	const index = urlAndGlobal.indexOf("@");
	if (index <= 0 || index === urlAndGlobal.length - 1) {
		throw new Error(`Invalid request "${urlAndGlobal}"`);
	}
	return [urlAndGlobal.substring(index + 1), urlAndGlobal.substring(0, index)];
};