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