• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * [The "BSD licence"]
3  * Copyright (c) 2011 Terence Parr
4  * All rights reserved.
5  *
6  * Conversion to C#:
7  * Copyright (c) 2011 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 {
35     using System.Collections.Generic;
36 
37     using ArgumentNullException = System.ArgumentNullException;
38     using Exception = System.Exception;
39     using IDictionary = System.Collections.IDictionary;
40     using NotSupportedException = System.NotSupportedException;
41 
42     /** <summary>A TreeAdaptor that works with any Tree implementation.</summary> */
43     public abstract class BaseTreeAdaptor : ITreeAdaptor
44     {
45         /** <summary>
46          *  System.identityHashCode() is not always unique; we have to
47          *  track ourselves.  That's ok, it's only for debugging, though it's
48          *  expensive: we have to create a hashtable with all tree nodes in it.
49          *  </summary>
50          */
51         protected IDictionary<object, int> treeToUniqueIDMap;
52         protected int uniqueNodeID = 1;
53 
Nil()54         public virtual object Nil()
55         {
56             return Create( null );
57         }
58 
59         /** <summary>
60          *  Create tree node that holds the start and stop tokens associated
61          *  with an error.
62          *  </summary>
63          *
64          *  <remarks>
65          *  If you specify your own kind of tree nodes, you will likely have to
66          *  override this method. CommonTree returns Token.INVALID_TOKEN_TYPE
67          *  if no token payload but you might have to set token type for diff
68          *  node type.
69          *
70          *  You don't have to subclass CommonErrorNode; you will likely need to
71          *  subclass your own tree node class to avoid class cast exception.
72          *  </remarks>
73          */
ErrorNode( ITokenStream input, IToken start, IToken stop, RecognitionException e )74         public virtual object ErrorNode( ITokenStream input, IToken start, IToken stop,
75                                 RecognitionException e )
76         {
77             CommonErrorNode t = new CommonErrorNode( input, start, stop, e );
78             //System.out.println("returning error node '"+t+"' @index="+input.index());
79             return t;
80         }
81 
IsNil( object tree )82         public virtual bool IsNil( object tree )
83         {
84             return ( (ITree)tree ).IsNil;
85         }
86 
DupNode(int type, object treeNode)87         public virtual object DupNode(int type, object treeNode)
88         {
89             object t = DupNode(treeNode);
90             SetType(t, type);
91             return t;
92         }
93 
DupNode(object treeNode, string text)94         public virtual object DupNode(object treeNode, string text)
95         {
96             object t = DupNode(treeNode);
97             SetText(t, text);
98             return t;
99         }
100 
DupNode(int type, object treeNode, string text)101         public virtual object DupNode(int type, object treeNode, string text)
102         {
103             object t = DupNode(treeNode);
104             SetType(t, type);
105             SetText(t, text);
106             return t;
107         }
108 
DupTree( object tree )109         public virtual object DupTree( object tree )
110         {
111             return DupTree( tree, null );
112         }
113 
114         /** <summary>
115          *  This is generic in the sense that it will work with any kind of
116          *  tree (not just ITree interface).  It invokes the adaptor routines
117          *  not the tree node routines to do the construction.
118          *  </summary>
119          */
DupTree( object t, object parent )120         public virtual object DupTree( object t, object parent )
121         {
122             if ( t == null )
123             {
124                 return null;
125             }
126             object newTree = DupNode( t );
127             // ensure new subtree root has parent/child index set
128             SetChildIndex( newTree, GetChildIndex( t ) ); // same index in new tree
129             SetParent( newTree, parent );
130             int n = GetChildCount( t );
131             for ( int i = 0; i < n; i++ )
132             {
133                 object child = GetChild( t, i );
134                 object newSubTree = DupTree( child, t );
135                 AddChild( newTree, newSubTree );
136             }
137             return newTree;
138         }
139 
140         /** <summary>
141          *  Add a child to the tree t.  If child is a flat tree (a list), make all
142          *  in list children of t.  Warning: if t has no children, but child does
143          *  and child isNil then you can decide it is ok to move children to t via
144          *  t.children = child.children; i.e., without copying the array.  Just
145          *  make sure that this is consistent with have the user will build
146          *  ASTs.
147          *  </summary>
148          */
AddChild( object t, object child )149         public virtual void AddChild( object t, object child )
150         {
151             if ( t != null && child != null )
152             {
153                 ( (ITree)t ).AddChild( (ITree)child );
154             }
155         }
156 
157         /** <summary>
158          *  If oldRoot is a nil root, just copy or move the children to newRoot.
159          *  If not a nil root, make oldRoot a child of newRoot.
160          *  </summary>
161          *
162          *  <remarks>
163          *    old=^(nil a b c), new=r yields ^(r a b c)
164          *    old=^(a b c), new=r yields ^(r ^(a b c))
165          *
166          *  If newRoot is a nil-rooted single child tree, use the single
167          *  child as the new root node.
168          *
169          *    old=^(nil a b c), new=^(nil r) yields ^(r a b c)
170          *    old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
171          *
172          *  If oldRoot was null, it's ok, just return newRoot (even if isNil).
173          *
174          *    old=null, new=r yields r
175          *    old=null, new=^(nil r) yields ^(nil r)
176          *
177          *  Return newRoot.  Throw an exception if newRoot is not a
178          *  simple node or nil root with a single child node--it must be a root
179          *  node.  If newRoot is ^(nil x) return x as newRoot.
180          *
181          *  Be advised that it's ok for newRoot to point at oldRoot's
182          *  children; i.e., you don't have to copy the list.  We are
183          *  constructing these nodes so we should have this control for
184          *  efficiency.
185          *  </remarks>
186          */
BecomeRoot( object newRoot, object oldRoot )187         public virtual object BecomeRoot( object newRoot, object oldRoot )
188         {
189             //System.out.println("becomeroot new "+newRoot.toString()+" old "+oldRoot);
190             ITree newRootTree = (ITree)newRoot;
191             ITree oldRootTree = (ITree)oldRoot;
192             if ( oldRoot == null )
193             {
194                 return newRoot;
195             }
196             // handle ^(nil real-node)
197             if ( newRootTree.IsNil )
198             {
199                 int nc = newRootTree.ChildCount;
200                 if ( nc == 1 )
201                     newRootTree = (ITree)newRootTree.GetChild( 0 );
202                 else if ( nc > 1 )
203                 {
204                     // TODO: make tree run time exceptions hierarchy
205                     throw new Exception( "more than one node as root (TODO: make exception hierarchy)" );
206                 }
207             }
208             // add oldRoot to newRoot; addChild takes care of case where oldRoot
209             // is a flat list (i.e., nil-rooted tree).  All children of oldRoot
210             // are added to newRoot.
211             newRootTree.AddChild( oldRootTree );
212             return newRootTree;
213         }
214 
215         /** <summary>Transform ^(nil x) to x and nil to null</summary> */
RulePostProcessing( object root )216         public virtual object RulePostProcessing( object root )
217         {
218             //System.out.println("rulePostProcessing: "+((Tree)root).toStringTree());
219             ITree r = (ITree)root;
220             if ( r != null && r.IsNil )
221             {
222                 if ( r.ChildCount == 0 )
223                 {
224                     r = null;
225                 }
226                 else if ( r.ChildCount == 1 )
227                 {
228                     r = (ITree)r.GetChild( 0 );
229                     // whoever invokes rule will set parent and child index
230                     r.Parent = null;
231                     r.ChildIndex = -1;
232                 }
233             }
234             return r;
235         }
236 
BecomeRoot( IToken newRoot, object oldRoot )237         public virtual object BecomeRoot( IToken newRoot, object oldRoot )
238         {
239             return BecomeRoot( Create( newRoot ), oldRoot );
240         }
241 
Create( int tokenType, IToken fromToken )242         public virtual object Create( int tokenType, IToken fromToken )
243         {
244             fromToken = CreateToken( fromToken );
245             fromToken.Type = tokenType;
246             object t = Create( fromToken );
247             return t;
248         }
249 
Create( int tokenType, IToken fromToken, string text )250         public virtual object Create( int tokenType, IToken fromToken, string text )
251         {
252             if ( fromToken == null )
253                 return Create( tokenType, text );
254 
255             fromToken = CreateToken( fromToken );
256             fromToken.Type = tokenType;
257             fromToken.Text = text;
258             object result = Create(fromToken);
259             return result;
260         }
261 
Create(IToken fromToken, string text)262         public virtual object Create(IToken fromToken, string text)
263         {
264             if (fromToken == null)
265                 throw new ArgumentNullException("fromToken");
266 
267             fromToken = CreateToken(fromToken);
268             fromToken.Text = text;
269             object result = Create(fromToken);
270             return result;
271         }
272 
Create( int tokenType, string text )273         public virtual object Create( int tokenType, string text )
274         {
275             IToken fromToken = CreateToken( tokenType, text );
276             object t = Create( fromToken );
277             return t;
278         }
279 
GetType( object t )280         public virtual int GetType( object t )
281         {
282             ITree tree = GetTree(t);
283             if (tree == null)
284                 return TokenTypes.Invalid;
285 
286             return tree.Type;
287         }
288 
SetType( object t, int type )289         public virtual void SetType( object t, int type )
290         {
291             throw new NotSupportedException( "don't know enough about Tree node" );
292         }
293 
GetText( object t )294         public virtual string GetText( object t )
295         {
296             ITree tree = GetTree(t);
297             if (tree == null)
298                 return null;
299 
300             return tree.Text;
301         }
302 
SetText( object t, string text )303         public virtual void SetText( object t, string text )
304         {
305             throw new NotSupportedException( "don't know enough about Tree node" );
306         }
307 
GetChild( object t, int i )308         public virtual object GetChild( object t, int i )
309         {
310             ITree tree = GetTree(t);
311             if (tree == null)
312                 return null;
313 
314             return tree.GetChild(i);
315         }
316 
SetChild( object t, int i, object child )317         public virtual void SetChild( object t, int i, object child )
318         {
319             ITree tree = GetTree(t);
320             if (tree == null)
321                 return;
322 
323             ITree childTree = GetTree(child);
324             tree.SetChild(i, childTree);
325         }
326 
DeleteChild( object t, int i )327         public virtual object DeleteChild( object t, int i )
328         {
329             return ( (ITree)t ).DeleteChild( i );
330         }
331 
GetChildCount( object t )332         public virtual int GetChildCount( object t )
333         {
334             ITree tree = GetTree(t);
335             if (tree == null)
336                 return 0;
337 
338             return tree.ChildCount;
339         }
340 
GetUniqueID( object node )341         public virtual int GetUniqueID( object node )
342         {
343             if ( treeToUniqueIDMap == null )
344             {
345                 treeToUniqueIDMap = new Dictionary<object, int>();
346             }
347             int id;
348             if ( treeToUniqueIDMap.TryGetValue( node, out id ) )
349                 return id;
350 
351             id = uniqueNodeID;
352             treeToUniqueIDMap[node] = id;
353             uniqueNodeID++;
354             return id;
355             // GC makes these nonunique:
356             // return System.identityHashCode(node);
357         }
358 
359         /** <summary>
360          *  Tell me how to create a token for use with imaginary token nodes.
361          *  For example, there is probably no input symbol associated with imaginary
362          *  token DECL, but you need to create it as a payload or whatever for
363          *  the DECL node as in ^(DECL type ID).
364          *  </summary>
365          *
366          *  <remarks>
367          *  If you care what the token payload objects' type is, you should
368          *  override this method and any other createToken variant.
369          *  </remarks>
370          */
CreateToken( int tokenType, string text )371         public abstract IToken CreateToken( int tokenType, string text );
372 
373         /** <summary>
374          *  Tell me how to create a token for use with imaginary token nodes.
375          *  For example, there is probably no input symbol associated with imaginary
376          *  token DECL, but you need to create it as a payload or whatever for
377          *  the DECL node as in ^(DECL type ID).
378          *  </summary>
379          *
380          *  <remarks>
381          *  This is a variant of createToken where the new token is derived from
382          *  an actual real input token.  Typically this is for converting '{'
383          *  tokens to BLOCK etc...  You'll see
384          *
385          *    r : lc='{' ID+ '}' -> ^(BLOCK[$lc] ID+) ;
386          *
387          *  If you care what the token payload objects' type is, you should
388          *  override this method and any other createToken variant.
389          *  </remarks>
390          */
CreateToken( IToken fromToken )391         public abstract IToken CreateToken( IToken fromToken );
392 
Create( IToken payload )393         public abstract object Create( IToken payload );
394 
395         /** <summary>
396          *  Duplicate a node.  This is part of the factory;
397          *  override if you want another kind of node to be built.
398          *  </summary>
399          *
400          *  <remarks>
401          *  I could use reflection to prevent having to override this
402          *  but reflection is slow.
403          *  </remarks>
404          */
DupNode(object treeNode)405         public virtual object DupNode(object treeNode)
406         {
407             ITree tree = GetTree(treeNode);
408             if (tree == null)
409                 return null;
410 
411             return tree.DupNode();
412         }
413 
GetToken( object t )414         public abstract IToken GetToken( object t );
415 
416         /** <summary>
417          *  Track start/stop token for subtree root created for a rule.
418          *  Only works with Tree nodes.  For rules that match nothing,
419          *  seems like this will yield start=i and stop=i-1 in a nil node.
420          *  Might be useful info so I'll not force to be i..i.
421          *  </summary>
422          */
SetTokenBoundaries(object t, IToken startToken, IToken stopToken)423         public virtual void SetTokenBoundaries(object t, IToken startToken, IToken stopToken)
424         {
425             ITree tree = GetTree(t);
426             if (tree == null)
427                 return;
428 
429             int start = 0;
430             int stop = 0;
431 
432             if (startToken != null)
433                 start = startToken.TokenIndex;
434             if (stopToken != null)
435                 stop = stopToken.TokenIndex;
436 
437             tree.TokenStartIndex = start;
438             tree.TokenStopIndex = stop;
439         }
440 
GetTokenStartIndex(object t)441         public virtual int GetTokenStartIndex(object t)
442         {
443             ITree tree = GetTree(t);
444             if (tree == null)
445                 return -1;
446 
447             return tree.TokenStartIndex;
448         }
449 
GetTokenStopIndex(object t)450         public virtual int GetTokenStopIndex(object t)
451         {
452             ITree tree = GetTree(t);
453             if (tree == null)
454                 return -1;
455 
456             return tree.TokenStopIndex;
457         }
458 
GetParent(object t)459         public virtual object GetParent(object t)
460         {
461             ITree tree = GetTree(t);
462             if (tree == null)
463                 return null;
464 
465             return tree.Parent;
466         }
467 
SetParent(object t, object parent)468         public virtual void SetParent(object t, object parent)
469         {
470             ITree tree = GetTree(t);
471             if (tree == null)
472                 return;
473 
474             ITree parentTree = GetTree(parent);
475             tree.Parent = parentTree;
476         }
477 
GetChildIndex(object t)478         public virtual int GetChildIndex(object t)
479         {
480             ITree tree = GetTree(t);
481             if (tree == null)
482                 return 0;
483 
484             return tree.ChildIndex;
485         }
486 
SetChildIndex(object t, int index)487         public virtual void SetChildIndex(object t, int index)
488         {
489             ITree tree = GetTree(t);
490             if (tree == null)
491                 return;
492 
493             tree.ChildIndex = index;
494         }
495 
ReplaceChildren(object parent, int startChildIndex, int stopChildIndex, object t)496         public virtual void ReplaceChildren(object parent, int startChildIndex, int stopChildIndex, object t)
497         {
498             ITree tree = GetTree(parent);
499             if (tree == null)
500                 return;
501 
502             tree.ReplaceChildren(startChildIndex, stopChildIndex, t);
503         }
504 
GetTree(object t)505         protected virtual ITree GetTree(object t)
506         {
507             if (t == null)
508                 return null;
509 
510             ITree tree = t as ITree;
511             if (tree == null)
512                 throw new NotSupportedException();
513 
514             return tree;
515         }
516     }
517 }
518