| /** 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". |
| */ |
| org.antlr.runtime.tree.BaseTree = function() {}; |
| |
| org.antlr.lang.extend(org.antlr.runtime.tree.BaseTree, |
| org.antlr.runtime.tree.Tree, |
| { |
| getChild: function(i) { |
| if ( !this.children || i>=this.children.length ) { |
| return null; |
| } |
| return this.children[i]; |
| }, |
| |
| /** Get the children internal List; note that if you directly mess with |
| * the list, do so at your own risk. |
| */ |
| getChildren: function() { |
| return this.children; |
| }, |
| |
| getFirstChildWithType: function(type) { |
| var i, t; |
| for (i = 0; this.children && i < this.children.length; i++) { |
| t = this.children[i]; |
| if ( t.getType()===type ) { |
| return t; |
| } |
| } |
| return null; |
| }, |
| |
| getChildCount: function() { |
| if ( !this.children ) { |
| return 0; |
| } |
| return this.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. |
| */ |
| addChild: function(t) { |
| if ( !org.antlr.lang.isValue(t) ) { |
| return; // do nothing upon addChild(null) |
| } |
| var childTree = t, n, i, c; |
| if ( childTree.isNil() ) { // t is an empty node possibly with children |
| if ( this.children && 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 ) { |
| if ( this.children ) { // must copy, this has children already |
| n = childTree.children.length; |
| for (i = 0; i < n; i++) { |
| c = childTree.children[i]; |
| this.children.push(c); |
| // handle double-link stuff for each child of nil root |
| c.setParent(this); |
| c.setChildIndex(this.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 ( !this.children ) { |
| this.children = this.createChildrenList(); // create children list on demand |
| } |
| this.children.push(t); |
| childTree.setParent(this); |
| childTree.setChildIndex(this.children.length-1); |
| } |
| }, |
| |
| /** Add all elements of kids list as children of this node */ |
| addChildren: function(kids) { |
| var i, t; |
| for (i = 0; i < kids.length; i++) { |
| t = kids[i]; |
| this.addChild(t); |
| } |
| }, |
| |
| setChild: function(i, t) { |
| if ( !t ) { |
| return; |
| } |
| if ( t.isNil() ) { |
| throw new Error("Can't set single child to a list"); |
| } |
| if ( !this.children ) { |
| this.children = this.createChildrenList(); |
| } |
| this.children[i] = t; |
| t.setParent(this); |
| t.setChildIndex(i); |
| }, |
| |
| deleteChild: function(i) { |
| if ( !this.children ) { |
| return null; |
| } |
| if (i<0 || i>=this.children.length) { |
| throw new Error("Index out of bounds."); |
| } |
| var killed = this.children.splice(i, 1)[0]; |
| // walk rest and decrement their child indexes |
| this.freshenParentAndChildIndexes(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. |
| */ |
| replaceChildren: function(startChildIndex, stopChildIndex, t) { |
| if ( !this.children ) { |
| throw new Error("indexes invalid; no children in list"); |
| } |
| var replacingHowMany = stopChildIndex - startChildIndex + 1; |
| var replacingWithHowMany; |
| var newTree = t; |
| var newChildren = null; |
| // normalize to a list of children to add: newChildren |
| if ( newTree.isNil() ) { |
| newChildren = newTree.children; |
| } |
| else { |
| newChildren = []; |
| newChildren.push(newTree); |
| } |
| replacingWithHowMany = newChildren.length; |
| var numNewChildren = newChildren.length; |
| var delta = replacingHowMany - replacingWithHowMany; |
| var j, i, child, indexToDelete, c, killed, numToInsert; |
| // if same number of nodes, do direct replace |
| if ( delta === 0 ) { |
| j = 0; // index into new children |
| for (i=startChildIndex; i<=stopChildIndex; i++) { |
| child = newChildren[j]; |
| this.children[i] = child; |
| child.setParent(this); |
| child.setChildIndex(i); |
| j++; |
| } |
| } |
| else if ( delta > 0 ) { // fewer new nodes than there were |
| // set children and then delete extra |
| for (j=0; j<numNewChildren; j++) { |
| this.children[startChildIndex+j] = newChildren[j]; |
| } |
| indexToDelete = startChildIndex+numNewChildren; |
| for (c=indexToDelete; c<=stopChildIndex; c++) { |
| // delete same index, shifting everybody down each time |
| killed = this.children.splice(indexToDelete, 1)[0]; |
| } |
| this.freshenParentAndChildIndexes(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++) { |
| this.children[startChildIndex+j] = newChildren[j]; |
| } |
| numToInsert = replacingWithHowMany-replacingHowMany; |
| for (j=replacingHowMany; j<replacingWithHowMany; j++) { |
| this.children.splice(startChildIndex+j, 0, newChildren[j]); |
| } |
| this.freshenParentAndChildIndexes(startChildIndex); |
| } |
| }, |
| |
| /** Override in a subclass to change the impl of children list */ |
| createChildrenList: function() { |
| return []; |
| }, |
| |
| isNil: function() { |
| return false; |
| }, |
| |
| freshenParentAndChildIndexes: function(offset) { |
| if (!org.antlr.lang.isNumber(offset)) { |
| offset = 0; |
| } |
| var n = this.getChildCount(), |
| c, |
| child; |
| for (c = offset; c < n; c++) { |
| child = this.getChild(c); |
| child.setChildIndex(c); |
| child.setParent(this); |
| } |
| }, |
| |
| sanityCheckParentAndChildIndexes: function(parent, i) { |
| if (arguments.length===0) { |
| parent = null; |
| i = -1; |
| } |
| |
| if ( parent!==this.getParent() ) { |
| throw new Error("parents don't match; expected "+parent+" found "+this.getParent()); |
| } |
| if ( i!==this.getChildIndex() ) { |
| throw new Error("child indexes don't match; expected "+i+" found "+this.getChildIndex()); |
| } |
| var n = this.getChildCount(), |
| c, |
| child; |
| for (c = 0; c < n; c++) { |
| child = this.getChild(c); |
| child.sanityCheckParentAndChildIndexes(this, c); |
| } |
| }, |
| |
| /** BaseTree doesn't track child indexes. */ |
| getChildIndex: function() { |
| return 0; |
| }, |
| setChildIndex: function(index) { |
| }, |
| |
| /** BaseTree doesn't track parent pointers. */ |
| getParent: function() { |
| return null; |
| }, |
| setParent: function(t) { |
| }, |
| |
| getTree: function() { |
| return this; |
| }, |
| |
| /** Print out a whole tree not just a node */ |
| toStringTree: function() { |
| if ( !this.children || this.children.length===0 ) { |
| return this.toString(); |
| } |
| var buf = "", |
| i, |
| t; |
| if ( !this.isNil() ) { |
| buf += "("; |
| buf += this.toString(); |
| buf += ' '; |
| } |
| for (i = 0; this.children && i < this.children.length; i++) { |
| t = this.children[i]; |
| if ( i>0 ) { |
| buf += ' '; |
| } |
| buf += t.toStringTree(); |
| } |
| if ( !this.isNil() ) { |
| buf += ")"; |
| } |
| return buf; |
| }, |
| |
| getLine: function() { |
| return 0; |
| }, |
| |
| getCharPositionInLine: function() { |
| return 0; |
| } |
| }); |