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 26package jdk.internal.module; 27 28import java.io.PrintStream; 29import java.lang.module.Configuration; 30import java.lang.module.ResolvedModule; 31import java.net.URI; 32import java.nio.file.Path; 33import java.nio.file.Paths; 34import java.util.ArrayDeque; 35import java.util.Collections; 36import java.util.Deque; 37import java.util.HashMap; 38import java.util.HashSet; 39import java.util.LinkedList; 40import java.util.Map; 41import java.util.Set; 42import java.util.function.Consumer; 43import java.util.function.Function; 44import java.util.stream.Stream; 45import static java.util.stream.Collectors.*; 46 47/** 48 * A Builder to compute ModuleHashes from a given configuration 49 */ 50public 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 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} 313