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.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.nio.ByteBuffer; 34 import java.util.Deque; 35 import java.util.HashMap; 36 import java.util.HashSet; 37 import java.util.LinkedList; 38 import java.util.Map; 39 import java.util.Set; 40 import java.util.stream.Stream; 41 42 /** 43 * Helper class to sort modules in topological order 44 */ 45 public final class ModuleSorter { 46 private final Deque<ResourcePoolModule> nodes = new LinkedList<>(); 47 private final Map<String, Set<ResourcePoolModule>> edges = new HashMap<>(); 48 private final Deque<ResourcePoolModule> result = new LinkedList<>(); 49 50 private final ResourcePoolModuleView moduleView; 51 52 public ModuleSorter(ResourcePoolModuleView moduleView) { 53 this.moduleView = moduleView; 54 55 moduleView.modules().forEach(this::addModule); 56 } 57 58 private ModuleDescriptor readModuleDescriptor(ResourcePoolModule module) { 59 String p = "/" + module.name() + "/module-info.class"; 60 ResourcePoolEntry content = module.findEntry(p).orElseThrow(() -> 61 new PluginException("module-info.class not found for " + 62 module.name() + " module") 63 ); 64 ByteBuffer bb = ByteBuffer.wrap(content.contentBytes()); 65 return ModuleDescriptor.read(bb); 66 } 67 68 private ModuleSorter addModule(ResourcePoolModule module) { 69 addNode(module); 70 readModuleDescriptor(module).requires().stream() 71 .forEach(req -> { 72 String dm = req.name(); 73 ResourcePoolModule dep = moduleView.findModule(dm) 74 .orElseThrow(() -> new PluginException(dm + " not found")); 75 addNode(dep); 76 edges.get(module.name()).add(dep); 77 }); 78 return this; 79 } 80 81 private void addNode(ResourcePoolModule module) { 82 nodes.add(module); 83 edges.computeIfAbsent(module.name(), _n -> new HashSet<>()); 84 } 85 86 private synchronized void build() { 87 if (!result.isEmpty() || nodes.isEmpty()) 88 return; 89 90 Deque<ResourcePoolModule> visited = new LinkedList<>(); 91 Deque<ResourcePoolModule> done = new LinkedList<>(); 92 ResourcePoolModule node; 93 while ((node = nodes.poll()) != null) { 94 if (!visited.contains(node)) { 95 visit(node, visited, done); 96 } 97 } 98 } 99 100 public Stream<ResourcePoolModule> sorted() { 101 build(); 102 return result.stream(); 103 } 104 105 private void visit(ResourcePoolModule node, 106 Deque<ResourcePoolModule> visited, 107 Deque<ResourcePoolModule> done) { 108 if (visited.contains(node)) { 109 if (!done.contains(node)) { 110 throw new IllegalArgumentException("Cyclic detected: " + 111 node + " " + edges.get(node.name())); 112 } 113 return; 114 } 115 visited.add(node); 116 edges.get(node.name()).stream() 117 .forEach(x -> visit(x, visited, done)); 118 done.add(node); 119 result.addLast(node); 120 } 121 }