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