ASTWriter.java revision 953:221a84ef44c0 
1/*
2 * Copyright (c) 2010, 2013, 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
26package jdk.nashorn.internal.ir.debug;
27
28import java.lang.reflect.Field;
29import java.util.ArrayDeque;
30import java.util.ArrayList;
31import java.util.Collection;
32import java.util.Deque;
33import java.util.Iterator;
34import java.util.LinkedList;
35import java.util.List;
36import jdk.nashorn.internal.ir.BinaryNode;
37import jdk.nashorn.internal.ir.Block;
38import jdk.nashorn.internal.ir.Expression;
39import jdk.nashorn.internal.ir.IdentNode;
40import jdk.nashorn.internal.ir.Node;
41import jdk.nashorn.internal.ir.Statement;
42import jdk.nashorn.internal.ir.Symbol;
43import jdk.nashorn.internal.ir.Terminal;
44import jdk.nashorn.internal.ir.TernaryNode;
45import jdk.nashorn.internal.ir.annotations.Ignore;
46import jdk.nashorn.internal.ir.annotations.Reference;
47import jdk.nashorn.internal.parser.Token;
48import jdk.nashorn.internal.runtime.Context;
49import 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 */
57public final class ASTWriter {
58    /** Root node from which to start the traversal */
59    private final Node root;
60
61    private static final int TABWIDTH = 4;
62
63    /**
64     * Constructor
65     * @param root root of the AST to visualize
66     */
67    public ASTWriter(final Node root) {
68        this.root = root;
69    }
70
71    /**
72     * Use the ASTWriter by instantiating it and retrieving its String
73     * representation
74     *
75     * @return the string representation of the AST
76     */
77    @Override
78    public String toString() {
79        final StringBuilder sb = new StringBuilder();
80        printAST(sb, null, null, "root", root, 0);
81        return sb.toString();
82    }
83
84    /**
85     * Return the visited nodes in an ordered list
86     * @return the list of nodes in order
87     */
88    public Node[] toArray() {
89        final List<Node> preorder = new ArrayList<>();
90        printAST(new StringBuilder(), preorder, null, "root", root, 0);
91        return preorder.toArray(new Node[preorder.size()]);
92    }
93
94    @SuppressWarnings("unchecked")
95    private void printAST(final StringBuilder sb, final List<Node> preorder, final Field field, final String name, final Node node, final int indent) {
96        ASTWriter.indent(sb, indent);
97        if (node == null) {
98            sb.append("[Object ");
99            sb.append(name);
100            sb.append(" null]\n");
101            return;
102        }
103
104        if (preorder != null) {
105            preorder.add(node);
106        }
107
108        final boolean isReference = field != null && field.isAnnotationPresent(Reference.class);
109
110        final Class<?> clazz = node.getClass();
111        String   type  = clazz.getName();
112
113        type = type.substring(type.lastIndexOf('.') + 1, type.length());
114        int truncate = type.indexOf("Node");
115        if (truncate == -1) {
116            truncate = type.indexOf("Statement");
117        }
118        if (truncate != -1) {
119            type = type.substring(0, truncate);
120        }
121        type = type.toLowerCase();
122
123        if (isReference) {
124            type = "ref: " + type;
125        }
126        final Symbol symbol;
127        if (node instanceof IdentNode) {
128            symbol = ((IdentNode)node).getSymbol();
129        } else {
130            symbol = null;
131        }
132
133        if (symbol != null) {
134            type += ">" + symbol;
135        }
136
137        if (node instanceof Block && ((Block)node).needsScope()) {
138            type += " <scope>";
139        }
140
141        final List<Field> children = new LinkedList<>();
142
143        if (!isReference) {
144            enqueueChildren(node, clazz, children);
145        }
146
147        String status = "";
148
149        if (node instanceof Terminal && ((Terminal)node).isTerminal()) {
150            status += " Terminal";
151        }
152
153        if (node instanceof Statement && ((Statement)node).hasGoto()) {
154            status += " Goto ";
155        }
156
157        if (symbol != null) {
158            status += symbol;
159        }
160
161        status = status.trim();
162        if (!"".equals(status)) {
163            status = " [" + status + "]";
164        }
165
166        if (symbol != null) {
167            String tname = ((Expression)node).getType().toString();
168            if (tname.indexOf('.') != -1) {
169                tname = tname.substring(tname.lastIndexOf('.') + 1, tname.length());
170            }
171            status += " (" + tname + ")";
172        }
173
174        status += " @" + Debug.id(node);
175
176        if (children.isEmpty()) {
177            sb.append("[").
178                append(type).
179                append(' ').
180                append(name).
181                append(" = '").
182                append(node).
183                append("'").
184                append(status).
185                append("] ").
186                append('\n');
187        } else {
188            sb.append("[").
189                append(type).
190                append(' ').
191                append(name).
192                append(' ').
193                append(Token.toString(node.getToken())).
194                append(status).
195                append("]").
196                append('\n');
197
198            for (final Field child : children) {
199                if (child.isAnnotationPresent(Ignore.class)) {
200                    continue;
201                }
202
203                Object value;
204                try {
205                    value = child.get(node);
206                } catch (final IllegalArgumentException | IllegalAccessException e) {
207                    Context.printStackTrace(e);
208                    return;
209                }
210
211                if (value instanceof Node) {
212                    printAST(sb, preorder, child, child.getName(), (Node)value, indent + 1);
213                } else if (value instanceof Collection) {
214                    int pos = 0;
215                    ASTWriter.indent(sb, indent + 1);
216                    sb.append('[').
217                        append(child.getName()).
218                        append("[0..").
219                        append(((Collection<Node>)value).size()).
220                        append("]]").
221                        append('\n');
222
223                    for (final Node member : (Collection<Node>)value) {
224                        printAST(sb, preorder, child, child.getName() + "[" + pos++ + "]", member, indent + 2);
225                    }
226                }
227            }
228        }
229    }
230
231    private static void enqueueChildren(final Node node, final Class<?> nodeClass, final List<Field> children) {
232        final Deque<Class<?>> stack = new ArrayDeque<>();
233
234        /**
235         * Here is some ugliness that can be overcome by proper ChildNode annotations
236         * with proper orders. Right now we basically sort all classes up to Node
237         * with super class first, as this often is the natural order, e.g. base
238         * before index for an IndexNode.
239         *
240         * Also there are special cases as this is not true for UnaryNodes(lhs) and
241         * BinaryNodes extends UnaryNode (with lhs), and TernaryNodes.
242         *
243         * TODO - generalize traversal with an order built on annotations and this
244         * will go away.
245         */
246        Class<?> clazz = nodeClass;
247        do {
248            stack.push(clazz);
249            clazz = clazz.getSuperclass();
250        } while (clazz != null);
251
252        if (node instanceof TernaryNode) {
253            // HACK juggle "third"
254            stack.push(stack.removeLast());
255        }
256        // HACK change operator order for BinaryNodes to get lhs first.
257        final Iterator<Class<?>> iter = node instanceof BinaryNode ? stack.descendingIterator() : stack.iterator();
258
259        while (iter.hasNext()) {
260            final Class<?> c = iter.next();
261            for (final Field f : c.getDeclaredFields()) {
262                try {
263                    f.setAccessible(true);
264                    final Object child = f.get(node);
265                    if (child == null) {
266                        continue;
267                    }
268
269                    if (child instanceof Node) {
270                        children.add(f);
271                    } else if (child instanceof Collection) {
272                        if (!((Collection<?>)child).isEmpty()) {
273                            children.add(f);
274                        }
275                    }
276                } catch (final IllegalArgumentException | IllegalAccessException e) {
277                    return;
278                }
279            }
280        }
281    }
282
283    private static void indent(final StringBuilder sb, final int indent) {
284        for (int i = 0; i < indent; i++) {
285            for (int j = 0; j < TABWIDTH; j++) {
286                sb.append(' ');
287            }
288        }
289    }
290}
291