1 /* 2 * Copyright (c) 2017, 2018, 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.Map; 39 import java.util.Set; 40 import java.util.function.Consumer; 41 import java.util.function.Function; 42 import java.util.stream.Stream; 43 import static java.util.stream.Collectors.*; 44 45 /** 46 * A Builder to compute ModuleHashes from a given configuration 47 */ 48 public class ModuleHashesBuilder { 49 private final Configuration configuration; 50 private final Set<String> hashModuleCandidates; 51 52 /** 53 * Constructs a ModuleHashesBuilder that finds the packaged modules 54 * from the location of ModuleReference found from the given Configuration. 55 * 56 * @param config Configuration for building module hashes 57 * @param modules the candidate modules to be hashed 58 */ ModuleHashesBuilder(Configuration config, Set<String> modules)59 public ModuleHashesBuilder(Configuration config, Set<String> modules) { 60 this.configuration = config; 61 this.hashModuleCandidates = modules; 62 } 63 64 /** 65 * Returns a map of a module M to ModuleHashes for the modules 66 * that depend upon M directly or indirectly. 67 * 68 * The key for each entry in the returned map is a module M that has 69 * no outgoing edges to any of the candidate modules to be hashed 70 * i.e. M is a leaf node in a connected subgraph containing M and 71 * other candidate modules from the module graph filtering 72 * the outgoing edges from M to non-candidate modules. 73 */ computeHashes(Set<String> roots)74 public Map<String, ModuleHashes> computeHashes(Set<String> roots) { 75 // build a graph containing the packaged modules and 76 // its transitive dependences matching --hash-modules 77 Graph.Builder<String> builder = new Graph.Builder<>(); 78 Deque<ResolvedModule> todo = new ArrayDeque<>(configuration.modules()); 79 Set<ResolvedModule> visited = new HashSet<>(); 80 ResolvedModule rm; 81 while ((rm = todo.poll()) != null) { 82 if (visited.add(rm)) { 83 builder.addNode(rm.name()); 84 for (ResolvedModule dm : rm.reads()) { 85 if (!visited.contains(dm)) { 86 todo.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) && hashModuleCandidates.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 moduleToPath(String name)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 = Path.of(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 * Utility class 139 */ 140 static class Graph<T> { 141 private final Set<T> nodes; 142 private final Map<T, Set<T>> edges; 143 Graph(Set<T> nodes, Map<T, Set<T>> edges)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 nodes()149 public Set<T> nodes() { 150 return nodes; 151 } 152 edges()153 public Map<T, Set<T>> edges() { 154 return edges; 155 } 156 adjacentNodes(T u)157 public Set<T> adjacentNodes(T u) { 158 return edges.get(u); 159 } 160 contains(T u)161 public boolean contains(T u) { 162 return nodes.contains(u); 163 } 164 165 /** 166 * Returns nodes sorted in topological order. 167 */ orderedNodes()168 public Stream<T> orderedNodes() { 169 TopoSorter<T> sorter = new TopoSorter<>(this); 170 return sorter.result.stream(); 171 } 172 173 /** 174 * Traverses this graph and performs the given action in topological order. 175 */ ordered(Consumer<T> action)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 */ reverse(Consumer<T> action)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 */ transpose()192 public Graph<T> transpose() { 193 Builder<T> builder = new Builder<>(); 194 nodes.forEach(builder::addNode); 195 // reverse edges 196 edges.keySet().forEach(u -> { 197 edges.get(u).forEach(v -> builder.addEdge(v, u)); 198 }); 199 return builder.build(); 200 } 201 202 /** 203 * Returns all nodes reachable from the given root. 204 */ dfs(T root)205 public Set<T> dfs(T root) { 206 return dfs(Set.of(root)); 207 } 208 209 /** 210 * Returns all nodes reachable from the given set of roots. 211 */ dfs(Set<T> roots)212 public Set<T> dfs(Set<T> roots) { 213 ArrayDeque<T> todo = new ArrayDeque<>(roots); 214 Set<T> visited = new HashSet<>(); 215 T u; 216 while ((u = todo.poll()) != null) { 217 if (visited.add(u) && contains(u)) { 218 adjacentNodes(u).stream() 219 .filter(v -> !visited.contains(v)) 220 .forEach(todo::push); 221 } 222 } 223 return visited; 224 } 225 printGraph(PrintStream out)226 public void printGraph(PrintStream out) { 227 out.println("graph for " + nodes); 228 nodes 229 .forEach(u -> adjacentNodes(u) 230 .forEach(v -> out.format(" %s -> %s%n", u, v))); 231 } 232 233 static class Builder<T> { 234 final Set<T> nodes = new HashSet<>(); 235 final Map<T, Set<T>> edges = new HashMap<>(); 236 addNode(T node)237 public void addNode(T node) { 238 if (nodes.add(node)) { 239 edges.computeIfAbsent(node, _e -> new HashSet<>()); 240 } 241 } 242 addEdge(T u, T v)243 public void addEdge(T u, T v) { 244 addNode(u); 245 addNode(v); 246 edges.get(u).add(v); 247 } 248 build()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 ArrayDeque<>(); 260 final Graph<T> graph; 261 TopoSorter(Graph<T> graph)262 TopoSorter(Graph<T> graph) { 263 this.graph = graph; 264 sort(); 265 } 266 ordered(Consumer<T> action)267 public void ordered(Consumer<T> action) { 268 result.forEach(action); 269 } 270 reverse(Consumer<T> action)271 public void reverse(Consumer<T> action) { 272 result.descendingIterator().forEachRemaining(action); 273 } 274 sort()275 private void sort() { 276 Set<T> visited = new HashSet<>(); 277 Deque<T> stack = new ArrayDeque<>(); 278 graph.nodes.forEach(node -> visit(node, visited, stack)); 279 } 280 children(T node)281 private Set<T> children(T node) { 282 return graph.edges().get(node); 283 } 284 visit(T node, Set<T> visited, Deque<T> stack)285 private void visit(T node, Set<T> visited, Deque<T> stack) { 286 if (visited.add(node)) { 287 stack.push(node); 288 children(node).forEach(child -> visit(child, visited, stack)); 289 stack.pop(); 290 result.addLast(node); 291 } 292 else if (stack.contains(node)) { 293 throw new IllegalArgumentException( 294 "Cycle detected: " + node + " -> " + children(node)); 295 } 296 } 297 } 298 } 299