1 /*
2 * Copyright (c) 2014, 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.parser;
26
27 import java.util.Iterator;
28 import java.util.NoSuchElementException;
29 import jdk.nashorn.internal.ir.Statement;
30
31 /**
32 * A class that tracks the current lexical context of node visitation as a stack of {@code ParserContextNode} nodes. Has special
33 * methods to retrieve useful subsets of the context.
34 *
35 * This is implemented with a primitive array and a stack pointer, because it really makes a difference
36 * performance wise. None of the collection classes were optimal
37 */
38
39 class ParserContext {
40
41 private ParserContextNode[] stack;
42 private int sp;
43
44 private static final int INITIAL_DEPTH = 16;
45
46 /**
47 * Constructs a ParserContext,
48 * initializes the stack
49 */
50 public ParserContext(){
51 this.sp = 0;
52 this.stack = new ParserContextNode[INITIAL_DEPTH];
53 }
54
55 /**
56 * Pushes a new block on top of the context, making it the innermost open block.
57 * @param node the new node
58 * @return The node that was pushed
59 */
60 public <T extends ParserContextNode> T push(final T node) {
61 assert !contains(node);
62 if (sp == stack.length) {
63 final ParserContextNode[] newStack = new ParserContextNode[sp * 2];
64 System.arraycopy(stack, 0, newStack, 0, sp);
65 stack = newStack;
66 }
67 stack[sp] = node;
68 sp++;
69
70 return node;
71 }
72
73 /**
74 * The topmost node on the stack
75 * @return The topmost node on the stack
76 */
77 public ParserContextNode peek() {
78 return stack[sp - 1];
79 }
80
81 /**
82 * Removes and returns the topmost Node from the stack.
83 * @param node The node expected to be popped, used for sanity check
84 * @return The removed node
85 */
86 public <T extends ParserContextNode> T pop(final T node) {
87 --sp;
88 @SuppressWarnings("unchecked")
89 final T popped = (T)stack[sp];
90 stack[sp] = null;
91 assert node == popped;
92
93 return popped;
94 }
95
96 /**
97 * Tests if a node is on the stack.
98 * @param node The node to test
99 * @return true if stack contains node, false otherwise
100 */
101 public boolean contains(final ParserContextNode node) {
102 for (int i = 0; i < sp; i++) {
103 if (stack[i] == node) {
104 return true;
105 }
106 }
107 return false;
108 }
109
110 /**
111 * Returns the topmost {@link ParserContextBreakableNode} on the stack, null if none on stack
112 * @return Returns the topmost {@link ParserContextBreakableNode} on the stack, null if none on stack
113 */
114 private ParserContextBreakableNode getBreakable() {
115 for (final NodeIterator<ParserContextBreakableNode> iter = new NodeIterator<>(ParserContextBreakableNode.class, getCurrentFunction()); iter.hasNext(); ) {
116 final ParserContextBreakableNode next = iter.next();
117 if (next.isBreakableWithoutLabel()) {
118 return next;
119 }
120 }
121 return null;
122 }
123
124
125
126 /**
127 * Find the breakable node corresponding to this label.
128 * @param labelName name of the label to search for. If null, the closest breakable node will be returned
129 * unconditionally, e.g. a while loop with no label
130 * @return closest breakable node
131 */
132 public ParserContextBreakableNode getBreakable(final String labelName) {
133 if (labelName != null) {
134 final ParserContextLabelNode foundLabel = findLabel(labelName);
135 if (foundLabel != null) {
136 // iterate to the nearest breakable to the foundLabel
137 ParserContextBreakableNode breakable = null;
138 for (final NodeIterator<ParserContextBreakableNode> iter = new NodeIterator<>(ParserContextBreakableNode.class, foundLabel); iter.hasNext(); ) {
139 breakable = iter.next();
140 }
141 return breakable;
142 }
143 return null;
144 }
145 return getBreakable();
146 }
147
148 /**
149 * Returns the loop node of the current loop, or null if not inside a loop
150 * @return loop noder
151 */
152 public ParserContextLoopNode getCurrentLoop() {
153 final Iterator<ParserContextLoopNode> iter = new NodeIterator<>(ParserContextLoopNode.class, getCurrentFunction());
154 return iter.hasNext() ? iter.next() : null;
155 }
156
157 private ParserContextLoopNode getContinueTo() {
158 return getCurrentLoop();
159 }
160
161 /**
162 * Find the continue target node corresponding to this label.
163 * @param labelName label name to search for. If null the closest loop node will be returned unconditionally, e.g. a
164 * while loop with no label
165 * @return closest continue target node
166 */
167 public ParserContextLoopNode getContinueTo(final String labelName) {
168 if (labelName != null) {
169 final ParserContextLabelNode foundLabel = findLabel(labelName);
170 if (foundLabel != null) {
171 // iterate to the nearest loop to the foundLabel
172 ParserContextLoopNode loop = null;
173 for (final NodeIterator<ParserContextLoopNode> iter = new NodeIterator<>(ParserContextLoopNode.class, foundLabel); iter.hasNext(); ) {
174 loop = iter.next();
175 }
176 return loop;
177 }
178 return null;
179 }
180 return getContinueTo();
181 }
182
183 /**
184 * Get the function body of a function node on the stack.
185 * This will trigger an assertion if node isn't present
186 * @param functionNode function node
187 * @return body of function node
188 */
189 public ParserContextBlockNode getFunctionBody(final ParserContextFunctionNode functionNode) {
190 for (int i = sp - 1; i >= 0 ; i--) {
191 if (stack[i] == functionNode) {
192 return (ParserContextBlockNode)stack[i + 1];
193 }
194 }
195 throw new AssertionError(functionNode.getName() + " not on context stack");
196 }
197
198 /**
199 * Check the stack for a given label node by name
200 * @param name name of the label
201 * @return LabelNode if found, null otherwise
202 */
203 public ParserContextLabelNode findLabel(final String name) {
204 for (final Iterator<ParserContextLabelNode> iter = new NodeIterator<>(ParserContextLabelNode.class, getCurrentFunction()); iter.hasNext(); ) {
205 final ParserContextLabelNode next = iter.next();
206 if (next.getLabelName().equals(name)) {
207 return next;
208 }
209 }
210 return null;
211 }
212
213 /**
214 * Prepends a statement to the current node.
215 * @param statement The statement to prepend
216 */
217 public void prependStatementToCurrentNode(final Statement statement) {
218 assert statement != null;
219 stack[sp - 1].prependStatement(statement);
220 }
221
222 /**
223 * Appends a statement to the current Node.
224 * @param statement The statement to append
225 */
226 public void appendStatementToCurrentNode(final Statement statement) {
227 assert statement != null;
228 stack[sp - 1].appendStatement(statement);
229 }
230
231 /**
232 * Returns the innermost function in the context.
233 * @return the innermost function in the context.
234 */
235 public ParserContextFunctionNode getCurrentFunction() {
236 for (int i = sp - 1; i >= 0; i--) {
237 if (stack[i] instanceof ParserContextFunctionNode) {
238 return (ParserContextFunctionNode) stack[i];
239 }
240 }
241 return null;
242 }
243
244 /**
245 * Returns an iterator over all blocks in the context, with the top block (innermost lexical context) first.
246 * @return an iterator over all blocks in the context.
247 */
248 public Iterator<ParserContextBlockNode> getBlocks() {
249 return new NodeIterator<>(ParserContextBlockNode.class);
250 }
251
252 /**
253 * Returns the innermost block in the context.
254 * @return the innermost block in the context.
255 */
256 public ParserContextBlockNode getCurrentBlock() {
257 return getBlocks().next();
258 }
259
260 /**
261 * The last statement added to the context
262 * @return The last statement added to the context
263 */
264 public Statement getLastStatement() {
265 if (sp == 0) {
266 return null;
267 }
268 final ParserContextNode top = stack[sp - 1];
269 final int s = top.getStatements().size();
270 return s == 0 ? null : top.getStatements().get(s - 1);
271 }
272
273 /**
274 * Returns an iterator over all functions in the context, with the top (innermost open) function first.
275 * @return an iterator over all functions in the context.
276 */
277 public Iterator<ParserContextFunctionNode> getFunctions() {
278 return new NodeIterator<>(ParserContextFunctionNode.class);
279 }
280
281 public ParserContextModuleNode getCurrentModule() {
282 final Iterator<ParserContextModuleNode> iter = new NodeIterator<>(ParserContextModuleNode.class, getCurrentFunction());
283 return iter.hasNext() ? iter.next() : null;
284 }
285
286 private class NodeIterator<T extends ParserContextNode> implements Iterator<T> {
287 private int index;
288 private T next;
289 private final Class<T> clazz;
290 private ParserContextNode until;
291
292 NodeIterator(final Class<T> clazz) {
293 this(clazz, null);
294 }
295
296 NodeIterator(final Class<T> clazz, final ParserContextNode until) {
297 this.index = sp - 1;
298 this.clazz = clazz;
299 this.until = until;
300 this.next = findNext();
301 }
302
303 @Override
304 public boolean hasNext() {
305 return next != null;
306 }
307
308 @Override
309 public T next() {
310 if (next == null) {
311 throw new NoSuchElementException();
312 }
313 final T lnext = next;
314 next = findNext();
315 return lnext;
316 }
317
318 @SuppressWarnings("unchecked")
319 private T findNext() {
320 for (int i = index; i >= 0; i--) {
321 final Object node = stack[i];
322 if (node == until) {
323 return null;
324 }
325 if (clazz.isAssignableFrom(node.getClass())) {
326 index = i - 1;
327 return (T)node;
328 }
329 }
330 return null;
331 }
332
333 @Override
334 public void remove() {
335 throw new UnsupportedOperationException();
336 }
337 }
338 }