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 }