1 /*
2 * Copyright (c) 2010, 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.nashorn.internal.ir.debug;
27
28 import java.lang.reflect.Field;
29 import java.util.ArrayDeque;
30 import java.util.ArrayList;
31 import java.util.Collection;
32 import java.util.Deque;
33 import java.util.Iterator;
34 import java.util.LinkedList;
35 import java.util.List;
36 import jdk.nashorn.internal.ir.BinaryNode;
37 import jdk.nashorn.internal.ir.Block;
38 import jdk.nashorn.internal.ir.Expression;
39 import jdk.nashorn.internal.ir.IdentNode;
40 import jdk.nashorn.internal.ir.Node;
41 import jdk.nashorn.internal.ir.Statement;
42 import jdk.nashorn.internal.ir.Symbol;
43 import jdk.nashorn.internal.ir.Terminal;
44 import jdk.nashorn.internal.ir.TernaryNode;
45 import jdk.nashorn.internal.ir.annotations.Ignore;
46 import jdk.nashorn.internal.ir.annotations.Reference;
47 import jdk.nashorn.internal.parser.Token;
48 import jdk.nashorn.internal.runtime.Context;
49 import jdk.nashorn.internal.runtime.Debug;
50
51 /**
52 * AST-as-text visualizer. Sometimes you want tree form and not source
53 * code. This works for both lowered and unlowered IR
54 *
55 * see the flags --print-ast and --print-ast-lower
56 */
57 public final class ASTWriter {
58 private static final ClassValue<Field[]> accessibleFields = new ClassValue<Field[]>() {
59 @Override
60 protected Field[] computeValue(final Class<?> type) {
61 final Field[] fields = type.getDeclaredFields();
62 for(final Field f: fields) {
63 f.setAccessible(true);
64 }
65 return fields;
66 }
67 };
68 /** Root node from which to start the traversal */
69 private final Node root;
70
71 private static final int TABWIDTH = 4;
72
73 /**
74 * Constructor
75 * @param root root of the AST to visualize
76 */
77 public ASTWriter(final Node root) {
78 this.root = root;
79 }
80
81 /**
82 * Use the ASTWriter by instantiating it and retrieving its String
83 * representation
84 *
85 * @return the string representation of the AST
86 */
87 @Override
88 public String toString() {
89 final StringBuilder sb = new StringBuilder();
90 printAST(sb, null, null, "root", root, 0);
91 return sb.toString();
92 }
93
94 /**
95 * Return the visited nodes in an ordered list
96 * @return the list of nodes in order
97 */
98 public Node[] toArray() {
99 final List<Node> preorder = new ArrayList<>();
100 printAST(new StringBuilder(), preorder, null, "root", root, 0);
101 return preorder.toArray(new Node[0]);
102 }
103
104 @SuppressWarnings("unchecked")
105 private void printAST(final StringBuilder sb, final List<Node> preorder, final Field field, final String name, final Node node, final int indent) {
106 ASTWriter.indent(sb, indent);
107 if (node == null) {
108 sb.append("[Object ");
109 sb.append(name);
110 sb.append(" null]\n");
111 return;
112 }
113
114 if (preorder != null) {
115 preorder.add(node);
116 }
117
118 final boolean isReference = field != null && field.isAnnotationPresent(Reference.class);
119
120 final Class<?> clazz = node.getClass();
121 String type = clazz.getName();
122
123 type = type.substring(type.lastIndexOf('.') + 1, type.length());
124 int truncate = type.indexOf("Node");
125 if (truncate == -1) {
126 truncate = type.indexOf("Statement");
127 }
128 if (truncate != -1) {
129 type = type.substring(0, truncate);
130 }
131 type = type.toLowerCase();
132
133 if (isReference) {
134 type = "ref: " + type;
135 }
136 final Symbol symbol;
137 if (node instanceof IdentNode) {
138 symbol = ((IdentNode)node).getSymbol();
139 } else {
140 symbol = null;
141 }
142
143 if (symbol != null) {
144 type += ">" + symbol;
145 }
146
147 if (node instanceof Block && ((Block)node).needsScope()) {
148 type += " <scope>";
149 }
150
151 final List<Field> children = new LinkedList<>();
152
153 if (!isReference) {
154 enqueueChildren(node, clazz, children);
155 }
156
157 String status = "";
158
159 if (node instanceof Terminal && ((Terminal)node).isTerminal()) {
160 status += " Terminal";
161 }
162
163 if (node instanceof Statement && ((Statement)node).hasGoto()) {
164 status += " Goto ";
165 }
166
167 if (symbol != null) {
168 status += symbol;
169 }
170
171 status = status.trim();
172 if (!"".equals(status)) {
173 status = " [" + status + "]";
174 }
175
176 if (symbol != null) {
177 String tname = ((Expression)node).getType().toString();
178 if (tname.indexOf('.') != -1) {
179 tname = tname.substring(tname.lastIndexOf('.') + 1, tname.length());
180 }
181 status += " (" + tname + ")";
182 }
183
184 status += " @" + Debug.id(node);
185
186 if (children.isEmpty()) {
187 sb.append("[").
188 append(type).
189 append(' ').
190 append(name).
191 append(" = '").
192 append(node).
193 append("'").
194 append(status).
195 append("] ").
196 append('\n');
197 } else {
198 sb.append("[").
199 append(type).
200 append(' ').
201 append(name).
202 append(' ').
203 append(Token.toString(node.getToken())).
204 append(status).
205 append("]").
206 append('\n');
207
208 for (final Field child : children) {
209 if (child.isAnnotationPresent(Ignore.class)) {
210 continue;
211 }
212
213 Object value;
214 try {
215 value = child.get(node);
216 } catch (final IllegalArgumentException | IllegalAccessException e) {
217 Context.printStackTrace(e);
218 return;
219 }
220
221 if (value instanceof Node) {
222 printAST(sb, preorder, child, child.getName(), (Node)value, indent + 1);
223 } else if (value instanceof Collection) {
224 int pos = 0;
225 ASTWriter.indent(sb, indent + 1);
226 sb.append('[').
227 append(child.getName()).
228 append("[0..").
229 append(((Collection<Node>)value).size()).
230 append("]]").
231 append('\n');
232
233 for (final Node member : (Collection<Node>)value) {
234 printAST(sb, preorder, child, child.getName() + "[" + pos++ + "]", member, indent + 2);
235 }
236 }
237 }
238 }
239 }
240
241 private static void enqueueChildren(final Node node, final Class<?> nodeClass, final List<Field> children) {
242 final Deque<Class<?>> stack = new ArrayDeque<>();
243
244 /**
245 * Here is some ugliness that can be overcome by proper ChildNode annotations
246 * with proper orders. Right now we basically sort all classes up to Node
247 * with super class first, as this often is the natural order, e.g. base
248 * before index for an IndexNode.
249 *
250 * Also there are special cases as this is not true for UnaryNodes(lhs) and
251 * BinaryNodes extends UnaryNode (with lhs), and TernaryNodes.
252 *
253 * TODO - generalize traversal with an order built on annotations and this
254 * will go away.
255 */
256 Class<?> clazz = nodeClass;
257 do {
258 stack.push(clazz);
259 clazz = clazz.getSuperclass();
260 } while (clazz != null);
261
262 if (node instanceof TernaryNode) {
263 // HACK juggle "third"
264 stack.push(stack.removeLast());
265 }
266 // HACK change operator order for BinaryNodes to get lhs first.
267 final Iterator<Class<?>> iter = node instanceof BinaryNode ? stack.descendingIterator() : stack.iterator();
268
269 while (iter.hasNext()) {
270 final Class<?> c = iter.next();
271 for (final Field f : accessibleFields.get(c)) {
272 try {
273 final Object child = f.get(node);
274 if (child == null) {
275 continue;
276 }
277
278 if (child instanceof Node) {
279 children.add(f);
280 } else if (child instanceof Collection) {
281 if (!((Collection<?>)child).isEmpty()) {
282 children.add(f);
283 }
284 }
285 } catch (final IllegalArgumentException | IllegalAccessException e) {
286 return;
287 }
288 }
289 }
290 }
291
292 private static void indent(final StringBuilder sb, final int indent) {
293 for (int i = 0; i < indent; i++) {
294 for (int j = 0; j < TABWIDTH; j++) {
295 sb.append(' ');
296 }
297 }
298 }
299 }