antlr3/tree.py

Go to the documentation of this file.

##
#  @package antlr3.tree
# @brief ANTLR3 runtime package, tree module
# 
# This module contains all support classes for AST construction and tree parsers.
# 
# 

# begin[licence]
#
# [The "BSD licence"]
# Copyright (c) 2005-2008 Terence Parr
# 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.
#
# end[licence]

# lot's of docstrings are missing, don't complain for now...
# pylint: disable-msg=C0111

from antlr3.constants import UP, DOWN, EOF, INVALID_TOKEN_TYPE
from antlr3.recognizers import BaseRecognizer, RuleReturnScope
from antlr3.streams import IntStream
from antlr3.tokens import CommonToken, Token, INVALID_TOKEN
from antlr3.exceptions import MismatchedTreeNodeException, \
     MissingTokenException, UnwantedTokenException, MismatchedTokenException, \
     NoViableAltException


############################################################################
#
# tree related exceptions
#
############################################################################


##
# 
#     @brief Base class for all exceptions thrown during AST rewrite construction.
# 
#     This signifies a case where the cardinality of two or more elements
#     in a subrule are different: (ID INT)+ where |ID|!=|INT|
#     
class RewriteCardinalityException(RuntimeError):

    def __init__(self, elementDescription):
        RuntimeError.__init__(self, elementDescription)

        self.elementDescription = elementDescription


    def getMessage(self):
        return self.elementDescription


##
# @brief No elements within a (...)+ in a rewrite rule
class RewriteEarlyExitException(RewriteCardinalityException):

    def __init__(self, elementDescription=None):
        RewriteCardinalityException.__init__(self, elementDescription)


##
# 
#     @brief Ref to ID or expr but no tokens in ID stream or subtrees in expr stream
#     
class RewriteEmptyStreamException(RewriteCardinalityException):

    pass


############################################################################
#
# basic Tree and TreeAdaptor interfaces
#
############################################################################

##
# 
#     @brief Abstract baseclass for tree nodes.
#     
#     What does a tree look like?  ANTLR has a number of support classes
#     such as CommonTreeNodeStream that work on these kinds of trees.  You
#     don't have to make your trees implement this interface, but if you do,
#     you'll be able to use more support code.
# 
#     NOTE: When constructing trees, ANTLR can build any kind of tree; it can
#     even use Token objects as trees if you add a child list to your tokens.
#     
#     This is a tree node without any payload; just navigation and factory stuff.
#     
class Tree(object):


    def getChild(self, i):
        raise NotImplementedError
    

    def getChildCount(self):
        raise NotImplementedError
    

    ##
    # Tree tracks parent and child index now > 3.0
    def getParent(self):

        raise NotImplementedError
    
    ##
    # Tree tracks parent and child index now > 3.0
    def setParent(self, t):

        raise NotImplementedError
    

    ##
    # This node is what child index? 0..n-1
    def getChildIndex(self):

        raise NotImplementedError
        
    ##
    # This node is what child index? 0..n-1
    def setChildIndex(self, index):

        raise NotImplementedError
        

    ##
    # Set the parent and child index values for all children
    def freshenParentAndChildIndexes(self):
        
        raise NotImplementedError

        
    ##
    # 
    #         Add t as a child to this node.  If t is null, do nothing.  If t
    #         is nil, add all children of t to this' children.
    #         
    def addChild(self, t):

        raise NotImplementedError
    

    ##
    # Set ith child (0..n-1) to t; t must be non-null and non-nil node
    def setChild(self, i, t):

        raise NotImplementedError

            
    def deleteChild(self, i):
        raise NotImplementedError
        
 
    ##
    # 
    #         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 childindex; could be slow.
    #         
    def replaceChildren(self, startChildIndex, stopChildIndex, t):

        raise NotImplementedError


    ##
    # 
    #         Indicates the node is a nil node but may still have children, meaning
    #         the tree is a flat list.
    #         
    def isNil(self):

        raise NotImplementedError
    

    ##
    # 
    #         What is the smallest token index (indexing from 0) for this node
    #            and its children?
    #         
    def getTokenStartIndex(self):

        raise NotImplementedError


    def setTokenStartIndex(self, index):
        raise NotImplementedError


    ##
    # 
    #         What is the largest token index (indexing from 0) for this node
    #         and its children?
    #         
    def getTokenStopIndex(self):

        raise NotImplementedError


    def setTokenStopIndex(self, index):
        raise NotImplementedError


    def dupNode(self):
        raise NotImplementedError
    
    
    ##
    # Return a token type; needed for tree parsing.
    def getType(self):

        raise NotImplementedError
    

    def getText(self):
        raise NotImplementedError
    

    ##
    # 
    #         In case we don't have a token payload, what is the line for errors?
    #         
    def getLine(self):

        raise NotImplementedError
    

    def getCharPositionInLine(self):
        raise NotImplementedError


    def toStringTree(self):
        raise NotImplementedError


    def toString(self):
        raise NotImplementedError



