1 /* 2 * Copyright (c) 2014, 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.codegen; 27 28 import static jdk.nashorn.internal.ir.Node.NO_FINISH; 29 import static jdk.nashorn.internal.ir.Node.NO_LINE_NUMBER; 30 import static jdk.nashorn.internal.ir.Node.NO_TOKEN; 31 32 import java.util.ArrayDeque; 33 import java.util.ArrayList; 34 import java.util.Arrays; 35 import java.util.Collections; 36 import java.util.Deque; 37 import java.util.List; 38 import java.util.Objects; 39 import jdk.nashorn.internal.ir.AccessNode; 40 import jdk.nashorn.internal.ir.BinaryNode; 41 import jdk.nashorn.internal.ir.Block; 42 import jdk.nashorn.internal.ir.BlockLexicalContext; 43 import jdk.nashorn.internal.ir.BreakNode; 44 import jdk.nashorn.internal.ir.CallNode; 45 import jdk.nashorn.internal.ir.CaseNode; 46 import jdk.nashorn.internal.ir.ContinueNode; 47 import jdk.nashorn.internal.ir.Expression; 48 import jdk.nashorn.internal.ir.ExpressionStatement; 49 import jdk.nashorn.internal.ir.FunctionNode; 50 import jdk.nashorn.internal.ir.FunctionNode.CompilationState; 51 import jdk.nashorn.internal.ir.GetSplitState; 52 import jdk.nashorn.internal.ir.IdentNode; 53 import jdk.nashorn.internal.ir.IfNode; 54 import jdk.nashorn.internal.ir.JumpStatement; 55 import jdk.nashorn.internal.ir.JumpToInlinedFinally; 56 import jdk.nashorn.internal.ir.LiteralNode; 57 import jdk.nashorn.internal.ir.Node; 58 import jdk.nashorn.internal.ir.ReturnNode; 59 import jdk.nashorn.internal.ir.SetSplitState; 60 import jdk.nashorn.internal.ir.SplitNode; 61 import jdk.nashorn.internal.ir.SplitReturn; 62 import jdk.nashorn.internal.ir.Statement; 63 import jdk.nashorn.internal.ir.SwitchNode; 64 import jdk.nashorn.internal.ir.VarNode; 65 import jdk.nashorn.internal.ir.visitor.NodeVisitor; 66 import jdk.nashorn.internal.parser.Token; 67 import jdk.nashorn.internal.parser.TokenType; 68 69 /** 70 * A node visitor that replaces {@link SplitNode}s with anonymous function invocations and some additional constructs 71 * to support control flow across splits. By using this transformation, split functions are translated into ordinary 72 * JavaScript functions with nested anonymous functions. The transformations however introduce several AST nodes that 73 * have no JavaScript source representations ({@link GetSplitState}, {@link SetSplitState}, and {@link SplitReturn}), 74 * and therefore such function is no longer reparseable from its source. For that reason, split functions and their 75 * fragments are serialized in-memory and deserialized when they need to be recompiled either for deoptimization or 76 * for type specialization. 77 * NOTE: all {@code leave*()} methods for statements are returning their input nodes. That way, they will not mutate 78 * the original statement list in the block containing the statement, which is fine, as it'll be replaced by the 79 * lexical context when the block is left. If we returned something else (e.g. null), we'd cause a mutation in the 80 * enclosing block's statement list that is otherwise overwritten later anyway. 81 */ 82 final class SplitIntoFunctions extends NodeVisitor<BlockLexicalContext> { 83 private static final int FALLTHROUGH_STATE = -1; 84 private static final int RETURN_STATE = 0; 85 private static final int BREAK_STATE = 1; 86 private static final int FIRST_JUMP_STATE = 2; 87 88 private static final String THIS_NAME = CompilerConstants.THIS.symbolName(); 89 private static final String RETURN_NAME = CompilerConstants.RETURN.symbolName(); 90 // Used as the name of the formal parameter for passing the current value of :return symbol into a split fragment. 91 private static final String RETURN_PARAM_NAME = RETURN_NAME + "-in"; 92 93 private final Deque<FunctionState> functionStates = new ArrayDeque<>(); 94 private final Deque<SplitState> splitStates = new ArrayDeque<>(); 95 private final Namespace namespace; 96 97 private boolean artificialBlock = false; 98 99 // -1 is program; we need to use negative ones 100 private int nextFunctionId = -2; 101 102 public SplitIntoFunctions(final Compiler compiler) { 103 super(new BlockLexicalContext() { 104 @Override 105 protected Block afterSetStatements(final Block block) { 106 for(Statement stmt: block.getStatements()) { 107 assert !(stmt instanceof SplitNode); 108 } 109 return block; 110 } 111 }); 112 namespace = new Namespace(compiler.getScriptEnvironment().getNamespace()); 113 } 114 115 @Override 116 public boolean enterFunctionNode(final FunctionNode functionNode) { 117 functionStates.push(new FunctionState(functionNode)); 118 return true; 119 } 120 121 @Override 122 public Node leaveFunctionNode(final FunctionNode functionNode) { 123 functionStates.pop(); 124 return functionNode; 125 } 126 127 @Override 128 protected Node leaveDefault(final Node node) { 129 if (node instanceof Statement) { 130 appendStatement((Statement)node); 131 } 132 return node; 133 } 134 135 @Override 136 public boolean enterSplitNode(final SplitNode splitNode) { 137 getCurrentFunctionState().splitDepth++; 138 splitStates.push(new SplitState(splitNode)); 139 return true; 140 } 141 142 @Override 143 public Node leaveSplitNode(final SplitNode splitNode) { 144 // Replace the split node with an anonymous function expression call. 145 146 final FunctionState fnState = getCurrentFunctionState(); 147 148 final String name = splitNode.getName(); 149 Block body = splitNode.getBody(); 150 final int firstLineNumber = body.getFirstStatementLineNumber(); 151 final long token = body.getToken(); 152 final int finish = body.getFinish(); 153 154 final FunctionNode originalFn = fnState.fn; 155 assert originalFn == lc.getCurrentFunction(); 156 final boolean isProgram = originalFn.isProgram(); 157 158 // Change SplitNode({...}) into "function () { ... }", or "function (:return-in) () { ... }" (for program) 159 final long newFnToken = Token.toDesc(TokenType.FUNCTION, nextFunctionId--, 0); 160 final FunctionNode fn = new FunctionNode( 161 originalFn.getSource(), 162 body.getFirstStatementLineNumber(), 163 newFnToken, 164 finish, 165 newFnToken, 166 NO_TOKEN, 167 namespace, 168 createIdent(name), 169 originalFn.getName() + "$" + name, 170 isProgram ? Collections.singletonList(createReturnParamIdent()) : Collections.<IdentNode>emptyList(), 171 FunctionNode.Kind.NORMAL, 172 // We only need IS_SPLIT conservatively, in case it contains any array units so that we force 173 // the :callee's existence, to force :scope to never be in a slot lower than 2. This is actually 174 // quite a horrible hack to do with CodeGenerator.fixScopeSlot not trampling other parameters 175 // and should go away once we no longer have array unit handling in codegen. Note however that 176 // we still use IS_SPLIT as the criteria in CompilationPhase.SERIALIZE_SPLIT_PHASE. 177 FunctionNode.IS_ANONYMOUS | FunctionNode.USES_ANCESTOR_SCOPE | FunctionNode.IS_SPLIT, 178 body, 179 CompilationState.INITIALIZED, 180 null 181 ) 182 .setCompileUnit(lc, splitNode.getCompileUnit()) 183 .copyCompilationState(lc, originalFn); 184 185 // Call the function: 186 // either "(function () { ... }).call(this)" 187 // or "(function (:return-in) { ... }).call(this, :return)" 188 // NOTE: Function.call() has optimized linking that basically does a pass-through to the function being invoked. 189 // NOTE: CompilationPhase.PROGRAM_POINT_PHASE happens after this, so these calls are subject to optimistic 190 // assumptions on their return value (when they return a value), as they should be. 191 final IdentNode thisIdent = createIdent(THIS_NAME); 192 final CallNode callNode = new CallNode(firstLineNumber, token, finish, new AccessNode(NO_TOKEN, NO_FINISH, fn, "call"), 193 isProgram ? Arrays.<Expression>asList(thisIdent, createReturnIdent()) 194 : Collections.<Expression>singletonList(thisIdent), 195 false); 196 197 final SplitState splitState = splitStates.pop(); 198 fnState.splitDepth--; 199 200 final Expression callWithReturn; 201 final boolean hasReturn = splitState.hasReturn; 202 if (hasReturn && fnState.splitDepth > 0) { 203 final SplitState parentSplit = splitStates.peek(); 204 if (parentSplit != null) { 205 // Propagate hasReturn to parent split 206 parentSplit.hasReturn = true; 207 } 208 } 209 if (hasReturn || isProgram) { 210 // capture return value: ":return = (function () { ... })();" 211 callWithReturn = new BinaryNode(Token.recast(token, TokenType.ASSIGN), createReturnIdent(), callNode); 212 } else { 213 // no return value, just call : "(function () { ... })();" 214 callWithReturn = callNode; 215 } 216 appendStatement(new ExpressionStatement(firstLineNumber, token, finish, callWithReturn)); 217 218 Statement splitStateHandler; 219 220 final List<JumpStatement> jumpStatements = splitState.jumpStatements; 221 final int jumpCount = jumpStatements.size(); 222 // There are jumps (breaks or continues) that need to be propagated outside the split node. We need to 223 // set up a switch statement for them: 224 // switch(:scope.getScopeState()) { ... } 225 if (jumpCount > 0) { 226 final List<CaseNode> cases = new ArrayList<>(jumpCount + (hasReturn ? 1 : 0)); 227 if (hasReturn) { 228 // If the split node also contained a return, we'll slip it as a case in the switch statement 229 addCase(cases, RETURN_STATE, createReturnFromSplit()); 230 } 231 int i = FIRST_JUMP_STATE; 232 for (final JumpStatement jump: jumpStatements) { 233 addCase(cases, i++, enblockAndVisit(jump)); 234 } 235 splitStateHandler = new SwitchNode(NO_LINE_NUMBER, token, finish, GetSplitState.INSTANCE, cases, null); 236 } else { 237 splitStateHandler = null; 238 } 239 240 // As the switch statement itself is breakable, an unlabelled break can't be in the switch statement, 241 // so we need to test for it separately. 242 if (splitState.hasBreak) { 243 // if(:scope.getScopeState() == Scope.BREAK) { break; } 244 splitStateHandler = makeIfStateEquals(firstLineNumber, token, finish, BREAK_STATE, 245 enblockAndVisit(new BreakNode(NO_LINE_NUMBER, token, finish, null)), splitStateHandler); 246 } 247 248 // Finally, if the split node had a return statement, but there were no external jumps, we didn't have 249 // the switch statement to handle the return, so we need a separate if for it. 250 if (hasReturn && jumpCount == 0) { 251 // if (:scope.getScopeState() == Scope.RETURN) { return :return; } 252 splitStateHandler = makeIfStateEquals(NO_LINE_NUMBER, token, finish, RETURN_STATE, 253 createReturnFromSplit(), splitStateHandler); 254 } 255 256 if (splitStateHandler != null) { 257 appendStatement(splitStateHandler); 258 } 259 260 return splitNode; 261 } 262 263 private static void addCase(final List<CaseNode> cases, final int i, final Block body) { 264 cases.add(new CaseNode(NO_TOKEN, NO_FINISH, intLiteral(i), body)); 265 } 266 267 private static LiteralNode<Number> intLiteral(final int i) { 268 return LiteralNode.newInstance(NO_TOKEN, NO_FINISH, i); 269 } 270 271 private static Block createReturnFromSplit() { 272 return new Block(NO_TOKEN, NO_FINISH, createReturnReturn()); 273 } 274 275 private static ReturnNode createReturnReturn() { 276 return new ReturnNode(NO_LINE_NUMBER, NO_TOKEN, NO_FINISH, createReturnIdent()); 277 } 278 279 private static IdentNode createReturnIdent() { 280 return createIdent(RETURN_NAME); 281 } 282 283 private static IdentNode createReturnParamIdent() { 284 return createIdent(RETURN_PARAM_NAME); 285 } 286 287 private static IdentNode createIdent(final String name) { 288 return new IdentNode(NO_TOKEN, NO_FINISH, name); 289 } 290 291 private Block enblockAndVisit(final JumpStatement jump) { 292 artificialBlock = true; 293 final Block block = (Block)new Block(NO_TOKEN, NO_FINISH, jump).accept(this); 294 artificialBlock = false; 295 return block; 296 } 297 298 private static IfNode makeIfStateEquals(final int lineNumber, final long token, final int finish, 299 final int value, final Block pass, final Statement fail) { 300 return new IfNode(lineNumber, token, finish, 301 new BinaryNode(Token.recast(token, TokenType.EQ_STRICT), 302 GetSplitState.INSTANCE, intLiteral(value)), 303 pass, 304 fail == null ? null : new Block(NO_TOKEN, NO_FINISH, fail)); 305 } 306 307 @Override 308 public boolean enterVarNode(final VarNode varNode) { 309 if (!inSplitNode()) { 310 return super.enterVarNode(varNode); 311 } 312 assert !varNode.isBlockScoped(); //TODO: we must handle these too, but we currently don't 313 314 final Expression init = varNode.getInit(); 315 316 // Move a declaration-only var statement to the top of the outermost function. 317 getCurrentFunctionState().varStatements.add(varNode.setInit(null)); 318 // If it had an initializer, replace it with an assignment expression statement. Note that "var" is a 319 // statement, so it doesn't contribute to :return of the programs, therefore we are _not_ adding a 320 // ":return = ..." assignment around the original assignment. 321 if (init != null) { 322 final long token = Token.recast(varNode.getToken(), TokenType.ASSIGN); 323 new ExpressionStatement(varNode.getLineNumber(), token, varNode.getFinish(), 324 new BinaryNode(token, varNode.getName(), varNode.getInit())).accept(this); 325 } 326 327 return false; 328 } 329 330 @Override 331 public Node leaveBlock(final Block block) { 332 if (!artificialBlock) { 333 if (lc.isFunctionBody()) { 334 // Prepend declaration-only var statements to the top of the statement list. 335 lc.prependStatements(getCurrentFunctionState().varStatements); 336 } else if (lc.isSplitBody()) { 337 appendSplitReturn(FALLTHROUGH_STATE, NO_LINE_NUMBER); 338 if (getCurrentFunctionState().fn.isProgram()) { 339 // If we're splitting the program, make sure every shard ends with "return :return" and 340 // begins with ":return = :return-in;". 341 lc.prependStatement(new ExpressionStatement(NO_LINE_NUMBER, NO_TOKEN, NO_FINISH, 342 new BinaryNode(Token.toDesc(TokenType.ASSIGN, 0, 0), createReturnIdent(), createReturnParamIdent()))); 343 } 344 } 345 } 346 return block; 347 } 348 349 @Override 350 public Node leaveBreakNode(final BreakNode breakNode) { 351 return leaveJumpNode(breakNode); 352 } 353 354 @Override 355 public Node leaveContinueNode(final ContinueNode continueNode) { 356 return leaveJumpNode(continueNode); 357 } 358 359 @Override 360 public Node leaveJumpToInlinedFinally(final JumpToInlinedFinally jumpToInlinedFinally) { 361 return leaveJumpNode(jumpToInlinedFinally); 362 } 363 364 private JumpStatement leaveJumpNode(final JumpStatement jump) { 365 if (inSplitNode()) { 366 final SplitState splitState = getCurrentSplitState(); 367 final SplitNode splitNode = splitState.splitNode; 368 if (lc.isExternalTarget(splitNode, jump.getTarget(lc))) { 369 appendSplitReturn(splitState.getSplitStateIndex(jump), jump.getLineNumber()); 370 return jump; 371 } 372 } 373 appendStatement(jump); 374 return jump; 375 } 376 377 private void appendSplitReturn(final int splitState, final int lineNumber) { 378 appendStatement(new SetSplitState(splitState, lineNumber)); 379 if (getCurrentFunctionState().fn.isProgram()) { 380 // If we're splitting the program, make sure every fragment passes back :return 381 appendStatement(createReturnReturn()); 382 } else { 383 appendStatement(SplitReturn.INSTANCE); 384 } 385 } 386 387 @Override 388 public Node leaveReturnNode(final ReturnNode returnNode) { 389 if(inSplitNode()) { 390 appendStatement(new SetSplitState(RETURN_STATE, returnNode.getLineNumber())); 391 getCurrentSplitState().hasReturn = true; 392 } 393 appendStatement(returnNode); 394 return returnNode; 395 } 396 397 private void appendStatement(final Statement statement) { 398 lc.appendStatement(statement); 399 } 400 401 private boolean inSplitNode() { 402 return getCurrentFunctionState().splitDepth > 0; 403 } 404 405 private FunctionState getCurrentFunctionState() { 406 return functionStates.peek(); 407 } 408 409 private SplitState getCurrentSplitState() { 410 return splitStates.peek(); 411 } 412 413 private static class FunctionState { 414 final FunctionNode fn; 415 final List<Statement> varStatements = new ArrayList<>(); 416 int splitDepth; 417 418 FunctionState(final FunctionNode fn) { 419 this.fn = fn; 420 } 421 } 422 423 private static class SplitState { 424 final SplitNode splitNode; 425 boolean hasReturn; 426 boolean hasBreak; 427 428 final List<JumpStatement> jumpStatements = new ArrayList<>(); 429 430 int getSplitStateIndex(final JumpStatement jump) { 431 if (jump instanceof BreakNode && jump.getLabelName() == null) { 432 // Unlabelled break is a special case 433 hasBreak = true; 434 return BREAK_STATE; 435 } 436 437 int i = 0; 438 for(final JumpStatement exJump: jumpStatements) { 439 if (jump.getClass() == exJump.getClass() && Objects.equals(jump.getLabelName(), exJump.getLabelName())) { 440 return i + FIRST_JUMP_STATE; 441 } 442 ++i; 443 } 444 jumpStatements.add(jump); 445 return i + FIRST_JUMP_STATE; 446 } 447 448 SplitState(final SplitNode splitNode) { 449 this.splitNode = splitNode; 450 } 451 } 452 }