Sat, 14 Sep 2013 19:04:47 +0100
7047734: javac, the LVT is not generated correctly in several scenarios
Reviewed-by: jjg, mcimadamore
mcimadamore@1562 | 1 | /* |
mcimadamore@1562 | 2 | * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved. |
mcimadamore@1562 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
mcimadamore@1562 | 4 | * |
mcimadamore@1562 | 5 | * This code is free software; you can redistribute it and/or modify it |
mcimadamore@1562 | 6 | * under the terms of the GNU General Public License version 2 only, as |
mcimadamore@1562 | 7 | * published by the Free Software Foundation. Oracle designates this |
mcimadamore@1562 | 8 | * particular file as subject to the "Classpath" exception as provided |
mcimadamore@1562 | 9 | * by Oracle in the LICENSE file that accompanied this code. |
mcimadamore@1562 | 10 | * |
mcimadamore@1562 | 11 | * This code is distributed in the hope that it will be useful, but WITHOUT |
mcimadamore@1562 | 12 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
mcimadamore@1562 | 13 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
mcimadamore@1562 | 14 | * version 2 for more details (a copy is included in the LICENSE file that |
mcimadamore@1562 | 15 | * accompanied this code). |
mcimadamore@1562 | 16 | * |
mcimadamore@1562 | 17 | * You should have received a copy of the GNU General Public License version |
mcimadamore@1562 | 18 | * 2 along with this work; if not, write to the Free Software Foundation, |
mcimadamore@1562 | 19 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
mcimadamore@1562 | 20 | * |
mcimadamore@1562 | 21 | * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
mcimadamore@1562 | 22 | * or visit www.oracle.com if you need additional information or have any |
mcimadamore@1562 | 23 | * questions. |
mcimadamore@1562 | 24 | */ |
mcimadamore@1562 | 25 | |
mcimadamore@1562 | 26 | package com.sun.tools.javac.util; |
mcimadamore@1562 | 27 | |
mcimadamore@1562 | 28 | /** <p><b>This is NOT part of any supported API. |
mcimadamore@1562 | 29 | * If you write code that depends on this, you do so at your own risk. |
mcimadamore@1562 | 30 | * This code and its internal interfaces are subject to change or |
mcimadamore@1562 | 31 | * deletion without notice.</b> |
mcimadamore@1562 | 32 | */ |
mcimadamore@1562 | 33 | public class GraphUtils { |
mcimadamore@1562 | 34 | |
mcimadamore@1562 | 35 | /** |
vromero@2000 | 36 | * Basic interface for defining various dependency kinds. All dependency kinds |
vromero@2000 | 37 | * must at least support basic capabilities to tell the DOT engine how to render them. |
vromero@2000 | 38 | */ |
vromero@2000 | 39 | public interface DependencyKind { |
vromero@2000 | 40 | /** |
vromero@2000 | 41 | * Returns the DOT representation (to be used in a {@code style} attribute |
vromero@2000 | 42 | * that's most suited for this dependency kind. |
vromero@2000 | 43 | */ |
vromero@2000 | 44 | String getDotStyle(); |
vromero@2000 | 45 | } |
vromero@2000 | 46 | |
vromero@2000 | 47 | /** |
mcimadamore@1562 | 48 | * This class is a basic abstract class for representing a node. |
mcimadamore@1562 | 49 | * A node is associated with a given data. |
mcimadamore@1562 | 50 | */ |
mcimadamore@1562 | 51 | public static abstract class Node<D> { |
mcimadamore@1562 | 52 | public final D data; |
mcimadamore@1562 | 53 | |
mcimadamore@1562 | 54 | public Node(D data) { |
mcimadamore@1562 | 55 | this.data = data; |
mcimadamore@1562 | 56 | } |
mcimadamore@1562 | 57 | |
vromero@2000 | 58 | /** |
vromero@2000 | 59 | * Get an array of the dependency kinds supported by this node. |
vromero@2000 | 60 | */ |
vromero@2000 | 61 | public abstract DependencyKind[] getSupportedDependencyKinds(); |
mcimadamore@1562 | 62 | |
vromero@2000 | 63 | /** |
vromero@2000 | 64 | * Get all dependencies, regardless of their kind. |
vromero@2000 | 65 | */ |
vromero@2000 | 66 | public abstract Iterable<? extends Node<D>> getAllDependencies(); |
vromero@2000 | 67 | |
vromero@2000 | 68 | /** |
vromero@2000 | 69 | * Get a name for the dependency (of given kind) linking this node to a given node |
vromero@2000 | 70 | */ |
vromero@2000 | 71 | public abstract String getDependencyName(Node<D> to, DependencyKind dk); |
mcimadamore@1562 | 72 | |
mcimadamore@1562 | 73 | @Override |
mcimadamore@1562 | 74 | public String toString() { |
mcimadamore@1562 | 75 | return data.toString(); |
mcimadamore@1562 | 76 | } |
mcimadamore@1562 | 77 | } |
mcimadamore@1562 | 78 | |
mcimadamore@1562 | 79 | /** |
mcimadamore@1562 | 80 | * This class specialized Node, by adding elements that are required in order |
mcimadamore@1562 | 81 | * to perform Tarjan computation of strongly connected components. |
mcimadamore@1562 | 82 | */ |
mcimadamore@1562 | 83 | public static abstract class TarjanNode<D> extends Node<D> implements Comparable<TarjanNode<D>> { |
mcimadamore@1562 | 84 | int index = -1; |
mcimadamore@1562 | 85 | int lowlink; |
mcimadamore@1562 | 86 | boolean active; |
mcimadamore@1562 | 87 | |
mcimadamore@1562 | 88 | public TarjanNode(D data) { |
mcimadamore@1562 | 89 | super(data); |
mcimadamore@1562 | 90 | } |
mcimadamore@1562 | 91 | |
vromero@2000 | 92 | public abstract Iterable<? extends TarjanNode<D>> getAllDependencies(); |
vromero@2000 | 93 | |
vromero@2000 | 94 | public abstract Iterable<? extends TarjanNode<D>> getDependenciesByKind(DependencyKind dk); |
mcimadamore@1562 | 95 | |
mcimadamore@1562 | 96 | public int compareTo(TarjanNode<D> o) { |
mcimadamore@1562 | 97 | return (index < o.index) ? -1 : (index == o.index) ? 0 : 1; |
mcimadamore@1562 | 98 | } |
mcimadamore@1562 | 99 | } |
mcimadamore@1562 | 100 | |
mcimadamore@1562 | 101 | /** |
mcimadamore@1562 | 102 | * Tarjan's algorithm to determine strongly connected components of a |
mcimadamore@1562 | 103 | * directed graph in linear time. Works on TarjanNode. |
mcimadamore@1562 | 104 | */ |
mcimadamore@1562 | 105 | public static <D, N extends TarjanNode<D>> List<? extends List<? extends N>> tarjan(Iterable<? extends N> nodes) { |
mcimadamore@1562 | 106 | ListBuffer<List<N>> cycles = ListBuffer.lb(); |
mcimadamore@1562 | 107 | ListBuffer<N> stack = ListBuffer.lb(); |
mcimadamore@1562 | 108 | int index = 0; |
mcimadamore@1562 | 109 | for (N node: nodes) { |
mcimadamore@1562 | 110 | if (node.index == -1) { |
mcimadamore@1562 | 111 | index += tarjan(node, index, stack, cycles); |
mcimadamore@1562 | 112 | } |
mcimadamore@1562 | 113 | } |
mcimadamore@1562 | 114 | return cycles.toList(); |
mcimadamore@1562 | 115 | } |
mcimadamore@1562 | 116 | |
mcimadamore@1562 | 117 | private static <D, N extends TarjanNode<D>> int tarjan(N v, int index, ListBuffer<N> stack, ListBuffer<List<N>> cycles) { |
mcimadamore@1562 | 118 | v.index = index; |
mcimadamore@1562 | 119 | v.lowlink = index; |
mcimadamore@1562 | 120 | index++; |
mcimadamore@1562 | 121 | stack.prepend(v); |
mcimadamore@1562 | 122 | v.active = true; |
vromero@2000 | 123 | for (TarjanNode<D> nd: v.getAllDependencies()) { |
mcimadamore@1562 | 124 | @SuppressWarnings("unchecked") |
mcimadamore@1562 | 125 | N n = (N)nd; |
mcimadamore@1562 | 126 | if (n.index == -1) { |
mcimadamore@1562 | 127 | tarjan(n, index, stack, cycles); |
mcimadamore@1562 | 128 | v.lowlink = Math.min(v.lowlink, n.lowlink); |
mcimadamore@1562 | 129 | } else if (stack.contains(n)) { |
mcimadamore@1562 | 130 | v.lowlink = Math.min(v.lowlink, n.index); |
mcimadamore@1562 | 131 | } |
mcimadamore@1562 | 132 | } |
mcimadamore@1562 | 133 | if (v.lowlink == v.index) { |
mcimadamore@1562 | 134 | N n; |
mcimadamore@1562 | 135 | ListBuffer<N> cycle = ListBuffer.lb(); |
mcimadamore@1562 | 136 | do { |
mcimadamore@1562 | 137 | n = stack.remove(); |
mcimadamore@1562 | 138 | n.active = false; |
mcimadamore@1562 | 139 | cycle.add(n); |
mcimadamore@1562 | 140 | } while (n != v); |
mcimadamore@1562 | 141 | cycles.add(cycle.toList()); |
mcimadamore@1562 | 142 | } |
mcimadamore@1562 | 143 | return index; |
mcimadamore@1562 | 144 | } |
mcimadamore@1562 | 145 | |
mcimadamore@1562 | 146 | /** |
mcimadamore@1562 | 147 | * Debugging: dot representation of a set of connected nodes. The resulting |
mcimadamore@1562 | 148 | * dot representation will use {@code Node.toString} to display node labels |
mcimadamore@1562 | 149 | * and {@code Node.printDependency} to display edge labels. The resulting |
mcimadamore@1562 | 150 | * representation is also customizable with a graph name and a header. |
mcimadamore@1562 | 151 | */ |
mcimadamore@1562 | 152 | public static <D> String toDot(Iterable<? extends TarjanNode<D>> nodes, String name, String header) { |
mcimadamore@1562 | 153 | StringBuilder buf = new StringBuilder(); |
mcimadamore@1562 | 154 | buf.append(String.format("digraph %s {\n", name)); |
mcimadamore@1562 | 155 | buf.append(String.format("label = \"%s\";\n", header)); |
mcimadamore@1562 | 156 | //dump nodes |
mcimadamore@1562 | 157 | for (TarjanNode<D> n : nodes) { |
mcimadamore@1562 | 158 | buf.append(String.format("%s [label = \"%s\"];\n", n.hashCode(), n.toString())); |
mcimadamore@1562 | 159 | } |
mcimadamore@1562 | 160 | //dump arcs |
mcimadamore@1562 | 161 | for (TarjanNode<D> from : nodes) { |
vromero@2000 | 162 | for (DependencyKind dk : from.getSupportedDependencyKinds()) { |
vromero@2000 | 163 | for (TarjanNode<D> to : from.getDependenciesByKind(dk)) { |
vromero@2000 | 164 | buf.append(String.format("%s -> %s [label = \" %s \" style = %s ];\n", |
vromero@2000 | 165 | from.hashCode(), to.hashCode(), from.getDependencyName(to, dk), dk.getDotStyle())); |
vromero@2000 | 166 | } |
mcimadamore@1562 | 167 | } |
mcimadamore@1562 | 168 | } |
mcimadamore@1562 | 169 | buf.append("}\n"); |
mcimadamore@1562 | 170 | return buf.toString(); |
mcimadamore@1562 | 171 | } |
mcimadamore@1562 | 172 | } |