1 /*
2 * Copyright (c) 2017, 2020, 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.TreeMap;
38 import java.util.HashSet;
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> todo = new ArrayDeque<>(configuration.modules());
80 Set<ResolvedModule> visited = new HashSet<>();
81 ResolvedModule rm;
82 while ((rm = todo.poll()) != null) {
83 if (visited.add(rm)) {
84 builder.addNode(rm.name());
85 for (ResolvedModule dm : rm.reads()) {
86 if (!visited.contains(dm)) {
87 todo.push(dm);
88 }
89 builder.addEdge(rm.name(), dm.name());
90 }
91 }
92 }
93
94 // each node in a transposed graph is a matching packaged module
95 // in which the hash of the modules that depend upon it is recorded
96 Graph<String> transposedGraph = builder.build().transpose();
97
98 // traverse the modules in topological order that will identify
99 // the modules to record the hashes - it is the first matching
100 // module and has not been hashed during the traversal.
101 Set<String> mods = new HashSet<>();
102 Map<String, ModuleHashes> hashes = new TreeMap<>();
103 builder.build()
104 .orderedNodes()
105 .filter(mn -> roots.contains(mn) && !mods.contains(mn))
106 .forEach(mn -> {
107 // Compute hashes of the modules that depend on mn directly and
108 // indirectly excluding itself.
109 Set<String> ns = transposedGraph.dfs(mn)
110 .stream()
111 .filter(n -> !n.equals(mn) && hashModuleCandidates.contains(n))
112 .collect(toSet());
113 mods.add(mn);
114 mods.addAll(ns);
115
116 if (!ns.isEmpty()) {
117 Map<String, Path> moduleToPath = ns.stream()
118 .collect(toMap(Function.identity(), this::moduleToPath));
119 hashes.put(mn, ModuleHashes.generate(moduleToPath, "SHA-256"));
120 }
121 });
122 return hashes;
123 }
124
125 private Path moduleToPath(String name) {
126 ResolvedModule rm = configuration.findModule(name).orElseThrow(
127 () -> new InternalError("Selected module " + name + " not on module path"));
128
129 URI uri = rm.reference().location().get();
130 Path path = Path.of(uri);
131 String fn = path.getFileName().toString();
132 if (!fn.endsWith(".jar") && !fn.endsWith(".jmod")) {
133 throw new UnsupportedOperationException(path + " is not a modular JAR or jmod file");
134 }
135 return path;
136 }
137
138 /*
139 * Utility class
140 */
141 static class Graph<T> {
142 private final Set<T> nodes;
143 private final Map<T, Set<T>> edges;
144
145 public Graph(Set<T> nodes, Map<T, Set<T>> edges) {
146 this.nodes = Collections.unmodifiableSet(nodes);
147 this.edges = Collections.unmodifiableMap(edges);
148 }
149
150 public Set<T> nodes() {
151 return nodes;
152 }
153
154 public Map<T, Set<T>> edges() {
155 return edges;
156 }
157
158 public Set<T> adjacentNodes(T u) {
159 return edges.get(u);
160 }
161
162 public boolean contains(T u) {
163 return nodes.contains(u);
164 }
165
166 /**
167 * Returns nodes sorted in topological order.
168 */
169 public Stream<T> orderedNodes() {
170 TopoSorter<T> sorter = new TopoSorter<>(this);
171 return sorter.result.stream();
172 }
173
174 /**
175 * Traverses this graph and performs the given action in topological order.
176 */
177 public void ordered(Consumer<T> action) {
178 TopoSorter<T> sorter = new TopoSorter<>(this);
179 sorter.ordered(action);
180 }
181
182 /**
183 * Traverses this graph and performs the given action in reverse topological order.
184 */
185 public void reverse(Consumer<T> action) {
186 TopoSorter<T> sorter = new TopoSorter<>(this);
187 sorter.reverse(action);
188 }
189
190 /**
191 * Returns a transposed graph from this graph.
192 */
193 public Graph<T> transpose() {
194 Builder<T> builder = new Builder<>();
195 nodes.forEach(builder::addNode);
196 // reverse edges
197 edges.keySet().forEach(u -> {
198 edges.get(u).forEach(v -> builder.addEdge(v, u));
199 });
200 return builder.build();
201 }
202
203 /**
204 * Returns all nodes reachable from the given root.
205 */
206 public Set<T> dfs(T root) {
207 return dfs(Set.of(root));
208 }
209
210 /**
211 * Returns all nodes reachable from the given set of roots.
212 */
213 public Set<T> dfs(Set<T> roots) {
214 ArrayDeque<T> todo = new ArrayDeque<>(roots);
215 Set<T> visited = new HashSet<>();
216 T u;
217 while ((u = todo.poll()) != null) {
218 if (visited.add(u) && contains(u)) {
219 adjacentNodes(u).stream()
220 .filter(v -> !visited.contains(v))
221 .forEach(todo::push);
222 }
223 }
224 return visited;
225 }
226
227 public void printGraph(PrintStream out) {
228 out.println("graph for " + nodes);
229 nodes
230 .forEach(u -> adjacentNodes(u)
231 .forEach(v -> out.format(" %s -> %s%n", u, v)));
232 }
233
234 static class Builder<T> {
235 final Set<T> nodes = new HashSet<>();
236 final Map<T, Set<T>> edges = new HashMap<>();
237
238 public void addNode(T node) {
239 if (nodes.add(node)) {
240 edges.computeIfAbsent(node, _e -> new HashSet<>());
241 }
242 }
243
244 public void addEdge(T u, T v) {
245 addNode(u);
246 addNode(v);
247 edges.get(u).add(v);
248 }
249
250 public Graph<T> build() {
251 return new Graph<T>(nodes, edges);
252 }
253 }
254 }
255
256 /**
257 * Topological sort
258 */
259 private static class TopoSorter<T> {
260 final Deque<T> result = new ArrayDeque<>();
261 final Graph<T> graph;
262
263 TopoSorter(Graph<T> graph) {
264 this.graph = graph;
265 sort();
266 }
267
268 public void ordered(Consumer<T> action) {
269 result.forEach(action);
270 }
271
272 public void reverse(Consumer<T> action) {
273 result.descendingIterator().forEachRemaining(action);
274 }
275
276 private void sort() {
277 Set<T> visited = new HashSet<>();
278 Deque<T> stack = new ArrayDeque<>();
279 graph.nodes.forEach(node -> visit(node, visited, stack));
280 }
281
282 private Set<T> children(T node) {
283 return graph.edges().get(node);
284 }
285
286 private void visit(T node, Set<T> visited, Deque<T> stack) {
287 if (visited.add(node)) {
288 stack.push(node);
289 children(node).forEach(child -> visit(child, visited, stack));
290 stack.pop();
291 result.addLast(node);
292 }
293 else if (stack.contains(node)) {
294 throw new IllegalArgumentException(
295 "Cycle detected: " + node + " -> " + children(node));
296 }
297 }
298 }
299 }