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

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