• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * [The "BSD licence"]
3  * Copyright (c) 2005-2008 Terence Parr
4  * All rights reserved.
5  *
6  * Conversion to C#:
7  * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc.
8  * All rights reserved.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  * 3. The name of the author may not be used to endorse or promote products
19  *    derived from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
23  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
24  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
26  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
30  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31  */
32 
33 namespace Antlr.Runtime.Tree {
34     using System.Collections.Generic;
35 
36     using Console = System.Console;
37     using IList = System.Collections.IList;
38     using InvalidOperationException = System.InvalidOperationException;
39     using StringBuilder = System.Text.StringBuilder;
40 
41     /** <summary>A buffered stream of tree nodes.  Nodes can be from a tree of ANY kind.</summary>
42      *
43      *  This node stream sucks all nodes out of the tree specified in
44      *  the constructor during construction and makes pointers into
45      *  the tree using an array of Object pointers. The stream necessarily
46      *  includes pointers to DOWN and UP and EOF nodes.
47      *
48      *  This stream knows how to mark/release for backtracking.
49      *
50      *  This stream is most suitable for tree interpreters that need to
51      *  jump around a lot or for tree parsers requiring speed (at cost of memory).
52      *  There is some duplicated functionality here with UnBufferedTreeNodeStream
53      *  but just in bookkeeping, not tree walking etc...
54      *
55      *  TARGET DEVELOPERS:
56      *
57      *  This is the old CommonTreeNodeStream that buffered up entire node stream.
58      *  No need to implement really as new CommonTreeNodeStream is much better
59      *  and covers what we need.
60      *
61      *  @see CommonTreeNodeStream
62      */
63     public class BufferedTreeNodeStream : ITreeNodeStream, ITokenStreamInformation {
64         public const int DEFAULT_INITIAL_BUFFER_SIZE = 100;
65         public const int INITIAL_CALL_STACK_SIZE = 10;
66 
67         protected sealed class StreamIterator : IEnumerator<object> {
68             BufferedTreeNodeStream _outer;
69             int _index;
70 
StreamIterator(BufferedTreeNodeStream outer)71             public StreamIterator(BufferedTreeNodeStream outer) {
72                 _outer = outer;
73                 _index = -1;
74             }
75 
76             #region IEnumerator<object> Members
77 
78             public object Current {
79                 get {
80                     if (_index < _outer.nodes.Count)
81                         return _outer.nodes[_index];
82 
83                     return _outer.eof;
84                 }
85             }
86 
87             #endregion
88 
89             #region IDisposable Members
90 
Dispose()91             public void Dispose() {
92             }
93 
94             #endregion
95 
96             #region IEnumerator Members
97 
MoveNext()98             public bool MoveNext() {
99                 if (_index < _outer.nodes.Count)
100                     _index++;
101 
102                 return _index < _outer.nodes.Count;
103             }
104 
Reset()105             public void Reset() {
106                 _index = -1;
107             }
108 
109             #endregion
110         }
111 
112         // all these navigation nodes are shared and hence they
113         // cannot contain any line/column info
114 
115         protected object down;
116         protected object up;
117         protected object eof;
118 
119         /** <summary>The complete mapping from stream index to tree node.
120          *  This buffer includes pointers to DOWN, UP, and EOF nodes.
121          *  It is built upon ctor invocation.  The elements are type
122          *  Object as we don't what the trees look like.</summary>
123          *
124          *  Load upon first need of the buffer so we can set token types
125          *  of interest for reverseIndexing.  Slows us down a wee bit to
126          *  do all of the if p==-1 testing everywhere though.
127          */
128         protected IList nodes;
129 
130         /** <summary>Pull nodes from which tree?</summary> */
131         protected object root;
132 
133         /** <summary>IF this tree (root) was created from a token stream, track it.</summary> */
134         protected ITokenStream tokens;
135 
136         /** <summary>What tree adaptor was used to build these trees</summary> */
137         ITreeAdaptor adaptor;
138 
139         /** <summary>Reuse same DOWN, UP navigation nodes unless this is true</summary> */
140         bool uniqueNavigationNodes = false;
141 
142         /** <summary>The index into the nodes list of the current node (next node
143          *  to consume).  If -1, nodes array not filled yet.</summary>
144          */
145         protected int p = -1;
146 
147         /** <summary>Track the last mark() call result value for use in rewind().</summary> */
148         protected int lastMarker;
149 
150         /** <summary>Stack of indexes used for push/pop calls</summary> */
151         protected Stack<int> calls;
152 
BufferedTreeNodeStream(object tree)153         public BufferedTreeNodeStream(object tree)
154             : this(new CommonTreeAdaptor(), tree) {
155         }
156 
BufferedTreeNodeStream(ITreeAdaptor adaptor, object tree)157         public BufferedTreeNodeStream(ITreeAdaptor adaptor, object tree)
158             : this(adaptor, tree, DEFAULT_INITIAL_BUFFER_SIZE) {
159         }
160 
BufferedTreeNodeStream(ITreeAdaptor adaptor, object tree, int initialBufferSize)161         public BufferedTreeNodeStream(ITreeAdaptor adaptor, object tree, int initialBufferSize) {
162             this.root = tree;
163             this.adaptor = adaptor;
164             nodes = new List<object>(initialBufferSize);
165             down = adaptor.Create(TokenTypes.Down, "DOWN");
166             up = adaptor.Create(TokenTypes.Up, "UP");
167             eof = adaptor.Create(TokenTypes.EndOfFile, "EOF");
168         }
169 
170         #region Properties
171 
172         public virtual int Count {
173             get {
174                 if (p == -1) {
175                     throw new InvalidOperationException("Cannot determine the Count before the buffer is filled.");
176                 }
177                 return nodes.Count;
178             }
179         }
180 
181         public virtual object TreeSource {
182             get {
183                 return root;
184             }
185         }
186 
187         public virtual string SourceName {
188             get {
189                 return TokenStream.SourceName;
190             }
191         }
192 
193         public virtual ITokenStream TokenStream {
194             get {
195                 return tokens;
196             }
197             set {
198                 tokens = value;
199             }
200         }
201 
202         public virtual ITreeAdaptor TreeAdaptor {
203             get {
204                 return adaptor;
205             }
206             set {
207                 adaptor = value;
208             }
209         }
210 
211         public virtual bool UniqueNavigationNodes {
212             get {
213                 return uniqueNavigationNodes;
214             }
215             set {
216                 uniqueNavigationNodes = value;
217             }
218         }
219 
220         public virtual IToken LastToken {
221             get {
222                 return TreeAdaptor.GetToken(LB(1));
223             }
224         }
225 
226         public virtual IToken LastRealToken {
227             get {
228                 int i = 0;
229                 IToken token;
230                 do {
231                     i++;
232                     token = TreeAdaptor.GetToken(LB(i));
233                 } while (token != null && token.Line <= 0);
234 
235                 return token;
236             }
237         }
238 
239         public virtual int MaxLookBehind {
240             get {
241                 return int.MaxValue;
242             }
243         }
244 
245         #endregion
246 
247         /** Walk tree with depth-first-search and fill nodes buffer.
248          *  Don't do DOWN, UP nodes if its a list (t is isNil).
249          */
FillBuffer()250         protected virtual void FillBuffer() {
251             FillBuffer(root);
252             //Console.Out.WriteLine( "revIndex=" + tokenTypeToStreamIndexesMap );
253             p = 0; // buffer of nodes intialized now
254         }
255 
FillBuffer(object t)256         public virtual void FillBuffer(object t) {
257             bool nil = adaptor.IsNil(t);
258             if (!nil) {
259                 nodes.Add(t); // add this node
260             }
261             // add DOWN node if t has children
262             int n = adaptor.GetChildCount(t);
263             if (!nil && n > 0) {
264                 AddNavigationNode(TokenTypes.Down);
265             }
266             // and now add all its children
267             for (int c = 0; c < n; c++) {
268                 object child = adaptor.GetChild(t, c);
269                 FillBuffer(child);
270             }
271             // add UP node if t has children
272             if (!nil && n > 0) {
273                 AddNavigationNode(TokenTypes.Up);
274             }
275         }
276 
277         /** What is the stream index for node? 0..n-1
278          *  Return -1 if node not found.
279          */
GetNodeIndex(object node)280         protected virtual int GetNodeIndex(object node) {
281             if (p == -1) {
282                 FillBuffer();
283             }
284             for (int i = 0; i < nodes.Count; i++) {
285                 object t = nodes[i];
286                 if (t == node) {
287                     return i;
288                 }
289             }
290             return -1;
291         }
292 
293         /** As we flatten the tree, we use UP, DOWN nodes to represent
294          *  the tree structure.  When debugging we need unique nodes
295          *  so instantiate new ones when uniqueNavigationNodes is true.
296          */
AddNavigationNode(int ttype)297         protected virtual void AddNavigationNode(int ttype) {
298             object navNode = null;
299             if (ttype == TokenTypes.Down) {
300                 if (UniqueNavigationNodes) {
301                     navNode = adaptor.Create(TokenTypes.Down, "DOWN");
302                 } else {
303                     navNode = down;
304                 }
305             } else {
306                 if (UniqueNavigationNodes) {
307                     navNode = adaptor.Create(TokenTypes.Up, "UP");
308                 } else {
309                     navNode = up;
310                 }
311             }
312             nodes.Add(navNode);
313         }
314 
315         public virtual object this[int i] {
316             get {
317                 if (p == -1) {
318                     throw new InvalidOperationException("Cannot get the node at index i before the buffer is filled.");
319                 }
320                 return nodes[i];
321             }
322         }
323 
LT(int k)324         public virtual object LT(int k) {
325             if (p == -1) {
326                 FillBuffer();
327             }
328             if (k == 0) {
329                 return null;
330             }
331             if (k < 0) {
332                 return LB(-k);
333             }
334             //System.out.print("LT(p="+p+","+k+")=");
335             if ((p + k - 1) >= nodes.Count) {
336                 return eof;
337             }
338             return nodes[p + k - 1];
339         }
340 
GetCurrentSymbol()341         public virtual object GetCurrentSymbol() {
342             return LT(1);
343         }
344 
345 #if false
getLastTreeNode()346         public virtual object getLastTreeNode()
347         {
348             int i = Index;
349             if ( i >= size() )
350             {
351                 i--; // if at EOF, have to start one back
352             }
353             Console.Out.WriteLine( "start last node: " + i + " size==" + nodes.Count );
354             while ( i >= 0 &&
355                 ( adaptor.getType( this[i] ) == TokenTypes.EOF ||
356                  adaptor.getType( this[i] ) == TokenTypes.UP ||
357                  adaptor.getType( this[i] ) == TokenTypes.DOWN ) )
358             {
359                 i--;
360             }
361             Console.Out.WriteLine( "stop at node: " + i + " " + nodes[i] );
362             return nodes[i];
363         }
364 #endif
365 
366         /** <summary>Look backwards k nodes</summary> */
LB(int k)367         protected virtual object LB(int k) {
368             if (k == 0) {
369                 return null;
370             }
371             if ((p - k) < 0) {
372                 return null;
373             }
374             return nodes[p - k];
375         }
376 
Consume()377         public virtual void Consume() {
378             if (p == -1) {
379                 FillBuffer();
380             }
381             p++;
382         }
383 
LA(int i)384         public virtual int LA(int i) {
385             return adaptor.GetType(LT(i));
386         }
387 
Mark()388         public virtual int Mark() {
389             if (p == -1) {
390                 FillBuffer();
391             }
392             lastMarker = Index;
393             return lastMarker;
394         }
395 
Release(int marker)396         public virtual void Release(int marker) {
397             // no resources to release
398         }
399 
400         public virtual int Index {
401             get {
402                 return p;
403             }
404         }
405 
Rewind(int marker)406         public virtual void Rewind(int marker) {
407             Seek(marker);
408         }
409 
Rewind()410         public virtual void Rewind() {
411             Seek(lastMarker);
412         }
413 
Seek(int index)414         public virtual void Seek(int index) {
415             if (p == -1) {
416                 FillBuffer();
417             }
418             p = index;
419         }
420 
421         /** <summary>
422          *  Make stream jump to a new location, saving old location.
423          *  Switch back with pop().
424          *  </summary>
425          */
Push(int index)426         public virtual void Push(int index) {
427             if (calls == null) {
428                 calls = new Stack<int>();
429             }
430             calls.Push(p); // save current index
431             Seek(index);
432         }
433 
434         /** <summary>
435          *  Seek back to previous index saved during last push() call.
436          *  Return top of stack (return index).
437          *  </summary>
438          */
Pop()439         public virtual int Pop() {
440             int ret = calls.Pop();
441             Seek(ret);
442             return ret;
443         }
444 
Reset()445         public virtual void Reset() {
446             p = 0;
447             lastMarker = 0;
448             if (calls != null) {
449                 calls.Clear();
450             }
451         }
452 
Iterator()453         public virtual IEnumerator<object> Iterator() {
454             if (p == -1) {
455                 FillBuffer();
456             }
457 
458             return new StreamIterator(this);
459         }
460 
461         // TREE REWRITE INTERFACE
462 
ReplaceChildren(object parent, int startChildIndex, int stopChildIndex, object t)463         public virtual void ReplaceChildren(object parent, int startChildIndex, int stopChildIndex, object t) {
464             if (parent != null) {
465                 adaptor.ReplaceChildren(parent, startChildIndex, stopChildIndex, t);
466             }
467         }
468 
469         /** <summary>Used for testing, just return the token type stream</summary> */
ToTokenTypeString()470         public virtual string ToTokenTypeString() {
471             if (p == -1) {
472                 FillBuffer();
473             }
474             StringBuilder buf = new StringBuilder();
475             for (int i = 0; i < nodes.Count; i++) {
476                 object t = nodes[i];
477                 buf.Append(" ");
478                 buf.Append(adaptor.GetType(t));
479             }
480             return buf.ToString();
481         }
482 
483         /** <summary>Debugging</summary> */
ToTokenString(int start, int stop)484         public virtual string ToTokenString(int start, int stop) {
485             if (p == -1) {
486                 FillBuffer();
487             }
488             StringBuilder buf = new StringBuilder();
489             for (int i = start; i < nodes.Count && i <= stop; i++) {
490                 object t = nodes[i];
491                 buf.Append(" ");
492                 buf.Append(adaptor.GetToken(t));
493             }
494             return buf.ToString();
495         }
496 
ToString(object start, object stop)497         public virtual string ToString(object start, object stop) {
498             Console.Out.WriteLine("toString");
499             if (start == null || stop == null) {
500                 return null;
501             }
502             if (p == -1) {
503                 throw new InvalidOperationException("Buffer is not yet filled.");
504             }
505             //Console.Out.WriteLine( "stop: " + stop );
506             if (start is CommonTree)
507                 Console.Out.Write("toString: " + ((CommonTree)start).Token + ", ");
508             else
509                 Console.Out.WriteLine(start);
510             if (stop is CommonTree)
511                 Console.Out.WriteLine(((CommonTree)stop).Token);
512             else
513                 Console.Out.WriteLine(stop);
514             // if we have the token stream, use that to dump text in order
515             if (tokens != null) {
516                 int beginTokenIndex = adaptor.GetTokenStartIndex(start);
517                 int endTokenIndex = adaptor.GetTokenStopIndex(stop);
518                 // if it's a tree, use start/stop index from start node
519                 // else use token range from start/stop nodes
520                 if (adaptor.GetType(stop) == TokenTypes.Up) {
521                     endTokenIndex = adaptor.GetTokenStopIndex(start);
522                 } else if (adaptor.GetType(stop) == TokenTypes.EndOfFile) {
523                     endTokenIndex = Count - 2; // don't use EOF
524                 }
525                 return tokens.ToString(beginTokenIndex, endTokenIndex);
526             }
527             // walk nodes looking for start
528             object t = null;
529             int i = 0;
530             for (; i < nodes.Count; i++) {
531                 t = nodes[i];
532                 if (t == start) {
533                     break;
534                 }
535             }
536             // now walk until we see stop, filling string buffer with text
537             StringBuilder buf = new StringBuilder();
538             t = nodes[i];
539             while (t != stop) {
540                 string text = adaptor.GetText(t);
541                 if (text == null) {
542                     text = " " + adaptor.GetType(t).ToString();
543                 }
544                 buf.Append(text);
545                 i++;
546                 t = nodes[i];
547             }
548             // include stop node too
549             string text2 = adaptor.GetText(stop);
550             if (text2 == null) {
551                 text2 = " " + adaptor.GetType(stop).ToString();
552             }
553             buf.Append(text2);
554             return buf.ToString();
555         }
556     }
557 }
558