tree.py

antlr最新版本V3源代码

            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
#
############################################################################


class BaseTree(Tree):
    """
    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".
    """

    # BaseTree is abstract, no need to complain about not implemented abstract
    # methods
    # pylint: disable-msg=W0223
    
    def __init__(self, node=None):
        """
        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. 
        """
        
        Tree.__init__(self)
        self.children = []


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


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

        return None


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


    def addChild(self, childTree):
        """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.
        """

        # 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():
            self.children += childTree.children

        else:
            self.children.append(childTree)



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

        self.children += children


    def setChild(self, i, t):
        self.children[i] = t


    def deleteChild(self, i):
        del self.children[i]


    def isNil(self):
        return False


    def dupTree(self):
        """
        Recursively walk this tree, dup'ing nodes until you have copy of
        this tree.  This method should work for all subclasses as long
        as they override dupNode().
        """

        newTree = self.dupNode()
        for child in self.children:
            newTree.addChild(child.dupTree())

        return newTree


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

        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


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

        raise NotImplementedError



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)


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


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


    def addChild(self, tree, child):
        """
        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.
        """

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


    def becomeRoot(self, newRoot, oldRoot):
        """
        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.
        """

        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():
            if newRoot.getChildCount() > 1:
                # TODO: make tree run time exceptions hierarchy
                raise RuntimeError("more than one node as root (TODO: make exception hierarchy)")

            newRoot = newRoot.getChild(0)

        # 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


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

        return root


    def createFromToken(self, tokenType, fromToken, text=None):
        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):
        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 getChildCount(self, t):
        return t.getChildCount()


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


    def createToken(self, fromToken=None, tokenType=None, text=None):
        """
        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.
        """

        raise NotImplementedError


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


class CommonTree(BaseTree):
    """A tree node that is wrapper for a Token object."""

    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

        # A single token is the payload
        if isinstance(payload, CommonTree):
            self.token = payload.token
        elif payload is None or isinstance(payload, Token):
            self.token = payload
        else:
            raise TypeError(type(payload).__name__)



    def getToken(self):
        return self.token


    def dupNode(self):
        return CommonTree(self)


    def isNil(self):
        return self.token is None


    def getType(self):
        if self.token is None:
            return 0

        return self.token.getType()


    def getText(self):
        return self.toString()


    def getLine(self):
        if self.token is None or self.token.getLine() == 0:
            if len(self.getChildCount()) > 0:
                return self.getChild(0).getLine()
            else:
                return 0

        return self.token.getLine()


    def getCharPositionInLine(self):
        if self.token is None or self.token.getCharPositionInLine() == -1:
            if self.getChildCount():
                return self.getChild(0).getCharPositionInLine()
            else:
                return 0

        else:
            return self.token.getCharPositionInLine()


    def getTokenStartIndex(self):
        if self.startIndex == -1 and self.token is not None:
            return self.token.getTokenIndex()
        
        return self.startIndex


    def setTokenStartIndex(self, index):
        self.startIndex = index


    def getTokenStopIndex(self):
        if self.stopIndex == -1 and self.token is not None:
            return self.token.getTokenIndex()
        
        return self.stopIndex


    def setTokenStopIndex(self, index):
        self.stopIndex = index


    def toString(self):
        if self.isNil():
            return "nil"

        else:
            return self.token.text

    __str__ = toString   



    def toStringTree(self):
        if not self.children:
            return str(self)

        ret = ''
        if not self.isNil():
            ret += '(%s ' % (str(self))
        
        ret += ' '.join([child.toStringTree() for child in self.children])

        if not self.isNil():
            ret += ')'

        return ret


INVALID_NODE = CommonTree(INVALID_TOKEN)


class CommonTreeAdaptor(BaseTreeAdaptor):
    """
    A TreeAdaptor that works with any Tree implementation.  It provides
    really just factory methods; all the work is done by BaseTreeAdaptor.
    If you would like to have different tokens created than ClassicToken
    objects, you need to override this and then set the parser tree adaptor to
    use your subclass.

    To get your parser to build nodes of a different type, override
    create(Token).
    """
    
    def dupNode(self, treeNode):
        """
        Duplicate a node.  This is part of the factory;
        override if you want another kind of node to be built.

        I could use reflection to prevent having to override this
        but reflection is slow.
        """
        
        return treeNode.dupNode()


    def createWithPayload(self, payload):
        return CommonTree(payload)


    def createToken(self, fromToken=None, tokenType=None, text=None):
        """
        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.
        """
        
        if fromToken is not None:
            return CommonToken(oldToken=fromToken)