2 /// Definition of the ANTLR3 common tree node stream.
\r
5 #ifndef _ANTLR3_COMMON_TREE_NODE_STREAM__H
\r
6 #define _ANTLR3_COMMON_TREE_NODE_STREAM__H
\r
8 // [The "BSD licence"]
\r
9 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
\r
10 // http://www.temporal-wave.com
\r
11 // http://www.linkedin.com/in/jimidle
\r
13 // All rights reserved.
\r
15 // Redistribution and use in source and binary forms, with or without
\r
16 // modification, are permitted provided that the following conditions
\r
18 // 1. Redistributions of source code must retain the above copyright
\r
19 // notice, this list of conditions and the following disclaimer.
\r
20 // 2. Redistributions in binary form must reproduce the above copyright
\r
21 // notice, this list of conditions and the following disclaimer in the
\r
22 // documentation and/or other materials provided with the distribution.
\r
23 // 3. The name of the author may not be used to endorse or promote products
\r
24 // derived from this software without specific prior written permission.
\r
26 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
\r
27 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
\r
28 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
\r
29 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
\r
30 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
\r
31 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
\r
32 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
\r
33 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
\r
34 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
\r
35 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
\r
37 #include <antlr3defs.h>
\r
38 #include <antlr3commontreeadaptor.h>
\r
39 #include <antlr3commontree.h>
\r
40 #include <antlr3collections.h>
\r
41 #include <antlr3intstream.h>
\r
42 #include <antlr3string.h>
\r
44 /// Token buffer initial size settings ( will auto increase)
\r
46 #define DEFAULT_INITIAL_BUFFER_SIZE 100
\r
47 #define INITIAL_CALL_STACK_SIZE 10
\r
53 typedef struct ANTLR3_TREE_NODE_STREAM_struct
\r
55 /// Any interface that implements this interface (is a
\r
56 /// super structure containing this structure), may store the pointer
\r
57 /// to itself here in the super pointer, which is not used by
\r
58 /// the tree node stream. This will point to an implementation
\r
59 /// of ANTLR3_COMMON_TREE_NODE_STREAM in this case.
\r
61 pANTLR3_COMMON_TREE_NODE_STREAM ctns;
\r
63 /// All input streams implement the ANTLR3_INT_STREAM interface...
\r
65 pANTLR3_INT_STREAM istream;
\r
67 /// Get tree node at current input pointer + i ahead where i=1 is next node.
\r
68 /// i<0 indicates nodes in the past. So LT(-1) is previous node, but
\r
69 /// implementations are not required to provide results for k < -1.
\r
70 /// LT(0) is undefined. For i>=n, return null.
\r
71 /// Return NULL for LT(0) and any index that results in an absolute address
\r
72 /// that is negative (beyond the start of the list).
\r
74 /// This is analogous to the LT() method of the TokenStream, but this
\r
75 /// returns a tree node instead of a token. Makes code gen identical
\r
76 /// for both parser and tree grammars. :)
\r
78 pANTLR3_BASE_TREE (*_LT) (struct ANTLR3_TREE_NODE_STREAM_struct * tns, ANTLR3_INT32 k);
\r
80 /// Where is this stream pulling nodes from? This is not the name, but
\r
81 /// the object that provides node objects.
\r
83 pANTLR3_BASE_TREE (*getTreeSource) (struct ANTLR3_TREE_NODE_STREAM_struct * tns);
\r
85 /// What adaptor can tell me how to interpret/navigate nodes and
\r
86 /// trees. E.g., get text of a node.
\r
88 pANTLR3_BASE_TREE_ADAPTOR (*getTreeAdaptor) (struct ANTLR3_TREE_NODE_STREAM_struct * tns);
\r
90 /// As we flatten the tree, we use UP, DOWN nodes to represent
\r
91 /// the tree structure. When debugging we need unique nodes
\r
92 /// so we have to instantiate new ones. When doing normal tree
\r
93 /// parsing, it's slow and a waste of memory to create unique
\r
94 /// navigation nodes. Default should be false;
\r
96 void (*setUniqueNavigationNodes) (struct ANTLR3_TREE_NODE_STREAM_struct * tns, ANTLR3_BOOLEAN uniqueNavigationNodes);
\r
98 pANTLR3_STRING (*toString) (struct ANTLR3_TREE_NODE_STREAM_struct * tns);
\r
100 /// Return the text of all nodes from start to stop, inclusive.
\r
101 /// If the stream does not buffer all the nodes then it can still
\r
102 /// walk recursively from start until stop. You can always return
\r
103 /// null or "" too, but users should not access $ruleLabel.text in
\r
104 /// an action of course in that case.
\r
106 pANTLR3_STRING (*toStringSS) (struct ANTLR3_TREE_NODE_STREAM_struct * tns, pANTLR3_BASE_TREE start, pANTLR3_BASE_TREE stop);
\r
108 /// Return the text of all nodes from start to stop, inclusive, into the
\r
109 /// supplied buffer.
\r
110 /// If the stream does not buffer all the nodes then it can still
\r
111 /// walk recursively from start until stop. You can always return
\r
112 /// null or "" too, but users should not access $ruleLabel.text in
\r
113 /// an action of course in that case.
\r
115 void (*toStringWork) (struct ANTLR3_TREE_NODE_STREAM_struct * tns, pANTLR3_BASE_TREE start, pANTLR3_BASE_TREE stop, pANTLR3_STRING buf);
\r
117 /// Release up any and all space the the interface allocate, including for this structure.
\r
119 void (*free) (struct ANTLR3_TREE_NODE_STREAM_struct * tns);
\r
121 /// Get a tree node at an absolute index i; 0..n-1.
\r
122 /// If you don't want to buffer up nodes, then this method makes no
\r
125 pANTLR3_BASE_TREE (*get) (struct ANTLR3_TREE_NODE_STREAM_struct * tns, ANTLR3_INT32 i);
\r
127 // REWRITING TREES (used by tree parser)
\r
129 /// Replace from start to stop child index of parent with t, which might
\r
130 /// be a list. Number of children may be different
\r
131 /// after this call. The stream is notified because it is walking the
\r
132 /// tree and might need to know you are monkeying with the underlying
\r
133 /// tree. Also, it might be able to modify the node stream to avoid
\r
134 /// restreaming for future phases.
\r
136 /// If parent is null, don't do anything; must be at root of overall tree.
\r
137 /// Can't replace whatever points to the parent externally. Do nothing.
\r
139 void (*replaceChildren) (struct ANTLR3_TREE_NODE_STREAM_struct * tns, pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE t);
\r
142 ANTLR3_TREE_NODE_STREAM;
\r
144 typedef struct ANTLR3_COMMON_TREE_NODE_STREAM_struct
\r
146 /// Any interface that implements this interface (is a
\r
147 /// super structure containing this structure), may store the pointer
\r
148 /// to itself here in the super pointer, which is not used by
\r
149 /// the common tree node stream.
\r
153 /// Pointer to the tree node stream interface
\r
155 pANTLR3_TREE_NODE_STREAM tnstream;
\r
157 /// String factory for use by anything that wishes to create strings
\r
158 /// such as a tree representation or some copy of the text etc.
\r
160 pANTLR3_STRING_FACTORY stringFactory;
\r
162 /// Dummy tree node that indicates a descent into a child
\r
163 /// tree. Initialized by a call to create a new interface.
\r
165 ANTLR3_COMMON_TREE DOWN;
\r
167 /// Dummy tree node that indicates a descent up to a parent
\r
168 /// tree. Initialized by a call to create a new interface.
\r
170 ANTLR3_COMMON_TREE UP;
\r
172 /// Dummy tree node that indicates the termination point of the
\r
173 /// tree. Initialized by a call to create a new interface.
\r
175 ANTLR3_COMMON_TREE EOF_NODE;
\r
177 /// Dummy node that is returned if we need to indicate an invalid node
\r
178 /// for any reason.
\r
180 ANTLR3_COMMON_TREE INVALID_NODE;
\r
182 /// The complete mapping from stream index to tree node.
\r
183 /// This buffer includes pointers to DOWN, UP, and EOF nodes.
\r
184 /// It is built upon ctor invocation. The elements are type
\r
185 /// Object as we don't what the trees look like.
\r
187 /// Load upon first need of the buffer so we can set token types
\r
188 /// of interest for reverseIndexing. Slows us down a wee bit to
\r
189 /// do all of the if p==-1 testing everywhere though, though in C
\r
190 /// you won't really be able to measure this.
\r
192 /// Must be freed when the tree node stream is torn down.
\r
194 pANTLR3_VECTOR nodes;
\r
196 /// If set to ANTLR3_TRUE then the navigation nodes UP, DOWN are
\r
197 /// duplicated rather than reused within the tree.
\r
199 ANTLR3_BOOLEAN uniqueNavigationNodes;
\r
201 /// Which tree are we navigating ?
\r
203 pANTLR3_BASE_TREE root;
\r
205 /// Pointer to tree adaptor interface that manipulates/builds
\r
208 pANTLR3_BASE_TREE_ADAPTOR adaptor;
\r
210 /// As we walk down the nodes, we must track parent nodes so we know
\r
211 /// where to go after walking the last child of a node. When visiting
\r
212 /// a child, push current node and current index (current index
\r
213 /// is first stored in the tree node structure to avoid two stacks.
\r
215 pANTLR3_STACK nodeStack;
\r
217 /// The current index into the nodes vector of the current tree
\r
218 /// we are parsing and possibly rewriting.
\r
222 /// Which node are we currently visiting?
\r
224 pANTLR3_BASE_TREE currentNode;
\r
226 /// Which node did we last visit? Used for LT(-1)
\r
228 pANTLR3_BASE_TREE previousNode;
\r
230 /// Which child are we currently visiting? If -1 we have not visited
\r
231 /// this node yet; next consume() request will set currentIndex to 0.
\r
233 ANTLR3_INT32 currentChildIndex;
\r
235 /// What node index did we just consume? i=0..n-1 for n node trees.
\r
236 /// IntStream.next is hence 1 + this value. Size will be same.
\r
238 ANTLR3_MARKER absoluteNodeIndex;
\r
240 /// Buffer tree node stream for use with LT(i). This list grows
\r
241 /// to fit new lookahead depths, but consume() wraps like a circular
\r
244 pANTLR3_BASE_TREE * lookAhead;
\r
246 /// Number of elements available in the lookahead buffer at any point in
\r
247 /// time. This is the current size of the array.
\r
249 ANTLR3_UINT32 lookAheadLength;
\r
251 /// lookAhead[head] is the first symbol of lookahead, LT(1).
\r
253 ANTLR3_UINT32 head;
\r
255 /// Add new lookahead at lookahead[tail]. tail wraps around at the
\r
256 /// end of the lookahead buffer so tail could be less than head.
\r
258 ANTLR3_UINT32 tail;
\r
260 /// Calls to mark() may be nested so we have to track a stack of
\r
261 /// them. The marker is an index into this stack. Index 0 is
\r
262 /// the first marker. This is a List<TreeWalkState>
\r
264 pANTLR3_VECTOR markers;
\r
268 void (*fill) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns, ANTLR3_INT32 k);
\r
270 void (*addLookahead) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns, pANTLR3_BASE_TREE node);
\r
272 ANTLR3_BOOLEAN (*hasNext) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns);
\r
274 pANTLR3_BASE_TREE (*next) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns);
\r
276 pANTLR3_BASE_TREE (*handleRootnode) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns);
\r
278 pANTLR3_BASE_TREE (*visitChild) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns, ANTLR3_UINT32 child);
\r
280 void (*addNavigationNode) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns, ANTLR3_UINT32 ttype);
\r
282 pANTLR3_BASE_TREE (*newDownNode) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns);
\r
284 pANTLR3_BASE_TREE (*newUpNode) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns);
\r
286 void (*walkBackToMostRecentNodeWithUnvisitedChildren)
\r
287 (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns);
\r
289 ANTLR3_BOOLEAN (*hasUniqueNavigationNodes) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns);
\r
291 ANTLR3_UINT32 (*getLookaheadSize) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns);
\r
293 void (*push) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns, ANTLR3_INT32 index);
\r
295 ANTLR3_INT32 (*pop) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns);
\r
297 void (*reset) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns);
\r
299 void (*free) (struct ANTLR3_COMMON_TREE_NODE_STREAM_struct * ctns);
\r
301 /// Indicates whether this node stream was derived from a prior
\r
302 /// node stream to be used by a rewriting tree parser for instance.
\r
303 /// If this flag is set to ANTLR3_TRUE, then when this stream is
\r
304 /// closed it will not free the root tree as this tree always
\r
305 /// belongs to the origniating node stream.
\r
307 ANTLR3_BOOLEAN isRewriter;
\r
310 ANTLR3_COMMON_TREE_NODE_STREAM;
\r
312 /** This structure is used to save the state information in the treenodestream
\r
313 * when walking ahead with cyclic DFA or for syntactic predicates,
\r
314 * we need to record the state of the tree node stream. This
\r
315 * class wraps up the current state of the CommonTreeNodeStream.
\r
316 * Calling mark() will push another of these on the markers stack.
\r
318 typedef struct ANTLR3_TREE_WALK_STATE_struct
\r
320 ANTLR3_UINT32 currentChildIndex;
\r
321 ANTLR3_MARKER absoluteNodeIndex;
\r
322 pANTLR3_BASE_TREE currentNode;
\r
323 pANTLR3_BASE_TREE previousNode;
\r
324 ANTLR3_UINT32 nodeStackSize;
\r
325 pANTLR3_BASE_TREE * lookAhead;
\r
326 ANTLR3_UINT32 lookAheadLength;
\r
327 ANTLR3_UINT32 tail;
\r
328 ANTLR3_UINT32 head;
\r
330 ANTLR3_TREE_WALK_STATE;
\r