diff options
Diffstat (limited to 'antlr/libantlr3c-3.4/src/antlr3basetree.c')
| -rw-r--r-- | antlr/libantlr3c-3.4/src/antlr3basetree.c | 489 |
1 files changed, 489 insertions, 0 deletions
diff --git a/antlr/libantlr3c-3.4/src/antlr3basetree.c b/antlr/libantlr3c-3.4/src/antlr3basetree.c new file mode 100644 index 0000000..bbc81e7 --- /dev/null +++ b/antlr/libantlr3c-3.4/src/antlr3basetree.c @@ -0,0 +1,489 @@ +#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); + } +} + |