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 36static void * getChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i); 37static ANTLR3_UINT32 getChildCount (pANTLR3_BASE_TREE tree); 38static ANTLR3_UINT32 getCharPositionInLine 39(pANTLR3_BASE_TREE tree); 40static ANTLR3_UINT32 getLine (pANTLR3_BASE_TREE tree); 41static pANTLR3_BASE_TREE 42getFirstChildWithType 43(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 type); 44static void addChild (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE child); 45static void addChildren (pANTLR3_BASE_TREE tree, pANTLR3_LIST kids); 46static void replaceChildren (pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE t); 47 48static void freshenPACIndexesAll(pANTLR3_BASE_TREE tree); 49static void freshenPACIndexes (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 offset); 50 51static void setChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i, void * child); 52static void * deleteChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i); 53static void * dupTree (pANTLR3_BASE_TREE tree); 54static pANTLR3_STRING toStringTree (pANTLR3_BASE_TREE tree); 55 56 57ANTLR3_API pANTLR3_BASE_TREE 58antlr3BaseTreeNew(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 83static ANTLR3_UINT32 84getCharPositionInLine (pANTLR3_BASE_TREE tree) 85{ 86 return 0; 87} 88 89static ANTLR3_UINT32 90getLine (pANTLR3_BASE_TREE tree) 91{ 92 return 0; 93} 94static pANTLR3_BASE_TREE 95getFirstChildWithType (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 118static void * 119getChild (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 130static ANTLR3_UINT32 131getChildCount (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 143void 144addChild (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/// 221static void 222addChildren (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 235static void 236setChild (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 245static void * 246deleteChild (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 256static void * 257dupTree (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 287static pANTLR3_STRING 288toStringTree (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/// 338static void 339replaceChildren (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/// 460static void 461freshenPACIndexesAll(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/// 469static void 470freshenPACIndexes (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 490