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.indexOf(File.pathSeparator) != -1) {
591 src = src.substring(src.lastIndexOf(File.pathSeparator));
592 }
593 src += ' ';
594 src += source.getLine(fn.getStart());
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 }