Home | History | Annotate | Download | only in include
      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