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