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      */
  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      */
  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 
 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 
 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          * Traverses 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.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          */
 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          */
 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 
 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 
 237             public void addNode(T node) {
 238                 if (nodes.add(node)) {
 239                     edges.computeIfAbsent(node, _e -> new HashSet<>());
 240                 }
 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 ArrayDeque<>();
 260         final Graph<T> graph;
 261 
 262         TopoSorter(Graph<T> graph) {
 263             this.graph = graph;
 264             sort();
 265         }
 266 
 267         public void ordered(Consumer<T> action) {
 268             result.forEach(action);
 269         }
 270 
 271         public void reverse(Consumer<T> action) {
 272             result.descendingIterator().forEachRemaining(action);
 273         }
 274 
 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 
 281         private Set<T> children(T node) {
 282             return graph.edges().get(node);
 283         }
 284 
 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 }