| /* |
| [The "BSD licence"] |
| Copyright (c) 2005-2006 Terence Parr |
| 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. |
| */ |
| package org.antlr.runtime.tree { |
| /** 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". |
| */ |
| public class BaseTree implements Tree { |
| protected var _children:Array; |
| |
| /** 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. |
| */ |
| public function BaseTree(node:Tree = null) { |
| } |
| |
| public function getChild(i:int):Tree { |
| if ( _children==null || i>=_children.length ) { |
| return null; |
| } |
| return BaseTree(_children[i]); |
| } |
| |
| /** Get the children internal List; note that if you directly mess with |
| * the list, do so at your own risk. |
| */ |
| public function get children():Array { |
| return _children; |
| } |
| |
| public function getFirstChildWithType(type:int):Tree { |
| for (var i:int = 0; _children!=null && i < _children.length; i++) { |
| var t:Tree = Tree(_children[i]); |
| if ( t.type==type ) { |
| return t; |
| } |
| } |
| return null; |
| } |
| |
| public function get childCount():int { |
| if ( _children==null ) { |
| return 0; |
| } |
| return _children.length; |
| } |
| |
| /** Add t as child of this node. |
| * |
| * 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. |
| */ |
| public function addChild(t:Tree):void { |
| if ( t==null ) { |
| return; // do nothing upon addChild(null) |
| } |
| var childTree:BaseTree = BaseTree(t); |
| if ( childTree.isNil ) { // t is an empty node possibly with children |
| if ( this._children!=null && this._children == childTree._children ) { |
| throw new Error("attempt to add child list to itself"); |
| } |
| // just add all of childTree's children to this |
| if ( childTree._children!=null ) { |
| if ( this._children!=null ) { // must copy, this has children already |
| var n:int = childTree._children.length; |
| for (var i:int = 0; i < n; i++) { |
| var c:Tree = Tree(childTree._children[i]); |
| this.children.push(c); |
| // handle double-link stuff for each child of nil root |
| c.parent = this; |
| c.childIndex = children.length-1; |
| } |
| } |
| else { |
| // no children for this but t has 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 = new Array(); // create children list on demand |
| } |
| _children.push(t); |
| childTree.parent = this; |
| childTree.childIndex = children.length-1; |
| } |
| } |
| |
| /** Add all elements of kids list as children of this node */ |
| public function addChildren(kids:Array):void { |
| for (var i:int = 0; i < kids.length; i++) { |
| var t:Tree = Tree(kids[i]); |
| addChild(t); |
| } |
| } |
| |
| public function setChild(i:int, t:Tree):void { |
| if ( t==null ) { |
| return; |
| } |
| if ( t.isNil ) { |
| throw new Error("Can't set single child to a list"); |
| } |
| if ( _children==null ) { |
| _children = new Array(); |
| } |
| _children[i] = t; |
| t.parent = this; |
| t.childIndex = i; |
| } |
| |
| public function deleteChild(i:int):Object { |
| if ( _children==null ) { |
| return null; |
| } |
| var killed:BaseTree = BaseTree(children.remove(i)); |
| // walk rest and decrement their child indexes |
| this.freshenParentAndChildIndexesFrom(i); |
| return killed; |
| } |
| |
| /** 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. |
| */ |
| public function replaceChildren(startChildIndex:int, stopChildIndex:int, t:Object):void { |
| if ( children==null ) { |
| throw new Error("indexes invalid; no children in list"); |
| } |
| var replacingHowMany:int = stopChildIndex - startChildIndex + 1; |
| var replacingWithHowMany:int; |
| var newTree:BaseTree = BaseTree(t); |
| var newChildren:Array = null; |
| // normalize to a list of children to add: newChildren |
| if ( newTree.isNil ) { |
| newChildren = newTree.children; |
| } |
| else { |
| newChildren = new Array(); |
| newChildren.push(newTree); |
| } |
| replacingWithHowMany = newChildren.length; |
| var numNewChildren:int = newChildren.length; |
| var delta:int = replacingHowMany - replacingWithHowMany; |
| // if same number of nodes, do direct replace |
| if ( delta == 0 ) { |
| var j:int = 0; // index into new children |
| for (var i:int=startChildIndex; i<=stopChildIndex; i++) { |
| var child:BaseTree = BaseTree(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 (j=0; j<numNewChildren; j++) { |
| children[startChildIndex+j] = newChildren[j]; |
| } |
| var indexToDelete:int = startChildIndex+numNewChildren; |
| for (var c:int=indexToDelete; c<=stopChildIndex; c++) { |
| // delete same index, shifting everybody down each time |
| var killed:BaseTree = BaseTree(children.remove(indexToDelete)); |
| } |
| freshenParentAndChildIndexesFrom(startChildIndex); |
| } |
| else { // more new nodes than were there before |
| // fill in as many children as we can (replacingHowMany) w/o moving data |
| for (j=0; j<replacingHowMany; j++) { |
| children[startChildIndex+j] = newChildren[j]; |
| } |
| var numToInsert:int = replacingWithHowMany-replacingHowMany; |
| for (j=replacingHowMany; j<replacingWithHowMany; j++) { |
| children.splice(startChildIndex+j, 0, newChildren[j]); |
| } |
| freshenParentAndChildIndexesFrom(startChildIndex); |
| } |
| } |
| |
| public function get isNil():Boolean { |
| return false; |
| } |
| |
| /** Set the parent and child index values for all child of t */ |
| public function freshenParentAndChildIndexes():void { |
| freshenParentAndChildIndexesFrom(0); |
| } |
| |
| public function freshenParentAndChildIndexesFrom(offset:int):void { |
| var n:int = childCount; |
| for (var c:int = offset; c < n; c++) { |
| var child:Tree = Tree(getChild(c)); |
| child.childIndex = c; |
| child.parent = this; |
| } |
| } |
| |
| public function sanityCheckParentAndChildIndexes():void { |
| sanityCheckParentAndChildIndexesFrom(null, -1); |
| } |
| |
| public function sanityCheckParentAndChildIndexesFrom(parent:Tree, i:int):void { |
| if ( parent!=this.parent ) { |
| throw new Error("parents don't match; expected "+parent+" found "+this.parent); |
| } |
| if ( i!=this.childIndex ) { |
| throw new Error("child indexes don't match; expected "+i+" found "+this.childIndex); |
| } |
| var n:int = this.childCount; |
| for (var c:int = 0; c < n; c++) { |
| var child:CommonTree = CommonTree(this.getChild(c)); |
| child.sanityCheckParentAndChildIndexesFrom(this, c); |
| } |
| } |
| |
| /** BaseTree doesn't track child indexes. */ |
| public function get childIndex():int { |
| return 0; |
| } |
| |
| public function set childIndex(index:int):void { |
| } |
| |
| /** BaseTree doesn't track parent pointers. */ |
| public function get parent():Tree { |
| return null; |
| } |
| public function set parent(t:Tree):void { |
| } |
| |
| /** Walk upwards looking for ancestor with this token type. */ |
| public function hasAncestor(ttype:int):Boolean { return getAncestor(ttype)!=null; } |
| |
| /** Walk upwards and get first ancestor with this token type. */ |
| public function getAncestor(ttype:int):Tree { |
| var t:Tree = this; |
| t = t.parent; |
| while ( t!=null ) { |
| if ( t.type==ttype ) return t; |
| t = t.parent; |
| } |
| return null; |
| } |
| |
| /** 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. |
| */ |
| public function get ancestors():Array { |
| if ( parent==null ) return null; |
| var ancestors:Array = new Array(); |
| var t:Tree = this; |
| t = t.parent; |
| while ( t!=null ) { |
| ancestors.unshift(t); // insert at start |
| t = t.parent; |
| } |
| return ancestors; |
| } |
| |
| /** Print out a whole tree not just a node */ |
| public function toStringTree():String { |
| if ( _children==null || _children.length==0 ) { |
| return String(this); |
| } |
| var buf:String = ""; |
| if ( !isNil ) { |
| buf += "("; |
| buf += String(this); |
| buf += ' '; |
| } |
| for (var i:int = 0; _children!=null && i < _children.length; i++) { |
| var t:BaseTree = BaseTree(_children[i]); |
| if ( i>0 ) { |
| buf += ' '; |
| } |
| buf += t.toStringTree(); |
| } |
| if ( !isNil ) { |
| buf += ")"; |
| } |
| return buf; |
| } |
| |
| public function get line():int { |
| return 0; |
| } |
| |
| public function get charPositionInLine():int { |
| return 0; |
| } |
| |
| // "Abstract" functions since there are no abstract classes in actionscript |
| |
| public function dupNode():Tree { |
| throw new Error("Not implemented"); |
| } |
| |
| public function get type():int { |
| throw new Error("Not implemented"); |
| } |
| |
| public function get text():String { |
| throw new Error("Not implemented"); |
| } |
| |
| public function get tokenStartIndex():int { |
| throw new Error("Not implemented"); |
| } |
| |
| public function set tokenStartIndex(index:int):void { |
| throw new Error("Not implemented"); |
| } |
| |
| public function get tokenStopIndex():int { |
| throw new Error("Not implemented"); |
| } |
| |
| public function set tokenStopIndex(index:int):void { |
| throw new Error("Not implemented"); |
| } |
| |
| } |
| } |