| /* |
| * [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; |
| using System.Collections.Generic; |
| |
| using StringBuilder = System.Text.StringBuilder; |
| |
| /** <summary> |
| * A generic tree implementation with no payload. You must subclass to |
| * actually have any user data. ANTLR v3 uses a list of children approach |
| * instead of the child-sibling approach in v2. A flat tree (a list) is |
| * an empty node whose children represent the list. An empty, but |
| * non-null node is called "nil". |
| * </summary> |
| */ |
| [System.Serializable] |
| [System.Diagnostics.DebuggerTypeProxy(typeof(AntlrRuntime_BaseTreeDebugView))] |
| public abstract class BaseTree : ITree |
| { |
| private IList<ITree> _children; |
| |
| public BaseTree() |
| { |
| } |
| |
| /** <summary> |
| * Create a new node from an existing node does nothing for BaseTree |
| * as there are no fields other than the children list, which cannot |
| * be copied as the children are not considered part of this node. |
| * </summary> |
| */ |
| public BaseTree( ITree node ) |
| { |
| } |
| |
| /** <summary> |
| * Get the children internal List; note that if you directly mess with |
| * the list, do so at your own risk. |
| * </summary> |
| */ |
| public virtual IList<ITree> Children |
| { |
| get |
| { |
| return _children; |
| } |
| |
| private set |
| { |
| _children = value; |
| } |
| } |
| |
| #region ITree Members |
| |
| public virtual int ChildCount |
| { |
| get |
| { |
| if ( Children == null ) |
| return 0; |
| |
| return Children.Count; |
| } |
| } |
| |
| /** <summary>BaseTree doesn't track parent pointers.</summary> */ |
| public virtual ITree Parent |
| { |
| get |
| { |
| return null; |
| } |
| set |
| { |
| } |
| } |
| |
| /** <summary>BaseTree doesn't track child indexes.</summary> */ |
| public virtual int ChildIndex |
| { |
| get |
| { |
| return 0; |
| } |
| set |
| { |
| } |
| } |
| |
| public virtual bool IsNil |
| { |
| get |
| { |
| return false; |
| } |
| } |
| |
| public abstract int TokenStartIndex |
| { |
| get; |
| set; |
| } |
| |
| public abstract int TokenStopIndex |
| { |
| get; |
| set; |
| } |
| |
| public abstract int Type |
| { |
| get; |
| set; |
| } |
| |
| public abstract string Text |
| { |
| get; |
| set; |
| } |
| |
| public virtual int Line |
| { |
| get; |
| set; |
| } |
| |
| public virtual int CharPositionInLine |
| { |
| get; |
| set; |
| } |
| |
| #endregion |
| |
| public virtual ITree GetChild( int i ) |
| { |
| if (i < 0) |
| throw new ArgumentOutOfRangeException(); |
| |
| if ( Children == null || i >= Children.Count ) |
| return null; |
| |
| return Children[i]; |
| } |
| |
| public virtual ITree GetFirstChildWithType( int type ) |
| { |
| foreach ( ITree child in Children ) |
| { |
| if ( child.Type == type ) |
| return child; |
| } |
| |
| return null; |
| } |
| |
| /** <summary>Add t as child of this node.</summary> |
| * |
| * <remarks> |
| * Warning: if t has no children, but child does |
| * and child isNil then this routine moves children to t via |
| * t.children = child.children; i.e., without copying the array. |
| * </remarks> |
| */ |
| public virtual void AddChild( ITree t ) |
| { |
| //System.out.println("add child "+t.toStringTree()+" "+this.toStringTree()); |
| //System.out.println("existing children: "+children); |
| if ( t == null ) |
| { |
| return; // do nothing upon addChild(null) |
| } |
| if ( t.IsNil ) |
| { |
| // t is an empty node possibly with children |
| BaseTree childTree = t as BaseTree; |
| if ( childTree != null && this.Children != null && this.Children == childTree.Children ) |
| { |
| throw new Exception( "attempt to add child list to itself" ); |
| } |
| // just add all of childTree's children to this |
| if ( t.ChildCount > 0 ) |
| { |
| if ( this.Children != null || childTree == null ) |
| { |
| if ( this.Children == null ) |
| this.Children = CreateChildrenList(); |
| |
| // must copy, this has children already |
| int n = t.ChildCount; |
| for ( int i = 0; i < n; i++ ) |
| { |
| ITree c = t.GetChild( i ); |
| this.Children.Add( c ); |
| // handle double-link stuff for each child of nil root |
| c.Parent = this; |
| c.ChildIndex = Children.Count - 1; |
| } |
| } |
| else |
| { |
| // no children for this but t is a BaseTree with children; |
| // just set pointer call general freshener routine |
| this.Children = childTree.Children; |
| this.FreshenParentAndChildIndexes(); |
| } |
| } |
| } |
| else |
| { |
| // child is not nil (don't care about children) |
| if ( Children == null ) |
| { |
| Children = CreateChildrenList(); // create children list on demand |
| } |
| Children.Add( t ); |
| t.Parent = this; |
| t.ChildIndex = Children.Count - 1; |
| } |
| // System.out.println("now children are: "+children); |
| } |
| |
| /** <summary>Add all elements of kids list as children of this node</summary> */ |
| public virtual void AddChildren( IEnumerable<ITree> kids ) |
| { |
| if (kids == null) |
| throw new ArgumentNullException("kids"); |
| |
| foreach ( ITree t in kids ) |
| AddChild( t ); |
| } |
| |
| public virtual void SetChild( int i, ITree t ) |
| { |
| if (i < 0) |
| throw new ArgumentOutOfRangeException("i"); |
| |
| if ( t == null ) |
| { |
| return; |
| } |
| if ( t.IsNil ) |
| { |
| throw new ArgumentException( "Can't set single child to a list" ); |
| } |
| if ( Children == null ) |
| { |
| Children = CreateChildrenList(); |
| } |
| Children[i] = t; |
| t.Parent = this; |
| t.ChildIndex = i; |
| } |
| |
| public virtual object DeleteChild( int i ) |
| { |
| if (i < 0) |
| throw new ArgumentOutOfRangeException("i"); |
| if (i >= ChildCount) |
| throw new ArgumentException(); |
| |
| if ( Children == null ) |
| return null; |
| |
| ITree killed = Children[i]; |
| Children.RemoveAt( i ); |
| // walk rest and decrement their child indexes |
| this.FreshenParentAndChildIndexes( i ); |
| return killed; |
| } |
| |
| /** <summary> |
| * Delete children from start to stop and replace with t even if t is |
| * a list (nil-root tree). num of children can increase or decrease. |
| * For huge child lists, inserting children can force walking rest of |
| * children to set their childindex; could be slow. |
| * </summary> |
| */ |
| public virtual void ReplaceChildren( int startChildIndex, int stopChildIndex, object t ) |
| { |
| if (startChildIndex < 0) |
| throw new ArgumentOutOfRangeException(); |
| if (stopChildIndex < 0) |
| throw new ArgumentOutOfRangeException(); |
| if (t == null) |
| throw new ArgumentNullException("t"); |
| if (stopChildIndex < startChildIndex) |
| throw new ArgumentException(); |
| |
| /* |
| System.out.println("replaceChildren "+startChildIndex+", "+stopChildIndex+ |
| " with "+((BaseTree)t).toStringTree()); |
| System.out.println("in="+toStringTree()); |
| */ |
| if ( Children == null ) |
| { |
| throw new ArgumentException( "indexes invalid; no children in list" ); |
| } |
| int replacingHowMany = stopChildIndex - startChildIndex + 1; |
| int replacingWithHowMany; |
| ITree newTree = (ITree)t; |
| IList<ITree> newChildren = null; |
| // normalize to a list of children to add: newChildren |
| if ( newTree.IsNil ) |
| { |
| BaseTree baseTree = newTree as BaseTree; |
| if ( baseTree != null && baseTree.Children != null ) |
| { |
| newChildren = baseTree.Children; |
| } |
| else |
| { |
| newChildren = CreateChildrenList(); |
| int n = newTree.ChildCount; |
| for ( int i = 0; i < n; i++ ) |
| newChildren.Add( newTree.GetChild( i ) ); |
| } |
| } |
| else |
| { |
| newChildren = new List<ITree>( 1 ); |
| newChildren.Add( newTree ); |
| } |
| replacingWithHowMany = newChildren.Count; |
| int numNewChildren = newChildren.Count; |
| int delta = replacingHowMany - replacingWithHowMany; |
| // if same number of nodes, do direct replace |
| if ( delta == 0 ) |
| { |
| int j = 0; // index into new children |
| for ( int i = startChildIndex; i <= stopChildIndex; i++ ) |
| { |
| ITree child = newChildren[j]; |
| Children[i] = child; |
| child.Parent = this; |
| child.ChildIndex = i; |
| j++; |
| } |
| } |
| else if ( delta > 0 ) |
| { |
| // fewer new nodes than there were |
| // set children and then delete extra |
| for ( int j = 0; j < numNewChildren; j++ ) |
| { |
| Children[startChildIndex + j] = newChildren[j]; |
| } |
| int indexToDelete = startChildIndex + numNewChildren; |
| for ( int c = indexToDelete; c <= stopChildIndex; c++ ) |
| { |
| // delete same index, shifting everybody down each time |
| Children.RemoveAt( indexToDelete ); |
| } |
| FreshenParentAndChildIndexes( startChildIndex ); |
| } |
| else |
| { |
| // more new nodes than were there before |
| // fill in as many children as we can (replacingHowMany) w/o moving data |
| for ( int j = 0; j < replacingHowMany; j++ ) |
| { |
| Children[startChildIndex + j] = newChildren[j]; |
| } |
| int numToInsert = replacingWithHowMany - replacingHowMany; |
| for ( int j = replacingHowMany; j < replacingWithHowMany; j++ ) |
| { |
| Children.Insert( startChildIndex + j, newChildren[j] ); |
| } |
| FreshenParentAndChildIndexes( startChildIndex ); |
| } |
| //System.out.println("out="+toStringTree()); |
| } |
| |
| /** <summary>Override in a subclass to change the impl of children list</summary> */ |
| protected virtual IList<ITree> CreateChildrenList() |
| { |
| return new List<ITree>(); |
| } |
| |
| /** <summary>Set the parent and child index values for all child of t</summary> */ |
| public virtual void FreshenParentAndChildIndexes() |
| { |
| FreshenParentAndChildIndexes( 0 ); |
| } |
| |
| public virtual void FreshenParentAndChildIndexes( int offset ) |
| { |
| int n = ChildCount; |
| for ( int c = offset; c < n; c++ ) |
| { |
| ITree child = GetChild( c ); |
| child.ChildIndex = c; |
| child.Parent = this; |
| } |
| } |
| |
| public virtual void SanityCheckParentAndChildIndexes() |
| { |
| SanityCheckParentAndChildIndexes( null, -1 ); |
| } |
| |
| public virtual void SanityCheckParentAndChildIndexes( ITree parent, int i ) |
| { |
| if ( parent != this.Parent ) |
| { |
| throw new InvalidOperationException( "parents don't match; expected " + parent + " found " + this.Parent ); |
| } |
| if ( i != this.ChildIndex ) |
| { |
| throw new InvalidOperationException( "child indexes don't match; expected " + i + " found " + this.ChildIndex ); |
| } |
| int n = this.ChildCount; |
| for ( int c = 0; c < n; c++ ) |
| { |
| BaseTree child = (BaseTree)this.GetChild( c ); |
| child.SanityCheckParentAndChildIndexes( this, c ); |
| } |
| } |
| |
| /** <summary>Walk upwards looking for ancestor with this token type.</summary> */ |
| public virtual bool HasAncestor( int ttype ) |
| { |
| return GetAncestor( ttype ) != null; |
| } |
| |
| /** <summary>Walk upwards and get first ancestor with this token type.</summary> */ |
| public virtual ITree GetAncestor( int ttype ) |
| { |
| ITree t = this; |
| t = t.Parent; |
| while ( t != null ) |
| { |
| if ( t.Type == ttype ) |
| return t; |
| t = t.Parent; |
| } |
| return null; |
| } |
| |
| /** <summary> |
| * Return a list of all ancestors of this node. The first node of |
| * list is the root and the last is the parent of this node. |
| * </summary> |
| */ |
| public virtual IList<ITree> GetAncestors() |
| { |
| if ( Parent == null ) |
| return null; |
| |
| List<ITree> ancestors = new List<ITree>(); |
| ITree t = this; |
| t = t.Parent; |
| while ( t != null ) |
| { |
| ancestors.Insert( 0, t ); // insert at start |
| t = t.Parent; |
| } |
| return ancestors; |
| } |
| |
| /** <summary>Print out a whole tree not just a node</summary> */ |
| public virtual string ToStringTree() |
| { |
| if ( Children == null || Children.Count == 0 ) |
| { |
| return this.ToString(); |
| } |
| StringBuilder buf = new StringBuilder(); |
| if ( !IsNil ) |
| { |
| buf.Append( "(" ); |
| buf.Append( this.ToString() ); |
| buf.Append( ' ' ); |
| } |
| for ( int i = 0; Children != null && i < Children.Count; i++ ) |
| { |
| ITree t = Children[i]; |
| if ( i > 0 ) |
| { |
| buf.Append( ' ' ); |
| } |
| buf.Append( t.ToStringTree() ); |
| } |
| if ( !IsNil ) |
| { |
| buf.Append( ")" ); |
| } |
| return buf.ToString(); |
| } |
| |
| /** <summary>Override to say how a node (not a tree) should look as text</summary> */ |
| public override abstract string ToString(); |
| |
| #region Tree Members |
| public abstract ITree DupNode(); |
| #endregion |
| } |
| } |