1/** A buffered stream of tree nodes.  Nodes can be from a tree of ANY kind.
2 *
3 *  This node stream sucks all nodes out of the tree specified in
4 *  the constructor during construction and makes pointers into
5 *  the tree using an array of Object pointers. The stream necessarily
6 *  includes pointers to DOWN and UP and EOF nodes.
7 *
8 *  This stream knows how to mark/release for backtracking.
9 *
10 *  This stream is most suitable for tree interpreters that need to
11 *  jump around a lot or for tree parsers requiring speed (at cost of memory).
12 *  There is some duplicated functionality here with UnBufferedTreeNodeStream
13 *  but just in bookkeeping, not tree walking etc...
14 *
15 *  @see UnBufferedTreeNodeStream
16 */
17org.antlr.runtime.tree.CommonTreeNodeStream = function(adaptor,
18                                                    tree,
19                                                    initialBufferSize)
20{
21    if (arguments.length===1) {
22        tree = adaptor;
23        adaptor = new org.antlr.runtime.tree.CommonTreeAdaptor();
24    }
25    if (arguments.length <= 2) {
26        initialBufferSize =
27            org.antlr.runtime.tree.CommonTreeNodeStream.DEFAULT_INITIAL_BUFFER_SIZE;
28    }
29
30    /** Reuse same DOWN, UP navigation nodes unless this is true */
31    this.uniqueNavigationNodes = false;
32
33    /** The index into the nodes list of the current node (next node
34     *  to consume).  If -1, nodes array not filled yet.
35     */
36    this.p = -1;
37
38    var Token = org.antlr.runtime.Token;
39    this.root = tree;
40    this.adaptor = adaptor;
41    this.nodes = []; //new ArrayList(initialBufferSize);
42    this.down = this.adaptor.create(Token.DOWN, "DOWN");
43    this.up = this.adaptor.create(Token.UP, "UP");
44    this.eof = this.adaptor.create(Token.EOF, "EOF");
45};
46
47org.antlr.lang.augmentObject(org.antlr.runtime.tree.CommonTreeNodeStream, {
48    DEFAULT_INITIAL_BUFFER_SIZE: 100,
49    INITIAL_CALL_STACK_SIZE: 10
50});
51
52org.antlr.lang.extend(org.antlr.runtime.tree.CommonTreeNodeStream,
53                  org.antlr.runtime.tree.TreeNodeStream,
54{
55    StreamIterator: function() {
56        var i = 0,
57            nodes = this.nodes,
58            eof = this.eof;
59
60        return {
61            hasNext: function() {
62                return i<nodes.length;
63            },
64
65            next: function() {
66                var current = i;
67                i++;
68                if ( current < nodes.length ) {
69                    return nodes[current];
70                }
71                return eof;
72            },
73
74            remove: function() {
75                throw new Error("cannot remove nodes from stream");
76            }
77        };
78    },
79
80    /** Walk tree with depth-first-search and fill nodes buffer.
81     *  Don't do DOWN, UP nodes if its a list (t is isNil).
82     */
83    fillBuffer: function(t) {
84        var reset_p = false;
85        if (org.antlr.lang.isUndefined(t)) {
86            t = this.root;
87            reset_p = true;
88        }
89
90        var nil = this.adaptor.isNil(t);
91        if ( !nil ) {
92            this.nodes.push(t); // add this node
93        }
94        // add DOWN node if t has children
95        var n = this.adaptor.getChildCount(t);
96        if ( !nil && n>0 ) {
97            this.addNavigationNode(org.antlr.runtime.Token.DOWN);
98        }
99        // and now add all its children
100        var c, child;
101        for (c=0; c<n; c++) {
102            child = this.adaptor.getChild(t,c);
103            this.fillBuffer(child);
104        }
105        // add UP node if t has children
106        if ( !nil && n>0 ) {
107            this.addNavigationNode(org.antlr.runtime.Token.UP);
108        }
109
110        if (reset_p) {
111            this.p = 0; // buffer of nodes intialized now
112        }
113    },
114
115    getNodeIndex: function(node) {
116        if ( this.p==-1 ) {
117            this.fillBuffer();
118        }
119        var i, t;
120        for (i=0; i<this.nodes.length; i++) {
121            t = this.nodes[i];
122            if ( t===node ) {
123                return i;
124            }
125        }
126        return -1;
127    },
128
129    /** As we flatten the tree, we use UP, DOWN nodes to represent
130     *  the tree structure.  When debugging we need unique nodes
131     *  so instantiate new ones when uniqueNavigationNodes is true.
132     */
133    addNavigationNode: function(ttype) {
134        var navNode = null;
135        if ( ttype===org.antlr.runtime.Token.DOWN ) {
136            if ( this.hasUniqueNavigationNodes() ) {
137                navNode = this.adaptor.create(org.antlr.runtime.Token.DOWN, "DOWN");
138            }
139            else {
140                navNode = this.down;
141            }
142        }
143        else {
144            if ( this.hasUniqueNavigationNodes() ) {
145                navNode = this.adaptor.create(org.antlr.runtime.Token.UP, "UP");
146            }
147            else {
148                navNode = this.up;
149            }
150        }
151        this.nodes.push(navNode);
152    },
153
154    get: function(i) {
155        if ( this.p===-1 ) {
156            this.fillBuffer();
157        }
158        return this.nodes[i];
159    },
160
161    LT: function(k) {
162        if ( this.p===-1 ) {
163            this.fillBuffer();
164        }
165        if ( k===0 ) {
166            return null;
167        }
168        if ( k<0 ) {
169            return this.LB(-1*k);
170        }
171        if ( (this.p+k-1) >= this.nodes.length ) {
172            return this.eof;
173        }
174        return this.nodes[this.p+k-1];
175    },
176
177    getCurrentSymbol: function() { return this.LT(1); },
178
179    /** Look backwards k nodes */
180    LB: function(k) {
181        if ( k===0 ) {
182            return null;
183        }
184        if ( (this.p-k)<0 ) {
185            return null;
186        }
187        return this.nodes[this.p-k];
188    },
189
190    getTreeSource: function() {
191        return this.root;
192    },
193
194    getSourceName: function() {
195        return this.getTokenStream().getSourceName();
196    },
197
198    getTokenStream: function() {
199        return this.tokens;
200    },
201
202    setTokenStream: function(tokens) {
203        this.tokens = tokens;
204    },
205
206    getTreeAdaptor: function() {
207        return this.adaptor;
208    },
209
210    setTreeAdaptor: function(adaptor) {
211        this.adaptor = adaptor;
212    },
213
214    hasUniqueNavigationNodes: function() {
215        return this.uniqueNavigationNodes;
216    },
217
218    setUniqueNavigationNodes: function(uniqueNavigationNodes) {
219        this.uniqueNavigationNodes = uniqueNavigationNodes;
220    },
221
222    consume: function() {
223        if ( this.p===-1 ) {
224            this.fillBuffer();
225        }
226        this.p++;
227    },
228
229    LA: function(i) {
230        return this.adaptor.getType(this.LT(i));
231    },
232
233    mark: function() {
234        if ( this.p===-1 ) {
235            this.fillBuffer();
236        }
237        this.lastMarker = this.index();
238        return this.lastMarker;
239    },
240
241    release: function(marker) {
242        // no resources to release
243    },
244
245    index: function() {
246        return this.p;
247    },
248
249    rewind: function(marker) {
250        if (!org.antlr.lang.isNumber(marker)) {
251            marker = this.lastMarker;
252        }
253        this.seek(marker);
254    },
255
256    seek: function(index) {
257        if ( this.p===-1 ) {
258            this.fillBuffer();
259        }
260        this.p = index;
261    },
262
263    /** Make stream jump to a new location, saving old location.
264     *  Switch back with pop().
265     */
266    push: function(index) {
267        if ( !this.calls ) {
268            this.calls = [];
269        }
270        this.calls.push(this.p); // save current index
271        this.seek(index);
272    },
273
274    /** Seek back to previous index saved during last push() call.
275     *  Return top of stack (return index).
276     */
277    pop: function() {
278        var ret = this.calls.pop();
279        this.seek(ret);
280        return ret;
281    },
282
283    reset: function() {
284        this.p = 0;
285        this.lastMarker = 0;
286        if (this.calls) {
287            this.calls = [];
288        }
289    },
290
291    size: function() {
292        if ( this.p===-1 ) {
293            this.fillBuffer();
294        }
295        return this.nodes.length;
296    },
297
298    iterator: function() {
299        if ( this.p===-1 ) {
300            this.fillBuffer();
301        }
302        return this.StreamIterator();
303    },
304
305    replaceChildren: function(parent, startChildIndex, stopChildIndex, t) {
306        if ( parent ) {
307            this.adaptor.replaceChildren(parent, startChildIndex, stopChildIndex, t);
308        }
309    },
310
311    /** Debugging */
312    toTokenString: function(start, stop) {
313        if ( this.p===-1 ) {
314            this.fillBuffer();
315        }
316        var buf='', i, t;
317        for (i = start; i < this.nodes.length && i <= stop; i++) {
318            t = this.nodes[i];
319            buf += " "+this.adaptor.getToken(t);
320        }
321        return buf;
322    },
323
324    /** Used for testing, just return the token type stream */
325    toString: function(start, stop) {
326        var buf = "",
327            text,
328            t,
329            i;
330        if (arguments.length===0) {
331            if ( this.p===-1 ) {
332                this.fillBuffer();
333            }
334            for (i = 0; i < this.nodes.length; i++) {
335                t = this.nodes[i];
336                buf += " ";
337                buf += this.adaptor.getType(t);
338            }
339            return buf;
340        } else {
341            if ( !org.antlr.lang.isNumber(start) || !org.antlr.lang.isNumber(stop) ) {
342                return null;
343            }
344            if ( this.p===-1 ) {
345                this.fillBuffer();
346            }
347            // if we have the token stream, use that to dump text in order
348            var beginTokenIndex,
349                endTokenIndex;
350            if ( this.tokens ) {
351                beginTokenIndex = this.adaptor.getTokenStartIndex(start);
352                endTokenIndex = this.adaptor.getTokenStopIndex(stop);
353                // if it's a tree, use start/stop index from start node
354                // else use token range from start/stop nodes
355                if ( this.adaptor.getType(stop)===org.antlr.runtime.Token.UP ) {
356                    endTokenIndex = this.adaptor.getTokenStopIndex(start);
357                }
358                else if ( this.adaptor.getType(stop)==org.antlr.runtime.Token.EOF )
359                {
360                    endTokenIndex = this.size()-2; // don't use EOF
361                }
362                return this.tokens.toString(beginTokenIndex, endTokenIndex);
363            }
364            // walk nodes looking for start
365            t = null;
366            i = 0;
367            for (; i < this.nodes.length; i++) {
368                t = this.nodes[i];
369                if ( t===start ) {
370                    break;
371                }
372            }
373            // now walk until we see stop, filling string buffer with text
374            buf = text = "";
375            t = this.nodes[i];
376            while ( t!==stop ) {
377                text = this.adaptor.getText(t);
378                if ( !org.antlr.lang.isString(text) ) {
379                    text = " "+this.adaptor.getType(t).toString();
380                }
381                buf += text;
382                i++;
383                t = nodes[i];
384            }
385            // include stop node too
386            text = this.adaptor.getText(stop);
387            if ( !org.antlr.lang.isString(text) ) {
388                text = " "+this.adaptor.getType(stop).toString();
389            }
390            buf += text;
391            return buf;
392        }
393    }
394});
395