##
# 
#     @brief Abstract baseclass for tree adaptors.
#     
#     How to create and navigate trees.  Rather than have a separate factory
#     and adaptor, I've merged them.  Makes sense to encapsulate.
# 
#     This takes the place of the tree construction code generated in the
#     generated code in 2.x and the ASTFactory.
# 
#     I do not need to know the type of a tree at all so they are all
#     generic Objects.  This may increase the amount of typecasting needed. :(
#     
class TreeAdaptor(object):
    
    # C o n s t r u c t i o n

    ##
    # 
    #         Create a tree node from Token object; for CommonTree type trees,
    #         then the token just becomes the payload.  This is the most
    #         common create call.
    # 
    #         Override if you want another kind of node to be built.
    #         
    def createWithPayload(self, payload):

        raise NotImplementedError
    

    ##
    # Duplicate a single tree node.
    # 
    #         Override if you want another kind of node to be built.
    def dupNode(self, treeNode):

        raise NotImplementedError


    ##
    # Duplicate tree recursively, using dupNode() for each node
    def dupTree(self, tree):

        raise NotImplementedError


    ##
    # 
    #         Return a nil node (an empty but non-null node) that can hold
    #         a list of element as the children.  If you want a flat tree (a list)
    #         use "t=adaptor.nil(); t.addChild(x); t.addChild(y);"
    #         
    def nil(self):

        raise NotImplementedError


    ##
    # 
    #         Return a tree node representing an error.  This node records the
    #         tokens consumed during error recovery.  The start token indicates the
    #         input symbol at which the error was detected.  The stop token indicates
    #         the last symbol consumed during recovery.
    # 
    #         You must specify the input stream so that the erroneous text can
    #         be packaged up in the error node.  The exception could be useful
    #         to some applications; default implementation stores ptr to it in
    #         the CommonErrorNode.
    # 
    #         This only makes sense during token parsing, not tree parsing.
    #         Tree parsing should happen only when parsing and tree construction
    #         succeed.
    #         
    def errorNode(self, input, start, stop, exc):

        raise NotImplementedError


    ##
    # Is tree considered a nil node used to make lists of child nodes?
    def isNil(self, tree):

        raise NotImplementedError


    ##
    # 
    #         Add a child to the tree t.  If child is a flat tree (a list), make all
    #         in list children of t.  Warning: if t has no children, but child does
    #         and child isNil then you can decide it is ok to move children to t via
    #         t.children = child.children; i.e., without copying the array.  Just
    #         make sure that this is consistent with have the user will build
    #         ASTs. Do nothing if t or child is null.
    #         
    def addChild(self, t, child):

        raise NotImplementedError


    ##
    # 
    #         If oldRoot is a nil root, just copy or move the children to newRoot.
    #         If not a nil root, make oldRoot a child of newRoot.
    #         
    #            old=^(nil a b c), new=r yields ^(r a b c)
    #            old=^(a b c), new=r yields ^(r ^(a b c))
    # 
    #         If newRoot is a nil-rooted single child tree, use the single
    #         child as the new root node.
    # 
    #            old=^(nil a b c), new=^(nil r) yields ^(r a b c)
    #            old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
    # 
    #         If oldRoot was null, it's ok, just return newRoot (even if isNil).
    # 
    #            old=null, new=r yields r
    #            old=null, new=^(nil r) yields ^(nil r)
    # 
    #         Return newRoot.  Throw an exception if newRoot is not a
    #         simple node or nil root with a single child node--it must be a root
    #         node.  If newRoot is ^(nil x) return x as newRoot.
    # 
    #         Be advised that it's ok for newRoot to point at oldRoot's
    #         children; i.e., you don't have to copy the list.  We are
    #         constructing these nodes so we should have this control for
    #         efficiency.
    #         
    def becomeRoot(self, newRoot, oldRoot):

        raise NotImplementedError


    ##
    # 
    #         Given the root of the subtree created for this rule, post process
    #         it to do any simplifications or whatever you want.  A required
    #         behavior is to convert ^(nil singleSubtree) to singleSubtree
    #         as the setting of start/stop indexes relies on a single non-nil root
    #         for non-flat trees.
    # 
    #         Flat trees such as for lists like "idlist : ID+ ;" are left alone
    #         unless there is only one ID.  For a list, the start/stop indexes
    #         are set in the nil node.
    # 
    #         This method is executed after all rule tree construction and right
    #         before setTokenBoundaries().
    #         
    def rulePostProcessing(self, root):

        raise NotImplementedError


    ##
    # For identifying trees.
    # 
    #         How to identify nodes so we can say "add node to a prior node"?
    #         Even becomeRoot is an issue.  Use System.identityHashCode(node)
    #         usually.
    #         
    def getUniqueID(self, node):

        raise NotImplementedError


    # R e w r i t e  R u l e s

    ##
    # 
    #         Create a new node derived from a token, with a new token type and
    #         (optionally) new text.
    # 
    #         This is invoked from an imaginary node ref on right side of a
    #         rewrite rule as IMAG[$tokenLabel] or IMAG[$tokenLabel "IMAG"].
    # 
    #         This should invoke createToken(Token).
    #         
    def createFromToken(self, tokenType, fromToken, text=None):

        raise NotImplementedError


    ##
    # Create a new node derived from a token, with a new token type.
    # 
    #         This is invoked from an imaginary node ref on right side of a
    #         rewrite rule as IMAG["IMAG"].
    # 
    #         This should invoke createToken(int,String).
    #         
    def createFromType(self, tokenType, text):

        raise NotImplementedError


    # C o n t e n t

    ##
    # For tree parsing, I need to know the token type of a node
    def getType(self, t):

        raise NotImplementedError


    ##
    # Node constructors can set the type of a node
    def setType(self, t, type):

        raise NotImplementedError


    def getText(self, t):
        raise NotImplementedError

    ##
    # Node constructors can set the text of a node
    def setText(self, t, text):

        raise NotImplementedError


    ##
    # Return the token object from which this node was created.
    # 
    #         Currently used only for printing an error message.
    #         The error display routine in BaseRecognizer needs to
    #         display where the input the error occurred. If your
    #         tree of limitation does not store information that can
    #         lead you to the token, you can create a token filled with
    #         the appropriate information and pass that back.  See
    #         BaseRecognizer.getErrorMessage().
    #         
    def getToken(self, t):

        raise NotImplementedError


    ##
    # 
    #         Where are the bounds in the input token stream for this node and
    #         all children?  Each rule that creates AST nodes will call this
    #         method right before returning.  Flat trees (i.e., lists) will
    #         still usually have a nil root node just to hold the children list.
    #         That node would contain the start/stop indexes then.
    #         
    def setTokenBoundaries(self, t, startToken, stopToken):

        raise NotImplementedError


    ##
    # 
    #         Get the token start index for this subtree; return -1 if no such index
    #         
    def getTokenStartIndex(self, t):

        raise NotImplementedError

        
    ##
    # 
    #         Get the token stop index for this subtree; return -1 if no such index
    #         
    def getTokenStopIndex(self, t):

        raise NotImplementedError
        

    # N a v i g a t i o n  /  T r e e  P a r s i n g

    ##
    # Get a child 0..n-1 node
    def getChild(self, t, i):

        raise NotImplementedError


    ##
    # Set ith child (0..n-1) to t; t must be non-null and non-nil node
    def setChild(self, t, i, child):

        raise NotImplementedError


    ##
    # Remove ith child and shift children down from right.
    def deleteChild(self, t, i):
        
        raise NotImplementedError


    ##
    # How many children?  If 0, then this is a leaf node
    def getChildCount(self, t):

        raise NotImplementedError


    ##
    # 
    #         Who is the parent node of this node; if null, implies node is root.
    #         If your node type doesn't handle this, it's ok but the tree rewrites
    #         in tree parsers need this functionality.
    #         
    def getParent(self, t):
        
        raise NotImplementedError


    ##
    # 
    #         Who is the parent node of this node; if null, implies node is root.
    #         If your node type doesn't handle this, it's ok but the tree rewrites
    #         in tree parsers need this functionality.
    #         
    def setParent(self, t, parent):

        raise NotImplementedError


    ##
    # 
    #         What index is this node in the child list? Range: 0..n-1
    #         If your node type doesn't handle this, it's ok but the tree rewrites
    #         in tree parsers need this functionality.
    #         
    def getChildIndex(self, t):

        raise NotImplementedError

        
    ##
    # 
    #         What index is this node in the child list? Range: 0..n-1
    #         If your node type doesn't handle this, it's ok but the tree rewrites
    #         in tree parsers need this functionality.
    #         
    def setChildIndex(self, t, index):

        raise NotImplementedError


    ##
    # 
    #         Replace from start to stop child index of parent with t, which might
    #         be a list.  Number of children may be different
    #         after this call.
    # 
    #         If parent is null, don't do anything; must be at root of overall tree.
    #         Can't replace whatever points to the parent externally.  Do nothing.
    #         
    def replaceChildren(self, parent, startChildIndex, stopChildIndex, t):

        raise NotImplementedError


    # Misc

    ##
    # 
    #         Deprecated, use createWithPayload, createFromToken or createFromType.
    # 
    #         This method only exists to mimic the Java interface of TreeAdaptor.
    #         
    #         
    def create(self, *args):

        if len(args) == 1 and isinstance(args[0], Token):
            # Object create(Token payload);
