1 /*
2  * Copyright (c) 2016, 2017, 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.lang.module.ModuleDescriptor.Requires;
34 import java.lang.module.ModuleDescriptor.Requires.Modifier;
35 
36 import java.nio.ByteBuffer;
37 import java.util.ArrayList;
38 import java.util.Comparator;
39 import java.util.HashMap;
40 import java.util.HashSet;
41 import java.util.LinkedHashSet;
42 import java.util.List;
43 import java.util.Map;
44 import java.util.Set;
45 import java.util.stream.Stream;
46 
47 /**
48  * Helper class to sort modules in topological order
49  */
50 public final class ModuleSorter {
51     private final Map<ResourcePoolModule, Set<ResourcePoolModule>> graph = new HashMap<>();
52     private final List<ResourcePoolModule> result = new ArrayList<>();
53 
54     private final ResourcePoolModuleView moduleView;
55 
ModuleSorter(ResourcePoolModuleView moduleView)56     public ModuleSorter(ResourcePoolModuleView moduleView) {
57         this.moduleView = moduleView;
58 
59         moduleView.modules().forEach(this::addModule);
60     }
61 
readModuleDescriptor(ResourcePoolModule module)62     private ModuleDescriptor readModuleDescriptor(ResourcePoolModule module) {
63         String p = "/" + module.name() + "/module-info.class";
64         ResourcePoolEntry content = module.findEntry(p).orElseThrow(() ->
65             new PluginException("module-info.class not found for " +
66                 module.name() + " module")
67         );
68         ByteBuffer bb = ByteBuffer.wrap(content.contentBytes());
69         return ModuleDescriptor.read(bb);
70     }
71 
addModule(ResourcePoolModule module)72     private ModuleSorter addModule(ResourcePoolModule module) {
73         addNode(module);
74         // the module graph will be traversed in a stable order for
75         // the topological sort. So add the dependences in the module name order
76         readModuleDescriptor(module).requires()
77                                     .stream()
78                                     .sorted(Comparator.comparing(Requires::name))
79                                     .forEach(req ->
80         {
81             ResourcePoolModule dep = moduleView.findModule(req.name()).orElse(null);
82             if (dep != null) {
83                 addNode(dep);
84                 graph.get(module).add(dep);
85             } else if (!req.modifiers().contains(Modifier.STATIC)) {
86                 throw new PluginException(req.name() + " not found");
87             }
88         });
89         return this;
90     }
91 
addNode(ResourcePoolModule module)92     private void addNode(ResourcePoolModule module) {
93         graph.computeIfAbsent(module, _n -> new LinkedHashSet<>());
94     }
95 
96     /*
97      * The module graph will be traversed in a stable order
98      * (traversing the modules and their dependences in alphabetical order)
99      * so that it will produce the same result of a given module graph.
100      */
build()101     private synchronized void build() {
102         if (!result.isEmpty() || graph.isEmpty())
103             return;
104 
105         Set<ResourcePoolModule> visited = new HashSet<>();
106         Set<ResourcePoolModule> done = new HashSet<>();
107         graph.keySet().stream()
108              .sorted(Comparator.comparing(ResourcePoolModule::name))
109              .forEach(node -> visit(node, visited, done));
110     }
111 
sorted()112     public Stream<ResourcePoolModule> sorted() {
113         build();
114         return result.stream();
115     }
116 
visit(ResourcePoolModule node, Set<ResourcePoolModule> visited, Set<ResourcePoolModule> done)117     private void visit(ResourcePoolModule node,
118                        Set<ResourcePoolModule> visited,
119                        Set<ResourcePoolModule> done) {
120         if (visited.contains(node)) {
121             if (!done.contains(node)) {
122                 throw new IllegalArgumentException("Cyclic detected: " +
123                     node + " " + graph.get(node));
124             }
125             return;
126         }
127 
128         // traverse the dependences of the given module which are
129         // also sorted in alphabetical order
130         visited.add(node);
131         graph.get(node).forEach(x -> visit(x, visited, done));
132         done.add(node);
133         result.add(node);
134     }
135 }
136