| // \file |
| // |
| // Implementation of ANTLR3 CommonTree, which you can use as a |
| // starting point for your own tree. Though it is often easier just to tag things on |
| // to the user pointer in the tree unless you are building a different type |
| // of structure. |
| // |
| |
| // [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. |
| |
| #include <antlr3commontree.h> |
| |
| |
| static pANTLR3_COMMON_TOKEN getToken (pANTLR3_BASE_TREE tree); |
| static pANTLR3_BASE_TREE dupNode (pANTLR3_BASE_TREE tree); |
| static ANTLR3_BOOLEAN isNilNode (pANTLR3_BASE_TREE tree); |
| static ANTLR3_UINT32 getType (pANTLR3_BASE_TREE tree); |
| static pANTLR3_STRING getText (pANTLR3_BASE_TREE tree); |
| static ANTLR3_UINT32 getLine (pANTLR3_BASE_TREE tree); |
| static ANTLR3_UINT32 getCharPositionInLine (pANTLR3_BASE_TREE tree); |
| static pANTLR3_STRING toString (pANTLR3_BASE_TREE tree); |
| static pANTLR3_BASE_TREE getParent (pANTLR3_BASE_TREE tree); |
| static void setParent (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE parent); |
| static void setChildIndex (pANTLR3_BASE_TREE tree, ANTLR3_INT32 i); |
| static ANTLR3_INT32 getChildIndex (pANTLR3_BASE_TREE tree); |
| static void createChildrenList (pANTLR3_BASE_TREE tree); |
| static void reuse (pANTLR3_BASE_TREE tree); |
| |
| // Factory functions for the Arboretum |
| // |
| static ANTLR3_BOOLEAN newPool (pANTLR3_ARBORETUM factory); |
| static pANTLR3_BASE_TREE newPoolTree (pANTLR3_ARBORETUM factory); |
| static pANTLR3_BASE_TREE newFromTree (pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TREE tree); |
| static pANTLR3_BASE_TREE newFromToken (pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TOKEN token); |
| static void factoryClose (pANTLR3_ARBORETUM factory); |
| |
| ANTLR3_API pANTLR3_ARBORETUM |
| antlr3ArboretumNew(pANTLR3_STRING_FACTORY strFactory) |
| { |
| pANTLR3_ARBORETUM factory; |
| |
| // Allocate memory |
| // |
| factory = (pANTLR3_ARBORETUM) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_ARBORETUM)); |
| if (factory == NULL) |
| { |
| return NULL; |
| } |
| |
| // Install a vector factory to create, track and free() any child |
| // node lists. |
| // |
| factory->vFactory = antlr3VectorFactoryNew(0); |
| if (factory->vFactory == NULL) |
| { |
| free(factory); |
| return NULL; |
| } |
| |
| // We also keep a reclaim stack, so that any Nil nodes that are |
| // orphaned are not just left in the pool but are reused, other wise |
| // we create 6 times as many nilNodes as ordinary nodes and use loads of |
| // memory. Perhaps at some point, the analysis phase will generate better |
| // code and we won't need to do this here. |
| // |
| factory->nilStack = antlr3StackNew(0); |
| |
| // Install factory API |
| // |
| factory->newTree = newPoolTree; |
| factory->newFromTree = newFromTree; |
| factory->newFromToken = newFromToken; |
| factory->close = factoryClose; |
| |
| // Allocate the initial pool |
| // |
| factory->thisPool = -1; |
| factory->pools = NULL; |
| newPool(factory); |
| |
| // Factory space is good, we now want to initialize our cheating token |
| // which one it is initialized is the model for all tokens we manufacture |
| // |
| antlr3SetCTAPI(&factory->unTruc); |
| |
| // Set some initial variables for future copying, including a string factory |
| // that we can use later for converting trees to strings. |
| // |
| factory->unTruc.factory = factory; |
| factory->unTruc.baseTree.strFactory = strFactory; |
| |
| return factory; |
| |
| } |
| |
| static ANTLR3_BOOLEAN |
| newPool(pANTLR3_ARBORETUM factory) |
| { |
| pANTLR3_COMMON_TREE *newPools; |
| |
| // Increment factory count |
| // |
| ++factory->thisPool; |
| |
| // Ensure we have enough pointers allocated |
| // |
| newPools = (pANTLR3_COMMON_TREE *) |
| ANTLR3_REALLOC( (void *)factory->pools, // Current pools pointer (starts at NULL) |
| (ANTLR3_UINT32)((factory->thisPool + 1) * sizeof(pANTLR3_COMMON_TREE *)) // Memory for new pool pointers |
| ); |
| if (newPools == NULL) |
| { |
| // realloc failed, but we still have the old allocation |
| --factory->thisPool; |
| return ANTLR3_FALSE; |
| } |
| factory->pools = newPools; |
| |
| // Allocate a new pool for the factory |
| // |
| factory->pools[factory->thisPool] = |
| (pANTLR3_COMMON_TREE) |
| ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_COMMON_TREE) * ANTLR3_FACTORY_POOL_SIZE)); |
| if (factory->pools[factory->thisPool] == NULL) |
| { |
| // malloc failed |
| --factory->thisPool; |
| return ANTLR3_FALSE; |
| } |
| |
| |
| // Reset the counters |
| // |
| factory->nextTree = 0; |
| |
| // Done |
| // |
| return ANTLR3_TRUE; |
| } |
| |
| static pANTLR3_BASE_TREE |
| newPoolTree (pANTLR3_ARBORETUM factory) |
| { |
| pANTLR3_COMMON_TREE tree; |
| |
| // If we have anything on the re claim stack, reuse that sucker first |
| // |
| tree = (pANTLR3_COMMON_TREE)factory->nilStack->peek(factory->nilStack); |
| |
| if (tree != NULL) |
| { |
| // Cool we got something we could reuse, it will have been cleaned up by |
| // whatever put it back on the stack (for instance if it had a child vector, |
| // that will have been cleared to hold zero entries and that vector will get reused too. |
| // It is the basetree pointer that is placed on the stack of course |
| // |
| factory->nilStack->pop(factory->nilStack); |
| return (pANTLR3_BASE_TREE)tree; |
| |
| } |
| // See if we need a new tree pool before allocating a new tree |
| // |
| if (factory->nextTree >= ANTLR3_FACTORY_POOL_SIZE) |
| { |
| // We ran out of tokens in the current pool, so we need a new pool |
| // |
| if (!newPool(factory)) |
| { |
| // new pool creation failed |
| return NULL; |
| } |
| } |
| |
| // Assuming everything went well - we are trying for performance here so doing minimal |
| // error checking - then we can work out what the pointer is to the next commontree. |
| // |
| tree = factory->pools[factory->thisPool] + factory->nextTree; |
| factory->nextTree++; |
| |
| // We have our token pointer now, so we can initialize it to the predefined model. |
| // |
| antlr3SetCTAPI(tree); |
| |
| // Set some initial variables for future copying, including a string factory |
| // that we can use later for converting trees to strings. |
| // |
| tree->factory = factory; |
| tree->baseTree.strFactory = factory->unTruc.baseTree.strFactory; |
| |
| // The super points to the common tree so we must override the one used by |
| // by the pre-built tree as otherwise we will always poitn to the same initial |
| // common tree and we might spend 3 hours trying to debug why - this would never |
| // happen to me of course! :-( |
| // |
| tree->baseTree.super = tree; |
| |
| |
| // And we are done |
| // |
| return &(tree->baseTree); |
| } |
| |
| |
| static pANTLR3_BASE_TREE |
| newFromTree(pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TREE tree) |
| { |
| pANTLR3_BASE_TREE newTree; |
| |
| newTree = factory->newTree(factory); |
| |
| if (newTree == NULL) |
| { |
| return NULL; |
| } |
| |
| // Pick up the payload we had in the supplied tree |
| // |
| ((pANTLR3_COMMON_TREE)(newTree->super))->token = tree->token; |
| newTree->u = tree->baseTree.u; // Copy any user pointer |
| |
| return newTree; |
| } |
| |
| static pANTLR3_BASE_TREE |
| newFromToken(pANTLR3_ARBORETUM factory, pANTLR3_COMMON_TOKEN token) |
| { |
| pANTLR3_BASE_TREE newTree; |
| |
| newTree = factory->newTree(factory); |
| |
| if (newTree == NULL) |
| { |
| return NULL; |
| } |
| |
| // Pick up the payload we had in the supplied tree |
| // |
| ((pANTLR3_COMMON_TREE)(newTree->super))->token = token; |
| |
| return newTree; |
| } |
| |
| static void |
| factoryClose (pANTLR3_ARBORETUM factory) |
| { |
| ANTLR3_INT32 poolCount; |
| |
| // First close the vector factory that supplied all the child pointer |
| // vectors. |
| // |
| factory->vFactory->close(factory->vFactory); |
| |
| if (factory->nilStack != NULL) |
| { |
| factory->nilStack->free(factory->nilStack); |
| } |
| |
| // We now JUST free the pools because the C runtime CommonToken based tree |
| // cannot contain anything that was not made by this factory. |
| // |
| for (poolCount = 0; poolCount <= factory->thisPool; poolCount++) |
| { |
| // We can now free this pool allocation |
| // |
| ANTLR3_FREE(factory->pools[poolCount]); |
| factory->pools[poolCount] = NULL; |
| } |
| |
| // All the pools are deallocated we can free the pointers to the pools |
| // now. |
| // |
| ANTLR3_FREE(factory->pools); |
| |
| // Finally, we can free the space for the factory itself |
| // |
| ANTLR3_FREE(factory); |
| } |
| |
| |
| ANTLR3_API void |
| antlr3SetCTAPI(pANTLR3_COMMON_TREE tree) |
| { |
| // Init base tree |
| // |
| antlr3BaseTreeNew(&(tree->baseTree)); |
| |
| // We need a pointer to ourselves for |
| // the payload and few functions that we |
| // provide. |
| // |
| tree->baseTree.super = tree; |
| |
| // Common tree overrides |
| |
| tree->baseTree.isNilNode = isNilNode; |
| tree->baseTree.toString = toString; |
| tree->baseTree.dupNode = (void *(*)(pANTLR3_BASE_TREE))(dupNode); |
| tree->baseTree.getLine = getLine; |
| tree->baseTree.getCharPositionInLine = getCharPositionInLine; |
| tree->baseTree.toString = toString; |
| tree->baseTree.getType = getType; |
| tree->baseTree.getText = getText; |
| tree->baseTree.getToken = getToken; |
| tree->baseTree.getParent = getParent; |
| tree->baseTree.setParent = setParent; |
| tree->baseTree.setChildIndex = setChildIndex; |
| tree->baseTree.getChildIndex = getChildIndex; |
| tree->baseTree.createChildrenList = createChildrenList; |
| tree->baseTree.reuse = reuse; |
| tree->baseTree.free = NULL; // Factory trees have no free function |
| tree->baseTree.u = NULL; // Initialize user pointer |
| |
| tree->baseTree.children = NULL; |
| |
| tree->token = NULL; // No token as yet |
| tree->startIndex = 0; |
| tree->stopIndex = 0; |
| tree->parent = NULL; // No parent yet |
| tree->childIndex = -1; |
| |
| return; |
| } |
| |
| // -------------------------------------- |
| // Non factory node constructors. |
| // |
| |
| ANTLR3_API pANTLR3_COMMON_TREE |
| antlr3CommonTreeNew() |
| { |
| pANTLR3_COMMON_TREE tree; |
| tree = (pANTLR3_COMMON_TREE)ANTLR3_CALLOC(1, sizeof(ANTLR3_COMMON_TREE)); |
| |
| if (tree == NULL) |
| { |
| return NULL; |
| } |
| |
| antlr3SetCTAPI(tree); |
| |
| return tree; |
| } |
| |
| ANTLR3_API pANTLR3_COMMON_TREE |
| antlr3CommonTreeNewFromToken(pANTLR3_COMMON_TOKEN token) |
| { |
| pANTLR3_COMMON_TREE newTree; |
| |
| newTree = antlr3CommonTreeNew(); |
| |
| if (newTree == NULL) |
| { |
| return NULL; |
| } |
| |
| //Pick up the payload we had in the supplied tree |
| // |
| newTree->token = token; |
| return newTree; |
| } |
| |
| /// Create a new vector for holding child nodes using the inbuilt |
| /// vector factory. |
| /// |
| static void |
| createChildrenList (pANTLR3_BASE_TREE tree) |
| { |
| tree->children = ((pANTLR3_COMMON_TREE)(tree->super))->factory->vFactory->newVector(((pANTLR3_COMMON_TREE)(tree->super))->factory->vFactory); |
| } |
| |
| |
| static pANTLR3_COMMON_TOKEN |
| getToken (pANTLR3_BASE_TREE tree) |
| { |
| // The token is the payload of the common tree or other implementor |
| // so it is stored within ourselves, which is the super pointer.Note |
| // that whatever the actual token is, it is passed around by its pointer |
| // to the common token implementation, which it may of course surround |
| // with its own super structure. |
| // |
| return ((pANTLR3_COMMON_TREE)(tree->super))->token; |
| } |
| |
| static pANTLR3_BASE_TREE |
| dupNode (pANTLR3_BASE_TREE tree) |
| { |
| // The node we are duplicating is in fact the common tree (that's why we are here) |
| // so we use the super pointer to duplicate. |
| // |
| pANTLR3_COMMON_TREE theOld; |
| |
| theOld = (pANTLR3_COMMON_TREE)(tree->super); |
| |
| // The pointer we return is the base implementation of course |
| // |
| return theOld->factory->newFromTree(theOld->factory, theOld); |
| } |
| |
| static ANTLR3_BOOLEAN |
| isNilNode (pANTLR3_BASE_TREE tree) |
| { |
| // This is a Nil tree if it has no payload (Token in our case) |
| // |
| if (((pANTLR3_COMMON_TREE)(tree->super))->token == NULL) |
| { |
| return ANTLR3_TRUE; |
| } |
| else |
| { |
| return ANTLR3_FALSE; |
| } |
| } |
| |
| static ANTLR3_UINT32 |
| getType (pANTLR3_BASE_TREE tree) |
| { |
| pANTLR3_COMMON_TREE theTree; |
| |
| theTree = (pANTLR3_COMMON_TREE)(tree->super); |
| |
| if (theTree->token == NULL) |
| { |
| return 0; |
| } |
| else |
| { |
| return theTree->token->getType(theTree->token); |
| } |
| } |
| |
| static pANTLR3_STRING |
| getText (pANTLR3_BASE_TREE tree) |
| { |
| return tree->toString(tree); |
| } |
| |
| static ANTLR3_UINT32 getLine (pANTLR3_BASE_TREE tree) |
| { |
| pANTLR3_COMMON_TREE cTree; |
| pANTLR3_COMMON_TOKEN token; |
| |
| cTree = (pANTLR3_COMMON_TREE)(tree->super); |
| |
| token = cTree->token; |
| |
| if (token == NULL || token->getLine(token) == 0) |
| { |
| if (tree->getChildCount(tree) > 0) |
| { |
| pANTLR3_BASE_TREE child; |
| |
| child = (pANTLR3_BASE_TREE)tree->getChild(tree, 0); |
| return child->getLine(child); |
| } |
| return 0; |
| } |
| return token->getLine(token); |
| } |
| |
| static ANTLR3_UINT32 getCharPositionInLine (pANTLR3_BASE_TREE tree) |
| { |
| pANTLR3_COMMON_TOKEN token; |
| |
| token = ((pANTLR3_COMMON_TREE)(tree->super))->token; |
| |
| if (token == NULL || token->getCharPositionInLine(token) == -1) |
| { |
| if (tree->getChildCount(tree) > 0) |
| { |
| pANTLR3_BASE_TREE child; |
| |
| child = (pANTLR3_BASE_TREE)tree->getChild(tree, 0); |
| |
| return child->getCharPositionInLine(child); |
| } |
| return 0; |
| } |
| return token->getCharPositionInLine(token); |
| } |
| |
| static pANTLR3_STRING toString (pANTLR3_BASE_TREE tree) |
| { |
| if (tree->isNilNode(tree) == ANTLR3_TRUE) |
| { |
| pANTLR3_STRING nilNode; |
| |
| nilNode = tree->strFactory->newPtr(tree->strFactory, (pANTLR3_UINT8)"nil", 3); |
| |
| return nilNode; |
| } |
| |
| return ((pANTLR3_COMMON_TREE)(tree->super))->token->getText(((pANTLR3_COMMON_TREE)(tree->super))->token); |
| } |
| |
| static pANTLR3_BASE_TREE |
| getParent (pANTLR3_BASE_TREE tree) |
| { |
| if (((pANTLR3_COMMON_TREE)(tree->super))->parent == NULL) |
| return NULL; |
| return & (((pANTLR3_COMMON_TREE)(tree->super))->parent->baseTree); |
| } |
| |
| static void |
| setParent (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE parent) |
| { |
| ((pANTLR3_COMMON_TREE)(tree->super))->parent = parent == NULL ? NULL : ((pANTLR3_COMMON_TREE)(parent->super)); |
| } |
| |
| static void |
| setChildIndex (pANTLR3_BASE_TREE tree, ANTLR3_INT32 i) |
| { |
| ((pANTLR3_COMMON_TREE)(tree->super))->childIndex = i; |
| } |
| static ANTLR3_INT32 |
| getChildIndex (pANTLR3_BASE_TREE tree ) |
| { |
| return ((pANTLR3_COMMON_TREE)(tree->super))->childIndex; |
| } |
| |
| /** Clean up any child vector that the tree might have, so it can be reused, |
| * then add it into the reuse stack. |
| */ |
| static void |
| reuse (pANTLR3_BASE_TREE tree) |
| { |
| pANTLR3_COMMON_TREE cTree; |
| |
| cTree = (pANTLR3_COMMON_TREE)(tree->super); |
| |
| if (cTree->factory != NULL) |
| { |
| |
| if (cTree->baseTree.children != NULL) |
| { |
| |
| cTree->baseTree.children->clear(cTree->baseTree.children); |
| } |
| cTree->factory->nilStack->push(cTree->factory->nilStack, tree, NULL); |
| |
| } |
| } |