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
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 Node> 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(Node)} 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 * Find the inlined finally block node corresponding to this label.
569 * @param labelName label name to search for. Must not be null.
570 * @return closest inlined finally block with the given label
571 */
572 public Block getInlinedFinally(final String labelName) {
573 for (final NodeIterator<TryNode> iter = new NodeIterator<>(TryNode.class); iter.hasNext(); ) {
574 final Block inlinedFinally = iter.next().getInlinedFinally(labelName);
575 if (inlinedFinally != null) {
576 return inlinedFinally;
577 }
578 }
579 return null;
580 }
581
582 /**
583 * Find the try node for an inlined finally block corresponding to this label.
584 * @param labelName label name to search for. Must not be null.
585 * @return the try node to which the labelled inlined finally block belongs.
586 */
587 public TryNode getTryNodeForInlinedFinally(final String labelName) {
588 for (final NodeIterator<TryNode> iter = new NodeIterator<>(TryNode.class); iter.hasNext(); ) {
589 final TryNode tryNode = iter.next();
590 if (tryNode.getInlinedFinally(labelName) != null) {
591 return tryNode;
592 }
593 }
594 return null;
595 }
596
597 /**
598 * Check the lexical context for a given label node by name
599 * @param name name of the label
600 * @return LabelNode if found, null otherwise
601 */
602 private LabelNode findLabel(final String name) {
603 for (final Iterator<LabelNode> iter = new NodeIterator<>(LabelNode.class, getCurrentFunction()); iter.hasNext(); ) {
604 final LabelNode next = iter.next();
605 if (next.getLabelName().equals(name)) {
606 return next;
607 }
608 }
609 return null;
610 }
611
612 /**
613 * Checks whether a given target is a jump destination that lies outside a given split node
614 * @param splitNode the split node
615 * @param target the target node
616 * @return true if target resides outside the split node
617 */
618 public boolean isExternalTarget(final SplitNode splitNode, final BreakableNode target) {
619 for (int i = sp; i-- > 0;) {
620 final LexicalContextNode next = stack[i];
621 if (next == splitNode) {
622 return true;
623 } else if (next == target) {
624 return false;
625 } else if (next instanceof TryNode) {
626 for(final Block inlinedFinally: ((TryNode)next).getInlinedFinallies()) {
627 if (TryNode.getLabelledInlinedFinallyBlock(inlinedFinally) == target) {
628 return false;
629 }
630 }
631 }
632 }
633 throw new AssertionError(target + " was expected in lexical context " + LexicalContext.this + " but wasn't");
634 }
635
636 /**
637 * Checks whether the current context is inside a switch statement without explicit blocks (curly braces).
638 * @return true if in unprotected switch statement
639 */
640 public boolean inUnprotectedSwitchContext() {
641 for (int i = sp; i > 0; i--) {
642 final LexicalContextNode next = stack[i];
643 if (next instanceof Block) {
644 return stack[i - 1] instanceof SwitchNode;
645 }
646 }
647 return false;
648 }
649
650 @Override
651 public String toString() {
652 final StringBuffer sb = new StringBuffer();
653 sb.append("[ ");
654 for (int i = 0; i < sp; i++) {
655 final Object node = stack[i];
656 sb.append(node.getClass().getSimpleName());
657 sb.append('@');
658 sb.append(Debug.id(node));
|
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
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; 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));
|