View Javadoc
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.codegen.Label;
31  import jdk.nashorn.internal.runtime.Debug;
32  import 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   */
41  public 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         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     /**
206      * Return the top element in the context
207      * @return the node that was pushed last
208      */
209     public LexicalContextNode peek() {
210         return stack[sp - 1];
211     }
212 
213     /**
214      * Check if a node is in the lexical context
215      * @param node node to check for
216      * @return true if in the context
217      */
218     public boolean contains(final LexicalContextNode node) {
219         for (int i = 0; i < sp; i++) {
220             if (stack[i] == node) {
221                 return true;
222             }
223         }
224         return false;
225     }
226 
227     /**
228      * Replace a node on the lexical context with a new one. Normally
229      * you should try to engineer IR traversals so this isn't needed
230      *
231      * @param oldNode old node
232      * @param newNode new node
233      * @return the new node
234      */
235     public LexicalContextNode replace(final LexicalContextNode oldNode, final LexicalContextNode newNode) {
236        //System.err.println("REPLACE old=" + Debug.id(oldNode) + " new=" + Debug.id(newNode));
237         for (int i = sp - 1; i >= 0; i--) {
238             if (stack[i] == oldNode) {
239                 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";
240                 stack[i] = newNode;
241                 break;
242             }
243          }
244         return newNode;
245     }
246 
247     /**
248      * Returns an iterator over all blocks in the context, with the top block (innermost lexical context) first.
249      * @return an iterator over all blocks in the context.
250      */
251     public Iterator<Block> getBlocks() {
252         return new NodeIterator<>(Block.class);
253     }
254 
255     /**
256      * Returns an iterator over all functions in the context, with the top (innermost open) function first.
257      * @return an iterator over all functions in the context.
258      */
259     public Iterator<FunctionNode> getFunctions() {
260         return new NodeIterator<>(FunctionNode.class);
261     }
262 
263     /**
264      * Get the parent block for the current lexical context block
265      * @return parent block
266      */
267     public Block getParentBlock() {
268         final Iterator<Block> iter = new NodeIterator<>(Block.class, getCurrentFunction());
269         iter.next();
270         return iter.hasNext() ? iter.next() : null;
271     }
272 
273     /**
274      * Returns an iterator over all ancestors block of the given block, with its parent block first.
275      * @param block the block whose ancestors are returned
276      * @return an iterator over all ancestors block of the given block.
277      */
278     public Iterator<Block> getAncestorBlocks(final Block block) {
279         final Iterator<Block> iter = getBlocks();
280         while (iter.hasNext()) {
281             final Block b = iter.next();
282             if (block == b) {
283                 return iter;
284             }
285         }
286         throw new AssertionError("Block is not on the current lexical context stack");
287     }
288 
289     /**
290      * Returns an iterator over a block and all its ancestors blocks, with the block first.
291      * @param block the block that is the starting point of the iteration.
292      * @return an iterator over a block and all its ancestors.
293      */
294     public Iterator<Block> getBlocks(final Block block) {
295         final Iterator<Block> iter = getAncestorBlocks(block);
296         return new Iterator<Block>() {
297             boolean blockReturned = false;
298             @Override
299             public boolean hasNext() {
300                 return iter.hasNext() || !blockReturned;
301             }
302             @Override
303             public Block next() {
304                 if (blockReturned) {
305                     return iter.next();
306                 }
307                 blockReturned = true;
308                 return block;
309             }
310             @Override
311             public void remove() {
312                 throw new UnsupportedOperationException();
313             }
314         };
315     }
316 
317     /**
318      * Get the function for this block. If the block is itself a function
319      * this returns identity
320      * @param block block for which to get function
321      * @return function for block
322      */
323     public FunctionNode getFunction(final Block block) {
324         final Iterator<LexicalContextNode> iter = new NodeIterator<>(LexicalContextNode.class);
325         while (iter.hasNext()) {
326             final LexicalContextNode next = iter.next();
327             if (next == block) {
328                 while (iter.hasNext()) {
329                     final LexicalContextNode next2 = iter.next();
330                     if (next2 instanceof FunctionNode) {
331                         return (FunctionNode)next2;
332                     }
333                 }
334             }
335         }
336         assert false;
337         return null;
338     }
339 
340     /**
341      * Returns the innermost block in the context.
342      * @return the innermost block in the context.
343      */
344     public Block getCurrentBlock() {
345         return getBlocks().next();
346     }
347 
348     /**
349      * Returns the innermost function in the context.
350      * @return the innermost function in the context.
351      */
352     public FunctionNode getCurrentFunction() {
353         for (int i = sp - 1; i >= 0; i--) {
354             if (stack[i] instanceof FunctionNode) {
355                 return (FunctionNode) stack[i];
356             }
357         }
358         return null;
359     }
360 
361     /**
362      * Get the block in which a symbol is defined
363      * @param symbol symbol
364      * @return block in which the symbol is defined, assert if no such block in context
365      */
366     public Block getDefiningBlock(final Symbol symbol) {
367         if (symbol.isTemp()) {
368             return null;
369         }
370         final String name = symbol.getName();
371         for (final Iterator<Block> it = getBlocks(); it.hasNext();) {
372             final Block next = it.next();
373             if (next.getExistingSymbol(name) == symbol) {
374                 return next;
375             }
376         }
377         throw new AssertionError("Couldn't find symbol " + name + " in the context");
378     }
379 
380     /**
381      * Get the function in which a symbol is defined
382      * @param symbol symbol
383      * @return function node in which this symbol is defined, assert if no such symbol exists in context
384      */
385     public FunctionNode getDefiningFunction(Symbol symbol) {
386         if (symbol.isTemp()) {
387             return null;
388         }
389         final String name = symbol.getName();
390         for (final Iterator<LexicalContextNode> iter = new NodeIterator<>(LexicalContextNode.class); iter.hasNext();) {
391             final LexicalContextNode next = iter.next();
392             if (next instanceof Block && ((Block)next).getExistingSymbol(name) == symbol) {
393                 while (iter.hasNext()) {
394                     final LexicalContextNode next2 = iter.next();
395                     if (next2 instanceof FunctionNode) {
396                         return ((FunctionNode)next2);
397                     }
398                 }
399                 throw new AssertionError("Defining block for symbol " + name + " has no function in the context");
400             }
401         }
402         throw new AssertionError("Couldn't find symbol " + name + " in the context");
403     }
404 
405     /**
406      * Is the topmost lexical context element a function body?
407      * @return true if function body
408      */
409     public boolean isFunctionBody() {
410         return getParentBlock() == null;
411     }
412 
413     /**
414      * Returns true if the expression defining the function is a callee of a CallNode that should be the second
415      * element on the stack, e.g. <code>(function(){})()</code>. That is, if the stack ends with
416      * {@code [..., CallNode, FunctionNode]} then {@code callNode.getFunction()} should be equal to
417      * {@code functionNode}, and the top of the stack should itself be a variant of {@code functionNode}.
418      * @param functionNode the function node being tested
419      * @return true if the expression defining the current function is a callee of a call expression.
420      */
421     public boolean isFunctionDefinedInCurrentCall(FunctionNode functionNode) {
422         final LexicalContextNode parent = stack[sp - 2];
423         if (parent instanceof CallNode && ((CallNode)parent).getFunction() == functionNode) {
424             return true;
425         }
426         return false;
427     }
428 
429     /**
430      * Get the parent function for a function in the lexical context
431      * @param functionNode function for which to get parent
432      * @return parent function of functionNode or null if none (e.g. if functionNode is the program)
433      */
434     public FunctionNode getParentFunction(final FunctionNode functionNode) {
435         final Iterator<FunctionNode> iter = new NodeIterator<>(FunctionNode.class);
436         while (iter.hasNext()) {
437             final FunctionNode next = iter.next();
438             if (next == functionNode) {
439                 return iter.hasNext() ? iter.next() : null;
440             }
441         }
442         assert false;
443         return null;
444     }
445 
446     /**
447      * Count the number of with scopes until a given node
448      * @param until node to stop counting at, or null if all nodes should be counted
449      * @return number of with scopes encountered in the context
450      */
451     public int getScopeNestingLevelTo(final LexicalContextNode until) {
452         //count the number of with nodes until "until" is hit
453         int n = 0;
454         for (final Iterator<WithNode> iter = new NodeIterator<>(WithNode.class, until); iter.hasNext(); iter.next()) {
455             n++;
456         }
457         return n;
458     }
459 
460     private BreakableNode getBreakable() {
461         for (final NodeIterator<BreakableNode> iter = new NodeIterator<>(BreakableNode.class, getCurrentFunction()); iter.hasNext(); ) {
462             final BreakableNode next = iter.next();
463             if (next.isBreakableWithoutLabel()) {
464                 return next;
465             }
466         }
467         return null;
468     }
469 
470     /**
471      * Check whether the lexical context is currently inside a loop
472      * @return true if inside a loop
473      */
474     public boolean inLoop() {
475         return getCurrentLoop() != null;
476     }
477 
478     /**
479      * Returns the loop header of the current loop, or null if not inside a loop
480      * @return loop header
481      */
482     public LoopNode getCurrentLoop() {
483         final Iterator<LoopNode> iter = new NodeIterator<>(LoopNode.class, getCurrentFunction());
484         return iter.hasNext() ? iter.next() : null;
485     }
486 
487     /**
488      * Find the breakable node corresponding to this label.
489      * @param label label to search for, if null the closest breakable node will be returned unconditionally, e.g. a while loop with no label
490      * @return closest breakable node
491      */
492     public BreakableNode getBreakable(final IdentNode label) {
493         if (label != null) {
494             final LabelNode foundLabel = findLabel(label.getName());
495             if (foundLabel != null) {
496                 // iterate to the nearest breakable to the foundLabel
497                 BreakableNode breakable = null;
498                 for (final NodeIterator<BreakableNode> iter = new NodeIterator<>(BreakableNode.class, foundLabel); iter.hasNext(); ) {
499                     breakable = iter.next();
500                 }
501                 return breakable;
502             }
503             return null;
504         }
505         return getBreakable();
506     }
507 
508     private LoopNode getContinueTo() {
509         return getCurrentLoop();
510     }
511 
512     /**
513      * Find the continue target node corresponding to this label.
514      * @param label label to search for, if null the closest loop node will be returned unconditionally, e.g. a while loop with no label
515      * @return closest continue target node
516      */
517     public LoopNode getContinueTo(final IdentNode label) {
518         if (label != null) {
519             final LabelNode foundLabel = findLabel(label.getName());
520             if (foundLabel != null) {
521                 // iterate to the nearest loop to the foundLabel
522                 LoopNode loop = null;
523                 for (final NodeIterator<LoopNode> iter = new NodeIterator<>(LoopNode.class, foundLabel); iter.hasNext(); ) {
524                     loop = iter.next();
525                 }
526                 return loop;
527             }
528             return null;
529         }
530         return getContinueTo();
531     }
532 
533     /**
534      * Check the lexical context for a given label node by name
535      * @param name name of the label
536      * @return LabelNode if found, null otherwise
537      */
538     public LabelNode findLabel(final String name) {
539         for (final Iterator<LabelNode> iter = new NodeIterator<>(LabelNode.class, getCurrentFunction()); iter.hasNext(); ) {
540             final LabelNode next = iter.next();
541             if (next.getLabel().getName().equals(name)) {
542                 return next;
543             }
544         }
545         return null;
546     }
547 
548     /**
549      * Checks whether a given label is a jump destination that lies outside a given
550      * split node
551      * @param splitNode the split node
552      * @param label     the label
553      * @return true if label resides outside the split node
554      */
555     public boolean isExternalTarget(final SplitNode splitNode, final Label label) {
556         boolean targetFound = false;
557         for (int i = sp - 1; i >= 0; i--) {
558             final LexicalContextNode next = stack[i];
559             if (next == splitNode) {
560                 return !targetFound;
561             }
562 
563             if (next instanceof BreakableNode) {
564                 for (final Label l : ((BreakableNode)next).getLabels()) {
565                     if (l == label) {
566                         targetFound = true;
567                         break;
568                     }
569                 }
570             }
571         }
572         assert false : label + " was expected in lexical context " + LexicalContext.this + " but wasn't";
573         return false;
574     }
575 
576     @Override
577     public String toString() {
578         final StringBuffer sb = new StringBuffer();
579         sb.append("[ ");
580         for (int i = 0; i < sp; i++) {
581             final Object node = stack[i];
582             sb.append(node.getClass().getSimpleName());
583             sb.append('@');
584             sb.append(Debug.id(node));
585             sb.append(':');
586             if (node instanceof FunctionNode) {
587                 final FunctionNode fn = (FunctionNode)node;
588                 final Source source = fn.getSource();
589                 String src = source.toString();
590                 if (src.contains(File.pathSeparator)) {
591                     src = src.substring(src.lastIndexOf(File.pathSeparator));
592                 }
593                 src += ' ';
594                 src += fn.getLineNumber();
595                 sb.append(src);
596             }
597             sb.append(' ');
598         }
599         sb.append(" ==> ]");
600         return sb.toString();
601     }
602 
603     private class NodeIterator <T extends LexicalContextNode> implements Iterator<T> {
604         private int index;
605         private T next;
606         private final Class<T> clazz;
607         private LexicalContextNode until;
608 
609         NodeIterator(final Class<T> clazz) {
610             this(clazz, null);
611         }
612 
613         NodeIterator(final Class<T> clazz, final LexicalContextNode until) {
614             this.index = sp - 1;
615             this.clazz = clazz;
616             this.until = until;
617             this.next  = findNext();
618         }
619 
620         @Override
621         public boolean hasNext() {
622             return next != null;
623         }
624 
625         @Override
626         public T next() {
627             if (next == null) {
628                 throw new NoSuchElementException();
629             }
630             T lnext = next;
631             next = findNext();
632             return lnext;
633         }
634 
635         private T findNext() {
636             for (int i = index; i >= 0; i--) {
637                 final Object node = stack[i];
638                 if (node == until) {
639                     return null;
640                 }
641                 if (clazz.isAssignableFrom(node.getClass())) {
642                     index = i - 1;
643                     return clazz.cast(node);
644                 }
645             }
646             return null;
647         }
648 
649         @Override
650         public void remove() {
651             throw new UnsupportedOperationException();
652         }
653     }
654 }