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.GetSplitState;
51 import jdk.nashorn.internal.ir.IdentNode;
52 import jdk.nashorn.internal.ir.IfNode;
53 import jdk.nashorn.internal.ir.JumpStatement;
54 import jdk.nashorn.internal.ir.JumpToInlinedFinally;
55 import jdk.nashorn.internal.ir.LiteralNode;
56 import jdk.nashorn.internal.ir.Node;
57 import jdk.nashorn.internal.ir.ReturnNode;
58 import jdk.nashorn.internal.ir.SetSplitState;
59 import jdk.nashorn.internal.ir.SplitNode;
60 import jdk.nashorn.internal.ir.SplitReturn;
61 import jdk.nashorn.internal.ir.Statement;
62 import jdk.nashorn.internal.ir.SwitchNode;
63 import jdk.nashorn.internal.ir.VarNode;
64 import jdk.nashorn.internal.ir.visitor.NodeVisitor;
65 import jdk.nashorn.internal.parser.Token;
66 import jdk.nashorn.internal.parser.TokenType;
67
68 /**
69 * A node visitor that replaces {@link SplitNode}s with anonymous function invocations and some additional constructs
70 * to support control flow across splits. By using this transformation, split functions are translated into ordinary
71 * JavaScript functions with nested anonymous functions. The transformations however introduce several AST nodes that
72 * have no JavaScript source representations ({@link GetSplitState}, {@link SetSplitState}, and {@link SplitReturn}),
73 * and therefore such function is no longer reparseable from its source. For that reason, split functions and their
74 * fragments are serialized in-memory and deserialized when they need to be recompiled either for deoptimization or
75 * for type specialization.
76 * NOTE: all {@code leave*()} methods for statements are returning their input nodes. That way, they will not mutate
77 * the original statement list in the block containing the statement, which is fine, as it'll be replaced by the
78 * lexical context when the block is left. If we returned something else (e.g. null), we'd cause a mutation in the
79 * enclosing block's statement list that is otherwise overwritten later anyway.
80 */
81 final class SplitIntoFunctions extends NodeVisitor<BlockLexicalContext> {
82 private static final int FALLTHROUGH_STATE = -1;
83 private static final int RETURN_STATE = 0;
84 private static final int BREAK_STATE = 1;
85 private static final int FIRST_JUMP_STATE = 2;
86
87 private static final String THIS_NAME = CompilerConstants.THIS.symbolName();
88 private static final String RETURN_NAME = CompilerConstants.RETURN.symbolName();
89 // Used as the name of the formal parameter for passing the current value of :return symbol into a split fragment.
90 private static final String RETURN_PARAM_NAME = RETURN_NAME + "-in";
91
92 private final Deque<FunctionState> functionStates = new ArrayDeque<>();
93 private final Deque<SplitState> splitStates = new ArrayDeque<>();
94 private final Namespace namespace;
95
96 private boolean artificialBlock = false;
97
98 // -1 is program; we need to use negative ones
99 private int nextFunctionId = -2;
100
101 public SplitIntoFunctions(final Compiler compiler) {
102 super(new BlockLexicalContext() {
103 @Override
104 protected Block afterSetStatements(final Block block) {
105 for(Statement stmt: block.getStatements()) {
106 assert !(stmt instanceof SplitNode);
107 }
108 return block;
109 }
110 });
111 namespace = new Namespace(compiler.getScriptEnvironment().getNamespace());
112 }
113
114 @Override
115 public boolean enterFunctionNode(final FunctionNode functionNode) {
116 functionStates.push(new FunctionState(functionNode));
117 return true;
118 }
119
120 @Override
121 public Node leaveFunctionNode(final FunctionNode functionNode) {
122 functionStates.pop();
123 return functionNode;
124 }
125
126 @Override
127 protected Node leaveDefault(final Node node) {
128 if (node instanceof Statement) {
129 appendStatement((Statement)node);
130 }
131 return node;
132 }
133
134 @Override
135 public boolean enterSplitNode(final SplitNode splitNode) {
136 getCurrentFunctionState().splitDepth++;
137 splitStates.push(new SplitState(splitNode));
138 return true;
139 }
140
141 @Override
142 public Node leaveSplitNode(final SplitNode splitNode) {
143 // Replace the split node with an anonymous function expression call.
144
145 final FunctionState fnState = getCurrentFunctionState();
146
147 final String name = splitNode.getName();
148 Block body = splitNode.getBody();
149 final int firstLineNumber = body.getFirstStatementLineNumber();
150 final long token = body.getToken();
151 final int finish = body.getFinish();
152
153 final FunctionNode originalFn = fnState.fn;
154 assert originalFn == lc.getCurrentFunction();
155 final boolean isProgram = originalFn.isProgram();
156
157 // Change SplitNode({...}) into "function () { ... }", or "function (:return-in) () { ... }" (for program)
158 final long newFnToken = Token.toDesc(TokenType.FUNCTION, nextFunctionId--, 0);
159 final FunctionNode fn = new FunctionNode(
160 originalFn.getSource(),
161 body.getFirstStatementLineNumber(),
162 newFnToken,
163 finish,
164 NO_TOKEN,
165 namespace,
166 createIdent(name),
167 originalFn.getName() + "$" + name,
168 isProgram ? Collections.singletonList(createReturnParamIdent()) : Collections.<IdentNode>emptyList(),
169 FunctionNode.Kind.NORMAL,
170 // We only need IS_SPLIT conservatively, in case it contains any array units so that we force
171 // the :callee's existence, to force :scope to never be in a slot lower than 2. This is actually
172 // quite a horrible hack to do with CodeGenerator.fixScopeSlot not trampling other parameters
173 // and should go away once we no longer have array unit handling in codegen. Note however that
174 // we still use IS_SPLIT as the criteria in CompilationPhase.SERIALIZE_SPLIT_PHASE.
175 FunctionNode.IS_ANONYMOUS | FunctionNode.USES_ANCESTOR_SCOPE | FunctionNode.IS_SPLIT
176 )
177 .setBody(lc, body)
178 .setCompileUnit(lc, splitNode.getCompileUnit())
179 .copyCompilationState(lc, originalFn);
180
181 // Call the function:
182 // either "(function () { ... }).call(this)"
183 // or "(function (:return-in) { ... }).call(this, :return)"
184 // NOTE: Function.call() has optimized linking that basically does a pass-through to the function being invoked.
185 // NOTE: CompilationPhase.PROGRAM_POINT_PHASE happens after this, so these calls are subject to optimistic
186 // assumptions on their return value (when they return a value), as they should be.
187 final IdentNode thisIdent = createIdent(THIS_NAME);
188 final CallNode callNode = new CallNode(firstLineNumber, token, finish, new AccessNode(NO_TOKEN, NO_FINISH, fn, "call"),
189 isProgram ? Arrays.<Expression>asList(thisIdent, createReturnIdent())
190 : Collections.<Expression>singletonList(thisIdent),
191 false);
192
193 final SplitState splitState = splitStates.pop();
194 fnState.splitDepth--;
195
196 final Expression callWithReturn;
197 final boolean hasReturn = splitState.hasReturn;
198 if (hasReturn && fnState.splitDepth > 0) {
199 final SplitState parentSplit = splitStates.peek();
200 if (parentSplit != null) {
201 // Propagate hasReturn to parent split
202 parentSplit.hasReturn = true;
203 }
204 }
205 if (hasReturn || isProgram) {
206 // capture return value: ":return = (function () { ... })();"
207 callWithReturn = new BinaryNode(Token.recast(token, TokenType.ASSIGN), createReturnIdent(), callNode);
208 } else {
209 // no return value, just call : "(function () { ... })();"
210 callWithReturn = callNode;
211 }
212 appendStatement(new ExpressionStatement(firstLineNumber, token, finish, callWithReturn));
213
214 Statement splitStateHandler;
215
216 final List<JumpStatement> jumpStatements = splitState.jumpStatements;
217 final int jumpCount = jumpStatements.size();
218 // There are jumps (breaks or continues) that need to be propagated outside the split node. We need to
219 // set up a switch statement for them:
220 // switch(:scope.getScopeState()) { ... }
221 if (jumpCount > 0) {
222 final List<CaseNode> cases = new ArrayList<>(jumpCount + (hasReturn ? 1 : 0));
223 if (hasReturn) {
224 // If the split node also contained a return, we'll slip it as a case in the switch statement
225 addCase(cases, RETURN_STATE, createReturnFromSplit());
226 }
227 int i = FIRST_JUMP_STATE;
228 for (final JumpStatement jump: jumpStatements) {
229 addCase(cases, i++, enblockAndVisit(jump));
230 }
231 splitStateHandler = new SwitchNode(NO_LINE_NUMBER, token, finish, GetSplitState.INSTANCE, cases, null);
232 } else {
233 splitStateHandler = null;
234 }
235
236 // As the switch statement itself is breakable, an unlabelled break can't be in the switch statement,
237 // so we need to test for it separately.
238 if (splitState.hasBreak) {
239 // if(:scope.getScopeState() == Scope.BREAK) { break; }
240 splitStateHandler = makeIfStateEquals(firstLineNumber, token, finish, BREAK_STATE,
241 enblockAndVisit(new BreakNode(NO_LINE_NUMBER, token, finish, null)), splitStateHandler);
242 }
243
244 // Finally, if the split node had a return statement, but there were no external jumps, we didn't have
245 // the switch statement to handle the return, so we need a separate if for it.
246 if (hasReturn && jumpCount == 0) {
247 // if (:scope.getScopeState() == Scope.RETURN) { return :return; }
248 splitStateHandler = makeIfStateEquals(NO_LINE_NUMBER, token, finish, RETURN_STATE,
249 createReturnFromSplit(), splitStateHandler);
250 }
251
252 if (splitStateHandler != null) {
253 appendStatement(splitStateHandler);
254 }
255
256 return splitNode;
257 }
258
259 private static void addCase(final List<CaseNode> cases, final int i, final Block body) {
260 cases.add(new CaseNode(NO_TOKEN, NO_FINISH, intLiteral(i), body));
261 }
262
263 private static LiteralNode<Number> intLiteral(final int i) {
264 return LiteralNode.newInstance(NO_TOKEN, NO_FINISH, i);
265 }
266
267 private static Block createReturnFromSplit() {
268 return new Block(NO_TOKEN, NO_FINISH, createReturnReturn());
269 }
270
271 private static ReturnNode createReturnReturn() {
272 return new ReturnNode(NO_LINE_NUMBER, NO_TOKEN, NO_FINISH, createReturnIdent());
273 }
274
275 private static IdentNode createReturnIdent() {
276 return createIdent(RETURN_NAME);
277 }
278
279 private static IdentNode createReturnParamIdent() {
280 return createIdent(RETURN_PARAM_NAME);
281 }
282
283 private static IdentNode createIdent(final String name) {
284 return new IdentNode(NO_TOKEN, NO_FINISH, name);
285 }
286
287 private Block enblockAndVisit(final JumpStatement jump) {
288 artificialBlock = true;
289 final Block block = (Block)new Block(NO_TOKEN, NO_FINISH, jump).accept(this);
290 artificialBlock = false;
291 return block;
292 }
293
294 private static IfNode makeIfStateEquals(final int lineNumber, final long token, final int finish,
295 final int value, final Block pass, final Statement fail) {
296 return new IfNode(lineNumber, token, finish,
297 new BinaryNode(Token.recast(token, TokenType.EQ_STRICT),
298 GetSplitState.INSTANCE, intLiteral(value)),
299 pass,
300 fail == null ? null : new Block(NO_TOKEN, NO_FINISH, fail));
301 }
302
303 @Override
304 public boolean enterVarNode(final VarNode varNode) {
305 if (!inSplitNode()) {
306 return super.enterVarNode(varNode);
307 }
308 assert !varNode.isBlockScoped(); //TODO: we must handle these too, but we currently don't
309
310 final Expression init = varNode.getInit();
311 if (varNode.isAnonymousFunctionDeclaration()) {
312 // We ain't moving anonymous function declarations.
313 return super.enterVarNode(varNode);
314 }
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 }