tree.py

antlr最新版本V3源代码

        
        if fromToken is not None:
            return CommonToken(oldToken=fromToken)

        return CommonToken(type=tokenType, text=text)


    def setTokenBoundaries(self, t, startToken, stopToken):
        """
        Track start/stop token for subtree root created for a rule.
        Only works with Tree nodes.  For rules that match nothing,
        seems like this will yield start=i and stop=i-1 in a nil node.
        Might be useful info so I'll not force to be i..i.
        """
        
        if t is None:
            return

        start = 0
        stop = 0
        
        if startToken is not None:
            start = startToken.index
                
        if stopToken is not None:
            stop = stopToken.index

        t.setTokenStartIndex(start)
        t.setTokenStopIndex(stop)


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


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


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


    def getType(self, t):
        if t is None:
            return INVALID_TOKEN_TYPE
        
        return t.getType()


    def getToken(self, t):
        """
        What is the Token associated with this node?  If
        you are not using CommonTree, then you must
        override this in your own adaptor.
        """

        if isinstance(t, CommonTree):
            return t.getToken()

        return None # no idea what to do


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


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


############################################################################
#
# streams
#
# TreeNodeStream
# \- BaseTree
#    \- CommonTree
#
# TreeAdaptor
# \- BaseTreeAdaptor
#    \- CommonTreeAdaptor
#
############################################################################



class TreeNodeStream(IntStream):
    """@brief A stream of tree nodes

    It accessing nodes from a tree of some kind.
    """
    
    # TreeNodeStream is abstract, no need to complain about not implemented
    # abstract methods
    # pylint: disable-msg=W0223
    
    def get(self, i):
        """Get a tree node at an absolute index i; 0..n-1.
        If you don't want to buffer up nodes, then this method makes no
        sense for you.
        """

        raise NotImplementedError


    def LT(self, k):
        """
        Get tree node at current input pointer + i ahead where i=1 is next node.
        i<0 indicates nodes in the past.  So LT(-1) is previous node, but
        implementations are not required to provide results for k < -1.
        LT(0) is undefined.  For i>=n, return null.
        Return null for LT(0) and any index that results in an absolute address
        that is negative.

        This is analogus to the LT() method of the TokenStream, but this
        returns a tree node instead of a token.  Makes code gen identical
        for both parser and tree grammars. :)
        """

        raise NotImplementedError


    def getTreeSource(self):
        """
        Where is this stream pulling nodes from?  This is not the name, but
        the object that provides node objects.
        """

        raise NotImplementedError
    

    def getTokenStream(self):
        """
        If the tree associated with this stream was created from a TokenStream,
        you can specify it here.  Used to do rule $text attribute in tree
        parser.  Optional unless you use tree parser rule text attribute
        or output=template and rewrite=true options.
        """

        raise NotImplementedError


    def getTreeAdaptor(self):
        """
        What adaptor can tell me how to interpret/navigate nodes and
        trees.  E.g., get text of a node.
        """

        raise NotImplementedError
        

    def setUniqueNavigationNodes(self, uniqueNavigationNodes):
        """
        As we flatten the tree, we use UP, DOWN nodes to represent
        the tree structure.  When debugging we need unique nodes
        so we have to instantiate new ones.  When doing normal tree
        parsing, it's slow and a waste of memory to create unique
        navigation nodes.  Default should be false;
        """

        raise NotImplementedError
        

    def toString(self, start, stop):
        """
        Return the text of all nodes from start to stop, inclusive.
        If the stream does not buffer all the nodes then it can still
        walk recursively from start until stop.  You can always return
        null or "" too, but users should not access $ruleLabel.text in
        an action of course in that case.
        """

        raise NotImplementedError


