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