< prev index next >

src/java.base/share/classes/jdk/internal/module/ModuleHashesBuilder.java

Print this page
8200134: Improve ModuleHashesBuilder
Reviewed-by: mchung, alanb


  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.LinkedList;
  39 import java.util.Map;
  40 import java.util.Set;
  41 import java.util.function.Consumer;
  42 import java.util.function.Function;
  43 import java.util.stream.Stream;
  44 import static java.util.stream.Collectors.*;
  45 
  46 /**
  47  * A Builder to compute ModuleHashes from a given configuration
  48  */
  49 public class ModuleHashesBuilder {
  50     private final Configuration configuration;
  51     private final Set<String> hashModuleCandidates;
  52 
  53     /**
  54      * Constructs a ModuleHashesBuilder that finds the packaged modules
  55      * from the location of ModuleReference found from the given Configuration.
  56      *
  57      * @param config Configuration for building module hashes
  58      * @param modules the candidate modules to be hashed
  59      */
  60     public ModuleHashesBuilder(Configuration config, Set<String> modules) {
  61         this.configuration = config;
  62         this.hashModuleCandidates = modules;
  63     }
  64 
  65     /**
  66      * Returns a map of a module M to ModuleHashes for the modules
  67      * that depend upon M directly or indirectly.
  68      *
  69      * The key for each entry in the returned map is a module M that has
  70      * no outgoing edges to any of the candidate modules to be hashed
  71      * i.e. M is a leaf node in a connected subgraph containing M and
  72      * other candidate modules from the module graph filtering
  73      * the outgoing edges from M to non-candidate modules.
  74      */
  75     public Map<String, ModuleHashes> computeHashes(Set<String> roots) {
  76         // build a graph containing the packaged modules and
  77         // its transitive dependences matching --hash-modules
  78         Graph.Builder<String> builder = new Graph.Builder<>();
  79         Deque<ResolvedModule> deque = new ArrayDeque<>(configuration.modules());
  80         Set<ResolvedModule> visited = new HashSet<>();
  81         while (!deque.isEmpty()) {
  82             ResolvedModule rm = deque.pop();
  83             if (!visited.contains(rm)) {
  84                 visited.add(rm);
  85                 builder.addNode(rm.name());
  86                 for (ResolvedModule dm : rm.reads()) {
  87                     if (!visited.contains(dm)) {
  88                         deque.push(dm);
  89                     }
  90                     builder.addEdge(rm.name(), dm.name());
  91                 }
  92             }
  93         }
  94 
  95         // each node in a transposed graph is a matching packaged module
  96         // in which the hash of the modules that depend upon it is recorded
  97         Graph<String> transposedGraph = builder.build().transpose();
  98 
  99         // traverse the modules in topological order that will identify
 100         // the modules to record the hashes - it is the first matching
 101         // module and has not been hashed during the traversal.
 102         Set<String> mods = new HashSet<>();
 103         Map<String, ModuleHashes> hashes = new HashMap<>();
 104         builder.build()
 105                .orderedNodes()
 106                .filter(mn -> roots.contains(mn) && !mods.contains(mn))
 107                .forEach(mn -> {
 108                    // Compute hashes of the modules that depend on mn directly and


 195             Builder<T> builder = new Builder<>();
 196             nodes.forEach(builder::addNode);
 197             // reverse edges
 198             edges.keySet().forEach(u -> {
 199                 edges.get(u).forEach(v -> builder.addEdge(v, u));
 200             });
 201             return builder.build();
 202         }
 203 
 204         /**
 205          * Returns all nodes reachable from the given root.
 206          */
 207         public Set<T> dfs(T root) {
 208             return dfs(Set.of(root));
 209         }
 210 
 211         /**
 212          * Returns all nodes reachable from the given set of roots.
 213          */
 214         public Set<T> dfs(Set<T> roots) {
 215             Deque<T> deque = new LinkedList<>(roots);
 216             Set<T> visited = new HashSet<>();
 217             while (!deque.isEmpty()) {
 218                 T u = deque.pop();
 219                 if (!visited.contains(u)) {
 220                     visited.add(u);
 221                     if (contains(u)) {
 222                         adjacentNodes(u).stream()
 223                             .filter(v -> !visited.contains(v))
 224                             .forEach(deque::push);
 225                     }
 226                 }
 227             }
 228             return visited;
 229         }
 230 
 231         public void printGraph(PrintStream out) {
 232             out.println("graph for " + nodes);
 233             nodes
 234                 .forEach(u -> adjacentNodes(u)
 235                     .forEach(v -> out.format("  %s -> %s%n", u, v)));
 236         }
 237 
 238         static class Builder<T> {
 239             final Set<T> nodes = new HashSet<>();
 240             final Map<T, Set<T>> edges = new HashMap<>();
 241 
 242             public void addNode(T node) {
 243                 if (nodes.contains(node)) {
 244                     return;
 245                 }
 246                 nodes.add(node);
 247                 edges.computeIfAbsent(node, _e -> new HashSet<>());
 248             }

 249 
 250             public void addEdge(T u, T v) {
 251                 addNode(u);
 252                 addNode(v);
 253                 edges.get(u).add(v);
 254             }
 255 
 256             public Graph<T> build() {
 257                 return new Graph<T>(nodes, edges);
 258             }
 259         }
 260     }
 261 
 262     /**
 263      * Topological sort
 264      */
 265     private static class TopoSorter<T> {
 266         final Deque<T> result = new LinkedList<>();
 267         final Deque<T> nodes;
 268         final Graph<T> graph;
 269 
 270         TopoSorter(Graph<T> graph) {
 271             this.graph = graph;
 272             this.nodes = new LinkedList<>(graph.nodes);
 273             sort();
 274         }
 275 
 276         public void ordered(Consumer<T> action) {
 277             result.iterator().forEachRemaining(action);
 278         }
 279 
 280         public void reverse(Consumer<T> action) {
 281             result.descendingIterator().forEachRemaining(action);
 282         }
 283 
 284         private void sort() {
 285             Deque<T> visited = new LinkedList<>();
 286             Deque<T> done = new LinkedList<>();
 287             T node;
 288             while ((node = nodes.poll()) != null) {
 289                 if (!visited.contains(node)) {
 290                     visit(node, visited, done);
 291                 }
 292             }



 293         }
 294 
 295         private void visit(T node, Deque<T> visited, Deque<T> done) {
 296             if (visited.contains(node)) {
 297                 if (!done.contains(node)) {
 298                     throw new IllegalArgumentException("Cyclic detected: " +
 299                         node + " " + graph.edges().get(node));

 300                 }
 301                 return;


 302             }
 303             visited.add(node);
 304             graph.edges().get(node)
 305                 .forEach(x -> visit(x, visited, done));
 306             done.add(node);
 307             result.addLast(node);
 308         }
 309     }
 310 }


  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


 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 }
< prev index next >