##             warnings.warn(
##                 "Using create() is deprecated, use createWithPayload()",
##                 DeprecationWarning,
##                 stacklevel=2
##                 )
            return self.createWithPayload(args[0])

        if (len(args) == 2
            and isinstance(args[0], (int, long))
            and isinstance(args[1], Token)
            ):
            # Object create(int tokenType, Token fromToken);
##             warnings.warn(
##                 "Using create() is deprecated, use createFromToken()",
##                 DeprecationWarning,
##                 stacklevel=2
##                 )
            return self.createFromToken(args[0], args[1])

        if (len(args) == 3
            and isinstance(args[0], (int, long))
            and isinstance(args[1], Token)
            and isinstance(args[2], basestring)
            ):
            # Object create(int tokenType, Token fromToken, String text);
##             warnings.warn(
##                 "Using create() is deprecated, use createFromToken()",
##                 DeprecationWarning,
##                 stacklevel=2
##                 )
            return self.createFromToken(args[0], args[1], args[2])

        if (len(args) == 2
            and isinstance(args[0], (int, long))
            and isinstance(args[1], basestring)
            ):
            # Object create(int tokenType, String text);
##             warnings.warn(
##                 "Using create() is deprecated, use createFromType()",
##                 DeprecationWarning,
##                 stacklevel=2
##                 )
            return self.createFromType(args[0], args[1])

        raise TypeError(
            "No create method with this signature found: %s"
            % (', '.join(type(v).__name__ for v in args))
            )
    

