1 /* 2 [The "BSD license"] 3 Copyright (c) 2005-2009 Terence Parr 4 All rights reserved. 5 6 Redistribution and use in source and binary forms, with or without 7 modification, are permitted provided that the following conditions 8 are met: 9 1. Redistributions of source code must retain the above copyright 10 notice, this list of conditions and the following disclaimer. 11 2. Redistributions in binary form must reproduce the above copyright 12 notice, this list of conditions and the following disclaimer in the 13 documentation and/or other materials provided with the distribution. 14 3. The name of the author may not be used to endorse or promote products 15 derived from this software without specific prior written permission. 16 17 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 package org.antlr.runtime.tree; 29 30 import org.antlr.stringtemplate.StringTemplate; 31 32 import java.util.HashMap; 33 34 /** A utility class to generate DOT diagrams (graphviz) from 35 * arbitrary trees. You can pass in your own templates and 36 * can pass in any kind of tree or use Tree interface method. 37 * I wanted this separator so that you don't have to include 38 * ST just to use the org.antlr.runtime.tree.* package. 39 * This is a set of non-static methods so you can subclass 40 * to override. For example, here is an invocation: 41 * 42 * CharStream input = new ANTLRInputStream(System.in); 43 * TLexer lex = new TLexer(input); 44 * CommonTokenStream tokens = new CommonTokenStream(lex); 45 * TParser parser = new TParser(tokens); 46 * TParser.e_return r = parser.e(); 47 * Tree t = (Tree)r.tree; 48 * System.out.println(t.toStringTree()); 49 * DOTTreeGenerator gen = new DOTTreeGenerator(); 50 * StringTemplate st = gen.toDOT(t); 51 * System.out.println(st); 52 */ 53 public class DOTTreeGenerator { 54 55 public static StringTemplate _treeST = 56 new StringTemplate( 57 "digraph {\n\n" + 58 "\tordering=out;\n" + 59 "\tranksep=.4;\n" + 60 "\tbgcolor=\"lightgrey\"; node [shape=box, fixedsize=false, fontsize=12, fontname=\"Helvetica-bold\", fontcolor=\"blue\"\n" + 61 "\t\twidth=.25, height=.25, color=\"black\", fillcolor=\"white\", style=\"filled, solid, bold\"];\n" + 62 "\tedge [arrowsize=.5, color=\"black\", style=\"bold\"]\n\n" + 63 " $nodes$\n" + 64 " $edges$\n" + 65 "}\n"); 66 67 public static StringTemplate _nodeST = 68 new StringTemplate("$name$ [label=\"$text$\"];\n"); 69 70 public static StringTemplate _edgeST = 71 new StringTemplate("$parent$ -> $child$ // \"$parentText$\" -> \"$childText$\"\n"); 72 73 /** Track node to number mapping so we can get proper node name back */ 74 HashMap nodeToNumberMap = new HashMap(); 75 76 /** Track node number so we can get unique node names */ 77 int nodeNumber = 0; 78 toDOT(Object tree, TreeAdaptor adaptor, StringTemplate _treeST, StringTemplate _edgeST)79 public StringTemplate toDOT(Object tree, 80 TreeAdaptor adaptor, 81 StringTemplate _treeST, 82 StringTemplate _edgeST) 83 { 84 StringTemplate treeST = _treeST.getInstanceOf(); 85 nodeNumber = 0; 86 toDOTDefineNodes(tree, adaptor, treeST); 87 nodeNumber = 0; 88 toDOTDefineEdges(tree, adaptor, treeST); 89 /* 90 if ( adaptor.getChildCount(tree)==0 ) { 91 // single node, don't do edge. 92 treeST.add("nodes", adaptor.getText(tree)); 93 } 94 */ 95 return treeST; 96 } 97 toDOT(Object tree, TreeAdaptor adaptor)98 public StringTemplate toDOT(Object tree, 99 TreeAdaptor adaptor) 100 { 101 return toDOT(tree, adaptor, _treeST, _edgeST); 102 } 103 104 /** Generate DOT (graphviz) for a whole tree not just a node. 105 * For example, 3+4*5 should generate: 106 * 107 * digraph { 108 * node [shape=plaintext, fixedsize=true, fontsize=11, fontname="Courier", 109 * width=.4, height=.2]; 110 * edge [arrowsize=.7] 111 * "+"->3 112 * "+"->"*" 113 * "*"->4 114 * "*"->5 115 * } 116 * 117 * Return the ST not a string in case people want to alter. 118 * 119 * Takes a Tree interface object. 120 */ toDOT(Tree tree)121 public StringTemplate toDOT(Tree tree) { 122 return toDOT(tree, new CommonTreeAdaptor()); 123 } 124 toDOTDefineNodes(Object tree, TreeAdaptor adaptor, StringTemplate treeST)125 protected void toDOTDefineNodes(Object tree, 126 TreeAdaptor adaptor, 127 StringTemplate treeST) 128 { 129 if ( tree==null ) { 130 return; 131 } 132 int n = adaptor.getChildCount(tree); 133 if ( n==0 ) { 134 // must have already dumped as child from previous 135 // invocation; do nothing 136 return; 137 } 138 139 // define parent node 140 StringTemplate parentNodeST = getNodeST(adaptor, tree); 141 treeST.setAttribute("nodes", parentNodeST); 142 143 // for each child, do a "<unique-name> [label=text]" node def 144 for (int i = 0; i < n; i++) { 145 Object child = adaptor.getChild(tree, i); 146 StringTemplate nodeST = getNodeST(adaptor, child); 147 treeST.setAttribute("nodes", nodeST); 148 toDOTDefineNodes(child, adaptor, treeST); 149 } 150 } 151 toDOTDefineEdges(Object tree, TreeAdaptor adaptor, StringTemplate treeST)152 protected void toDOTDefineEdges(Object tree, 153 TreeAdaptor adaptor, 154 StringTemplate treeST) 155 { 156 if ( tree==null ) { 157 return; 158 } 159 int n = adaptor.getChildCount(tree); 160 if ( n==0 ) { 161 // must have already dumped as child from previous 162 // invocation; do nothing 163 return; 164 } 165 166 String parentName = "n"+getNodeNumber(tree); 167 168 // for each child, do a parent -> child edge using unique node names 169 String parentText = adaptor.getText(tree); 170 for (int i = 0; i < n; i++) { 171 Object child = adaptor.getChild(tree, i); 172 String childText = adaptor.getText(child); 173 String childName = "n"+getNodeNumber(child); 174 StringTemplate edgeST = _edgeST.getInstanceOf(); 175 edgeST.setAttribute("parent", parentName); 176 edgeST.setAttribute("child", childName); 177 edgeST.setAttribute("parentText", fixString(parentText)); 178 edgeST.setAttribute("childText", fixString(childText)); 179 treeST.setAttribute("edges", edgeST); 180 toDOTDefineEdges(child, adaptor, treeST); 181 } 182 } 183 getNodeST(TreeAdaptor adaptor, Object t)184 protected StringTemplate getNodeST(TreeAdaptor adaptor, Object t) { 185 String text = adaptor.getText(t); 186 StringTemplate nodeST = _nodeST.getInstanceOf(); 187 String uniqueName = "n"+getNodeNumber(t); 188 nodeST.setAttribute("name", uniqueName); 189 190 nodeST.setAttribute("text", fixString(text)); 191 return nodeST; 192 } 193 getNodeNumber(Object t)194 protected int getNodeNumber(Object t) { 195 Integer nI = (Integer)nodeToNumberMap.get(t); 196 if ( nI!=null ) { 197 return nI.intValue(); 198 } 199 else { 200 nodeToNumberMap.put(t, new Integer(nodeNumber)); 201 nodeNumber++; 202 return nodeNumber-1; 203 } 204 } 205 fixString(String in)206 protected String fixString(String in) 207 { 208 String text = in; 209 210 if (text!=null) { 211 212 text = text.replaceAll("\"", "\\\\\""); 213 text = text.replaceAll("\\t", " "); 214 text = text.replaceAll("\\n", "\\\\n"); 215 text = text.replaceAll("\\r", "\\\\r"); 216 if (text.length() > 20) { 217 text = text.substring(0, 8) + "..." + text.substring(text.length()-8); 218 } 219 220 } 221 222 return text; 223 } 224 } 225