* Builds a CycleGraph by constructing the synchronous outgoing-connection * adjacency list and running iterative SCC to detect circular modules. * @param {Iterable<Module>} modules the set of modules * @param {ModuleGraph} moduleGraph the module graph * @returns {CycleGraph} the result
(modules, moduleGraph)
| 40 | * @returns {CycleGraph} the result |
| 41 | */ |
| 42 | static build(modules, moduleGraph) { |
| 43 | /** @type {Module[]} */ |
| 44 | const moduleList = []; |
| 45 | /** @type {Map<Module, number>} */ |
| 46 | const moduleToIndex = new Map(); |
| 47 | for (const module of modules) { |
| 48 | moduleToIndex.set(module, moduleList.length); |
| 49 | moduleList.push(module); |
| 50 | } |
| 51 | |
| 52 | const size = moduleList.length; |
| 53 | if (size === 0) return new CycleGraph(new Set()); |
| 54 | |
| 55 | /** @type {number[][]} */ |
| 56 | const edges = Array.from({ length: size }); |
| 57 | /** @type {boolean[]} */ |
| 58 | const selfLoops = Array.from({ length: size }, () => false); |
| 59 | |
| 60 | for (let i = 0; i < size; i++) { |
| 61 | const module = moduleList[i]; |
| 62 | /** @type {number[]} */ |
| 63 | const deps = []; |
| 64 | for (const connection of moduleGraph.getOutgoingConnections(module)) { |
| 65 | const dep = connection.dependency; |
| 66 | if (!dep) continue; |
| 67 | const target = connection.module; |
| 68 | if (!target) continue; |
| 69 | // Weak references don't synchronously evaluate the target. |
| 70 | if (connection.weak) continue; |
| 71 | // Async edges (dynamic import & friends) live in AsyncDependenciesBlock, |
| 72 | // so a synchronous dep's parent block is the module itself. |
| 73 | if (moduleGraph.getParentBlock(dep) !== module) continue; |
| 74 | if (target === module) { |
| 75 | selfLoops[i] = true; |
| 76 | continue; |
| 77 | } |
| 78 | const targetIdx = moduleToIndex.get(target); |
| 79 | if (targetIdx !== undefined) { |
| 80 | deps.push(targetIdx); |
| 81 | } |
| 82 | } |
| 83 | edges[i] = deps; |
| 84 | } |
| 85 | |
| 86 | // Iterative SCC algorithm |
| 87 | /** @type {Set<Module>} */ |
| 88 | const circular = new Set(); |
| 89 | let nextIndex = 0; |
| 90 | const nodeIndex = new Int32Array(size).fill(-1); |
| 91 | const nodeLowLink = new Int32Array(size); |
| 92 | const nodeOnStack = new Uint8Array(size); |
| 93 | /** @type {number[]} */ |
| 94 | const sccStack = []; |
| 95 | |
| 96 | /** |
| 97 | * @typedef {object} Frame |
| 98 | * @property {number} node |
| 99 | * @property {number} edgeIdx |
no test coverage detected