############################################################################
#
# base implementation of Tree and TreeAdaptor
#
# Tree
# \- BaseTree
#
# TreeAdaptor
# \- BaseTreeAdaptor
#
############################################################################


##
# 
#     @brief A generic tree implementation with no payload.
# 
#     You must subclass to
#     actually have any user data.  ANTLR v3 uses a list of children approach
#     instead of the child-sibling approach in v2.  A flat tree (a list) is
#     an empty node whose children represent the list.  An empty, but
#     non-null node is called "nil".
#     
class BaseTree(Tree):

    # BaseTree is abstract, no need to complain about not implemented abstract
    # methods
    # pylint: disable-msg=W0223
    
    ##
    # 
    #         Create a new node from an existing node does nothing for BaseTree
    #         as there are no fields other than the children list, which cannot
    #         be copied as the children are not considered part of this node. 
    #         
    def __init__(self, node=None):
        
        Tree.__init__(self)
        self.children = []
        self.parent = None
        self.childIndex = 0
        

    def getChild(self, i):
        try:
            return self.children[i]
        except IndexError:
            return None


    ##
    # @brief Get the children internal List
    # 
    #         Note that if you directly mess with
    #         the list, do so at your own risk.
    #         
    def getChildren(self):
        
        # FIXME: mark as deprecated
        return self.children


    def getFirstChildWithType(self, treeType):
        for child in self.children:
            if child.getType() == treeType:
                return child

        return None


    def getChildCount(self):
        return len(self.children)


    ##
    # Add t as child of this node.
    # 
    #         Warning: if t has no children, but child does
    #         and child isNil then this routine moves children to t via
    #         t.children = child.children; i.e., without copying the array.
    #         
    def addChild(self, childTree):

        # this implementation is much simpler and probably less efficient
        # than the mumbo-jumbo that Ter did for the Java runtime.
        
        if childTree is None:
            return

        if childTree.isNil():
            # t is an empty node possibly with children

            if self.children is childTree.children:
                raise ValueError("attempt to add child list to itself")

            # fix parent pointer and childIndex for new children
            for idx, child in enumerate(childTree.children):
                child.parent = self
                child.childIndex = len(self.children) + idx
                
            self.children += childTree.children

        else:
            # child is not nil (don't care about children)
            self.children.append(childTree)
            childTree.parent = self
            childTree.childIndex = len(self.children) - 1


    ##
    # Add all elements of kids list as children of this node
    def addChildren(self, children):

        self.children += children


    def setChild(self, i, t):
        if t is None:
            return

        if t.isNil():
            raise ValueError("Can't set single child to a list")
        
        self.children[i] = t
        t.parent = self
        t.childIndex = i
        

    def deleteChild(self, i):
        killed = self.children[i]
        
        del self.children[i]
        
        # walk rest and decrement their child indexes
        for idx, child in enumerate(self.children[i:]):
            child.childIndex = i + idx
            
        return killed

    
    ##
    # 
    #         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 childindex; could be slow.
    #         
    def replaceChildren(self, startChildIndex, stopChildIndex, newTree):

        if (startChildIndex >= len(self.children)
            or stopChildIndex >= len(self.children)
            ):
            raise IndexError("indexes invalid")

        replacingHowMany = stopChildIndex - startChildIndex + 1

        # normalize to a list of children to add: newChildren
        if newTree.isNil():
            newChildren = newTree.children

        else:
            newChildren = [newTree]

        replacingWithHowMany = len(newChildren)
        delta = replacingHowMany - replacingWithHowMany
        
        
        if delta == 0:
            # if same number of nodes, do direct replace
            for idx, child in enumerate(newChildren):
                self.children[idx + startChildIndex] = child
                child.parent = self
                child.childIndex = idx + startChildIndex

        else:
            # length of children changes...

            # ...delete replaced segment...
            del self.children[startChildIndex:stopChildIndex+1]

            # ...insert new segment...
            self.children[startChildIndex:startChildIndex] = newChildren

            # ...and fix indeces
            self.freshenParentAndChildIndexes(startChildIndex)
            

    def isNil(self):
        return False


    def freshenParentAndChildIndexes(self, offset=0):
        for idx, child in enumerate(self.children[offset:]):
            child.childIndex = idx + offset
            child.parent = self


    def sanityCheckParentAndChildIndexes(self, parent=None, i=-1):
        if parent != self.parent:
            raise ValueError(
                "parents don't match; expected %r found %r"
                % (parent, self.parent)
                )
        
        if i != self.childIndex:
            raise ValueError(
                "child indexes don't match; expected %d found %d"
                % (i, self.childIndex)
                )

        for idx, child in enumerate(self.children):
            child.sanityCheckParentAndChildIndexes(self, idx)


    ##
    # BaseTree doesn't track child indexes.
    def getChildIndex(self):
        
        return 0


    ##
    # BaseTree doesn't track child indexes.
    def setChildIndex(self, index):

        pass
    

    ##
    # BaseTree doesn't track parent pointers.
    def getParent(self):

        return None

    ##
    # BaseTree doesn't track parent pointers.
    def setParent(self, t):

        pass


    ##
    # Print out a whole tree not just a node
    def toStringTree(self):

        if len(self.children) == 0:
            return self.toString()

        buf = []
        if not self.isNil():
            buf.append('(')
            buf.append(self.toString())
            buf.append(' ')

        for i, child in enumerate(self.children):
            if i > 0:
                buf.append(' ')
            buf.append(child.toStringTree())

        if not self.isNil():
            buf.append(')')

        return ''.join(buf)


    def getLine(self):
        return 0


    def getCharPositionInLine(self):
        return 0


    ##
    # Override to say how a node (not a tree) should look as text
    def toString(self):

        raise NotImplementedError



