bundles/org.simantics.databoard/cpp/DataBoardTest/libantlr3c-3.2/src/antlr3commontree.c

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