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