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{
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         */
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
120        public virtual string ToDot( ITree tree )
121        {
122            return ToDot( tree, new CommonTreeAdaptor() );
123        }
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
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.GetText( tree );
167            for ( int i = 0; i < n; i++ )
168            {
169                object child = adaptor.GetChild( tree, i );
170                string childText = adaptor.GetText( 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
178        protected virtual string GetNodeText( ITreeAdaptor adaptor, object t )
179        {
180            string text = adaptor.GetText( t );
181            string uniqueName = "n" + GetNodeNumber( t );
182            return string.Format( NodeFormat, uniqueName, FixString( text ) );
183        }
184
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
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