1.1 --- a/src/share/classes/com/sun/tools/javac/util/GraphUtils.java Mon Jan 25 08:48:11 2016 +0000
1.2 +++ b/src/share/classes/com/sun/tools/javac/util/GraphUtils.java Tue Jan 26 21:08:18 2016 +0000
1.3 @@ -103,34 +103,60 @@
1.4 * directed graph in linear time. Works on TarjanNode.
1.5 */
1.6 public static <D, N extends TarjanNode<D>> List<? extends List<? extends N>> tarjan(Iterable<? extends N> nodes) {
1.7 - ListBuffer<List<N>> cycles = new ListBuffer<>();
1.8 + Tarjan<D, N> tarjan = new Tarjan<>();
1.9 + return tarjan.findSCC(nodes);
1.10 + }
1.11 +
1.12 + //where
1.13 + private static class Tarjan<D, N extends TarjanNode<D>> {
1.14 +
1.15 + /** Unique node identifier. */
1.16 + int index = 0;
1.17 +
1.18 + /** List of SCCs found so far. */
1.19 + ListBuffer<List<N>> sccs = new ListBuffer<>();
1.20 +
1.21 + /** Stack of all reacheable nodes from given root. */
1.22 ListBuffer<N> stack = new ListBuffer<>();
1.23 - int index = 0;
1.24 - for (N node: nodes) {
1.25 - if (node.index == -1) {
1.26 - index += tarjan(node, index, stack, cycles);
1.27 +
1.28 + private List<? extends List<? extends N>> findSCC(Iterable<? extends N> nodes) {
1.29 + for (N node : nodes) {
1.30 + if (node.index == -1) {
1.31 + findSCC(node);
1.32 + }
1.33 + }
1.34 + return sccs.toList();
1.35 + }
1.36 +
1.37 + private void findSCC(N v) {
1.38 + visitNode(v);
1.39 + for (TarjanNode<D> tn : v.getAllDependencies()) {
1.40 + @SuppressWarnings("unchecked")
1.41 + N n = (N)tn;
1.42 + if (n.index == -1) {
1.43 + //it's the first time we see this node
1.44 + findSCC(n);
1.45 + v.lowlink = Math.min(v.lowlink, n.lowlink);
1.46 + } else if (stack.contains(n)) {
1.47 + //this node is already reachable from current root
1.48 + v.lowlink = Math.min(v.lowlink, n.index);
1.49 + }
1.50 + }
1.51 + if (v.lowlink == v.index) {
1.52 + //v is the root of a SCC
1.53 + addSCC(v);
1.54 }
1.55 }
1.56 - return cycles.toList();
1.57 - }
1.58
1.59 - private static <D, N extends TarjanNode<D>> int tarjan(N v, int index, ListBuffer<N> stack, ListBuffer<List<N>> cycles) {
1.60 - v.index = index;
1.61 - v.lowlink = index;
1.62 - index++;
1.63 - stack.prepend(v);
1.64 - v.active = true;
1.65 - for (TarjanNode<D> nd: v.getAllDependencies()) {
1.66 - @SuppressWarnings("unchecked")
1.67 - N n = (N)nd;
1.68 - if (n.index == -1) {
1.69 - tarjan(n, index, stack, cycles);
1.70 - v.lowlink = Math.min(v.lowlink, n.lowlink);
1.71 - } else if (stack.contains(n)) {
1.72 - v.lowlink = Math.min(v.lowlink, n.index);
1.73 - }
1.74 + private void visitNode(N n) {
1.75 + n.index = index;
1.76 + n.lowlink = index;
1.77 + index++;
1.78 + stack.prepend(n);
1.79 + n.active = true;
1.80 }
1.81 - if (v.lowlink == v.index) {
1.82 +
1.83 + private void addSCC(N v) {
1.84 N n;
1.85 ListBuffer<N> cycle = new ListBuffer<>();
1.86 do {
1.87 @@ -138,9 +164,8 @@
1.88 n.active = false;
1.89 cycle.add(n);
1.90 } while (n != v);
1.91 - cycles.add(cycle.toList());
1.92 + sccs.add(cycle.toList());
1.93 }
1.94 - return index;
1.95 }
1.96
1.97 /**
