1 /* 2 * Copyright (c) 2016, 2017, 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.ResourcePoolEntry; 29 import jdk.tools.jlink.plugin.ResourcePoolModule; 30 import jdk.tools.jlink.plugin.ResourcePoolModuleView; 31 32 import java.lang.module.ModuleDescriptor; 33 import java.lang.module.ModuleDescriptor.Requires; 34 import java.lang.module.ModuleDescriptor.Requires.Modifier; 35 36 import java.nio.ByteBuffer; 37 import java.util.ArrayList; 38 import java.util.Comparator; 39 import java.util.HashMap; 40 import java.util.HashSet; 41 import java.util.LinkedHashSet; 42 import java.util.List; 43 import java.util.Map; 44 import java.util.Set; 45 import java.util.stream.Stream; 46 47 /** 48 * Helper class to sort modules in topological order 49 */ 50 public final class ModuleSorter { 51 private final Map<ResourcePoolModule, Set<ResourcePoolModule>> graph = new HashMap<>(); 52 private final List<ResourcePoolModule> result = new ArrayList<>(); 53 54 private final ResourcePoolModuleView moduleView; 55 ModuleSorter(ResourcePoolModuleView moduleView)56 public ModuleSorter(ResourcePoolModuleView moduleView) { 57 this.moduleView = moduleView; 58 59 moduleView.modules().forEach(this::addModule); 60 } 61 readModuleDescriptor(ResourcePoolModule module)62 private ModuleDescriptor readModuleDescriptor(ResourcePoolModule module) { 63 String p = "/" + module.name() + "/module-info.class"; 64 ResourcePoolEntry content = module.findEntry(p).orElseThrow(() -> 65 new PluginException("module-info.class not found for " + 66 module.name() + " module") 67 ); 68 ByteBuffer bb = ByteBuffer.wrap(content.contentBytes()); 69 return ModuleDescriptor.read(bb); 70 } 71 addModule(ResourcePoolModule module)72 private ModuleSorter addModule(ResourcePoolModule module) { 73 addNode(module); 74 // the module graph will be traversed in a stable order for 75 // the topological sort. So add the dependences in the module name order 76 readModuleDescriptor(module).requires() 77 .stream() 78 .sorted(Comparator.comparing(Requires::name)) 79 .forEach(req -> 80 { 81 ResourcePoolModule dep = moduleView.findModule(req.name()).orElse(null); 82 if (dep != null) { 83 addNode(dep); 84 graph.get(module).add(dep); 85 } else if (!req.modifiers().contains(Modifier.STATIC)) { 86 throw new PluginException(req.name() + " not found"); 87 } 88 }); 89 return this; 90 } 91 addNode(ResourcePoolModule module)92 private void addNode(ResourcePoolModule module) { 93 graph.computeIfAbsent(module, _n -> new LinkedHashSet<>()); 94 } 95 96 /* 97 * The module graph will be traversed in a stable order 98 * (traversing the modules and their dependences in alphabetical order) 99 * so that it will produce the same result of a given module graph. 100 */ build()101 private synchronized void build() { 102 if (!result.isEmpty() || graph.isEmpty()) 103 return; 104 105 Set<ResourcePoolModule> visited = new HashSet<>(); 106 Set<ResourcePoolModule> done = new HashSet<>(); 107 graph.keySet().stream() 108 .sorted(Comparator.comparing(ResourcePoolModule::name)) 109 .forEach(node -> visit(node, visited, done)); 110 } 111 sorted()112 public Stream<ResourcePoolModule> sorted() { 113 build(); 114 return result.stream(); 115 } 116 visit(ResourcePoolModule node, Set<ResourcePoolModule> visited, Set<ResourcePoolModule> done)117 private void visit(ResourcePoolModule node, 118 Set<ResourcePoolModule> visited, 119 Set<ResourcePoolModule> done) { 120 if (visited.contains(node)) { 121 if (!done.contains(node)) { 122 throw new IllegalArgumentException("Cyclic detected: " + 123 node + " " + graph.get(node)); 124 } 125 return; 126 } 127 128 // traverse the dependences of the given module which are 129 // also sorted in alphabetical order 130 visited.add(node); 131 graph.get(node).forEach(x -> visit(x, visited, done)); 132 done.add(node); 133 result.add(node); 134 } 135 } 136