| /* |
| * [The "BSD licence"] |
| * Copyright (c) 2005-2008 Terence Parr |
| * All rights reserved. |
| * |
| * Conversion to C#: |
| * Copyright (c) 2008-2009 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] |
| public abstract class BaseTree : ITree { |
| List<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; |
| } |
| } |
| |
| #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; |
| List<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 List<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 |
| } |
| } |