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.*;
034:
035: /** A buffered stream of tree nodes. Nodes can be from a tree of ANY kind.
036: *
037: * This node stream sucks all nodes out of the tree specified in
038: * the constructor during construction and makes pointers into
039: * the tree using an array of Object pointers. The stream necessarily
040: * includes pointers to DOWN and UP and EOF nodes.
041: *
042: * This stream knows how to mark/release for backtracking.
043: *
044: * This stream is most suitable for tree interpreters that need to
045: * jump around a lot or for tree parsers requiring speed (at cost of memory).
046: * There is some duplicated functionality here with UnBufferedTreeNodeStream
047: * but just in bookkeeping, not tree walking etc...
048: *
049: * @see UnBufferedTreeNodeStream
050: */
051: public class CommonTreeNodeStream implements TreeNodeStream {
052: public static final int DEFAULT_INITIAL_BUFFER_SIZE = 100;
053: public static final int INITIAL_CALL_STACK_SIZE = 10;
054:
055: protected class StreamIterator implements Iterator {
056: int i = 0;
057:
058: public boolean hasNext() {
059: return i < nodes.size();
060: }
061:
062: public Object next() {
063: int current = i;
064: i++;
065: if (current < nodes.size()) {
066: return nodes.get(current);
067: }
068: return eof;
069: }
070:
071: public void remove() {
072: throw new RuntimeException(
073: "cannot remove nodes from stream");
074: }
075: }
076:
077: // all these navigation nodes are shared and hence they
078: // cannot contain any line/column info
079:
080: protected Object down;
081: protected Object up;
082: protected Object eof;
083:
084: /** The complete mapping from stream index to tree node.
085: * This buffer includes pointers to DOWN, UP, and EOF nodes.
086: * It is built upon ctor invocation. The elements are type
087: * Object as we don't what the trees look like.
088: *
089: * Load upon first need of the buffer so we can set token types
090: * of interest for reverseIndexing. Slows us down a wee bit to
091: * do all of the if p==-1 testing everywhere though.
092: */
093: protected List nodes;
094:
095: /** Pull nodes from which tree? */
096: protected Object root;
097:
098: /** IF this tree (root) was created from a token stream, track it. */
099: protected TokenStream tokens;
100:
101: /** What tree adaptor was used to build these trees */
102: TreeAdaptor adaptor;
103:
104: /** Reuse same DOWN, UP navigation nodes unless this is true */
105: protected boolean uniqueNavigationNodes = false;
106:
107: /** The index into the nodes list of the current node (next node
108: * to consume). If -1, nodes array not filled yet.
109: */
110: protected int p = -1;
111:
112: /** Track the last mark() call result value for use in rewind(). */
113: protected int lastMarker;
114:
115: /** Stack of indexes used for push/pop calls */
116: protected int[] calls;
117:
118: /** Stack pointer for stack of indexes; -1 indicates empty. Points
119: * at next location to push a value.
120: */
121: protected int _sp = -1;
122:
123: /** During fillBuffer(), we can make a reverse index from a set
124: * of token types of interest to the list of indexes into the
125: * node stream. This lets us convert a node pointer to a
126: * stream index semi-efficiently for a list of interesting
127: * nodes such as function definition nodes (you'll want to seek
128: * to their bodies for an interpreter). Also useful for doing
129: * dynamic searches; i.e., go find me all PLUS nodes.
130: */
131: protected Map tokenTypeToStreamIndexesMap;
132:
133: /** If tokenTypesToReverseIndex set to INDEX_ALL then indexing
134: * occurs for all token types.
135: */
136: public static final Set INDEX_ALL = new HashSet();
137:
138: /** A set of token types user would like to index for faster lookup.
139: * If this is INDEX_ALL, then all token types are tracked. If null,
140: * then none are indexed.
141: */
142: protected Set tokenTypesToReverseIndex = null;
143:
144: public CommonTreeNodeStream(Object tree) {
145: this (new CommonTreeAdaptor(), tree);
146: }
147:
148: public CommonTreeNodeStream(TreeAdaptor adaptor, Object tree) {
149: this (adaptor, tree, DEFAULT_INITIAL_BUFFER_SIZE);
150: }
151:
152: public CommonTreeNodeStream(TreeAdaptor adaptor, Object tree,
153: int initialBufferSize) {
154: this .root = tree;
155: this .adaptor = adaptor;
156: nodes = new ArrayList(initialBufferSize);
157: down = adaptor.create(Token.DOWN, "DOWN");
158: up = adaptor.create(Token.UP, "UP");
159: eof = adaptor.create(Token.EOF, "EOF");
160: }
161:
162: /** Walk tree with depth-first-search and fill nodes buffer.
163: * Don't do DOWN, UP nodes if its a list (t is isNil).
164: */
165: protected void fillBuffer() {
166: fillBuffer(root);
167: //System.out.println("revIndex="+tokenTypeToStreamIndexesMap);
168: p = 0; // buffer of nodes intialized now
169: }
170:
171: protected void fillBuffer(Object t) {
172: boolean nil = adaptor.isNil(t);
173: if (!nil) {
174: nodes.add(t); // add this node
175: fillReverseIndex(t, nodes.size() - 1);
176: }
177: // add DOWN node if t has children
178: int n = adaptor.getChildCount(t);
179: if (!nil && n > 0) {
180: addNavigationNode(Token.DOWN);
181: }
182: // and now add all its children
183: for (int c = 0; c < n; c++) {
184: Object child = adaptor.getChild(t, c);
185: fillBuffer(child);
186: }
187: // add UP node if t has children
188: if (!nil && n > 0) {
189: addNavigationNode(Token.UP);
190: }
191: }
192:
193: /** Given a node, add this to the reverse index tokenTypeToStreamIndexesMap.
194: * You can override this method to alter how indexing occurs. The
195: * default is to create a
196: *
197: * Map<Integer token type,ArrayList<Integer stream index>>
198: *
199: * This data structure allows you to find all nodes with type INT in order.
200: *
201: * If you really need to find a node of type, say, FUNC quickly then perhaps
202: *
203: * Map<Integertoken type,Map<Object tree node,Integer stream index>>
204: *
205: * would be better for you. The interior maps map a tree node to
206: * the index so you don't have to search linearly for a specific node.
207: *
208: * If you change this method, you will likely need to change
209: * getNodeIndex(), which extracts information.
210: */
211: protected void fillReverseIndex(Object node, int streamIndex) {
212: //System.out.println("revIndex "+node+"@"+streamIndex);
213: if (tokenTypesToReverseIndex == null) {
214: return; // no indexing if this is empty (nothing of interest)
215: }
216: if (tokenTypeToStreamIndexesMap == null) {
217: tokenTypeToStreamIndexesMap = new HashMap(); // first indexing op
218: }
219: int tokenType = adaptor.getType(node);
220: Integer tokenTypeI = new Integer(tokenType);
221: if (!(tokenTypesToReverseIndex == INDEX_ALL || tokenTypesToReverseIndex
222: .contains(tokenTypeI))) {
223: return; // tokenType not of interest
224: }
225: Integer streamIndexI = new Integer(streamIndex);
226: ArrayList indexes = (ArrayList) tokenTypeToStreamIndexesMap
227: .get(tokenTypeI);
228: if (indexes == null) {
229: indexes = new ArrayList(); // no list yet for this token type
230: indexes.add(streamIndexI); // not there yet, add
231: tokenTypeToStreamIndexesMap.put(tokenTypeI, indexes);
232: } else {
233: if (!indexes.contains(streamIndexI)) {
234: indexes.add(streamIndexI); // not there yet, add
235: }
236: }
237: }
238:
239: /** Track the indicated token type in the reverse index. Call this
240: * repeatedly for each type or use variant with Set argument to
241: * set all at once.
242: * @param tokenType
243: */
244: public void reverseIndex(int tokenType) {
245: if (tokenTypesToReverseIndex == null) {
246: tokenTypesToReverseIndex = new HashSet();
247: } else if (tokenTypesToReverseIndex == INDEX_ALL) {
248: return;
249: }
250: tokenTypesToReverseIndex.add(new Integer(tokenType));
251: }
252:
253: /** Track the indicated token types in the reverse index. Set
254: * to INDEX_ALL to track all token types.
255: */
256: public void reverseIndex(Set tokenTypes) {
257: tokenTypesToReverseIndex = tokenTypes;
258: }
259:
260: /** Given a node pointer, return its index into the node stream.
261: * This is not its Token stream index. If there is no reverse map
262: * from node to stream index or the map does not contain entries
263: * for node's token type, a linear search of entire stream is used.
264: *
265: * Return -1 if exact node pointer not in stream.
266: */
267: public int getNodeIndex(Object node) {
268: //System.out.println("get "+node);
269: if (tokenTypeToStreamIndexesMap == null) {
270: return getNodeIndexLinearly(node);
271: }
272: int tokenType = adaptor.getType(node);
273: Integer tokenTypeI = new Integer(tokenType);
274: ArrayList indexes = (ArrayList) tokenTypeToStreamIndexesMap
275: .get(tokenTypeI);
276: if (indexes == null) {
277: //System.out.println("found linearly; stream index = "+getNodeIndexLinearly(node));
278: return getNodeIndexLinearly(node);
279: }
280: for (int i = 0; i < indexes.size(); i++) {
281: Integer streamIndexI = (Integer) indexes.get(i);
282: Object n = get(streamIndexI.intValue());
283: if (n == node) {
284: //System.out.println("found in index; stream index = "+streamIndexI);
285: return streamIndexI.intValue(); // found it!
286: }
287: }
288: return -1;
289: }
290:
291: protected int getNodeIndexLinearly(Object node) {
292: if (p == -1) {
293: fillBuffer();
294: }
295: for (int i = 0; i < nodes.size(); i++) {
296: Object t = (Object) nodes.get(i);
297: if (t == node) {
298: return i;
299: }
300: }
301: return -1;
302: }
303:
304: /** As we flatten the tree, we use UP, DOWN nodes to represent
305: * the tree structure. When debugging we need unique nodes
306: * so instantiate new ones when uniqueNavigationNodes is true.
307: */
308: protected void addNavigationNode(final int ttype) {
309: Object navNode = null;
310: if (ttype == Token.DOWN) {
311: if (hasUniqueNavigationNodes()) {
312: navNode = adaptor.create(Token.DOWN, "DOWN");
313: } else {
314: navNode = down;
315: }
316: } else {
317: if (hasUniqueNavigationNodes()) {
318: navNode = adaptor.create(Token.UP, "UP");
319: } else {
320: navNode = up;
321: }
322: }
323: nodes.add(navNode);
324: }
325:
326: public Object get(int i) {
327: if (p == -1) {
328: fillBuffer();
329: }
330: return nodes.get(i);
331: }
332:
333: public Object LT(int k) {
334: if (p == -1) {
335: fillBuffer();
336: }
337: if (k == 0) {
338: return null;
339: }
340: if (k < 0) {
341: return LB(-k);
342: }
343: //System.out.print("LT(p="+p+","+k+")=");
344: if ((p + k - 1) >= nodes.size()) {
345: return eof;
346: }
347: return nodes.get(p + k - 1);
348: }
349:
350: /*
351: public Object getLastTreeNode() {
352: int i = index();
353: if ( i>=size() ) {
354: i--; // if at EOF, have to start one back
355: }
356: System.out.println("start last node: "+i+" size=="+nodes.size());
357: while ( i>=0 &&
358: (adaptor.getType(get(i))==Token.EOF ||
359: adaptor.getType(get(i))==Token.UP ||
360: adaptor.getType(get(i))==Token.DOWN) )
361: {
362: i--;
363: }
364: System.out.println("stop at node: "+i+" "+nodes.get(i));
365: return nodes.get(i);
366: }
367: */
368:
369: /** Look backwards k nodes */
370: protected Object LB(int k) {
371: if (k == 0) {
372: return null;
373: }
374: if ((p - k) < 0) {
375: return null;
376: }
377: return nodes.get(p - k);
378: }
379:
380: public Object getTreeSource() {
381: return root;
382: }
383:
384: public TokenStream getTokenStream() {
385: return tokens;
386: }
387:
388: public void setTokenStream(TokenStream tokens) {
389: this .tokens = tokens;
390: }
391:
392: public TreeAdaptor getTreeAdaptor() {
393: return adaptor;
394: }
395:
396: public boolean hasUniqueNavigationNodes() {
397: return uniqueNavigationNodes;
398: }
399:
400: public void setUniqueNavigationNodes(boolean uniqueNavigationNodes) {
401: this .uniqueNavigationNodes = uniqueNavigationNodes;
402: }
403:
404: public void consume() {
405: if (p == -1) {
406: fillBuffer();
407: }
408: p++;
409: }
410:
411: public int LA(int i) {
412: return adaptor.getType(LT(i));
413: }
414:
415: public int mark() {
416: if (p == -1) {
417: fillBuffer();
418: }
419: lastMarker = index();
420: return lastMarker;
421: }
422:
423: public void release(int marker) {
424: // no resources to release
425: }
426:
427: public int index() {
428: return p;
429: }
430:
431: public void rewind(int marker) {
432: seek(marker);
433: }
434:
435: public void rewind() {
436: seek(lastMarker);
437: }
438:
439: public void seek(int index) {
440: if (p == -1) {
441: fillBuffer();
442: }
443: p = index;
444: }
445:
446: /** Make stream jump to a new location, saving old location.
447: * Switch back with pop(). I manage dyanmic array manually
448: * to avoid creating Integer objects all over the place.
449: */
450: public void push(int index) {
451: if (calls == null) {
452: calls = new int[INITIAL_CALL_STACK_SIZE];
453: } else if ((_sp + 1) >= calls.length) {
454: int[] newStack = new int[calls.length * 2];
455: System.arraycopy(calls, 0, newStack, 0, calls.length);
456: calls = newStack;
457: }
458: calls[++_sp] = p; // save current index
459: seek(index);
460: }
461:
462: /** Seek back to previous index saved during last push() call.
463: * Return top of stack (return index).
464: */
465: public int pop() {
466: int ret = calls[_sp--];
467: seek(ret);
468: return ret;
469: }
470:
471: public int size() {
472: if (p == -1) {
473: fillBuffer();
474: }
475: return nodes.size();
476: }
477:
478: public Iterator iterator() {
479: if (p == -1) {
480: fillBuffer();
481: }
482: return new StreamIterator();
483: }
484:
485: /** Used for testing, just return the token type stream */
486: public String toString() {
487: if (p == -1) {
488: fillBuffer();
489: }
490: StringBuffer buf = new StringBuffer();
491: for (int i = 0; i < nodes.size(); i++) {
492: Object t = (Object) nodes.get(i);
493: buf.append(" ");
494: buf.append(adaptor.getType(t));
495: }
496: return buf.toString();
497: }
498:
499: public String toString(Object start, Object stop) {
500: if (start == null || stop == null) {
501: return null;
502: }
503: if (p == -1) {
504: fillBuffer();
505: }
506: System.out.println("stop: " + stop);
507: if (start instanceof CommonTree)
508: System.out.print("toString: "
509: + ((CommonTree) start).getToken() + ", ");
510: else
511: System.out.println(start);
512: if (stop instanceof CommonTree)
513: System.out.println(((CommonTree) stop).getToken());
514: else
515: System.out.println(stop);
516: // if we have the token stream, use that to dump text in order
517: if (tokens != null) {
518: int beginTokenIndex = adaptor.getTokenStartIndex(start);
519: int endTokenIndex = adaptor.getTokenStopIndex(stop);
520: // if it's a tree, use start/stop index from start node
521: // else use token range from start/stop nodes
522: if (adaptor.getType(stop) == Token.UP) {
523: endTokenIndex = adaptor.getTokenStopIndex(start);
524: } else if (adaptor.getType(stop) == Token.EOF) {
525: endTokenIndex = size() - 2; // don't use EOF
526: }
527: return tokens.toString(beginTokenIndex, endTokenIndex);
528: }
529: // walk nodes looking for start
530: Object t = null;
531: int i = 0;
532: for (; i < nodes.size(); i++) {
533: t = nodes.get(i);
534: if (t == start) {
535: break;
536: }
537: }
538: // now walk until we see stop, filling string buffer with text
539: StringBuffer buf = new StringBuffer();
540: t = nodes.get(i);
541: while (t != stop) {
542: String text = adaptor.getText(t);
543: if (text == null) {
544: text = " " + String.valueOf(adaptor.getType(t));
545: }
546: buf.append(text);
547: i++;
548: t = nodes.get(i);
549: }
550: // include stop node too
551: String text = adaptor.getText(stop);
552: if (text == null) {
553: text = " " + String.valueOf(adaptor.getType(stop));
554: }
555: buf.append(text);
556: return buf.toString();
557: }
558: }
|