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