diff options
Diffstat (limited to 'runtime/CSharp3/Sources/Antlr3.Runtime/Tree/DotTreeGenerator.cs')
| -rw-r--r-- | runtime/CSharp3/Sources/Antlr3.Runtime/Tree/DotTreeGenerator.cs | 216 |
1 files changed, 216 insertions, 0 deletions
diff --git a/runtime/CSharp3/Sources/Antlr3.Runtime/Tree/DotTreeGenerator.cs b/runtime/CSharp3/Sources/Antlr3.Runtime/Tree/DotTreeGenerator.cs new file mode 100644 index 0000000..8a35b45 --- /dev/null +++ b/runtime/CSharp3/Sources/Antlr3.Runtime/Tree/DotTreeGenerator.cs @@ -0,0 +1,216 @@ +/* + * [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; + } + } +} |