• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1/** A generic tree implementation with no payload.  You must subclass to
2 *  actually have any user data.  ANTLR v3 uses a list of children approach
3 *  instead of the child-sibling approach in v2.  A flat tree (a list) is
4 *  an empty node whose children represent the list.  An empty, but
5 *  non-null node is called "nil".
6 */
7org.antlr.runtime.tree.BaseTree = function() {};
8
9org.antlr.lang.extend(org.antlr.runtime.tree.BaseTree,
10                      org.antlr.runtime.tree.Tree,
11{
12    getChild: function(i) {
13        if ( !this.children || i>=this.children.length ) {
14            return null;
15        }
16        return this.children[i];
17    },
18
19    /** Get the children internal List; note that if you directly mess with
20     *  the list, do so at your own risk.
21     */
22    getChildren: function() {
23        return this.children;
24    },
25
26    getFirstChildWithType: function(type) {
27        var i, t;
28        for (i = 0; this.children && i < this.children.length; i++) {
29            t = this.children[i];
30            if ( t.getType()===type ) {
31                return t;
32            }
33        }
34        return null;
35    },
36
37    getChildCount: function() {
38        if ( !this.children ) {
39            return 0;
40        }
41        return this.children.length;
42    },
43
44    /** Add t as child of this node.
45     *
46     *  Warning: if t has no children, but child does
47     *  and child isNil then this routine moves children to t via
48     *  t.children = child.children; i.e., without copying the array.
49     */
50    addChild: function(t) {
51        if ( !org.antlr.lang.isValue(t) ) {
52            return; // do nothing upon addChild(null)
53        }
54        var childTree = t, n, i, c;
55        if ( childTree.isNil() ) { // t is an empty node possibly with children
56            if ( this.children && this.children == childTree.children ) {
57                throw new Error("attempt to add child list to itself");
58            }
59            // just add all of childTree's children to this
60            if ( childTree.children ) {
61                if ( this.children ) { // must copy, this has children already
62                    n = childTree.children.length;
63                    for (i = 0; i < n; i++) {
64                        c = childTree.children[i];
65                        this.children.push(c);
66                        // handle double-link stuff for each child of nil root
67                        c.setParent(this);
68                        c.setChildIndex(this.children.length-1);
69                    }
70                }
71                else {
72                    // no children for this but t has children; just set pointer
73                    // call general freshener routine
74                    this.children = childTree.children;
75                    this.freshenParentAndChildIndexes();
76                }
77            }
78        }
79        else { // child is not nil (don't care about children)
80            if ( !this.children ) {
81                this.children = this.createChildrenList(); // create children list on demand
82            }
83            this.children.push(t);
84            childTree.setParent(this);
85            childTree.setChildIndex(this.children.length-1);
86        }
87    },
88
89    /** Add all elements of kids list as children of this node */
90    addChildren: function(kids) {
91        var i, t;
92        for (i = 0; i < kids.length; i++) {
93            t = kids[i];
94            this.addChild(t);
95        }
96    },
97
98    setChild: function(i, t) {
99        if ( !t ) {
100            return;
101        }
102        if ( t.isNil() ) {
103            throw new Error("Can't set single child to a list");
104        }
105        if ( !this.children ) {
106            this.children = this.createChildrenList();
107        }
108        this.children[i] = t;
109        t.setParent(this);
110        t.setChildIndex(i);
111    },
112
113    deleteChild: function(i) {
114        if ( !this.children ) {
115            return null;
116        }
117        if (i<0 || i>=this.children.length) {
118            throw new Error("Index out of bounds.");
119        }
120        var killed = this.children.splice(i, 1)[0];
121        // walk rest and decrement their child indexes
122        this.freshenParentAndChildIndexes(i);
123        return killed;
124    },
125
126    /** Delete children from start to stop and replace with t even if t is
127     *  a list (nil-root tree).  num of children can increase or decrease.
128     *  For huge child lists, inserting children can force walking rest of
129     *  children to set their childindex; could be slow.
130     */
131    replaceChildren: function(startChildIndex, stopChildIndex, t) {
132        if ( !this.children ) {
133            throw new Error("indexes invalid; no children in list");
134        }
135        var replacingHowMany = stopChildIndex - startChildIndex + 1;
136        var replacingWithHowMany;
137        var newTree = t;
138        var newChildren = null;
139        // normalize to a list of children to add: newChildren
140        if ( newTree.isNil() ) {
141            newChildren = newTree.children;
142        }
143        else {
144            newChildren = [];
145            newChildren.push(newTree);
146        }
147        replacingWithHowMany = newChildren.length;
148        var numNewChildren = newChildren.length;
149        var delta = replacingHowMany - replacingWithHowMany;
150        var j, i, child, indexToDelete, c, killed, numToInsert;
151        // if same number of nodes, do direct replace
152        if ( delta === 0 ) {
153            j = 0; // index into new children
154            for (i=startChildIndex; i<=stopChildIndex; i++) {
155                child = newChildren[j];
156                this.children[i] = child;
157                child.setParent(this);
158                child.setChildIndex(i);
159                j++;
160            }
161        }
162        else if ( delta > 0 ) { // fewer new nodes than there were
163            // set children and then delete extra
164            for (j=0; j<numNewChildren; j++) {
165                this.children[startChildIndex+j] = newChildren[j];
166            }
167            indexToDelete = startChildIndex+numNewChildren;
168            for (c=indexToDelete; c<=stopChildIndex; c++) {
169                // delete same index, shifting everybody down each time
170                killed = this.children.splice(indexToDelete, 1)[0];
171            }
172            this.freshenParentAndChildIndexes(startChildIndex);
173        }
174        else { // more new nodes than were there before
175            // fill in as many children as we can (replacingHowMany) w/o moving data
176            for (j=0; j<replacingHowMany; j++) {
177                this.children[startChildIndex+j] = newChildren[j];
178            }
179            numToInsert = replacingWithHowMany-replacingHowMany;
180            for (j=replacingHowMany; j<replacingWithHowMany; j++) {
181                this.children.splice(startChildIndex+j, 0, newChildren[j]);
182            }
183            this.freshenParentAndChildIndexes(startChildIndex);
184        }
185    },
186
187    /** Override in a subclass to change the impl of children list */
188    createChildrenList: function() {
189        return [];
190    },
191
192    isNil: function() {
193        return false;
194    },
195
196    freshenParentAndChildIndexes: function(offset) {
197        if (!org.antlr.lang.isNumber(offset)) {
198            offset = 0;
199        }
200        var n = this.getChildCount(),
201            c,
202            child;
203        for (c = offset; c < n; c++) {
204            child = this.getChild(c);
205            child.setChildIndex(c);
206            child.setParent(this);
207        }
208    },
209
210    sanityCheckParentAndChildIndexes: function(parent, i) {
211        if (arguments.length===0) {
212            parent = null;
213            i = -1;
214        }
215
216        if ( parent!==this.getParent() ) {
217            throw new Error("parents don't match; expected "+parent+" found "+this.getParent());
218        }
219        if ( i!==this.getChildIndex() ) {
220            throw new Error("child indexes don't match; expected "+i+" found "+this.getChildIndex());
221        }
222        var n = this.getChildCount(),
223            c,
224            child;
225        for (c = 0; c < n; c++) {
226            child = this.getChild(c);
227            child.sanityCheckParentAndChildIndexes(this, c);
228        }
229    },
230
231    /** BaseTree doesn't track child indexes. */
232    getChildIndex: function() {
233        return 0;
234    },
235    setChildIndex: function(index) {
236    },
237
238    /** BaseTree doesn't track parent pointers. */
239    getParent: function() {
240        return null;
241    },
242    setParent: function(t) {
243    },
244
245    getTree: function() {
246        return this;
247    },
248
249    /** Print out a whole tree not just a node */
250    toStringTree: function() {
251        if ( !this.children || this.children.length===0 ) {
252            return this.toString();
253        }
254        var buf = "",
255            i,
256            t;
257        if ( !this.isNil() ) {
258            buf += "(";
259            buf += this.toString();
260            buf += ' ';
261        }
262        for (i = 0; this.children && i < this.children.length; i++) {
263            t = this.children[i];
264            if ( i>0 ) {
265                buf += ' ';
266            }
267            buf += t.toStringTree();
268        }
269        if ( !this.isNil() ) {
270            buf += ")";
271        }
272        return buf;
273    },
274
275    getLine: function() {
276        return 0;
277    },
278
279    getCharPositionInLine: function() {
280        return 0;
281    }
282});
283