1 /* |
1 /* |
2 * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved. |
2 * Copyright (c) 2016, 2017, Oracle and/or its affiliates. All rights reserved. |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 * |
4 * |
5 * This code is free software; you can redistribute it and/or modify it |
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 |
6 * under the terms of the GNU General Public License version 2 only, as |
7 * published by the Free Software Foundation. Oracle designates this |
7 * published by the Free Software Foundation. Oracle designates this |
23 * questions. |
23 * questions. |
24 */ |
24 */ |
25 package com.sun.tools.jdeps; |
25 package com.sun.tools.jdeps; |
26 |
26 |
27 import java.io.PrintWriter; |
27 import java.io.PrintWriter; |
28 import java.lang.module.ModuleDescriptor; |
28 import java.util.ArrayDeque; |
29 import java.lang.module.ModuleFinder; |
|
30 import java.lang.module.ModuleReference; |
|
31 import java.util.Collections; |
29 import java.util.Collections; |
32 import java.util.Deque; |
30 import java.util.Deque; |
33 import java.util.HashMap; |
31 import java.util.HashMap; |
34 import java.util.HashSet; |
32 import java.util.HashSet; |
35 import java.util.LinkedList; |
|
36 import java.util.Map; |
33 import java.util.Map; |
37 import java.util.Set; |
34 import java.util.Set; |
38 import java.util.function.Consumer; |
35 import java.util.function.Consumer; |
39 import java.util.function.Predicate; |
|
40 import java.util.stream.Collectors; |
36 import java.util.stream.Collectors; |
41 import java.util.stream.Stream; |
37 import java.util.stream.Stream; |
42 |
38 |
43 public final class Graph<T> { |
39 public final class Graph<T> { |
44 private final Set<T> nodes; |
40 private final Set<T> nodes; |
159 |
155 |
160 /** |
156 /** |
161 * Returns all nodes reachable from the given set of roots. |
157 * Returns all nodes reachable from the given set of roots. |
162 */ |
158 */ |
163 public Set<T> dfs(Set<T> roots) { |
159 public Set<T> dfs(Set<T> roots) { |
164 Deque<T> deque = new LinkedList<>(roots); |
160 Deque<T> deque = new ArrayDeque<>(roots); |
165 Set<T> visited = new HashSet<>(); |
161 Set<T> visited = new HashSet<>(); |
166 while (!deque.isEmpty()) { |
162 while (!deque.isEmpty()) { |
167 T u = deque.pop(); |
163 T u = deque.pop(); |
168 if (!visited.contains(u)) { |
164 if (!visited.contains(u)) { |
169 visited.add(u); |
165 visited.add(u); |
195 return false; |
191 return false; |
196 } |
192 } |
197 if (includeAdjacent && isAdjacent(u, v)) { |
193 if (includeAdjacent && isAdjacent(u, v)) { |
198 return true; |
194 return true; |
199 } |
195 } |
200 Deque<T> stack = new LinkedList<>(); |
196 Deque<T> stack = new ArrayDeque<>(); |
201 Set<T> visited = new HashSet<>(); |
197 Set<T> visited = new HashSet<>(); |
202 stack.push(u); |
198 stack.push(u); |
203 while (!stack.isEmpty()) { |
199 while (!stack.isEmpty()) { |
204 T node = stack.pop(); |
200 T node = stack.pop(); |
205 if (node.equals(v)) { |
201 if (node.equals(v)) { |
290 |
286 |
291 /** |
287 /** |
292 * Topological sort |
288 * Topological sort |
293 */ |
289 */ |
294 static class TopoSorter<T> { |
290 static class TopoSorter<T> { |
295 final Deque<T> result = new LinkedList<>(); |
291 final Deque<T> result = new ArrayDeque<>(); |
296 final Deque<T> nodes; |
|
297 final Graph<T> graph; |
292 final Graph<T> graph; |
298 TopoSorter(Graph<T> graph) { |
293 TopoSorter(Graph<T> graph) { |
299 this.graph = graph; |
294 this.graph = graph; |
300 this.nodes = new LinkedList<>(graph.nodes); |
|
301 sort(); |
295 sort(); |
302 } |
296 } |
303 |
297 |
304 public void ordered(Consumer<T> action) { |
298 public void ordered(Consumer<T> action) { |
305 result.iterator().forEachRemaining(action); |
299 result.iterator().forEachRemaining(action); |
308 public void reverse(Consumer<T> action) { |
302 public void reverse(Consumer<T> action) { |
309 result.descendingIterator().forEachRemaining(action); |
303 result.descendingIterator().forEachRemaining(action); |
310 } |
304 } |
311 |
305 |
312 private void sort() { |
306 private void sort() { |
313 Deque<T> visited = new LinkedList<>(); |
307 Set<T> visited = new HashSet<>(); |
314 Deque<T> done = new LinkedList<>(); |
308 Set<T> done = new HashSet<>(); |
315 T node; |
309 for (T node : graph.nodes()) { |
316 while ((node = nodes.poll()) != null) { |
|
317 if (!visited.contains(node)) { |
310 if (!visited.contains(node)) { |
318 visit(node, visited, done); |
311 visit(node, visited, done); |
319 } |
312 } |
320 } |
313 } |
321 } |
314 } |
322 |
315 |
323 private void visit(T node, Deque<T> visited, Deque<T> done) { |
316 private void visit(T node, Set<T> visited, Set<T> done) { |
324 if (visited.contains(node)) { |
317 if (visited.contains(node)) { |
325 if (!done.contains(node)) { |
318 if (!done.contains(node)) { |
326 throw new IllegalArgumentException("Cyclic detected: " + |
319 throw new IllegalArgumentException("Cyclic detected: " + |
327 node + " " + graph.edges().get(node)); |
320 node + " " + graph.edges().get(node)); |
328 } |
321 } |
329 return; |
322 return; |
330 } |
323 } |
331 visited.add(node); |
324 visited.add(node); |
332 graph.edges().get(node).stream() |
325 graph.edges().get(node).stream() |
333 .forEach(x -> visit(x, visited, done)); |
326 .forEach(x -> visit(x, visited, done)); |
334 done.add(node); |
327 done.add(node); |
335 result.addLast(node); |
328 result.addLast(node); |
336 } |
329 } |
337 } |
330 } |
338 } |
331 } |