aboutsummaryrefslogtreecommitdiff
path: root/runtime/CSharp3/Sources/Antlr3.Runtime/Tree/BaseTree.cs
diff options
context:
space:
mode:
Diffstat (limited to 'runtime/CSharp3/Sources/Antlr3.Runtime/Tree/BaseTree.cs')
-rw-r--r--runtime/CSharp3/Sources/Antlr3.Runtime/Tree/BaseTree.cs532
1 files changed, 532 insertions, 0 deletions
diff --git a/runtime/CSharp3/Sources/Antlr3.Runtime/Tree/BaseTree.cs b/runtime/CSharp3/Sources/Antlr3.Runtime/Tree/BaseTree.cs
new file mode 100644
index 0000000..79f3d97
--- /dev/null
+++ b/runtime/CSharp3/Sources/Antlr3.Runtime/Tree/BaseTree.cs
@@ -0,0 +1,532 @@
+/*
+ * [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
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-11 10:36:43 +0000