| #include <antlr3basetree.h> |
| |
| #ifdef ANTLR3_WINDOWS |
| #pragma warning( disable : 4100 ) |
| #endif |
| |
| // [The "BSD licence"] |
| // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC |
| // http://www.temporal-wave.com |
| // http://www.linkedin.com/in/jimidle |
| // |
| // All rights reserved. |
| // |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions |
| // are met: |
| // 1. Redistributions of source code must retain the above copyright |
| // notice, this list of conditions and the following disclaimer. |
| // 2. Redistributions in binary form must reproduce the above copyright |
| // notice, this list of conditions and the following disclaimer in the |
| // documentation and/or other materials provided with the distribution. |
| // 3. The name of the author may not be used to endorse or promote products |
| // derived from this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| static void * getChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i); |
| static ANTLR3_UINT32 getChildCount (pANTLR3_BASE_TREE tree); |
| static ANTLR3_UINT32 getCharPositionInLine |
| (pANTLR3_BASE_TREE tree); |
| static ANTLR3_UINT32 getLine (pANTLR3_BASE_TREE tree); |
| static pANTLR3_BASE_TREE |
| getFirstChildWithType |
| (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 type); |
| static void addChild (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE child); |
| static void addChildren (pANTLR3_BASE_TREE tree, pANTLR3_LIST kids); |
| static void replaceChildren (pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE t); |
| |
| static void freshenPACIndexesAll(pANTLR3_BASE_TREE tree); |
| static void freshenPACIndexes (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 offset); |
| |
| static void setChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i, void * child); |
| static void * deleteChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i); |
| static void * dupTree (pANTLR3_BASE_TREE tree); |
| static pANTLR3_STRING toStringTree (pANTLR3_BASE_TREE tree); |
| |
| |
| ANTLR3_API pANTLR3_BASE_TREE |
| antlr3BaseTreeNew(pANTLR3_BASE_TREE tree) |
| { |
| /* api */ |
| tree->getChild = getChild; |
| tree->getChildCount = getChildCount; |
| tree->addChild = (void (*)(pANTLR3_BASE_TREE, void *))(addChild); |
| tree->addChildren = addChildren; |
| tree->setChild = setChild; |
| tree->deleteChild = deleteChild; |
| tree->dupTree = dupTree; |
| tree->toStringTree = toStringTree; |
| tree->getCharPositionInLine = getCharPositionInLine; |
| tree->getLine = getLine; |
| tree->replaceChildren = replaceChildren; |
| tree->freshenPACIndexesAll = freshenPACIndexesAll; |
| tree->freshenPACIndexes = freshenPACIndexes; |
| tree->getFirstChildWithType = (void *(*)(pANTLR3_BASE_TREE, ANTLR3_UINT32))(getFirstChildWithType); |
| tree->children = NULL; |
| tree->strFactory = NULL; |
| |
| /* Rest must be filled in by caller. |
| */ |
| return tree; |
| } |
| |
| static ANTLR3_UINT32 |
| getCharPositionInLine (pANTLR3_BASE_TREE tree) |
| { |
| return 0; |
| } |
| |
| static ANTLR3_UINT32 |
| getLine (pANTLR3_BASE_TREE tree) |
| { |
| return 0; |
| } |
| static pANTLR3_BASE_TREE |
| getFirstChildWithType (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 type) |
| { |
| ANTLR3_UINT32 i; |
| ANTLR3_UINT32 cs; |
| |
| pANTLR3_BASE_TREE t; |
| if (tree->children != NULL) |
| { |
| cs = tree->children->size(tree->children); |
| for (i = 0; i < cs; i++) |
| { |
| t = (pANTLR3_BASE_TREE) (tree->children->get(tree->children, i)); |
| if (tree->getType(t) == type) |
| { |
| return (pANTLR3_BASE_TREE)t; |
| } |
| } |
| } |
| return NULL; |
| } |
| |
| |
| |
| static void * |
| getChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i) |
| { |
| if ( tree->children == NULL |
| || i >= tree->children->size(tree->children)) |
| { |
| return NULL; |
| } |
| return tree->children->get(tree->children, i); |
| } |
| |
| |
| static ANTLR3_UINT32 |
| getChildCount (pANTLR3_BASE_TREE tree) |
| { |
| if (tree->children == NULL) |
| { |
| return 0; |
| } |
| else |
| { |
| return tree->children->size(tree->children); |
| } |
| } |
| |
| void |
| addChild (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE child) |
| { |
| ANTLR3_UINT32 n; |
| ANTLR3_UINT32 i; |
| |
| if (child == NULL) |
| { |
| return; |
| } |
| |
| if (child->isNilNode(child) == ANTLR3_TRUE) |
| { |
| if (child->children != NULL && child->children == tree->children) |
| { |
| // TODO: Change to exception rather than ANTLR3_FPRINTF? |
| // |
| ANTLR3_FPRINTF(stderr, "ANTLR3: An attempt was made to add a child list to itself!\n"); |
| return; |
| } |
| |
| // Add all of the children's children to this list |
| // |
| if (child->children != NULL) |
| { |
| if (tree->children == NULL) |
| { |
| // We are build ing the tree structure here, so we need not |
| // worry about duplication of pointers as the tree node |
| // factory will only clean up each node once. So we just |
| // copy in the child's children pointer as the child is |
| // a nil node (has not root itself). |
| // |
| tree->children = child->children; |
| child->children = NULL; |
| freshenPACIndexesAll(tree); |
| |
| } |
| else |
| { |
| // Need to copy the children |
| // |
| n = child->children->size(child->children); |
| |
| for (i = 0; i < n; i++) |
| { |
| pANTLR3_BASE_TREE entry; |
| entry = child->children->get(child->children, i); |
| |
| // ANTLR3 lists can be sparse, unlike Array Lists |
| // |
| if (entry != NULL) |
| { |
| tree->children->add(tree->children, entry, (void (ANTLR3_CDECL *) (void *))child->free); |
| } |
| } |
| } |
| } |
| } |
| else |
| { |
| // Tree we are adding is not a Nil and might have children to copy |
| // |
| if (tree->children == NULL) |
| { |
| // No children in the tree we are adding to, so create a new list on |
| // the fly to hold them. |
| // |
| tree->createChildrenList(tree); |
| } |
| |
| tree->children->add(tree->children, child, (void (ANTLR3_CDECL *)(void *))child->free); |
| |
| } |
| } |
| |
| /// Add all elements of the supplied list as children of this node |
| /// |
| static void |
| addChildren (pANTLR3_BASE_TREE tree, pANTLR3_LIST kids) |
| { |
| ANTLR3_UINT32 i; |
| ANTLR3_UINT32 s; |
| |
| s = kids->size(kids); |
| for (i = 0; i<s; i++) |
| { |
| tree->addChild(tree, (pANTLR3_BASE_TREE)(kids->get(kids, i+1))); |
| } |
| } |
| |
| |
| static void |
| setChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i, void * child) |
| { |
| if (tree->children == NULL) |
| { |
| tree->createChildrenList(tree); |
| } |
| tree->children->set(tree->children, i, child, NULL, ANTLR3_FALSE); |
| } |
| |
| static void * |
| deleteChild (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i) |
| { |
| if ( tree->children == NULL) |
| { |
| return NULL; |
| } |
| |
| return tree->children->remove(tree->children, i); |
| } |
| |
| static void * |
| dupTree (pANTLR3_BASE_TREE tree) |
| { |
| pANTLR3_BASE_TREE newTree; |
| ANTLR3_UINT32 i; |
| ANTLR3_UINT32 s; |
| |
| newTree = tree->dupNode (tree); |
| |
| if (tree->children != NULL) |
| { |
| s = tree->children->size (tree->children); |
| |
| for (i = 0; i < s; i++) |
| { |
| pANTLR3_BASE_TREE t; |
| pANTLR3_BASE_TREE newNode; |
| |
| t = (pANTLR3_BASE_TREE) tree->children->get(tree->children, i); |
| |
| if (t!= NULL) |
| { |
| newNode = t->dupTree(t); |
| newTree->addChild(newTree, newNode); |
| } |
| } |
| } |
| |
| return newTree; |
| } |
| |
| static pANTLR3_STRING |
| toStringTree (pANTLR3_BASE_TREE tree) |
| { |
| pANTLR3_STRING string; |
| ANTLR3_UINT32 i; |
| ANTLR3_UINT32 n; |
| pANTLR3_BASE_TREE t; |
| |
| if (tree->children == NULL || tree->children->size(tree->children) == 0) |
| { |
| return tree->toString(tree); |
| } |
| |
| /* Need a new string with nothing at all in it. |
| */ |
| string = tree->strFactory->newRaw(tree->strFactory); |
| |
| if (tree->isNilNode(tree) == ANTLR3_FALSE) |
| { |
| string->append8 (string, "("); |
| string->appendS (string, tree->toString(tree)); |
| string->append8 (string, " "); |
| } |
| if (tree->children != NULL) |
| { |
| n = tree->children->size(tree->children); |
| |
| for (i = 0; i < n; i++) |
| { |
| t = (pANTLR3_BASE_TREE) tree->children->get(tree->children, i); |
| |
| if (i > 0) |
| { |
| string->append8(string, " "); |
| } |
| string->appendS(string, t->toStringTree(t)); |
| } |
| } |
| if (tree->isNilNode(tree) == ANTLR3_FALSE) |
| { |
| string->append8(string,")"); |
| } |
| |
| return string; |
| } |
| |
| /// Delete children from start to stop and replace with t even if t is |
| /// a list (nil-root tree). Num of children can increase or decrease. |
| /// For huge child lists, inserting children can force walking rest of |
| /// children to set their child index; could be slow. |
| /// |
| static void |
| replaceChildren (pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE newTree) |
| { |
| ANTLR3_INT32 replacingHowMany; // How many nodes will go away |
| ANTLR3_INT32 replacingWithHowMany; // How many nodes will replace them |
| ANTLR3_INT32 numNewChildren; // Tracking variable |
| ANTLR3_INT32 delta; // Difference in new vs existing count |
| |
| ANTLR3_INT32 i; |
| ANTLR3_INT32 j; |
| |
| pANTLR3_VECTOR newChildren; // Iterator for whatever we are going to add in |
| ANTLR3_BOOLEAN freeNewChildren; // Whether we created the iterator locally or reused it |
| |
| if (parent->children == NULL) |
| { |
| ANTLR3_FPRINTF(stderr, "replaceChildren call: Indexes are invalid; no children in list for %s", parent->getText(parent)->chars); |
| return; |
| } |
| |
| // Either use the existing list of children in the supplied nil node, or build a vector of the |
| // tree we were given if it is not a nil node, then we treat both situations exactly the same |
| // |
| if (newTree->isNilNode(newTree)) |
| { |
| newChildren = newTree->children; |
| freeNewChildren = ANTLR3_FALSE; // We must NO free this memory |
| } |
| else |
| { |
| newChildren = antlr3VectorNew(1); |
| if (newChildren == NULL) |
| { |
| ANTLR3_FPRINTF(stderr, "replaceChildren: out of memory!!"); |
| exit(1); |
| } |
| newChildren->add(newChildren, (void *)newTree, NULL); |
| |
| freeNewChildren = ANTLR3_TRUE; // We must free this memory |
| } |
| |
| // Initialize |
| // |
| replacingHowMany = stopChildIndex - startChildIndex + 1; |
| replacingWithHowMany = newChildren->size(newChildren); |
| delta = replacingHowMany - replacingWithHowMany; |
| numNewChildren = newChildren->size(newChildren); |
| |
| // If it is the same number of nodes, then do a direct replacement |
| // |
| if (delta == 0) |
| { |
| pANTLR3_BASE_TREE child; |
| |
| // Same number of nodes |
| // |
| j = 0; |
| for (i = startChildIndex; i <= stopChildIndex; i++) |
| { |
| child = (pANTLR3_BASE_TREE) newChildren->get(newChildren, j); |
| parent->children->set(parent->children, i, child, NULL, ANTLR3_FALSE); |
| child->setParent(child, parent); |
| child->setChildIndex(child, i); |
| } |
| } |
| else if (delta > 0) |
| { |
| ANTLR3_UINT32 indexToDelete; |
| |
| // Less nodes than there were before |
| // reuse what we have then delete the rest |
| // |
| for (j = 0; j < numNewChildren; j++) |
| { |
| parent->children->set(parent->children, startChildIndex + j, newChildren->get(newChildren, j), NULL, ANTLR3_FALSE); |
| } |
| |
| // We just delete the same index position until done |
| // |
| indexToDelete = startChildIndex + numNewChildren; |
| |
| for (j = indexToDelete; j <= (ANTLR3_INT32)stopChildIndex; j++) |
| { |
| parent->children->remove(parent->children, indexToDelete); |
| } |
| |
| parent->freshenPACIndexes(parent, startChildIndex); |
| } |
| else |
| { |
| ANTLR3_UINT32 numToInsert; |
| |
| // More nodes than there were before |
| // Use what we can, then start adding |
| // |
| for (j = 0; j < replacingHowMany; j++) |
| { |
| parent->children->set(parent->children, startChildIndex + j, newChildren->get(newChildren, j), NULL, ANTLR3_FALSE); |
| } |
| |
| numToInsert = replacingWithHowMany - replacingHowMany; |
| |
| for (j = replacingHowMany; j < replacingWithHowMany; j++) |
| { |
| parent->children->add(parent->children, newChildren->get(newChildren, j), NULL); |
| } |
| |
| parent->freshenPACIndexes(parent, startChildIndex); |
| } |
| |
| if (freeNewChildren == ANTLR3_TRUE) |
| { |
| ANTLR3_FREE(newChildren->elements); |
| newChildren->elements = NULL; |
| newChildren->size = 0; |
| ANTLR3_FREE(newChildren); // Will not free the nodes |
| } |
| } |
| |
| /// Set the parent and child indexes for all children of the |
| /// supplied tree. |
| /// |
| static void |
| freshenPACIndexesAll(pANTLR3_BASE_TREE tree) |
| { |
| tree->freshenPACIndexes(tree, 0); |
| } |
| |
| /// Set the parent and child indexes for some of the children of the |
| /// supplied tree, starting with the child at the supplied index. |
| /// |
| static void |
| freshenPACIndexes (pANTLR3_BASE_TREE tree, ANTLR3_UINT32 offset) |
| { |
| ANTLR3_UINT32 count; |
| ANTLR3_UINT32 c; |
| |
| count = tree->getChildCount(tree); // How many children do we have |
| |
| // Loop from the supplied index and set the indexes and parent |
| // |
| for (c = offset; c < count; c++) |
| { |
| pANTLR3_BASE_TREE child; |
| |
| child = tree->getChild(tree, c); |
| |
| child->setChildIndex(child, c); |
| child->setParent(child, tree); |
| } |
| } |
| |