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

   1 #include    <antlr3basetree.h>\r
   2 \r
   3 #ifdef  ANTLR3_WINDOWS\r
   4 #pragma warning( disable : 4100 )\r
   5 #endif\r
   6 \r
   7 // [The "BSD licence"]\r
   8 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC\r
   9 // http://www.temporal-wave.com\r
  10 // http://www.linkedin.com/in/jimidle\r
  11 //\r
  12 // All rights reserved.\r
  13 //\r
  14 // Redistribution and use in source and binary forms, with or without\r
  15 // modification, are permitted provided that the following conditions\r
  16 // are met:\r
  17 // 1. Redistributions of source code must retain the above copyright\r
  18 //    notice, this list of conditions and the following disclaimer.\r
  19 // 2. Redistributions in binary form must reproduce the above copyright\r
  20 //    notice, this list of conditions and the following disclaimer in the\r
  21 //    documentation and/or other materials provided with the distribution.\r
  22 // 3. The name of the author may not be used to endorse or promote products\r
  23 //    derived from this software without specific prior written permission.\r
  24 //\r
  25 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR\r
  26 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\r
  27 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.\r
  28 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,\r
  29 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\r
  30 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\r
  31 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\r
  32 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\r
  33 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF\r
  34 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
  35 \r
  36 static void                             *       getChild                        (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i);\r
  37 static ANTLR3_UINT32            getChildCount           (pANTLR3_BASE_TREE tree);\r
  38 static ANTLR3_UINT32            getCharPositionInLine\r
  39 (pANTLR3_BASE_TREE tree);\r
  40 static ANTLR3_UINT32            getLine                         (pANTLR3_BASE_TREE tree);\r
  41 static pANTLR3_BASE_TREE    \r
  42 getFirstChildWithType\r
  43 (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 type);\r
  44 static void                                     addChild                        (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE child);\r
  45 static void                                     addChildren                     (pANTLR3_BASE_TREE tree, pANTLR3_LIST kids);\r
  46 static void                                     replaceChildren         (pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE t);\r
  47 \r
  48 static  void                            freshenPACIndexesAll(pANTLR3_BASE_TREE tree);\r
  49 static  void                            freshenPACIndexes       (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 offset);\r
  50 \r
  51 static void                                     setChild                        (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i, void * child);\r
  52 static void                             *       deleteChild                     (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i);\r
  53 static void                             *       dupTree                         (pANTLR3_BASE_TREE tree);\r
  54 static pANTLR3_STRING           toStringTree            (pANTLR3_BASE_TREE tree);\r
  55 \r
  56 \r
  57 ANTLR3_API pANTLR3_BASE_TREE\r
  58 antlr3BaseTreeNew(pANTLR3_BASE_TREE  tree)\r
  59 {\r
  60         /* api */\r
  61         tree->getChild                          = getChild;\r
  62         tree->getChildCount                     = getChildCount;\r
  63         tree->addChild                          = (void (*)(pANTLR3_BASE_TREE, void *))(addChild);\r
  64         tree->addChildren                       = addChildren;\r
  65         tree->setChild                          = setChild;\r
  66         tree->deleteChild                       = deleteChild;\r
  67         tree->dupTree                           = dupTree;\r
  68         tree->toStringTree                      = toStringTree;\r
  69         tree->getCharPositionInLine     = getCharPositionInLine;\r
  70         tree->getLine                           = getLine;\r
  71         tree->replaceChildren           = replaceChildren;\r
  72         tree->freshenPACIndexesAll      = freshenPACIndexesAll;\r
  73         tree->freshenPACIndexes         = freshenPACIndexes;\r
  74         tree->getFirstChildWithType     = (void *(*)(pANTLR3_BASE_TREE, ANTLR3_UINT32))(getFirstChildWithType);\r
  75         tree->children                          = NULL;\r
  76         tree->strFactory                        = NULL;\r
  77 \r
  78         /* Rest must be filled in by caller.\r
  79         */\r
  80         return  tree;\r
  81 }\r
  82 \r
  83 static ANTLR3_UINT32    \r
  84 getCharPositionInLine   (pANTLR3_BASE_TREE tree)\r
  85 {\r
  86         return  0;\r
  87 }\r
  88 \r
  89 static ANTLR3_UINT32    \r
  90 getLine (pANTLR3_BASE_TREE tree)\r
  91 {\r
  92         return  0;\r
  93 }\r
  94 static pANTLR3_BASE_TREE\r
  95 getFirstChildWithType   (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 type)\r
  96 {\r
  97         ANTLR3_UINT32   i;\r
  98         ANTLR3_UINT32   cs;\r
  99 \r
 100         pANTLR3_BASE_TREE       t;\r
 101         if      (tree->children != NULL)\r
 102         {\r
 103                 cs      = tree->children->size(tree->children);\r
 104                 for     (i = 0; i < cs; i++)\r
 105                 {\r
 106                         t = (pANTLR3_BASE_TREE) (tree->children->get(tree->children, i));\r
 107                         if  (tree->getType(t) == type)\r
 108                         {\r
 109                                 return  (pANTLR3_BASE_TREE)t;\r
 110                         }\r
 111                 }\r
 112         }\r
 113         return  NULL;\r
 114 }\r
 115 \r
 116 \r
 117 \r
 118 static void    *\r
 119 getChild                (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i)\r
 120 {\r
 121         if      (      tree->children == NULL\r
 122                 || i >= tree->children->size(tree->children))\r
 123         {\r
 124                 return NULL;\r
 125         }\r
 126         return  tree->children->get(tree->children, i);\r
 127 }\r
 128 \r
 129 \r
 130 static ANTLR3_UINT32\r
 131 getChildCount   (pANTLR3_BASE_TREE tree)\r
 132 {\r
 133         if      (tree->children == NULL)\r
 134         {\r
 135                 return 0;\r
 136         }\r
 137         else\r
 138         {\r
 139                 return  tree->children->size(tree->children);\r
 140         }\r
 141 }\r
 142 \r
 143 void        \r
 144 addChild (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE child)\r
 145 {\r
 146         ANTLR3_UINT32   n;\r
 147         ANTLR3_UINT32   i;\r
 148 \r
 149         if      (child == NULL)\r
 150         {\r
 151                 return;\r
 152         }\r
 153 \r
 154         if      (child->isNilNode(child) == ANTLR3_TRUE)\r
 155         {\r
 156                 if  (child->children != NULL && child->children == tree->children)\r
 157                 {\r
 158                         // TODO: Change to exception rather than ANTLR3_FPRINTF?\r
 159                         //\r
 160                         ANTLR3_FPRINTF(stderr, "ANTLR3: An attempt was made to add a child list to itself!\n");\r
 161                         return;\r
 162                 }\r
 163 \r
 164         // Add all of the children's children to this list\r
 165         //\r
 166         if (child->children != NULL)\r
 167         {\r
 168             if (tree->children == NULL)\r
 169             {\r
 170                 // We are build ing the tree structure here, so we need not\r
 171                 // worry about duplication of pointers as the tree node\r
 172                 // factory will only clean up each node once. So we just\r
 173                 // copy in the child's children pointer as the child is\r
 174                 // a nil node (has not root itself).\r
 175                 //\r
 176                 tree->children = child->children;\r
 177                 child->children = NULL;\r
 178                 freshenPACIndexesAll(tree);\r
 179                 \r
 180             }\r
 181             else\r
 182             {\r
 183                 // Need to copy the children\r
 184                 //\r
 185                 n = child->children->size(child->children);\r
 186 \r
 187                 for (i = 0; i < n; i++)\r
 188                 {\r
 189                     pANTLR3_BASE_TREE entry;\r
 190                     entry = child->children->get(child->children, i);\r
 191 \r
 192                     // ANTLR3 lists can be sparse, unlike Array Lists\r
 193                     //\r
 194                     if (entry != NULL)\r
 195                     {\r
 196                         tree->children->add(tree->children, entry, (void (ANTLR3_CDECL *) (void *))child->free);\r
 197                     }\r
 198                 }\r
 199             }\r
 200                 }\r
 201         }\r
 202         else\r
 203         {\r
 204                 // Tree we are adding is not a Nil and might have children to copy\r
 205                 //\r
 206                 if  (tree->children == NULL)\r
 207                 {\r
 208                         // No children in the tree we are adding to, so create a new list on\r
 209                         // the fly to hold them.\r
 210                         //\r
 211                         tree->createChildrenList(tree);\r
 212                 }\r
 213 \r
 214                 tree->children->add(tree->children, child, (void (ANTLR3_CDECL *)(void *))child->free);\r
 215                 \r
 216         }\r
 217 }\r
 218 \r
 219 /// Add all elements of the supplied list as children of this node\r
 220 ///\r
 221 static void\r
 222 addChildren     (pANTLR3_BASE_TREE tree, pANTLR3_LIST kids)\r
 223 {\r
 224         ANTLR3_UINT32    i;\r
 225         ANTLR3_UINT32    s;\r
 226 \r
 227         s = kids->size(kids);\r
 228         for     (i = 0; i<s; i++)\r
 229         {\r
 230                 tree->addChild(tree, (pANTLR3_BASE_TREE)(kids->get(kids, i+1)));\r
 231         }\r
 232 }\r
 233 \r
 234 \r
 235 static    void\r
 236 setChild        (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i, void * child)\r
 237 {\r
 238         if      (tree->children == NULL)\r
 239         {\r
 240                 tree->createChildrenList(tree);\r
 241         }\r
 242         tree->children->set(tree->children, i, child, NULL, ANTLR3_FALSE);\r
 243 }\r
 244 \r
 245 static void    *\r
 246 deleteChild     (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i)\r
 247 {\r
 248         if      ( tree->children == NULL)\r
 249         {\r
 250                 return  NULL;\r
 251         }\r
 252 \r
 253         return  tree->children->remove(tree->children, i);\r
 254 }\r
 255 \r
 256 static void    *\r
 257 dupTree         (pANTLR3_BASE_TREE tree)\r
 258 {\r
 259         pANTLR3_BASE_TREE       newTree;\r
 260         ANTLR3_UINT32   i;\r
 261         ANTLR3_UINT32   s;\r
 262 \r
 263         newTree = tree->dupNode     (tree);\r
 264 \r
 265         if      (tree->children != NULL)\r
 266         {\r
 267                 s           = tree->children->size  (tree->children);\r
 268 \r
 269                 for     (i = 0; i < s; i++)\r
 270                 {\r
 271                         pANTLR3_BASE_TREE    t;\r
 272                         pANTLR3_BASE_TREE    newNode;\r
 273 \r
 274                         t   = (pANTLR3_BASE_TREE) tree->children->get(tree->children, i);\r
 275 \r
 276                         if  (t!= NULL)\r
 277                         {\r
 278                                 newNode     = t->dupTree(t);\r
 279                                 newTree->addChild(newTree, newNode);\r
 280                         }\r
 281                 }\r
 282         }\r
 283 \r
 284         return newTree;\r
 285 }\r
 286 \r
 287 static pANTLR3_STRING\r
 288 toStringTree    (pANTLR3_BASE_TREE tree)\r
 289 {\r
 290         pANTLR3_STRING  string;\r
 291         ANTLR3_UINT32   i;\r
 292         ANTLR3_UINT32   n;\r
 293         pANTLR3_BASE_TREE   t;\r
 294 \r
 295         if      (tree->children == NULL || tree->children->size(tree->children) == 0)\r
 296         {\r
 297                 return  tree->toString(tree);\r
 298         }\r
 299 \r
 300         /* Need a new string with nothing at all in it.\r
 301         */\r
 302         string  = tree->strFactory->newRaw(tree->strFactory);\r
 303 \r
 304         if      (tree->isNilNode(tree) == ANTLR3_FALSE)\r
 305         {\r
 306                 string->append8 (string, "(");\r
 307                 string->appendS (string, tree->toString(tree));\r
 308                 string->append8 (string, " ");\r
 309         }\r
 310         if      (tree->children != NULL)\r
 311         {\r
 312                 n = tree->children->size(tree->children);\r
 313 \r
 314                 for     (i = 0; i < n; i++)\r
 315                 {   \r
 316                         t   = (pANTLR3_BASE_TREE) tree->children->get(tree->children, i);\r
 317 \r
 318                         if  (i > 0)\r
 319                         {\r
 320                                 string->append8(string, " ");\r
 321                         }\r
 322                         string->appendS(string, t->toStringTree(t));\r
 323                 }\r
 324         }\r
 325         if      (tree->isNilNode(tree) == ANTLR3_FALSE)\r
 326         {\r
 327                 string->append8(string,")");\r
 328         }\r
 329 \r
 330         return  string;\r
 331 }\r
 332 \r
 333 /// Delete children from start to stop and replace with t even if t is\r
 334 /// a list (nil-root tree). Num of children can increase or decrease.\r
 335 /// For huge child lists, inserting children can force walking rest of\r
 336 /// children to set their child index; could be slow.\r
 337 ///\r
 338 static void                                     \r
 339 replaceChildren         (pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE newTree)\r
 340 {\r
 341         ANTLR3_INT32    replacingHowMany;               // How many nodes will go away\r
 342         ANTLR3_INT32    replacingWithHowMany;   // How many nodes will replace them\r
 343         ANTLR3_INT32    numNewChildren;                 // Tracking variable\r
 344         ANTLR3_INT32    delta;                                  // Difference in new vs existing count\r
 345 \r
 346         ANTLR3_INT32    i;\r
 347         ANTLR3_INT32    j;\r
 348 \r
 349         pANTLR3_VECTOR  newChildren;                    // Iterator for whatever we are going to add in\r
 350         ANTLR3_BOOLEAN  freeNewChildren;                // Whether we created the iterator locally or reused it\r
 351 \r
 352         if      (parent->children == NULL)\r
 353         {\r
 354                 ANTLR3_FPRINTF(stderr, "replaceChildren call: Indexes are invalid; no children in list for %s", parent->getText(parent)->chars);\r
 355                 return;\r
 356         }\r
 357 \r
 358         // Either use the existing list of children in the supplied nil node, or build a vector of the\r
 359         // tree we were given if it is not a nil node, then we treat both situations exactly the same\r
 360         //\r
 361         if      (newTree->isNilNode(newTree))\r
 362         {\r
 363                 newChildren = newTree->children;\r
 364                 freeNewChildren = ANTLR3_FALSE;         // We must NO free this memory\r
 365         }\r
 366         else\r
 367         {\r
 368                 newChildren = antlr3VectorNew(1);\r
 369                 if      (newChildren == NULL)\r
 370                 {\r
 371                         ANTLR3_FPRINTF(stderr, "replaceChildren: out of memory!!");\r
 372                         exit(1);\r
 373                 }\r
 374                 newChildren->add(newChildren, (void *)newTree, NULL);\r
 375 \r
 376                 freeNewChildren = ANTLR3_TRUE;          // We must free this memory\r
 377         }\r
 378 \r
 379         // Initialize\r
 380         //\r
 381         replacingHowMany                = stopChildIndex - startChildIndex + 1;\r
 382         replacingWithHowMany    = newChildren->size(newChildren);\r
 383         delta                                   = replacingHowMany - replacingWithHowMany;\r
 384         numNewChildren                  = newChildren->size(newChildren);\r
 385 \r
 386         // If it is the same number of nodes, then do a direct replacement\r
 387         //\r
 388         if      (delta == 0)\r
 389         {\r
 390                 pANTLR3_BASE_TREE       child;\r
 391 \r
 392                 // Same number of nodes\r
 393                 //\r
 394                 j       = 0;\r
 395                 for     (i = startChildIndex; i <= stopChildIndex; i++)\r
 396                 {\r
 397                         child = (pANTLR3_BASE_TREE) newChildren->get(newChildren, j);\r
 398                         parent->children->set(parent->children, i, child, NULL, ANTLR3_FALSE);\r
 399                         child->setParent(child, parent);\r
 400                         child->setChildIndex(child, i);\r
 401                 }\r
 402         }\r
 403         else if (delta > 0)\r
 404         {\r
 405                 ANTLR3_UINT32   indexToDelete;\r
 406 \r
 407                 // Less nodes than there were before\r
 408                 // reuse what we have then delete the rest\r
 409                 //\r
 410                 for     (j = 0; j < numNewChildren; j++)\r
 411                 {\r
 412                         parent->children->set(parent->children, startChildIndex + j, newChildren->get(newChildren, j), NULL, ANTLR3_FALSE);\r
 413                 }\r
 414 \r
 415                 // We just delete the same index position until done\r
 416                 //\r
 417                 indexToDelete = startChildIndex + numNewChildren;\r
 418 \r
 419                 for     (j = indexToDelete; j <= (ANTLR3_INT32)stopChildIndex; j++)\r
 420                 {\r
 421                         parent->children->remove(parent->children, indexToDelete);\r
 422                 }\r
 423 \r
 424                 parent->freshenPACIndexes(parent, startChildIndex);\r
 425         }\r
 426         else\r
 427         {\r
 428                 ANTLR3_UINT32 numToInsert;\r
 429 \r
 430                 // More nodes than there were before\r
 431                 // Use what we can, then start adding\r
 432                 //\r
 433                 for     (j = 0; j < replacingHowMany; j++)\r
 434                 {\r
 435                         parent->children->set(parent->children, startChildIndex + j, newChildren->get(newChildren, j), NULL, ANTLR3_FALSE);\r
 436                 }\r
 437 \r
 438                 numToInsert = replacingWithHowMany - replacingHowMany;\r
 439 \r
 440                 for     (j = replacingHowMany; j < replacingWithHowMany; j++)\r
 441                 {\r
 442                         parent->children->add(parent->children, newChildren->get(newChildren, j), NULL);\r
 443                 }\r
 444 \r
 445                 parent->freshenPACIndexes(parent, startChildIndex);\r
 446         }\r
 447 \r
 448         if      (freeNewChildren == ANTLR3_TRUE)\r
 449         {\r
 450                 ANTLR3_FREE(newChildren->elements);\r
 451                 newChildren->elements = NULL;\r
 452                 newChildren->size = 0;\r
 453                 ANTLR3_FREE(newChildren);               // Will not free the nodes\r
 454         }\r
 455 }\r
 456 \r
 457 /// Set the parent and child indexes for all children of the\r
 458 /// supplied tree.\r
 459 ///\r
 460 static  void\r
 461 freshenPACIndexesAll(pANTLR3_BASE_TREE tree)\r
 462 {\r
 463         tree->freshenPACIndexes(tree, 0);\r
 464 }\r
 465 \r
 466 /// Set the parent and child indexes for some of the children of the\r
 467 /// supplied tree, starting with the child at the supplied index.\r
 468 ///\r
 469 static  void\r
 470 freshenPACIndexes       (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 offset)\r
 471 {\r
 472         ANTLR3_UINT32   count;\r
 473         ANTLR3_UINT32   c;\r
 474 \r
 475         count   = tree->getChildCount(tree);            // How many children do we have \r
 476 \r
 477         // Loop from the supplied index and set the indexes and parent\r
 478         //\r
 479         for     (c = offset; c < count; c++)\r
 480         {\r
 481                 pANTLR3_BASE_TREE       child;\r
 482 \r
 483                 child = tree->getChild(tree, c);\r
 484 \r
 485                 child->setChildIndex(child, c);\r
 486                 child->setParent(child, tree);\r
 487         }\r
 488 }\r
 489 \r