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 }