1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [The "BSD licence"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2005-2008 Terence Parr 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Conversion to C#: 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc. 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Redistribution and use in source and binary forms, with or without 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * modification, are permitted provided that the following conditions 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * are met: 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1. Redistributions of source code must retain the above copyright 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer. 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 2. Redistributions in binary form must reproduce the above copyright 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer in the 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * documentation and/or other materials provided with the distribution. 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 3. The name of the author may not be used to endorse or promote products 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * derived from this software without specific prior written permission. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvernamespace Antlr.Runtime.Tree { 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver using System.Collections.Generic; 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver using Antlr.Runtime.Misc; 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver using StringBuilder = System.Text.StringBuilder; 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver using NotSupportedException = System.NotSupportedException; 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver [System.Serializable] 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public class CommonTreeNodeStream : LookaheadStream<object>, ITreeNodeStream { 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public const int DEFAULT_INITIAL_BUFFER_SIZE = 100; 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public const int INITIAL_CALL_STACK_SIZE = 10; 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Pull nodes from which tree?</summary> */ 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver object _root; 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>If this tree (root) was created from a token stream, track it.</summary> */ 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected ITokenStream tokens; 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>What tree adaptor was used to build these trees</summary> */ 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver [System.NonSerialized] 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ITreeAdaptor _adaptor; 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** The tree iterator we are using */ 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreeIterator _it; 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Stack of indexes used for push/pop calls</summary> */ 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Stack<int> _calls; 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Tree (nil A B C) trees like flat A B C streams</summary> */ 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bool _hasNilRoot = false; 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Tracks tree depth. Level=0 means we're at root node level.</summary> */ 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int _level = 0; 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public CommonTreeNodeStream(object tree) 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : this(new CommonTreeAdaptor(), tree) { 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public CommonTreeNodeStream(ITreeAdaptor adaptor, object tree) { 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this._root = tree; 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this._adaptor = adaptor; 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _it = new TreeIterator(adaptor, _root); 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #region Properties 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual string SourceName { 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get { 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (TokenStream == null) 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return TokenStream.SourceName; 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual ITokenStream TokenStream { 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get { 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return tokens; 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver set { 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tokens = value; 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual ITreeAdaptor TreeAdaptor { 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get { 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return _adaptor; 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver set { 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _adaptor = value; 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual object TreeSource { 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get { 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return _root; 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual bool UniqueNavigationNodes { 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get { 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver set { 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #endregion 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void Reset() { 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver base.Clear(); 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _it.Reset(); 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _hasNilRoot = false; 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _level = 0; 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (_calls != null) 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _calls.Clear(); 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public override object NextElement() { 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _it.MoveNext(); 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver object t = _it.Current; 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("pulled "+adaptor.getType(t)); 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (t == _it.up) { 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _level--; 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (_level == 0 && _hasNilRoot) { 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _it.MoveNext(); 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return _it.Current; // don't give last UP; get EOF 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } else if (t == _it.down) { 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _level++; 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (_level == 0 && TreeAdaptor.IsNil(t)) { 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if nil root, scarf nil, DOWN 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _hasNilRoot = true; 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _it.MoveNext(); 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t = _it.Current; // t is now DOWN, so get first real node next 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _level++; 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _it.MoveNext(); 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t = _it.Current; 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return t; 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public override bool IsEndOfFile(object o) { 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return TreeAdaptor.GetType(o) == CharStreamConstants.EndOfFile; 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual int LA(int i) { 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return TreeAdaptor.GetType(LT(i)); 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Make stream jump to a new location, saving old location. 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Switch back with pop(). 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void Push(int index) { 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (_calls == null) { 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _calls = new Stack<int>(); 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _calls.Push(_p); // save current index 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Seek(index); 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Seek back to previous index saved during last push() call. 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Return top of stack (return index). 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual int Pop() { 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int ret = _calls.Pop(); 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Seek(ret); 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ret; 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #region Tree rewrite interface 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void ReplaceChildren(object parent, int startChildIndex, int stopChildIndex, object t) { 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (parent != null) { 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver TreeAdaptor.ReplaceChildren(parent, startChildIndex, stopChildIndex, t); 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #endregion 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual string ToString(object start, object stop) { 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // we'll have to walk from start to stop in tree; we're not keeping 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // a complete node stream buffer 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return "n/a"; 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>For debugging; destructive: moves tree iterator to end.</summary> */ 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual string ToTokenTypeString() { 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Reset(); 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver StringBuilder buf = new StringBuilder(); 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver object o = LT(1); 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int type = TreeAdaptor.GetType(o); 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while (type != TokenTypes.EndOfFile) { 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.Append(" "); 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.Append(type); 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Consume(); 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver o = LT(1); 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver type = TreeAdaptor.GetType(o); 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return buf.ToString(); 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 221