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 = (pANTLR3_BASE_TREE)child->children->get(child->children, i); 191 192 // ANTLR3 lists can be sparse, unlike Array Lists 193 // 194 if (entry != NULL) 195 { 196 ANTLR3_UINT32 count = tree->children->add(tree->children, entry, (void (ANTLR3_CDECL *) (void *))child->free); 197 198 entry->setChildIndex(entry, count - 1); 199 entry->setParent(entry, tree); 200 } 201 } 202 } 203 } 204 } 205 else 206 { 207 // Tree we are adding is not a Nil and might have children to copy 208 // 209 if (tree->children == NULL) 210 { 211 // No children in the tree we are adding to, so create a new list on 212 // the fly to hold them. 213 // 214 tree->createChildrenList(tree); 215 } 216 217 ANTLR3_UINT32 count = tree->children->add(tree->children, child, (void (ANTLR3_CDECL *)(void *))child->free); 218 child->setChildIndex(child, count - 1); 219 child->setParent(child, tree); 220 } 221 } 222 223 /// Add all elements of the supplied list as children of this node 224 /// 225 static void 226 addChildren (pANTLR3_BASE_TREE tree, pANTLR3_LIST kids) 227 { 228 ANTLR3_UINT32 i; 229 ANTLR3_UINT32 s; 230 231 s = kids->size(kids); 232 for (i = 0; i<s; i++) 233 { 234 tree->addChild(tree, (pANTLR3_BASE_TREE)(kids->get(kids, i+1))); 235 } 236 } 237 238 239 static void 240 setChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i, void * child) 241 { 242 if (tree->children == NULL) 243 { 244 tree->createChildrenList(tree); 245 } 246 tree->children->set(tree->children, i, child, NULL, ANTLR3_FALSE); 247 } 248 249 static void * 250 deleteChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i) 251 { 252 if ( tree->children == NULL) 253 { 254 return NULL; 255 } 256 257 return tree->children->remove(tree->children, i); 258 } 259 260 static void * 261 dupTree (pANTLR3_BASE_TREE tree) 262 { 263 pANTLR3_BASE_TREE newTree; 264 ANTLR3_UINT32 i; 265 ANTLR3_UINT32 s; 266 267 newTree = (pANTLR3_BASE_TREE)tree->dupNode (tree); 268 269 if (tree->children != NULL) 270 { 271 s = tree->children->size (tree->children); 272 273 for (i = 0; i < s; i++) 274 { 275 pANTLR3_BASE_TREE t; 276 pANTLR3_BASE_TREE newNode; 277 278 t = (pANTLR3_BASE_TREE) tree->children->get(tree->children, i); 279 280 if (t!= NULL) 281 { 282 newNode = (pANTLR3_BASE_TREE)t->dupTree(t); 283 newTree->addChild(newTree, newNode); 284 } 285 } 286 } 287 288 return newTree; 289 } 290 291 static pANTLR3_STRING 292 toStringTree (pANTLR3_BASE_TREE tree) 293 { 294 pANTLR3_STRING string; 295 ANTLR3_UINT32 i; 296 ANTLR3_UINT32 n; 297 pANTLR3_BASE_TREE t; 298 299 if (tree->children == NULL || tree->children->size(tree->children) == 0) 300 { 301 return tree->toString(tree); 302 } 303 304 /* Need a new string with nothing at all in it. 305 */ 306 string = tree->strFactory->newRaw(tree->strFactory); 307 308 if (tree->isNilNode(tree) == ANTLR3_FALSE) 309 { 310 string->append8 (string, "("); 311 string->appendS (string, tree->toString(tree)); 312 string->append8 (string, " "); 313 } 314 if (tree->children != NULL) 315 { 316 n = tree->children->size(tree->children); 317 318 for (i = 0; i < n; i++) 319 { 320 t = (pANTLR3_BASE_TREE) tree->children->get(tree->children, i); 321 322 if (i > 0) 323 { 324 string->append8(string, " "); 325 } 326 string->appendS(string, t->toStringTree(t)); 327 } 328 } 329 if (tree->isNilNode(tree) == ANTLR3_FALSE) 330 { 331 string->append8(string,")"); 332 } 333 334 return string; 335 } 336 337 /// Delete children from start to stop and replace with t even if t is 338 /// a list (nil-root tree). Num of children can increase or decrease. 339 /// For huge child lists, inserting children can force walking rest of 340 /// children to set their child index; could be slow. 341 /// 342 static void 343 replaceChildren (pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE newTree) 344 { 345 ANTLR3_INT32 replacingHowMany; // How many nodes will go away 346 ANTLR3_INT32 replacingWithHowMany; // How many nodes will replace them 347 ANTLR3_INT32 numNewChildren; // Tracking variable 348 ANTLR3_INT32 delta; // Difference in new vs existing count 349 350 ANTLR3_INT32 i; 351 ANTLR3_INT32 j; 352 353 pANTLR3_VECTOR newChildren; // Iterator for whatever we are going to add in 354 ANTLR3_BOOLEAN freeNewChildren; // Whether we created the iterator locally or reused it 355 356 if (parent->children == NULL) 357 { 358 ANTLR3_FPRINTF(stderr, "replaceChildren call: Indexes are invalid; no children in list for %s", parent->getText(parent)->chars); 359 return; 360 } 361 362 // Either use the existing list of children in the supplied nil node, or build a vector of the 363 // tree we were given if it is not a nil node, then we treat both situations exactly the same 364 // 365 if (newTree->isNilNode(newTree)) 366 { 367 newChildren = newTree->children; 368 freeNewChildren = ANTLR3_FALSE; // We must NO free this memory 369 } 370 else 371 { 372 newChildren = antlr3VectorNew(1); 373 if (newChildren == NULL) 374 { 375 ANTLR3_FPRINTF(stderr, "replaceChildren: out of memory!!"); 376 exit(1); 377 } 378 newChildren->add(newChildren, (void *)newTree, NULL); 379 380 freeNewChildren = ANTLR3_TRUE; // We must free this memory 381 } 382 383 // Initialize 384 // 385 replacingHowMany = stopChildIndex - startChildIndex + 1; 386 replacingWithHowMany = newChildren->size(newChildren); 387 delta = replacingHowMany - replacingWithHowMany; 388 numNewChildren = newChildren->size(newChildren); 389 390 // If it is the same number of nodes, then do a direct replacement 391 // 392 if (delta == 0) 393 { 394 pANTLR3_BASE_TREE child; 395 396 // Same number of nodes 397 // 398 j = 0; 399 for (i = startChildIndex; i <= stopChildIndex; i++) 400 { 401 child = (pANTLR3_BASE_TREE) newChildren->get(newChildren, j); 402 parent->children->set(parent->children, i, child, NULL, ANTLR3_FALSE); 403 child->setParent(child, parent); 404 child->setChildIndex(child, i); 405 } 406 } 407 else if (delta > 0) 408 { 409 ANTLR3_UINT32 indexToDelete; 410 411 // Less nodes than there were before 412 // reuse what we have then delete the rest 413 // 414 for (j = 0; j < numNewChildren; j++) 415 { 416 parent->children->set(parent->children, startChildIndex + j, newChildren->get(newChildren, j), NULL, ANTLR3_FALSE); 417 } 418 419 // We just delete the same index position until done 420 // 421 indexToDelete = startChildIndex + numNewChildren; 422 423 for (j = indexToDelete; j <= (ANTLR3_INT32)stopChildIndex; j++) 424 { 425 parent->children->remove(parent->children, indexToDelete); 426 } 427 428 parent->freshenPACIndexes(parent, startChildIndex); 429 } 430 else 431 { 432 ANTLR3_UINT32 numToInsert; 433 434 // More nodes than there were before 435 // Use what we can, then start adding 436 // 437 for (j = 0; j < replacingHowMany; j++) 438 { 439 parent->children->set(parent->children, startChildIndex + j, newChildren->get(newChildren, j), NULL, ANTLR3_FALSE); 440 } 441 442 numToInsert = replacingWithHowMany - replacingHowMany; 443 444 for (j = replacingHowMany; j < replacingWithHowMany; j++) 445 { 446 parent->children->add(parent->children, newChildren->get(newChildren, j), NULL); 447 } 448 449 parent->freshenPACIndexes(parent, startChildIndex); 450 } 451 452 if (freeNewChildren == ANTLR3_TRUE) 453 { 454 ANTLR3_FREE(newChildren->elements); 455 newChildren->elements = NULL; 456 newChildren->size = 0; 457 ANTLR3_FREE(newChildren); // Will not free the nodes 458 } 459 } 460 461 /// Set the parent and child indexes for all children of the 462 /// supplied tree. 463 /// 464 static void 465 freshenPACIndexesAll(pANTLR3_BASE_TREE tree) 466 { 467 tree->freshenPACIndexes(tree, 0); 468 } 469 470 /// Set the parent and child indexes for some of the children of the 471 /// supplied tree, starting with the child at the supplied index. 472 /// 473 static void 474 freshenPACIndexes (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 offset) 475 { 476 ANTLR3_UINT32 count; 477 ANTLR3_UINT32 c; 478 479 count = tree->getChildCount(tree); // How many children do we have 480 481 // Loop from the supplied index and set the indexes and parent 482 // 483 for (c = offset; c < count; c++) 484 { 485 pANTLR3_BASE_TREE child; 486 487 child = (pANTLR3_BASE_TREE)tree->getChild(tree, c); 488 489 child->setChildIndex(child, c); 490 child->setParent(child, tree); 491 } 492 } 493 494