1 /*
2 * Copyright (c) 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
26 package jdk.internal.module;
27
28 import java.io.PrintStream;
29 import java.lang.module.Configuration;
30 import java.lang.module.ResolvedModule;
31 import java.net.URI;
32 import java.nio.file.Path;
33 import java.util.ArrayDeque;
34 import java.util.Collections;
35 import java.util.Deque;
36 import java.util.HashMap;
37 import java.util.HashSet;
38 import java.util.LinkedList;
39 import java.util.Map;
40 import java.util.Set;
41 import java.util.function.Consumer;
42 import java.util.function.Function;
43 import java.util.stream.Stream;
44 import static java.util.stream.Collectors.*;
45
46 /**
47 * A Builder to compute ModuleHashes from a given configuration
48 */
49 public class ModuleHashesBuilder {
50 private final Configuration configuration;
51 private final Set<String> hashModuleCandidates;
52
53 /**
54 * Constructs a ModuleHashesBuilder that finds the packaged modules
55 * from the location of ModuleReference found from the given Configuration.
56 *
57 * @param config Configuration for building module hashes
58 * @param modules the candidate modules to be hashed
59 */
60 public ModuleHashesBuilder(Configuration config, Set<String> modules) {
61 this.configuration = config;
62 this.hashModuleCandidates = modules;
63 }
64
65 /**
66 * Returns a map of a module M to ModuleHashes for the modules
67 * that depend upon M directly or indirectly.
68 *
69 * The key for each entry in the returned map is a module M that has
70 * no outgoing edges to any of the candidate modules to be hashed
71 * i.e. M is a leaf node in a connected subgraph containing M and
72 * other candidate modules from the module graph filtering
73 * the outgoing edges from M to non-candidate modules.
74 */
75 public Map<String, ModuleHashes> computeHashes(Set<String> roots) {
76 // build a graph containing the packaged modules and
77 // its transitive dependences matching --hash-modules
78 Graph.Builder<String> builder = new Graph.Builder<>();
79 Deque<ResolvedModule> deque = new ArrayDeque<>(configuration.modules());
80 Set<ResolvedModule> visited = new HashSet<>();
81 while (!deque.isEmpty()) {
82 ResolvedModule rm = deque.pop();
83 if (!visited.contains(rm)) {
84 visited.add(rm);
85 builder.addNode(rm.name());
86 for (ResolvedModule dm : rm.reads()) {
87 if (!visited.contains(dm)) {
88 deque.push(dm);
89 }
90 builder.addEdge(rm.name(), dm.name());
91 }
92 }
93 }
94
95 // each node in a transposed graph is a matching packaged module
96 // in which the hash of the modules that depend upon it is recorded
97 Graph<String> transposedGraph = builder.build().transpose();
98
99 // traverse the modules in topological order that will identify
100 // the modules to record the hashes - it is the first matching
101 // module and has not been hashed during the traversal.
102 Set<String> mods = new HashSet<>();
103 Map<String, ModuleHashes> hashes = new HashMap<>();
104 builder.build()
105 .orderedNodes()
106 .filter(mn -> roots.contains(mn) && !mods.contains(mn))
107 .forEach(mn -> {
108 // Compute hashes of the modules that depend on mn directly and
109 // indirectly excluding itself.
110 Set<String> ns = transposedGraph.dfs(mn)
111 .stream()
112 .filter(n -> !n.equals(mn) && hashModuleCandidates.contains(n))
113 .collect(toSet());
114 mods.add(mn);
115 mods.addAll(ns);
116
117 if (!ns.isEmpty()) {
118 Map<String, Path> moduleToPath = ns.stream()
119 .collect(toMap(Function.identity(), this::moduleToPath));
120 hashes.put(mn, ModuleHashes.generate(moduleToPath, "SHA-256"));
121 }
122 });
123 return hashes;
124 }
125
126 private Path moduleToPath(String name) {
127 ResolvedModule rm = configuration.findModule(name).orElseThrow(
128 () -> new InternalError("Selected module " + name + " not on module path"));
129
130 URI uri = rm.reference().location().get();
131 Path path = Path.get(uri);
132 String fn = path.getFileName().toString();
133 if (!fn.endsWith(".jar") && !fn.endsWith(".jmod")) {
134 throw new UnsupportedOperationException(path + " is not a modular JAR or jmod file");
135 }
136 return path;
137 }
138
139 /*
140 * Utility class
141 */
142 static class Graph<T> {
143 private final Set<T> nodes;
144 private final Map<T, Set<T>> edges;
145
146 public Graph(Set<T> nodes, Map<T, Set<T>> edges) {
147 this.nodes = Collections.unmodifiableSet(nodes);
148 this.edges = Collections.unmodifiableMap(edges);
149 }
150
151 public Set<T> nodes() {
152 return nodes;
153 }
154
155 public Map<T, Set<T>> edges() {
156 return edges;
157 }
158
159 public Set<T> adjacentNodes(T u) {
160 return edges.get(u);
161 }
162
163 public boolean contains(T u) {
164 return nodes.contains(u);
165 }
166
167 /**
168 * Returns nodes sorted in topological order.
169 */
170 public Stream<T> orderedNodes() {
171 TopoSorter<T> sorter = new TopoSorter<>(this);
172 return sorter.result.stream();
173 }
174
175 /**
176 * Traverse this graph and performs the given action in topological order
177 */
178 public void ordered(Consumer<T> action) {
179 TopoSorter<T> sorter = new TopoSorter<>(this);
180 sorter.ordered(action);
181 }
182
183 /**
184 * Traverses this graph and performs the given action in reverse topological order
185 */
186 public void reverse(Consumer<T> action) {
187 TopoSorter<T> sorter = new TopoSorter<>(this);
188 sorter.reverse(action);
189 }
190
191 /**
192 * Returns a transposed graph from this graph
193 */
194 public Graph<T> transpose() {
195 Builder<T> builder = new Builder<>();
196 nodes.stream().forEach(builder::addNode);
197 // reverse edges
198 edges.keySet().forEach(u -> {
199 edges.get(u).stream()
200 .forEach(v -> builder.addEdge(v, u));
201 });
202 return builder.build();
203 }
204
205 /**
206 * Returns all nodes reachable from the given root.
207 */
208 public Set<T> dfs(T root) {
209 return dfs(Set.of(root));
210 }
211
212 /**
213 * Returns all nodes reachable from the given set of roots.
214 */
215 public Set<T> dfs(Set<T> roots) {
216 Deque<T> deque = new LinkedList<>(roots);
217 Set<T> visited = new HashSet<>();
218 while (!deque.isEmpty()) {
219 T u = deque.pop();
220 if (!visited.contains(u)) {
221 visited.add(u);
222 if (contains(u)) {
223 adjacentNodes(u).stream()
224 .filter(v -> !visited.contains(v))
225 .forEach(deque::push);
226 }
227 }
228 }
229 return visited;
230 }
231
232 public void printGraph(PrintStream out) {
233 out.println("graph for " + nodes);
234 nodes.stream()
235 .forEach(u -> adjacentNodes(u).stream()
236 .forEach(v -> out.format(" %s -> %s%n", u, v)));
237 }
238
239 static class Builder<T> {
240 final Set<T> nodes = new HashSet<>();
241 final Map<T, Set<T>> edges = new HashMap<>();
242
243 public void addNode(T node) {
244 if (nodes.contains(node)) {
245 return;
246 }
247 nodes.add(node);
248 edges.computeIfAbsent(node, _e -> new HashSet<>());
249 }
250
251 public void addEdge(T u, T v) {
252 addNode(u);
253 addNode(v);
254 edges.get(u).add(v);
255 }
256
257 public Graph<T> build() {
258 return new Graph<T>(nodes, edges);
259 }
260 }
261 }
262
263 /**
264 * Topological sort
265 */
266 private static class TopoSorter<T> {
267 final Deque<T> result = new LinkedList<>();
268 final Deque<T> nodes;
269 final Graph<T> graph;
270
271 TopoSorter(Graph<T> graph) {
272 this.graph = graph;
273 this.nodes = new LinkedList<>(graph.nodes);
274 sort();
275 }
276
277 public void ordered(Consumer<T> action) {
278 result.iterator().forEachRemaining(action);
279 }
280
281 public void reverse(Consumer<T> action) {
282 result.descendingIterator().forEachRemaining(action);
283 }
284
285 private void sort() {
286 Deque<T> visited = new LinkedList<>();
287 Deque<T> done = new LinkedList<>();
288 T node;
289 while ((node = nodes.poll()) != null) {
290 if (!visited.contains(node)) {
291 visit(node, visited, done);
292 }
293 }
294 }
295
296 private void visit(T node, Deque<T> visited, Deque<T> done) {
297 if (visited.contains(node)) {
298 if (!done.contains(node)) {
299 throw new IllegalArgumentException("Cyclic detected: " +
300 node + " " + graph.edges().get(node));
301 }
302 return;
303 }
304 visited.add(node);
305 graph.edges().get(node).stream()
306 .forEach(x -> visit(x, visited, done));
307 done.add(node);
308 result.addLast(node);
309 }
310 }
311 }