001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2006 Terence Parr
004: All rights reserved.
005:
006: Redistribution and use in source and binary forms, with or without
007: modification, are permitted provided that the following conditions
008: are met:
009: 1. Redistributions of source code must retain the above copyright
010: notice, this list of conditions and the following disclaimer.
011: 2. Redistributions in binary form must reproduce the above copyright
012: notice, this list of conditions and the following disclaimer in the
013: documentation and/or other materials provided with the distribution.
014: 3. The name of the author may not be used to endorse or promote products
015: derived from this software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
018: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
019: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
020: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
021: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
022: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
023: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
024: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
026: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028: package org.antlr.runtime.tree;
029:
030: import org.antlr.stringtemplate.StringTemplate;
031:
032: import java.util.HashMap;
033:
034: /** A utility class to generate DOT diagrams (graphviz) from
035: * arbitrary trees. You can pass in your own templates and
036: * can pass in any kind of tree or use Tree interface method.
037: * I wanted this separator so that you don't have to include
038: * ST just to use the org.antlr.runtime.tree.* package.
039: * This is a set of non-static methods so you can subclass
040: * to override. For example, here is an invocation:
041: *
042: * CharStream input = new ANTLRInputStream(System.in);
043: * TLexer lex = new TLexer(input);
044: * CommonTokenStream tokens = new CommonTokenStream(lex);
045: * TParser parser = new TParser(tokens);
046: * TParser.e_return r = parser.e();
047: * Tree t = (Tree)r.tree;
048: * System.out.println(t.toStringTree());
049: * DOTTreeGenerator gen = new DOTTreeGenerator();
050: * StringTemplate st = gen.toDOT(t);
051: * System.out.println(st);
052: */
053: public class DOTTreeGenerator {
054:
055: public static StringTemplate _treeST = new StringTemplate(
056: "digraph {\n"
057: + " ordering=out;\n"
058: + " ranksep=.4;\n"
059: + " node [shape=plaintext, fixedsize=true, fontsize=11, fontname=\"Courier\",\n"
060: + " width=.25, height=.25];\n"
061: + " edge [arrowsize=.5]\n" + " $nodes$\n"
062: + " $edges$\n" + "}\n");
063:
064: public static StringTemplate _nodeST = new StringTemplate(
065: "$name$ [label=\"$text$\"];\n");
066:
067: public static StringTemplate _edgeST = new StringTemplate(
068: "$parent$ -> $child$ // \"$parentText$\" -> \"$childText$\"\n");
069:
070: /** Track node to number mapping so we can get proper node name back */
071: HashMap nodeToNumberMap = new HashMap();
072:
073: /** Track node number so we can get unique node names */
074: int nodeNumber = 0;
075:
076: public StringTemplate toDOT(Object tree, TreeAdaptor adaptor,
077: StringTemplate _treeST, StringTemplate _edgeST) {
078: StringTemplate treeST = _treeST.getInstanceOf();
079: nodeNumber = 0;
080: toDOTDefineNodes(tree, adaptor, treeST);
081: nodeNumber = 0;
082: toDOTDefineEdges(tree, adaptor, treeST);
083: /*
084: if ( adaptor.getChildCount(tree)==0 ) {
085: // single node, don't do edge.
086: treeST.setAttribute("nodes", adaptor.getText(tree));
087: }
088: */
089: return treeST;
090: }
091:
092: public StringTemplate toDOT(Object tree, TreeAdaptor adaptor) {
093: return toDOT(tree, adaptor, _treeST, _edgeST);
094: }
095:
096: /** Generate DOT (graphviz) for a whole tree not just a node.
097: * For example, 3+4*5 should generate:
098: *
099: * digraph {
100: * node [shape=plaintext, fixedsize=true, fontsize=11, fontname="Courier",
101: * width=.4, height=.2];
102: * edge [arrowsize=.7]
103: * "+"->3
104: * "+"->"*"
105: * "*"->4
106: * "*"->5
107: * }
108: *
109: * Return the ST not a string in case people want to alter.
110: *
111: * Takes a Tree interface object.
112: */
113: public StringTemplate toDOT(Tree tree) {
114: return toDOT(tree, new CommonTreeAdaptor());
115: }
116:
117: protected void toDOTDefineNodes(Object tree, TreeAdaptor adaptor,
118: StringTemplate treeST) {
119: if (tree == null) {
120: return;
121: }
122: int n = adaptor.getChildCount(tree);
123: if (n == 0) {
124: // must have already dumped as child from previous
125: // invocation; do nothing
126: return;
127: }
128:
129: // define parent node
130: StringTemplate parentNodeST = getNodeST(adaptor, tree);
131: treeST.setAttribute("nodes", parentNodeST);
132:
133: // for each child, do a "<unique-name> [label=text]" node def
134: for (int i = 0; i < n; i++) {
135: Object child = adaptor.getChild(tree, i);
136: StringTemplate nodeST = getNodeST(adaptor, child);
137: treeST.setAttribute("nodes", nodeST);
138: toDOTDefineNodes(child, adaptor, treeST);
139: }
140: }
141:
142: protected void toDOTDefineEdges(Object tree, TreeAdaptor adaptor,
143: StringTemplate treeST) {
144: if (tree == null) {
145: return;
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: return;
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: StringTemplate edgeST = _edgeST.getInstanceOf();
163: edgeST.setAttribute("parent", parentName);
164: edgeST.setAttribute("child", childName);
165: edgeST.setAttribute("parentText", parentText);
166: edgeST.setAttribute("childText", childText);
167: treeST.setAttribute("edges", edgeST);
168: toDOTDefineEdges(child, adaptor, treeST);
169: }
170: }
171:
172: protected StringTemplate getNodeST(TreeAdaptor adaptor, Object t) {
173: String text = adaptor.getText(t);
174: StringTemplate nodeST = _nodeST.getInstanceOf();
175: String uniqueName = "n" + getNodeNumber(t);
176: nodeST.setAttribute("name", uniqueName);
177: if (text != null)
178: text = text.replaceAll("\"", "\\\\\"");
179: nodeST.setAttribute("text", text);
180: return nodeST;
181: }
182:
183: protected int getNodeNumber(Object t) {
184: Integer nI = (Integer) nodeToNumberMap.get(t);
185: if (nI != null) {
186: return nI.intValue();
187: } else {
188: nodeToNumberMap.put(t, new Integer(nodeNumber));
189: nodeNumber++;
190: return nodeNumber - 1;
191: }
192: }
193: }
|