1 /*
2 * Copyright (c) 2010, 2017, 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.ir;
27
28 import java.io.PrintWriter;
29 import java.util.ArrayList;
30 import java.util.Arrays;
31 import java.util.Collections;
32 import java.util.Comparator;
33 import java.util.LinkedHashMap;
34 import java.util.List;
35 import java.util.Map;
36 import jdk.nashorn.internal.codegen.Label;
37 import jdk.nashorn.internal.ir.annotations.Immutable;
38 import jdk.nashorn.internal.ir.visitor.NodeVisitor;
39
40 /**
41 * IR representation for a list of statements.
42 */
43 @Immutable
44 public class Block extends Node implements BreakableNode, Terminal, Flags<Block> {
45 private static final long serialVersionUID = 1L;
46
47 /** List of statements */
48 protected final List<Statement> statements;
49
50 /** Symbol table - keys must be returned in the order they were put in. */
51 protected final Map<String, Symbol> symbols;
52
53 /** Entry label. */
54 private final Label entryLabel;
55
56 /** Break label. */
57 private final Label breakLabel;
58
59 /** Does the block/function need a new scope? Is this synthetic? */
60 protected final int flags;
61
62 /**
63 * @see JoinPredecessor
64 */
65 private final LocalVariableConversion conversion;
66
67 /** Flag indicating that this block needs scope */
68 public static final int NEEDS_SCOPE = 1 << 0;
69
70 /**
71 * Is this block tagged as terminal based on its contents
72 * (usually the last statement)
73 */
74 public static final int IS_TERMINAL = 1 << 2;
75
76 /**
77 * Is this block the eager global scope - i.e. the original program. This isn't true for the
78 * outermost level of recompiles
79 */
80 public static final int IS_GLOBAL_SCOPE = 1 << 3;
81
82 /**
83 * Is this block a synthetic one introduced by Parser?
84 */
85 public static final int IS_SYNTHETIC = 1 << 4;
86
87 /**
88 * Is this the function body block? May not be the first, if parameter list contains expressions.
89 */
90 public static final int IS_BODY = 1 << 5;
91
92 /**
93 * Is this the parameter initialization block? If present, must be the first block, immediately wrapping the function body block.
94 */
95 public static final int IS_PARAMETER_BLOCK = 1 << 6;
96
97 /**
98 * Marks the variable declaration block for case clauses of a switch statement.
99 */
100 public static final int IS_SWITCH_BLOCK = 1 << 7;
101
102 /**
103 * Is this block tagged as breakable based on its contents
104 * (block having labelled break statement)
105 */
106 public static final int IS_BREAKABLE = 1 << 8;
107
108 /**
109 * Constructor
110 *
111 * @param token The first token of the block
112 * @param finish The index of the last character
113 * @param flags The flags of the block
114 * @param statements All statements in the block
115 */
116 public Block(final long token, final int finish, final int flags, final Statement... statements) {
117 super(token, finish);
118
119 this.statements = Arrays.asList(statements);
120 this.symbols = new LinkedHashMap<>();
121 this.entryLabel = new Label("block_entry");
122 this.breakLabel = new Label("block_break");
123 final int len = statements.length;
124 final int terminalFlags = len > 0 && statements[len - 1].hasTerminalFlags() ? IS_TERMINAL : 0;
125 this.flags = terminalFlags | flags;
126 this.conversion = null;
127 }
128
129 /**
130 * Constructs a new block
131 *
132 * @param token The first token of the block
133 * @param finish The index of the last character
134 * @param statements All statements in the block
135 */
136 public Block(final long token, final int finish, final Statement...statements){
137 this(token, finish, IS_SYNTHETIC, statements);
138 }
139
140 /**
141 * Constructs a new block
142 *
143 * @param token The first token of the block
144 * @param finish The index of the last character
145 * @param statements All statements in the block
146 */
147 public Block(final long token, final int finish, final List<Statement> statements){
148 this(token, finish, IS_SYNTHETIC, statements);
149 }
150
151 /**
152 * Constructor
153 *
154 * @param token The first token of the block
155 * @param finish The index of the last character
156 * @param flags The flags of the block
157 * @param statements All statements in the block
158 */
159 public Block(final long token, final int finish, final int flags, final List<Statement> statements) {
160 this(token, finish, flags, statements.toArray(new Statement[0]));
161 }
162
163 private Block(final Block block, final int finish, final List<Statement> statements, final int flags, final Map<String, Symbol> symbols, final LocalVariableConversion conversion) {
164 super(block, finish);
165 this.statements = statements;
166 this.flags = flags;
167 this.symbols = new LinkedHashMap<>(symbols); //todo - symbols have no dependencies on any IR node and can as far as we understand it be shallow copied now
168 this.entryLabel = new Label(block.entryLabel);
169 this.breakLabel = new Label(block.breakLabel);
170 this.conversion = conversion;
171 }
172
173 /**
174 * Is this block the outermost eager global scope - i.e. the primordial program?
175 * Used for global anchor point for scope depth computation for recompilation code
176 * @return true if outermost eager global scope
177 */
178 public boolean isGlobalScope() {
179 return getFlag(IS_GLOBAL_SCOPE);
180 }
181
182 /**
183 * Returns true if this block defines any symbols.
184 * @return true if this block defines any symbols.
185 */
186 public boolean hasSymbols() {
187 return !symbols.isEmpty();
188 }
189
190 /**
191 * Replaces symbols defined in this block with different symbols. Used to ensure symbol tables are
192 * immutable upon construction and have copy-on-write semantics. Note that this method only replaces the
193 * symbols in the symbol table, it does not act on any contained AST nodes that might reference the symbols.
194 * Those should be updated separately as this method is meant to be used as part of such an update pass.
195 * @param lc the current lexical context
196 * @param replacements the map of symbol replacements
197 * @return a new block with replaced symbols, or this block if none of the replacements modified the symbol
198 * table.
199 */
200 public Block replaceSymbols(final LexicalContext lc, final Map<Symbol, Symbol> replacements) {
201 if (symbols.isEmpty()) {
202 return this;
203 }
204 final LinkedHashMap<String, Symbol> newSymbols = new LinkedHashMap<>(symbols);
205 for (final Map.Entry<String, Symbol> entry: newSymbols.entrySet()) {
206 final Symbol newSymbol = replacements.get(entry.getValue());
207 assert newSymbol != null : "Missing replacement for " + entry.getKey();
208 entry.setValue(newSymbol);
209 }
210 return Node.replaceInLexicalContext(lc, this, new Block(this, finish, statements, flags, newSymbols, conversion));
211 }
212
213 /**
214 * Returns a copy of this block with a shallow copy of the symbol table.
215 * @return a copy of this block with a shallow copy of the symbol table.
216 */
217 public Block copyWithNewSymbols() {
218 return new Block(this, finish, statements, flags, new LinkedHashMap<>(symbols), conversion);
219 }
220
221 @Override
222 public Node ensureUniqueLabels(final LexicalContext lc) {
223 return Node.replaceInLexicalContext(lc, this, new Block(this, finish, statements, flags, symbols, conversion));
224 }
225
226 /**
227 * Assist in IR navigation.
228 *
229 * @param visitor IR navigating visitor.
230 * @return new or same node
231 */
232 @Override
233 public Node accept(final LexicalContext lc, final NodeVisitor<? extends LexicalContext> visitor) {
234 if (visitor.enterBlock(this)) {
235 return visitor.leaveBlock(setStatements(lc, Node.accept(visitor, statements)));
236 }
237
238 return this;
239 }
240
241 /**
242 * Get a copy of the list for all the symbols defined in this block
243 * @return symbol iterator
244 */
245 public List<Symbol> getSymbols() {
246 return symbols.isEmpty() ? Collections.emptyList() : Collections.unmodifiableList(new ArrayList<>(symbols.values()));
247 }
248
249 /**
250 * Retrieves an existing symbol defined in the current block.
251 * @param name the name of the symbol
252 * @return an existing symbol with the specified name defined in the current block, or null if this block doesn't
253 * define a symbol with this name.T
254 */
255 public Symbol getExistingSymbol(final String name) {
256 return symbols.get(name);
257 }
258
259 /**
260 * Test if this block represents a <code>catch</code> block in a <code>try</code> statement.
261 * This is used by the Splitter as catch blocks are not be subject to splitting.
262 *
263 * @return true if this block represents a catch block in a try statement.
264 */
265 public boolean isCatchBlock() {
266 return statements.size() == 1 && statements.get(0) instanceof CatchNode;
267 }
268
269 @Override
270 public void toString(final StringBuilder sb, final boolean printType) {
271 for (final Node statement : statements) {
272 statement.toString(sb, printType);
273 sb.append(';');
274 }
275 }
276
277 /**
278 * Print symbols in block in alphabetical order, sorted on name
279 * Used for debugging, see the --print-symbols flag
280 *
281 * @param stream print writer to output symbols to
282 *
283 * @return true if symbols were found
284 */
285 public boolean printSymbols(final PrintWriter stream) {
286 final List<Symbol> values = new ArrayList<>(symbols.values());
287
288 Collections.sort(values, new Comparator<Symbol>() {
289 @Override
290 public int compare(final Symbol s0, final Symbol s1) {
291 return s0.getName().compareTo(s1.getName());
292 }
293 });
294
295 for (final Symbol symbol : values) {
296 symbol.print(stream);
297 }
298
299 return !values.isEmpty();
300 }
301
302 /**
303 * Tag block as terminal or non terminal
304 * @param lc lexical context
305 * @param isTerminal is block terminal
306 * @return same block, or new if flag changed
307 */
308 public Block setIsTerminal(final LexicalContext lc, final boolean isTerminal) {
309 return isTerminal ? setFlag(lc, IS_TERMINAL) : clearFlag(lc, IS_TERMINAL);
310 }
311
312 @Override
313 public int getFlags() {
314 return flags;
315 }
316
317 /**
318 * Is this a terminal block, i.e. does it end control flow like ending with a throw or return?
319 *
320 * @return true if this node statement is terminal
321 */
322 @Override
323 public boolean isTerminal() {
324 return getFlag(IS_TERMINAL) && !getFlag(IS_BREAKABLE);
325 }
326
327 /**
328 * Get the entry label for this block
329 * @return the entry label
330 */
331 public Label getEntryLabel() {
332 return entryLabel;
333 }
334
335 @Override
336 public Label getBreakLabel() {
337 return breakLabel;
338 }
339
340 @Override
341 public Block setLocalVariableConversion(final LexicalContext lc, final LocalVariableConversion conversion) {
342 if(this.conversion == conversion) {
343 return this;
344 }
345 return Node.replaceInLexicalContext(lc, this, new Block(this, finish, statements, flags, symbols, conversion));
346 }
347
348 @Override
349 public LocalVariableConversion getLocalVariableConversion() {
350 return conversion;
351 }
352
353 /**
354 * Get the list of statements in this block
355 *
356 * @return a list of statements
357 */
358 public List<Statement> getStatements() {
359 return Collections.unmodifiableList(statements);
360 }
361
362 /**
363 * Returns the number of statements in the block.
364 * @return the number of statements in the block.
365 */
366 public int getStatementCount() {
367 return statements.size();
368 }
369
370 /**
371 * Returns the line number of the first statement in the block.
372 * @return the line number of the first statement in the block, or -1 if the block has no statements.
373 */
374 public int getFirstStatementLineNumber() {
375 if(statements == null || statements.isEmpty()) {
376 return -1;
377 }
378 return statements.get(0).getLineNumber();
379 }
380
381 /**
382 * Returns the last statement in the block.
383 * @return the last statement in the block, or null if the block has no statements.
384 */
385 public Statement getLastStatement() {
386 return statements.isEmpty() ? null : statements.get(statements.size() - 1);
387 }
388
389 /**
390 * Reset the statement list for this block
391 *
392 * @param lc lexical context
393 * @param statements new statement list
394 * @return new block if statements changed, identity of statements == block.statements
395 */
396 public Block setStatements(final LexicalContext lc, final List<Statement> statements) {
397 if (this.statements == statements) {
398 return this;
399 }
400 int lastFinish = 0;
401 if (!statements.isEmpty()) {
402 lastFinish = statements.get(statements.size() - 1).getFinish();
403 }
404 return Node.replaceInLexicalContext(lc, this, new Block(this, Math.max(finish, lastFinish), statements, flags, symbols, conversion));
405 }
406
407 /**
408 * Add or overwrite an existing symbol in the block
409 *
410 * @param symbol symbol
411 */
412 public void putSymbol(final Symbol symbol) {
413 symbols.put(symbol.getName(), symbol);
414 }
415
416 /**
417 * Check whether scope is necessary for this Block
418 *
419 * @return true if this function needs a scope
420 */
421 public boolean needsScope() {
422 return (flags & NEEDS_SCOPE) == NEEDS_SCOPE;
423 }
424
425 /**
426 * Check whether this block is synthetic or not.
427 *
428 * @return true if this is a synthetic block
429 */
430 public boolean isSynthetic() {
431 return (flags & IS_SYNTHETIC) == IS_SYNTHETIC;
432 }
433
434 @Override
435 public Block setFlags(final LexicalContext lc, final int flags) {
436 if (this.flags == flags) {
437 return this;
438 }
439 return Node.replaceInLexicalContext(lc, this, new Block(this, finish, statements, flags, symbols, conversion));
440 }
441
442 @Override
443 public Block clearFlag(final LexicalContext lc, final int flag) {
444 return setFlags(lc, flags & ~flag);
445 }
446
447 @Override
448 public Block setFlag(final LexicalContext lc, final int flag) {
449 return setFlags(lc, flags | flag);
450 }
451
452 @Override
453 public boolean getFlag(final int flag) {
454 return (flags & flag) == flag;
455 }
456
457 /**
458 * Set the needs scope flag.
459 * @param lc lexicalContext
460 * @return new block if state changed, otherwise this
461 */
462 public Block setNeedsScope(final LexicalContext lc) {
463 if (needsScope()) {
464 return this;
465 }
466
467 return Node.replaceInLexicalContext(lc, this, new Block(this, finish, statements, flags | NEEDS_SCOPE, symbols, conversion));
468 }
469
470 /**
471 * Computationally determine the next slot for this block,
472 * indexed from 0. Use this as a relative base when computing
473 * frames
474 * @return next slot
475 */
476 public int nextSlot() {
477 int next = 0;
478 for (final Symbol symbol : getSymbols()) {
479 if (symbol.hasSlot()) {
480 next += symbol.slotCount();
481 }
482 }
483 return next;
484 }
485
486 /**
487 * Determine whether this block needs to provide its scope object creator for use by its child nodes.
488 * This is only necessary for synthetic parent blocks of for-in loops with lexical declarations.
489 *
490 * @see ForNode#needsScopeCreator()
491 * @return true if child nodes need access to this block's scope creator
492 */
493 public boolean providesScopeCreator() {
494 return needsScope() && isSynthetic()
495 && (getLastStatement() instanceof ForNode)
496 && ((ForNode) getLastStatement()).needsScopeCreator();
497 }
498
499 @Override
500 public boolean isBreakableWithoutLabel() {
501 return false;
502 }
503
504 @Override
505 public List<Label> getLabels() {
506 return Collections.unmodifiableList(Arrays.asList(entryLabel, breakLabel));
507 }
508
509 @Override
510 public Node accept(final NodeVisitor<? extends LexicalContext> visitor) {
511 return Acceptor.accept(this, visitor);
512 }
513
514 /**
515 * Checks if this is a function body.
516 *
517 * @return true if the function body flag is set
518 */
519 public boolean isFunctionBody() {
520 return getFlag(IS_BODY);
521 }
522
523 /**
524 * Checks if this is a parameter block.
525 *
526 * @return true if the parameter block flag is set
527 */
528 public boolean isParameterBlock() {
529 return getFlag(IS_PARAMETER_BLOCK);
530 }
531
532 /**
533 * Checks whether this is a switch block.
534 *
535 * @return true if this is a switch block
536 */
537 public boolean isSwitchBlock() {
538 return getFlag(IS_SWITCH_BLOCK);
539 }
540 }