| /* |
| * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| package jdk.nashorn.internal.codegen; |
| |
| import static jdk.nashorn.internal.codegen.CompilerConstants.EVAL; |
| import static jdk.nashorn.internal.codegen.CompilerConstants.RETURN; |
| import static jdk.nashorn.internal.codegen.CompilerConstants.THIS; |
| |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| import java.util.List; |
| import jdk.nashorn.internal.ir.BaseNode; |
| import jdk.nashorn.internal.ir.BinaryNode; |
| import jdk.nashorn.internal.ir.Block; |
| import jdk.nashorn.internal.ir.BlockLexicalContext; |
| import jdk.nashorn.internal.ir.BreakNode; |
| import jdk.nashorn.internal.ir.CallNode; |
| import jdk.nashorn.internal.ir.CatchNode; |
| import jdk.nashorn.internal.ir.ContinueNode; |
| import jdk.nashorn.internal.ir.EmptyNode; |
| import jdk.nashorn.internal.ir.ExecuteNode; |
| import jdk.nashorn.internal.ir.ForNode; |
| import jdk.nashorn.internal.ir.FunctionNode; |
| import jdk.nashorn.internal.ir.FunctionNode.CompilationState; |
| import jdk.nashorn.internal.ir.IdentNode; |
| import jdk.nashorn.internal.ir.IfNode; |
| import jdk.nashorn.internal.ir.LabelNode; |
| import jdk.nashorn.internal.ir.LexicalContext; |
| import jdk.nashorn.internal.ir.LiteralNode; |
| import jdk.nashorn.internal.ir.LoopNode; |
| import jdk.nashorn.internal.ir.Node; |
| import jdk.nashorn.internal.ir.ReturnNode; |
| import jdk.nashorn.internal.ir.Statement; |
| import jdk.nashorn.internal.ir.SwitchNode; |
| import jdk.nashorn.internal.ir.Symbol; |
| import jdk.nashorn.internal.ir.ThrowNode; |
| import jdk.nashorn.internal.ir.TryNode; |
| import jdk.nashorn.internal.ir.VarNode; |
| import jdk.nashorn.internal.ir.WhileNode; |
| import jdk.nashorn.internal.ir.WithNode; |
| import jdk.nashorn.internal.ir.visitor.NodeOperatorVisitor; |
| import jdk.nashorn.internal.ir.visitor.NodeVisitor; |
| import jdk.nashorn.internal.parser.Token; |
| import jdk.nashorn.internal.parser.TokenType; |
| import jdk.nashorn.internal.runtime.DebugLogger; |
| import jdk.nashorn.internal.runtime.ScriptRuntime; |
| import jdk.nashorn.internal.runtime.Source; |
| |
| /** |
| * Lower to more primitive operations. After lowering, an AST still has no symbols |
| * and types, but several nodes have been turned into more low level constructs |
| * and control flow termination criteria have been computed. |
| * |
| * We do things like code copying/inlining of finallies here, as it is much |
| * harder and context dependent to do any code copying after symbols have been |
| * finalized. |
| */ |
| |
| final class Lower extends NodeOperatorVisitor<BlockLexicalContext> { |
| |
| private static final DebugLogger LOG = new DebugLogger("lower"); |
| |
| /** |
| * Constructor. |
| * |
| * @param compiler the compiler |
| */ |
| Lower() { |
| super(new BlockLexicalContext() { |
| |
| @Override |
| public List<Statement> popStatements() { |
| final List<Statement> newStatements = new ArrayList<>(); |
| boolean terminated = false; |
| |
| final List<Statement> statements = super.popStatements(); |
| for (final Statement statement : statements) { |
| if (!terminated) { |
| newStatements.add(statement); |
| if (statement.isTerminal() || statement instanceof BreakNode || statement instanceof ContinueNode) { //TODO hasGoto? But some Loops are hasGoto too - why? |
| terminated = true; |
| } |
| } else { |
| statement.accept(new NodeVisitor<LexicalContext>(new LexicalContext()) { |
| @Override |
| public boolean enterVarNode(final VarNode varNode) { |
| newStatements.add(varNode.setInit(null)); |
| return false; |
| } |
| }); |
| } |
| } |
| return newStatements; |
| } |
| }); |
| } |
| |
| @Override |
| public boolean enterBlock(final Block block) { |
| final FunctionNode function = lc.getCurrentFunction(); |
| if (lc.isFunctionBody() && function.isProgram() && !function.hasDeclaredFunctions()) { |
| new ExecuteNode(block.getLineNumber(), block.getToken(), block.getFinish(), LiteralNode.newInstance(block, ScriptRuntime.UNDEFINED)).accept(this); |
| } |
| return true; |
| } |
| |
| @Override |
| public Node leaveBlock(final Block block) { |
| //now we have committed the entire statement list to the block, but we need to truncate |
| //whatever is after the last terminal. block append won't append past it |
| |
| Statement last = lc.getLastStatement(); |
| |
| if (lc.isFunctionBody()) { |
| final FunctionNode currentFunction = lc.getCurrentFunction(); |
| final boolean isProgram = currentFunction.isProgram(); |
| final ReturnNode returnNode = new ReturnNode( |
| last == null ? block.getLineNumber() : last.getLineNumber(), //TODO? |
| currentFunction.getToken(), |
| currentFunction.getFinish(), |
| isProgram ? |
| compilerConstant(RETURN) : |
| LiteralNode.newInstance(block, ScriptRuntime.UNDEFINED)); |
| |
| last = (Statement)returnNode.accept(this); |
| } |
| |
| if (last != null && last.isTerminal()) { |
| return block.setIsTerminal(lc, true); |
| } |
| |
| return block; |
| } |
| |
| @Override |
| public boolean enterBreakNode(final BreakNode breakNode) { |
| addStatement(breakNode); |
| return false; |
| } |
| |
| @Override |
| public Node leaveCallNode(final CallNode callNode) { |
| return checkEval(callNode.setFunction(markerFunction(callNode.getFunction()))); |
| } |
| |
| @Override |
| public Node leaveCatchNode(final CatchNode catchNode) { |
| return addStatement(catchNode); |
| } |
| |
| @Override |
| public boolean enterContinueNode(final ContinueNode continueNode) { |
| addStatement(continueNode); |
| return false; |
| } |
| |
| @Override |
| public boolean enterEmptyNode(final EmptyNode emptyNode) { |
| return false; |
| } |
| |
| @Override |
| public Node leaveExecuteNode(final ExecuteNode executeNode) { |
| final Node expr = executeNode.getExpression(); |
| ExecuteNode node = executeNode; |
| |
| final FunctionNode currentFunction = lc.getCurrentFunction(); |
| |
| if (currentFunction.isProgram()) { |
| if (!(expr instanceof Block) || expr instanceof FunctionNode) { // it's not a block, but can be a function |
| if (!isInternalExpression(expr) && !isEvalResultAssignment(expr)) { |
| node = executeNode.setExpression( |
| new BinaryNode( |
| Token.recast( |
| executeNode.getToken(), |
| TokenType.ASSIGN), |
| compilerConstant(RETURN), |
| expr)); |
| } |
| } |
| } |
| |
| return addStatement(node); |
| } |
| |
| @Override |
| public Node leaveForNode(final ForNode forNode) { |
| ForNode newForNode = forNode; |
| |
| final Node test = forNode.getTest(); |
| if (!forNode.isForIn() && conservativeAlwaysTrue(test)) { |
| newForNode = forNode.setTest(lc, null); |
| } |
| |
| return addStatement(checkEscape(newForNode)); |
| } |
| |
| @Override |
| public boolean enterFunctionNode(final FunctionNode functionNode) { |
| return !functionNode.isLazy(); |
| } |
| |
| @Override |
| public Node leaveFunctionNode(final FunctionNode functionNode) { |
| LOG.info("END FunctionNode: ", functionNode.getName()); |
| return functionNode.setState(lc, CompilationState.LOWERED); |
| } |
| |
| @Override |
| public Node leaveIfNode(final IfNode ifNode) { |
| return addStatement(ifNode); |
| } |
| |
| @Override |
| public Node leaveLabelNode(final LabelNode labelNode) { |
| return addStatement(labelNode); |
| } |
| |
| @Override |
| public Node leaveReturnNode(final ReturnNode returnNode) { |
| addStatement(returnNode); //ReturnNodes are always terminal, marked as such in constructor |
| return returnNode; |
| } |
| |
| |
| @Override |
| public Node leaveSwitchNode(final SwitchNode switchNode) { |
| return addStatement(switchNode); |
| } |
| |
| @Override |
| public Node leaveThrowNode(final ThrowNode throwNode) { |
| addStatement(throwNode); //ThrowNodes are always terminal, marked as such in constructor |
| return throwNode; |
| } |
| |
| private static Node ensureUniqueNamesIn(final Node node) { |
| return node.accept(new NodeVisitor<LexicalContext>(new LexicalContext()) { |
| @Override |
| public Node leaveFunctionNode(final FunctionNode functionNode) { |
| final String name = functionNode.getName(); |
| return functionNode.setName(lc, lc.getCurrentFunction().uniqueName(name)); |
| } |
| |
| @Override |
| public Node leaveDefault(final Node labelledNode) { |
| return labelledNode.ensureUniqueLabels(lc); |
| } |
| }); |
| } |
| |
| private static List<Statement> copyFinally(final Block finallyBody) { |
| final List<Statement> newStatements = new ArrayList<>(); |
| for (final Statement statement : finallyBody.getStatements()) { |
| newStatements.add((Statement)ensureUniqueNamesIn(statement)); |
| if (statement.hasTerminalFlags()) { |
| return newStatements; |
| } |
| } |
| return newStatements; |
| } |
| |
| private Block catchAllBlock(final TryNode tryNode) { |
| final int lineNumber = tryNode.getLineNumber(); |
| final long token = tryNode.getToken(); |
| final int finish = tryNode.getFinish(); |
| |
| final IdentNode exception = new IdentNode(token, finish, lc.getCurrentFunction().uniqueName("catch_all")); |
| |
| final Block catchBody = new Block(lineNumber, token, finish, new ThrowNode(lineNumber, token, finish, new IdentNode(exception), ThrowNode.IS_SYNTHETIC_RETHROW)). |
| setIsTerminal(lc, true); //ends with throw, so terminal |
| |
| final CatchNode catchAllNode = new CatchNode(lineNumber, token, finish, new IdentNode(exception), null, catchBody, CatchNode.IS_SYNTHETIC_RETHROW); |
| final Block catchAllBlock = new Block(lineNumber, token, finish, catchAllNode); |
| |
| //catchallblock -> catchallnode (catchnode) -> exception -> throw |
| |
| return (Block)catchAllBlock.accept(this); //not accepted. has to be accepted by lower |
| } |
| |
| private IdentNode compilerConstant(final CompilerConstants cc) { |
| final FunctionNode functionNode = lc.getCurrentFunction(); |
| return new IdentNode(functionNode.getToken(), functionNode.getFinish(), cc.symbolName()); |
| } |
| |
| private static boolean isTerminal(final List<Statement> statements) { |
| return !statements.isEmpty() && statements.get(statements.size() - 1).hasTerminalFlags(); |
| } |
| |
| /** |
| * Splice finally code into all endpoints of a trynode |
| * @param tryNode the try node |
| * @param list of rethrowing throw nodes from synthetic catch blocks |
| * @param finallyBody the code in the original finally block |
| * @return new try node after splicing finally code (same if nop) |
| */ |
| private Node spliceFinally(final TryNode tryNode, final List<ThrowNode> rethrows, final Block finallyBody) { |
| assert tryNode.getFinallyBody() == null; |
| final int finish = tryNode.getFinish(); |
| |
| final TryNode newTryNode = (TryNode)tryNode.accept(new NodeVisitor<LexicalContext>(new LexicalContext()) { |
| final List<Node> insideTry = new ArrayList<>(); |
| |
| @Override |
| public boolean enterDefault(final Node node) { |
| insideTry.add(node); |
| return true; |
| } |
| |
| @Override |
| public boolean enterFunctionNode(final FunctionNode functionNode) { |
| // do not enter function nodes - finally code should not be inlined into them |
| return false; |
| } |
| |
| @Override |
| public Node leaveThrowNode(final ThrowNode throwNode) { |
| if (rethrows.contains(throwNode)) { |
| final List<Statement> newStatements = copyFinally(finallyBody); |
| if (!isTerminal(newStatements)) { |
| newStatements.add(throwNode); |
| } |
| return new Block(throwNode.getLineNumber(), throwNode.getToken(), throwNode.getFinish(), newStatements); |
| } |
| return throwNode; |
| } |
| |
| @Override |
| public Node leaveBreakNode(final BreakNode breakNode) { |
| return copy(breakNode, Lower.this.lc.getBreakable(breakNode.getLabel())); |
| } |
| |
| @Override |
| public Node leaveContinueNode(final ContinueNode continueNode) { |
| return copy(continueNode, Lower.this.lc.getContinueTo(continueNode.getLabel())); |
| } |
| |
| @Override |
| public Node leaveReturnNode(final ReturnNode returnNode) { |
| final Node expr = returnNode.getExpression(); |
| final List<Statement> newStatements = new ArrayList<>(); |
| |
| final Node resultNode; |
| if (expr != null) { |
| //we need to evaluate the result of the return in case it is complex while |
| //still in the try block, store it in a result value and return it afterwards |
| resultNode = new IdentNode(Lower.this.compilerConstant(RETURN)); |
| newStatements.add(new ExecuteNode(returnNode.getLineNumber(), returnNode.getToken(), returnNode.getFinish(), new BinaryNode(Token.recast(returnNode.getToken(), TokenType.ASSIGN), resultNode, expr))); |
| } else { |
| resultNode = null; |
| } |
| |
| newStatements.addAll(copyFinally(finallyBody)); |
| if (!isTerminal(newStatements)) { |
| newStatements.add(expr == null ? returnNode : returnNode.setExpression(resultNode)); |
| } |
| |
| return new ExecuteNode(returnNode.getLineNumber(), returnNode.getToken(), returnNode.getFinish(), new Block(returnNode.getLineNumber(), returnNode.getToken(), lc.getCurrentBlock().getFinish(), newStatements)); |
| } |
| |
| private Node copy(final Statement endpoint, final Node targetNode) { |
| if (!insideTry.contains(targetNode)) { |
| final List<Statement> newStatements = copyFinally(finallyBody); |
| if (!isTerminal(newStatements)) { |
| newStatements.add(endpoint); |
| } |
| return new ExecuteNode(endpoint.getLineNumber(), endpoint.getToken(), endpoint.getFinish(), new Block(endpoint.getLineNumber(), endpoint.getToken(), finish, newStatements)); |
| } |
| return endpoint; |
| } |
| }); |
| |
| addStatement(newTryNode); |
| for (final Node statement : finallyBody.getStatements()) { |
| addStatement((Statement)statement); |
| } |
| |
| return newTryNode; |
| } |
| |
| @Override |
| public Node leaveTryNode(final TryNode tryNode) { |
| final Block finallyBody = tryNode.getFinallyBody(); |
| |
| if (finallyBody == null) { |
| return addStatement(tryNode); |
| } |
| |
| /* |
| * create a new trynode |
| * if we have catches: |
| * |
| * try try |
| * x try |
| * catch x |
| * y catch |
| * finally z y |
| * catchall |
| * rethrow |
| * |
| * otheriwse |
| * |
| * try try |
| * x x |
| * finally catchall |
| * y rethrow |
| * |
| * |
| * now splice in finally code wherever needed |
| * |
| */ |
| TryNode newTryNode; |
| |
| final Block catchAll = catchAllBlock(tryNode); |
| |
| final List<ThrowNode> rethrows = new ArrayList<>(); |
| catchAll.accept(new NodeVisitor<LexicalContext>(new LexicalContext()) { |
| @Override |
| public boolean enterThrowNode(final ThrowNode throwNode) { |
| rethrows.add(throwNode); |
| return true; |
| } |
| }); |
| assert rethrows.size() == 1; |
| |
| if (tryNode.getCatchBlocks().isEmpty()) { |
| newTryNode = tryNode.setFinallyBody(null); |
| } else { |
| Block outerBody = new Block(tryNode.getLineNumber(), tryNode.getToken(), tryNode.getFinish(), new ArrayList<Statement>(Arrays.asList(tryNode.setFinallyBody(null)))); |
| newTryNode = tryNode.setBody(outerBody).setCatchBlocks(null); |
| } |
| |
| newTryNode = newTryNode.setCatchBlocks(Arrays.asList(catchAll)).setFinallyBody(null); |
| |
| /* |
| * Now that the transform is done, we have to go into the try and splice |
| * the finally block in front of any statement that is outside the try |
| */ |
| return spliceFinally(newTryNode, rethrows, finallyBody); |
| } |
| |
| @Override |
| public Node leaveVarNode(final VarNode varNode) { |
| addStatement(varNode); |
| if (varNode.getFlag(VarNode.IS_LAST_FUNCTION_DECLARATION) && lc.getCurrentFunction().isProgram()) { |
| new ExecuteNode(varNode.getLineNumber(), varNode.getToken(), varNode.getFinish(), new IdentNode(varNode.getName())).accept(this); |
| } |
| return varNode; |
| } |
| |
| @Override |
| public Node leaveWhileNode(final WhileNode whileNode) { |
| final Node test = whileNode.getTest(); |
| final Block body = whileNode.getBody(); |
| |
| if (conservativeAlwaysTrue(test)) { |
| //turn it into a for node without a test. |
| final ForNode forNode = (ForNode)new ForNode(whileNode.getLineNumber(), whileNode.getToken(), whileNode.getFinish(), null, null, body, null, ForNode.IS_FOR).accept(this); |
| lc.replace(whileNode, forNode); |
| return forNode; |
| } |
| |
| return addStatement(checkEscape(whileNode)); |
| } |
| |
| @Override |
| public Node leaveWithNode(final WithNode withNode) { |
| return addStatement(withNode); |
| } |
| |
| /** |
| * Given a function node that is a callee in a CallNode, replace it with |
| * the appropriate marker function. This is used by {@link CodeGenerator} |
| * for fast scope calls |
| * |
| * @param function function called by a CallNode |
| * @return transformed node to marker function or identity if not ident/access/indexnode |
| */ |
| private static Node markerFunction(final Node function) { |
| if (function instanceof IdentNode) { |
| return ((IdentNode)function).setIsFunction(); |
| } else if (function instanceof BaseNode) { |
| return ((BaseNode)function).setIsFunction(); |
| } |
| return function; |
| } |
| |
| /** |
| * Calculate a synthetic eval location for a node for the stacktrace, for example src#17<eval> |
| * @param node a node |
| * @return eval location |
| */ |
| private String evalLocation(final IdentNode node) { |
| final Source source = lc.getCurrentFunction().getSource(); |
| return new StringBuilder(). |
| append(source.getName()). |
| append('#'). |
| append(source.getLine(node.position())). |
| append("<eval>"). |
| toString(); |
| } |
| |
| /** |
| * Check whether a call node may be a call to eval. In that case we |
| * clone the args in order to create the following construct in |
| * {@link CodeGenerator} |
| * |
| * <pre> |
| * if (calledFuntion == buildInEval) { |
| * eval(cloned arg); |
| * } else { |
| * cloned arg; |
| * } |
| * </pre> |
| * |
| * @param callNode call node to check if it's an eval |
| */ |
| private CallNode checkEval(final CallNode callNode) { |
| if (callNode.getFunction() instanceof IdentNode) { |
| |
| final List<Node> args = callNode.getArgs(); |
| final IdentNode callee = (IdentNode)callNode.getFunction(); |
| |
| // 'eval' call with at least one argument |
| if (args.size() >= 1 && EVAL.symbolName().equals(callee.getName())) { |
| final FunctionNode currentFunction = lc.getCurrentFunction(); |
| return callNode.setEvalArgs( |
| new CallNode.EvalArgs( |
| ensureUniqueNamesIn(args.get(0)).accept(this), |
| compilerConstant(THIS), |
| evalLocation(callee), |
| currentFunction.isStrict())); |
| } |
| } |
| |
| return callNode; |
| } |
| |
| private static boolean conservativeAlwaysTrue(final Node node) { |
| return node == null || ((node instanceof LiteralNode) && Boolean.TRUE.equals(((LiteralNode<?>)node).getValue())); |
| } |
| |
| /** |
| * Helper that given a loop body makes sure that it is not terminal if it |
| * has a continue that leads to the loop header or to outer loops' loop |
| * headers. This means that, even if the body ends with a terminal |
| * statement, we cannot tag it as terminal |
| * |
| * @param loopBody the loop body to check |
| * @return true if control flow may escape the loop |
| */ |
| private static boolean controlFlowEscapes(final LexicalContext lex, final Block loopBody) { |
| final List<Node> escapes = new ArrayList<>(); |
| |
| loopBody.accept(new NodeVisitor<LexicalContext>(new LexicalContext()) { |
| @Override |
| public Node leaveBreakNode(final BreakNode node) { |
| escapes.add(node); |
| return node; |
| } |
| |
| @Override |
| public Node leaveContinueNode(final ContinueNode node) { |
| // all inner loops have been popped. |
| if (lex.contains(lex.getContinueTo(node.getLabel()))) { |
| escapes.add(node); |
| } |
| return node; |
| } |
| }); |
| |
| return !escapes.isEmpty(); |
| } |
| |
| private LoopNode checkEscape(final LoopNode loopNode) { |
| final boolean escapes = controlFlowEscapes(lc, loopNode.getBody()); |
| if (escapes) { |
| return loopNode. |
| setBody(lc, loopNode.getBody().setIsTerminal(lc, false)). |
| setControlFlowEscapes(lc, escapes); |
| } |
| return loopNode; |
| } |
| |
| |
| private Node addStatement(final Statement statement) { |
| lc.appendStatement(statement); |
| return statement; |
| } |
| |
| /** |
| * An internal expression has a symbol that is tagged internal. Check if |
| * this is such a node |
| * |
| * @param expression expression to check for internal symbol |
| * @return true if internal, false otherwise |
| */ |
| private static boolean isInternalExpression(final Node expression) { |
| final Symbol symbol = expression.getSymbol(); |
| return symbol != null && symbol.isInternal(); |
| } |
| |
| /** |
| * Is this an assignment to the special variable that hosts scripting eval |
| * results, i.e. __return__? |
| * |
| * @param expression expression to check whether it is $evalresult = X |
| * @return true if an assignment to eval result, false otherwise |
| */ |
| private static boolean isEvalResultAssignment(final Node expression) { |
| Node e = expression; |
| assert e.tokenType() != TokenType.DISCARD; //there are no discards this early anymore |
| if (e instanceof BinaryNode) { |
| final Node lhs = ((BinaryNode)e).lhs(); |
| if (lhs instanceof IdentNode) { |
| return ((IdentNode)lhs).getName().equals(RETURN.symbolName()); |
| } |
| } |
| return false; |
| } |
| |
| } |