1 /* 2 * Copyright (c) 2015, 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 java.util.ArrayList; 28 import java.util.HashMap; 29 import java.util.HashSet; 30 import java.util.LinkedHashMap; 31 import java.util.LinkedHashSet; 32 import java.util.List; 33 import java.util.Map; 34 import java.util.Set; 35 import jdk.tools.jlink.plugin.Plugin; 36 import jdk.tools.jlink.plugin.PluginException; 37 38 public class PluginOrderingGraph { 39 40 static class Node { 41 42 Plugin plugin; 43 Set<Node> nexts = new HashSet<>(); 44 Set<Node> previous = new HashSet<>(); 45 46 @Override 47 public String toString() { 48 return plugin.getName(); 49 } 50 } 51 52 public static List<Plugin> sort(List<Plugin> plugs) { 53 List<Plugin> plugins = new ArrayList<>(); 54 plugins.addAll(plugs); 55 56 // for each plugin creates its graph. 57 Map<Plugin, Node> graphs = buildGraphs(plugins); 58 59 // At this points all individual graphs are connected 60 // Check for cycles. 61 for (Node n : graphs.values()) { 62 checkCycle(n); 63 } 64 65 List<Plugin> orderedPlugins = new ArrayList<>(); 66 // Retrieve the current roots, add them to the result, remove them from 67 while (!plugins.isEmpty()) { 68 // Build the current set of graphs from the list of input plugins 69 Map<Plugin, Node> currentGraphs = buildGraphs(plugins); 70 // Retrieve the root nodes (no previous) 71 List<Node> roots = getRoots(currentGraphs); 72 for (Node n : roots) { 73 // add them to the ordered list. 74 orderedPlugins.add(n.plugin); 75 // remove them from the input list. 76 plugins.remove(n.plugin); 77 } 78 } 79 return orderedPlugins; 80 } 81 82 // Create a grapth according to list of plugins. 83 private static Map<Plugin, Node> buildGraphs(List<Plugin> plugins) { 84 Map<String, Node> nodeStore = new HashMap<>(); 85 for (Plugin p : plugins) { 86 Node newNode = new Node(); 87 newNode.plugin = p; 88 nodeStore.put(p.getName(), newNode); 89 } 90 // for each plugin creates its graph. 91 Map<Plugin, Node> graphs = new LinkedHashMap<>(); 92 for (Plugin p : plugins) { 93 Node node = nodeStore.get(p.getName()); 94 for (String after : p.isAfter()) { 95 Node previous = nodeStore.get(after); 96 if (previous == null) { 97 continue; 98 } 99 node.previous.add(previous); 100 previous.nexts.add(node); 101 } 102 for (String before : p.isBefore()) { 103 Node next = nodeStore.get(before); 104 if (next == null) { 105 continue; 106 } 107 node.nexts.add(next); 108 next.previous.add(node); 109 } 110 graphs.put(p, node); 111 112 } 113 return graphs; 114 } 115 116 private static List<Node> getRoots(Map<Plugin, Node> graphs) { 117 List<Node> ret = new ArrayList<>(); 118 for (Node n : graphs.values()) { 119 if (n.previous.isEmpty()) { 120 ret.add(n); 121 } 122 } 123 return ret; 124 } 125 126 private static void checkCycle(Node root) { 127 for (Node next : root.nexts) { 128 Set<Node> path = new LinkedHashSet<>(); 129 path.add(root); 130 checkCycle(next, root, path); 131 } 132 } 133 134 private static void checkCycle(Node current, Node root, Set<Node> path) { 135 path.add(current); 136 if (current == root) { 137 StringBuilder builder = new StringBuilder(); 138 for (Node p : path) { 139 builder.append(p.plugin.getName()).append(">"); 140 } 141 builder.append(root); 142 throw new PluginException("Cycle detected for " + builder.toString() 143 + ". Please fix Plugin ordering (before, after constraints)."); 144 } 145 146 for (Node n : current.nexts) { 147 checkCycle(n, root, path); 148 } 149 } 150 }