Home | History | Annotate | Download | only in src
      1 /// \file
      2 /// Defines the implementation of the common node stream the default
      3 /// tree node stream used by ANTLR.
      4 ///
      5 
      6 // [The "BSD licence"]
      7 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
      8 // http://www.temporal-wave.com
      9 // http://www.linkedin.com/in/jimidle
     10 //
     11 // All rights reserved.
     12 //
     13 // Redistribution and use in source and binary forms, with or without
     14 // modification, are permitted provided that the following conditions
     15 // are met:
     16 // 1. Redistributions of source code must retain the above copyright
     17 //    notice, this list of conditions and the following disclaimer.
     18 // 2. Redistributions in binary form must reproduce the above copyright
     19 //    notice, this list of conditions and the following disclaimer in the
     20 //    documentation and/or other materials provided with the distribution.
     21 // 3. The name of the author may not be used to endorse or promote products
     22 //    derived from this software without specific prior written permission.
     23 //
     24 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     25 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     26 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     27 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     28 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     29 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     30 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     31 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     32 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     33 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     34 
     35 #include    <antlr3commontreenodestream.h>
     36 
     37 #ifdef	ANTLR3_WINDOWS
     38 #pragma warning( disable : 4100 )
     39 #endif
     40 
     41 // COMMON TREE STREAM API
     42 //
     43 static	void						addNavigationNode			(pANTLR3_COMMON_TREE_NODE_STREAM ctns, ANTLR3_UINT32 ttype);
     44 static	ANTLR3_BOOLEAN				hasUniqueNavigationNodes	(pANTLR3_COMMON_TREE_NODE_STREAM ctns);
     45 static	pANTLR3_BASE_TREE			newDownNode					(pANTLR3_COMMON_TREE_NODE_STREAM ctns);
     46 static	pANTLR3_BASE_TREE			newUpNode					(pANTLR3_COMMON_TREE_NODE_STREAM ctns);
     47 static	void						reset						(pANTLR3_COMMON_TREE_NODE_STREAM ctns);
     48 static	void						push						(pANTLR3_COMMON_TREE_NODE_STREAM ctns, ANTLR3_INT32 index);
     49 static	ANTLR3_INT32				pop							(pANTLR3_COMMON_TREE_NODE_STREAM ctns);
     50 //static	ANTLR3_INT32				index						(pANTLR3_COMMON_TREE_NODE_STREAM ctns);
     51 static	ANTLR3_UINT32				getLookaheadSize			(pANTLR3_COMMON_TREE_NODE_STREAM ctns);
     52 // TREE NODE STREAM API
     53 //
     54 static	pANTLR3_BASE_TREE_ADAPTOR   getTreeAdaptor				(pANTLR3_TREE_NODE_STREAM tns);
     55 static	pANTLR3_BASE_TREE			getTreeSource				(pANTLR3_TREE_NODE_STREAM tns);
     56 static	pANTLR3_BASE_TREE			_LT							(pANTLR3_TREE_NODE_STREAM tns, ANTLR3_INT32 k);
     57 static	pANTLR3_BASE_TREE			get							(pANTLR3_TREE_NODE_STREAM tns, ANTLR3_INT32 k);
     58 static	void						setUniqueNavigationNodes	(pANTLR3_TREE_NODE_STREAM tns, ANTLR3_BOOLEAN uniqueNavigationNodes);
     59 static	pANTLR3_STRING				toString					(pANTLR3_TREE_NODE_STREAM tns);
     60 static	pANTLR3_STRING				toStringSS					(pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE start, pANTLR3_BASE_TREE stop);
     61 static	void						toStringWork				(pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE start, pANTLR3_BASE_TREE stop, pANTLR3_STRING buf);
     62 static	void						replaceChildren				(pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE t);
     63 
     64 // INT STREAM API
     65 //
     66 static	void						consume						(pANTLR3_INT_STREAM is);
     67 static	ANTLR3_MARKER				tindex						(pANTLR3_INT_STREAM is);
     68 static	ANTLR3_UINT32				_LA							(pANTLR3_INT_STREAM is, ANTLR3_INT32 i);
     69 static	ANTLR3_MARKER				mark						(pANTLR3_INT_STREAM is);
     70 static	void						release						(pANTLR3_INT_STREAM is, ANTLR3_MARKER marker);
     71 static	void						rewindMark					(pANTLR3_INT_STREAM is, ANTLR3_MARKER marker);
     72 static	void						rewindLast					(pANTLR3_INT_STREAM is);
     73 static	void						seek						(pANTLR3_INT_STREAM is, ANTLR3_MARKER index);
     74 static	ANTLR3_UINT32				size						(pANTLR3_INT_STREAM is);
     75 
     76 
     77 // Helper functions
     78 //
     79 static	void						fillBuffer					(pANTLR3_COMMON_TREE_NODE_STREAM ctns, pANTLR3_BASE_TREE t);
     80 static	void						fillBufferRoot				(pANTLR3_COMMON_TREE_NODE_STREAM ctns);
     81 
     82 // Constructors
     83 //
     84 static	void						antlr3TreeNodeStreamFree			(pANTLR3_TREE_NODE_STREAM tns);
     85 static	void						antlr3CommonTreeNodeStreamFree		(pANTLR3_COMMON_TREE_NODE_STREAM ctns);
     86 
     87 ANTLR3_API pANTLR3_TREE_NODE_STREAM
     88 antlr3TreeNodeStreamNew()
     89 {
     90     pANTLR3_TREE_NODE_STREAM stream;
     91 
     92     // Memory for the interface structure
     93     //
     94     stream  = (pANTLR3_TREE_NODE_STREAM) ANTLR3_CALLOC(1, sizeof(ANTLR3_TREE_NODE_STREAM));
     95 
     96     if	(stream == NULL)
     97     {
     98 		return	NULL;
     99     }
    100 
    101     // Install basic API
    102     //
    103 	stream->replaceChildren = replaceChildren;
    104     stream->free			= antlr3TreeNodeStreamFree;
    105 
    106     return stream;
    107 }
    108 
    109 static void
    110 antlr3TreeNodeStreamFree(pANTLR3_TREE_NODE_STREAM stream)
    111 {
    112     ANTLR3_FREE(stream);
    113 }
    114 
    115 ANTLR3_API pANTLR3_COMMON_TREE_NODE_STREAM
    116 antlr3CommonTreeNodeStreamNewTree(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 hint)
    117 {
    118 	pANTLR3_COMMON_TREE_NODE_STREAM stream;
    119 
    120 	stream = antlr3CommonTreeNodeStreamNew(tree->strFactory, hint);
    121 
    122 	if	(stream == NULL)
    123 	{
    124 		return	NULL;
    125 	}
    126 	stream->root    = tree;
    127 
    128 	return stream;
    129 }
    130 
    131 ANTLR3_API pANTLR3_COMMON_TREE_NODE_STREAM
    132 antlr3CommonTreeNodeStreamNewStream(pANTLR3_COMMON_TREE_NODE_STREAM inStream)
    133 {
    134 	pANTLR3_COMMON_TREE_NODE_STREAM stream;
    135 
    136 	// Memory for the interface structure
    137 	//
    138 	stream  = (pANTLR3_COMMON_TREE_NODE_STREAM) ANTLR3_CALLOC(1, sizeof(ANTLR3_COMMON_TREE_NODE_STREAM));
    139 
    140 	if	(stream == NULL)
    141 	{
    142 		return	NULL;
    143 	}
    144 
    145 	// Copy in all the reusable parts of the originating stream and create new
    146 	// pieces where necessary.
    147 	//
    148 
    149 	// String factory for tree walker
    150 	//
    151 	stream->stringFactory		= inStream->stringFactory;
    152 
    153 	// Create an adaptor for the common tree node stream
    154 	//
    155 	stream->adaptor				= inStream->adaptor;
    156 
    157 	// Create space for the tree node stream interface
    158 	//
    159 	stream->tnstream	    = antlr3TreeNodeStreamNew();
    160 
    161 	if	(stream->tnstream == NULL)
    162 	{
    163 		stream->free				(stream);
    164 
    165 		return	NULL;
    166 	}
    167 
    168 	// Create space for the INT_STREAM interface
    169 	//
    170 	stream->tnstream->istream		    =  antlr3IntStreamNew();
    171 
    172 	if	(stream->tnstream->istream == NULL)
    173 	{
    174 		stream->tnstream->free		(stream->tnstream);
    175 		stream->free				(stream);
    176 
    177 		return	NULL;
    178 	}
    179 
    180 	// Install the common tree node stream API
    181 	//
    182 	stream->addNavigationNode		    =  addNavigationNode;
    183 	stream->hasUniqueNavigationNodes    =  hasUniqueNavigationNodes;
    184 	stream->newDownNode					=  newDownNode;
    185 	stream->newUpNode					=  newUpNode;
    186 	stream->reset						=  reset;
    187 	stream->push						=  push;
    188 	stream->pop							=  pop;
    189 	stream->getLookaheadSize			=  getLookaheadSize;
    190 
    191 	stream->free			    =  antlr3CommonTreeNodeStreamFree;
    192 
    193 	// Install the tree node stream API
    194 	//
    195 	stream->tnstream->getTreeAdaptor			=  getTreeAdaptor;
    196 	stream->tnstream->getTreeSource				=  getTreeSource;
    197 	stream->tnstream->_LT						=  _LT;
    198 	stream->tnstream->setUniqueNavigationNodes	=  setUniqueNavigationNodes;
    199 	stream->tnstream->toString					=  toString;
    200 	stream->tnstream->toStringSS				=  toStringSS;
    201 	stream->tnstream->toStringWork				=  toStringWork;
    202 	stream->tnstream->get						=  get;
    203 
    204 	// Install INT_STREAM interface
    205 	//
    206 	stream->tnstream->istream->consume	    =  consume;
    207 	stream->tnstream->istream->index	    =  tindex;
    208 	stream->tnstream->istream->_LA			=  _LA;
    209 	stream->tnstream->istream->mark			=  mark;
    210 	stream->tnstream->istream->release	    =  release;
    211 	stream->tnstream->istream->rewind	    =  rewindMark;
    212 	stream->tnstream->istream->rewindLast   =  rewindLast;
    213 	stream->tnstream->istream->seek			=  seek;
    214 	stream->tnstream->istream->size			=  size;
    215 
    216 	// Initialize data elements of INT stream
    217 	//
    218 	stream->tnstream->istream->type			= ANTLR3_COMMONTREENODE;
    219 	stream->tnstream->istream->super	    =  (stream->tnstream);
    220 
    221 	// Initialize data elements of TREE stream
    222 	//
    223 	stream->tnstream->ctns =  stream;
    224 
    225 	// Initialize data elements of the COMMON TREE NODE stream
    226 	//
    227 	stream->super					= NULL;
    228 	stream->uniqueNavigationNodes	= ANTLR3_FALSE;
    229 	stream->markers					= NULL;
    230 	stream->nodeStack				= inStream->nodeStack;
    231 
    232 	// Create the node list map
    233 	//
    234 	stream->nodes	= antlr3VectorNew(DEFAULT_INITIAL_BUFFER_SIZE);
    235 	stream->p		= -1;
    236 
    237 	// Install the navigation nodes
    238 	//
    239 
    240 	// Install the navigation nodes
    241 	//
    242 	antlr3SetCTAPI(&(stream->UP));
    243 	antlr3SetCTAPI(&(stream->DOWN));
    244 	antlr3SetCTAPI(&(stream->EOF_NODE));
    245 	antlr3SetCTAPI(&(stream->INVALID_NODE));
    246 
    247 	stream->UP.token						= inStream->UP.token;
    248 	inStream->UP.token->strFactory			= stream->stringFactory;
    249 	stream->DOWN.token						= inStream->DOWN.token;
    250 	inStream->DOWN.token->strFactory		= stream->stringFactory;
    251 	stream->EOF_NODE.token					= inStream->EOF_NODE.token;
    252 	inStream->EOF_NODE.token->strFactory	= stream->stringFactory;
    253 	stream->INVALID_NODE.token				= inStream->INVALID_NODE.token;
    254 	inStream->INVALID_NODE.token->strFactory= stream->stringFactory;
    255 
    256 	// Reuse the root tree of the originating stream
    257 	//
    258 	stream->root		= inStream->root;
    259 
    260 	// Signal that this is a rewriting stream so we don't
    261 	// free the originating tree. Anything that we rewrite or
    262 	// duplicate here will be done through the adaptor or
    263 	// the original tree factory.
    264 	//
    265 	stream->isRewriter	= ANTLR3_TRUE;
    266 	return stream;
    267 }
    268 
    269 ANTLR3_API pANTLR3_COMMON_TREE_NODE_STREAM
    270 antlr3CommonTreeNodeStreamNew(pANTLR3_STRING_FACTORY strFactory, ANTLR3_UINT32 hint)
    271 {
    272 	pANTLR3_COMMON_TREE_NODE_STREAM stream;
    273 	pANTLR3_COMMON_TOKEN			token;
    274 
    275 	// Memory for the interface structure
    276 	//
    277 	stream  = (pANTLR3_COMMON_TREE_NODE_STREAM) ANTLR3_CALLOC(1, sizeof(ANTLR3_COMMON_TREE_NODE_STREAM));
    278 
    279 	if	(stream == NULL)
    280 	{
    281 		return	NULL;
    282 	}
    283 
    284 	// String factory for tree walker
    285 	//
    286 	stream->stringFactory		= strFactory;
    287 
    288 	// Create an adaptor for the common tree node stream
    289 	//
    290 	stream->adaptor				= ANTLR3_TREE_ADAPTORNew(strFactory);
    291 
    292 	if	(stream->adaptor == NULL)
    293 	{
    294 		stream->free(stream);
    295 		return	NULL;
    296 	}
    297 
    298 	// Create space for the tree node stream interface
    299 	//
    300 	stream->tnstream	    = antlr3TreeNodeStreamNew();
    301 
    302 	if	(stream->tnstream == NULL)
    303 	{
    304 		stream->adaptor->free		(stream->adaptor);
    305 		stream->free				(stream);
    306 
    307 		return	NULL;
    308 	}
    309 
    310 	// Create space for the INT_STREAM interface
    311 	//
    312 	stream->tnstream->istream		    =  antlr3IntStreamNew();
    313 
    314 	if	(stream->tnstream->istream == NULL)
    315 	{
    316 		stream->adaptor->free		(stream->adaptor);
    317 		stream->tnstream->free		(stream->tnstream);
    318 		stream->free				(stream);
    319 
    320 		return	NULL;
    321 	}
    322 
    323 	// Install the common tree node stream API
    324 	//
    325 	stream->addNavigationNode		    =  addNavigationNode;
    326 	stream->hasUniqueNavigationNodes    =  hasUniqueNavigationNodes;
    327 	stream->newDownNode					=  newDownNode;
    328 	stream->newUpNode					=  newUpNode;
    329 	stream->reset						=  reset;
    330 	stream->push						=  push;
    331 	stream->pop							=  pop;
    332 
    333 	stream->free			    =  antlr3CommonTreeNodeStreamFree;
    334 
    335 	// Install the tree node stream API
    336 	//
    337 	stream->tnstream->getTreeAdaptor			=  getTreeAdaptor;
    338 	stream->tnstream->getTreeSource				=  getTreeSource;
    339 	stream->tnstream->_LT						=  _LT;
    340 	stream->tnstream->setUniqueNavigationNodes	=  setUniqueNavigationNodes;
    341 	stream->tnstream->toString					=  toString;
    342 	stream->tnstream->toStringSS				=  toStringSS;
    343 	stream->tnstream->toStringWork				=  toStringWork;
    344 	stream->tnstream->get						=  get;
    345 
    346 	// Install INT_STREAM interface
    347 	//
    348 	stream->tnstream->istream->consume	    =  consume;
    349 	stream->tnstream->istream->index	    =  tindex;
    350 	stream->tnstream->istream->_LA			=  _LA;
    351 	stream->tnstream->istream->mark			=  mark;
    352 	stream->tnstream->istream->release	    =  release;
    353 	stream->tnstream->istream->rewind	    =  rewindMark;
    354 	stream->tnstream->istream->rewindLast   =  rewindLast;
    355 	stream->tnstream->istream->seek			=  seek;
    356 	stream->tnstream->istream->size			=  size;
    357 
    358 	// Initialize data elements of INT stream
    359 	//
    360 	stream->tnstream->istream->type			= ANTLR3_COMMONTREENODE;
    361 	stream->tnstream->istream->super	    =  (stream->tnstream);
    362 
    363 	// Initialize data elements of TREE stream
    364 	//
    365 	stream->tnstream->ctns =  stream;
    366 
    367 	// Initialize data elements of the COMMON TREE NODE stream
    368 	//
    369 	stream->super					= NULL;
    370 	stream->uniqueNavigationNodes	= ANTLR3_FALSE;
    371 	stream->markers					= NULL;
    372 	stream->nodeStack				= antlr3StackNew(INITIAL_CALL_STACK_SIZE);
    373 
    374 	// Create the node list map
    375 	//
    376 	if	(hint == 0)
    377 	{
    378 		hint = DEFAULT_INITIAL_BUFFER_SIZE;
    379 	}
    380 	stream->nodes	= antlr3VectorNew(hint);
    381 	stream->p		= -1;
    382 
    383 	// Install the navigation nodes
    384 	//
    385 	antlr3SetCTAPI(&(stream->UP));
    386 	antlr3SetCTAPI(&(stream->DOWN));
    387 	antlr3SetCTAPI(&(stream->EOF_NODE));
    388 	antlr3SetCTAPI(&(stream->INVALID_NODE));
    389 
    390 	token						= antlr3CommonTokenNew(ANTLR3_TOKEN_UP);
    391 	token->strFactory			= strFactory;
    392 	token->textState			= ANTLR3_TEXT_CHARP;
    393 	token->tokText.chars		= (pANTLR3_UCHAR)"UP";
    394 	stream->UP.token			= token;
    395 
    396 	token						= antlr3CommonTokenNew(ANTLR3_TOKEN_DOWN);
    397 	token->strFactory			= strFactory;
    398 	token->textState			= ANTLR3_TEXT_CHARP;
    399 	token->tokText.chars		= (pANTLR3_UCHAR)"DOWN";
    400 	stream->DOWN.token			= token;
    401 
    402 	token						= antlr3CommonTokenNew(ANTLR3_TOKEN_EOF);
    403 	token->strFactory			= strFactory;
    404 	token->textState			= ANTLR3_TEXT_CHARP;
    405 	token->tokText.chars		= (pANTLR3_UCHAR)"EOF";
    406 	stream->EOF_NODE.token		= token;
    407 
    408 	token						= antlr3CommonTokenNew(ANTLR3_TOKEN_INVALID);
    409 	token->strFactory			= strFactory;
    410 	token->textState			= ANTLR3_TEXT_CHARP;
    411 	token->tokText.chars		= (pANTLR3_UCHAR)"INVALID";
    412 	stream->INVALID_NODE.token	= token;
    413 
    414 
    415 	return  stream;
    416 }
    417 
    418 /// Free up any resources that belong to this common tree node stream.
    419 ///
    420 static	void			    antlr3CommonTreeNodeStreamFree  (pANTLR3_COMMON_TREE_NODE_STREAM ctns)
    421 {
    422 
    423 	// If this is a rewrting stream, then certain resources
    424 	// belong to the originating node stream and we do not
    425 	// free them here.
    426 	//
    427 	if	(ctns->isRewriter != ANTLR3_TRUE)
    428 	{
    429 		ctns->adaptor			->free  (ctns->adaptor);
    430 
    431 		if	(ctns->nodeStack != NULL)
    432 		{
    433 			ctns->nodeStack->free(ctns->nodeStack);
    434 		}
    435 
    436 		ANTLR3_FREE(ctns->INVALID_NODE.token);
    437 		ANTLR3_FREE(ctns->EOF_NODE.token);
    438 		ANTLR3_FREE(ctns->DOWN.token);
    439 		ANTLR3_FREE(ctns->UP.token);
    440 	}
    441 
    442 	if	(ctns->nodes != NULL)
    443 	{
    444 		ctns->nodes			->free  (ctns->nodes);
    445 	}
    446 	ctns->tnstream->istream ->free  (ctns->tnstream->istream);
    447     ctns->tnstream			->free  (ctns->tnstream);
    448 
    449 
    450     ANTLR3_FREE(ctns);
    451 }
    452 
    453 // ------------------------------------------------------------------------------
    454 // Local helpers
    455 //
    456 
    457 /// Walk and fill the tree node buffer from the root tree
    458 ///
    459 static void
    460 fillBufferRoot(pANTLR3_COMMON_TREE_NODE_STREAM ctns)
    461 {
    462 	// Call the generic buffer routine with the root as the
    463 	// argument
    464 	//
    465 	fillBuffer(ctns, ctns->root);
    466 	ctns->p = 0;					// Indicate we are at buffer start
    467 }
    468 
    469 /// Walk tree with depth-first-search and fill nodes buffer.
    470 /// Don't add in DOWN, UP nodes if the supplied tree is a list (t is isNilNode)
    471 // such as the root tree is.
    472 ///
    473 static void
    474 fillBuffer(pANTLR3_COMMON_TREE_NODE_STREAM ctns, pANTLR3_BASE_TREE t)
    475 {
    476 	ANTLR3_BOOLEAN	nilNode;
    477 	ANTLR3_UINT32	nCount;
    478 	ANTLR3_UINT32	c;
    479 
    480 	nilNode = ctns->adaptor->isNilNode(ctns->adaptor, t);
    481 
    482 	// If the supplied node is not a nil (list) node then we
    483 	// add in the node itself to the vector
    484 	//
    485 	if	(nilNode == ANTLR3_FALSE)
    486 	{
    487 		ctns->nodes->add(ctns->nodes, t, NULL);
    488 	}
    489 
    490 	// Only add a DOWN node if the tree is not a nil tree and
    491 	// the tree does have children.
    492 	//
    493 	nCount = t->getChildCount(t);
    494 
    495 	if	(nilNode == ANTLR3_FALSE && nCount>0)
    496 	{
    497 		ctns->addNavigationNode(ctns, ANTLR3_TOKEN_DOWN);
    498 	}
    499 
    500 	// We always add any children the tree contains, which is
    501 	// a recursive call to this function, which will cause similar
    502 	// recursion and implement a depth first addition
    503 	//
    504 	for	(c = 0; c < nCount; c++)
    505 	{
    506 		fillBuffer(ctns, ctns->adaptor->getChild(ctns->adaptor, t, c));
    507 	}
    508 
    509 	// If the tree had children and was not a nil (list) node, then we
    510 	// we need to add an UP node here to match the DOWN node
    511 	//
    512 	if	(nilNode == ANTLR3_FALSE && nCount > 0)
    513 	{
    514 		ctns->addNavigationNode(ctns, ANTLR3_TOKEN_UP);
    515 	}
    516 }
    517 
    518 
    519 // ------------------------------------------------------------------------------
    520 // Interface functions
    521 //
    522 
    523 /// Reset the input stream to the start of the input nodes.
    524 ///
    525 static	void
    526 reset	    (pANTLR3_COMMON_TREE_NODE_STREAM ctns)
    527 {
    528 	if	(ctns->p != -1)
    529 	{
    530 		ctns->p									= 0;
    531 	}
    532 	ctns->tnstream->istream->lastMarker		= 0;
    533 
    534 
    535 	// Free and reset the node stack only if this is not
    536 	// a rewriter, which is going to reuse the originating
    537 	// node streams node stack
    538 	//
    539 	if  (ctns->isRewriter != ANTLR3_TRUE)
    540     {
    541 		if	(ctns->nodeStack != NULL)
    542 		{
    543 			ctns->nodeStack->free(ctns->nodeStack);
    544 			ctns->nodeStack = antlr3StackNew(INITIAL_CALL_STACK_SIZE);
    545 		}
    546 	}
    547 }
    548 
    549 
    550 static pANTLR3_BASE_TREE
    551 LB(pANTLR3_TREE_NODE_STREAM tns, ANTLR3_INT32 k)
    552 {
    553 	if	( k==0)
    554 	{
    555 		return	&(tns->ctns->INVALID_NODE.baseTree);
    556 	}
    557 
    558 	if	( (tns->ctns->p - k) < 0)
    559 	{
    560 		return	&(tns->ctns->INVALID_NODE.baseTree);
    561 	}
    562 
    563 	return tns->ctns->nodes->get(tns->ctns->nodes, tns->ctns->p - k);
    564 }
    565 
    566 /// Get tree node at current input pointer + i ahead where i=1 is next node.
    567 /// i<0 indicates nodes in the past.  So -1 is previous node and -2 is
    568 /// two nodes ago. LT(0) is undefined.  For i>=n, return null.
    569 /// Return null for LT(0) and any index that results in an absolute address
    570 /// that is negative.
    571 ///
    572 /// This is analogous to the _LT() method of the TokenStream, but this
    573 /// returns a tree node instead of a token.  Makes code gen identical
    574 /// for both parser and tree grammars. :)
    575 ///
    576 static	pANTLR3_BASE_TREE
    577 _LT	    (pANTLR3_TREE_NODE_STREAM tns, ANTLR3_INT32 k)
    578 {
    579 	if	(tns->ctns->p == -1)
    580 	{
    581 		fillBufferRoot(tns->ctns);
    582 	}
    583 
    584 	if	(k < 0)
    585 	{
    586 		return LB(tns, -k);
    587 	}
    588 	else if	(k == 0)
    589 	{
    590 		return	&(tns->ctns->INVALID_NODE.baseTree);
    591 	}
    592 
    593 	// k was a legitimate request,
    594 	//
    595 	if	(( tns->ctns->p + k - 1) >= (ANTLR3_INT32)(tns->ctns->nodes->count))
    596 	{
    597 		return &(tns->ctns->EOF_NODE.baseTree);
    598 	}
    599 
    600 	return	tns->ctns->nodes->get(tns->ctns->nodes, tns->ctns->p + k - 1);
    601 }
    602 
    603 /// Where is this stream pulling nodes from?  This is not the name, but
    604 /// the object that provides node objects.
    605 ///
    606 static	pANTLR3_BASE_TREE
    607 getTreeSource	(pANTLR3_TREE_NODE_STREAM tns)
    608 {
    609     return  tns->ctns->root;
    610 }
    611 
    612 /// Consume the next node from the input stream
    613 ///
    614 static	void
    615 consume	(pANTLR3_INT_STREAM is)
    616 {
    617     pANTLR3_TREE_NODE_STREAM		tns;
    618     pANTLR3_COMMON_TREE_NODE_STREAM	ctns;
    619 
    620     tns	    = (pANTLR3_TREE_NODE_STREAM)(is->super);
    621     ctns    = tns->ctns;
    622 
    623 	if	(ctns->p == -1)
    624 	{
    625 		fillBufferRoot(ctns);
    626 	}
    627 	ctns->p++;
    628 }
    629 
    630 static	ANTLR3_UINT32
    631 _LA	    (pANTLR3_INT_STREAM is, ANTLR3_INT32 i)
    632 {
    633 	pANTLR3_TREE_NODE_STREAM		tns;
    634 	pANTLR3_BASE_TREE				t;
    635 
    636 	tns	    = (pANTLR3_TREE_NODE_STREAM)(is->super);
    637 
    638 	// Ask LT for the 'token' at that position
    639 	//
    640 	t = tns->_LT(tns, i);
    641 
    642 	if	(t == NULL)
    643 	{
    644 		return	ANTLR3_TOKEN_INVALID;
    645 	}
    646 
    647 	// Token node was there so return the type of it
    648 	//
    649 	return  t->getType(t);
    650 }
    651 
    652 /// Mark the state of the input stream so that we can come back to it
    653 /// after a syntactic predicate and so on.
    654 ///
    655 static	ANTLR3_MARKER
    656 mark	(pANTLR3_INT_STREAM is)
    657 {
    658 	pANTLR3_TREE_NODE_STREAM		tns;
    659 	pANTLR3_COMMON_TREE_NODE_STREAM	ctns;
    660 
    661 	tns	    = (pANTLR3_TREE_NODE_STREAM)(is->super);
    662 	ctns    = tns->ctns;
    663 
    664 	if	(tns->ctns->p == -1)
    665 	{
    666 		fillBufferRoot(tns->ctns);
    667 	}
    668 
    669 	// Return the current mark point
    670 	//
    671 	ctns->tnstream->istream->lastMarker = ctns->tnstream->istream->index(ctns->tnstream->istream);
    672 
    673 	return ctns->tnstream->istream->lastMarker;
    674 }
    675 
    676 static	void
    677 release	(pANTLR3_INT_STREAM is, ANTLR3_MARKER marker)
    678 {
    679 }
    680 
    681 /// Rewind the current state of the tree walk to the state it
    682 /// was in when mark() was called and it returned marker.  Also,
    683 /// wipe out the lookahead which will force reloading a few nodes
    684 /// but it is better than making a copy of the lookahead buffer
    685 /// upon mark().
    686 ///
    687 static	void
    688 rewindMark	    (pANTLR3_INT_STREAM is, ANTLR3_MARKER marker)
    689 {
    690 	is->seek(is, marker);
    691 }
    692 
    693 static	void
    694 rewindLast	(pANTLR3_INT_STREAM is)
    695 {
    696    is->seek(is, is->lastMarker);
    697 }
    698 
    699 /// consume() ahead until we hit index.  Can't just jump ahead--must
    700 /// spit out the navigation nodes.
    701 ///
    702 static	void
    703 seek	(pANTLR3_INT_STREAM is, ANTLR3_MARKER index)
    704 {
    705     pANTLR3_TREE_NODE_STREAM		tns;
    706     pANTLR3_COMMON_TREE_NODE_STREAM	ctns;
    707 
    708     tns	    = (pANTLR3_TREE_NODE_STREAM)(is->super);
    709     ctns    = tns->ctns;
    710 
    711 	ctns->p = ANTLR3_UINT32_CAST(index);
    712 }
    713 
    714 static	ANTLR3_MARKER
    715 tindex	(pANTLR3_INT_STREAM is)
    716 {
    717     pANTLR3_TREE_NODE_STREAM		tns;
    718     pANTLR3_COMMON_TREE_NODE_STREAM	ctns;
    719 
    720     tns	    = (pANTLR3_TREE_NODE_STREAM)(is->super);
    721     ctns    = tns->ctns;
    722 
    723 	return (ANTLR3_MARKER)(ctns->p);
    724 }
    725 
    726 /// Expensive to compute the size of the whole tree while parsing.
    727 /// This method only returns how much input has been seen so far.  So
    728 /// after parsing it returns true size.
    729 ///
    730 static	ANTLR3_UINT32
    731 size	(pANTLR3_INT_STREAM is)
    732 {
    733     pANTLR3_TREE_NODE_STREAM		tns;
    734     pANTLR3_COMMON_TREE_NODE_STREAM	ctns;
    735 
    736     tns	    = (pANTLR3_TREE_NODE_STREAM)(is->super);
    737     ctns    = tns->ctns;
    738 
    739 	if	(ctns->p == -1)
    740 	{
    741 		fillBufferRoot(ctns);
    742 	}
    743 
    744 	return ctns->nodes->size(ctns->nodes);
    745 }
    746 
    747 /// As we flatten the tree, we use UP, DOWN nodes to represent
    748 /// the tree structure.  When debugging we need unique nodes
    749 /// so instantiate new ones when uniqueNavigationNodes is true.
    750 ///
    751 static	void
    752 addNavigationNode	    (pANTLR3_COMMON_TREE_NODE_STREAM ctns, ANTLR3_UINT32 ttype)
    753 {
    754 	pANTLR3_BASE_TREE	    node;
    755 
    756 	node = NULL;
    757 
    758 	if	(ttype == ANTLR3_TOKEN_DOWN)
    759 	{
    760 		if  (ctns->hasUniqueNavigationNodes(ctns) == ANTLR3_TRUE)
    761 		{
    762 			node    = ctns->newDownNode(ctns);
    763 		}
    764 		else
    765 		{
    766 			node    = &(ctns->DOWN.baseTree);
    767 		}
    768 	}
    769 	else
    770 	{
    771 		if  (ctns->hasUniqueNavigationNodes(ctns) == ANTLR3_TRUE)
    772 		{
    773 			node    = ctns->newUpNode(ctns);
    774 		}
    775 		else
    776 		{
    777 			node    = &(ctns->UP.baseTree);
    778 		}
    779 	}
    780 
    781 	// Now add the node we decided upon.
    782 	//
    783 	ctns->nodes->add(ctns->nodes, node, NULL);
    784 }
    785 
    786 
    787 static	pANTLR3_BASE_TREE_ADAPTOR
    788 getTreeAdaptor	(pANTLR3_TREE_NODE_STREAM tns)
    789 {
    790     return  tns->ctns->adaptor;
    791 }
    792 
    793 static	ANTLR3_BOOLEAN
    794 hasUniqueNavigationNodes	    (pANTLR3_COMMON_TREE_NODE_STREAM ctns)
    795 {
    796     return  ctns->uniqueNavigationNodes;
    797 }
    798 
    799 static	void
    800 setUniqueNavigationNodes	    (pANTLR3_TREE_NODE_STREAM tns, ANTLR3_BOOLEAN uniqueNavigationNodes)
    801 {
    802     tns->ctns->uniqueNavigationNodes = uniqueNavigationNodes;
    803 }
    804 
    805 
    806 /// Print out the entire tree including DOWN/UP nodes.  Uses
    807 /// a recursive walk.  Mostly useful for testing as it yields
    808 /// the token types not text.
    809 ///
    810 static	pANTLR3_STRING
    811 toString	    (pANTLR3_TREE_NODE_STREAM tns)
    812 {
    813 
    814     return  tns->toStringSS(tns, tns->ctns->root, NULL);
    815 }
    816 
    817 static	pANTLR3_STRING
    818 toStringSS	    (pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE start, pANTLR3_BASE_TREE stop)
    819 {
    820     pANTLR3_STRING  buf;
    821 
    822     buf = tns->ctns->stringFactory->newRaw(tns->ctns->stringFactory);
    823 
    824     tns->toStringWork(tns, start, stop, buf);
    825 
    826     return  buf;
    827 }
    828 
    829 static	void
    830 toStringWork	(pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE p, pANTLR3_BASE_TREE stop, pANTLR3_STRING buf)
    831 {
    832 
    833 	ANTLR3_UINT32   n;
    834 	ANTLR3_UINT32   c;
    835 
    836 	if	(!p->isNilNode(p) )
    837 	{
    838 		pANTLR3_STRING	text;
    839 
    840 		text	= p->toString(p);
    841 
    842 		if  (text == NULL)
    843 		{
    844 			text = tns->ctns->stringFactory->newRaw(tns->ctns->stringFactory);
    845 
    846 			text->addc	(text, ' ');
    847 			text->addi	(text, p->getType(p));
    848 		}
    849 
    850 		buf->appendS(buf, text);
    851 	}
    852 
    853 	if	(p == stop)
    854 	{
    855 		return;		/* Finished */
    856 	}
    857 
    858 	n = p->getChildCount(p);
    859 
    860 	if	(n > 0 && ! p->isNilNode(p) )
    861 	{
    862 		buf->addc   (buf, ' ');
    863 		buf->addi   (buf, ANTLR3_TOKEN_DOWN);
    864 	}
    865 
    866 	for	(c = 0; c<n ; c++)
    867 	{
    868 		pANTLR3_BASE_TREE   child;
    869 
    870 		child = p->getChild(p, c);
    871 		tns->toStringWork(tns, child, stop, buf);
    872 	}
    873 
    874 	if	(n > 0 && ! p->isNilNode(p) )
    875 	{
    876 		buf->addc   (buf, ' ');
    877 		buf->addi   (buf, ANTLR3_TOKEN_UP);
    878 	}
    879 }
    880 
    881 static	ANTLR3_UINT32
    882 getLookaheadSize	(pANTLR3_COMMON_TREE_NODE_STREAM ctns)
    883 {
    884     return	ctns->tail < ctns->head
    885 	    ?	(ctns->lookAheadLength - ctns->head + ctns->tail)
    886 	    :	(ctns->tail - ctns->head);
    887 }
    888 
    889 static	pANTLR3_BASE_TREE
    890 newDownNode		(pANTLR3_COMMON_TREE_NODE_STREAM ctns)
    891 {
    892     pANTLR3_COMMON_TREE	    dNode;
    893     pANTLR3_COMMON_TOKEN    token;
    894 
    895     token					= antlr3CommonTokenNew(ANTLR3_TOKEN_DOWN);
    896 	token->textState		= ANTLR3_TEXT_CHARP;
    897 	token->tokText.chars	= (pANTLR3_UCHAR)"DOWN";
    898     dNode					= antlr3CommonTreeNewFromToken(token);
    899 
    900     return  &(dNode->baseTree);
    901 }
    902 
    903 static	pANTLR3_BASE_TREE
    904 newUpNode		(pANTLR3_COMMON_TREE_NODE_STREAM ctns)
    905 {
    906     pANTLR3_COMMON_TREE	    uNode;
    907     pANTLR3_COMMON_TOKEN    token;
    908 
    909     token					= antlr3CommonTokenNew(ANTLR3_TOKEN_UP);
    910 	token->textState		= ANTLR3_TEXT_CHARP;
    911 	token->tokText.chars	= (pANTLR3_UCHAR)"UP";
    912     uNode					= antlr3CommonTreeNewFromToken(token);
    913 
    914     return  &(uNode->baseTree);
    915 }
    916 
    917 /// Replace from start to stop child index of parent with t, which might
    918 /// be a list.  Number of children may be different
    919 /// after this call.  The stream is notified because it is walking the
    920 /// tree and might need to know you are monkey-ing with the underlying
    921 /// tree.  Also, it might be able to modify the node stream to avoid
    922 /// re-streaming for future phases.
    923 ///
    924 /// If parent is null, don't do anything; must be at root of overall tree.
    925 /// Can't replace whatever points to the parent externally.  Do nothing.
    926 ///
    927 static	void
    928 replaceChildren				(pANTLR3_TREE_NODE_STREAM tns, pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE t)
    929 {
    930 	if	(parent != NULL)
    931 	{
    932 		pANTLR3_BASE_TREE_ADAPTOR	adaptor;
    933 		pANTLR3_COMMON_TREE_ADAPTOR	cta;
    934 
    935 		adaptor	= tns->getTreeAdaptor(tns);
    936 		cta		= (pANTLR3_COMMON_TREE_ADAPTOR)(adaptor->super);
    937 
    938 		adaptor->replaceChildren(adaptor, parent, startChildIndex, stopChildIndex, t);
    939 	}
    940 }
    941 
    942 static	pANTLR3_BASE_TREE
    943 get							(pANTLR3_TREE_NODE_STREAM tns, ANTLR3_INT32 k)
    944 {
    945 	if	(tns->ctns->p == -1)
    946 	{
    947 		fillBufferRoot(tns->ctns);
    948 	}
    949 
    950 	return tns->ctns->nodes->get(tns->ctns->nodes, k);
    951 }
    952 
    953 static	void
    954 push						(pANTLR3_COMMON_TREE_NODE_STREAM ctns, ANTLR3_INT32 index)
    955 {
    956 	ctns->nodeStack->push(ctns->nodeStack, ANTLR3_FUNC_PTR(ctns->p), NULL);	// Save current index
    957 	ctns->tnstream->istream->seek(ctns->tnstream->istream, index);
    958 }
    959 
    960 static	ANTLR3_INT32
    961 pop							(pANTLR3_COMMON_TREE_NODE_STREAM ctns)
    962 {
    963 	ANTLR3_INT32	retVal;
    964 
    965 	retVal = ANTLR3_UINT32_CAST(ctns->nodeStack->pop(ctns->nodeStack));
    966 	ctns->tnstream->istream->seek(ctns->tnstream->istream, retVal);
    967 	return retVal;
    968 }
    969