class CommonTreeNodeStream(TreeNodeStream):
    """@brief A buffered stream of tree nodes.

    Nodes can be from a tree of ANY kind.

    This node stream sucks all nodes out of the tree specified in
    the constructor during construction and makes pointers into
    the tree using an array of Object pointers. The stream necessarily
    includes pointers to DOWN and UP and EOF nodes.

    This stream knows how to mark/release for backtracking.

    This stream is most suitable for tree interpreters that need to
    jump around a lot or for tree parsers requiring speed (at cost of memory).
    There is some duplicated functionality here with UnBufferedTreeNodeStream
    but just in bookkeeping, not tree walking etc...

    @see UnBufferedTreeNodeStream
    """
    
    # If tokenTypesToReverseIndex set to INDEX_ALL then indexing
    # occurs for all token types.
    INDEX_ALL = '***INDEX_ALL***'

    def __init__(self, *args):
        TreeNodeStream.__init__(self)

        if len(args) == 1:
            adaptor = CommonTreeAdaptor()
            tree = args[0]

        elif len(args) == 2:
            adaptor = args[0]
            tree = args[1]

        else:
            raise TypeError("Invalid arguments")
        
        # all these navigation nodes are shared and hence they
        # cannot contain any line/column info
        self.down = adaptor.createFromType(DOWN, "DOWN")
        self.up = adaptor.createFromType(UP, "UP")
        self.eof = adaptor.createFromType(EOF, "EOF")

        # The complete mapping from stream index to tree node.
        # This buffer includes pointers to DOWN, UP, and EOF nodes.
        # It is built upon ctor invocation.  The elements are type
        #  Object as we don't what the trees look like.

        # Load upon first need of the buffer so we can set token types
        # of interest for reverseIndexing.  Slows us down a wee bit to
        # do all of the if p==-1 testing everywhere though.
        self.nodes = []

        # Pull nodes from which tree?
        self.root = tree

        # IF this tree (root) was created from a token stream, track it.
        self.tokens = None

        # What tree adaptor was used to build these trees
        self.adaptor = adaptor

        # Reuse same DOWN, UP navigation nodes unless this is true
        self.uniqueNavigationNodes = False

        # The index into the nodes list of the current node (next node
        # to consume).  If -1, nodes array not filled yet.
        self.p = -1

        # Track the last mark() call result value for use in rewind().
        self.lastMarker = None

        # Stack of indexes used for push/pop calls
        self.calls = []

        # During fillBuffer(), we can make a reverse index from a set
        # of token types of interest to the list of indexes into the
        # node stream.  This lets us convert a node pointer to a
        # stream index semi-efficiently for a list of interesting
        # nodes such as function definition nodes (you'll want to seek
        # to their bodies for an interpreter).  Also useful for doing
        # dynamic searches; i.e., go find me all PLUS nodes.
        self.tokenTypeToStreamIndexesMap = None

        # A set of token types user would like to index for faster lookup.
        # If this is INDEX_ALL, then all token types are tracked.  If null,
        # then none are indexed.
        self.tokenTypesToReverseIndex = None



    def fillBuffer(self):
        """Walk tree with depth-first-search and fill nodes buffer.
        Don't do DOWN, UP nodes if its a list (t is isNil).
        """

        self._fillBuffer(self.root)
        self.p = 0 # buffer of nodes intialized now


    def _fillBuffer(self, t):
        nil = self.adaptor.isNil(t)
        
        if not nil:
            self.nodes.append(t) # add this node
            self.fillReverseIndex(t, len(self.nodes) - 1)

        # add DOWN node if t has children
        n = self.adaptor.getChildCount(t)
        if not nil and n > 0:
            self.addNavigationNode(DOWN)

        # and now add all its children
        for c in range(n):
            self._fillBuffer(self.adaptor.getChild(t, c))

        # add UP node if t has children
        if not nil and n > 0:
            self.addNavigationNode(UP)


    def fillReverseIndex(self, node, streamIndex):
        """
        Given a node, add this to the reverse index tokenTypeToStreamIndexesMap.
        You can override this method to alter how indexing occurs.  The
        default is to create a

           Map<Integer token type,ArrayList<Integer stream index>>

        This data structure allows you to find all nodes with type INT in order.

        If you really need to find a node of type, say, FUNC quickly then perhaps

           Map<Integertoken type,Map<Object tree node,Integer stream index>>

        would be better for you.  The interior maps map a tree node to
        the index so you don't have to search linearly for a specific node.

        If you change this method, you will likely need to change
        getNodeIndex(), which extracts information.
        """
        
        #System.out.println("revIndex "+node+"@"+streamIndex);
        if self.tokenTypesToReverseIndex is None:
            return # no indexing if this is empty (nothing of interest)

        if self.tokenTypeToStreamIndexesMap is None:
            self.tokenTypeToStreamIndexesMap = {} # first indexing op

        tokenType = self.adaptor.getType(node)
        if not (self.tokenTypesToReverseIndex == self.INDEX_ALL
                or tokenType in self.tokenTypesToReverseIndex
                ):
            return # tokenType not of interest

        indexes = self.tokenTypeToStreamIndexesMap.get(tokenType, None)
        if indexes is None:
            indexes = [] # no list yet for this token type
            indexes.append(streamIndex) # not there yet, add
            self.tokenTypeToStreamIndexesMap[tokenType] = indexes

        else:
            if streamIndex not in indexes:
                indexes.append(streamIndex) # not there yet, add


    def reverseIndex(self, tokenType):
        """
        For set of token types:
        Track the indicated token types in the reverse index. Set
        to INDEX_ALL to track all token types.
        
        For a single token type:
        Track the indicated token type in the reverse index.  Call this
        repeatedly for each type or use variant with Set argument to
        set all at once.
        
        @param tokenType
        """

        if isinstance(tokenType, (set, frozenset)):
            self.tokenTypesToReverseIndex = tokenType

        else:
            # add single type to set
            if self.tokenTypesToReverseIndex is None:
                self.tokenTypesToReverseIndex = set()

            elif self.tokenTypesToReverseIndex == self.INDEX_ALL:
                return

            self.tokenTypesToReverseIndex.add(tokenType)


    def getNodeIndex(self, node):
        """
        Given a node pointer, return its index into the node stream.
        This is not its Token stream index.  If there is no reverse map
        from node to stream index or the map does not contain entries
        for node's token type, a linear search of entire stream is used.

        Return -1 if exact node pointer not in stream.
        """
        
        #System.out.println("get "+node);
        if self.tokenTypeToStreamIndexesMap is None:
            return self.getNodeIndexLinearly(node)

        tokenType = self.adaptor.getType(node)
        indexes = self.tokenTypeToStreamIndexesMap.get(tokenType, None)
        if indexes  is None:
            #System.out.println("found linearly; stream index = "+getNodeIndexLinearly(node));
            return self.getNodeIndexLinearly(node)
      
        for streamIndex in indexes:
            n = self.get(streamIndex)
            if n == node:
                #System.out.println("found in index; stream index = "+streamIndexI);
                return streamIndex # found it!


        return -1


    def getNodeIndexLinearly(self, node):
        if self.p == -1:
            self.fillBuffer()

        for i, t in enumerate(self.nodes):
            if t == node:
                return i

        return -1


    def addNavigationNode(self, ttype):
        """
        As we flatten the tree, we use UP, DOWN nodes to represent
        the tree structure.  When debugging we need unique nodes
        so instantiate new ones when uniqueNavigationNodes is true.
        """
        
        navNode = None
        
        if ttype == DOWN:
            if self.hasUniqueNavigationNodes():
                navNode = self.adaptor.createFromType(DOWN, "DOWN")

            else:
                navNode = self.down

        else:
            if self.hasUniqueNavigationNodes():
                navNode = self.adaptor.createFromType(UP, "UP")
                
            else:
                navNode = self.up

        self.nodes.append(navNode)


    def get(self, i):
        if self.p == -1:
            self.fillBuffer()

        return self.nodes[i]


    def LT(self, k):
        if self.p == -1:
            self.fillBuffer()

        if k == 0:
            return None

        if k < 0:
            return self.LB(-k)

        #System.out.print("LT(p="+p+","+k+")=");
        if self.p + k - 1 >= len(self.nodes):
            return self.eof

        return self.nodes[self.p + k - 1]
    

    def LB(self, k):
        """Look backwards k nodes"""
        
        if k == 0:
            return None

        if self.p - k < 0:
            return None

        return self.nodes[self.p - k]


    def getTreeSource(self):
        return self.root


    def getTokenStream(self):
        return self.tokens


    def setTokenStream(self, tokens):
        self.tokens = tokens


    def getTreeAdaptor(self):
        return self.adaptor