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