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 }
|