| /* |
| * [The "BSD licence"] |
| * Copyright (c) 2011 Terence Parr |
| * All rights reserved. |
| * |
| * Conversion to C#: |
| * Copyright (c) 2011 Sam Harwell, Pixel Mine, Inc. |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * 3. The name of the author may not be used to endorse or promote products |
| * derived from this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| namespace Antlr.Runtime.Tree |
| { |
| using System.Collections.Generic; |
| |
| using ArgumentNullException = System.ArgumentNullException; |
| using Exception = System.Exception; |
| using IDictionary = System.Collections.IDictionary; |
| using NotSupportedException = System.NotSupportedException; |
| |
| /** <summary>A TreeAdaptor that works with any Tree implementation.</summary> */ |
| public abstract class BaseTreeAdaptor : ITreeAdaptor |
| { |
| /** <summary> |
| * System.identityHashCode() is not always unique; we have to |
| * track ourselves. That's ok, it's only for debugging, though it's |
| * expensive: we have to create a hashtable with all tree nodes in it. |
| * </summary> |
| */ |
| protected IDictionary<object, int> treeToUniqueIDMap; |
| protected int uniqueNodeID = 1; |
| |
| public virtual object Nil() |
| { |
| return Create( null ); |
| } |
| |
| /** <summary> |
| * Create tree node that holds the start and stop tokens associated |
| * with an error. |
| * </summary> |
| * |
| * <remarks> |
| * If you specify your own kind of tree nodes, you will likely have to |
| * override this method. CommonTree returns Token.INVALID_TOKEN_TYPE |
| * if no token payload but you might have to set token type for diff |
| * node type. |
| * |
| * You don't have to subclass CommonErrorNode; you will likely need to |
| * subclass your own tree node class to avoid class cast exception. |
| * </remarks> |
| */ |
| public virtual object ErrorNode( ITokenStream input, IToken start, IToken stop, |
| RecognitionException e ) |
| { |
| CommonErrorNode t = new CommonErrorNode( input, start, stop, e ); |
| //System.out.println("returning error node '"+t+"' @index="+input.index()); |
| return t; |
| } |
| |
| public virtual bool IsNil( object tree ) |
| { |
| return ( (ITree)tree ).IsNil; |
| } |
| |
| public virtual object DupNode(int type, object treeNode) |
| { |
| object t = DupNode(treeNode); |
| SetType(t, type); |
| return t; |
| } |
| |
| public virtual object DupNode(object treeNode, string text) |
| { |
| object t = DupNode(treeNode); |
| SetText(t, text); |
| return t; |
| } |
| |
| public virtual object DupNode(int type, object treeNode, string text) |
| { |
| object t = DupNode(treeNode); |
| SetType(t, type); |
| SetText(t, text); |
| return t; |
| } |
| |
| public virtual object DupTree( object tree ) |
| { |
| return DupTree( tree, null ); |
| } |
| |
| /** <summary> |
| * This is generic in the sense that it will work with any kind of |
| * tree (not just ITree interface). It invokes the adaptor routines |
| * not the tree node routines to do the construction. |
| * </summary> |
| */ |
| public virtual object DupTree( object t, object parent ) |
| { |
| if ( t == null ) |
| { |
| return null; |
| } |
| object newTree = DupNode( t ); |
| // ensure new subtree root has parent/child index set |
| SetChildIndex( newTree, GetChildIndex( t ) ); // same index in new tree |
| SetParent( newTree, parent ); |
| int n = GetChildCount( t ); |
| for ( int i = 0; i < n; i++ ) |
| { |
| object child = GetChild( t, i ); |
| object newSubTree = DupTree( child, t ); |
| AddChild( newTree, newSubTree ); |
| } |
| return newTree; |
| } |
| |
| /** <summary> |
| * Add a child to the tree t. If child is a flat tree (a list), make all |
| * in list children of t. Warning: if t has no children, but child does |
| * and child isNil then you can decide it is ok to move children to t via |
| * t.children = child.children; i.e., without copying the array. Just |
| * make sure that this is consistent with have the user will build |
| * ASTs. |
| * </summary> |
| */ |
| public virtual void AddChild( object t, object child ) |
| { |
| if ( t != null && child != null ) |
| { |
| ( (ITree)t ).AddChild( (ITree)child ); |
| } |
| } |
| |
| /** <summary> |
| * If oldRoot is a nil root, just copy or move the children to newRoot. |
| * If not a nil root, make oldRoot a child of newRoot. |
| * </summary> |
| * |
| * <remarks> |
| * old=^(nil a b c), new=r yields ^(r a b c) |
| * old=^(a b c), new=r yields ^(r ^(a b c)) |
| * |
| * If newRoot is a nil-rooted single child tree, use the single |
| * child as the new root node. |
| * |
| * old=^(nil a b c), new=^(nil r) yields ^(r a b c) |
| * old=^(a b c), new=^(nil r) yields ^(r ^(a b c)) |
| * |
| * If oldRoot was null, it's ok, just return newRoot (even if isNil). |
| * |
| * old=null, new=r yields r |
| * old=null, new=^(nil r) yields ^(nil r) |
| * |
| * Return newRoot. Throw an exception if newRoot is not a |
| * simple node or nil root with a single child node--it must be a root |
| * node. If newRoot is ^(nil x) return x as newRoot. |
| * |
| * Be advised that it's ok for newRoot to point at oldRoot's |
| * children; i.e., you don't have to copy the list. We are |
| * constructing these nodes so we should have this control for |
| * efficiency. |
| * </remarks> |
| */ |
| public virtual object BecomeRoot( object newRoot, object oldRoot ) |
| { |
| //System.out.println("becomeroot new "+newRoot.toString()+" old "+oldRoot); |
| ITree newRootTree = (ITree)newRoot; |
| ITree oldRootTree = (ITree)oldRoot; |
| if ( oldRoot == null ) |
| { |
| return newRoot; |
| } |
| // handle ^(nil real-node) |
| if ( newRootTree.IsNil ) |
| { |
| int nc = newRootTree.ChildCount; |
| if ( nc == 1 ) |
| newRootTree = (ITree)newRootTree.GetChild( 0 ); |
| else if ( nc > 1 ) |
| { |
| // TODO: make tree run time exceptions hierarchy |
| throw new Exception( "more than one node as root (TODO: make exception hierarchy)" ); |
| } |
| } |
| // add oldRoot to newRoot; addChild takes care of case where oldRoot |
| // is a flat list (i.e., nil-rooted tree). All children of oldRoot |
| // are added to newRoot. |
| newRootTree.AddChild( oldRootTree ); |
| return newRootTree; |
| } |
| |
| /** <summary>Transform ^(nil x) to x and nil to null</summary> */ |
| public virtual object RulePostProcessing( object root ) |
| { |
| //System.out.println("rulePostProcessing: "+((Tree)root).toStringTree()); |
| ITree r = (ITree)root; |
| if ( r != null && r.IsNil ) |
| { |
| if ( r.ChildCount == 0 ) |
| { |
| r = null; |
| } |
| else if ( r.ChildCount == 1 ) |
| { |
| r = (ITree)r.GetChild( 0 ); |
| // whoever invokes rule will set parent and child index |
| r.Parent = null; |
| r.ChildIndex = -1; |
| } |
| } |
| return r; |
| } |
| |
| public virtual object BecomeRoot( IToken newRoot, object oldRoot ) |
| { |
| return BecomeRoot( Create( newRoot ), oldRoot ); |
| } |
| |
| public virtual object Create( int tokenType, IToken fromToken ) |
| { |
| fromToken = CreateToken( fromToken ); |
| fromToken.Type = tokenType; |
| object t = Create( fromToken ); |
| return t; |
| } |
| |
| public virtual object Create( int tokenType, IToken fromToken, string text ) |
| { |
| if ( fromToken == null ) |
| return Create( tokenType, text ); |
| |
| fromToken = CreateToken( fromToken ); |
| fromToken.Type = tokenType; |
| fromToken.Text = text; |
| object result = Create(fromToken); |
| return result; |
| } |
| |
| public virtual object Create(IToken fromToken, string text) |
| { |
| if (fromToken == null) |
| throw new ArgumentNullException("fromToken"); |
| |
| fromToken = CreateToken(fromToken); |
| fromToken.Text = text; |
| object result = Create(fromToken); |
| return result; |
| } |
| |
| public virtual object Create( int tokenType, string text ) |
| { |
| IToken fromToken = CreateToken( tokenType, text ); |
| object t = Create( fromToken ); |
| return t; |
| } |
| |
| public virtual int GetType( object t ) |
| { |
| ITree tree = GetTree(t); |
| if (tree == null) |
| return TokenTypes.Invalid; |
| |
| return tree.Type; |
| } |
| |
| public virtual void SetType( object t, int type ) |
| { |
| throw new NotSupportedException( "don't know enough about Tree node" ); |
| } |
| |
| public virtual string GetText( object t ) |
| { |
| ITree tree = GetTree(t); |
| if (tree == null) |
| return null; |
| |
| return tree.Text; |
| } |
| |
| public virtual void SetText( object t, string text ) |
| { |
| throw new NotSupportedException( "don't know enough about Tree node" ); |
| } |
| |
| public virtual object GetChild( object t, int i ) |
| { |
| ITree tree = GetTree(t); |
| if (tree == null) |
| return null; |
| |
| return tree.GetChild(i); |
| } |
| |
| public virtual void SetChild( object t, int i, object child ) |
| { |
| ITree tree = GetTree(t); |
| if (tree == null) |
| return; |
| |
| ITree childTree = GetTree(child); |
| tree.SetChild(i, childTree); |
| } |
| |
| public virtual object DeleteChild( object t, int i ) |
| { |
| return ( (ITree)t ).DeleteChild( i ); |
| } |
| |
| public virtual int GetChildCount( object t ) |
| { |
| ITree tree = GetTree(t); |
| if (tree == null) |
| return 0; |
| |
| return tree.ChildCount; |
| } |
| |
| public virtual int GetUniqueID( object node ) |
| { |
| if ( treeToUniqueIDMap == null ) |
| { |
| treeToUniqueIDMap = new Dictionary<object, int>(); |
| } |
| int id; |
| if ( treeToUniqueIDMap.TryGetValue( node, out id ) ) |
| return id; |
| |
| id = uniqueNodeID; |
| treeToUniqueIDMap[node] = id; |
| uniqueNodeID++; |
| return id; |
| // GC makes these nonunique: |
| // return System.identityHashCode(node); |
| } |
| |
| /** <summary> |
| * Tell me how to create a token for use with imaginary token nodes. |
| * For example, there is probably no input symbol associated with imaginary |
| * token DECL, but you need to create it as a payload or whatever for |
| * the DECL node as in ^(DECL type ID). |
| * </summary> |
| * |
| * <remarks> |
| * If you care what the token payload objects' type is, you should |
| * override this method and any other createToken variant. |
| * </remarks> |
| */ |
| public abstract IToken CreateToken( int tokenType, string text ); |
| |
| /** <summary> |
| * Tell me how to create a token for use with imaginary token nodes. |
| * For example, there is probably no input symbol associated with imaginary |
| * token DECL, but you need to create it as a payload or whatever for |
| * the DECL node as in ^(DECL type ID). |
| * </summary> |
| * |
| * <remarks> |
| * This is a variant of createToken where the new token is derived from |
| * an actual real input token. Typically this is for converting '{' |
| * tokens to BLOCK etc... You'll see |
| * |
| * r : lc='{' ID+ '}' -> ^(BLOCK[$lc] ID+) ; |
| * |
| * If you care what the token payload objects' type is, you should |
| * override this method and any other createToken variant. |
| * </remarks> |
| */ |
| public abstract IToken CreateToken( IToken fromToken ); |
| |
| public abstract object Create( IToken payload ); |
| |
| /** <summary> |
| * Duplicate a node. This is part of the factory; |
| * override if you want another kind of node to be built. |
| * </summary> |
| * |
| * <remarks> |
| * I could use reflection to prevent having to override this |
| * but reflection is slow. |
| * </remarks> |
| */ |
| public virtual object DupNode(object treeNode) |
| { |
| ITree tree = GetTree(treeNode); |
| if (tree == null) |
| return null; |
| |
| return tree.DupNode(); |
| } |
| |
| public abstract IToken GetToken( object t ); |
| |
| /** <summary> |
| * Track start/stop token for subtree root created for a rule. |
| * Only works with Tree nodes. For rules that match nothing, |
| * seems like this will yield start=i and stop=i-1 in a nil node. |
| * Might be useful info so I'll not force to be i..i. |
| * </summary> |
| */ |
| public virtual void SetTokenBoundaries(object t, IToken startToken, IToken stopToken) |
| { |
| ITree tree = GetTree(t); |
| if (tree == null) |
| return; |
| |
| int start = 0; |
| int stop = 0; |
| |
| if (startToken != null) |
| start = startToken.TokenIndex; |
| if (stopToken != null) |
| stop = stopToken.TokenIndex; |
| |
| tree.TokenStartIndex = start; |
| tree.TokenStopIndex = stop; |
| } |
| |
| public virtual int GetTokenStartIndex(object t) |
| { |
| ITree tree = GetTree(t); |
| if (tree == null) |
| return -1; |
| |
| return tree.TokenStartIndex; |
| } |
| |
| public virtual int GetTokenStopIndex(object t) |
| { |
| ITree tree = GetTree(t); |
| if (tree == null) |
| return -1; |
| |
| return tree.TokenStopIndex; |
| } |
| |
| public virtual object GetParent(object t) |
| { |
| ITree tree = GetTree(t); |
| if (tree == null) |
| return null; |
| |
| return tree.Parent; |
| } |
| |
| public virtual void SetParent(object t, object parent) |
| { |
| ITree tree = GetTree(t); |
| if (tree == null) |
| return; |
| |
| ITree parentTree = GetTree(parent); |
| tree.Parent = parentTree; |
| } |
| |
| public virtual int GetChildIndex(object t) |
| { |
| ITree tree = GetTree(t); |
| if (tree == null) |
| return 0; |
| |
| return tree.ChildIndex; |
| } |
| |
| public virtual void SetChildIndex(object t, int index) |
| { |
| ITree tree = GetTree(t); |
| if (tree == null) |
| return; |
| |
| tree.ChildIndex = index; |
| } |
| |
| public virtual void ReplaceChildren(object parent, int startChildIndex, int stopChildIndex, object t) |
| { |
| ITree tree = GetTree(parent); |
| if (tree == null) |
| return; |
| |
| tree.ReplaceChildren(startChildIndex, stopChildIndex, t); |
| } |
| |
| protected virtual ITree GetTree(object t) |
| { |
| if (t == null) |
| return null; |
| |
| ITree tree = t as ITree; |
| if (tree == null) |
| throw new NotSupportedException(); |
| |
| return tree; |
| } |
| } |
| } |