13447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein/* 23447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein [The "BSD license"] 33447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Copyright (c) 2005-2009 Terence Parr 43447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein All rights reserved. 53447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 63447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Redistribution and use in source and binary forms, with or without 73447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein modification, are permitted provided that the following conditions 83447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein are met: 93447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1. Redistributions of source code must retain the above copyright 103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer. 113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 2. Redistributions in binary form must reproduce the above copyright 123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein notice, this list of conditions and the following disclaimer in the 133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein documentation and/or other materials provided with the distribution. 143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 3. The name of the author may not be used to endorse or promote products 153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein derived from this software without specific prior written permission. 163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpackage org.antlr.runtime.tree; 293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport org.antlr.runtime.Token; 313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport org.antlr.runtime.TokenStream; 323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport org.antlr.runtime.misc.LookaheadStream; 333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport org.antlr.runtime.misc.IntArray; 343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinimport java.util.*; 363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sappersteinpublic class CommonTreeNodeStream extends LookaheadStream<Object> implements TreeNodeStream { 383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static final int DEFAULT_INITIAL_BUFFER_SIZE = 100; 393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public static final int INITIAL_CALL_STACK_SIZE = 10; 403447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Pull nodes from which tree? */ 423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected Object root; 433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** If this tree (root) was created from a token stream, track it. */ 453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected TokenStream tokens; 463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** What tree adaptor was used to build these trees */ 483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein TreeAdaptor adaptor; 493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** The tree iterator we using */ 513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected TreeIterator it; 523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Stack of indexes used for push/pop calls */ 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected IntArray calls; 553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Tree (nil A B C) trees like flat A B C streams */ 573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected boolean hasNilRoot = false; 583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Tracks tree depth. Level=0 means we're at root node level. */ 603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein protected int level = 0; 613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public CommonTreeNodeStream(Object tree) { 633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this(new CommonTreeAdaptor(), tree); 643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public CommonTreeNodeStream(TreeAdaptor adaptor, Object tree) { 673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this.root = tree; 683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein this.adaptor = adaptor; 693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein it = new TreeIterator(adaptor,root); 703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 723447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void reset() { 733447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein super.reset(); 743447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein it.reset(); 753447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein hasNilRoot = false; 763447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein level = 0; 773447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( calls != null ) calls.clear(); 783447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 803447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Pull elements from tree iterator. Track tree level 0..max_level. 813447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * If nil rooted tree, don't give initial nil and DOWN nor final UP. 823447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 833447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object nextElement() { 843447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Object t = it.next(); 853447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein //System.out.println("pulled "+adaptor.getType(t)); 863447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( t == it.up ) { 873447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein level--; 883447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( level==0 && hasNilRoot ) return it.next(); // don't give last UP; get EOF 893447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 903447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein else if ( t == it.down ) level++; 913447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( level==0 && adaptor.isNil(t) ) { // if nil root, scarf nil, DOWN 923447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein hasNilRoot = true; 933447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein t = it.next(); // t is now DOWN, so get first real node next 943447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein level++; 953447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein t = it.next(); 963447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 973447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return t; 983447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 993447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1003447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public boolean isEOF(Object o) { return adaptor.getType(o) == Token.EOF; } 1013447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1023447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void setUniqueNavigationNodes(boolean uniqueNavigationNodes) { } 1033447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1043447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object getTreeSource() { return root; } 1053447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1063447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public String getSourceName() { return getTokenStream().getSourceName(); } 1073447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1083447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public TokenStream getTokenStream() { return tokens; } 1093447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1103447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void setTokenStream(TokenStream tokens) { this.tokens = tokens; } 1113447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1123447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public TreeAdaptor getTreeAdaptor() { return adaptor; } 1133447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1143447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void setTreeAdaptor(TreeAdaptor adaptor) { this.adaptor = adaptor; } 1153447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1163447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public Object get(int i) { 1173447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein throw new UnsupportedOperationException("Absolute node indexes are meaningless in an unbuffered stream"); 1183447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1193447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1203447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int LA(int i) { return adaptor.getType(LT(i)); } 1213447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1223447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Make stream jump to a new location, saving old location. 1233447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Switch back with pop(). 1243447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 1253447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void push(int index) { 1263447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( calls==null ) { 1273447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein calls = new IntArray(); 1283447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1293447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein calls.push(p); // save current index 1303447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein seek(index); 1313447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1323447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1333447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** Seek back to previous index saved during last push() call. 1343447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein * Return top of stack (return index). 1353447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein */ 1363447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public int pop() { 1373447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int ret = calls.pop(); 1383447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein seek(ret); 1393447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return ret; 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 1413447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1423447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // TREE REWRITE INTERFACE 1433447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1443447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public void replaceChildren(Object parent, int startChildIndex, int stopChildIndex, Object t) { 1453447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein if ( parent!=null ) { 1463447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein adaptor.replaceChildren(parent, startChildIndex, stopChildIndex, t); 1473447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1483447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1493447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1503447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public String toString(Object start, Object stop) { 1513447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // we'll have to walk from start to stop in tree; we're not keeping 1523447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein // a complete node stream buffer 1533447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return "n/a"; 1543447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1553447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein 1563447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein /** For debugging; destructive: moves tree iterator to end. */ 1573447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein public String toTokenTypeString() { 1583447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein reset(); 1593447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein StringBuffer buf = new StringBuffer(); 1603447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein Object o = LT(1); 1613447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein int type = adaptor.getType(o); 1623447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein while ( type!=Token.EOF ) { 1633447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein buf.append(" "); 1643447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein buf.append(type); 1653447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein consume(); 1663447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein o = LT(1); 1673447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein type = adaptor.getType(o); 1683447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1693447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein return buf.toString(); 1703447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein } 1713447a5916aa62f44de24cc441fc9987116ddff52Andrew Sapperstein} 172