GraphUtils.java revision 2990:70c852df047c
1/* 2 * Copyright (c) 1999, 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 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 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 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 26package com.sun.tools.javac.util; 27 28import java.util.ArrayList; 29import java.util.Collection; 30import java.util.Properties; 31 32/** <p><b>This is NOT part of any supported API. 33 * If you write code that depends on this, you do so at your own risk. 34 * This code and its internal interfaces are subject to change or 35 * deletion without notice.</b> 36 */ 37public class GraphUtils { 38 39 /** 40 * Basic interface for defining various dependency kinds. 41 */ 42 public interface DependencyKind { } 43 44 /** 45 * Common superinterfaces to all graph nodes. 46 */ 47 public interface Node<D, N extends Node<D, N>> { 48 /** 49 * visitor method. 50 */ 51 <A> void accept(NodeVisitor<D, N, A> visitor, A arg); 52 } 53 54 /** 55 * Visitor for graph nodes. 56 */ 57 static abstract class NodeVisitor<D, N extends Node<D, N>, A> { 58 /** 59 * Visitor action for nodes. 60 */ 61 public abstract void visitNode(N node, A arg); 62 /** 63 * Visitor action for a dependency between 'from' and 'to' with given kind. 64 */ 65 public abstract void visitDependency(DependencyKind dk, N from, N to, A arg); 66 67 /** 68 * Visitor entry point. 69 */ 70 public void visit(Collection<? extends N> nodes, A arg) { 71 for (N n : new ArrayList<>(nodes)) { 72 n.accept(this, arg); 73 } 74 } 75 } 76 77 /** 78 * Optional interface for nodes supporting dot-based representation. 79 */ 80 public interface DottableNode<D, N extends DottableNode<D, N>> extends Node<D, N> { 81 /** 82 * Retrieves the set of dot attributes associated with the node. 83 */ 84 Properties nodeAttributes(); 85 /** 86 * Retrieves the set of dot attributes associated with a given dependency. 87 */ 88 Properties dependencyAttributes(N to, DependencyKind dk); 89 } 90 91 /** 92 * This class is a basic abstract class for representing a node. 93 * A node is associated with a given data. 94 */ 95 public static abstract class AbstractNode<D, N extends AbstractNode<D, N>> implements Node<D, N> { 96 public final D data; 97 98 public AbstractNode(D data) { 99 this.data = data; 100 } 101 102 /** 103 * Get an array of the dependency kinds supported by this node. 104 */ 105 public abstract DependencyKind[] getSupportedDependencyKinds(); 106 107 /** 108 * Get all dependencies of a given kind 109 */ 110 public abstract Collection<? extends N> getDependenciesByKind(DependencyKind dk); 111 112 @Override 113 public String toString() { 114 return data.toString(); 115 } 116 117 @SuppressWarnings("unchecked") 118 public <A> void accept(NodeVisitor<D, N, A> visitor, A arg) { 119 visitor.visitNode((N)this, arg); 120 for (DependencyKind dk : getSupportedDependencyKinds()) { 121 for (N dep : new ArrayList<>(getDependenciesByKind(dk))) { 122 visitor.visitDependency(dk, (N)this, dep, arg); 123 } 124 } 125 } 126 } 127 128 /** 129 * This class specialized Node, by adding elements that are required in order 130 * to perform Tarjan computation of strongly connected components. 131 */ 132 public static abstract class TarjanNode<D, N extends TarjanNode<D, N>> extends AbstractNode<D, N> 133 implements Comparable<N> { 134 int index = -1; 135 int lowlink; 136 boolean active; 137 138 public TarjanNode(D data) { 139 super(data); 140 } 141 142 public abstract Iterable<? extends N> getAllDependencies(); 143 144 public int compareTo(N o) { 145 return (index < o.index) ? -1 : (index == o.index) ? 0 : 1; 146 } 147 } 148 149 /** 150 * Tarjan's algorithm to determine strongly connected components of a 151 * directed graph in linear time. Works on TarjanNode. 152 */ 153 public static <D, N extends TarjanNode<D, N>> List<? extends List<? extends N>> tarjan(Iterable<? extends N> nodes) { 154 Tarjan<D, N> tarjan = new Tarjan<>(); 155 return tarjan.findSCC(nodes); 156 } 157 //where 158 private static class Tarjan<D, N extends TarjanNode<D, N>> { 159 160 /** Unique node identifier. */ 161 int index = 0; 162 163 /** List of SCCs found fso far. */ 164 ListBuffer<List<N>> sccs = new ListBuffer<>(); 165 166 /** Stack of all reacheable nodes from given root. */ 167 ListBuffer<N> stack = new ListBuffer<>(); 168 169 private List<? extends List<? extends N>> findSCC(Iterable<? extends N> nodes) { 170 for (N node : nodes) { 171 if (node.index == -1) { 172 findSCC(node); 173 } 174 } 175 return sccs.toList(); 176 } 177 178 private void findSCC(N v) { 179 visitNode(v); 180 for (N n: v.getAllDependencies()) { 181 if (n.index == -1) { 182 //it's the first time we see this node 183 findSCC(n); 184 v.lowlink = Math.min(v.lowlink, n.lowlink); 185 } else if (stack.contains(n)) { 186 //this node is already reachable from current root 187 v.lowlink = Math.min(v.lowlink, n.index); 188 } 189 } 190 if (v.lowlink == v.index) { 191 //v is the root of a SCC 192 addSCC(v); 193 } 194 } 195 196 private void visitNode(N n) { 197 n.index = index; 198 n.lowlink = index; 199 index++; 200 stack.prepend(n); 201 n.active = true; 202 } 203 204 private void addSCC(N v) { 205 N n; 206 ListBuffer<N> cycle = new ListBuffer<>(); 207 do { 208 n = stack.remove(); 209 n.active = false; 210 cycle.add(n); 211 } while (n != v); 212 sccs.add(cycle.toList()); 213 } 214 } 215 216 /** 217 * Debugging: dot representation of a set of connected nodes. The resulting 218 * dot representation will use {@code Node.toString} to display node labels 219 * and {@code Node.printDependency} to display edge labels. The resulting 220 * representation is also customizable with a graph name and a header. 221 */ 222 public static <D, N extends DottableNode<D, N>> String toDot(Collection<? extends N> nodes, String name, String header) { 223 StringBuilder buf = new StringBuilder(); 224 buf.append(String.format("digraph %s {\n", name)); 225 buf.append(String.format("label = %s;\n", DotVisitor.wrap(header))); 226 DotVisitor<D, N> dotVisitor = new DotVisitor<>(); 227 dotVisitor.visit(nodes, buf); 228 buf.append("}\n"); 229 return buf.toString(); 230 } 231 232 /** 233 * This visitor is used to dump the contents of a set of nodes of type {@link DottableNode} 234 * onto a string builder. 235 */ 236 public static class DotVisitor<D, N extends DottableNode<D, N>> extends NodeVisitor<D, N, StringBuilder> { 237 238 @Override 239 public void visitDependency(DependencyKind dk, N from, N to, StringBuilder buf) { 240 buf.append(String.format("%s -> %s", from.hashCode(), to.hashCode())); 241 buf.append(formatProperties(from.dependencyAttributes(to, dk))); 242 buf.append('\n'); 243 } 244 245 @Override 246 public void visitNode(N node, StringBuilder buf) { 247 buf.append(String.format("%s ", node.hashCode())); 248 buf.append(formatProperties(node.nodeAttributes())); 249 buf.append('\n'); 250 } 251 252 protected String formatProperties(Properties p) { 253 return p.toString().replaceAll(",", " ") 254 .replaceAll("\\{", "[") 255 .replaceAll("\\}", "]"); 256 } 257 258 protected static String wrap(String s) { 259 String res = "\"" + s + "\""; 260 return res.replaceAll("\n", ""); 261 } 262 } 263} 264