source: frontend/node_modules/webpack/lib/optimize/RemoveParentModulesPlugin.js

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

"use strict";

const { STAGE_BASIC } = require("../OptimizationStages");

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

/**
 * Intersects multiple masks represented as bigints
 * @param {bigint[]} masks The module masks to intersect
 * @returns {bigint} The intersection of all masks
 */
function intersectMasks(masks) {
        let result = masks[0];
        for (let i = masks.length - 1; i >= 1; i--) {
                result &= masks[i];
        }
        return result;
}

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

/**
 * Parses the module mask and returns the modules represented by it
 * @param {bigint} mask the module mask
 * @param {Module[]} ordinalModules the modules in the order they were added to the mask (LSB is index 0)
 * @returns {Generator<Module, undefined, undefined>} the modules represented by the mask
 */
function* getModulesFromMask(mask, ordinalModules) {
        let offset = 31;
        while (mask !== ZERO_BIGINT) {
                // Consider the last 32 bits, since that's what Math.clz32 can handle
                let last32 = Number(BigInt.asUintN(32, mask));
                while (last32 > 0) {
                        const last = Math.clz32(last32);
                        // The number of trailing zeros is the number trimmed off the input mask + 31 - the number of leading zeros
                        // The 32 is baked into the initial value of offset
                        const moduleIndex = offset - last;
                        // The number of trailing zeros is the index into the array generated by getOrCreateModuleMask
                        const module = ordinalModules[moduleIndex];
                        yield module;
                        // Remove the matched module from the mask
                        // Since we can only count leading zeros, not trailing, we can't just downshift the mask
                        last32 &= ~(1 << (31 - last));
                }

                // Remove the processed chunk from the mask
                mask >>= THIRTY_TWO_BIGINT;
                offset += 32;
        }
}

const PLUGIN_NAME = "RemoveParentModulesPlugin";

class RemoveParentModulesPlugin {
        /**
         * Applies the plugin by registering its hooks on the compiler.
         * @param {Compiler} compiler the compiler
         * @returns {void}
         */
        apply(compiler) {
                compiler.hooks.compilation.tap(PLUGIN_NAME, (compilation) => {
                        /**
                         * Handles the hook callback for this code path.
                         * @param {Iterable<Chunk>} chunks the chunks
                         * @param {ChunkGroup[]} chunkGroups the chunk groups
                         */
                        const handler = (chunks, chunkGroups) => {
                                const chunkGraph = compilation.chunkGraph;
                                /** @type {Set<ChunkGroup>} */
                                const queue = new Set();
                                /** @type {WeakMap<ChunkGroup, bigint | undefined>} */
                                const availableModulesMap = new WeakMap();

                                let nextModuleMask = ONE_BIGINT;
                                /** @type {WeakMap<Module, bigint>} */
                                const maskByModule = new WeakMap();
                                /** @type {Module[]} */
                                const ordinalModules = [];

                                /**
                                 * Gets or create module mask.
                                 * @param {Module} mod the module to get the mask for
                                 * @returns {bigint} the module mask to uniquely identify the module
                                 */
                                const getOrCreateModuleMask = (mod) => {
                                        let id = maskByModule.get(mod);
                                        if (id === undefined) {
                                                id = nextModuleMask;
                                                ordinalModules.push(mod);
                                                maskByModule.set(mod, id);
                                                nextModuleMask <<= ONE_BIGINT;
                                        }
                                        return id;
                                };

                                // Initialize masks by chunk and by chunk group for quicker comparisons
                                /** @type {WeakMap<Chunk, bigint>} */
                                const chunkMasks = new WeakMap();
                                for (const chunk of chunks) {
                                        let mask = ZERO_BIGINT;
                                        for (const m of chunkGraph.getChunkModulesIterable(chunk)) {
                                                const id = getOrCreateModuleMask(m);
                                                mask |= id;
                                        }
                                        chunkMasks.set(chunk, mask);
                                }

                                /** @type {WeakMap<ChunkGroup, bigint>} */
                                const chunkGroupMasks = new WeakMap();
                                for (const chunkGroup of chunkGroups) {
                                        let mask = ZERO_BIGINT;
                                        for (const chunk of chunkGroup.chunks) {
                                                const chunkMask = chunkMasks.get(chunk);
                                                if (chunkMask !== undefined) {
                                                        mask |= chunkMask;
                                                }
                                        }
                                        chunkGroupMasks.set(chunkGroup, mask);
                                }

                                for (const chunkGroup of compilation.entrypoints.values()) {
                                        // initialize available modules for chunks without parents
                                        availableModulesMap.set(chunkGroup, ZERO_BIGINT);
                                        for (const child of chunkGroup.childrenIterable) {
                                                queue.add(child);
                                        }
                                }
                                for (const chunkGroup of compilation.asyncEntrypoints) {
                                        // initialize available modules for chunks without parents
                                        availableModulesMap.set(chunkGroup, ZERO_BIGINT);
                                        for (const child of chunkGroup.childrenIterable) {
                                                queue.add(child);
                                        }
                                }

                                for (const chunkGroup of queue) {
                                        let availableModulesMask = availableModulesMap.get(chunkGroup);
                                        let changed = false;
                                        for (const parent of chunkGroup.parentsIterable) {
                                                const availableModulesInParent = availableModulesMap.get(parent);
                                                if (availableModulesInParent !== undefined) {
                                                        const parentMask =
                                                                availableModulesInParent |
                                                                /** @type {bigint} */ (chunkGroupMasks.get(parent));
                                                        // If we know the available modules in parent: process these
                                                        if (availableModulesMask === undefined) {
                                                                // if we have not own info yet: create new entry
                                                                availableModulesMask = parentMask;
                                                                changed = true;
                                                        } else {
                                                                const newMask = availableModulesMask & parentMask;
                                                                if (newMask !== availableModulesMask) {
                                                                        changed = true;
                                                                        availableModulesMask = newMask;
                                                                }
                                                        }
                                                }
                                        }

                                        if (changed) {
                                                availableModulesMap.set(chunkGroup, availableModulesMask);
                                                // if something changed: enqueue our children
                                                for (const child of chunkGroup.childrenIterable) {
                                                        // Push the child to the end of the queue
                                                        queue.delete(child);
                                                        queue.add(child);
                                                }
                                        }
                                }

                                // now we have available modules for every chunk
                                for (const chunk of chunks) {
                                        const chunkMask = chunkMasks.get(chunk);
                                        if (chunkMask === undefined) continue; // No info about this chunk

                                        const availableModulesSets = Array.from(
                                                chunk.groupsIterable,
                                                (chunkGroup) => availableModulesMap.get(chunkGroup)
                                        );
                                        if (availableModulesSets.includes(undefined)) continue; // No info about this chunk group

                                        const availableModulesMask = intersectMasks(
                                                /** @type {bigint[]} */
                                                (availableModulesSets)
                                        );
                                        const toRemoveMask = chunkMask & availableModulesMask;
                                        if (toRemoveMask !== ZERO_BIGINT) {
                                                for (const module of getModulesFromMask(
                                                        toRemoveMask,
                                                        ordinalModules
                                                )) {
                                                        chunkGraph.disconnectChunkAndModule(chunk, module);
                                                }
                                        }
                                }
                        };
                        compilation.hooks.optimizeChunks.tap(
                                {
                                        name: PLUGIN_NAME,
                                        stage: STAGE_BASIC
                                },
                                handler
                        );
                });
        }
}

module.exports = RemoveParentModulesPlugin;