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