source: proto/RE2Pablo/ref/re2pbs/antlr/antlr_python_runtime-3.1.3/build/lib.linux-i686-2.7/antlr3/tree.py @ 2226

Last change on this file since 2226 was 2226, checked in by ksherdy, 7 years ago

Initial check in.

File size: 76.5 KB
Line 
1""" @package antlr3.tree
2@brief ANTLR3 runtime package, tree module
3
4This module contains all support classes for AST construction and tree parsers.
5
6"""
7
8# begin[licence]
9#
10# [The "BSD licence"]
11# Copyright (c) 2005-2008 Terence Parr
12# All rights reserved.
13#
14# Redistribution and use in source and binary forms, with or without
15# modification, are permitted provided that the following conditions
16# are met:
17# 1. Redistributions of source code must retain the above copyright
18#    notice, this list of conditions and the following disclaimer.
19# 2. Redistributions in binary form must reproduce the above copyright
20#    notice, this list of conditions and the following disclaimer in the
21#    documentation and/or other materials provided with the distribution.
22# 3. The name of the author may not be used to endorse or promote products
23#    derived from this software without specific prior written permission.
24#
25# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
26# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
27# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
28# IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
29# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
30# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
31# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
32# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
34# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35#
36# end[licence]
37
38# lot's of docstrings are missing, don't complain for now...
39# pylint: disable-msg=C0111
40
41import re
42
43from antlr3.constants import UP, DOWN, EOF, INVALID_TOKEN_TYPE
44from antlr3.recognizers import BaseRecognizer, RuleReturnScope
45from antlr3.streams import IntStream
46from antlr3.tokens import CommonToken, Token, INVALID_TOKEN
47from antlr3.exceptions import MismatchedTreeNodeException, \
48     MissingTokenException, UnwantedTokenException, MismatchedTokenException, \
49     NoViableAltException
50
51
52############################################################################
53#
54# tree related exceptions
55#
56############################################################################
57
58
59class RewriteCardinalityException(RuntimeError):
60    """
61    @brief Base class for all exceptions thrown during AST rewrite construction.
62
63    This signifies a case where the cardinality of two or more elements
64    in a subrule are different: (ID INT)+ where |ID|!=|INT|
65    """
66
67    def __init__(self, elementDescription):
68        RuntimeError.__init__(self, elementDescription)
69
70        self.elementDescription = elementDescription
71
72
73    def getMessage(self):
74        return self.elementDescription
75
76
77class RewriteEarlyExitException(RewriteCardinalityException):
78    """@brief No elements within a (...)+ in a rewrite rule"""
79
80    def __init__(self, elementDescription=None):
81        RewriteCardinalityException.__init__(self, elementDescription)
82
83
84class RewriteEmptyStreamException(RewriteCardinalityException):
85    """
86    @brief Ref to ID or expr but no tokens in ID stream or subtrees in expr stream
87    """
88
89    pass
90
91
92############################################################################
93#
94# basic Tree and TreeAdaptor interfaces
95#
96############################################################################
97
98class Tree(object):
99    """
100    @brief Abstract baseclass for tree nodes.
101   
102    What does a tree look like?  ANTLR has a number of support classes
103    such as CommonTreeNodeStream that work on these kinds of trees.  You
104    don't have to make your trees implement this interface, but if you do,
105    you'll be able to use more support code.
106
107    NOTE: When constructing trees, ANTLR can build any kind of tree; it can
108    even use Token objects as trees if you add a child list to your tokens.
109   
110    This is a tree node without any payload; just navigation and factory stuff.
111    """
112
113
114    def getChild(self, i):
115        raise NotImplementedError
116   
117
118    def getChildCount(self):
119        raise NotImplementedError
120   
121
122    def getParent(self):
123        """Tree tracks parent and child index now > 3.0"""
124
125        raise NotImplementedError
126   
127    def setParent(self, t):
128        """Tree tracks parent and child index now > 3.0"""
129
130        raise NotImplementedError
131   
132
133    def hasAncestor(self, ttype):
134        """Walk upwards looking for ancestor with this token type."""
135
136        raise NotImplementedError
137
138    def getAncestor(self, ttype):
139        """Walk upwards and get first ancestor with this token type."""
140
141        raise NotImplementedError
142
143    def getAncestors(self):
144        """Return a list of all ancestors of this node.
145
146        The first node of list is the root and the last is the parent of
147        this node.
148        """
149
150        raise NotImplementedError
151
152
153    def getChildIndex(self):
154        """This node is what child index? 0..n-1"""
155
156        raise NotImplementedError
157       
158    def setChildIndex(self, index):
159        """This node is what child index? 0..n-1"""
160
161        raise NotImplementedError
162       
163
164    def freshenParentAndChildIndexes(self):
165        """Set the parent and child index values for all children"""
166       
167        raise NotImplementedError
168
169       
170    def addChild(self, t):
171        """
172        Add t as a child to this node.  If t is null, do nothing.  If t
173        is nil, add all children of t to this' children.
174        """
175
176        raise NotImplementedError
177   
178
179    def setChild(self, i, t):
180        """Set ith child (0..n-1) to t; t must be non-null and non-nil node"""
181
182        raise NotImplementedError
183
184           
185    def deleteChild(self, i):
186        raise NotImplementedError
187       
188 
189    def replaceChildren(self, startChildIndex, stopChildIndex, t):
190        """
191        Delete children from start to stop and replace with t even if t is
192        a list (nil-root tree).  num of children can increase or decrease.
193        For huge child lists, inserting children can force walking rest of
194        children to set their childindex; could be slow.
195        """
196
197        raise NotImplementedError
198
199
200    def isNil(self):
201        """
202        Indicates the node is a nil node but may still have children, meaning
203        the tree is a flat list.
204        """
205
206        raise NotImplementedError
207   
208
209    def getTokenStartIndex(self):
210        """
211        What is the smallest token index (indexing from 0) for this node
212           and its children?
213        """
214
215        raise NotImplementedError
216
217
218    def setTokenStartIndex(self, index):
219        raise NotImplementedError
220
221
222    def getTokenStopIndex(self):
223        """
224        What is the largest token index (indexing from 0) for this node
225        and its children?
226        """
227
228        raise NotImplementedError
229
230
231    def setTokenStopIndex(self, index):
232        raise NotImplementedError
233
234
235    def dupNode(self):
236        raise NotImplementedError
237   
238   
239    def getType(self):
240        """Return a token type; needed for tree parsing."""
241
242        raise NotImplementedError
243   
244
245    def getText(self):
246        raise NotImplementedError
247   
248
249    def getLine(self):
250        """
251        In case we don't have a token payload, what is the line for errors?
252        """
253
254        raise NotImplementedError
255   
256
257    def getCharPositionInLine(self):
258        raise NotImplementedError
259
260
261    def toStringTree(self):
262        raise NotImplementedError
263
264
265    def toString(self):
266        raise NotImplementedError
267
268
269
270class TreeAdaptor(object):
271    """
272    @brief Abstract baseclass for tree adaptors.
273   
274    How to create and navigate trees.  Rather than have a separate factory
275    and adaptor, I've merged them.  Makes sense to encapsulate.
276
277    This takes the place of the tree construction code generated in the
278    generated code in 2.x and the ASTFactory.
279
280    I do not need to know the type of a tree at all so they are all
281    generic Objects.  This may increase the amount of typecasting needed. :(
282    """
283   
284    # C o n s t r u c t i o n
285
286    def createWithPayload(self, payload):
287        """
288        Create a tree node from Token object; for CommonTree type trees,
289        then the token just becomes the payload.  This is the most
290        common create call.
291
292        Override if you want another kind of node to be built.
293        """
294
295        raise NotImplementedError
296   
297
298    def dupNode(self, treeNode):
299        """Duplicate a single tree node.
300
301        Override if you want another kind of node to be built."""
302
303        raise NotImplementedError
304
305
306    def dupTree(self, tree):
307        """Duplicate tree recursively, using dupNode() for each node"""
308
309        raise NotImplementedError
310
311
312    def nil(self):
313        """
314        Return a nil node (an empty but non-null node) that can hold
315        a list of element as the children.  If you want a flat tree (a list)
316        use "t=adaptor.nil(); t.addChild(x); t.addChild(y);"
317        """
318
319        raise NotImplementedError
320
321
322    def errorNode(self, input, start, stop, exc):
323        """
324        Return a tree node representing an error.  This node records the
325        tokens consumed during error recovery.  The start token indicates the
326        input symbol at which the error was detected.  The stop token indicates
327        the last symbol consumed during recovery.
328
329        You must specify the input stream so that the erroneous text can
330        be packaged up in the error node.  The exception could be useful
331        to some applications; default implementation stores ptr to it in
332        the CommonErrorNode.
333
334        This only makes sense during token parsing, not tree parsing.
335        Tree parsing should happen only when parsing and tree construction
336        succeed.
337        """
338
339        raise NotImplementedError
340
341
342    def isNil(self, tree):
343        """Is tree considered a nil node used to make lists of child nodes?"""
344
345        raise NotImplementedError
346
347
348    def addChild(self, t, child):
349        """
350        Add a child to the tree t.  If child is a flat tree (a list), make all
351        in list children of t.  Warning: if t has no children, but child does
352        and child isNil then you can decide it is ok to move children to t via
353        t.children = child.children; i.e., without copying the array.  Just
354        make sure that this is consistent with have the user will build
355        ASTs. Do nothing if t or child is null.
356        """
357
358        raise NotImplementedError
359
360
361    def becomeRoot(self, newRoot, oldRoot):
362        """
363        If oldRoot is a nil root, just copy or move the children to newRoot.
364        If not a nil root, make oldRoot a child of newRoot.
365       
366           old=^(nil a b c), new=r yields ^(r a b c)
367           old=^(a b c), new=r yields ^(r ^(a b c))
368
369        If newRoot is a nil-rooted single child tree, use the single
370        child as the new root node.
371
372           old=^(nil a b c), new=^(nil r) yields ^(r a b c)
373           old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
374
375        If oldRoot was null, it's ok, just return newRoot (even if isNil).
376
377           old=null, new=r yields r
378           old=null, new=^(nil r) yields ^(nil r)
379
380        Return newRoot.  Throw an exception if newRoot is not a
381        simple node or nil root with a single child node--it must be a root
382        node.  If newRoot is ^(nil x) return x as newRoot.
383
384        Be advised that it's ok for newRoot to point at oldRoot's
385        children; i.e., you don't have to copy the list.  We are
386        constructing these nodes so we should have this control for
387        efficiency.
388        """
389
390        raise NotImplementedError
391
392
393    def rulePostProcessing(self, root):
394        """
395        Given the root of the subtree created for this rule, post process
396        it to do any simplifications or whatever you want.  A required
397        behavior is to convert ^(nil singleSubtree) to singleSubtree
398        as the setting of start/stop indexes relies on a single non-nil root
399        for non-flat trees.
400
401        Flat trees such as for lists like "idlist : ID+ ;" are left alone
402        unless there is only one ID.  For a list, the start/stop indexes
403        are set in the nil node.
404
405        This method is executed after all rule tree construction and right
406        before setTokenBoundaries().
407        """
408
409        raise NotImplementedError
410
411
412    def getUniqueID(self, node):
413        """For identifying trees.
414
415        How to identify nodes so we can say "add node to a prior node"?
416        Even becomeRoot is an issue.  Use System.identityHashCode(node)
417        usually.
418        """
419
420        raise NotImplementedError
421
422
423    # R e w r i t e  R u l e s
424
425    def createFromToken(self, tokenType, fromToken, text=None):
426        """
427        Create a new node derived from a token, with a new token type and
428        (optionally) new text.
429
430        This is invoked from an imaginary node ref on right side of a
431        rewrite rule as IMAG[$tokenLabel] or IMAG[$tokenLabel "IMAG"].
432
433        This should invoke createToken(Token).
434        """
435
436        raise NotImplementedError
437
438
439    def createFromType(self, tokenType, text):
440        """Create a new node derived from a token, with a new token type.
441
442        This is invoked from an imaginary node ref on right side of a
443        rewrite rule as IMAG["IMAG"].
444
445        This should invoke createToken(int,String).
446        """
447
448        raise NotImplementedError
449
450
451    # C o n t e n t
452
453    def getType(self, t):
454        """For tree parsing, I need to know the token type of a node"""
455
456        raise NotImplementedError
457
458
459    def setType(self, t, type):
460        """Node constructors can set the type of a node"""
461
462        raise NotImplementedError
463
464
465    def getText(self, t):
466        raise NotImplementedError
467
468    def setText(self, t, text):
469        """Node constructors can set the text of a node"""
470
471        raise NotImplementedError
472
473
474    def getToken(self, t):
475        """Return the token object from which this node was created.
476
477        Currently used only for printing an error message.
478        The error display routine in BaseRecognizer needs to
479        display where the input the error occurred. If your
480        tree of limitation does not store information that can
481        lead you to the token, you can create a token filled with
482        the appropriate information and pass that back.  See
483        BaseRecognizer.getErrorMessage().
484        """
485
486        raise NotImplementedError
487
488
489    def setTokenBoundaries(self, t, startToken, stopToken):
490        """
491        Where are the bounds in the input token stream for this node and
492        all children?  Each rule that creates AST nodes will call this
493        method right before returning.  Flat trees (i.e., lists) will
494        still usually have a nil root node just to hold the children list.
495        That node would contain the start/stop indexes then.
496        """
497
498        raise NotImplementedError
499
500
501    def getTokenStartIndex(self, t):
502        """
503        Get the token start index for this subtree; return -1 if no such index
504        """
505
506        raise NotImplementedError
507
508       
509    def getTokenStopIndex(self, t):
510        """
511        Get the token stop index for this subtree; return -1 if no such index
512        """
513
514        raise NotImplementedError
515       
516
517    # N a v i g a t i o n  /  T r e e  P a r s i n g
518
519    def getChild(self, t, i):
520        """Get a child 0..n-1 node"""
521
522        raise NotImplementedError
523
524
525    def setChild(self, t, i, child):
526        """Set ith child (0..n-1) to t; t must be non-null and non-nil node"""
527
528        raise NotImplementedError
529
530
531    def deleteChild(self, t, i):
532        """Remove ith child and shift children down from right."""
533       
534        raise NotImplementedError
535
536
537    def getChildCount(self, t):
538        """How many children?  If 0, then this is a leaf node"""
539
540        raise NotImplementedError
541
542
543    def getParent(self, t):
544        """
545        Who is the parent node of this node; if null, implies node is root.
546        If your node type doesn't handle this, it's ok but the tree rewrites
547        in tree parsers need this functionality.
548        """
549       
550        raise NotImplementedError
551
552
553    def setParent(self, t, parent):
554        """
555        Who is the parent node of this node; if null, implies node is root.
556        If your node type doesn't handle this, it's ok but the tree rewrites
557        in tree parsers need this functionality.
558        """
559
560        raise NotImplementedError
561
562
563    def getChildIndex(self, t):
564        """
565        What index is this node in the child list? Range: 0..n-1
566        If your node type doesn't handle this, it's ok but the tree rewrites
567        in tree parsers need this functionality.
568        """
569
570        raise NotImplementedError
571
572       
573    def setChildIndex(self, t, index):
574        """
575        What index is this node in the child list? Range: 0..n-1
576        If your node type doesn't handle this, it's ok but the tree rewrites
577        in tree parsers need this functionality.
578        """
579
580        raise NotImplementedError
581
582
583    def replaceChildren(self, parent, startChildIndex, stopChildIndex, t):
584        """
585        Replace from start to stop child index of parent with t, which might
586        be a list.  Number of children may be different
587        after this call.
588
589        If parent is null, don't do anything; must be at root of overall tree.
590        Can't replace whatever points to the parent externally.  Do nothing.
591        """
592
593        raise NotImplementedError
594
595
596    # Misc
597
598    def create(self, *args):
599        """
600        Deprecated, use createWithPayload, createFromToken or createFromType.
601
602        This method only exists to mimic the Java interface of TreeAdaptor.
603       
604        """
605
606        if len(args) == 1 and isinstance(args[0], Token):
607            # Object create(Token payload);
608##             warnings.warn(
609##                 "Using create() is deprecated, use createWithPayload()",
610##                 DeprecationWarning,
611##                 stacklevel=2
612##                 )
613            return self.createWithPayload(args[0])
614
615        if (len(args) == 2
616            and isinstance(args[0], (int, long))
617            and isinstance(args[1], Token)
618            ):
619            # Object create(int tokenType, Token fromToken);
620##             warnings.warn(
621##                 "Using create() is deprecated, use createFromToken()",
622##                 DeprecationWarning,
623##                 stacklevel=2
624##                 )
625            return self.createFromToken(args[0], args[1])
626
627        if (len(args) == 3
628            and isinstance(args[0], (int, long))
629            and isinstance(args[1], Token)
630            and isinstance(args[2], basestring)
631            ):
632            # Object create(int tokenType, Token fromToken, String text);
633##             warnings.warn(
634##                 "Using create() is deprecated, use createFromToken()",
635##                 DeprecationWarning,
636##                 stacklevel=2
637##                 )
638            return self.createFromToken(args[0], args[1], args[2])
639
640        if (len(args) == 2
641            and isinstance(args[0], (int, long))
642            and isinstance(args[1], basestring)
643            ):
644            # Object create(int tokenType, String text);
645##             warnings.warn(
646##                 "Using create() is deprecated, use createFromType()",
647##                 DeprecationWarning,
648##                 stacklevel=2
649##                 )
650            return self.createFromType(args[0], args[1])
651
652        raise TypeError(
653            "No create method with this signature found: %s"
654            % (', '.join(type(v).__name__ for v in args))
655            )
656   
657
658############################################################################
659#
660# base implementation of Tree and TreeAdaptor
661#
662# Tree
663# \- BaseTree
664#
665# TreeAdaptor
666# \- BaseTreeAdaptor
667#
668############################################################################
669
670
671class BaseTree(Tree):
672    """
673    @brief A generic tree implementation with no payload.
674
675    You must subclass to
676    actually have any user data.  ANTLR v3 uses a list of children approach
677    instead of the child-sibling approach in v2.  A flat tree (a list) is
678    an empty node whose children represent the list.  An empty, but
679    non-null node is called "nil".
680    """
681
682    # BaseTree is abstract, no need to complain about not implemented abstract
683    # methods
684    # pylint: disable-msg=W0223
685   
686    def __init__(self, node=None):
687        """
688        Create a new node from an existing node does nothing for BaseTree
689        as there are no fields other than the children list, which cannot
690        be copied as the children are not considered part of this node.
691        """
692       
693        Tree.__init__(self)
694        self.children = []
695        self.parent = None
696        self.childIndex = 0
697       
698
699    def getChild(self, i):
700        try:
701            return self.children[i]
702        except IndexError:
703            return None
704
705
706    def getChildren(self):
707        """@brief Get the children internal List
708
709        Note that if you directly mess with
710        the list, do so at your own risk.
711        """
712       
713        # FIXME: mark as deprecated
714        return self.children
715
716
717    def getFirstChildWithType(self, treeType):
718        for child in self.children:
719            if child.getType() == treeType:
720                return child
721
722        return None
723
724
725    def getChildCount(self):
726        return len(self.children)
727
728
729    def addChild(self, childTree):
730        """Add t as child of this node.
731
732        Warning: if t has no children, but child does
733        and child isNil then this routine moves children to t via
734        t.children = child.children; i.e., without copying the array.
735        """
736
737        # this implementation is much simpler and probably less efficient
738        # than the mumbo-jumbo that Ter did for the Java runtime.
739       
740        if childTree is None:
741            return
742
743        if childTree.isNil():
744            # t is an empty node possibly with children
745
746            if self.children is childTree.children:
747                raise ValueError("attempt to add child list to itself")
748
749            # fix parent pointer and childIndex for new children
750            for idx, child in enumerate(childTree.children):
751                child.parent = self
752                child.childIndex = len(self.children) + idx
753               
754            self.children += childTree.children
755
756        else:
757            # child is not nil (don't care about children)
758            self.children.append(childTree)
759            childTree.parent = self
760            childTree.childIndex = len(self.children) - 1
761
762
763    def addChildren(self, children):
764        """Add all elements of kids list as children of this node"""
765
766        self.children += children
767
768
769    def setChild(self, i, t):
770        if t is None:
771            return
772
773        if t.isNil():
774            raise ValueError("Can't set single child to a list")
775       
776        self.children[i] = t
777        t.parent = self
778        t.childIndex = i
779       
780
781    def deleteChild(self, i):
782        killed = self.children[i]
783       
784        del self.children[i]
785       
786        # walk rest and decrement their child indexes
787        for idx, child in enumerate(self.children[i:]):
788            child.childIndex = i + idx
789           
790        return killed
791
792   
793    def replaceChildren(self, startChildIndex, stopChildIndex, newTree):
794        """
795        Delete children from start to stop and replace with t even if t is
796        a list (nil-root tree).  num of children can increase or decrease.
797        For huge child lists, inserting children can force walking rest of
798        children to set their childindex; could be slow.
799        """
800
801        if (startChildIndex >= len(self.children)
802            or stopChildIndex >= len(self.children)
803            ):
804            raise IndexError("indexes invalid")
805
806        replacingHowMany = stopChildIndex - startChildIndex + 1
807
808        # normalize to a list of children to add: newChildren
809        if newTree.isNil():
810            newChildren = newTree.children
811
812        else:
813            newChildren = [newTree]
814
815        replacingWithHowMany = len(newChildren)
816        delta = replacingHowMany - replacingWithHowMany
817       
818       
819        if delta == 0:
820            # if same number of nodes, do direct replace
821            for idx, child in enumerate(newChildren):
822                self.children[idx + startChildIndex] = child
823                child.parent = self
824                child.childIndex = idx + startChildIndex
825
826        else:
827            # length of children changes...
828
829            # ...delete replaced segment...
830            del self.children[startChildIndex:stopChildIndex+1]
831
832            # ...insert new segment...
833            self.children[startChildIndex:startChildIndex] = newChildren
834
835            # ...and fix indeces
836            self.freshenParentAndChildIndexes(startChildIndex)
837           
838
839    def isNil(self):
840        return False
841
842
843    def freshenParentAndChildIndexes(self, offset=0):
844        for idx, child in enumerate(self.children[offset:]):
845            child.childIndex = idx + offset
846            child.parent = self
847
848
849    def sanityCheckParentAndChildIndexes(self, parent=None, i=-1):
850        if parent != self.parent:
851            raise ValueError(
852                "parents don't match; expected %r found %r"
853                % (parent, self.parent)
854                )
855       
856        if i != self.childIndex:
857            raise ValueError(
858                "child indexes don't match; expected %d found %d"
859                % (i, self.childIndex)
860                )
861
862        for idx, child in enumerate(self.children):
863            child.sanityCheckParentAndChildIndexes(self, idx)
864
865
866    def getChildIndex(self):
867        """BaseTree doesn't track child indexes."""
868       
869        return 0
870
871
872    def setChildIndex(self, index):
873        """BaseTree doesn't track child indexes."""
874
875        pass
876   
877
878    def getParent(self):
879        """BaseTree doesn't track parent pointers."""
880
881        return None
882
883    def setParent(self, t):
884        """BaseTree doesn't track parent pointers."""
885
886        pass
887
888
889    def hasAncestor(self, ttype):
890        """Walk upwards looking for ancestor with this token type."""
891        return self.getAncestor(ttype) is not None
892
893    def getAncestor(self, ttype):
894        """Walk upwards and get first ancestor with this token type."""
895        t = self.getParent()
896        while t is not None:
897            if t.getType() == ttype:
898                return t
899            t = t.getParent()
900
901        return None
902
903    def getAncestors(self):
904        """Return a list of all ancestors of this node.
905
906        The first node of list is the root and the last is the parent of
907        this node.
908        """
909        if selfgetParent() is None:
910            return None
911
912        ancestors = []
913        t = self.getParent()
914        while t is not None:
915            ancestors.insert(0, t) # insert at start
916            t = t.getParent()
917
918        return ancestors
919
920
921    def toStringTree(self):
922        """Print out a whole tree not just a node"""
923
924        if len(self.children) == 0:
925            return self.toString()
926
927        buf = []
928        if not self.isNil():
929            buf.append('(')
930            buf.append(self.toString())
931            buf.append(' ')
932
933        for i, child in enumerate(self.children):
934            if i > 0:
935                buf.append(' ')
936            buf.append(child.toStringTree())
937
938        if not self.isNil():
939            buf.append(')')
940
941        return ''.join(buf)
942
943
944    def getLine(self):
945        return 0
946
947
948    def getCharPositionInLine(self):
949        return 0
950
951
952    def toString(self):
953        """Override to say how a node (not a tree) should look as text"""
954
955        raise NotImplementedError
956
957
958
959class BaseTreeAdaptor(TreeAdaptor):
960    """
961    @brief A TreeAdaptor that works with any Tree implementation.
962    """
963   
964    # BaseTreeAdaptor is abstract, no need to complain about not implemented
965    # abstract methods
966    # pylint: disable-msg=W0223
967   
968    def nil(self):
969        return self.createWithPayload(None)
970
971
972    def errorNode(self, input, start, stop, exc):
973        """
974        create tree node that holds the start and stop tokens associated
975        with an error.
976
977        If you specify your own kind of tree nodes, you will likely have to
978        override this method. CommonTree returns Token.INVALID_TOKEN_TYPE
979        if no token payload but you might have to set token type for diff
980        node type.
981
982        You don't have to subclass CommonErrorNode; you will likely need to
983        subclass your own tree node class to avoid class cast exception.
984        """
985       
986        return CommonErrorNode(input, start, stop, exc)
987   
988
989    def isNil(self, tree):
990        return tree.isNil()
991
992
993    def dupTree(self, t, parent=None):
994        """
995        This is generic in the sense that it will work with any kind of
996        tree (not just Tree interface).  It invokes the adaptor routines
997        not the tree node routines to do the construction.
998        """
999
1000        if t is None:
1001            return None
1002
1003        newTree = self.dupNode(t)
1004       
1005        # ensure new subtree root has parent/child index set
1006
1007        # same index in new tree
1008        self.setChildIndex(newTree, self.getChildIndex(t))
1009       
1010        self.setParent(newTree, parent)
1011
1012        for i in range(self.getChildCount(t)):
1013            child = self.getChild(t, i)
1014            newSubTree = self.dupTree(child, t)
1015            self.addChild(newTree, newSubTree)
1016
1017        return newTree
1018
1019
1020    def addChild(self, tree, child):
1021        """
1022        Add a child to the tree t.  If child is a flat tree (a list), make all
1023        in list children of t.  Warning: if t has no children, but child does
1024        and child isNil then you can decide it is ok to move children to t via
1025        t.children = child.children; i.e., without copying the array.  Just
1026        make sure that this is consistent with have the user will build
1027        ASTs.
1028        """
1029
1030        #if isinstance(child, Token):
1031        #    child = self.createWithPayload(child)
1032       
1033        if tree is not None and child is not None:
1034            tree.addChild(child)
1035
1036
1037    def becomeRoot(self, newRoot, oldRoot):
1038        """
1039        If oldRoot is a nil root, just copy or move the children to newRoot.
1040        If not a nil root, make oldRoot a child of newRoot.
1041
1042          old=^(nil a b c), new=r yields ^(r a b c)
1043          old=^(a b c), new=r yields ^(r ^(a b c))
1044
1045        If newRoot is a nil-rooted single child tree, use the single
1046        child as the new root node.
1047
1048          old=^(nil a b c), new=^(nil r) yields ^(r a b c)
1049          old=^(a b c), new=^(nil r) yields ^(r ^(a b c))
1050
1051        If oldRoot was null, it's ok, just return newRoot (even if isNil).
1052
1053          old=null, new=r yields r
1054          old=null, new=^(nil r) yields ^(nil r)
1055
1056        Return newRoot.  Throw an exception if newRoot is not a
1057        simple node or nil root with a single child node--it must be a root
1058        node.  If newRoot is ^(nil x) return x as newRoot.
1059
1060        Be advised that it's ok for newRoot to point at oldRoot's
1061        children; i.e., you don't have to copy the list.  We are
1062        constructing these nodes so we should have this control for
1063        efficiency.
1064        """
1065
1066        if isinstance(newRoot, Token):
1067            newRoot = self.create(newRoot)
1068
1069        if oldRoot is None:
1070            return newRoot
1071       
1072        if not isinstance(newRoot, CommonTree):
1073            newRoot = self.createWithPayload(newRoot)
1074
1075        # handle ^(nil real-node)
1076        if newRoot.isNil():
1077            nc = newRoot.getChildCount()
1078            if nc == 1:
1079                newRoot = newRoot.getChild(0)
1080               
1081            elif nc > 1:
1082                # TODO: make tree run time exceptions hierarchy
1083                raise RuntimeError("more than one node as root")
1084
1085        # add oldRoot to newRoot; addChild takes care of case where oldRoot
1086        # is a flat list (i.e., nil-rooted tree).  All children of oldRoot
1087        # are added to newRoot.
1088        newRoot.addChild(oldRoot)
1089        return newRoot
1090
1091
1092    def rulePostProcessing(self, root):
1093        """Transform ^(nil x) to x and nil to null"""
1094       
1095        if root is not None and root.isNil():
1096            if root.getChildCount() == 0:
1097                root = None
1098
1099            elif root.getChildCount() == 1:
1100                root = root.getChild(0)
1101                # whoever invokes rule will set parent and child index
1102                root.setParent(None)
1103                root.setChildIndex(-1)
1104
1105        return root
1106
1107
1108    def createFromToken(self, tokenType, fromToken, text=None):
1109        assert isinstance(tokenType, (int, long)), type(tokenType).__name__
1110        assert isinstance(fromToken, Token), type(fromToken).__name__
1111        assert text is None or isinstance(text, basestring), type(text).__name__
1112
1113        fromToken = self.createToken(fromToken)
1114        fromToken.type = tokenType
1115        if text is not None:
1116            fromToken.text = text
1117        t = self.createWithPayload(fromToken)
1118        return t
1119
1120
1121    def createFromType(self, tokenType, text):
1122        assert isinstance(tokenType, (int, long)), type(tokenType).__name__
1123        assert isinstance(text, basestring) or text is None, type(text).__name__
1124                         
1125        fromToken = self.createToken(tokenType=tokenType, text=text)
1126        t = self.createWithPayload(fromToken)
1127        return t
1128
1129
1130    def getType(self, t):
1131        return t.getType()
1132
1133
1134    def setType(self, t, type):
1135        raise RuntimeError("don't know enough about Tree node")
1136
1137
1138    def getText(self, t):
1139        return t.getText()
1140
1141
1142    def setText(self, t, text):
1143        raise RuntimeError("don't know enough about Tree node")
1144
1145
1146    def getChild(self, t, i):
1147        return t.getChild(i)
1148
1149
1150    def setChild(self, t, i, child):
1151        t.setChild(i, child)
1152
1153
1154    def deleteChild(self, t, i):
1155        return t.deleteChild(i)
1156
1157
1158    def getChildCount(self, t):
1159        return t.getChildCount()
1160
1161
1162    def getUniqueID(self, node):
1163        return hash(node)
1164
1165
1166    def createToken(self, fromToken=None, tokenType=None, text=None):
1167        """
1168        Tell me how to create a token for use with imaginary token nodes.
1169        For example, there is probably no input symbol associated with imaginary
1170        token DECL, but you need to create it as a payload or whatever for
1171        the DECL node as in ^(DECL type ID).
1172
1173        If you care what the token payload objects' type is, you should
1174        override this method and any other createToken variant.
1175        """
1176
1177        raise NotImplementedError
1178
1179
1180############################################################################
1181#
1182# common tree implementation
1183#
1184# Tree
1185# \- BaseTree
1186#    \- CommonTree
1187#       \- CommonErrorNode
1188#
1189# TreeAdaptor
1190# \- BaseTreeAdaptor
1191#    \- CommonTreeAdaptor
1192#
1193############################################################################
1194
1195
1196class CommonTree(BaseTree):
1197    """@brief A tree node that is wrapper for a Token object.
1198
1199    After 3.0 release
1200    while building tree rewrite stuff, it became clear that computing
1201    parent and child index is very difficult and cumbersome.  Better to
1202    spend the space in every tree node.  If you don't want these extra
1203    fields, it's easy to cut them out in your own BaseTree subclass.
1204   
1205    """
1206
1207    def __init__(self, payload):
1208        BaseTree.__init__(self)
1209       
1210        # What token indexes bracket all tokens associated with this node
1211        # and below?
1212        self.startIndex = -1
1213        self.stopIndex = -1
1214
1215        # Who is the parent node of this node; if null, implies node is root
1216        self.parent = None
1217       
1218        # What index is this node in the child list? Range: 0..n-1
1219        self.childIndex = -1
1220
1221        # A single token is the payload
1222        if payload is None:
1223            self.token = None
1224           
1225        elif isinstance(payload, CommonTree):
1226            self.token = payload.token
1227            self.startIndex = payload.startIndex
1228            self.stopIndex = payload.stopIndex
1229           
1230        elif payload is None or isinstance(payload, Token):
1231            self.token = payload
1232           
1233        else:
1234            raise TypeError(type(payload).__name__)
1235
1236
1237
1238    def getToken(self):
1239        return self.token
1240
1241
1242    def dupNode(self):
1243        return CommonTree(self)
1244
1245
1246    def isNil(self):
1247        return self.token is None
1248
1249
1250    def getType(self):
1251        if self.token is None:
1252            return INVALID_TOKEN_TYPE
1253
1254        return self.token.getType()
1255
1256    type = property(getType)
1257   
1258
1259    def getText(self):
1260        if self.token is None:
1261            return None
1262       
1263        return self.token.text
1264
1265    text = property(getText)
1266   
1267
1268    def getLine(self):
1269        if self.token is None or self.token.getLine() == 0:
1270            if self.getChildCount():
1271                return self.getChild(0).getLine()
1272            else:
1273                return 0
1274
1275        return self.token.getLine()
1276
1277    line = property(getLine)
1278   
1279
1280    def getCharPositionInLine(self):
1281        if self.token is None or self.token.getCharPositionInLine() == -1:
1282            if self.getChildCount():
1283                return self.getChild(0).getCharPositionInLine()
1284            else:
1285                return 0
1286
1287        else:
1288            return self.token.getCharPositionInLine()
1289
1290    charPositionInLine = property(getCharPositionInLine)
1291   
1292
1293    def getTokenStartIndex(self):
1294        if self.startIndex == -1 and self.token is not None:
1295            return self.token.getTokenIndex()
1296       
1297        return self.startIndex
1298   
1299    def setTokenStartIndex(self, index):
1300        self.startIndex = index
1301
1302    tokenStartIndex = property(getTokenStartIndex, setTokenStartIndex)
1303
1304
1305    def getTokenStopIndex(self):
1306        if self.stopIndex == -1 and self.token is not None:
1307            return self.token.getTokenIndex()
1308       
1309        return self.stopIndex
1310
1311    def setTokenStopIndex(self, index):
1312        self.stopIndex = index
1313
1314    tokenStopIndex = property(getTokenStopIndex, setTokenStopIndex)
1315
1316
1317    def setUnknownTokenBoundaries(self):
1318        """For every node in this subtree, make sure it's start/stop token's
1319        are set.  Walk depth first, visit bottom up.  Only updates nodes
1320        with at least one token index < 0.
1321        """
1322
1323        if self.children is None:
1324            if self.startIndex < 0 or self.stopIndex < 0:
1325                self.startIndex = self.stopIndex = self.token.getTokenIndex()
1326
1327            return
1328 
1329        for child in self.children:
1330            child.setUnknownTokenBoundaries()
1331
1332        if self.startIndex >= 0 and self.stopIndex >= 0:
1333            # already set
1334            return
1335
1336        if self.children:
1337            firstChild = self.children[0]
1338            lastChild = self.children[-1]
1339            self.startIndex = firstChild.getTokenStartIndex()
1340            self.stopIndex = lastChild.getTokenStopIndex()
1341
1342
1343    def getChildIndex(self):
1344        #FIXME: mark as deprecated
1345        return self.childIndex
1346
1347
1348    def setChildIndex(self, idx):
1349        #FIXME: mark as deprecated
1350        self.childIndex = idx
1351
1352
1353    def getParent(self):
1354        #FIXME: mark as deprecated
1355        return self.parent
1356
1357
1358    def setParent(self, t):
1359        #FIXME: mark as deprecated
1360        self.parent = t
1361
1362       
1363    def toString(self):
1364        if self.isNil():
1365            return "nil"
1366
1367        if self.getType() == INVALID_TOKEN_TYPE:
1368            return "<errornode>"
1369
1370        return self.token.text
1371
1372    __str__ = toString   
1373
1374
1375
1376    def toStringTree(self):
1377        if not self.children:
1378            return self.toString()
1379
1380        ret = ''
1381        if not self.isNil():
1382            ret += '(%s ' % (self.toString())
1383       
1384        ret += ' '.join([child.toStringTree() for child in self.children])
1385
1386        if not self.isNil():
1387            ret += ')'
1388
1389        return ret
1390
1391
1392INVALID_NODE = CommonTree(INVALID_TOKEN)
1393
1394
1395class CommonErrorNode(CommonTree):
1396    """A node representing erroneous token range in token stream"""
1397
1398    def __init__(self, input, start, stop, exc):
1399        CommonTree.__init__(self, None)
1400
1401        if (stop is None or
1402            (stop.getTokenIndex() < start.getTokenIndex() and
1403             stop.getType() != EOF
1404             )
1405            ):
1406            # sometimes resync does not consume a token (when LT(1) is
1407            # in follow set.  So, stop will be 1 to left to start. adjust.
1408            # Also handle case where start is the first token and no token
1409            # is consumed during recovery; LT(-1) will return null.
1410            stop = start
1411
1412        self.input = input
1413        self.start = start
1414        self.stop = stop
1415        self.trappedException = exc
1416
1417
1418    def isNil(self):
1419        return False
1420
1421
1422    def getType(self):
1423        return INVALID_TOKEN_TYPE
1424
1425
1426    def getText(self):
1427        if isinstance(self.start, Token):
1428            i = self.start.getTokenIndex()
1429            j = self.stop.getTokenIndex()
1430            if self.stop.getType() == EOF:
1431                j = self.input.size()
1432
1433            badText = self.input.toString(i, j)
1434
1435        elif isinstance(self.start, Tree):
1436            badText = self.input.toString(self.start, self.stop)
1437
1438        else:
1439            # people should subclass if they alter the tree type so this
1440            # next one is for sure correct.
1441            badText = "<unknown>"
1442
1443        return badText
1444
1445
1446    def toString(self):
1447        if isinstance(self.trappedException, MissingTokenException):
1448            return ("<missing type: "
1449                    + str(self.trappedException.getMissingType())
1450                    + ">")
1451
1452        elif isinstance(self.trappedException, UnwantedTokenException):
1453            return ("<extraneous: "
1454                    + str(self.trappedException.getUnexpectedToken())
1455                    + ", resync=" + self.getText() + ">")
1456
1457        elif isinstance(self.trappedException, MismatchedTokenException):
1458            return ("<mismatched token: "
1459                    + str(self.trappedException.token)
1460                    + ", resync=" + self.getText() + ">")
1461
1462        elif isinstance(self.trappedException, NoViableAltException):
1463            return ("<unexpected: "
1464                    + str(self.trappedException.token)
1465                    + ", resync=" + self.getText() + ">")
1466
1467        return "<error: "+self.getText()+">"
1468
1469
1470class CommonTreeAdaptor(BaseTreeAdaptor):
1471    """
1472    @brief A TreeAdaptor that works with any Tree implementation.
1473   
1474    It provides
1475    really just factory methods; all the work is done by BaseTreeAdaptor.
1476    If you would like to have different tokens created than ClassicToken
1477    objects, you need to override this and then set the parser tree adaptor to
1478    use your subclass.
1479
1480    To get your parser to build nodes of a different type, override
1481    create(Token), errorNode(), and to be safe, YourTreeClass.dupNode().
1482    dupNode is called to duplicate nodes during rewrite operations.
1483    """
1484   
1485    def dupNode(self, treeNode):
1486        """
1487        Duplicate a node.  This is part of the factory;
1488        override if you want another kind of node to be built.
1489
1490        I could use reflection to prevent having to override this
1491        but reflection is slow.
1492        """
1493
1494        if treeNode is None:
1495            return None
1496       
1497        return treeNode.dupNode()
1498
1499
1500    def createWithPayload(self, payload):
1501        return CommonTree(payload)
1502
1503
1504    def createToken(self, fromToken=None, tokenType=None, text=None):
1505        """
1506        Tell me how to create a token for use with imaginary token nodes.
1507        For example, there is probably no input symbol associated with imaginary
1508        token DECL, but you need to create it as a payload or whatever for
1509        the DECL node as in ^(DECL type ID).
1510
1511        If you care what the token payload objects' type is, you should
1512        override this method and any other createToken variant.
1513        """
1514       
1515        if fromToken is not None:
1516            return CommonToken(oldToken=fromToken)
1517
1518        return CommonToken(type=tokenType, text=text)
1519
1520
1521    def setTokenBoundaries(self, t, startToken, stopToken):
1522        """
1523        Track start/stop token for subtree root created for a rule.
1524        Only works with Tree nodes.  For rules that match nothing,
1525        seems like this will yield start=i and stop=i-1 in a nil node.
1526        Might be useful info so I'll not force to be i..i.
1527        """
1528       
1529        if t is None:
1530            return
1531
1532        start = 0
1533        stop = 0
1534       
1535        if startToken is not None:
1536            start = startToken.index
1537               
1538        if stopToken is not None:
1539            stop = stopToken.index
1540
1541        t.setTokenStartIndex(start)
1542        t.setTokenStopIndex(stop)
1543
1544
1545    def getTokenStartIndex(self, t):
1546        if t is None:
1547            return -1
1548        return t.getTokenStartIndex()
1549
1550
1551    def getTokenStopIndex(self, t):
1552        if t is None:
1553            return -1
1554        return t.getTokenStopIndex()
1555
1556
1557    def getText(self, t):
1558        if t is None:
1559            return None
1560        return t.getText()
1561
1562
1563    def getType(self, t):
1564        if t is None:
1565            return INVALID_TOKEN_TYPE
1566       
1567        return t.getType()
1568
1569
1570    def getToken(self, t):
1571        """
1572        What is the Token associated with this node?  If
1573        you are not using CommonTree, then you must
1574        override this in your own adaptor.
1575        """
1576
1577        if isinstance(t, CommonTree):
1578            return t.getToken()
1579
1580        return None # no idea what to do
1581
1582
1583    def getChild(self, t, i):
1584        if t is None:
1585            return None
1586        return t.getChild(i)
1587
1588
1589    def getChildCount(self, t):
1590        if t is None:
1591            return 0
1592        return t.getChildCount()
1593
1594
1595    def getParent(self, t):
1596        return t.getParent()
1597
1598
1599    def setParent(self, t, parent):
1600        t.setParent(parent)
1601
1602
1603    def getChildIndex(self, t):
1604        if t is None:
1605            return 0
1606        return t.getChildIndex()
1607
1608
1609    def setChildIndex(self, t, index):
1610        t.setChildIndex(index)
1611
1612
1613    def replaceChildren(self, parent, startChildIndex, stopChildIndex, t):
1614        if parent is not None:
1615            parent.replaceChildren(startChildIndex, stopChildIndex, t)
1616
1617
1618############################################################################
1619#
1620# streams
1621#
1622# TreeNodeStream
1623# \- BaseTree
1624#    \- CommonTree
1625#
1626# TreeAdaptor
1627# \- BaseTreeAdaptor
1628#    \- CommonTreeAdaptor
1629#
1630############################################################################
1631
1632
1633
1634class TreeNodeStream(IntStream):
1635    """@brief A stream of tree nodes
1636
1637    It accessing nodes from a tree of some kind.
1638    """
1639   
1640    # TreeNodeStream is abstract, no need to complain about not implemented
1641    # abstract methods
1642    # pylint: disable-msg=W0223
1643   
1644    def get(self, i):
1645        """Get a tree node at an absolute index i; 0..n-1.
1646        If you don't want to buffer up nodes, then this method makes no
1647        sense for you.
1648        """
1649
1650        raise NotImplementedError
1651
1652
1653    def LT(self, k):
1654        """
1655        Get tree node at current input pointer + i ahead where i=1 is next node.
1656        i<0 indicates nodes in the past.  So LT(-1) is previous node, but
1657        implementations are not required to provide results for k < -1.
1658        LT(0) is undefined.  For i>=n, return null.
1659        Return null for LT(0) and any index that results in an absolute address
1660        that is negative.
1661
1662        This is analogus to the LT() method of the TokenStream, but this
1663        returns a tree node instead of a token.  Makes code gen identical
1664        for both parser and tree grammars. :)
1665        """
1666
1667        raise NotImplementedError
1668
1669
1670    def getTreeSource(self):
1671        """
1672        Where is this stream pulling nodes from?  This is not the name, but
1673        the object that provides node objects.
1674        """
1675
1676        raise NotImplementedError
1677   
1678
1679    def getTokenStream(self):
1680        """
1681        If the tree associated with this stream was created from a TokenStream,
1682        you can specify it here.  Used to do rule $text attribute in tree
1683        parser.  Optional unless you use tree parser rule text attribute
1684        or output=template and rewrite=true options.
1685        """
1686
1687        raise NotImplementedError
1688
1689
1690    def getTreeAdaptor(self):
1691        """
1692        What adaptor can tell me how to interpret/navigate nodes and
1693        trees.  E.g., get text of a node.
1694        """
1695
1696        raise NotImplementedError
1697       
1698
1699    def setUniqueNavigationNodes(self, uniqueNavigationNodes):
1700        """
1701        As we flatten the tree, we use UP, DOWN nodes to represent
1702        the tree structure.  When debugging we need unique nodes
1703        so we have to instantiate new ones.  When doing normal tree
1704        parsing, it's slow and a waste of memory to create unique
1705        navigation nodes.  Default should be false;
1706        """
1707
1708        raise NotImplementedError
1709       
1710
1711    def toString(self, start, stop):
1712        """
1713        Return the text of all nodes from start to stop, inclusive.
1714        If the stream does not buffer all the nodes then it can still
1715        walk recursively from start until stop.  You can always return
1716        null or "" too, but users should not access $ruleLabel.text in
1717        an action of course in that case.
1718        """
1719
1720        raise NotImplementedError
1721
1722
1723    # REWRITING TREES (used by tree parser)
1724    def replaceChildren(self, parent, startChildIndex, stopChildIndex, t):
1725        """
1726        Replace from start to stop child index of parent with t, which might
1727        be a list.  Number of children may be different
1728        after this call.  The stream is notified because it is walking the
1729        tree and might need to know you are monkeying with the underlying
1730        tree.  Also, it might be able to modify the node stream to avoid
1731        restreaming for future phases.
1732
1733        If parent is null, don't do anything; must be at root of overall tree.
1734        Can't replace whatever points to the parent externally.  Do nothing.
1735        """
1736
1737        raise NotImplementedError
1738
1739
1740class CommonTreeNodeStream(TreeNodeStream):
1741    """@brief A buffered stream of tree nodes.
1742
1743    Nodes can be from a tree of ANY kind.
1744
1745    This node stream sucks all nodes out of the tree specified in
1746    the constructor during construction and makes pointers into
1747    the tree using an array of Object pointers. The stream necessarily
1748    includes pointers to DOWN and UP and EOF nodes.
1749
1750    This stream knows how to mark/release for backtracking.
1751
1752    This stream is most suitable for tree interpreters that need to
1753    jump around a lot or for tree parsers requiring speed (at cost of memory).
1754    There is some duplicated functionality here with UnBufferedTreeNodeStream
1755    but just in bookkeeping, not tree walking etc...
1756
1757    @see UnBufferedTreeNodeStream
1758    """
1759   
1760    def __init__(self, *args):
1761        TreeNodeStream.__init__(self)
1762
1763        if len(args) == 1:
1764            adaptor = CommonTreeAdaptor()
1765            tree = args[0]
1766
1767            nodes = None
1768            down = None
1769            up = None
1770            eof = None
1771
1772        elif len(args) == 2:
1773            adaptor = args[0]
1774            tree = args[1]
1775
1776            nodes = None
1777            down = None
1778            up = None
1779            eof = None
1780
1781        elif len(args) == 3:
1782            parent = args[0]
1783            start = args[1]
1784            stop = args[2]
1785
1786            adaptor = parent.adaptor
1787            tree = parent.root
1788
1789            nodes = parent.nodes[start:stop]
1790            down = parent.down
1791            up = parent.up
1792            eof = parent.eof
1793
1794        else:
1795            raise TypeError("Invalid arguments")
1796       
1797        # all these navigation nodes are shared and hence they
1798        # cannot contain any line/column info
1799        if down is not None:
1800            self.down = down
1801        else:
1802            self.down = adaptor.createFromType(DOWN, "DOWN")
1803
1804        if up is not None:
1805            self.up = up
1806        else:
1807            self.up = adaptor.createFromType(UP, "UP")
1808
1809        if eof is not None:
1810            self.eof = eof
1811        else:
1812            self.eof = adaptor.createFromType(EOF, "EOF")
1813
1814        # The complete mapping from stream index to tree node.
1815        # This buffer includes pointers to DOWN, UP, and EOF nodes.
1816        # It is built upon ctor invocation.  The elements are type
1817        #  Object as we don't what the trees look like.
1818
1819        # Load upon first need of the buffer so we can set token types
1820        # of interest for reverseIndexing.  Slows us down a wee bit to
1821        # do all of the if p==-1 testing everywhere though.
1822        if nodes is not None:
1823            self.nodes = nodes
1824        else:
1825            self.nodes = []
1826
1827        # Pull nodes from which tree?
1828        self.root = tree
1829
1830        # IF this tree (root) was created from a token stream, track it.
1831        self.tokens = None
1832
1833        # What tree adaptor was used to build these trees
1834        self.adaptor = adaptor
1835
1836        # Reuse same DOWN, UP navigation nodes unless this is true
1837        self.uniqueNavigationNodes = False
1838
1839        # The index into the nodes list of the current node (next node
1840        # to consume).  If -1, nodes array not filled yet.
1841        self.p = -1
1842
1843        # Track the last mark() call result value for use in rewind().
1844        self.lastMarker = None
1845
1846        # Stack of indexes used for push/pop calls
1847        self.calls = []
1848
1849
1850    def fillBuffer(self):
1851        """Walk tree with depth-first-search and fill nodes buffer.
1852        Don't do DOWN, UP nodes if its a list (t is isNil).
1853        """
1854
1855        self._fillBuffer(self.root)
1856        self.p = 0 # buffer of nodes intialized now
1857
1858
1859    def _fillBuffer(self, t):
1860        nil = self.adaptor.isNil(t)
1861       
1862        if not nil:
1863            self.nodes.append(t) # add this node
1864
1865        # add DOWN node if t has children
1866        n = self.adaptor.getChildCount(t)
1867        if not nil and n > 0:
1868            self.addNavigationNode(DOWN)
1869
1870        # and now add all its children
1871        for c in range(n):
1872            self._fillBuffer(self.adaptor.getChild(t, c))
1873
1874        # add UP node if t has children
1875        if not nil and n > 0:
1876            self.addNavigationNode(UP)
1877
1878
1879    def getNodeIndex(self, node):
1880        """What is the stream index for node? 0..n-1
1881        Return -1 if node not found.
1882        """
1883       
1884        if self.p == -1:
1885            self.fillBuffer()
1886
1887        for i, t in enumerate(self.nodes):
1888            if t == node:
1889                return i
1890
1891        return -1
1892
1893
1894    def addNavigationNode(self, ttype):
1895        """
1896        As we flatten the tree, we use UP, DOWN nodes to represent
1897        the tree structure.  When debugging we need unique nodes
1898        so instantiate new ones when uniqueNavigationNodes is true.
1899        """
1900       
1901        navNode = None
1902       
1903        if ttype == DOWN:
1904            if self.hasUniqueNavigationNodes():
1905                navNode = self.adaptor.createFromType(DOWN, "DOWN")
1906
1907            else:
1908                navNode = self.down
1909
1910        else:
1911            if self.hasUniqueNavigationNodes():
1912                navNode = self.adaptor.createFromType(UP, "UP")
1913               
1914            else:
1915                navNode = self.up
1916
1917        self.nodes.append(navNode)
1918
1919
1920    def get(self, i):
1921        if self.p == -1:
1922            self.fillBuffer()
1923
1924        return self.nodes[i]
1925
1926
1927    def LT(self, k):
1928        if self.p == -1:
1929            self.fillBuffer()
1930
1931        if k == 0:
1932            return None
1933
1934        if k < 0:
1935            return self.LB(-k)
1936
1937        if self.p + k - 1 >= len(self.nodes):
1938            return self.eof
1939
1940        return self.nodes[self.p + k - 1]
1941   
1942
1943    def getCurrentSymbol(self):
1944        return self.LT(1)
1945
1946
1947    def LB(self, k):
1948        """Look backwards k nodes"""
1949       
1950        if k == 0:
1951            return None
1952
1953        if self.p - k < 0:
1954            return None
1955
1956        return self.nodes[self.p - k]
1957
1958
1959    def getTreeSource(self):
1960        return self.root
1961
1962
1963    def getSourceName(self):
1964        return self.getTokenStream().getSourceName()
1965
1966
1967    def getTokenStream(self):
1968        return self.tokens
1969
1970
1971    def setTokenStream(self, tokens):
1972        self.tokens = tokens
1973
1974
1975    def getTreeAdaptor(self):
1976        return self.adaptor
1977
1978
1979    def hasUniqueNavigationNodes(self):
1980        return self.uniqueNavigationNodes
1981
1982
1983    def setUniqueNavigationNodes(self, uniqueNavigationNodes):
1984        self.uniqueNavigationNodes = uniqueNavigationNodes
1985
1986
1987    def consume(self):
1988        if self.p == -1:
1989            self.fillBuffer()
1990           
1991        self.p += 1
1992
1993       
1994    def LA(self, i):
1995        return self.adaptor.getType(self.LT(i))
1996
1997
1998    def mark(self):
1999        if self.p == -1:
2000            self.fillBuffer()
2001
2002       
2003        self.lastMarker = self.index()
2004        return self.lastMarker
2005
2006
2007    def release(self, marker=None):
2008        # no resources to release
2009
2010        pass
2011
2012
2013    def index(self):
2014        return self.p
2015
2016
2017    def rewind(self, marker=None):
2018        if marker is None:
2019            marker = self.lastMarker
2020           
2021        self.seek(marker)
2022
2023
2024    def seek(self, index):
2025        if self.p == -1:
2026            self.fillBuffer()
2027
2028        self.p = index
2029
2030
2031    def push(self, index):
2032        """
2033        Make stream jump to a new location, saving old location.
2034        Switch back with pop().
2035        """
2036
2037        self.calls.append(self.p) # save current index
2038        self.seek(index)
2039
2040
2041    def pop(self):
2042        """
2043        Seek back to previous index saved during last push() call.
2044        Return top of stack (return index).
2045        """
2046
2047        ret = self.calls.pop(-1)
2048        self.seek(ret)
2049        return ret
2050
2051
2052    def reset(self):
2053        self.p = 0
2054        self.lastMarker = 0
2055        self.calls = []
2056
2057       
2058    def size(self):
2059        if self.p == -1:
2060            self.fillBuffer()
2061
2062        return len(self.nodes)
2063
2064
2065    # TREE REWRITE INTERFACE
2066
2067    def replaceChildren(self, parent, startChildIndex, stopChildIndex, t):
2068        if parent is not None:
2069            self.adaptor.replaceChildren(
2070                parent, startChildIndex, stopChildIndex, t
2071                )
2072
2073
2074    def __str__(self):
2075        """Used for testing, just return the token type stream"""
2076
2077        if self.p == -1:
2078            self.fillBuffer()
2079
2080        return ' '.join([str(self.adaptor.getType(node))
2081                         for node in self.nodes
2082                         ])
2083
2084
2085    def toString(self, start, stop):
2086        if start is None or stop is None:
2087            return None
2088
2089        if self.p == -1:
2090            self.fillBuffer()
2091
2092        #System.out.println("stop: "+stop);
2093        #if ( start instanceof CommonTree )
2094        #    System.out.print("toString: "+((CommonTree)start).getToken()+", ");
2095        #else
2096        #    System.out.println(start);
2097        #if ( stop instanceof CommonTree )
2098        #    System.out.println(((CommonTree)stop).getToken());
2099        #else
2100        #    System.out.println(stop);
2101           
2102        # if we have the token stream, use that to dump text in order
2103        if self.tokens is not None:
2104            beginTokenIndex = self.adaptor.getTokenStartIndex(start)
2105            endTokenIndex = self.adaptor.getTokenStopIndex(stop)
2106           
2107            # if it's a tree, use start/stop index from start node
2108            # else use token range from start/stop nodes
2109            if self.adaptor.getType(stop) == UP:
2110                endTokenIndex = self.adaptor.getTokenStopIndex(start)
2111
2112            elif self.adaptor.getType(stop) == EOF:
2113                endTokenIndex = self.size() -2 # don't use EOF
2114
2115            return self.tokens.toString(beginTokenIndex, endTokenIndex)
2116
2117        # walk nodes looking for start
2118        i, t = 0, None
2119        for i, t in enumerate(self.nodes):
2120            if t == start:
2121                break
2122
2123        # now walk until we see stop, filling string buffer with text
2124        buf = []
2125        t = self.nodes[i]
2126        while t != stop:
2127            text = self.adaptor.getText(t)
2128            if text is None:
2129                text = " " + self.adaptor.getType(t)
2130
2131            buf.append(text)
2132            i += 1
2133            t = self.nodes[i]
2134
2135        # include stop node too
2136        text = self.adaptor.getText(stop)
2137        if text is None:
2138            text = " " +self.adaptor.getType(stop)
2139
2140        buf.append(text)
2141       
2142        return ''.join(buf)
2143   
2144
2145    ## iterator interface
2146    def __iter__(self):
2147        if self.p == -1:
2148            self.fillBuffer()
2149
2150        for node in self.nodes:
2151            yield node
2152
2153
2154#############################################################################
2155#
2156# tree parser
2157#
2158#############################################################################
2159
2160class TreeParser(BaseRecognizer):
2161    """@brief Baseclass for generated tree parsers.
2162   
2163    A parser for a stream of tree nodes.  "tree grammars" result in a subclass
2164    of this.  All the error reporting and recovery is shared with Parser via
2165    the BaseRecognizer superclass.
2166    """
2167
2168    def __init__(self, input, state=None):
2169        BaseRecognizer.__init__(self, state)
2170
2171        self.input = None
2172        self.setTreeNodeStream(input)
2173
2174
2175    def reset(self):
2176        BaseRecognizer.reset(self) # reset all recognizer state variables
2177        if self.input is not None:
2178            self.input.seek(0) # rewind the input
2179
2180
2181    def setTreeNodeStream(self, input):
2182        """Set the input stream"""
2183
2184        self.input = input
2185
2186
2187    def getTreeNodeStream(self):
2188        return self.input
2189
2190
2191    def getSourceName(self):
2192        return self.input.getSourceName()
2193
2194
2195    def getCurrentInputSymbol(self, input):
2196        return input.LT(1)
2197
2198
2199    def getMissingSymbol(self, input, e, expectedTokenType, follow):
2200        tokenText = "<missing " + self.tokenNames[expectedTokenType] + ">"
2201        return CommonTree(CommonToken(type=expectedTokenType, text=tokenText))
2202
2203
2204    # precompiled regex used by inContext
2205    dotdot = ".*[^.]\\.\\.[^.].*"
2206    doubleEtc = ".*\\.\\.\\.\\s+\\.\\.\\..*"
2207    dotdotPattern = re.compile(dotdot)
2208    doubleEtcPattern = re.compile(doubleEtc)
2209
2210    def inContext(self, context, adaptor=None, tokenName=None, t=None):
2211        """Check if current node in input has a context.
2212
2213        Context means sequence of nodes towards root of tree.  For example,
2214        you might say context is "MULT" which means my parent must be MULT.
2215        "CLASS VARDEF" says current node must be child of a VARDEF and whose
2216        parent is a CLASS node.  You can use "..." to mean zero-or-more nodes.
2217        "METHOD ... VARDEF" means my parent is VARDEF and somewhere above
2218        that is a METHOD node.  The first node in the context is not
2219        necessarily the root.  The context matcher stops matching and returns
2220        true when it runs out of context.  There is no way to force the first
2221        node to be the root.
2222        """
2223
2224        return _inContext(
2225            self.input.getTreeAdaptor(), self.getTokenNames(), 
2226            self.input.LT(1), context)
2227
2228    @classmethod
2229    def _inContext(cls, adaptor, tokenNames, t, context):
2230        """The worker for inContext.
2231
2232        It's static and full of parameters for testing purposes.
2233        """
2234
2235        if cls.dotdotPattern.match(context):
2236            # don't allow "..", must be "..."
2237            raise ValueError("invalid syntax: ..")
2238
2239        if cls.doubleEtcPattern.match(context):
2240            # don't allow double "..."
2241            raise ValueError("invalid syntax: ... ...")
2242
2243        # ensure spaces around ...
2244        context = context.replace("...", " ... ")
2245        context = context.strip()
2246        nodes = context.split()
2247
2248        ni = len(nodes) - 1
2249        t = adaptor.getParent(t)
2250        while ni >= 0 and t is not None:
2251            if nodes[ni] == "...":
2252                # walk upwards until we see nodes[ni-1] then continue walking
2253                if ni == 0:
2254                    # ... at start is no-op
2255                    return True
2256                goal = nodes[ni-1]
2257                ancestor = cls._getAncestor(adaptor, tokenNames, t, goal)
2258                if ancestor is None:
2259                    return False
2260                t = ancestor
2261                ni -= 1
2262
2263            name = tokenNames[adaptor.getType(t)]
2264            if name != nodes[ni]:
2265                return False
2266
2267            # advance to parent and to previous element in context node list
2268            ni -= 1
2269            t = adaptor.getParent(t)
2270
2271        # at root but more nodes to match
2272        if t is None and ni >= 0:
2273            return False
2274
2275        return True
2276
2277    @staticmethod
2278    def _getAncestor(adaptor, tokenNames, t, goal):
2279        """Helper for static inContext."""
2280        while t is not None:
2281            name = tokenNames[adaptor.getType(t)]
2282            if name == goal:
2283                return t
2284            t = adaptor.getParent(t)
2285
2286        return None
2287
2288
2289    def matchAny(self, ignore): # ignore stream, copy of this.input
2290        """
2291        Match '.' in tree parser has special meaning.  Skip node or
2292        entire tree if node has children.  If children, scan until
2293        corresponding UP node.
2294        """
2295       
2296        self._state.errorRecovery = False
2297
2298        look = self.input.LT(1)
2299        if self.input.getTreeAdaptor().getChildCount(look) == 0:
2300            self.input.consume() # not subtree, consume 1 node and return
2301            return
2302
2303        # current node is a subtree, skip to corresponding UP.
2304        # must count nesting level to get right UP
2305        level = 0
2306        tokenType = self.input.getTreeAdaptor().getType(look)
2307        while tokenType != EOF and not (tokenType == UP and level==0):
2308            self.input.consume()
2309            look = self.input.LT(1)
2310            tokenType = self.input.getTreeAdaptor().getType(look)
2311            if tokenType == DOWN:
2312                level += 1
2313
2314            elif tokenType == UP:
2315                level -= 1
2316
2317        self.input.consume() # consume UP
2318
2319
2320    def mismatch(self, input, ttype, follow):
2321        """
2322        We have DOWN/UP nodes in the stream that have no line info; override.
2323        plus we want to alter the exception type. Don't try to recover
2324        from tree parser errors inline...
2325        """
2326
2327        raise MismatchedTreeNodeException(ttype, input)
2328
2329
2330    def getErrorHeader(self, e):
2331        """
2332        Prefix error message with the grammar name because message is
2333        always intended for the programmer because the parser built
2334        the input tree not the user.
2335        """
2336
2337        return (self.getGrammarFileName() +
2338                ": node from %sline %s:%s"
2339                % (['', "after "][e.approximateLineInfo],
2340                   e.line,
2341                   e.charPositionInLine
2342                   )
2343                )
2344
2345    def getErrorMessage(self, e, tokenNames):
2346        """
2347        Tree parsers parse nodes they usually have a token object as
2348        payload. Set the exception token and do the default behavior.
2349        """
2350
2351        if isinstance(self, TreeParser):
2352            adaptor = e.input.getTreeAdaptor()
2353            e.token = adaptor.getToken(e.node)
2354            if e.token is not None: # could be an UP/DOWN node
2355                e.token = CommonToken(
2356                    type=adaptor.getType(e.node),
2357                    text=adaptor.getText(e.node)
2358                    )
2359
2360        return BaseRecognizer.getErrorMessage(self, e, tokenNames)
2361
2362
2363    def traceIn(self, ruleName, ruleIndex):
2364        BaseRecognizer.traceIn(self, ruleName, ruleIndex, self.input.LT(1))
2365
2366
2367    def traceOut(self, ruleName, ruleIndex):
2368        BaseRecognizer.traceOut(self, ruleName, ruleIndex, self.input.LT(1))
2369
2370
2371#############################################################################
2372#
2373# tree visitor
2374#
2375#############################################################################
2376
2377class TreeVisitor(object):
2378    """Do a depth first walk of a tree, applying pre() and post() actions
2379    we go.
2380    """
2381
2382    def __init__(self, adaptor=None):
2383        if adaptor is not None:
2384            self.adaptor = adaptor
2385        else:
2386            self.adaptor = CommonTreeAdaptor()
2387   
2388    def visit(self, t, pre_action=None, post_action=None):
2389        """Visit every node in tree t and trigger an action for each node
2390        before/after having visited all of its children.  Bottom up walk.
2391        Execute both actions even if t has no children.  Ignore return
2392        results from transforming children since they will have altered
2393        the child list of this node (their parent).  Return result of
2394        applying post action to this node.
2395
2396        The Python version differs from the Java version by taking two
2397        callables 'pre_action' and 'post_action' instead of a class instance
2398        that wraps those methods. Those callables must accept a TreeNode as
2399        their single argument and return the (potentially transformed or
2400        replaced) TreeNode.
2401        """
2402
2403        isNil = self.adaptor.isNil(t)
2404        if pre_action is not None and not isNil:
2405            # if rewritten, walk children of new t
2406            t = pre_action(t)
2407
2408        for idx in xrange(self.adaptor.getChildCount(t)):
2409            child = self.adaptor.getChild(t, idx)
2410            self.visit(child, pre_action, post_action)
2411
2412        if post_action is not None and not isNil:
2413            t = post_action(t)
2414
2415        return t
2416
2417
2418#############################################################################
2419#
2420# streams for rule rewriting
2421#
2422#############################################################################
2423
2424class RewriteRuleElementStream(object):
2425    """@brief Internal helper class.
2426   
2427    A generic list of elements tracked in an alternative to be used in
2428    a -> rewrite rule.  We need to subclass to fill in the next() method,
2429    which returns either an AST node wrapped around a token payload or
2430    an existing subtree.
2431
2432    Once you start next()ing, do not try to add more elements.  It will
2433    break the cursor tracking I believe.
2434
2435    @see org.antlr.runtime.tree.RewriteRuleSubtreeStream
2436    @see org.antlr.runtime.tree.RewriteRuleTokenStream
2437   
2438    TODO: add mechanism to detect/puke on modification after reading from
2439    stream
2440    """
2441
2442    def __init__(self, adaptor, elementDescription, elements=None):
2443        # Cursor 0..n-1.  If singleElement!=null, cursor is 0 until you next(),
2444        # which bumps it to 1 meaning no more elements.
2445        self.cursor = 0
2446
2447        # Track single elements w/o creating a list.  Upon 2nd add, alloc list
2448        self.singleElement = None
2449
2450        # The list of tokens or subtrees we are tracking
2451        self.elements = None
2452
2453        # Once a node / subtree has been used in a stream, it must be dup'd
2454        # from then on.  Streams are reset after subrules so that the streams
2455        # can be reused in future subrules.  So, reset must set a dirty bit.
2456        # If dirty, then next() always returns a dup.
2457        self.dirty = False
2458       
2459        # The element or stream description; usually has name of the token or
2460        # rule reference that this list tracks.  Can include rulename too, but
2461        # the exception would track that info.
2462        self.elementDescription = elementDescription
2463
2464        self.adaptor = adaptor
2465
2466        if isinstance(elements, (list, tuple)):
2467            # Create a stream, but feed off an existing list
2468            self.singleElement = None
2469            self.elements = elements
2470
2471        else:
2472            # Create a stream with one element
2473            self.add(elements)
2474
2475
2476    def reset(self):
2477        """
2478        Reset the condition of this stream so that it appears we have
2479        not consumed any of its elements.  Elements themselves are untouched.
2480        Once we reset the stream, any future use will need duplicates.  Set
2481        the dirty bit.
2482        """
2483       
2484        self.cursor = 0
2485        self.dirty = True
2486
2487       
2488    def add(self, el):
2489        if el is None:
2490            return
2491
2492        if self.elements is not None: # if in list, just add
2493            self.elements.append(el)
2494            return
2495
2496        if self.singleElement is None: # no elements yet, track w/o list
2497            self.singleElement = el
2498            return
2499
2500        # adding 2nd element, move to list
2501        self.elements = []
2502        self.elements.append(self.singleElement)
2503        self.singleElement = None
2504        self.elements.append(el)
2505
2506
2507    def nextTree(self):
2508        """
2509        Return the next element in the stream.  If out of elements, throw
2510        an exception unless size()==1.  If size is 1, then return elements[0].
2511       
2512        Return a duplicate node/subtree if stream is out of elements and
2513        size==1. If we've already used the element, dup (dirty bit set).
2514        """
2515       
2516        if (self.dirty
2517            or (self.cursor >= len(self) and len(self) == 1)
2518            ):
2519            # if out of elements and size is 1, dup
2520            el = self._next()
2521            return self.dup(el)
2522
2523        # test size above then fetch
2524        el = self._next()
2525        return el
2526
2527
2528    def _next(self):
2529        """
2530        do the work of getting the next element, making sure that it's
2531        a tree node or subtree.  Deal with the optimization of single-
2532        element list versus list of size > 1.  Throw an exception
2533        if the stream is empty or we're out of elements and size>1.
2534        protected so you can override in a subclass if necessary.
2535        """
2536
2537        if len(self) == 0:
2538            raise RewriteEmptyStreamException(self.elementDescription)
2539           
2540        if self.cursor >= len(self): # out of elements?
2541            if len(self) == 1: # if size is 1, it's ok; return and we'll dup
2542                return self.toTree(self.singleElement)
2543
2544            # out of elements and size was not 1, so we can't dup
2545            raise RewriteCardinalityException(self.elementDescription)
2546
2547        # we have elements
2548        if self.singleElement is not None:
2549            self.cursor += 1 # move cursor even for single element list
2550            return self.toTree(self.singleElement)
2551
2552        # must have more than one in list, pull from elements
2553        o = self.toTree(self.elements[self.cursor])
2554        self.cursor += 1
2555        return o
2556
2557
2558    def dup(self, el):
2559        """
2560        When constructing trees, sometimes we need to dup a token or AST
2561        subtree.  Dup'ing a token means just creating another AST node
2562        around it.  For trees, you must call the adaptor.dupTree() unless
2563        the element is for a tree root; then it must be a node dup.
2564        """
2565
2566        raise NotImplementedError
2567   
2568
2569    def toTree(self, el):
2570        """
2571        Ensure stream emits trees; tokens must be converted to AST nodes.
2572        AST nodes can be passed through unmolested.
2573        """
2574
2575        return el
2576
2577
2578    def hasNext(self):
2579        return ( (self.singleElement is not None and self.cursor < 1)
2580                 or (self.elements is not None
2581                     and self.cursor < len(self.elements)
2582                     )
2583                 )
2584
2585                 
2586    def size(self):
2587        if self.singleElement is not None:
2588            return 1
2589
2590        if self.elements is not None:
2591            return len(self.elements)
2592
2593        return 0
2594
2595    __len__ = size
2596   
2597
2598    def getDescription(self):
2599        """Deprecated. Directly access elementDescription attribute"""
2600       
2601        return self.elementDescription
2602
2603
2604class RewriteRuleTokenStream(RewriteRuleElementStream):
2605    """@brief Internal helper class."""
2606
2607    def toTree(self, el):
2608        # Don't convert to a tree unless they explicitly call nextTree.
2609        # This way we can do hetero tree nodes in rewrite.
2610        return el
2611
2612
2613    def nextNode(self):
2614        t = self._next()
2615        return self.adaptor.createWithPayload(t)
2616
2617   
2618    def nextToken(self):
2619        return self._next()
2620
2621   
2622    def dup(self, el):
2623        raise TypeError("dup can't be called for a token stream.")
2624
2625
2626class RewriteRuleSubtreeStream(RewriteRuleElementStream):
2627    """@brief Internal helper class."""
2628
2629    def nextNode(self):
2630        """
2631        Treat next element as a single node even if it's a subtree.
2632        This is used instead of next() when the result has to be a
2633        tree root node.  Also prevents us from duplicating recently-added
2634        children; e.g., ^(type ID)+ adds ID to type and then 2nd iteration
2635        must dup the type node, but ID has been added.
2636
2637        Referencing a rule result twice is ok; dup entire tree as
2638        we can't be adding trees as root; e.g., expr expr.
2639
2640        Hideous code duplication here with super.next().  Can't think of
2641        a proper way to refactor.  This needs to always call dup node
2642        and super.next() doesn't know which to call: dup node or dup tree.
2643        """
2644       
2645        if (self.dirty
2646            or (self.cursor >= len(self) and len(self) == 1)
2647            ):
2648            # if out of elements and size is 1, dup (at most a single node
2649            # since this is for making root nodes).
2650            el = self._next()
2651            return self.adaptor.dupNode(el)
2652
2653        # test size above then fetch
2654        el = self._next()
2655        return el
2656
2657
2658    def dup(self, el):
2659        return self.adaptor.dupTree(el)
2660
2661
2662
2663class RewriteRuleNodeStream(RewriteRuleElementStream):
2664    """
2665    Queues up nodes matched on left side of -> in a tree parser. This is
2666    the analog of RewriteRuleTokenStream for normal parsers.
2667    """
2668   
2669    def nextNode(self):
2670        return self._next()
2671
2672
2673    def toTree(self, el):
2674        return self.adaptor.dupNode(el)
2675
2676
2677    def dup(self, el):
2678        # we dup every node, so don't have to worry about calling dup; short-
2679        #circuited next() so it doesn't call.
2680        raise TypeError("dup can't be called for a node stream.")
2681
2682
2683class TreeRuleReturnScope(RuleReturnScope):
2684    """
2685    This is identical to the ParserRuleReturnScope except that
2686    the start property is a tree nodes not Token object
2687    when you are parsing trees.  To be generic the tree node types
2688    have to be Object.
2689    """
2690
2691    def __init__(self):
2692        self.start = None
2693        self.tree = None
2694       
2695   
2696    def getStart(self):
2697        return self.start
2698
2699   
2700    def getTree(self):
2701        return self.tree
2702
Note: See TracBrowser for help on using the repository browser.