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