001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2006 Terence Parr
004: All rights reserved.
005:
006: Redistribution and use in source and binary forms, with or without
007: modification, are permitted provided that the following conditions
008: are met:
009: 1. Redistributions of source code must retain the above copyright
010: notice, this list of conditions and the following disclaimer.
011: 2. Redistributions in binary form must reproduce the above copyright
012: notice, this list of conditions and the following disclaimer in the
013: documentation and/or other materials provided with the distribution.
014: 3. The name of the author may not be used to endorse or promote products
015: derived from this software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
018: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
019: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
020: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
021: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
022: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
023: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
024: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
026: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028: package org.antlr.runtime.tree;
029:
030: import org.antlr.runtime.Token;
031: import org.antlr.runtime.TokenStream;
032:
033: import java.util.ArrayList;
034: import java.util.List;
035: import java.util.Stack;
036:
037: /** A stream of tree nodes, accessing nodes from a tree of ANY kind.
038: * No new nodes should be created in tree during the walk. A small buffer
039: * of tokens is kept to efficiently and easily handle LT(i) calls, though
040: * the lookahead mechanism is fairly complicated.
041: *
042: * For tree rewriting during tree parsing, this must also be able
043: * to replace a set of children without "losing its place".
044: * That part is not yet implemented. Will permit a rule to return
045: * a different tree and have it stitched into the output tree probably.
046: *
047: * @see CommonTreeNodeStream
048: */
049: public class UnBufferedTreeNodeStream implements TreeNodeStream {
050: public static final int INITIAL_LOOKAHEAD_BUFFER_SIZE = 5;
051:
052: /** Reuse same DOWN, UP navigation nodes unless this is true */
053: protected boolean uniqueNavigationNodes = false;
054:
055: /** Pull nodes from which tree? */
056: protected Object root;
057:
058: /** IF this tree (root) was created from a token stream, track it. */
059: protected TokenStream tokens;
060:
061: /** What tree adaptor was used to build these trees */
062: TreeAdaptor adaptor;
063:
064: /** As we walk down the nodes, we must track parent nodes so we know
065: * where to go after walking the last child of a node. When visiting
066: * a child, push current node and current index.
067: */
068: protected Stack nodeStack = new Stack();
069:
070: /** Track which child index you are visiting for each node we push.
071: * TODO: pretty inefficient...use int[] when you have time
072: */
073: protected Stack indexStack = new Stack();
074:
075: /** Which node are we currently visiting? */
076: protected Object currentNode;
077:
078: /** Which node did we visit last? Used for LT(-1) calls. */
079: protected Object previousNode;
080:
081: /** Which child are we currently visiting? If -1 we have not visited
082: * this node yet; next consume() request will set currentIndex to 0.
083: */
084: protected int currentChildIndex;
085:
086: /** What node index did we just consume? i=0..n-1 for n node trees.
087: * IntStream.next is hence 1 + this value. Size will be same.
088: */
089: protected int absoluteNodeIndex;
090:
091: /** Buffer tree node stream for use with LT(i). This list grows
092: * to fit new lookahead depths, but consume() wraps like a circular
093: * buffer.
094: */
095: protected Object[] lookahead = new Object[INITIAL_LOOKAHEAD_BUFFER_SIZE];
096:
097: /** lookahead[head] is the first symbol of lookahead, LT(1). */
098: protected int head;
099:
100: /** Add new lookahead at lookahead[tail]. tail wraps around at the
101: * end of the lookahead buffer so tail could be less than head.
102: */
103: protected int tail;
104:
105: /** When walking ahead with cyclic DFA or for syntactic predicates,
106: * we need to record the state of the tree node stream. This
107: * class wraps up the current state of the UnBufferedTreeNodeStream.
108: * Calling mark() will push another of these on the markers stack.
109: */
110: protected class TreeWalkState {
111: int currentChildIndex;
112: int absoluteNodeIndex;
113: Object currentNode;
114: Object previousNode;
115: /** Record state of the nodeStack */
116: int nodeStackSize;
117: /** Record state of the indexStack */
118: int indexStackSize;
119: Object[] lookahead;
120: }
121:
122: /** Calls to mark() may be nested so we have to track a stack of
123: * them. The marker is an index into this stack.
124: * This is a List<TreeWalkState>. Indexed from 1..markDepth.
125: * A null is kept @ index 0. Create upon first call to mark().
126: */
127: protected List markers;
128:
129: /** tracks how deep mark() calls are nested */
130: protected int markDepth = 0;
131:
132: /** Track the last mark() call result value for use in rewind(). */
133: protected int lastMarker;
134:
135: // navigation nodes
136:
137: protected Object down;
138: protected Object up;
139: protected Object eof;
140:
141: public UnBufferedTreeNodeStream(Object tree) {
142: this (new CommonTreeAdaptor(), tree);
143: }
144:
145: public UnBufferedTreeNodeStream(TreeAdaptor adaptor, Object tree) {
146: this .root = tree;
147: this .adaptor = adaptor;
148: reset();
149: down = adaptor.create(Token.DOWN, "DOWN");
150: up = adaptor.create(Token.UP, "UP");
151: eof = adaptor.create(Token.EOF, "EOF");
152: }
153:
154: public void reset() {
155: currentNode = root;
156: previousNode = null;
157: currentChildIndex = -1;
158: absoluteNodeIndex = -1;
159: head = tail = 0;
160: }
161:
162: // Satisfy TreeNodeStream
163:
164: public Object get(int i) {
165: throw new UnsupportedOperationException("stream is unbuffered");
166: }
167:
168: /** Get tree node at current input pointer + i ahead where i=1 is next node.
169: * i<0 indicates nodes in the past. So -1 is previous node and -2 is
170: * two nodes ago. LT(0) is undefined. For i>=n, return null.
171: * Return null for LT(0) and any index that results in an absolute address
172: * that is negative.
173: *
174: * This is analogus to the LT() method of the TokenStream, but this
175: * returns a tree node instead of a token. Makes code gen identical
176: * for both parser and tree grammars. :)
177: */
178: public Object LT(int k) {
179: //System.out.println("LT("+k+"); head="+head+", tail="+tail);
180: if (k == -1) {
181: return previousNode;
182: }
183: if (k < 0) {
184: throw new IllegalArgumentException(
185: "tree node streams cannot look backwards more than 1 node");
186: }
187: if (k == 0) {
188: return Tree.INVALID_NODE;
189: }
190: fill(k);
191: return lookahead[(head + k - 1) % lookahead.length];
192: }
193:
194: /** Where is this stream pulling nodes from? This is not the name, but
195: * the object that provides node objects.
196: */
197: public Object getTreeSource() {
198: return root;
199: }
200:
201: public TokenStream getTokenStream() {
202: return tokens;
203: }
204:
205: public void setTokenStream(TokenStream tokens) {
206: this .tokens = tokens;
207: }
208:
209: /** Make sure we have at least k symbols in lookahead buffer */
210: protected void fill(int k) {
211: int n = getLookaheadSize();
212: //System.out.println("we have "+n+" nodes; need "+(k-n));
213: for (int i = 1; i <= k - n; i++) {
214: next(); // get at least k-depth lookahead nodes
215: }
216: }
217:
218: /** Add a node to the lookahead buffer. Add at lookahead[tail].
219: * If you tail+1 == head, then we must create a bigger buffer
220: * and copy all the nodes over plus reset head, tail. After
221: * this method, LT(1) will be lookahead[0].
222: */
223: protected void addLookahead(Object node) {
224: //System.out.println("addLookahead head="+head+", tail="+tail);
225: lookahead[tail] = node;
226: tail = (tail + 1) % lookahead.length;
227: if (tail == head) {
228: // buffer overflow: tail caught up with head
229: // allocate a buffer 2x as big
230: Object[] bigger = new Object[2 * lookahead.length];
231: // copy head to end of buffer to beginning of bigger buffer
232: int remainderHeadToEnd = lookahead.length - head;
233: System.arraycopy(lookahead, head, bigger, 0,
234: remainderHeadToEnd);
235: // copy 0..tail to after that
236: System.arraycopy(lookahead, 0, bigger, remainderHeadToEnd,
237: tail);
238: lookahead = bigger; // reset to bigger buffer
239: head = 0;
240: tail += remainderHeadToEnd;
241: }
242: }
243:
244: // Satisfy IntStream interface
245:
246: public void consume() {
247: /*
248: System.out.println("consume: currentNode="+currentNode.getType()+
249: " childIndex="+currentChildIndex+
250: " nodeIndex="+absoluteNodeIndex);
251: */
252: // make sure there is something in lookahead buf, which might call next()
253: fill(1);
254: absoluteNodeIndex++;
255: previousNode = lookahead[head]; // track previous node before moving on
256: head = (head + 1) % lookahead.length;
257: }
258:
259: public int LA(int i) {
260: Object t = LT(i);
261: if (t == null) {
262: return Token.INVALID_TOKEN_TYPE;
263: }
264: return adaptor.getType(t);
265: }
266:
267: /** Record the current state of the tree walk which includes
268: * the current node and stack state as well as the lookahead
269: * buffer.
270: */
271: public int mark() {
272: if (markers == null) {
273: markers = new ArrayList();
274: markers.add(null); // depth 0 means no backtracking, leave blank
275: }
276: markDepth++;
277: TreeWalkState state = null;
278: if (markDepth >= markers.size()) {
279: state = new TreeWalkState();
280: markers.add(state);
281: } else {
282: state = (TreeWalkState) markers.get(markDepth);
283: }
284: state.absoluteNodeIndex = absoluteNodeIndex;
285: state.currentChildIndex = currentChildIndex;
286: state.currentNode = currentNode;
287: state.previousNode = previousNode;
288: state.nodeStackSize = nodeStack.size();
289: state.indexStackSize = indexStack.size();
290: // take snapshot of lookahead buffer
291: int n = getLookaheadSize();
292: int i = 0;
293: state.lookahead = new Object[n];
294: for (int k = 1; k <= n; k++, i++) {
295: state.lookahead[i] = LT(k);
296: }
297: lastMarker = markDepth;
298: return markDepth;
299: }
300:
301: public void release(int marker) {
302: // unwind any other markers made after marker and release marker
303: markDepth = marker;
304: // release this marker
305: markDepth--;
306: }
307:
308: /** Rewind the current state of the tree walk to the state it
309: * was in when mark() was called and it returned marker. Also,
310: * wipe out the lookahead which will force reloading a few nodes
311: * but it is better than making a copy of the lookahead buffer
312: * upon mark().
313: */
314: public void rewind(int marker) {
315: if (markers == null) {
316: return;
317: }
318: TreeWalkState state = (TreeWalkState) markers.get(marker);
319: absoluteNodeIndex = state.absoluteNodeIndex;
320: currentChildIndex = state.currentChildIndex;
321: currentNode = state.currentNode;
322: previousNode = state.previousNode;
323: // drop node and index stacks back to old size
324: nodeStack.setSize(state.nodeStackSize);
325: indexStack.setSize(state.indexStackSize);
326: head = tail = 0; // wack lookahead buffer and then refill
327: for (; tail < state.lookahead.length; tail++) {
328: lookahead[tail] = state.lookahead[tail];
329: }
330: release(marker);
331: }
332:
333: public void rewind() {
334: rewind(lastMarker);
335: }
336:
337: /** consume() ahead until we hit index. Can't just jump ahead--must
338: * spit out the navigation nodes.
339: */
340: public void seek(int index) {
341: if (index < this .index()) {
342: throw new IllegalArgumentException(
343: "can't seek backwards in node stream");
344: }
345: // seek forward, consume until we hit index
346: while (this .index() < index) {
347: consume();
348: }
349: }
350:
351: public int index() {
352: return absoluteNodeIndex + 1;
353: }
354:
355: /** Expensive to compute; recursively walk tree to find size;
356: * include navigation nodes and EOF. Reuse functionality
357: * in CommonTreeNodeStream as we only really use this
358: * for testing.
359: */
360: public int size() {
361: CommonTreeNodeStream s = new CommonTreeNodeStream(root);
362: return s.size();
363: }
364:
365: /** Return the next node found during a depth-first walk of root.
366: * Also, add these nodes and DOWN/UP imaginary nodes into the lokoahead
367: * buffer as a side-effect. Normally side-effects are bad, but because
368: * we can emit many tokens for every next() call, it's pretty hard to
369: * use a single return value for that. We must add these tokens to
370: * the lookahead buffer.
371: *
372: * This does *not* return the DOWN/UP nodes; those are only returned
373: * by the LT() method.
374: *
375: * Ugh. This mechanism is much more complicated than a recursive
376: * solution, but it's the only way to provide nodes on-demand instead
377: * of walking once completely through and buffering up the nodes. :(
378: */
379: public Object next() {
380: // already walked entire tree; nothing to return
381: if (currentNode == null) {
382: addLookahead(eof);
383: // this is infinite stream returning EOF at end forever
384: // so don't throw NoSuchElementException
385: return null;
386: }
387:
388: // initial condition (first time method is called)
389: if (currentChildIndex == -1) {
390: return handleRootNode();
391: }
392:
393: // index is in the child list?
394: if (currentChildIndex < adaptor.getChildCount(currentNode)) {
395: return visitChild(currentChildIndex);
396: }
397:
398: // hit end of child list, return to parent node or its parent ...
399: walkBackToMostRecentNodeWithUnvisitedChildren();
400: if (currentNode != null) {
401: return visitChild(currentChildIndex);
402: }
403:
404: return null;
405: }
406:
407: protected Object handleRootNode() {
408: Object node;
409: node = currentNode;
410: // point to first child in prep for subsequent next()
411: currentChildIndex = 0;
412: if (adaptor.isNil(node)) {
413: // don't count this root nil node
414: node = visitChild(currentChildIndex);
415: } else {
416: addLookahead(node);
417: if (adaptor.getChildCount(currentNode) == 0) {
418: // single node case
419: currentNode = null; // say we're done
420: }
421: }
422: return node;
423: }
424:
425: protected Object visitChild(int child) {
426: Object node = null;
427: // save state
428: nodeStack.push(currentNode);
429: indexStack.push(new Integer(child));
430: if (child == 0 && !adaptor.isNil(currentNode)) {
431: addNavigationNode(Token.DOWN);
432: }
433: // visit child
434: currentNode = adaptor.getChild(currentNode, child);
435: currentChildIndex = 0;
436: node = currentNode; // record node to return
437: addLookahead(node);
438: walkBackToMostRecentNodeWithUnvisitedChildren();
439: return node;
440: }
441:
442: /** As we flatten the tree, we use UP, DOWN nodes to represent
443: * the tree structure. When debugging we need unique nodes
444: * so instantiate new ones when uniqueNavigationNodes is true.
445: */
446: protected void addNavigationNode(final int ttype) {
447: Object navNode = null;
448: if (ttype == Token.DOWN) {
449: if (hasUniqueNavigationNodes()) {
450: navNode = adaptor.create(Token.DOWN, "DOWN");
451: } else {
452: navNode = down;
453: }
454: } else {
455: if (hasUniqueNavigationNodes()) {
456: navNode = adaptor.create(Token.UP, "UP");
457: } else {
458: navNode = up;
459: }
460: }
461: addLookahead(navNode);
462: }
463:
464: /** Walk upwards looking for a node with more children to walk. */
465: protected void walkBackToMostRecentNodeWithUnvisitedChildren() {
466: while (currentNode != null
467: && currentChildIndex >= adaptor
468: .getChildCount(currentNode)) {
469: currentNode = nodeStack.pop();
470: if (currentNode == null) { // hit the root?
471: return;
472: }
473: currentChildIndex = ((Integer) indexStack.pop()).intValue();
474: currentChildIndex++; // move to next child
475: if (currentChildIndex >= adaptor.getChildCount(currentNode)) {
476: if (!adaptor.isNil(currentNode)) {
477: addNavigationNode(Token.UP);
478: }
479: if (currentNode == root) { // we done yet?
480: currentNode = null;
481: }
482: }
483: }
484: }
485:
486: public TreeAdaptor getTreeAdaptor() {
487: return adaptor;
488: }
489:
490: public boolean hasUniqueNavigationNodes() {
491: return uniqueNavigationNodes;
492: }
493:
494: public void setUniqueNavigationNodes(boolean uniqueNavigationNodes) {
495: this .uniqueNavigationNodes = uniqueNavigationNodes;
496: }
497:
498: /** Print out the entire tree including DOWN/UP nodes. Uses
499: * a recursive walk. Mostly useful for testing as it yields
500: * the token types not text.
501: */
502: public String toString() {
503: return toString(root, null);
504: }
505:
506: protected int getLookaheadSize() {
507: return tail < head ? (lookahead.length - head + tail)
508: : (tail - head);
509: }
510:
511: public String toString(Object start, Object stop) {
512: if (start == null) {
513: return null;
514: }
515: // if we have the token stream, use that to dump text in order
516: if (tokens != null) {
517: // don't trust stop node as it's often an UP node etc...
518: // walk backwards until you find a non-UP, non-DOWN node
519: // and ask for it's token index.
520: int beginTokenIndex = adaptor.getTokenStartIndex(start);
521: int endTokenIndex = adaptor.getTokenStopIndex(stop);
522: if (stop != null && adaptor.getType(stop) == Token.UP) {
523: endTokenIndex = adaptor.getTokenStopIndex(start);
524: } else {
525: endTokenIndex = size() - 1;
526: }
527: return tokens.toString(beginTokenIndex, endTokenIndex);
528: }
529: StringBuffer buf = new StringBuffer();
530: toStringWork(start, stop, buf);
531: return buf.toString();
532: }
533:
534: protected void toStringWork(Object p, Object stop, StringBuffer buf) {
535: if (!adaptor.isNil(p)) {
536: String text = adaptor.getText(p);
537: if (text == null) {
538: text = " " + String.valueOf(adaptor.getType(p));
539: }
540: buf.append(text); // ask the node to go to string
541: }
542: if (p == stop) {
543: return;
544: }
545: int n = adaptor.getChildCount(p);
546: if (n > 0 && !adaptor.isNil(p)) {
547: buf.append(" ");
548: buf.append(Token.DOWN);
549: }
550: for (int c = 0; c < n; c++) {
551: Object child = adaptor.getChild(p, c);
552: toStringWork(child, stop, buf);
553: }
554: if (n > 0 && !adaptor.isNil(p)) {
555: buf.append(" ");
556: buf.append(Token.UP);
557: }
558: }
559: }
|