#include #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; ANTLR3_UINT32 count; 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 = (pANTLR3_BASE_TREE)child->children->get(child->children, i); // ANTLR3 lists can be sparse, unlike Array Lists // if (entry != NULL) { ANTLR3_UINT32 count = tree->children->add(tree->children, entry, (void (ANTLR3_CDECL *) (void *))child->free); entry->setChildIndex(entry, count - 1); entry->setParent(entry, tree); } } } } } 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); } count = tree->children->add(tree->children, child, (void (ANTLR3_CDECL *)(void *))child->free); child->setChildIndex(child, count - 1); child->setParent(child, tree); } } /// 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; iaddChild(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 = (pANTLR3_BASE_TREE)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 = (pANTLR3_BASE_TREE)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 = (pANTLR3_BASE_TREE)tree->getChild(tree, c); child->setChildIndex(child, c); child->setParent(child, tree); } }