##
# 
#     @brief A TreeAdaptor that works with any Tree implementation.
#     
class BaseTreeAdaptor(TreeAdaptor):
    
    # BaseTreeAdaptor is abstract, no need to complain about not implemented
    # abstract methods
    # pylint: disable-msg=W0223
    
    def nil(self):
        return self.createWithPayload(None)


    ##
    # 
    #         create tree node that holds the start and stop tokens associated
    #         with an error.
    # 
    #         If you specify your own kind of tree nodes, you will likely have to
    #         override this method. CommonTree returns Token.INVALID_TOKEN_TYPE
    #         if no token payload but you might have to set token type for diff
    #         node type.
    #         
    def errorNode(self, input, start, stop, exc):
        
        return CommonErrorNode(input, start, stop, exc)
    

    def isNil(self, tree):
        return tree.isNil()


    ##
    # 
    #         This is generic in the sense that it will work with any kind of
    #         tree (not just Tree interface).  It invokes the adaptor routines
    #         not the tree node routines to do the construction.
    #         
    def dupTree(self, t, parent=None):

        if t is None:
            return None

        newTree = self.dupNode(t)
        
        # ensure new subtree root has parent/child index set

        # same index in new tree
        self.setChildIndex(newTree, self.getChildIndex(t))
        
        self.setParent(newTree, parent)

        for i in range(self.getChildCount(t)):
            child = self.getChild(t, i)
            newSubTree = self.dupTree(child, t)
            self.addChild(newTree, newSubTree)

        return newTree


    ##
    # 
    #         Add a child to the tree t.  If child is a flat tree (a list), make all
    #         in list children of t.  Warning: if t has no children, but child does
    #         and child isNil then you can decide it is ok to move children to t via
    #         t.children = child.children; i.e., without copying the array.  Just
    #         make sure that this is consistent with have the user will build
    #         ASTs.
    #         
    def addChild(self, tree, child):

        #if isinstance(child, Token):
        #    child = self.createWithPayload(child)
        
        if tree is not None and child is not None:
            tree.addChild(child)


    ##
    # 
    #         If oldRoot is a nil root, just copy or move the children to newRoot.
    #         If not a nil root, make oldRoot a child of newRoot.
    # 
    #           old=^(nil a b c), new=r yields ^(r a b c)
    #           old=^(a b c), new=r yields ^(r ^(a b c))
    # 
    #         If newRoot is a nil-rooted single child tree, use the single
    #         child as the new root node.
    # 
    #           old=^(nil a b c), new=^(nil r) yields ^(r a b c)
    #           old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
    # 
    #         If oldRoot was null, it's ok, just return newRoot (even if isNil).
    # 
    #           old=null, new=r yields r
    #           old=null, new=^(nil r) yields ^(nil r)
    # 
    #         Return newRoot.  Throw an exception if newRoot is not a
    #         simple node or nil root with a single child node--it must be a root
    #         node.  If newRoot is ^(nil x) return x as newRoot.
    # 
    #         Be advised that it's ok for newRoot to point at oldRoot's
    #         children; i.e., you don't have to copy the list.  We are
    #         constructing these nodes so we should have this control for
    #         efficiency.
    #         
    def becomeRoot(self, newRoot, oldRoot):

        if isinstance(newRoot, Token):
            newRoot = self.create(newRoot)

        if oldRoot is None:
            return newRoot
        
        if not isinstance(newRoot, CommonTree):
            newRoot = self.createWithPayload(newRoot)

        # handle ^(nil real-node)
        if newRoot.isNil():
            nc = newRoot.getChildCount()
            if nc == 1:
                newRoot = newRoot.getChild(0)
                
            elif nc > 1:
                # TODO: make tree run time exceptions hierarchy
                raise RuntimeError("more than one node as root")

        # add oldRoot to newRoot; addChild takes care of case where oldRoot
        # is a flat list (i.e., nil-rooted tree).  All children of oldRoot
        # are added to newRoot.
        newRoot.addChild(oldRoot)
        return newRoot


    ##
    # Transform ^(nil x) to x and nil to null
    def rulePostProcessing(self, root):
        
        if root is not None and root.isNil():
            if root.getChildCount() == 0:
                root = None

            elif root.getChildCount() == 1:
                root = root.getChild(0)
                # whoever invokes rule will set parent and child index
                root.setParent(None)
                root.setChildIndex(-1)

        return root


    def createFromToken(self, tokenType, fromToken, text=None):
        assert isinstance(tokenType, (int, long)), type(tokenType).__name__
        assert isinstance(fromToken, Token), type(fromToken).__name__
        assert text is None or isinstance(text, basestring), type(text).__name__

        fromToken = self.createToken(fromToken)
        fromToken.type = tokenType
        if text is not None:
            fromToken.text = text
        t = self.createWithPayload(fromToken)
        return t


    def createFromType(self, tokenType, text):
        assert isinstance(tokenType, (int, long)), type(tokenType).__name__
        assert isinstance(text, basestring), type(text).__name__
                          
        fromToken = self.createToken(tokenType=tokenType, text=text)
        t = self.createWithPayload(fromToken)
        return t


    def getType(self, t):
        return t.getType()


    def setType(self, t, type):
        raise RuntimeError("don't know enough about Tree node")


    def getText(self, t):
        return t.getText()


    def setText(self, t, text):
        raise RuntimeError("don't know enough about Tree node")


    def getChild(self, t, i):
        return t.getChild(i)


    def setChild(self, t, i, child):
        t.setChild(i, child)


    def deleteChild(self, t, i):
        return t.deleteChild(i)


    def getChildCount(self, t):
        return t.getChildCount()


    def getUniqueID(self, node):
        return hash(node)


    ##
    # 
    #         Tell me how to create a token for use with imaginary token nodes.
    #         For example, there is probably no input symbol associated with imaginary
    #         token DECL, but you need to create it as a payload or whatever for
    #         the DECL node as in ^(DECL type ID).
    # 
    #         If you care what the token payload objects' type is, you should
    #         override this method and any other createToken variant.
    #         
    def createToken(self, fromToken=None, tokenType=None, text=None):

        raise NotImplementedError


############################################################################
#
# common tree implementation
#
# Tree
# \- BaseTree
#    \- CommonTree
#       \- CommonErrorNode
#
# TreeAdaptor
# \- BaseTreeAdaptor
#    \- CommonTreeAdaptor
#
############################################################################


##
# @brief A tree node that is wrapper for a Token object.
# 
#     After 3.0 release
#     while building tree rewrite stuff, it became clear that computing
#     parent and child index is very difficult and cumbersome.  Better to
#     spend the space in every tree node.  If you don't want these extra
#     fields, it's easy to cut them out in your own BaseTree subclass.
#     
#     
class CommonTree(BaseTree):

    def __init__(self, payload):
        BaseTree.__init__(self)
        
        # What token indexes bracket all tokens associated with this node
        # and below?
        self.startIndex = -1
        self.stopIndex = -1

        # Who is the parent node of this node; if null, implies node is root
        self.parent = None
        
        # What index is this node in the child list? Range: 0..n-1
        self.childIndex = -1

        # A single token is the payload
        if payload is None:
            self.token