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 }