// \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);
|
|
}
|
}
|
