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 LexicalContextNode> 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(LexicalContextNode)} 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      * Check the lexical context for a given label node by name
 569      * @param name name of the label
 570      * @return LabelNode if found, null otherwise
 571      */
 572     public LabelNode findLabel(final String name) {
 573         for (final Iterator<LabelNode> iter = new NodeIterator<>(LabelNode.class, getCurrentFunction()); iter.hasNext(); ) {
 574             final LabelNode next = iter.next();
 575             if (next.getLabelName().equals(name)) {
 576                 return next;
 577             }
 578         }
 579         return null;
 580     }
 581 
 582     /**
 583      * Checks whether a given target is a jump destination that lies outside a given split node
 584      * @param splitNode the split node
 585      * @param target the target node
 586      * @return true if target resides outside the split node
 587      */
 588     public boolean isExternalTarget(final SplitNode splitNode, final BreakableNode target) {
 589         for (int i = sp; i-- > 0;) {
 590             final LexicalContextNode next = stack[i];
 591             if (next == splitNode) {
 592                 return true;
 593             } else if (next == target) {
 594                 return false;
 595             }
 596         }
 597         throw new AssertionError(target + " was expected in lexical context " + LexicalContext.this + " but wasn't");
 598     }
 599 














 600     @Override
 601     public String toString() {
 602         final StringBuffer sb = new StringBuffer();
 603         sb.append("[ ");
 604         for (int i = 0; i < sp; i++) {
 605             final Object node = stack[i];
 606             sb.append(node.getClass().getSimpleName());
 607             sb.append('@');
 608             sb.append(Debug.id(node));
 609             sb.append(':');
 610             if (node instanceof FunctionNode) {
 611                 final FunctionNode fn = (FunctionNode)node;
 612                 final Source source = fn.getSource();
 613                 String src = source.toString();
 614                 if (src.contains(File.pathSeparator)) {
 615                     src = src.substring(src.lastIndexOf(File.pathSeparator));
 616                 }
 617                 src += ' ';
 618                 src += fn.getLineNumber();
 619                 sb.append(src);
 620             }
 621             sb.append(' ');
 622         }
 623         sb.append(" ==> ]");
 624         return sb.toString();
 625     }
 626 
 627     private class NodeIterator <T extends LexicalContextNode> implements Iterator<T> {
 628         private int index;
 629         private T next;
 630         private final Class<T> clazz;
 631         private LexicalContextNode until;
 632 
 633         NodeIterator(final Class<T> clazz) {
 634             this(clazz, null);
 635         }
 636 
 637         NodeIterator(final Class<T> clazz, final LexicalContextNode until) {
 638             this.index = sp - 1;
 639             this.clazz = clazz;
 640             this.until = until;
 641             this.next  = findNext();
 642         }
 643 
 644         @Override
 645         public boolean hasNext() {
 646             return next != null;
 647         }
 648 
 649         @Override
 650         public T next() {
 651             if (next == null) {
 652                 throw new NoSuchElementException();
 653             }
 654             final T lnext = next;
 655             next = findNext();
 656             return lnext;
 657         }
 658 
 659         @SuppressWarnings("unchecked")
 660         private T findNext() {
 661             for (int i = index; i >= 0; i--) {
 662                 final Object node = stack[i];
 663                 if (node == until) {
 664                     return null;
 665                 }
 666                 if (clazz.isAssignableFrom(node.getClass())) {
 667                     index = i - 1;
 668                     return (T)node;
 669                 }
 670             }
 671             return null;
 672         }
 673 
 674         @Override
 675         public void remove() {
 676             throw new UnsupportedOperationException();
 677         }
 678     }
 679 }
--- EOF ---