1 /* 2 * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 package jdk.tools.jlink.internal; 26 27 import jdk.tools.jlink.plugin.PluginException; 28 import jdk.tools.jlink.plugin.ResourcePoolModule; 29 import jdk.tools.jlink.plugin.ResourcePoolModuleView; 30 31 import java.lang.module.ModuleDescriptor; 32 import java.util.Deque; 33 import java.util.HashMap; 34 import java.util.HashSet; 35 import java.util.LinkedList; 36 import java.util.Map; 37 import java.util.Set; 38 import java.util.stream.Stream; 39 40 /** 41 * Helper class to sort modules in topological order 42 */ 43 public class ModuleSorter { 44 private final Deque<ResourcePoolModule> nodes = new LinkedList<>(); 45 private final Map<String, Set<ResourcePoolModule>> edges = new HashMap<>(); 46 private final Deque<ResourcePoolModule> result = new LinkedList<>(); 47 48 private final ResourcePoolModuleView moduleView; 49 50 public ModuleSorter(ResourcePoolModuleView moduleView) { 51 this.moduleView = moduleView; 52 53 moduleView.modules().forEach(this::addModule); 54 } 55 56 private ModuleSorter addModule(ResourcePoolModule module) { 57 ModuleDescriptor descriptor = module.descriptor(); 58 addNode(module); 59 descriptor.requires().stream() 60 .forEach(req -> { 61 String dm = req.name(); 62 ResourcePoolModule dep = moduleView.findModule(dm) 63 .orElseThrow(() -> new PluginException(dm + " not found")); 64 addNode(dep); 65 edges.get(module.name()).add(dep); 66 }); 67 return this; 68 } 69 70 private void addNode(ResourcePoolModule module) { 71 nodes.add(module); 72 edges.computeIfAbsent(module.name(), _n -> new HashSet<>()); 73 } 74 75 private synchronized void build() { 76 if (!result.isEmpty() || nodes.isEmpty()) 77 return; 78 79 Deque<ResourcePoolModule> visited = new LinkedList<>(); 80 Deque<ResourcePoolModule> done = new LinkedList<>(); 81 ResourcePoolModule node; 82 while ((node = nodes.poll()) != null) { 83 if (!visited.contains(node)) { 84 visit(node, visited, done); 85 } 86 } 87 } 88 89 public Stream<ResourcePoolModule> sorted() { 90 build(); 91 return result.stream(); 92 } 93 94 private void visit(ResourcePoolModule node, 95 Deque<ResourcePoolModule> visited, 96 Deque<ResourcePoolModule> done) { 97 if (visited.contains(node)) { 98 if (!done.contains(node)) { 99 throw new IllegalArgumentException("Cyclic detected: " + 100 node + " " + edges.get(node.name())); 101 } 102 return; 103 } 104 visited.add(node); 105 edges.get(node.name()).stream() 106 .forEach(x -> visit(x, visited, done)); 107 done.add(node); 108 result.addLast(node); 109 } 110 }