1// \file 2// 3// Implementation of ANTLR3 CommonTree, which you can use as a 4// starting point for your own tree. Though it is often easier just to tag things on 5// to the user pointer in the tree unless you are building a different type 6// of structure. 7// 8 9// [The "BSD licence"] 10// Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC 11// http://www.temporal-wave.com 12// http://www.linkedin.com/in/jimidle 13// 14// All rights reserved. 15// 16// Redistribution and use in source and binary forms, with or without 17// modification, are permitted provided that the following conditions 18// are met: 19// 1. Redistributions of source code must retain the above copyright 20// notice, this list of conditions and the following disclaimer. 21// 2. Redistributions in binary form must reproduce the above copyright 22// notice, this list of conditions and the following disclaimer in the 23// documentation and/or other materials provided with the distribution. 24// 3. The name of the author may not be used to endorse or promote products 25// derived from this software without specific prior written permission. 26// 27// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 28// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 29// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 30// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 31// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 32// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 33// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 34// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 35// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 36// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 37 38#include <antlr3commontree.h> 39 40 41static pANTLR3_COMMON_TOKEN getToken (pANTLR3_BASE_TREE tree); 42static pANTLR3_BASE_TREE dupNode (pANTLR3_BASE_TREE tree); 43static ANTLR3_BOOLEAN isNilNode (pANTLR3_BASE_TREE tree); 44static ANTLR3_UINT32 getType (pANTLR3_BASE_TREE tree); 45static pANTLR3_STRING getText (pANTLR3_BASE_TREE tree); 46static ANTLR3_UINT32 getLine (pANTLR3_BASE_TREE tree); 47static ANTLR3_UINT32 getCharPositionInLine (pANTLR3_BASE_TREE tree); 48static pANTLR3_STRING toString (pANTLR3_BASE_TREE tree); 49static pANTLR3_BASE_TREE getParent (pANTLR3_BASE_TREE tree); 50static void setParent (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE parent); 51static void setChildIndex (pANTLR3_BASE_TREE tree, ANTLR3_INT32 i); 52static ANTLR3_INT32 getChildIndex (pANTLR3_BASE_TREE tree); 53static void createChildrenList (pANTLR3_BASE_TREE tree); 54static void reuse (pANTLR3_BASE_TREE tree); 55 56// Factory functions for the Arboretum 57// 58static void newPool (pANTLR3_ARBORETUM factory); 59static pANTLR3_BASE_TREE newPoolTree (pANTLR3_ARBORETUM factory); 60static pANTLR3_BASE_TREE newFromTree (pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TREE tree); 61static pANTLR3_BASE_TREE newFromToken (pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TOKEN token); 62static void factoryClose (pANTLR3_ARBORETUM factory); 63 64ANTLR3_API pANTLR3_ARBORETUM 65antlr3ArboretumNew(pANTLR3_STRING_FACTORY strFactory) 66{ 67 pANTLR3_ARBORETUM factory; 68 69 // Allocate memory 70 // 71 factory = (pANTLR3_ARBORETUM) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_ARBORETUM)); 72 if (factory == NULL) 73 { 74 return NULL; 75 } 76 77 // Install a vector factory to create, track and free() any child 78 // node lists. 79 // 80 factory->vFactory = antlr3VectorFactoryNew(0); 81 if (factory->vFactory == NULL) 82 { 83 free(factory); 84 return NULL; 85 } 86 87 // We also keep a reclaim stack, so that any Nil nodes that are 88 // orphaned are not just left in the pool but are reused, other wise 89 // we create 6 times as many nilNodes as ordinary nodes and use loads of 90 // memory. Perhaps at some point, the analysis phase will generate better 91 // code and we won't need to do this here. 92 // 93 factory->nilStack = antlr3StackNew(0); 94 95 // Install factory API 96 // 97 factory->newTree = newPoolTree; 98 factory->newFromTree = newFromTree; 99 factory->newFromToken = newFromToken; 100 factory->close = factoryClose; 101 102 // Allocate the initial pool 103 // 104 factory->thisPool = -1; 105 factory->pools = NULL; 106 newPool(factory); 107 108 // Factory space is good, we now want to initialize our cheating token 109 // which one it is initialized is the model for all tokens we manufacture 110 // 111 antlr3SetCTAPI(&factory->unTruc); 112 113 // Set some initial variables for future copying, including a string factory 114 // that we can use later for converting trees to strings. 115 // 116 factory->unTruc.factory = factory; 117 factory->unTruc.baseTree.strFactory = strFactory; 118 119 return factory; 120 121} 122 123static void 124newPool(pANTLR3_ARBORETUM factory) 125{ 126 // Increment factory count 127 // 128 factory->thisPool++; 129 130 // Ensure we have enough pointers allocated 131 // 132 factory->pools = (pANTLR3_COMMON_TREE *) 133 ANTLR3_REALLOC( (void *)factory->pools, // Current pools pointer (starts at NULL) 134 (ANTLR3_UINT32)((factory->thisPool + 1) * sizeof(pANTLR3_COMMON_TREE *)) // Memory for new pool pointers 135 ); 136 137 // Allocate a new pool for the factory 138 // 139 factory->pools[factory->thisPool] = 140 (pANTLR3_COMMON_TREE) 141 ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_COMMON_TREE) * ANTLR3_FACTORY_POOL_SIZE)); 142 143 144 // Reset the counters 145 // 146 factory->nextTree = 0; 147 148 // Done 149 // 150 return; 151} 152 153static pANTLR3_BASE_TREE 154newPoolTree (pANTLR3_ARBORETUM factory) 155{ 156 pANTLR3_COMMON_TREE tree; 157 158 // If we have anything on the re claim stack, reuse that sucker first 159 // 160 tree = factory->nilStack->peek(factory->nilStack); 161 162 if (tree != NULL) 163 { 164 // Cool we got something we could reuse, it will have been cleaned up by 165 // whatever put it back on the stack (for instance if it had a child vector, 166 // that will have been cleared to hold zero entries and that vector will get reused too. 167 // It is the basetree pointer that is placed on the stack of course 168 // 169 factory->nilStack->pop(factory->nilStack); 170 return (pANTLR3_BASE_TREE)tree; 171 172 } 173 // See if we need a new tree pool before allocating a new tree 174 // 175 if (factory->nextTree >= ANTLR3_FACTORY_POOL_SIZE) 176 { 177 // We ran out of tokens in the current pool, so we need a new pool 178 // 179 newPool(factory); 180 } 181 182 // Assuming everything went well - we are trying for performance here so doing minimal 183 // error checking - then we can work out what the pointer is to the next commontree. 184 // 185 tree = factory->pools[factory->thisPool] + factory->nextTree; 186 factory->nextTree++; 187 188 // We have our token pointer now, so we can initialize it to the predefined model. 189 // 190 antlr3SetCTAPI(tree); 191 192 // Set some initial variables for future copying, including a string factory 193 // that we can use later for converting trees to strings. 194 // 195 tree->factory = factory; 196 tree->baseTree.strFactory = factory->unTruc.baseTree.strFactory; 197 198 // The super points to the common tree so we must override the one used by 199 // by the pre-built tree as otherwise we will always poitn to the same initial 200 // common tree and we might spend 3 hours trying to debug why - this would never 201 // happen to me of course! :-( 202 // 203 tree->baseTree.super = tree; 204 205 206 // And we are done 207 // 208 return &(tree->baseTree); 209} 210 211 212static pANTLR3_BASE_TREE 213newFromTree(pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TREE tree) 214{ 215 pANTLR3_BASE_TREE newTree; 216 217 newTree = factory->newTree(factory); 218 219 if (newTree == NULL) 220 { 221 return NULL; 222 } 223 224 // Pick up the payload we had in the supplied tree 225 // 226 ((pANTLR3_COMMON_TREE)(newTree->super))->token = tree->token; 227 newTree->u = tree->baseTree.u; // Copy any user pointer 228 229 return newTree; 230} 231 232static pANTLR3_BASE_TREE 233newFromToken(pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TOKEN token) 234{ 235 pANTLR3_BASE_TREE newTree; 236 237 newTree = factory->newTree(factory); 238 239 if (newTree == NULL) 240 { 241 return NULL; 242 } 243 244 // Pick up the payload we had in the supplied tree 245 // 246 ((pANTLR3_COMMON_TREE)(newTree->super))->token = token; 247 248 return newTree; 249} 250 251static void 252factoryClose (pANTLR3_ARBORETUM factory) 253{ 254 ANTLR3_INT32 poolCount; 255 256 // First close the vector factory that supplied all the child pointer 257 // vectors. 258 // 259 factory->vFactory->close(factory->vFactory); 260 261 if (factory->nilStack != NULL) 262 { 263 factory->nilStack->free(factory->nilStack); 264 } 265 266 // We now JUST free the pools because the C runtime CommonToken based tree 267 // cannot contain anything that was not made by this factory. 268 // 269 for (poolCount = 0; poolCount <= factory->thisPool; poolCount++) 270 { 271 // We can now free this pool allocation 272 // 273 ANTLR3_FREE(factory->pools[poolCount]); 274 factory->pools[poolCount] = NULL; 275 } 276 277 // All the pools are deallocated we can free the pointers to the pools 278 // now. 279 // 280 ANTLR3_FREE(factory->pools); 281 282 // Finally, we can free the space for the factory itself 283 // 284 ANTLR3_FREE(factory); 285} 286 287 288ANTLR3_API void 289antlr3SetCTAPI(pANTLR3_COMMON_TREE tree) 290{ 291 // Init base tree 292 // 293 antlr3BaseTreeNew(&(tree->baseTree)); 294 295 // We need a pointer to ourselves for 296 // the payload and few functions that we 297 // provide. 298 // 299 tree->baseTree.super = tree; 300 301 // Common tree overrides 302 303 tree->baseTree.isNilNode = isNilNode; 304 tree->baseTree.toString = toString; 305 tree->baseTree.dupNode = (void *(*)(pANTLR3_BASE_TREE))(dupNode); 306 tree->baseTree.getLine = getLine; 307 tree->baseTree.getCharPositionInLine = getCharPositionInLine; 308 tree->baseTree.toString = toString; 309 tree->baseTree.getType = getType; 310 tree->baseTree.getText = getText; 311 tree->baseTree.getToken = getToken; 312 tree->baseTree.getParent = getParent; 313 tree->baseTree.setParent = setParent; 314 tree->baseTree.setChildIndex = setChildIndex; 315 tree->baseTree.getChildIndex = getChildIndex; 316 tree->baseTree.createChildrenList = createChildrenList; 317 tree->baseTree.reuse = reuse; 318 tree->baseTree.free = NULL; // Factory trees have no free function 319 tree->baseTree.u = NULL; // Initialize user pointer 320 321 tree->baseTree.children = NULL; 322 323 tree->token = NULL; // No token as yet 324 tree->startIndex = 0; 325 tree->stopIndex = 0; 326 tree->parent = NULL; // No parent yet 327 tree->childIndex = -1; 328 329 return; 330} 331 332// -------------------------------------- 333// Non factory node constructors. 334// 335 336ANTLR3_API pANTLR3_COMMON_TREE 337antlr3CommonTreeNew() 338{ 339 pANTLR3_COMMON_TREE tree; 340 tree = ANTLR3_CALLOC(1, sizeof(ANTLR3_COMMON_TREE)); 341 342 if (tree == NULL) 343 { 344 return NULL; 345 } 346 347 antlr3SetCTAPI(tree); 348 349 return tree; 350} 351 352ANTLR3_API pANTLR3_COMMON_TREE 353antlr3CommonTreeNewFromToken(pANTLR3_COMMON_TOKEN token) 354{ 355 pANTLR3_COMMON_TREE newTree; 356 357 newTree = antlr3CommonTreeNew(); 358 359 if (newTree == NULL) 360 { 361 return NULL; 362 } 363 364 //Pick up the payload we had in the supplied tree 365 // 366 newTree->token = token; 367 return newTree; 368} 369 370/// Create a new vector for holding child nodes using the inbuilt 371/// vector factory. 372/// 373static void 374createChildrenList (pANTLR3_BASE_TREE tree) 375{ 376 tree->children = ((pANTLR3_COMMON_TREE)(tree->super))->factory->vFactory->newVector(((pANTLR3_COMMON_TREE)(tree->super))->factory->vFactory); 377} 378 379 380static pANTLR3_COMMON_TOKEN 381getToken (pANTLR3_BASE_TREE tree) 382{ 383 // The token is the payload of the common tree or other implementor 384 // so it is stored within ourselves, which is the super pointer.Note 385 // that whatever the actual token is, it is passed around by its pointer 386 // to the common token implementation, which it may of course surround 387 // with its own super structure. 388 // 389 return ((pANTLR3_COMMON_TREE)(tree->super))->token; 390} 391 392static pANTLR3_BASE_TREE 393dupNode (pANTLR3_BASE_TREE tree) 394{ 395 // The node we are duplicating is in fact the common tree (that's why we are here) 396 // so we use the super pointer to duplicate. 397 // 398 pANTLR3_COMMON_TREE theOld; 399 400 theOld = (pANTLR3_COMMON_TREE)(tree->super); 401 402 // The pointer we return is the base implementation of course 403 // 404 return theOld->factory->newFromTree(theOld->factory, theOld); 405} 406 407static ANTLR3_BOOLEAN 408isNilNode (pANTLR3_BASE_TREE tree) 409{ 410 // This is a Nil tree if it has no payload (Token in our case) 411 // 412 if (((pANTLR3_COMMON_TREE)(tree->super))->token == NULL) 413 { 414 return ANTLR3_TRUE; 415 } 416 else 417 { 418 return ANTLR3_FALSE; 419 } 420} 421 422static ANTLR3_UINT32 423getType (pANTLR3_BASE_TREE tree) 424{ 425 pANTLR3_COMMON_TREE theTree; 426 427 theTree = (pANTLR3_COMMON_TREE)(tree->super); 428 429 if (theTree->token == NULL) 430 { 431 return 0; 432 } 433 else 434 { 435 return theTree->token->getType(theTree->token); 436 } 437} 438 439static pANTLR3_STRING 440getText (pANTLR3_BASE_TREE tree) 441{ 442 return tree->toString(tree); 443} 444 445static ANTLR3_UINT32 getLine (pANTLR3_BASE_TREE tree) 446{ 447 pANTLR3_COMMON_TREE cTree; 448 pANTLR3_COMMON_TOKEN token; 449 450 cTree = (pANTLR3_COMMON_TREE)(tree->super); 451 452 token = cTree->token; 453 454 if (token == NULL || token->getLine(token) == 0) 455 { 456 if (tree->getChildCount(tree) > 0) 457 { 458 pANTLR3_BASE_TREE child; 459 460 child = (pANTLR3_BASE_TREE)tree->getChild(tree, 0); 461 return child->getLine(child); 462 } 463 return 0; 464 } 465 return token->getLine(token); 466} 467 468static ANTLR3_UINT32 getCharPositionInLine (pANTLR3_BASE_TREE tree) 469{ 470 pANTLR3_COMMON_TOKEN token; 471 472 token = ((pANTLR3_COMMON_TREE)(tree->super))->token; 473 474 if (token == NULL || token->getCharPositionInLine(token) == -1) 475 { 476 if (tree->getChildCount(tree) > 0) 477 { 478 pANTLR3_BASE_TREE child; 479 480 child = (pANTLR3_BASE_TREE)tree->getChild(tree, 0); 481 482 return child->getCharPositionInLine(child); 483 } 484 return 0; 485 } 486 return token->getCharPositionInLine(token); 487} 488 489static pANTLR3_STRING toString (pANTLR3_BASE_TREE tree) 490{ 491 if (tree->isNilNode(tree) == ANTLR3_TRUE) 492 { 493 pANTLR3_STRING nilNode; 494 495 nilNode = tree->strFactory->newPtr(tree->strFactory, (pANTLR3_UINT8)"nil", 3); 496 497 return nilNode; 498 } 499 500 return ((pANTLR3_COMMON_TREE)(tree->super))->token->getText(((pANTLR3_COMMON_TREE)(tree->super))->token); 501} 502 503static pANTLR3_BASE_TREE 504getParent (pANTLR3_BASE_TREE tree) 505{ 506 return & (((pANTLR3_COMMON_TREE)(tree->super))->parent->baseTree); 507} 508 509static void 510setParent (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE parent) 511{ 512 ((pANTLR3_COMMON_TREE)(tree->super))->parent = parent == NULL ? NULL : ((pANTLR3_COMMON_TREE)(parent->super))->parent; 513} 514 515static void 516setChildIndex (pANTLR3_BASE_TREE tree, ANTLR3_INT32 i) 517{ 518 ((pANTLR3_COMMON_TREE)(tree->super))->childIndex = i; 519} 520static ANTLR3_INT32 521getChildIndex (pANTLR3_BASE_TREE tree ) 522{ 523 return ((pANTLR3_COMMON_TREE)(tree->super))->childIndex; 524} 525 526/** Clean up any child vector that the tree might have, so it can be reused, 527 * then add it into the reuse stack. 528 */ 529static void 530reuse (pANTLR3_BASE_TREE tree) 531{ 532 pANTLR3_COMMON_TREE cTree; 533 534 cTree = (pANTLR3_COMMON_TREE)(tree->super); 535 536 if (cTree->factory != NULL) 537 { 538 539 if (cTree->baseTree.children != NULL) 540 { 541 542 cTree->baseTree.children->clear(cTree->baseTree.children); 543 } 544 cTree->factory->nilStack->push(cTree->factory->nilStack, tree, NULL); 545 546 } 547} 548