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