ASTWriter.java revision 1498:a8b20725bcf2
1145519Sdarrenr/* 2145510Sdarrenr * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved. 331183Speter * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 431183Speter * 531183Speter * This code is free software; you can redistribute it and/or modify it 631183Speter * under the terms of the GNU General Public License version 2 only, as 731183Speter * published by the Free Software Foundation. Oracle designates this 831183Speter * particular file as subject to the "Classpath" exception as provided 931183Speter * by Oracle in the LICENSE file that accompanied this code. 1031183Speter * 1131183Speter * This code is distributed in the hope that it will be useful, but WITHOUT 1231183Speter * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1331183Speter * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1431183Speter * version 2 for more details (a copy is included in the LICENSE file that 1531183Speter * accompanied this code). 1631183Speter * 1731183Speter * You should have received a copy of the GNU General Public License version 1831183Speter * 2 along with this work; if not, write to the Free Software Foundation, 1931183Speter * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2031183Speter * 2131183Speter * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2231183Speter * or visit www.oracle.com if you need additional information or have any 2331183Speter * questions. 2431183Speter */ 2531183Speter 2631183Speterpackage jdk.nashorn.internal.ir.debug; 2731183Speter 2831183Speterimport java.lang.reflect.Field; 2931183Speterimport java.util.ArrayDeque; 3031183Speterimport java.util.ArrayList; 3131183Speterimport java.util.Collection; 3231183Speterimport java.util.Deque; 3331183Speterimport java.util.Iterator; 3431183Speterimport java.util.LinkedList; 3531183Speterimport java.util.List; 3631183Speterimport jdk.nashorn.internal.ir.BinaryNode; 3731183Speterimport jdk.nashorn.internal.ir.Block; 3831183Speterimport jdk.nashorn.internal.ir.Expression; 3931183Speterimport jdk.nashorn.internal.ir.IdentNode; 4031183Speterimport jdk.nashorn.internal.ir.Node; 4131183Speterimport jdk.nashorn.internal.ir.Statement; 4231183Speterimport jdk.nashorn.internal.ir.Symbol; 4331183Speterimport jdk.nashorn.internal.ir.Terminal; 4431183Speterimport jdk.nashorn.internal.ir.TernaryNode; 4531183Speterimport jdk.nashorn.internal.ir.annotations.Ignore; 4692686Sdarrenrimport jdk.nashorn.internal.ir.annotations.Reference; 4792686Sdarrenrimport jdk.nashorn.internal.parser.Token; 4831183Speterimport jdk.nashorn.internal.runtime.Context; 4931183Speterimport jdk.nashorn.internal.runtime.Debug; 50145510Sdarrenr 5131183Speter/** 5231183Speter * AST-as-text visualizer. Sometimes you want tree form and not source 5331183Speter * code. This works for both lowered and unlowered IR 54255332Scy * 55255332Scy * see the flags --print-ast and --print-ast-lower 5631183Speter */ 5731183Speterpublic final class ASTWriter { 58145510Sdarrenr private static final ClassValue<Field[]> accessibleFields = new ClassValue<Field[]>() { 5931183Speter @Override 6031183Speter protected Field[] computeValue(final Class<?> type) { 6131183Speter final Field[] fields = type.getDeclaredFields(); 6231183Speter for(final Field f: fields) { 6331183Speter f.setAccessible(true); 6431183Speter } 6531183Speter return fields; 6631183Speter } 6731183Speter }; 6831183Speter /** Root node from which to start the traversal */ 6931183Speter private final Node root; 7031183Speter 7131183Speter private static final int TABWIDTH = 4; 7231183Speter 7331183Speter /** 7431183Speter * Constructor 7531183Speter * @param root root of the AST to visualize 7631183Speter */ 7731183Speter public ASTWriter(final Node root) { 7831183Speter this.root = root; 7931183Speter } 8031183Speter 8131183Speter /** 8231183Speter * Use the ASTWriter by instantiating it and retrieving its String 83145510Sdarrenr * representation 84145510Sdarrenr * 85145510Sdarrenr * @return the string representation of the AST 86145510Sdarrenr */ 87145510Sdarrenr @Override 88145510Sdarrenr public String toString() { 8931183Speter final StringBuilder sb = new StringBuilder(); 9031183Speter printAST(sb, null, null, "root", root, 0); 9131183Speter return sb.toString(); 9231183Speter } 9331183Speter 9431183Speter /** 95145510Sdarrenr * Return the visited nodes in an ordered list 96153881Sguido * @return the list of nodes in order 97153881Sguido */ 9831183Speter public Node[] toArray() { 9931183Speter final List<Node> preorder = new ArrayList<>(); 10031183Speter printAST(new StringBuilder(), preorder, null, "root", root, 0); 10131183Speter return preorder.toArray(new Node[preorder.size()]); 102145510Sdarrenr } 103145510Sdarrenr 10492686Sdarrenr @SuppressWarnings("unchecked") 10531183Speter private void printAST(final StringBuilder sb, final List<Node> preorder, final Field field, final String name, final Node node, final int indent) { 10631183Speter ASTWriter.indent(sb, indent); 10792686Sdarrenr if (node == null) { 10892686Sdarrenr sb.append("[Object "); 10992686Sdarrenr sb.append(name); 11092686Sdarrenr sb.append(" null]\n"); 11192686Sdarrenr return; 11292686Sdarrenr } 11392686Sdarrenr 11431183Speter if (preorder != null) { 11531183Speter preorder.add(node); 11631183Speter } 11731183Speter 11834739Speter final boolean isReference = field != null && field.isAnnotationPresent(Reference.class); 11931183Speter 12031183Speter final Class<?> clazz = node.getClass(); 12131183Speter String type = clazz.getName(); 12231183Speter 12331183Speter type = type.substring(type.lastIndexOf('.') + 1, type.length()); 12431183Speter int truncate = type.indexOf("Node"); 12531183Speter if (truncate == -1) { 12631183Speter truncate = type.indexOf("Statement"); 12731183Speter } 12831183Speter if (truncate != -1) { 12992686Sdarrenr type = type.substring(0, truncate); 13031183Speter } 13192686Sdarrenr type = type.toLowerCase(); 13292686Sdarrenr 13392686Sdarrenr if (isReference) { 13492686Sdarrenr type = "ref: " + type; 135255332Scy } 136255332Scy final Symbol symbol; 137255332Scy if (node instanceof IdentNode) { 13892686Sdarrenr symbol = ((IdentNode)node).getSymbol(); 13992686Sdarrenr } else { 14092686Sdarrenr symbol = null; 14192686Sdarrenr } 14292686Sdarrenr 143145510Sdarrenr if (symbol != null) { 14492686Sdarrenr type += ">" + symbol; 14592686Sdarrenr } 14692686Sdarrenr 14792686Sdarrenr if (node instanceof Block && ((Block)node).needsScope()) { 14892686Sdarrenr type += " <scope>"; 14992686Sdarrenr } 15092686Sdarrenr 15192686Sdarrenr final List<Field> children = new LinkedList<>(); 15292686Sdarrenr 153145510Sdarrenr if (!isReference) { 154145510Sdarrenr enqueueChildren(node, clazz, children); 155145510Sdarrenr } 156145510Sdarrenr 157145510Sdarrenr String status = ""; 158145510Sdarrenr 15992686Sdarrenr if (node instanceof Terminal && ((Terminal)node).isTerminal()) { 16092686Sdarrenr status += " Terminal"; 16192686Sdarrenr } 16292686Sdarrenr 16392686Sdarrenr if (node instanceof Statement && ((Statement)node).hasGoto()) { 16492686Sdarrenr status += " Goto "; 16592686Sdarrenr } 16692686Sdarrenr 16792686Sdarrenr if (symbol != null) { 16892686Sdarrenr status += symbol; 16992686Sdarrenr } 17092686Sdarrenr 17192686Sdarrenr status = status.trim(); 17292686Sdarrenr if (!"".equals(status)) { 17392686Sdarrenr status = " [" + status + "]"; 17492686Sdarrenr } 17592686Sdarrenr 17692686Sdarrenr if (symbol != null) { 17792686Sdarrenr String tname = ((Expression)node).getType().toString(); 17892686Sdarrenr if (tname.indexOf('.') != -1) { 17992686Sdarrenr tname = tname.substring(tname.lastIndexOf('.') + 1, tname.length()); 18092686Sdarrenr } 18192686Sdarrenr status += " (" + tname + ")"; 18292686Sdarrenr } 18392686Sdarrenr 18492686Sdarrenr status += " @" + Debug.id(node); 18592686Sdarrenr 18692686Sdarrenr if (children.isEmpty()) { 18792686Sdarrenr sb.append("["). 18892686Sdarrenr append(type). 18992686Sdarrenr append(' '). 19092686Sdarrenr append(name). 19192686Sdarrenr append(" = '"). 19292686Sdarrenr append(node). 19392686Sdarrenr append("'"). 19492686Sdarrenr append(status). 19592686Sdarrenr append("] "). 19692686Sdarrenr append('\n'); 19792686Sdarrenr } else { 19892686Sdarrenr sb.append("["). 19992686Sdarrenr append(type). 20092686Sdarrenr append(' '). 20192686Sdarrenr append(name). 20292686Sdarrenr append(' '). 203145510Sdarrenr append(Token.toString(node.getToken())). 204145510Sdarrenr append(status). 205145510Sdarrenr append("]"). 206145510Sdarrenr append('\n'); 207145510Sdarrenr 208145510Sdarrenr for (final Field child : children) { 20992686Sdarrenr if (child.isAnnotationPresent(Ignore.class)) { 21092686Sdarrenr continue; 211145510Sdarrenr } 21292686Sdarrenr 21392686Sdarrenr Object value; 21492686Sdarrenr try { 21592686Sdarrenr value = child.get(node); 21692686Sdarrenr } catch (final IllegalArgumentException | IllegalAccessException e) { 21792686Sdarrenr Context.printStackTrace(e); 21892686Sdarrenr return; 21992686Sdarrenr } 22092686Sdarrenr 22192686Sdarrenr if (value instanceof Node) { 22292686Sdarrenr printAST(sb, preorder, child, child.getName(), (Node)value, indent + 1); 22392686Sdarrenr } else if (value instanceof Collection) { 22492686Sdarrenr int pos = 0; 22592686Sdarrenr ASTWriter.indent(sb, indent + 1); 22692686Sdarrenr sb.append('['). 22792686Sdarrenr append(child.getName()). 22892686Sdarrenr append("[0.."). 22992686Sdarrenr append(((Collection<Node>)value).size()). 23092686Sdarrenr append("]]"). 231255332Scy append('\n'); 23292686Sdarrenr 23392686Sdarrenr for (final Node member : (Collection<Node>)value) { 23492686Sdarrenr printAST(sb, preorder, child, child.getName() + "[" + pos++ + "]", member, indent + 2); 23592686Sdarrenr } 23692686Sdarrenr } 23792686Sdarrenr } 23892686Sdarrenr } 23992686Sdarrenr } 24092686Sdarrenr 24192686Sdarrenr private static void enqueueChildren(final Node node, final Class<?> nodeClass, final List<Field> children) { 24292686Sdarrenr final Deque<Class<?>> stack = new ArrayDeque<>(); 24392686Sdarrenr 24492686Sdarrenr /** 24592686Sdarrenr * Here is some ugliness that can be overcome by proper ChildNode annotations 24692686Sdarrenr * with proper orders. Right now we basically sort all classes up to Node 24792686Sdarrenr * with super class first, as this often is the natural order, e.g. base 24892686Sdarrenr * before index for an IndexNode. 24992686Sdarrenr * 25092686Sdarrenr * Also there are special cases as this is not true for UnaryNodes(lhs) and 25192686Sdarrenr * BinaryNodes extends UnaryNode (with lhs), and TernaryNodes. 25292686Sdarrenr * 25392686Sdarrenr * TODO - generalize traversal with an order built on annotations and this 25492686Sdarrenr * will go away. 25592686Sdarrenr */ 25692686Sdarrenr Class<?> clazz = nodeClass; 25792686Sdarrenr do { 25892686Sdarrenr stack.push(clazz); 25992686Sdarrenr clazz = clazz.getSuperclass(); 26092686Sdarrenr } while (clazz != null); 26192686Sdarrenr 26292686Sdarrenr if (node instanceof TernaryNode) { 26392686Sdarrenr // HACK juggle "third" 26492686Sdarrenr stack.push(stack.removeLast()); 26592686Sdarrenr } 26692686Sdarrenr // HACK change operator order for BinaryNodes to get lhs first. 26792686Sdarrenr final Iterator<Class<?>> iter = node instanceof BinaryNode ? stack.descendingIterator() : stack.iterator(); 26892686Sdarrenr 26992686Sdarrenr while (iter.hasNext()) { 27092686Sdarrenr final Class<?> c = iter.next(); 27192686Sdarrenr for (final Field f : accessibleFields.get(c)) { 27292686Sdarrenr try { 27392686Sdarrenr final Object child = f.get(node); 27492686Sdarrenr if (child == null) { 27592686Sdarrenr continue; 27692686Sdarrenr } 27792686Sdarrenr 27892686Sdarrenr if (child instanceof Node) { 27992686Sdarrenr children.add(f); 28092686Sdarrenr } else if (child instanceof Collection) { 28192686Sdarrenr if (!((Collection<?>)child).isEmpty()) { 28292686Sdarrenr children.add(f); 28392686Sdarrenr } 28492686Sdarrenr } 28592686Sdarrenr } catch (final IllegalArgumentException | IllegalAccessException e) { 28692686Sdarrenr return; 28792686Sdarrenr } 28892686Sdarrenr } 28992686Sdarrenr } 29092686Sdarrenr } 29192686Sdarrenr 29292686Sdarrenr private static void indent(final StringBuilder sb, final int indent) { 29392686Sdarrenr for (int i = 0; i < indent; i++) { 29492686Sdarrenr for (int j = 0; j < TABWIDTH; j++) { 29592686Sdarrenr sb.append(' '); 29692686Sdarrenr } 29792686Sdarrenr } 29892686Sdarrenr } 29992686Sdarrenr} 30092686Sdarrenr