1 /* 2 * Copyright (c) 2010, 2013, 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 package jdk.nashorn.internal.ir; 26 27 import java.io.File; 28 import java.util.Iterator; 29 import java.util.NoSuchElementException; 30 import jdk.nashorn.internal.runtime.Debug; 31 import jdk.nashorn.internal.runtime.Source; 32 33 /** 34 * A class that tracks the current lexical context of node visitation as a stack of {@link Block} nodes. Has special 35 * methods to retrieve useful subsets of the context. 36 * 37 * This is implemented with a primitive array and a stack pointer, because it really makes a difference 38 * performance wise. None of the collection classes were optimal 39 */ 40 public class LexicalContext { 41 private LexicalContextNode[] stack; 42 43 private int[] flags; 44 private int sp; 45 46 /** 47 * Creates a new empty lexical context. 48 */ 49 public LexicalContext() { 50 stack = new LexicalContextNode[16]; 51 flags = new int[16]; 52 } 53 54 /** 55 * Set the flags for a lexical context node on the stack. Does not 56 * replace the flags, but rather adds to them. 57 * 58 * @param node node 59 * @param flag new flag to set 60 */ 61 public void setFlag(final LexicalContextNode node, final int flag) { 62 if (flag != 0) { 63 // Use setBlockNeedsScope() instead 64 assert !(flag == Block.NEEDS_SCOPE && node instanceof Block); 65 66 for (int i = sp - 1; i >= 0; i--) { 67 if (stack[i] == node) { 68 flags[i] |= flag; 69 return; 70 } 71 } 72 } 73 assert false; 74 } 75 76 /** 77 * Marks the block as one that creates a scope. Note that this method must 78 * be used instead of {@link #setFlag(LexicalContextNode, int)} with 79 * {@link Block#NEEDS_SCOPE} because it atomically also sets the 80 * {@link FunctionNode#HAS_SCOPE_BLOCK} flag on the block's containing 81 * function. 82 * @param block the block that needs to be marked as creating a scope. 83 */ 84 public void setBlockNeedsScope(final Block block) { 85 for (int i = sp - 1; i >= 0; i--) { 86 if (stack[i] == block) { 87 flags[i] |= Block.NEEDS_SCOPE; 88 for(int j = i - 1; j >=0; j --) { 89 if(stack[j] instanceof FunctionNode) { 90 flags[j] |= FunctionNode.HAS_SCOPE_BLOCK; 91 return; 92 } 93 } 94 } 95 } 96 assert false; 97 } 98 99 /** 100 * Get the flags for a lexical context node on the stack 101 * @param node node 102 * @return the flags for the node 103 */ 104 public int getFlags(final LexicalContextNode node) { 105 for (int i = sp - 1; i >= 0; i--) { 106 if (stack[i] == node) { 107 return flags[i]; 108 } 109 } 110 throw new AssertionError("flag node not on context stack"); 111 } 112 113 /** 114 * Get the function body of a function node on the lexical context 115 * stack. This will trigger an assertion if node isn't present 116 * @param functionNode function node 117 * @return body of function node 118 */ 119 public Block getFunctionBody(final FunctionNode functionNode) { 120 for (int i = sp - 1; i >= 0 ; i--) { 121 if (stack[i] == functionNode) { 122 return (Block)stack[i + 1]; 123 } 124 } 125 throw new AssertionError(functionNode.getName() + " not on context stack"); 126 } 127 128 /** 129 * Return all nodes in the LexicalContext 130 * @return all nodes 131 */ 132 public Iterator<LexicalContextNode> getAllNodes() { 133 return new NodeIterator<>(LexicalContextNode.class); 134 } 135 136 /** 137 * Returns the outermost function in this context. It is either the program, or a lazily compiled function. 138 * @return the outermost function in this context. 139 */ 140 public FunctionNode getOutermostFunction() { 141 return (FunctionNode)stack[0]; 142 } 143 144 /** 145 * Pushes a new block on top of the context, making it the innermost open block. 146 * @param node the new node 147 * @return the node that was pushed 148 */ 149 public <T extends LexicalContextNode> T push(final T node) { 150 assert !contains(node); 151 if (sp == stack.length) { 152 final LexicalContextNode[] newStack = new LexicalContextNode[sp * 2]; 153 System.arraycopy(stack, 0, newStack, 0, sp); 154 stack = newStack; 155 156 final int[] newFlags = new int[sp * 2]; 157 System.arraycopy(flags, 0, newFlags, 0, sp); 158 flags = newFlags; 159 160 } 161 stack[sp] = node; 162 flags[sp] = 0; 163 164 sp++; 165 166 return node; 167 } 168 169 /** 170 * Is the context empty? 171 * @return true if empty 172 */ 173 public boolean isEmpty() { 174 return sp == 0; 175 } 176 177 /** 178 * The depth of the lexical context 179 * @return depth 180 */ 181 public int size() { 182 return sp; 183 } 184 185 /** 186 * Pops the innermost block off the context and all nodes that has been contributed 187 * since it was put there 188 * 189 * @param node the node expected to be popped, used to detect unbalanced pushes/pops 190 * @return the node that was popped 191 */ 192 @SuppressWarnings("unchecked") 193 public <T extends Node> T pop(final T node) { 194 --sp; 195 final LexicalContextNode popped = stack[sp]; 196 stack[sp] = null; 197 if (popped instanceof Flags) { 198 return (T)((Flags<?>)popped).setFlag(this, flags[sp]); 199 } 200 201 return (T)popped; 202 } 203 204 /** 205 * Explicitly apply flags to the topmost element on the stack. This is only valid to use from a 206 * {@code NodeVisitor.leaveXxx()} method and only on the node being exited at the time. It is not mandatory to use, 207 * as {@link #pop(Node)} will apply the flags automatically, but this method can be used to apply them 208 * during the {@code leaveXxx()} method in case its logic depends on the value of the flags. 209 * @param node the node to apply the flags to. Must be the topmost node on the stack. 210 * @return the passed in node, or a modified node (if any flags were modified) 211 */ 212 public <T extends LexicalContextNode & Flags<T>> T applyTopFlags(final T node) { 213 assert node == peek(); 214 return node.setFlag(this, flags[sp - 1]); 215 } 216 217 /** 218 * Return the top element in the context 219 * @return the node that was pushed last 220 */ 221 public LexicalContextNode peek() { 222 return stack[sp - 1]; 223 } 224 225 /** 226 * Check if a node is in the lexical context 227 * @param node node to check for 228 * @return true if in the context 229 */ 230 public boolean contains(final LexicalContextNode node) { 231 for (int i = 0; i < sp; i++) { 232 if (stack[i] == node) { 233 return true; 234 } 235 } 236 return false; 237 } 238 239 /** 240 * Replace a node on the lexical context with a new one. Normally 241 * you should try to engineer IR traversals so this isn't needed 242 * 243 * @param oldNode old node 244 * @param newNode new node 245 * @return the new node 246 */ 247 public LexicalContextNode replace(final LexicalContextNode oldNode, final LexicalContextNode newNode) { 248 for (int i = sp - 1; i >= 0; i--) { 249 if (stack[i] == oldNode) { 250 assert i == sp - 1 : "violation of contract - we always expect to find the replacement node on top of the lexical context stack: " + newNode + " has " + stack[i + 1].getClass() + " above it"; 251 stack[i] = newNode; 252 break; 253 } 254 } 255 return newNode; 256 } 257 258 /** 259 * Returns an iterator over all blocks in the context, with the top block (innermost lexical context) first. 260 * @return an iterator over all blocks in the context. 261 */ 262 public Iterator<Block> getBlocks() { 263 return new NodeIterator<>(Block.class); 264 } 265 266 /** 267 * Returns an iterator over all functions in the context, with the top (innermost open) function first. 268 * @return an iterator over all functions in the context. 269 */ 270 public Iterator<FunctionNode> getFunctions() { 271 return new NodeIterator<>(FunctionNode.class); 272 } 273 274 /** 275 * Get the parent block for the current lexical context block 276 * @return parent block 277 */ 278 public Block getParentBlock() { 279 final Iterator<Block> iter = new NodeIterator<>(Block.class, getCurrentFunction()); 280 iter.next(); 281 return iter.hasNext() ? iter.next() : null; 282 } 283 284 /** 285 * Gets the label node of the current block. 286 * @return the label node of the current block, if it is labeled. Otherwise returns null. 287 */ 288 public LabelNode getCurrentBlockLabelNode() { 289 assert stack[sp - 1] instanceof Block; 290 if(sp < 2) { 291 return null; 292 } 293 final LexicalContextNode parent = stack[sp - 2]; 294 return parent instanceof LabelNode ? (LabelNode)parent : null; 295 } 296 297 298 /* 299 public FunctionNode getProgram() { 300 final Iterator<FunctionNode> iter = getFunctions(); 301 FunctionNode last = null; 302 while (iter.hasNext()) { 303 last = iter.next(); 304 } 305 assert last != null; 306 return last; 307 }*/ 308 309 /** 310 * Returns an iterator over all ancestors block of the given block, with its parent block first. 311 * @param block the block whose ancestors are returned 312 * @return an iterator over all ancestors block of the given block. 313 */ 314 public Iterator<Block> getAncestorBlocks(final Block block) { 315 final Iterator<Block> iter = getBlocks(); 316 while (iter.hasNext()) { 317 final Block b = iter.next(); 318 if (block == b) { 319 return iter; 320 } 321 } 322 throw new AssertionError("Block is not on the current lexical context stack"); 323 } 324 325 /** 326 * Returns an iterator over a block and all its ancestors blocks, with the block first. 327 * @param block the block that is the starting point of the iteration. 328 * @return an iterator over a block and all its ancestors. 329 */ 330 public Iterator<Block> getBlocks(final Block block) { 331 final Iterator<Block> iter = getAncestorBlocks(block); 332 return new Iterator<Block>() { 333 boolean blockReturned = false; 334 @Override 335 public boolean hasNext() { 336 return iter.hasNext() || !blockReturned; 337 } 338 @Override 339 public Block next() { 340 if (blockReturned) { 341 return iter.next(); 342 } 343 blockReturned = true; 344 return block; 345 } 346 @Override 347 public void remove() { 348 throw new UnsupportedOperationException(); 349 } 350 }; 351 } 352 353 /** 354 * Get the function for this block. 355 * @param block block for which to get function 356 * @return function for block 357 */ 358 public FunctionNode getFunction(final Block block) { 359 final Iterator<LexicalContextNode> iter = new NodeIterator<>(LexicalContextNode.class); 360 while (iter.hasNext()) { 361 final LexicalContextNode next = iter.next(); 362 if (next == block) { 363 while (iter.hasNext()) { 364 final LexicalContextNode next2 = iter.next(); 365 if (next2 instanceof FunctionNode) { 366 return (FunctionNode)next2; 367 } 368 } 369 } 370 } 371 assert false; 372 return null; 373 } 374 375 /** 376 * Returns the innermost block in the context. 377 * @return the innermost block in the context. 378 */ 379 public Block getCurrentBlock() { 380 return getBlocks().next(); 381 } 382 383 /** 384 * Returns the innermost function in the context. 385 * @return the innermost function in the context. 386 */ 387 public FunctionNode getCurrentFunction() { 388 for (int i = sp - 1; i >= 0; i--) { 389 if (stack[i] instanceof FunctionNode) { 390 return (FunctionNode) stack[i]; 391 } 392 } 393 return null; 394 } 395 396 /** 397 * Get the block in which a symbol is defined 398 * @param symbol symbol 399 * @return block in which the symbol is defined, assert if no such block in context 400 */ 401 public Block getDefiningBlock(final Symbol symbol) { 402 final String name = symbol.getName(); 403 for (final Iterator<Block> it = getBlocks(); it.hasNext();) { 404 final Block next = it.next(); 405 if (next.getExistingSymbol(name) == symbol) { 406 return next; 407 } 408 } 409 throw new AssertionError("Couldn't find symbol " + name + " in the context"); 410 } 411 412 /** 413 * Get the function in which a symbol is defined 414 * @param symbol symbol 415 * @return function node in which this symbol is defined, assert if no such symbol exists in context 416 */ 417 public FunctionNode getDefiningFunction(final Symbol symbol) { 418 final String name = symbol.getName(); 419 for (final Iterator<LexicalContextNode> iter = new NodeIterator<>(LexicalContextNode.class); iter.hasNext();) { 420 final LexicalContextNode next = iter.next(); 421 if (next instanceof Block && ((Block)next).getExistingSymbol(name) == symbol) { 422 while (iter.hasNext()) { 423 final LexicalContextNode next2 = iter.next(); 424 if (next2 instanceof FunctionNode) { 425 return (FunctionNode)next2; 426 } 427 } 428 throw new AssertionError("Defining block for symbol " + name + " has no function in the context"); 429 } 430 } 431 throw new AssertionError("Couldn't find symbol " + name + " in the context"); 432 } 433 434 /** 435 * Is the topmost lexical context element a function body? 436 * @return true if function body 437 */ 438 public boolean isFunctionBody() { 439 return getParentBlock() == null; 440 } 441 442 /** 443 * Is the topmost lexical context element body of a SplitNode? 444 * @return true if it's the body of a split node. 445 */ 446 public boolean isSplitBody() { 447 return sp >= 2 && stack[sp - 1] instanceof Block && stack[sp - 2] instanceof SplitNode; 448 } 449 450 /** 451 * Get the parent function for a function in the lexical context 452 * @param functionNode function for which to get parent 453 * @return parent function of functionNode or null if none (e.g. if functionNode is the program) 454 */ 455 public FunctionNode getParentFunction(final FunctionNode functionNode) { 456 final Iterator<FunctionNode> iter = new NodeIterator<>(FunctionNode.class); 457 while (iter.hasNext()) { 458 final FunctionNode next = iter.next(); 459 if (next == functionNode) { 460 return iter.hasNext() ? iter.next() : null; 461 } 462 } 463 assert false; 464 return null; 465 } 466 467 /** 468 * Count the number of scopes until a given node. Note that this method is solely used to figure out the number of 469 * scopes that need to be explicitly popped in order to perform a break or continue jump within the current bytecode 470 * method. For this reason, the method returns 0 if it encounters a {@code SplitNode} between the current location 471 * and the break/continue target. 472 * @param until node to stop counting at. Must be within the current function 473 * @return number of with scopes encountered in the context 474 */ 475 public int getScopeNestingLevelTo(final LexicalContextNode until) { 476 assert until != null; 477 //count the number of with nodes until "until" is hit 478 int n = 0; 479 for (final Iterator<LexicalContextNode> iter = getAllNodes(); iter.hasNext();) { 480 final LexicalContextNode node = iter.next(); 481 if (node == until) { 482 break; 483 } 484 assert !(node instanceof FunctionNode); // Can't go outside current function 485 if (node instanceof WithNode || node instanceof Block && ((Block)node).needsScope()) { 486 n++; 487 } 488 } 489 return n; 490 } 491 492 private BreakableNode getBreakable() { 493 for (final NodeIterator<BreakableNode> iter = new NodeIterator<>(BreakableNode.class, getCurrentFunction()); iter.hasNext(); ) { 494 final BreakableNode next = iter.next(); 495 if (next.isBreakableWithoutLabel()) { 496 return next; 497 } 498 } 499 return null; 500 } 501 502 /** 503 * Check whether the lexical context is currently inside a loop 504 * @return true if inside a loop 505 */ 506 public boolean inLoop() { 507 return getCurrentLoop() != null; 508 } 509 510 /** 511 * Returns the loop header of the current loop, or null if not inside a loop 512 * @return loop header 513 */ 514 public LoopNode getCurrentLoop() { 515 final Iterator<LoopNode> iter = new NodeIterator<>(LoopNode.class, getCurrentFunction()); 516 return iter.hasNext() ? iter.next() : null; 517 } 518 519 /** 520 * Find the breakable node corresponding to this label. 521 * @param labelName name of the label to search for. If null, the closest breakable node will be returned 522 * unconditionally, e.g. a while loop with no label 523 * @return closest breakable node 524 */ 525 public BreakableNode getBreakable(final String labelName) { 526 if (labelName != null) { 527 final LabelNode foundLabel = findLabel(labelName); 528 if (foundLabel != null) { 529 // iterate to the nearest breakable to the foundLabel 530 BreakableNode breakable = null; 531 for (final NodeIterator<BreakableNode> iter = new NodeIterator<>(BreakableNode.class, foundLabel); iter.hasNext(); ) { 532 breakable = iter.next(); 533 } 534 return breakable; 535 } 536 return null; 537 } 538 return getBreakable(); 539 } 540 541 private LoopNode getContinueTo() { 542 return getCurrentLoop(); 543 } 544 545 /** 546 * Find the continue target node corresponding to this label. 547 * @param labelName label name to search for. If null the closest loop node will be returned unconditionally, e.g. a 548 * while loop with no label 549 * @return closest continue target node 550 */ 551 public LoopNode getContinueTo(final String labelName) { 552 if (labelName != null) { 553 final LabelNode foundLabel = findLabel(labelName); 554 if (foundLabel != null) { 555 // iterate to the nearest loop to the foundLabel 556 LoopNode loop = null; 557 for (final NodeIterator<LoopNode> iter = new NodeIterator<>(LoopNode.class, foundLabel); iter.hasNext(); ) { 558 loop = iter.next(); 559 } 560 return loop; 561 } 562 return null; 563 } 564 return getContinueTo(); 565 } 566 567 /** 568 * Find the inlined finally block node corresponding to this label. 569 * @param labelName label name to search for. Must not be null. 570 * @return closest inlined finally block with the given label 571 */ 572 public Block getInlinedFinally(final String labelName) { 573 for (final NodeIterator<TryNode> iter = new NodeIterator<>(TryNode.class); iter.hasNext(); ) { 574 final Block inlinedFinally = iter.next().getInlinedFinally(labelName); 575 if (inlinedFinally != null) { 576 return inlinedFinally; 577 } 578 } 579 return null; 580 } 581 582 /** 583 * Find the try node for an inlined finally block corresponding to this label. 584 * @param labelName label name to search for. Must not be null. 585 * @return the try node to which the labelled inlined finally block belongs. 586 */ 587 public TryNode getTryNodeForInlinedFinally(final String labelName) { 588 for (final NodeIterator<TryNode> iter = new NodeIterator<>(TryNode.class); iter.hasNext(); ) { 589 final TryNode tryNode = iter.next(); 590 if (tryNode.getInlinedFinally(labelName) != null) { 591 return tryNode; 592 } 593 } 594 return null; 595 } 596 597 /** 598 * Check the lexical context for a given label node by name 599 * @param name name of the label 600 * @return LabelNode if found, null otherwise 601 */ 602 public LabelNode findLabel(final String name) { 603 for (final Iterator<LabelNode> iter = new NodeIterator<>(LabelNode.class, getCurrentFunction()); iter.hasNext(); ) { 604 final LabelNode next = iter.next(); 605 if (next.getLabelName().equals(name)) { 606 return next; 607 } 608 } 609 return null; 610 } 611 612 /** 613 * Checks whether a given target is a jump destination that lies outside a given split node 614 * @param splitNode the split node 615 * @param target the target node 616 * @return true if target resides outside the split node 617 */ 618 public boolean isExternalTarget(final SplitNode splitNode, final BreakableNode target) { 619 for (int i = sp; i-- > 0;) { 620 final LexicalContextNode next = stack[i]; 621 if (next == splitNode) { 622 return true; 623 } else if (next == target) { 624 return false; 625 } else if (next instanceof TryNode) { 626 for(final Block inlinedFinally: ((TryNode)next).getInlinedFinallies()) { 627 if (TryNode.getLabelledInlinedFinallyBlock(inlinedFinally) == target) { 628 return false; 629 } 630 } 631 } 632 } 633 throw new AssertionError(target + " was expected in lexical context " + LexicalContext.this + " but wasn't"); 634 } 635 636 /** 637 * Checks whether the current context is inside a switch statement without explicit blocks (curly braces). 638 * @return true if in unprotected switch statement 639 */ 640 public boolean inUnprotectedSwitchContext() { 641 for (int i = sp; i > 0; i--) { 642 final LexicalContextNode next = stack[i]; 643 if (next instanceof Block) { 644 return stack[i - 1] instanceof SwitchNode; 645 } 646 } 647 return false; 648 } 649 650 @Override 651 public String toString() { 652 final StringBuffer sb = new StringBuffer(); 653 sb.append("[ "); 654 for (int i = 0; i < sp; i++) { 655 final Object node = stack[i]; 656 sb.append(node.getClass().getSimpleName()); 657 sb.append('@'); 658 sb.append(Debug.id(node)); 659 sb.append(':'); 660 if (node instanceof FunctionNode) { 661 final FunctionNode fn = (FunctionNode)node; 662 final Source source = fn.getSource(); 663 String src = source.toString(); 664 if (src.contains(File.pathSeparator)) { 665 src = src.substring(src.lastIndexOf(File.pathSeparator)); 666 } 667 src += ' '; 668 src += fn.getLineNumber(); 669 sb.append(src); 670 } 671 sb.append(' '); 672 } 673 sb.append(" ==> ]"); 674 return sb.toString(); 675 } 676 677 private class NodeIterator <T extends LexicalContextNode> implements Iterator<T> { 678 private int index; 679 private T next; 680 private final Class<T> clazz; 681 private LexicalContextNode until; 682 683 NodeIterator(final Class<T> clazz) { 684 this(clazz, null); 685 } 686 687 NodeIterator(final Class<T> clazz, final LexicalContextNode until) { 688 this.index = sp - 1; 689 this.clazz = clazz; 690 this.until = until; 691 this.next = findNext(); 692 } 693 694 @Override 695 public boolean hasNext() { 696 return next != null; 697 } 698 699 @Override 700 public T next() { 701 if (next == null) { 702 throw new NoSuchElementException(); 703 } 704 final T lnext = next; 705 next = findNext(); 706 return lnext; 707 } 708 709 @SuppressWarnings("unchecked") 710 private T findNext() { 711 for (int i = index; i >= 0; i--) { 712 final Object node = stack[i]; 713 if (node == until) { 714 return null; 715 } 716 if (clazz.isAssignableFrom(node.getClass())) { 717 index = i - 1; 718 return (T)node; 719 } 720 } 721 return null; 722 } 723 724 @Override 725 public void remove() { 726 throw new UnsupportedOperationException(); 727 } 728 } 729 }