Home | History | Annotate | Download | only in src
      1 /** \file
      2  * Contains the base functions that all tree adaptors start with.
      3  * this implementation can then be overridden by any higher implementation.
      4  *
      5  */
      6 
      7 // [The "BSD licence"]
      8 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
      9 // http://www.temporal-wave.com
     10 // http://www.linkedin.com/in/jimidle
     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    <antlr3basetreeadaptor.h>
     37 
     38 #ifdef	ANTLR3_WINDOWS
     39 #pragma warning( disable : 4100 )
     40 #endif
     41 
     42 /* Interface functions
     43  */
     44 static	pANTLR3_BASE_TREE	nilNode					(pANTLR3_BASE_TREE_ADAPTOR adaptor);
     45 static	pANTLR3_BASE_TREE	dbgNil					(pANTLR3_BASE_TREE_ADAPTOR adaptor);
     46 static	pANTLR3_BASE_TREE	dupTree					(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t);
     47 static	pANTLR3_BASE_TREE	dbgDupTree				(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t);
     48 static	pANTLR3_BASE_TREE	dupTreeTT				(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t, pANTLR3_BASE_TREE parent);
     49 static	void				addChild				(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t, pANTLR3_BASE_TREE child);
     50 static	void				dbgAddChild				(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t, pANTLR3_BASE_TREE child);
     51 static	pANTLR3_BASE_TREE	becomeRoot				(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE newRoot, pANTLR3_BASE_TREE oldRoot);
     52 static	pANTLR3_BASE_TREE	dbgBecomeRoot			(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE newRoot, pANTLR3_BASE_TREE oldRoot);
     53 static	pANTLR3_BASE_TREE	rulePostProcessing		(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE root);
     54 static	void				addChildToken			(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t, pANTLR3_COMMON_TOKEN child);
     55 static	void				dbgAddChildToken		(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t, pANTLR3_COMMON_TOKEN child);
     56 static	pANTLR3_BASE_TREE	becomeRootToken			(pANTLR3_BASE_TREE_ADAPTOR adaptor, void * newRoot, pANTLR3_BASE_TREE oldRoot);
     57 static	pANTLR3_BASE_TREE	dbgBecomeRootToken		(pANTLR3_BASE_TREE_ADAPTOR adaptor, void * newRoot, pANTLR3_BASE_TREE oldRoot);
     58 static	pANTLR3_BASE_TREE	createTypeToken			(pANTLR3_BASE_TREE_ADAPTOR adaptor, ANTLR3_UINT32 tokenType, pANTLR3_COMMON_TOKEN fromToken);
     59 static	pANTLR3_BASE_TREE	dbgCreateTypeToken		(pANTLR3_BASE_TREE_ADAPTOR adaptor, ANTLR3_UINT32 tokenType, pANTLR3_COMMON_TOKEN fromToken);
     60 static	pANTLR3_BASE_TREE	createTypeTokenText		(pANTLR3_BASE_TREE_ADAPTOR adaptor, ANTLR3_UINT32 tokenType, pANTLR3_COMMON_TOKEN fromToken, pANTLR3_UINT8 text);
     61 static	pANTLR3_BASE_TREE	dbgCreateTypeTokenText	(pANTLR3_BASE_TREE_ADAPTOR adaptor, ANTLR3_UINT32 tokenType, pANTLR3_COMMON_TOKEN fromToken, pANTLR3_UINT8 text);
     62 static	pANTLR3_BASE_TREE	createTypeText			(pANTLR3_BASE_TREE_ADAPTOR adaptor, ANTLR3_UINT32 tokenType, pANTLR3_UINT8 text);
     63 static	pANTLR3_BASE_TREE	dbgCreateTypeText		(pANTLR3_BASE_TREE_ADAPTOR adaptor, ANTLR3_UINT32 tokenType, pANTLR3_UINT8 text);
     64 static	ANTLR3_UINT32		getType					(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t);
     65 static	void				setType					(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t, ANTLR3_UINT32 type);
     66 static	pANTLR3_STRING		getText					(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t);
     67 static	void				setText					(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_STRING t);
     68 static	void				setText8				(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_UINT8 t);
     69 static	pANTLR3_BASE_TREE	getChild				(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t, ANTLR3_UINT32 i);
     70 static	ANTLR3_UINT32		getChildCount			(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t);
     71 static	ANTLR3_UINT32		getUniqueID				(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t);
     72 static	ANTLR3_BOOLEAN		isNilNode				(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t);
     73 static	pANTLR3_STRING		makeDot					(pANTLR3_BASE_TREE_ADAPTOR adaptor, void * theTree);
     74 
     75 /** Given a pointer to a base tree adaptor structure (which is usually embedded in the
     76  *  super class the implements the tree adaptor used in the parse), initialize its
     77  *  function pointers and so on.
     78  */
     79 ANTLR3_API void
     80 antlr3BaseTreeAdaptorInit(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_DEBUG_EVENT_LISTENER	debugger)
     81 {
     82 	// Initialize the interface
     83 	//
     84 	if	(debugger == NULL)
     85 	{
     86 		adaptor->nilNode				= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR))
     87 																				nilNode;
     88 		adaptor->addChild				= (void   (*)(pANTLR3_BASE_TREE_ADAPTOR, void *, void *))
     89 																				addChild;
     90 		adaptor->becomeRoot				= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, void *, void *))
     91 																				becomeRoot;
     92 		adaptor->addChildToken			= (void   (*)(pANTLR3_BASE_TREE_ADAPTOR, void *, pANTLR3_COMMON_TOKEN))
     93 																				addChildToken;
     94 		adaptor->becomeRootToken		= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, void *, void *))
     95 																				becomeRootToken;
     96 		adaptor->createTypeToken		= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, ANTLR3_UINT32, pANTLR3_COMMON_TOKEN))
     97 																				createTypeToken;
     98 		adaptor->createTypeTokenText	= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, ANTLR3_UINT32, pANTLR3_COMMON_TOKEN, pANTLR3_UINT8))
     99 																				createTypeTokenText;
    100 		adaptor->createTypeText			= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, ANTLR3_UINT32, pANTLR3_UINT8))
    101 																				createTypeText;
    102 		adaptor->dupTree				= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, void *))
    103 																				dupTree;
    104 	}
    105 	else
    106 	{
    107 		adaptor->nilNode				= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR))
    108                                                                                 dbgNil;
    109 		adaptor->addChild				= (void   (*)(pANTLR3_BASE_TREE_ADAPTOR, void *, void *))
    110                                                                                 dbgAddChild;
    111 		adaptor->becomeRoot				= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, void *, void *))
    112 																				dbgBecomeRoot;
    113 		adaptor->addChildToken			= (void   (*)(pANTLR3_BASE_TREE_ADAPTOR, void *, pANTLR3_COMMON_TOKEN))
    114                                                                                 dbgAddChildToken;
    115 		adaptor->becomeRootToken		= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, void *, void *))
    116                                                                                 dbgBecomeRootToken;
    117 		adaptor->createTypeToken		= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, ANTLR3_UINT32, pANTLR3_COMMON_TOKEN))
    118                                                                                 dbgCreateTypeToken;
    119 		adaptor->createTypeTokenText	= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, ANTLR3_UINT32, pANTLR3_COMMON_TOKEN, pANTLR3_UINT8))
    120                                                                                 dbgCreateTypeTokenText;
    121 		adaptor->createTypeText			= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, ANTLR3_UINT32, pANTLR3_UINT8))
    122                                                                                 dbgCreateTypeText;
    123 		adaptor->dupTree				= (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, void *))
    124                                                                                 dbgDupTree;
    125 		debugger->adaptor				= adaptor;
    126 	}
    127 
    128 	adaptor->dupTreeTT				=  (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, void *, void *))
    129                                                                                 dupTreeTT;
    130 	adaptor->rulePostProcessing		=  (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, void *))
    131                                                                                 rulePostProcessing;
    132 	adaptor->getType				=  (ANTLR3_UINT32 (*)(pANTLR3_BASE_TREE_ADAPTOR, void *))
    133                                                                                 getType;
    134 	adaptor->setType				=  (void   (*)(pANTLR3_BASE_TREE_ADAPTOR, void *, ANTLR3_UINT32))
    135 																				setType;
    136 	adaptor->getText				=  (pANTLR3_STRING (*) (pANTLR3_BASE_TREE_ADAPTOR, void *))
    137                                                                                 getText;
    138 	adaptor->setText8				=  (void   (*)(pANTLR3_BASE_TREE_ADAPTOR, pANTLR3_UINT8))
    139 																				setText8;
    140 	adaptor->setText				=  (void   (*)(pANTLR3_BASE_TREE_ADAPTOR, pANTLR3_STRING))
    141                                                                                 setText;
    142 	adaptor->getChild				=  (void * (*)(pANTLR3_BASE_TREE_ADAPTOR, void *, ANTLR3_UINT32))
    143                                                                                 getChild;
    144 	adaptor->getChildCount			=  (ANTLR3_UINT32 (*)(pANTLR3_BASE_TREE_ADAPTOR, void *))
    145                                                                                 getChildCount;
    146 	adaptor->getUniqueID			=  (ANTLR3_UINT32 (*)(pANTLR3_BASE_TREE_ADAPTOR, void *))
    147                                                                                 getUniqueID;
    148 	adaptor->isNilNode				=  (ANTLR3_BOOLEAN (*)(pANTLR3_BASE_TREE_ADAPTOR, void *))
    149                                                                                 isNilNode;
    150 
    151 	adaptor->makeDot				=  (pANTLR3_STRING  (*)(pANTLR3_BASE_TREE_ADAPTOR, void *))
    152 																				makeDot;
    153 
    154 	/* Remaining functions filled in by the caller.
    155 	 */
    156 	return;
    157 }
    158 
    159 static void
    160 defineDotNodes(pANTLR3_BASE_TREE_ADAPTOR adaptor, void * t, pANTLR3_STRING dotSpec )
    161 {
    162 	// How many nodes are we talking about?
    163 	//
    164 	int	nCount;
    165 	int i;
    166     pANTLR3_BASE_TREE child;
    167 	char	buff[64];
    168 	pANTLR3_STRING	text;
    169 	int		j;
    170 
    171 
    172 
    173 
    174 
    175 	// Count the nodes
    176 	//
    177 	nCount = adaptor->getChildCount(adaptor, t);
    178 
    179 	if	(nCount == 0)
    180 	{
    181 		// This will already have been included as a child of another node
    182 		// so there is nothing to add.
    183 		//
    184 		return;
    185 	}
    186 
    187 	// For each child of the current tree, define a node using the
    188 	// memory address of the node to name it
    189 	//
    190 	for	(i = 0; i<nCount; i++)
    191 	{
    192 
    193 		// Pick up a pointer for the child
    194 		//
    195 		child = adaptor->getChild(adaptor, t, i);
    196 
    197 		// Name the node
    198 		//
    199 		sprintf(buff, "\tn%p[label=\"", child);
    200 		dotSpec->append8(dotSpec, buff);
    201 		text = adaptor->getText(adaptor, child);
    202 		for (j = 0; j < (ANTLR3_INT32)(text->len); j++)
    203 		{
    204             switch(text->charAt(text, j))
    205             {
    206                 case '"':
    207 
    208                     dotSpec->append8(dotSpec, "\\\"");
    209                     break;
    210 
    211                 case '\n':
    212 
    213                     dotSpec->append8(dotSpec, "\\n");
    214                     break;
    215 
    216                 case '\r':
    217 
    218                     dotSpec->append8(dotSpec, "\\r");
    219                     break;
    220 
    221                 default:
    222 
    223                     dotSpec->addc(dotSpec, text->charAt(text, j));
    224                     break;
    225             }
    226 		}
    227 		dotSpec->append8(dotSpec, "\"]\n");
    228 
    229 		// And now define the children of this child (if any)
    230 		//
    231 		defineDotNodes(adaptor, child, dotSpec);
    232 	}
    233 
    234 	// Done
    235 	//
    236 	return;
    237 }
    238 
    239 static void
    240 defineDotEdges(pANTLR3_BASE_TREE_ADAPTOR adaptor, void * t, pANTLR3_STRING dotSpec)
    241 {
    242 	// How many nodes are we talking about?
    243 	//
    244 	int	nCount;
    245 	int i;
    246 
    247 	if	(t == NULL)
    248 	{
    249 		// No tree, so do nothing
    250 		//
    251 		return;
    252 	}
    253 
    254 	// Count the nodes
    255 	//
    256 	nCount = adaptor->getChildCount(adaptor, t);
    257 
    258 	if	(nCount == 0)
    259 	{
    260 		// This will already have been included as a child of another node
    261 		// so there is nothing to add.
    262 		//
    263 		return;
    264 	}
    265 
    266 	// For each child, define an edge from this parent, then process
    267 	// and children of this child in the same way
    268 	//
    269 	for	(i=0; i<nCount; i++)
    270 	{
    271 		pANTLR3_BASE_TREE child;
    272 		char	buff[128];
    273         pANTLR3_STRING text;
    274         int                 j;
    275 
    276 		// Next child
    277 		//
    278 		child	= adaptor->getChild(adaptor, t, i);
    279 
    280 		// Create the edge relation
    281 		//
    282 		sprintf(buff, "\t\tn%p -> n%p\t\t// ",  t, child);
    283 
    284 		dotSpec->append8(dotSpec, buff);
    285 
    286 		// Document the relationship
    287 		//
    288         text = adaptor->getText(adaptor, t);
    289 		for (j = 0; j < (ANTLR3_INT32)(text->len); j++)
    290         {
    291                 switch(text->charAt(text, j))
    292                 {
    293                     case '"':
    294 
    295                         dotSpec->append8(dotSpec, "\\\"");
    296                         break;
    297 
    298                     case '\n':
    299 
    300                         dotSpec->append8(dotSpec, "\\n");
    301                         break;
    302 
    303                     case '\r':
    304 
    305                         dotSpec->append8(dotSpec, "\\r");
    306                         break;
    307 
    308                     default:
    309 
    310                         dotSpec->addc(dotSpec, text->charAt(text, j));
    311                         break;
    312                 }
    313         }
    314 
    315         dotSpec->append8(dotSpec, " -> ");
    316 
    317         text = adaptor->getText(adaptor, child);
    318         for (j = 0; j < (ANTLR3_INT32)(text->len); j++)
    319         {
    320                 switch(text->charAt(text, j))
    321                 {
    322                     case '"':
    323 
    324                         dotSpec->append8(dotSpec, "\\\"");
    325                         break;
    326 
    327                     case '\n':
    328 
    329                         dotSpec->append8(dotSpec, "\\n");
    330                         break;
    331 
    332                     case '\r':
    333 
    334                         dotSpec->append8(dotSpec, "\\r");
    335                         break;
    336 
    337                     default:
    338 
    339                         dotSpec->addc(dotSpec, text->charAt(text, j));
    340                         break;
    341                 }
    342         }
    343 		dotSpec->append8(dotSpec, "\n");
    344 
    345 
    346 		// Define edges for this child
    347 		//
    348 		defineDotEdges(adaptor, child, dotSpec);
    349 	}
    350 
    351 	// Done
    352 	//
    353 	return;
    354 }
    355 
    356 /// Produce a DOT specification for graphviz
    357 //
    358 static pANTLR3_STRING
    359 makeDot	(pANTLR3_BASE_TREE_ADAPTOR adaptor, void * theTree)
    360 {
    361 	// The string we are building up
    362 	//
    363 	pANTLR3_STRING		dotSpec;
    364 	char                buff[64];
    365 	pANTLR3_STRING      text;
    366 	int                 j;
    367 
    368 	dotSpec = adaptor->strFactory->newStr8
    369 
    370 		(
    371 			adaptor->strFactory,
    372 
    373 			// Default look and feel
    374 			//
    375 			(pANTLR3_UINT8)
    376 			"digraph {\n\n"
    377 			"\tordering=out;\n"
    378 			"\tranksep=.4;\n"
    379 			"\tbgcolor=\"lightgrey\";  node [shape=box, fixedsize=false, fontsize=12, fontname=\"Helvetica-bold\", fontcolor=\"blue\"\n"
    380 			"\twidth=.25, height=.25, color=\"black\", fillcolor=\"white\", style=\"filled, solid, bold\"];\n\n"
    381 			"\tedge [arrowsize=.5, color=\"black\", style=\"bold\"]\n\n"
    382 		);
    383 
    384     if	(theTree == NULL)
    385 	{
    386 		// No tree, so create a blank spec
    387 		//
    388 		dotSpec->append8(dotSpec, "n0[label=\"EMPTY TREE\"]\n");
    389 		return dotSpec;
    390 	}
    391 
    392     sprintf(buff, "\tn%p[label=\"", theTree);
    393 	dotSpec->append8(dotSpec, buff);
    394     text = adaptor->getText(adaptor, theTree);
    395     for (j = 0; j < (ANTLR3_INT32)(text->len); j++)
    396     {
    397             switch(text->charAt(text, j))
    398             {
    399                 case '"':
    400 
    401                     dotSpec->append8(dotSpec, "\\\"");
    402                     break;
    403 
    404                 case '\n':
    405 
    406                     dotSpec->append8(dotSpec, "\\n");
    407                     break;
    408 
    409                 case '\r':
    410 
    411                     dotSpec->append8(dotSpec, "\\r");
    412                     break;
    413 
    414                 default:
    415 
    416                     dotSpec->addc(dotSpec, text->charAt(text, j));
    417                     break;
    418             }
    419     }
    420 	dotSpec->append8(dotSpec, "\"]\n");
    421 
    422 	// First produce the node defintions
    423 	//
    424 	defineDotNodes(adaptor, theTree, dotSpec);
    425 	dotSpec->append8(dotSpec, "\n");
    426 	defineDotEdges(adaptor, theTree, dotSpec);
    427 
    428 	// Terminate the spec
    429 	//
    430 	dotSpec->append8(dotSpec, "\n}");
    431 
    432 	// Result
    433 	//
    434 	return dotSpec;
    435 }
    436 
    437 
    438 /** Create and return a nil tree node (no token payload)
    439  */
    440 static	pANTLR3_BASE_TREE
    441 nilNode	    (pANTLR3_BASE_TREE_ADAPTOR adaptor)
    442 {
    443 	return	adaptor->create(adaptor, NULL);
    444 }
    445 
    446 static	pANTLR3_BASE_TREE
    447 dbgNil	    (pANTLR3_BASE_TREE_ADAPTOR adaptor)
    448 {
    449 	pANTLR3_BASE_TREE t;
    450 
    451 	t = adaptor->create				(adaptor, NULL);
    452 	adaptor->debugger->createNode	(adaptor->debugger, t);
    453 
    454 	return	t;
    455 }
    456 
    457 /** Return a duplicate of the entire tree (implementation provided by the
    458  *  BASE_TREE interface.)
    459  */
    460 static	pANTLR3_BASE_TREE
    461 dupTree  (pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t)
    462 {
    463 	return	adaptor->dupTreeTT(adaptor, t, NULL);
    464 }
    465 
    466 pANTLR3_BASE_TREE
    467 dupTreeTT			(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t, pANTLR3_BASE_TREE parent)
    468 {
    469 	pANTLR3_BASE_TREE	newTree;
    470 	pANTLR3_BASE_TREE	child;
    471 	pANTLR3_BASE_TREE	newSubTree;
    472 	ANTLR3_UINT32		n;
    473 	ANTLR3_UINT32		i;
    474 
    475 	if	(t == NULL)
    476 	{
    477 		return NULL;
    478 	}
    479 	newTree = t->dupNode(t);
    480 
    481 	// Ensure new subtree root has parent/child index set
    482 	//
    483 	adaptor->setChildIndex		(adaptor, newTree, t->getChildIndex(t));
    484 	adaptor->setParent			(adaptor, newTree, parent);
    485 	n = adaptor->getChildCount	(adaptor, t);
    486 
    487 	for	(i=0; i < n; i++)
    488 	{
    489 		child = adaptor->getChild		(adaptor, t, i);
    490 		newSubTree = adaptor->dupTreeTT	(adaptor, child, t);
    491 		adaptor->addChild				(adaptor, newTree, newSubTree);
    492 	}
    493 	return	newTree;
    494 }
    495 
    496 /// Sends the required debugging events for duplicating a tree
    497 /// to the debugger.
    498 ///
    499 static void
    500 simulateTreeConstruction(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE tree)
    501 {
    502 	ANTLR3_UINT32		n;
    503 	ANTLR3_UINT32		i;
    504 	pANTLR3_BASE_TREE	child;
    505 
    506 	// Send the create node event
    507 	//
    508 	adaptor->debugger->createNode(adaptor->debugger, tree);
    509 
    510 	n = adaptor->getChildCount(adaptor, tree);
    511 	for	(i = 0; i < n; i++)
    512 	{
    513 		child = adaptor->getChild(adaptor, tree, i);
    514 		simulateTreeConstruction(adaptor, child);
    515 		adaptor->debugger->addChild(adaptor->debugger, tree, child);
    516 	}
    517 }
    518 
    519 pANTLR3_BASE_TREE
    520 dbgDupTree		(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE tree)
    521 {
    522 	pANTLR3_BASE_TREE t;
    523 
    524 	// Call the normal dup tree mechanism first
    525 	//
    526 	t = adaptor->dupTreeTT(adaptor, tree, NULL);
    527 
    528 	// In order to tell the debugger what we have just done, we now
    529 	// simulate the tree building mechanism. THis will fire
    530 	// lots of debugging events to the client and look like we
    531 	// duped the tree..
    532 	//
    533 	simulateTreeConstruction(adaptor, t);
    534 
    535 	return t;
    536 }
    537 
    538 /** Add a child to the tree t.  If child is a flat tree (a list), make all
    539  *  in list children of t. Warning: if t has no children, but child does
    540  *  and child isNilNode then it is ok to move children to t via
    541  *  t.children = child.children; i.e., without copying the array.  This
    542  *  is for construction and I'm not sure it's completely general for
    543  *  a tree's addChild method to work this way.  Make sure you differentiate
    544  *  between your tree's addChild and this parser tree construction addChild
    545  *  if it's not ok to move children to t with a simple assignment.
    546  */
    547 static	void
    548 addChild (pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t, pANTLR3_BASE_TREE child)
    549 {
    550 	if	(t != NULL && child != NULL)
    551 	{
    552 		t->addChild(t, child);
    553 	}
    554 }
    555 static	void
    556 dbgAddChild (pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t, pANTLR3_BASE_TREE child)
    557 {
    558 	if	(t != NULL && child != NULL)
    559 	{
    560 		t->addChild(t, child);
    561 		adaptor->debugger->addChild(adaptor->debugger, t, child);
    562 	}
    563 }
    564 /** Use the adaptor implementation to add a child node with the supplied token
    565  */
    566 static	void
    567 addChildToken		(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t, pANTLR3_COMMON_TOKEN child)
    568 {
    569 	if	(t != NULL && child != NULL)
    570 	{
    571 		adaptor->addChild(adaptor, t, adaptor->create(adaptor, child));
    572 	}
    573 }
    574 static	void
    575 dbgAddChildToken		(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t, pANTLR3_COMMON_TOKEN child)
    576 {
    577 	pANTLR3_BASE_TREE	tc;
    578 
    579 	if	(t != NULL && child != NULL)
    580 	{
    581 		tc = adaptor->create(adaptor, child);
    582 		adaptor->addChild(adaptor, t, tc);
    583 		adaptor->debugger->addChild(adaptor->debugger, t, tc);
    584 	}
    585 }
    586 
    587 /** If oldRoot is a nil root, just copy or move the children to newRoot.
    588  *  If not a nil root, make oldRoot a child of newRoot.
    589  *
    590  * \code
    591  *    old=^(nil a b c), new=r yields ^(r a b c)
    592  *    old=^(a b c), new=r yields ^(r ^(a b c))
    593  * \endcode
    594  *
    595  *  If newRoot is a nil-rooted single child tree, use the single
    596  *  child as the new root node.
    597  *
    598  * \code
    599  *    old=^(nil a b c), new=^(nil r) yields ^(r a b c)
    600  *    old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
    601  * \endcode
    602  *
    603  *  If oldRoot was null, it's ok, just return newRoot (even if isNilNode).
    604  *
    605  * \code
    606  *    old=null, new=r yields r
    607  *    old=null, new=^(nil r) yields ^(nil r)
    608  * \endcode
    609  *
    610  *  Return newRoot.  Throw an exception if newRoot is not a
    611  *  simple node or nil root with a single child node--it must be a root
    612  *  node.  If newRoot is <code>^(nil x)</endcode> return x as newRoot.
    613  *
    614  *  Be advised that it's ok for newRoot to point at oldRoot's
    615  *  children; i.e., you don't have to copy the list.  We are
    616  *  constructing these nodes so we should have this control for
    617  *  efficiency.
    618  */
    619 static	pANTLR3_BASE_TREE
    620 becomeRoot	(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE newRootTree, pANTLR3_BASE_TREE oldRootTree)
    621 {
    622     pANTLR3_BASE_TREE saveRoot;
    623 
    624 	/* Protect against tree rewrites if we are in some sort of error
    625 	 * state, but have tried to recover. In C we can end up with a null pointer
    626 	 * for a tree that was not produced.
    627 	 */
    628 	if	(newRootTree == NULL)
    629 	{
    630 		return	oldRootTree;
    631 	}
    632 
    633 	/* root is just the new tree as is if there is no
    634 	 * current root tree.
    635 	 */
    636 	if	(oldRootTree == NULL)
    637 	{
    638 		return	newRootTree;
    639 	}
    640 
    641 	/* Produce ^(nil real-node)
    642 	 */
    643 	if	(newRootTree->isNilNode(newRootTree))
    644 	{
    645 		if	(newRootTree->getChildCount(newRootTree) > 1)
    646 		{
    647 			/* TODO: Handle tree exceptions
    648 			 */
    649 			ANTLR3_FPRINTF(stderr, "More than one node as root! TODO: Create tree exception handling\n");
    650 			return newRootTree;
    651 		}
    652 
    653 		/* The new root is the first child, keep track of the original newRoot
    654          * because if it was a Nil Node, then we can reuse it now.
    655 		 */
    656         saveRoot    = newRootTree;
    657 		newRootTree = newRootTree->getChild(newRootTree, 0);
    658 
    659         // Reclaim the old nilNode()
    660         //
    661         saveRoot->reuse(saveRoot);
    662 	}
    663 
    664 	/* Add old root into new root. addChild takes care of the case where oldRoot
    665 	 * is a flat list (nill rooted tree). All children of oldroot are added to
    666 	 * new root.
    667 	 */
    668 	newRootTree->addChild(newRootTree, oldRootTree);
    669 
    670     // If the oldroot tree was a nil node, then we know at this point
    671     // it has become orphaned by the rewrite logic, so we tell it to do
    672     // whatever it needs to do to be reused.
    673     //
    674     if  (oldRootTree->isNilNode(oldRootTree))
    675     {
    676         // We have taken an old Root Tree and appended all its children to the new
    677         // root. In addition though it was a nil node, which means the generated code
    678         // will not reuse it again, so we will reclaim it here. First we want to zero out
    679         // any pointers it was carrying around. We are just the baseTree handler so we
    680         // don't know necessarilly know how to do this for the real node, we just ask the tree itself
    681         // to do it.
    682         //
    683         oldRootTree->reuse(oldRootTree);
    684     }
    685 	/* Always returns new root structure
    686 	 */
    687 	return	newRootTree;
    688 
    689 }
    690 static	pANTLR3_BASE_TREE
    691 dbgBecomeRoot	(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE newRootTree, pANTLR3_BASE_TREE oldRootTree)
    692 {
    693 	pANTLR3_BASE_TREE t;
    694 
    695 	t = becomeRoot(adaptor, newRootTree, oldRootTree);
    696 
    697 	adaptor->debugger->becomeRoot(adaptor->debugger, newRootTree, oldRootTree);
    698 
    699 	return t;
    700 }
    701 /** Transform ^(nil x) to x
    702  */
    703 static	pANTLR3_BASE_TREE
    704    rulePostProcessing	(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE root)
    705 {
    706     pANTLR3_BASE_TREE saveRoot;
    707 
    708     // Keep track of the root we are given. If it is a nilNode, then we
    709     // can reuse it rather than orphaning it!
    710     //
    711     saveRoot = root;
    712 
    713 	if (root != NULL && root->isNilNode(root))
    714 	{
    715 		if	(root->getChildCount(root) == 0)
    716 		{
    717 			root = NULL;
    718 		}
    719 		else if	(root->getChildCount(root) == 1)
    720 		{
    721 			root = root->getChild(root, 0);
    722 			root->setParent(root, NULL);
    723 			root->setChildIndex(root, -1);
    724 
    725             // The root we were given was a nil node, wiht one child, which means it has
    726             // been abandoned and would be lost in the node factory. However
    727             // nodes can be flagged as resuable to prevent this terrible waste
    728             //
    729             saveRoot->reuse(saveRoot);
    730 		}
    731 	}
    732 
    733 	return root;
    734 }
    735 
    736 /** Use the adaptor interface to set a new tree node with the supplied token
    737  *  to the root of the tree.
    738  */
    739 static	pANTLR3_BASE_TREE
    740    becomeRootToken	(pANTLR3_BASE_TREE_ADAPTOR adaptor, void * newRoot, pANTLR3_BASE_TREE oldRoot)
    741 {
    742 	return	adaptor->becomeRoot(adaptor, adaptor->create(adaptor, newRoot), oldRoot);
    743 }
    744 static	pANTLR3_BASE_TREE
    745 dbgBecomeRootToken	(pANTLR3_BASE_TREE_ADAPTOR adaptor, void * newRoot, pANTLR3_BASE_TREE oldRoot)
    746 {
    747 	pANTLR3_BASE_TREE	t;
    748 
    749 	t =	adaptor->becomeRoot(adaptor, adaptor->create(adaptor, newRoot), oldRoot);
    750 
    751 	adaptor->debugger->becomeRoot(adaptor->debugger,t, oldRoot);
    752 
    753 	return t;
    754 }
    755 
    756 /** Use the super class supplied create() method to create a new node
    757  *  from the supplied token.
    758  */
    759 static	pANTLR3_BASE_TREE
    760 createTypeToken	(pANTLR3_BASE_TREE_ADAPTOR adaptor, ANTLR3_UINT32 tokenType, pANTLR3_COMMON_TOKEN fromToken)
    761 {
    762 	/* Create the new token
    763 	 */
    764 	fromToken = adaptor->createTokenFromToken(adaptor, fromToken);
    765 
    766 	/* Set the type of the new token to that supplied
    767 	 */
    768 	fromToken->setType(fromToken, tokenType);
    769 
    770 	/* Return a new node based upon this token
    771 	 */
    772 	return	adaptor->create(adaptor, fromToken);
    773 }
    774 static	pANTLR3_BASE_TREE
    775 dbgCreateTypeToken	(pANTLR3_BASE_TREE_ADAPTOR adaptor, ANTLR3_UINT32 tokenType, pANTLR3_COMMON_TOKEN fromToken)
    776 {
    777 	pANTLR3_BASE_TREE t;
    778 
    779 	t = createTypeToken(adaptor, tokenType, fromToken);
    780 
    781 	adaptor->debugger->createNode(adaptor->debugger, t);
    782 
    783 	return t;
    784 }
    785 
    786 static	pANTLR3_BASE_TREE
    787 createTypeTokenText	(pANTLR3_BASE_TREE_ADAPTOR adaptor, ANTLR3_UINT32 tokenType, pANTLR3_COMMON_TOKEN fromToken, pANTLR3_UINT8 text)
    788 {
    789 	/* Create the new token
    790 	 */
    791 	fromToken = adaptor->createTokenFromToken(adaptor, fromToken);
    792 
    793 	/* Set the type of the new token to that supplied
    794 	 */
    795 	fromToken->setType(fromToken, tokenType);
    796 
    797 	/* Set the text of the token accordingly
    798 	 */
    799 	fromToken->setText8(fromToken, text);
    800 
    801 	/* Return a new node based upon this token
    802 	 */
    803 	return	adaptor->create(adaptor, fromToken);
    804 }
    805 static	pANTLR3_BASE_TREE
    806 dbgCreateTypeTokenText	(pANTLR3_BASE_TREE_ADAPTOR adaptor, ANTLR3_UINT32 tokenType, pANTLR3_COMMON_TOKEN fromToken, pANTLR3_UINT8 text)
    807 {
    808 	pANTLR3_BASE_TREE t;
    809 
    810 	t = createTypeTokenText(adaptor, tokenType, fromToken, text);
    811 
    812 	adaptor->debugger->createNode(adaptor->debugger, t);
    813 
    814 	return t;
    815 }
    816 
    817 static	pANTLR3_BASE_TREE
    818    createTypeText	(pANTLR3_BASE_TREE_ADAPTOR adaptor, ANTLR3_UINT32 tokenType, pANTLR3_UINT8 text)
    819 {
    820 	pANTLR3_COMMON_TOKEN	fromToken;
    821 
    822 	/* Create the new token
    823 	 */
    824 	fromToken = adaptor->createToken(adaptor, tokenType, text);
    825 
    826 	/* Return a new node based upon this token
    827 	 */
    828 	return	adaptor->create(adaptor, fromToken);
    829 }
    830 static	pANTLR3_BASE_TREE
    831    dbgCreateTypeText	(pANTLR3_BASE_TREE_ADAPTOR adaptor, ANTLR3_UINT32 tokenType, pANTLR3_UINT8 text)
    832 {
    833 	pANTLR3_BASE_TREE t;
    834 
    835 	t = createTypeText(adaptor, tokenType, text);
    836 
    837 	adaptor->debugger->createNode(adaptor->debugger, t);
    838 
    839 	return t;
    840 
    841 }
    842 /** Dummy implementation - will be supplied by super class
    843  */
    844 static	ANTLR3_UINT32
    845    getType		(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t)
    846 {
    847 	return	0;
    848 }
    849 
    850 /** Dummy implementation - will be supplied by super class
    851  */
    852 static	void
    853    setType		(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t, ANTLR3_UINT32 type)
    854 {
    855 	ANTLR3_FPRINTF(stderr, "Internal error - implementor of superclass containing ANTLR3_TREE_ADAPTOR did not implement setType()\n");
    856 }
    857 
    858 /** Dummy implementation - will be supplied by super class
    859  */
    860 static	pANTLR3_STRING
    861    getText		(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t)
    862 {
    863 	ANTLR3_FPRINTF(stderr, "Internal error - implementor of superclass containing ANTLR3_TREE_ADAPTOR did not implement getText()\n");
    864 	return	NULL;
    865 }
    866 
    867 /** Dummy implementation - will be supplied by super class
    868  */
    869 static	void
    870    setText		(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_STRING t)
    871 {
    872 	ANTLR3_FPRINTF(stderr, "Internal error - implementor of superclass containing ANTLR3_TREE_ADAPTOR did not implement setText()\n");
    873 }
    874 /** Dummy implementation - will be supplied by super class
    875  */
    876 static	void
    877 setText8		(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_UINT8 t)
    878 {
    879 	ANTLR3_FPRINTF(stderr, "Internal error - implementor of superclass containing ANTLR3_TREE_ADAPTOR did not implement setText()\n");
    880 }
    881 
    882 static	pANTLR3_BASE_TREE
    883    getChild		(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i)
    884 {
    885 	ANTLR3_FPRINTF(stderr, "Internal error - implementor of superclass containing ANTLR3_TREE_ADAPTOR did not implement getChild()\n");
    886 	return NULL;
    887 }
    888 
    889 static	ANTLR3_UINT32
    890    getChildCount	(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE tree)
    891 {
    892 	ANTLR3_FPRINTF(stderr, "Internal error - implementor of superclass containing ANTLR3_TREE_ADAPTOR did not implement getChildCount()\n");
    893 	return 0;
    894 }
    895 
    896 /** Returns a uniqueID for the node. Because this is the C implementation
    897  *  we can just use its address suitably converted/cast to an integer.
    898  */
    899 static	ANTLR3_UINT32
    900    getUniqueID		(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE node)
    901 {
    902 	return	ANTLR3_UINT32_CAST(node);
    903 }
    904 
    905 static	ANTLR3_BOOLEAN
    906 isNilNode					(pANTLR3_BASE_TREE_ADAPTOR adaptor, pANTLR3_BASE_TREE t)
    907 {
    908 	return t->isNilNode(t);
    909 }
    910