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 33namespace Antlr.Runtime.Tree { 34 using System.Collections.Generic; 35 using StringBuilder = System.Text.StringBuilder; 36 37 /** A utility class to generate DOT diagrams (graphviz) from 38 * arbitrary trees. You can pass in your own templates and 39 * can pass in any kind of tree or use Tree interface method. 40 * I wanted this separator so that you don't have to include 41 * ST just to use the org.antlr.runtime.tree.* package. 42 * This is a set of non-static methods so you can subclass 43 * to override. For example, here is an invocation: 44 * 45 * CharStream input = new ANTLRInputStream(System.in); 46 * TLexer lex = new TLexer(input); 47 * CommonTokenStream tokens = new CommonTokenStream(lex); 48 * TParser parser = new TParser(tokens); 49 * TParser.e_return r = parser.e(); 50 * Tree t = (Tree)r.tree; 51 * System.out.println(t.toStringTree()); 52 * DOTTreeGenerator gen = new DOTTreeGenerator(); 53 * StringTemplate st = gen.toDOT(t); 54 * System.out.println(st); 55 */ 56 public class DotTreeGenerator { 57 readonly string[] HeaderLines = 58 { 59 "digraph {", 60 "", 61 "\tordering=out;", 62 "\tranksep=.4;", 63 "\tbgcolor=\"lightgrey\"; node [shape=box, fixedsize=false, fontsize=12, fontname=\"Helvetica-bold\", fontcolor=\"blue\"", 64 "\t\twidth=.25, height=.25, color=\"black\", fillcolor=\"white\", style=\"filled, solid, bold\"];", 65 "\tedge [arrowsize=.5, color=\"black\", style=\"bold\"]", 66 "" 67 }; 68 const string Footer = "}"; 69 const string NodeFormat = " {0} [label=\"{1}\"];"; 70 const string EdgeFormat = " {0} -> {1} // \"{2}\" -> \"{3}\""; 71 72 /** Track node to number mapping so we can get proper node name back */ 73 Dictionary<object, int> nodeToNumberMap = new Dictionary<object, int>(); 74 75 /** Track node number so we can get unique node names */ 76 int nodeNumber = 0; 77 78 /** Generate DOT (graphviz) for a whole tree not just a node. 79 * For example, 3+4*5 should generate: 80 * 81 * digraph { 82 * node [shape=plaintext, fixedsize=true, fontsize=11, fontname="Courier", 83 * width=.4, height=.2]; 84 * edge [arrowsize=.7] 85 * "+"->3 86 * "+"->"*" 87 * "*"->4 88 * "*"->5 89 * } 90 * 91 * Takes a Tree interface object. 92 */ 93 public virtual string ToDot(object tree, ITreeAdaptor adaptor) { 94 StringBuilder builder = new StringBuilder(); 95 foreach (string line in HeaderLines) 96 builder.AppendLine(line); 97 98 nodeNumber = 0; 99 var nodes = DefineNodes(tree, adaptor); 100 nodeNumber = 0; 101 var edges = DefineEdges(tree, adaptor); 102 103 foreach (var s in nodes) 104 builder.AppendLine(s); 105 106 builder.AppendLine(); 107 108 foreach (var s in edges) 109 builder.AppendLine(s); 110 111 builder.AppendLine(); 112 113 builder.AppendLine(Footer); 114 return builder.ToString(); 115 } 116 117 public virtual string ToDot(ITree tree) { 118 return ToDot(tree, new CommonTreeAdaptor()); 119 } 120 protected virtual IEnumerable<string> DefineNodes(object tree, ITreeAdaptor adaptor) { 121 if (tree == null) 122 yield break; 123 124 int n = adaptor.GetChildCount(tree); 125 if (n == 0) { 126 // must have already dumped as child from previous 127 // invocation; do nothing 128 yield break; 129 } 130 131 // define parent node 132 yield return GetNodeText(adaptor, tree); 133 134 // for each child, do a "<unique-name> [label=text]" node def 135 for (int i = 0; i < n; i++) { 136 object child = adaptor.GetChild(tree, i); 137 yield return GetNodeText(adaptor, child); 138 foreach (var t in DefineNodes(child, adaptor)) 139 yield return t; 140 } 141 } 142 143 protected virtual IEnumerable<string> DefineEdges(object tree, ITreeAdaptor adaptor) { 144 if (tree == null) 145 yield break; 146 147 int n = adaptor.GetChildCount(tree); 148 if (n == 0) { 149 // must have already dumped as child from previous 150 // invocation; do nothing 151 yield break; 152 } 153 154 string parentName = "n" + GetNodeNumber(tree); 155 156 // for each child, do a parent -> child edge using unique node names 157 string parentText = adaptor.GetText(tree); 158 for (int i = 0; i < n; i++) { 159 object child = adaptor.GetChild(tree, i); 160 string childText = adaptor.GetText(child); 161 string childName = "n" + GetNodeNumber(child); 162 yield return string.Format(EdgeFormat, parentName, childName, FixString(parentText), FixString(childText)); 163 foreach (var t in DefineEdges(child, adaptor)) 164 yield return t; 165 } 166 } 167 168 protected virtual string GetNodeText(ITreeAdaptor adaptor, object t) { 169 string text = adaptor.GetText(t); 170 string uniqueName = "n" + GetNodeNumber(t); 171 return string.Format(NodeFormat, uniqueName, FixString(text)); 172 } 173 174 protected virtual int GetNodeNumber(object t) { 175 int i; 176 if (nodeToNumberMap.TryGetValue(t, out i)) { 177 return i; 178 } else { 179 nodeToNumberMap[t] = nodeNumber; 180 nodeNumber++; 181 return nodeNumber - 1; 182 } 183 } 184 185 protected virtual string FixString(string text) { 186 if (text != null) { 187 text = System.Text.RegularExpressions.Regex.Replace(text, "\"", "\\\\\""); 188 text = System.Text.RegularExpressions.Regex.Replace(text, "\\t", " "); 189 text = System.Text.RegularExpressions.Regex.Replace(text, "\\n", "\\\\n"); 190 text = System.Text.RegularExpressions.Regex.Replace(text, "\\r", "\\\\r"); 191 192 if (text.Length > 20) 193 text = text.Substring(0, 8) + "..." + text.Substring(text.Length - 8); 194 } 195 196 return text; 197 } 198 } 199} 200