* @param {ResourcePool} pool Modulepool to retrieve module information from * @param {string[]} moduleNames list of modules to be sorted * @returns {Promise } sorted list of modules * @private
(pool, moduleNames)
| 87 | * @private |
| 88 | */ |
| 89 | function topologicalSort(pool, moduleNames) { |
| 90 | return createDependencyGraph(pool, moduleNames, false). |
| 91 | then(function(graph) { |
| 92 | // now do a topological sort. |
| 93 | const sequence = []; |
| 94 | let i; |
| 95 | let j; |
| 96 | let l = moduleNames.length; |
| 97 | moduleNames = moduleNames.slice(); // clone |
| 98 | |
| 99 | do { |
| 100 | // invariant: the first 'l' items in moduleNames are still to be processed |
| 101 | |
| 102 | // first loop over all remaining modules and emit those that don't have any more dependencies |
| 103 | for (i = 0, j = 0; i < l; i++ ) { |
| 104 | const moduleName = moduleNames[i]; |
| 105 | const node = graph[moduleName]; |
| 106 | |
| 107 | // modules that don't have any unsatisfied dependencies can be emitted |
| 108 | if ( node == null || node.outgoing.length === 0 ) { |
| 109 | // console.log("emitting %s", moduleName, node); |
| 110 | |
| 111 | // add module to sequence |
| 112 | sequence.push(moduleName); |
| 113 | |
| 114 | // remove outgoing dependency to current module from all modules that depend on it |
| 115 | if ( node != null ) { |
| 116 | node.incoming.forEach( function(dependent) { |
| 117 | const index = dependent.outgoing.indexOf(node); |
| 118 | if ( index >= 0 ) { |
| 119 | dependent.outgoing.splice(index, 1); |
| 120 | // console.log("removing outgoing %s in %s", node.name, dependent.name); |
| 121 | } else { |
| 122 | log.error(`**** Could not find node ${node.name} in ${dependent.name}`); |
| 123 | } |
| 124 | }); |
| 125 | } |
| 126 | } else { |
| 127 | moduleNames[j++] = moduleName; |
| 128 | } |
| 129 | } |
| 130 | |
| 131 | // invariant: 'j' is the number of remaining items, 'i' is the same as 'l' now |
| 132 | |
| 133 | l = j; |
| 134 | |
| 135 | /* NODE-TODO metadata for cycle resolution not available yet |
| 136 | // if we have not been able to find a suitable module then we try to resolve well known cycles |
| 137 | if ( i === l && l > 0 cycles.hasNext() ) { |
| 138 | |
| 139 | // get one cycle |
| 140 | Collection<ModuleName> cycle = cycles.next(); |
| 141 | console.debug("trying to resolve cycle %s", cycle); |
| 142 | |
| 143 | // check that the full cycle is part of the remaining graph |
| 144 | for(ModuleName moduleName : cycle) { |
| 145 | if ( !moduleNames.contains(moduleName) ) { |
| 146 | throw new IllegalStateException("Misconfigured cycle, cannot resolve."); |
no test coverage detected