| /* |
| * [The "BSD licence"] |
| * Copyright (c) 2005-2008 Terence Parr |
| * All rights reserved. |
| * |
| * Conversion to C#: |
| * Copyright (c) 2008 Sam Harwell, Pixel Mine, Inc. |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * 3. The name of the author may not be used to endorse or promote products |
| * derived from this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| namespace Antlr.Runtime.Tree |
| { |
| using System.Collections.Generic; |
| using StringBuilder = System.Text.StringBuilder; |
| |
| /** A utility class to generate DOT diagrams (graphviz) from |
| * arbitrary trees. You can pass in your own templates and |
| * can pass in any kind of tree or use Tree interface method. |
| * I wanted this separator so that you don't have to include |
| * ST just to use the org.antlr.runtime.tree.* package. |
| * This is a set of non-static methods so you can subclass |
| * to override. For example, here is an invocation: |
| * |
| * CharStream input = new ANTLRInputStream(System.in); |
| * TLexer lex = new TLexer(input); |
| * CommonTokenStream tokens = new CommonTokenStream(lex); |
| * TParser parser = new TParser(tokens); |
| * TParser.e_return r = parser.e(); |
| * Tree t = (Tree)r.tree; |
| * System.out.println(t.toStringTree()); |
| * DOTTreeGenerator gen = new DOTTreeGenerator(); |
| * StringTemplate st = gen.toDOT(t); |
| * System.out.println(st); |
| */ |
| public class DotTreeGenerator |
| { |
| readonly string[] HeaderLines = |
| { |
| "digraph {", |
| "", |
| "\tordering=out;", |
| "\tranksep=.4;", |
| "\tbgcolor=\"lightgrey\"; node [shape=box, fixedsize=false, fontsize=12, fontname=\"Helvetica-bold\", fontcolor=\"blue\"", |
| "\t\twidth=.25, height=.25, color=\"black\", fillcolor=\"white\", style=\"filled, solid, bold\"];", |
| "\tedge [arrowsize=.5, color=\"black\", style=\"bold\"]", |
| "" |
| }; |
| const string Footer = "}"; |
| const string NodeFormat = " {0} [label=\"{1}\"];"; |
| const string EdgeFormat = " {0} -> {1} // \"{2}\" -> \"{3}\""; |
| |
| /** Track node to number mapping so we can get proper node name back */ |
| Dictionary<object, int> nodeToNumberMap = new Dictionary<object, int>(); |
| |
| /** Track node number so we can get unique node names */ |
| int nodeNumber = 0; |
| |
| /** Generate DOT (graphviz) for a whole tree not just a node. |
| * For example, 3+4*5 should generate: |
| * |
| * digraph { |
| * node [shape=plaintext, fixedsize=true, fontsize=11, fontname="Courier", |
| * width=.4, height=.2]; |
| * edge [arrowsize=.7] |
| * "+"->3 |
| * "+"->"*" |
| * "*"->4 |
| * "*"->5 |
| * } |
| * |
| * Takes a Tree interface object. |
| */ |
| public virtual string ToDot( object tree, ITreeAdaptor adaptor ) |
| { |
| StringBuilder builder = new StringBuilder(); |
| foreach ( string line in HeaderLines ) |
| builder.AppendLine( line ); |
| |
| nodeNumber = 0; |
| var nodes = DefineNodes( tree, adaptor ); |
| nodeNumber = 0; |
| var edges = DefineEdges( tree, adaptor ); |
| |
| foreach ( var s in nodes ) |
| builder.AppendLine( s ); |
| |
| builder.AppendLine(); |
| |
| foreach ( var s in edges ) |
| builder.AppendLine( s ); |
| |
| builder.AppendLine(); |
| |
| builder.AppendLine( Footer ); |
| return builder.ToString(); |
| } |
| |
| public virtual string ToDot( ITree tree ) |
| { |
| return ToDot( tree, new CommonTreeAdaptor() ); |
| } |
| protected virtual IEnumerable<string> DefineNodes( object tree, ITreeAdaptor adaptor ) |
| { |
| if ( tree == null ) |
| yield break; |
| |
| int n = adaptor.GetChildCount( tree ); |
| if ( n == 0 ) |
| { |
| // must have already dumped as child from previous |
| // invocation; do nothing |
| yield break; |
| } |
| |
| // define parent node |
| yield return GetNodeText( adaptor, tree ); |
| |
| // for each child, do a "<unique-name> [label=text]" node def |
| for ( int i = 0; i < n; i++ ) |
| { |
| object child = adaptor.GetChild( tree, i ); |
| yield return GetNodeText( adaptor, child ); |
| foreach ( var t in DefineNodes( child, adaptor ) ) |
| yield return t; |
| } |
| } |
| |
| protected virtual IEnumerable<string> DefineEdges( object tree, ITreeAdaptor adaptor ) |
| { |
| if ( tree == null ) |
| yield break; |
| |
| int n = adaptor.GetChildCount( tree ); |
| if ( n == 0 ) |
| { |
| // must have already dumped as child from previous |
| // invocation; do nothing |
| yield break; |
| } |
| |
| string parentName = "n" + GetNodeNumber( tree ); |
| |
| // for each child, do a parent -> child edge using unique node names |
| string parentText = adaptor.GetText( tree ); |
| for ( int i = 0; i < n; i++ ) |
| { |
| object child = adaptor.GetChild( tree, i ); |
| string childText = adaptor.GetText( child ); |
| string childName = "n" + GetNodeNumber( child ); |
| yield return string.Format( EdgeFormat, parentName, childName, FixString( parentText ), FixString( childText ) ); |
| foreach ( var t in DefineEdges( child, adaptor ) ) |
| yield return t; |
| } |
| } |
| |
| protected virtual string GetNodeText( ITreeAdaptor adaptor, object t ) |
| { |
| string text = adaptor.GetText( t ); |
| string uniqueName = "n" + GetNodeNumber( t ); |
| return string.Format( NodeFormat, uniqueName, FixString( text ) ); |
| } |
| |
| protected virtual int GetNodeNumber( object t ) |
| { |
| int i; |
| if ( nodeToNumberMap.TryGetValue( t, out i ) ) |
| { |
| return i; |
| } |
| else |
| { |
| nodeToNumberMap[t] = nodeNumber; |
| nodeNumber++; |
| return nodeNumber - 1; |
| } |
| } |
| |
| protected virtual string FixString( string text ) |
| { |
| if ( text != null ) |
| { |
| text = System.Text.RegularExpressions.Regex.Replace( text, "\"", "\\\\\"" ); |
| text = System.Text.RegularExpressions.Regex.Replace( text, "\\t", " " ); |
| text = System.Text.RegularExpressions.Regex.Replace( text, "\\n", "\\\\n" ); |
| text = System.Text.RegularExpressions.Regex.Replace( text, "\\r", "\\\\r" ); |
| |
| if ( text.Length > 20 ) |
| text = text.Substring( 0, 8 ) + "..." + text.Substring( text.Length - 8 ); |
| } |
| |
| return text; |
| } |
| } |
| } |