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