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