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