"""ANTLR3 runtime package"""

# begin[licence]
#
# [The "BSD licence"]
# Copyright (c) 2005-2006 Terence Parr
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in the
#    documentation and/or other materials provided with the distribution.
# 3. The name of the author may not be used to endorse or promote products
#    derived from this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
# IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
# end[licensc]

import sys
from antlrExceptions import RecognitionException, MismatchedTokenException, \
     MismatchedRangeException, MismatchedTreeNodeException, \
     NoViableAltException, EarlyExitException, MismatchedSetException, \
     MismatchedNotSetException, FailedPredicateException

EOF = -1

## All tokens go to the parser (unless skip() is called in that rule)
# on a particular "channel".  The parser tunes to a particular channel
# so that whitespace etc... can go to the parser on a "hidden" channel.
DEFAULT_CHANNEL = 0

## Anything on different channel than DEFAULT_CHANNEL is not parsed
# by parser.
HIDDEN_CHANNEL = 99

# Predefined token types
EOR_TOKEN_TYPE = 1

##
# imaginary tree navigation type; traverse "get child" link
DOWN = 2
##
#imaginary tree navigation type; finish with a child list
UP = 3

MIN_TOKEN_TYPE = UP+1

INVALID_TOKEN_TYPE = 0
"""---------------------------------------------------------------"""
"""ORANGESCAPE CHANGE 1: COMPAT.PY"""

try:
    set = set
    frozenset = frozenset
except NameError:
    from sets import Set as set, ImmutableSet as frozenset


try:
    reversed = reversed
except NameError:
    def reversed(l):
        l = l[:]
        l.reverse()
        return l


class Token(object):
    """@brief Abstract token baseclass."""

    def getText(self):
        """@brief Get the text of the token.

        Using setter/getter methods is deprecated. Use o.text instead.
        """
        raise NotImplementedError

    def setText(self, text):
        """@brief Set the text of the token.

        Using setter/getter methods is deprecated. Use o.text instead.
        """
        raise NotImplementedError


    def getType(self):
        """@brief Get the type of the token.

        Using setter/getter methods is deprecated. Use o.type instead."""

        raise NotImplementedError

    def setType(self, ttype):
        """@brief Get the type of the token.

        Using setter/getter methods is deprecated. Use o.type instead."""

        raise NotImplementedError


    def getLine(self):
        """@brief Get the line number on which this token was matched

        Lines are numbered 1..n

        Using setter/getter methods is deprecated. Use o.line instead."""

        raise NotImplementedError

    def setLine(self, line):
        """@brief Set the line number on which this token was matched

        Using setter/getter methods is deprecated. Use o.line instead."""

        raise NotImplementedError


    def getCharPositionInLine(self):
        """@brief Get the column of the tokens first character,

        Columns are numbered 0..n-1

        Using setter/getter methods is deprecated. Use o.charPositionInLine instead."""

        raise NotImplementedError

    def setCharPositionInLine(self, pos):
        """@brief Set the column of the tokens first character,

        Using setter/getter methods is deprecated. Use o.charPositionInLine instead."""

        raise NotImplementedError


    def getChannel(self):
        """@brief Get the channel of the token

        Using setter/getter methods is deprecated. Use o.channel instead."""

        raise NotImplementedError

    def setChannel(self, channel):
        """@brief Set the channel of the token

        Using setter/getter methods is deprecated. Use o.channel instead."""

        raise NotImplementedError



    def getTokenIndex(self):
        """@brief Get the index in the input stream.

        An index from 0..n-1 of the token object in the input stream.
        This must be valid in order to use the ANTLRWorks debugger.

        Using setter/getter methods is deprecated. Use o.index instead."""

        raise NotImplementedError

    def setTokenIndex(self, index):
        """@brief Set the index in the input stream.

        Using setter/getter methods is deprecated. Use o.index instead."""

        raise NotImplementedError


"""---------------------------------------------------------------"""
"""ORANGESCAPE CHANGE 2: TOKENS.PY"""

############################################################################
#
# token implementations
#
# Token
# +- CommonToken
# \- ClassicToken
#
############################################################################

class CommonToken(Token):
    """@brief Basic token implementation.

    This implementation does not copy the text from the input stream upon
    creation, but keeps start/stop pointers into the stream to avoid
    unnecessary copy operations.

    """

    def __init__(self, type=None, channel=DEFAULT_CHANNEL, text=None,
                 input=None, start=None, stop=None, oldToken=None):
        Token.__init__(self)

        if oldToken is not None:
            self.type = oldToken.type
            self.line = oldToken.line
            self.charPositionInLine = oldToken.charPositionInLine
            self.channel = oldToken.channel
            self.index = oldToken.index
            self._text = oldToken._text
            self.input = oldToken.input
            self.start = oldToken.start
            self.stop = oldToken.stop

        else:
            self.type = type
            self.input = input
            self.charPositionInLine = -1 # set to invalid position
            self.line = 0
            self.channel = channel

        #What token number is this from 0..n-1 tokens; < 0 implies invalid index
            self.index = -1

            # We need to be able to change the text once in a while.  If
            # this is non-null, then getText should return this.  Note that
            # start/stop are not affected by changing this.
            self._text = text

            # The char position into the input buffer where this token starts
            self.start = start

            # The char position into the input buffer where this token stops
            # This is the index of the last char, *not* the index after it!
            self.stop = stop


    def getText(self):
        if self._text is not None:
            return self._text

        if self.input is None:
            return None

        return self.input.substring(self.start, self.stop)


    def setText(self, text):
        """
        Override the text for this token.  getText() will return this text
        rather than pulling from the buffer.  Note that this does not mean
        that start/stop indexes are not valid.  It means that that input
        was converted to a new string in the token object.
    """
        self._text = text

    text = property(getText, setText)


    def getType(self):
        return self.type

    def setType(self, ttype):
        self.type = ttype


    def getLine(self):
        return self.line

    def setLine(self, line):
        self.line = line


    def getCharPositionInLine(self):
        return self.charPositionInLine

    def setCharPositionInLine(self, pos):
        self.charPositionInLine = pos


    def getChannel(self):
        return self.channel

    def setChannel(self, channel):
        self.channel = channel


    def getTokenIndex(self):
        return self.index

    def setTokenIndex(self, index):
        self.index = index


    def __str__(self):
        channelStr = ""
        if self.channel > 0:
            channelStr = ",channel=" + str(self.channel)

        txt = self.text
        if txt is not None:
            txt = txt.replace("\n","\\\\n")
            txt = txt.replace("\r","\\\\r")
            txt = txt.replace("\t","\\\\t")
        else:
            txt = "<no text>"

        return "[@%s,%s:%s=%r,<%s>%s,%s:%s]" % (
            self.index,
            self.start, self.stop,
            txt,
            self.type, channelStr,
            self.line, self.charPositionInLine
            )


class ClassicToken(Token):
    """@brief Alternative token implementation.

    A Token object like we'd use in ANTLR 2.x; has an actual string created
    and associated with this object.  These objects are needed for imaginary
    tree nodes that have payload objects.  We need to create a Token object
    that has a string; the tree node will point at this token.  CommonToken
    has indexes into a char stream and hence cannot be used to introduce
    new strings.
    """

    def __init__(self, type=None, text=None, channel=DEFAULT_CHANNEL,
                 oldToken=None
                 ):
        Token.__init__(self)

        if oldToken is not None:
            self.text = oldToken.text
            self.type = oldToken.type
            self.line = oldToken.line
            self.charPositionInLine = oldToken.charPositionInLine
            self.channel = oldToken.channel

        self.text = text
        self.type = type
        self.line = None
        self.charPositionInLine = None
        self.channel = channel
        self.index = None


    def getText(self):
        return self.text

    def setText(self, text):
        self.text = text


    def getType(self):
        return self.type

    def setType(self, ttype):
        self.type = ttype


    def getLine(self):
        return self.line

    def setLine(self, line):
        self.line = line


    def getCharPositionInLine(self):
        return self.charPositionInLine

    def setCharPositionInLine(self, pos):
        self.charPositionInLine = pos


    def getChannel(self):
        return self.channel

    def setChannel(self, channel):
        self.channel = channel


    def getTokenIndex(self):
        return self.index

    def setTokenIndex(self, index):
        self.index = index


    def toString(self):
        channelStr = ""
        if self.channel > 0:
            channelStr = ",channel=" + str(self.channel)

        txt = self.text
        if txt is None:
            txt = "<no text>"

        return "[@%r,%r,<%r>%s,%r:%r]" % (self.index,
                                          txt,
                                          self.type,
                                          channelStr,
                                          self.line,
                                          self.charPositionInLine
                                          )


    __str__ = toString
    __repr__ = toString



EOF_TOKEN = CommonToken(type=EOF)

INVALID_TOKEN = CommonToken(type=INVALID_TOKEN_TYPE)

# In an action, a lexer rule can set token to this SKIP_TOKEN and ANTLR
# will avoid creating a token for this symbol and try to fetch another.
SKIP_TOKEN = CommonToken(type=INVALID_TOKEN_TYPE)



"""------------------CHANGE 1 END-----------------------------------"""


"""---------------------------------------------------------------"""
"""ORANGESCAPE CHANGE 2: COMPAT.PY"""

class DFA(object):
    """@brief A DFA implemented as a set of transition tables.

    Any state that has a semantic predicate edge is special; those states
    are generated with if-then-else structures in a specialStateTransition()
    which is generated by cyclicDFA template.

    """

    def __init__(
        self,
        recognizer, decisionNumber,
        eot, eof, min, max, accept, special, transition
        ):
        ## Which recognizer encloses this DFA?  Needed to check backtracking
        self.recognizer = recognizer

        self.decisionNumber = decisionNumber
        self.eot = eot
        self.eof = eof
        self.min = min
        self.max = max
        self.accept = accept
        self.special = special
        self.transition = transition


    def predict(self, input):
        """
        From the input stream, predict what alternative will succeed
	using this DFA (representing the covering regular approximation
	to the underlying CFL).  Return an alternative number 1..n.  Throw
	 an exception upon error.
	"""
        mark = input.mark()
        s = 0 # we always start at s0
        try:
            for _ in xrange(50000):
                #print "***Current state = %d" % s

                specialState = self.special[s]
                if specialState >= 0:
                    #print "is special"
                    s = self.specialStateTransition(specialState, input)
                    input.consume()
                    continue

                if self.accept[s] >= 1:
                    #print "accept state for alt %d" % self.accept[s]
                    return self.accept[s]

                # look for a normal char transition
                LA = input.LA(1)
                #print LA, repr(input.LT(1)), input.LT(1).text
                if LA == EOF:
                    c = -1 #0xffff
                else:
                    try:
                        c = ord(LA)
                    except TypeError:
                        # LA is a token type (int), not a char
                        c = LA

                #print "LA = %d (%r)" % (c, unichr(c))
                #print "range = %d..%d" % (self.min[s], self.max[s])

                if c >= self.min[s] and c <= self.max[s]:
                    # move to next state
                    snext = self.transition[s][c-self.min[s]]
                    #print "in range, next state = %d" % snext

                    if snext < 0:
                        #print "not a normal transition"
                        # was in range but not a normal transition
                        # must check EOT, which is like the else clause.
                        # eot[s]>=0 indicates that an EOT edge goes to another
                        # state.
                        if self.eot[s] >= 0: # EOT Transition to accept state?
                            #print "EOT trans to accept state %d" % self.eot[s]

                            s = self.eot[s]
                            input.consume()
                            # TODO: I had this as return accept[eot[s]]
                            # which assumed here that the EOT edge always
                            # went to an accept...faster to do this, but
                            # what about predicated edges coming from EOT
                            # target?
                            continue

                        #print "no viable alt"
                        self.noViableAlt(s, input)
                        return 0

                    s = snext
                    input.consume()
                    continue

                if self.eot[s] >= 0:
                    #print "EOT to %d" % self.eot[s]

                    s = self.eot[s]
                    input.consume()
                    continue

                # EOF Transition to accept state?
                if c == EOF and self.eof[s] >= 0:
                    #print "EOF Transition to accept state %d" \
                    #  % self.accept[self.eof[s]]
                    return self.accept[self.eof[s]]

                # not in range and not EOF/EOT, must be invalid symbol
                self.noViableAlt(s, input)
                return 0

            else:
                raise RuntimeError("DFA bang!")

        finally:
            input.rewind(mark)


    def noViableAlt(self, s, input):
        if self.recognizer.backtracking > 0:
            self.recognizer.failed = True
            return

        nvae = NoViableAltException(
            self.getDescription(),
            self.decisionNumber,
            s,
            input
            )

        self.error(nvae)
        raise nvae


    def error(self, nvae):
        """A hook for debugging interface"""
        pass


    def specialStateTransition(self, s, input):
        return -1


    def getDescription(self):
        return "n/a"


    def specialTransition(self, state, symbol):
        return 0


    def unpack(cls, string):
        """@brief Unpack the runlength encoded table data.

        Terence implemented packed table initializers, because Java has a
        size restriction on .class files and the lookup tables can grow
        pretty large. The generated JavaLexer.java of the Java.g example
        would be about 15MB with uncompressed array initializers.

        Python does not have any size restrictions, but the compilation of
        such large source files seems to be pretty memory hungry. The memory
        consumption of the python process grew to >1.5GB when importing a
        15MB lexer, eating all my swap space and I was to impacient to see,
        if it could finish at all. With packed initializers that are unpacked
        at import time of the lexer module, everything works like a charm.

        """

        ret = []
        for i in range(len(string) / 2):
            (n, v) = ord(string[i*2]), ord(string[i*2+1])

            # Is there a bitwise operation to do this?
            if v == 0xFFFF:
                v = -1

            ret += [v] * n

        return ret

    unpack = classmethod(unpack)


class BaseRecognizer(object):
    """
    @brief Common recognizer functionality.

    A generic recognizer that can handle recognizers generated from
    lexer, parser, and tree grammars.  This is all the parsing
    support code essentially; most of it is error recovery stuff and
    backtracking.
    """

    MEMO_RULE_FAILED = -2
    MEMO_RULE_UNKNOWN = -1

    # copies from Token object for convenience in actions
    DEFAULT_TOKEN_CHANNEL = DEFAULT_CHANNEL

    # for convenience in actions
    HIDDEN = HIDDEN_CHANNEL

    # overridden by generated subclasses
    tokenNames = None

    def __init__(self):
        # Input stream of the recognizer. Must be initialized by a subclass.
        self.input = None

        # Track the set of token types that can follow any rule invocation.
        # Stack grows upwards.  When it hits the max, it grows 2x in size
        # and keeps going.
        self.following = []

        # This is true when we see an error and before having successfully
        # matched a token.  Prevents generation of more than one error message
        # per error.
        self.errorRecovery = False

        # The index into the input stream where the last error occurred.
        # This is used to prevent infinite loops where an error is found
        # but no token is consumed during recovery...another error is found,
        # ad naseum.  This is a failsafe mechanism to guarantee that at least
        # one token/tree node is consumed for two errors.
        self.lastErrorIndex = -1

        # In lieu of a return value, this indicates that a rule or token
        # has failed to match.  Reset to false upon valid token match.
        self.failed = False

        # If 0, no backtracking is going on.  Safe to exec actions etc...
        # If >0 then it's the level of backtracking.
        self.backtracking = 0

        # An array[size num rules] of Map<Integer,Integer> that tracks
        # the stop token index for each rule.  ruleMemo[ruleIndex] is
        # the memoization table for ruleIndex.  For key ruleStartIndex, you
        # get back the stop token for associated rule or MEMO_RULE_FAILED.
        #
        #  This is only used if rule memoization is on (which it is by default).
        self.ruleMemo = None


    # this one only exists to shut up pylint :(
    def setInput(self, input):
        self.input = input


    def reset(self):
        """
        reset the parser's state; subclasses must rewinds the input stream
        """

        # wack everything related to error recovery
        self.errorRecovery = False
        self.lastErrorIndex = -1
        self.failed = False
        # wack everything related to backtracking and memoization
        self.backtracking = 0
        if self.ruleMemo is not None:
            self.ruleMemo = {}


    def match(self, input, ttype, follow):
        """
        Match current input symbol against ttype.  Upon error, do one token
        insertion or deletion if possible.  You can override to not recover
    here and bail out of the current production to the normal error
    exception catch (at the end of the method) by just throwing
    MismatchedTokenException upon input.LA(1)!=ttype.
        """

        if self.input.LA(1) == ttype:
            self.input.consume()
            self.errorRecovery = False
            self.failed = False
            return

        if self.backtracking > 0:
            self.failed = True
            return

        self.mismatch(input, ttype, follow)
        return


    def matchAny(self, input):
        self.errorRecovery = False
        self.failed = False
        self.input.consume()


    def mismatch(self, input, ttype, follow):
        """
        factor out what to do upon token mismatch so tree parsers can behave
        differently.  Override this method in your parser to do things
    like bailing out after the first error; just throw the mte object
    instead of calling the recovery method.
        """

        mte = MismatchedTokenException(ttype, input)
        self.recoverFromMismatchedToken(input, mte, ttype, follow)


    def reportError(self, e):
        """Report a recognition problem.

        This method sets errorRecovery to indicate the parser is recovering
        not parsing.  Once in recovery mode, no errors are generated.
        To get out of recovery mode, the parser must successfully match
        a token (after a resync).  So it will go:

        -# error occurs
        -# enter recovery mode, report error
        -# consume until token found in resynch set
        -# try to resume parsing
        -# next match() will reset errorRecovery mode
        .

        """

        # if we've already reported an error and have not matched a token
        # yet successfully, don't report any errors.
        if self.errorRecovery:
            return

        self.errorRecovery = True

        self.displayRecognitionError(self.tokenNames, e)


    def displayRecognitionError(self, tokenNames, e):
        hdr = self.getErrorHeader(e)
        msg = self.getErrorMessage(e, tokenNames)
        self.emitErrorMessage(hdr+" "+msg)


    def getErrorMessage(self, e, tokenNames):
        """
        What error message should be generated for the various
        exception types?

        Not very object-oriented code, but I like having all error message
        generation within one method rather than spread among all of the
    exception classes. This also makes it much easier for the exception
    handling because the exception classes do not have to have pointers back
    to this object to access utility routines and so on. Also, changing
    the message for an exception type would be difficult because you
    would have to subclassing exception, but then somehow get ANTLR
    to make those kinds of exception objects instead of the default.
    This looks weird, but trust me--it makes the most sense in terms
    of flexibility.

        For grammar debugging, you will want to override this to add
    more information such as the stack frame with
    getRuleInvocationStack(e, this.getClass().getName()) and,
    for no viable alts, the decision description and state etc...

        Override this to change the message generated for one or more
    exception types.
        """

        msg = None
        if isinstance(e, MismatchedTokenException):
            tokenName = "<unknown>"
            if e.expecting == EOF:
                tokenName = "EOF"
            else:
                tokenName = self.tokenNames[e.expecting]

            msg = "mismatched input " \
                  + self.getTokenErrorDisplay(e.token) \
                  + " expecting " \
                  + tokenName

        elif isinstance(e, MismatchedTreeNodeException):
            tokenName = "<unknown>"
            if e.expecting == EOF:
                tokenName = "EOF"
            else:
                tokenName = self.tokenNames[e.expecting]

            msg = "mismatched tree node: " \
                  + e.node \
                  + " expecting " \
                  + tokenName

        elif isinstance(e, NoViableAltException):
            msg = "no viable alternative at input " \
                  + self.getTokenErrorDisplay(e.token)

        elif isinstance(e, EarlyExitException):
            msg = "required (...)+ loop did not match anything at input " \
                  + self.getTokenErrorDisplay(e.token)

        elif isinstance(e, MismatchedSetException):
            msg = "mismatched input " \
                  + self.getTokenErrorDisplay(e.token) \
                  + " expecting set " \
                  + repr(e.expecting)

        elif isinstance(e, MismatchedNotSetException):
            msg = "mismatched input " \
                  + self.getTokenErrorDisplay(e.token) \
                  + " expecting set " \
                  + repr(e.expecting)

        elif isinstance(e, FailedPredicateException):
            msg = "rule " \
                  + e.ruleName \
                  + " failed predicate: {" \
                  + e.predicateText \
                  + "}?"


        return msg


    def getErrorHeader(self, e):
        """
        What is the error header, normally line/character position information?
        """

        return "line %d:%d" % (e.line, e.charPositionInLine)


    def getTokenErrorDisplay(self, t):
        """
        How should a token be displayed in an error message? The default
        is to display just the text, but during development you might
        want to have a lot of information spit out.  Override in that case
        to use t.toString() (which, for CommonToken, dumps everything about
        the token). This is better than forcing you to override a method in
        your token objects because you don't have to go modify your lexer
        so that it creates a new Java type.
        """

        s = t.text
        if s is None:
            if t.type == EOF:
                s = "<EOF>"
            else:
                s = "<"+t.type+">"

        return repr(s)


    def emitErrorMessage(self, msg):
        """Override this method to change where error messages go"""
        sys.stderr.write(msg + '\n')


    def recover(self, input, re):
        """
        Recover from an error found on the input stream.  Mostly this is
        NoViableAlt exceptions, but could be a mismatched token that
        the match() routine could not recover from.
        """

        # PROBLEM? what if input stream is not the same as last time
        # perhaps make lastErrorIndex a member of input
        if self.lastErrorIndex == input.index():
            # uh oh, another error at same token index; must be a case
            # where LT(1) is in the recovery token set so nothing is
            # consumed; consume a single token so at least to prevent
            # an infinite loop; this is a failsafe.
            input.consume()

        self.lastErrorIndex = input.index()
        followSet = self.computeErrorRecoverySet()

        self.beginResync()
        self.consumeUntil(input, followSet)
        self.endResync()


    def beginResync(self):
        """
        A hook to listen in on the token consumption during error recovery.
        The DebugParser subclasses this to fire events to the listenter.
        """

        pass


    def endResync(self):
        """
        A hook to listen in on the token consumption during error recovery.
        The DebugParser subclasses this to fire events to the listenter.
        """

        pass


    def computeErrorRecoverySet(self):
        """
        Compute the error recovery set for the current rule.  During
        rule invocation, the parser pushes the set of tokens that can
        follow that rule reference on the stack; this amounts to
        computing FIRST of what follows the rule reference in the
        enclosing rule. This local follow set only includes tokens
        from within the rule; i.e., the FIRST computation done by
        ANTLR stops at the end of a rule.

        EXAMPLE

        When you find a "no viable alt exception", the input is not
        consistent with any of the alternatives for rule r.  The best
        thing to do is to consume tokens until you see something that
        can legally follow a call to r *or* any rule that called r.
        You don't want the exact set of viable next tokens because the
        input might just be missing a token--you might consume the
        rest of the input looking for one of the missing tokens.

        Consider grammar:

        a : '[' b ']'
          | '(' b ')'
          ;
        b : c '^' INT ;
        c : ID
          | INT
          ;

        At each rule invocation, the set of tokens that could follow
        that rule is pushed on a stack.  Here are the various "local"
        follow sets:

        FOLLOW(b1_in_a) = FIRST(']') = ']'
        FOLLOW(b2_in_a) = FIRST(')') = ')'
        FOLLOW(c_in_b) = FIRST('^') = '^'

        Upon erroneous input "[]", the call chain is

        a -> b -> c

        and, hence, the follow context stack is:

        depth  local follow set     after call to rule
          0         \<EOF>                    a (from main())
          1          ']'                     b
          3          '^'                     c

        Notice that ')' is not included, because b would have to have
        been called from a different context in rule a for ')' to be
        included.

        For error recovery, we cannot consider FOLLOW(c)
        (context-sensitive or otherwise).  We need the combined set of
        all context-sensitive FOLLOW sets--the set of all tokens that
        could follow any reference in the call chain.  We need to
        resync to one of those tokens.  Note that FOLLOW(c)='^' and if
        we resync'd to that token, we'd consume until EOF.  We need to
        sync to context-sensitive FOLLOWs for a, b, and c: {']','^'}.
        In this case, for input "[]", LA(1) is in this set so we would
        not consume anything and after printing an error rule c would
        return normally.  It would not find the required '^' though.
        At this point, it gets a mismatched token error and throws an
        exception (since LA(1) is not in the viable following token
        set).  The rule exception handler tries to recover, but finds
        the same recovery set and doesn't consume anything.  Rule b
        exits normally returning to rule a.  Now it finds the ']' (and
        with the successful match exits errorRecovery mode).

        So, you cna see that the parser walks up call chain looking
        for the token that was a member of the recovery set.

        Errors are not generated in errorRecovery mode.

        ANTLR's error recovery mechanism is based upon original ideas:

        "Algorithms + Data Structures = Programs" by Niklaus Wirth

        and

        "A note on error recovery in recursive descent parsers":
        http://portal.acm.org/citation.cfm?id=947902.947905

        Later, Josef Grosch had some good ideas:

        "Efficient and Comfortable Error Recovery in Recursive Descent
        Parsers":
        ftp://www.cocolab.com/products/cocktail/doca4.ps/ell.ps.zip

        Like Grosch I implemented local FOLLOW sets that are combined
        at run-time upon error to avoid overhead during parsing.
        """

        return self.combineFollows(False)


    def computeContextSensitiveRuleFOLLOW(self):
        """
        Compute the context-sensitive FOLLOW set for current rule.
        This is set of token types that can follow a specific rule
        reference given a specific call chain.  You get the set of
        viable tokens that can possibly come next (lookahead depth 1)
        given the current call chain.  Contrast this with the
        definition of plain FOLLOW for rule r:

         FOLLOW(r)={x | S=>*alpha r beta in G and x in FIRST(beta)}

        where x in T* and alpha, beta in V*; T is set of terminals and
        V is the set of terminals and nonterminals.  In other words,
        FOLLOW(r) is the set of all tokens that can possibly follow
        references to r in *any* sentential form (context).  At
        runtime, however, we know precisely which context applies as
        we have the call chain.  We may compute the exact (rather
        than covering superset) set of following tokens.

        For example, consider grammar:

        stat : ID '=' expr ';'      // FOLLOW(stat)=={EOF}
             | "return" expr '.'
             ;
        expr : atom ('+' atom)* ;   // FOLLOW(expr)=={';','.',')'}
        atom : INT                  // FOLLOW(atom)=={'+',')',';','.'}
             | '(' expr ')'
             ;

        The FOLLOW sets are all inclusive whereas context-sensitive
        FOLLOW sets are precisely what could follow a rule reference.
        For input input "i=(3);", here is the derivation:

        stat => ID '=' expr ';'
             => ID '=' atom ('+' atom)* ';'
             => ID '=' '(' expr ')' ('+' atom)* ';'
             => ID '=' '(' atom ')' ('+' atom)* ';'
             => ID '=' '(' INT ')' ('+' atom)* ';'
             => ID '=' '(' INT ')' ';'

        At the "3" token, you'd have a call chain of

          stat -> expr -> atom -> expr -> atom

        What can follow that specific nested ref to atom?  Exactly ')'
        as you can see by looking at the derivation of this specific
        input.  Contrast this with the FOLLOW(atom)={'+',')',';','.'}.

        You want the exact viable token set when recovering from a
        token mismatch.  Upon token mismatch, if LA(1) is member of
        the viable next token set, then you know there is most likely
        a missing token in the input stream.  "Insert" one by just not
        throwing an exception.
        """

        return self.combineFollows(True)


    def combineFollows(self, exact):
        followSet = set()
        for localFollowSet in reversed(self.following):
            followSet |= localFollowSet
            if exact and EOR_TOKEN_TYPE not in localFollowSet:
                break

        followSet -= set([EOR_TOKEN_TYPE])
        return followSet


    def recoverFromMismatchedToken(self, input, e, ttype, follow):
        """Attempt to recover from a single missing or extra token.

        EXTRA TOKEN

        LA(1) is not what we are looking for.  If LA(2) has the right token,
        however, then assume LA(1) is some extra spurious token.  Delete it
        and LA(2) as if we were doing a normal match(), which advances the
        input.

        MISSING TOKEN

        If current token is consistent with what could come after
        ttype then it is ok to "insert" the missing token, else throw
        exception For example, Input "i=(3;" is clearly missing the
        ')'.  When the parser returns from the nested call to expr, it
        will have call chain:

          stat -> expr -> atom

        and it will be trying to match the ')' at this point in the
        derivation:

             => ID '=' '(' INT ')' ('+' atom)* ';'
                                ^
        match() will see that ';' doesn't match ')' and report a
        mismatched token error.  To recover, it sees that LA(1)==';'
        is in the set of tokens that can follow the ')' token
        reference in rule atom.  It can assume that you forgot the ')'.
        """

        # if next token is what we are looking for then "delete" this token
        if input.LA(2) == ttype:
            self.reportError(e)

            self.beginResync()
            input.consume() # simply delete extra token
            self.endResync()
            input.consume()  # move past ttype token as if all were ok
            return

        if not self.recoverFromMismatchedElement(input, e, follow):
            raise e



    def recoverFromMismatchedSet(self, input, e, follow):
        # TODO do single token deletion like above for Token mismatch
        if not self.recoverFromMismatchedElement(input, e, follow):
            raise e


    def recoverFromMismatchedElement(self, input, e, follow):
        """
        This code is factored out from mismatched token and mismatched set
        recovery.  It handles "single token insertion" error recovery for
        both.  No tokens are consumed to recover from insertions.  Return
        true if recovery was possible else return false.
        """

        if follow is None:
            # we have no information about the follow; we can only consume
            # a single token and hope for the best
            return False

        # compute what can follow this grammar element reference
        if EOR_TOKEN_TYPE in follow:
            viableTokensFollowingThisRule = \
                self.computeContextSensitiveRuleFOLLOW()

            follow = (follow | viableTokensFollowingThisRule) \
                     - set([EOR_TOKEN_TYPE])

        # if current token is consistent with what could come after set
        # then it is ok to "insert" the missing token, else throw exception
        if input.LA(1) in follow:
            self.reportError(e)
            return True

        # nothing to do; throw exception
        return False


    def consumeUntil(self, input, tokenTypes):
        """
        Consume tokens until one matches the given token or token set

        tokenTypes can be a single token type or a set of token types

        """

        if not isinstance(tokenTypes, (set, frozenset)):
            tokenTypes = frozenset([tokenTypes])

        ttype = input.LA(1)
        while ttype != EOF and ttype not in tokenTypes:
            input.consume()
            ttype = input.LA(1)


    def getRuleInvocationStack(self):
        """
        Return List<String> of the rules in your parser instance
        leading up to a call to this method.  You could override if
        you want more details such as the file/line info of where
        in the parser java code a rule is invoked.

        This is very useful for error messages and for context-sensitive
        error recovery.

        You must be careful, if you subclass a generated recognizers.
        The default implementation will only search the module of self
        for rules, but the subclass will not contain any rules.
        You probably want to override this method to look like

        def getRuleInvocationStack(self):
            return self._getRuleInvocationStack(<class>.__module__)

        where <class> is the class of the generated recognizer, e.g.
        the superclass of self.
    """

        return self._getRuleInvocationStack(self.__module__)


    def _getRuleInvocationStack(cls, module):
        """
        A more general version of getRuleInvocationStack where you can
        pass in, for example, a RecognitionException to get it's rule
        stack trace.  This routine is shared with all recognizers, hence,
        static.

        TODO: move to a utility class or something; weird having lexer call
        this
        """

        # mmmhhh,... perhaps look at the first argument
        # (f_locals[co_varnames[0]]?) and test if it's a (sub)class of
        # requested recognizer...

        rules = []
#        for frame in reversed(inspect.stack()):
#            code = frame[0].f_code
#            codeMod = inspect.getmodule(code)
#            if codeMod is None:
#                continue
#
#            # skip frames not in requested module
#            if codeMod.__name__ != module:
#                continue
#
#            # skip some unwanted names
#            if code.co_name in ('nextToken', '<module>'):
#                continue
#
#            rules.append(code.co_name)

        return rules

    _getRuleInvocationStack = classmethod(_getRuleInvocationStack)


    def getBacktrackingLevel(self):
        return self.backtracking


    def getGrammarFileName(self):
        """For debugging and other purposes, might want the grammar name.

        Have ANTLR generate an implementation for this method.
        """

        return None


    def toStrings(self, tokens):
        """A convenience method for use most often with template rewrites.

        Convert a List<Token> to List<String>
        """

        if tokens is None:
            return None

        return [token.text for token in tokens]


    def getRuleMemoization(self, ruleIndex, ruleStartIndex):
        """
        Given a rule number and a start token index number, return
        MEMO_RULE_UNKNOWN if the rule has not parsed input starting from
        start index.  If this rule has parsed input starting from the
        start index before, then return where the rule stopped parsing.
        It returns the index of the last token matched by the rule.

        For now we use a hashtable and just the slow Object-based one.
        Later, we can make a special one for ints and also one that
        tosses out data after we commit past input position i.
    """

        if ruleIndex not in self.ruleMemo:
            self.ruleMemo[ruleIndex] = {}

        stopIndex = self.ruleMemo[ruleIndex].get(ruleStartIndex, None)
        if stopIndex is None:
            return self.MEMO_RULE_UNKNOWN

        return stopIndex


    def alreadyParsedRule(self, input, ruleIndex):
        """
        Has this rule already parsed input at the current index in the
        input stream?  Return the stop token index or MEMO_RULE_UNKNOWN.
        If we attempted but failed to parse properly before, return
        MEMO_RULE_FAILED.

        This method has a side-effect: if we have seen this input for
        this rule and successfully parsed before, then seek ahead to
        1 past the stop token matched for this rule last time.
        """

        stopIndex = self.getRuleMemoization(ruleIndex, input.index())
        if stopIndex == self.MEMO_RULE_UNKNOWN:
            return False

        if stopIndex == self.MEMO_RULE_FAILED:
            self.failed = True

        else:
            input.seek(stopIndex + 1)

        return True


    def memoize(self, input, ruleIndex, ruleStartIndex):
        """
        Record whether or not this rule parsed the input at this position
    successfully.
    """

        if self.failed:
            stopTokenIndex = self.MEMO_RULE_FAILED
        else:
            stopTokenIndex = input.index() - 1

        if ruleIndex in self.ruleMemo:
            self.ruleMemo[ruleIndex][ruleStartIndex] = stopTokenIndex


    def traceIn(self, ruleName, ruleIndex, inputSymbol):
        sys.stdout.write("enter %s %s" % (ruleName, inputSymbol))

        if self.failed:
            sys.stdout.write(" failed=%s" % self.failed)

        if self.backtracking > 0:
            sys.stdout.write(" backtracking=%s" % self.backtracking)

        sys.stdout.write('\n')


    def traceOut(self, ruleName, ruleIndex, inputSymbol):
        sys.stdout.write("exit %s %s" % (ruleName, inputSymbol))

        if self.failed:
            sys.stdout.write(" failed=%s" % self.failed)

        if self.backtracking > 0:
            sys.stdout.write(" backtracking=%s" % self.backtracking)

        sys.stdout.write('\n')



class TokenSource(object):
    """
    @brief Abstract baseclass for token producers.

    A source of tokens must provide a sequence of tokens via nextToken()
    and also must reveal it's source of characters; CommonToken's text is
    computed from a CharStream; it only store indices into the char stream.

    Errors from the lexer are never passed to the parser.  Either you want
    to keep going or you do not upon token recognition error.  If you do not
    want to continue lexing then you do not want to continue parsing.  Just
    throw an exception not under RecognitionException and Java will naturally
    toss you all the way out of the recognizers.  If you want to continue
    lexing then you should not throw an exception to the parser--it has already
    requested a token.  Keep lexing until you get a valid one.  Just report
    errors and keep going, looking for a valid token.
    """

    def nextToken(self):
        """Return a Token object from your input stream (usually a CharStream).

        Do not fail/return upon lexing error; keep chewing on the characters
        until you get a good one; errors are not passed through to the parser.
        """

        raise NotImplementedError


class Lexer(BaseRecognizer, TokenSource):
    """
    @brief Baseclass for generated lexer classes.

    A lexer is recognizer that draws input symbols from a character stream.
    lexer grammars result in a subclass of this object. A Lexer object
    uses simplified match() and error recovery mechanisms in the interest
    of speed.
    """

    def __init__(self, input):
        BaseRecognizer.__init__(self)
        TokenSource.__init__(self)

        # Where is the lexer drawing characters from?
        self.input = input

        # The goal of all lexer rules/methods is to create a token object.
    # This is an instance variable as multiple rules may collaborate to
    # create a single token.  nextToken will return this object after
    # matching lexer rule(s).  If you subclass to allow multiple token
    # emissions, then set this to the last token to be matched or
    # something nonnull so that the auto token emit mechanism will not
    # emit another token.
        self.token = None

    # What character index in the stream did the current token start at?
    # Needed, for example, to get the text for current token.  Set at
    # the start of nextToken.
        self.tokenStartCharIndex = -1

        # The line on which the first character of the token resides
        self.tokenStartLine = -1

        # The character position of first character within the line
        self.tokenStartCharPositionInLine = -1

        # The channel number for the current token
        self.channel = DEFAULT_CHANNEL

        # The token type for the current token
        self.type = INVALID_TOKEN_TYPE

        # You can set the text for the current token to override what is in
    # the input char buffer.  Use setText() or can set this instance var.
        self._text = None


    def reset(self):
        BaseRecognizer.reset(self) # reset all recognizer state variables

        # wack Lexer state variables
        self.token = None
        self.type = INVALID_TOKEN_TYPE
        self.channel = DEFAULT_CHANNEL
        self.tokenStartCharIndex = -1
        self.tokenStartLine = -1
        self.tokenStartCharPositionInLine = -1
        self._text = None
        if self.input is not None:
            self.input.seek(0) # rewind the input


    def nextToken(self):
        """
        Return a token from this source; i.e., match a token on the char
    stream.
    """

        while 1:
            self.token = None
            self.channel = DEFAULT_CHANNEL
            self.tokenStartCharIndex = self.input.index()
            self.tokenStartCharPositionInLine = self.input.charPositionInLine
            self.tokenStartLine = self.input.line
            self._text = None
            if self.input.LA(1) == EOF:
                return EOF_TOKEN

            try:
                self.mTokens()

                if self.token is None:
                    self.emit()

                elif self.token == SKIP_TOKEN:
                    continue

                return self.token

            except RecognitionException, re:
                self.reportError(re)
                self.recover(re)


    def skip(self):
        """
    Instruct the lexer to skip creating a token for current lexer rule
    and look for another token.  nextToken() knows to keep looking when
    a lexer rule finishes with token set to SKIP_TOKEN.  Recall that
    if token==null at end of any token rule, it creates one for you
    and emits it.
    """

        self.token = SKIP_TOKEN


    def mTokens(self):
        """This is the lexer entry point that sets instance var 'token'"""

        # abstract method
        raise NotImplementedError


    def setCharStream(self, input):
        """Set the char stream and reset the lexer"""
        self.input = None
        self.reset()
        self.input = input


    def emit(self, token=None):
        """
        The standard method called to automatically emit a token at the
    outermost lexical rule.  The token object should point into the
    char buffer start..stop.  If there is a text override in 'text',
    use that to set the token's text.
    """

        if token is None:
            token = CommonToken(
                input=self.input,
                type=self.type,
                channel=self.channel,
                start=self.tokenStartCharIndex,
                stop=self.getCharIndex()-1
                )
            token.line = self.tokenStartLine
            token.text = self.text
            token.charPositionInLine = self.tokenStartCharPositionInLine

        self.token = token

        return token


    def match(self, s):
        if isinstance(s, basestring):
            i = 0
            while i < len(s):
                if self.input.LA(1) != s[i]:
                    if self.backtracking > 0:
                        self.failed = True
                        return

                    mte = MismatchedTokenException(s[i], self.input)
                    self.recover(mte)
                    raise mte

                i += 1
                self.input.consume()
                self.failed = False

        else:
            if self.input.LA(1) != s:
                if self.backtracking > 0:
                    self.failed = True
                    return

                mte = MismatchedTokenException(s, self.input)
                self.recover(mte)
                raise mte

            self.input.consume()
            self.failed = False


    def matchAny(self):
        self.input.consume()


    def matchRange(self, a, b):
        if self.input.LA(1) < a or self.input.LA(1) > b:
            if self.backtracking > 0:
                self.failed = True
                return

            mre = MismatchedRangeException(a, b, self.input)
            self.recover(mre)
            raise mre

        self.input.consume()
        self.failed = False


    def getLine(self):
        return self.input.line


    def getCharPositionInLine(self):
        return self.input.charPositionInLine


    def getCharIndex(self):
        """What is the index of the current character of lookahead?"""

        return self.input.index()


    def getText(self):
        """
        Return the text matched so far for the current token or any
        text override.
        """
        if self._text is not None:
            return self._text

        return self.input.substring(
            self.tokenStartCharIndex,
            self.getCharIndex()-1
            )


    def setText(self, text):
        """
        Set the complete text of this token; it wipes any previous
    changes to the text.
    """
        self._text = text


    text = property(getText, setText)


    def reportError(self, e):
        ## TODO: not thought about recovery in lexer yet.

        ## # if we've already reported an error and have not matched a token
        ## # yet successfully, don't report any errors.
        ## if self.errorRecovery:
        ##     #System.err.print("[SPURIOUS] ");
        ##     return;
        ##
        ## self.errorRecovery = True

        self.displayRecognitionError(self.tokenNames, e)


    def getErrorMessage(self, e, tokenNames):
        msg = None

        if isinstance(e, MismatchedTokenException):
            msg = "mismatched character " \
                  + self.getCharErrorDisplay(e.c) \
                  + " expecting " \
                  + self.getCharErrorDisplay(e.expecting)

        elif isinstance(e, NoViableAltException):
            msg = "no viable alternative at character " \
                  + self.getCharErrorDisplay(e.c)

        elif isinstance(e, EarlyExitException):
            msg = "required (...)+ loop did not match anything at character " \
                  + self.getCharErrorDisplay(e.c)

        elif isinstance(e, MismatchedSetException):
            msg = "mismatched character " \
                  + self.getCharErrorDisplay(e.c) \
                  + " expecting set " \
                  + repr(e.expecting)

        elif isinstance(e, MismatchedNotSetException):
            msg = "mismatched character " \
                  + self.getCharErrorDisplay(e.c) \
                  + " expecting set " \
                  + repr(e.expecting)

        elif isinstance(e, MismatchedRangeException):
            msg = "mismatched character " \
                  + self.getCharErrorDisplay(e.c) \
                  + " expecting set " \
                  + self.getCharErrorDisplay(e.a) \
                  + ".." \
                  + self.getCharErrorDisplay(e.b)

        else:
            msg = BaseRecognizer.getErrorMessage(self, e, tokenNames)

        return msg


    def getCharErrorDisplay(self, c):
        if c == EOF:
            c = '<EOF>'
        return repr(c)


    def recover(self, re):
        """
        Lexers can normally match any char in it's vocabulary after matching
    a token, so do the easy thing and just kill a character and hope
    it all works out.  You can instead use the rule invocation stack
    to do sophisticated error recovery if you are in a fragment rule.
    """

        self.input.consume()


    def traceIn(self, ruleName, ruleIndex):
        inputSymbol = "%s line=%d:%s" % (self.input.LT(1),
                                         self.getLine(),
                                         self.getCharPositionInLine()
                                         )

        BaseRecognizer.traceIn(self, ruleName, ruleIndex, inputSymbol)


    def traceOut(self, ruleName, ruleIndex):
        inputSymbol = "%s line=%d:%s" % (self.input.LT(1),
                                         self.getLine(),
                                         self.getCharPositionInLine()
                                         )

        BaseRecognizer.traceOut(self, ruleName, ruleIndex, inputSymbol)



class Parser(BaseRecognizer):
    """
    @brief Baseclass for generated parser classes.
    """

    def __init__(self, lexer):
        BaseRecognizer.__init__(self)

        self.setTokenStream(lexer)


    def reset(self):
        BaseRecognizer.reset(self) # reset all recognizer state variables
        if self.input is not None:
            self.input.seek(0) # rewind the input


    def setTokenStream(self, input):
        """Set the token stream and reset the parser"""

        self.input = None
        self.reset()
        self.input = input


    def getTokenStream(self):
        return self.input


    def traceIn(self, ruleName, ruleIndex):
        BaseRecognizer.traceIn(self, ruleName, ruleIndex, self.input.LT(1))


    def traceOut(self, ruleName, ruleIndex):
        BaseRecognizer.traceOut(self, ruleName, ruleIndex, self.input.LT(1))

class IntStream(object):
    """
    @brief Base interface for streams of integer values.

    A simple stream of integers used when all I care about is the char
    or token type sequence (such as interpretation).
    """

    def consume(self):
        raise NotImplementedError


    def LA(self, i):
        """Get int at current input pointer + i ahead where i=1 is next int.

        Negative indexes are allowed.  LA(-1) is previous token (token
    just matched).  LA(-i) where i is before first token should
    yield -1, invalid char / EOF.
    """

        raise NotImplementedError


    def mark(self):
        """
        Tell the stream to start buffering if it hasn't already.  Return
        current input position, index(), or some other marker so that
        when passed to rewind() you get back to the same spot.
        rewind(mark()) should not affect the input cursor.  The Lexer
        track line/col info as well as input index so its markers are
        not pure input indexes.  Same for tree node streams.
        """

        raise NotImplementedError


    def index(self):
        """
        Return the current input symbol index 0..n where n indicates the
        last symbol has been read.  The index is the symbol about to be
        read not the most recently read symbol.
        """

        raise NotImplementedError


    def rewind(self, marker=None):
        """
        Reset the stream so that next call to index would return marker.
        The marker will usually be index() but it doesn't have to be.  It's
        just a marker to indicate what state the stream was in.  This is
        essentially calling release() and seek().  If there are markers
        created after this marker argument, this routine must unroll them
        like a stack.  Assume the state the stream was in when this marker
        was created.

        If marker is None:
        Rewind to the input position of the last marker.
        Used currently only after a cyclic DFA and just
        before starting a sem/syn predicate to get the
        input position back to the start of the decision.
        Do not "pop" the marker off the state.  mark(i)
        and rewind(i) should balance still. It is
        like invoking rewind(last marker) but it should not "pop"
        the marker off.  It's like seek(last marker's input position).
    """

        raise NotImplementedError


    def release(self, marker=None):
        """
        You may want to commit to a backtrack but don't want to force the
        stream to keep bookkeeping objects around for a marker that is
        no longer necessary.  This will have the same behavior as
        rewind() except it releases resources without the backward seek.
        This must throw away resources for all markers back to the marker
        argument.  So if you're nested 5 levels of mark(), and then release(2)
        you have to release resources for depths 2..5.
    """

        raise NotImplementedError


    def seek(self, index):
        """
        Set the input cursor to the position indicated by index.  This is
        normally used to seek ahead in the input stream.  No buffering is
        required to do this unless you know your stream will use seek to
        move backwards such as when backtracking.

        This is different from rewind in its multi-directional
        requirement and in that its argument is strictly an input cursor
        (index).

        For char streams, seeking forward must update the stream state such
        as line number.  For seeking backwards, you will be presumably
        backtracking using the mark/rewind mechanism that restores state and
        so this method does not need to update state when seeking backwards.

        Currently, this method is only used for efficient backtracking using
        memoization, but in the future it may be used for incremental parsing.

        The index is 0..n-1.  A seek to position i means that LA(1) will
        return the ith symbol.  So, seeking to 0 means LA(1) will return the
        first element in the stream.
        """

        raise NotImplementedError


    def size(self):
        """
        Only makes sense for streams that buffer everything up probably, but
        might be useful to display the entire stream or for testing.  This
        value includes a single EOF.
    """

        raise NotImplementedError



class CharStream(IntStream):
    """
    @brief A source of characters for an ANTLR lexer.

    This is an abstract class that must be implemented by a subclass.

    """

    # pylint does not realize that this is an interface, too
    #pylint: disable-msg=W0223

    EOF = -1


    def substring(self, start, stop):
        """
        For infinite streams, you don't need this; primarily I'm providing
        a useful interface for action code.  Just make sure actions don't
        use this on streams that don't support it.
        """

        raise NotImplementedError


    def LT(self, i):
        """
        Get the ith character of lookahead.  This is the same usually as
        LA(i).  This will be used for labels in the generated
        lexer code.  I'd prefer to return a char here type-wise, but it's
        probably better to be 32-bit clean and be consistent with LA.
        """

        raise NotImplementedError


    def getLine(self):
        """ANTLR tracks the line information automatically"""

        raise NotImplementedError


    def setLine(self, line):
        """
        Because this stream can rewind, we need to be able to reset the line
        """

        raise NotImplementedError


    def getCharPositionInLine(self):
        """
        The index of the character relative to the beginning of the line 0..n-1
        """

        raise NotImplementedError


    def setCharPositionInLine(self, pos):
        raise NotImplementedError


class TokenStream(IntStream):
    """

    @brief A stream of tokens accessing tokens from a TokenSource

    This is an abstract class that must be implemented by a subclass.

    """

    # pylint does not realize that this is an interface, too
    #pylint: disable-msg=W0223

    def LT(self, k):
        """
        Get Token at current input pointer + i ahead where i=1 is next Token.
        i<0 indicates tokens in the past.  So -1 is previous token and -2 is
        two tokens ago. LT(0) is undefined.  For i>=n, return Token.EOFToken.
        Return null for LT(0) and any index that results in an absolute address
        that is negative.
    """

        raise NotImplementedError


    def get(self, i):
        """
        Get a token at an absolute index i; 0..n-1.  This is really only
        needed for profiling and debugging and token stream rewriting.
        If you don't want to buffer up tokens, then this method makes no
        sense for you.  Naturally you can't use the rewrite stream feature.
        I believe DebugTokenStream can easily be altered to not use
        this method, removing the dependency.
        """

        raise NotImplementedError


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

        raise NotImplementedError


    def toString(self, start=None, stop=None):
        """
        Return the text of all tokens from start to stop, inclusive.
        If the stream does not buffer all the tokens then it can just
        return "" or null;  Users should not access $ruleLabel.text in
        an action of course in that case.

        Because the user is not required to use a token with an index stored
        in it, we must provide a means for two token objects themselves to
        indicate the start/end location.  Most often this will just delegate
        to the other toString(int,int).  This is also parallel with
        the TreeNodeStream.toString(Object,Object).
    """

        raise NotImplementedError


############################################################################
#
# character streams for use in lexers
#   CharStream
#   \- ANTLRStringStream
#
############################################################################


class ANTLRStringStream(CharStream):
    """
    @brief CharStream that pull data from a unicode string.

    A pretty quick CharStream that pulls all data from an array
    directly.  Every method call counts in the lexer.

    """


    def __init__(self, data):
        """
        @param data This should be a unicode string holding the data you want
           to parse. If you pass in a byte string, the Lexer will choke on
           non-ascii data.

        """

        CharStream.__init__(self)

      # The data being scanned
        self.data = data

    # How many characters are actually in the buffer
        self.n = len(data)

     # 0..n-1 index into string of next char
        self.p = 0

    # line number 1..n within the input
        self.line = 1

     # The index of the character relative to the beginning of the
        # line 0..n-1
        self.charPositionInLine = 0

    # A list of CharStreamState objects that tracks the stream state
        # values line, charPositionInLine, and p that can change as you
        # move through the input stream.  Indexed from 0..markDepth-1.
        self._markers = [ ]
        self.lastMarker = None
        self.markDepth = 0


    def reset(self):
        """
        Reset the stream so that it's in the same state it was
        when the object was created *except* the data array is not
        touched.
        """

        self.p = 0
        self.line = 1
        self.charPositionInLine = 0
        self._markers = [ ]


    def consume(self):
        if self.p < self.n:
            self.charPositionInLine += 1
            if self.data[self.p] == '\n':
                self.line += 1
                self.charPositionInLine = 0

            self.p += 1


    def LA(self, i):
        if i == 0:
            return 0 # undefined

        if i < 0:
            i += 1 # e.g., translate LA(-1) to use offset i=0; then data[p+0-1]
            if self.p+i-1 < 0:
                return EOF # invalid; no char before first char

        if self.p+i-1 >= self.n:
            return EOF

        return self.data[self.p+i-1]

    LT = LA

    def index(self):
        """
        Return the current input symbol index 0..n where n indicates the
        last symbol has been read.  The index is the index of char to
        be returned from LA(1).
        """

        return self.p


    def size(self):
        return self.n


    def mark(self):
        state = (self.p, self.line, self.charPositionInLine)
        try:
            self._markers[self.markDepth] = state
        except IndexError:
            self._markers.append(state)
        self.markDepth += 1

        self.lastMarker = self.markDepth

        return self.lastMarker


    def rewind(self, marker=None):
        if marker is None:
            marker = self.lastMarker

        p, line, charPositionInLine = self._markers[marker-1]

        self.seek(p)
        self.line = line
        self.charPositionInLine = charPositionInLine
        self.release(marker)


    def release(self, marker=None):
        if marker is None:
            marker = self.lastMarker

        self.markDepth = marker-1


    def seek(self, index):
        """
        consume() ahead until p==index; can't just set p=index as we must
        update line and charPositionInLine.
        """

        if index <= self.p:
            self.p = index # just jump; don't update stream state (line, ...)
            return

        # seek forward, consume until p hits index
        while self.p < index:
            self.consume()


    def substring(self, start, stop):
        return self.data[start:stop+1]


    def getLine(self):
        """Using setter/getter methods is deprecated. Use o.line instead."""
        return self.line


    def getCharPositionInLine(self):
        """Using setter/getter methods is deprecated. Use o.charPositionInLine instead."""
        return self.charPositionInLine


    def setLine(self, line):
        """Using setter/getter methods is deprecated. Use o.line instead."""
        self.line = line


    def setCharPositionInLine(self, pos):
        """Using setter/getter methods is deprecated. Use o.charPositionInLine instead."""
        self.charPositionInLine = pos


# I guess the ANTLR prefix exists only to avoid a name clash with some Java
# mumbojumbo. A plain "StringStream" looks better to me, which should be
# the preferred name in Python.
StringStream = ANTLRStringStream


############################################################################
#
# Token streams
#   TokenStream
#   +- CommonTokenStream
#   \- TokenRewriteStream
#
############################################################################


class CommonTokenStream(TokenStream):
    """
    @brief The most common stream of tokens

    The most common stream of tokens is one where every token is buffered up
    and tokens are prefiltered for a certain channel (the parser will only
    see these tokens and cannot change the filter channel number during the
    parse).
    """

    def __init__(self, tokenSource=None, channel=DEFAULT_CHANNEL):
        """
        @param tokenSource A TokenSource instance (usually a Lexer) to pull
            the tokens from.

        @param channel Skip tokens on any channel but this one; this is how we
            skip whitespace...

        """

        TokenStream.__init__(self)

        self.tokenSource = tokenSource

    # Record every single token pulled from the source so we can reproduce
        # chunks of it later.
        self.tokens = []

    # Map<tokentype, channel> to override some Tokens' channel numbers
        self.channelOverrideMap = {}

    # Set<tokentype>; discard any tokens with this type
        self.discardSet = set()

    # Skip tokens on any channel but this one; this is how we skip whitespace...
        self.channel = channel

    # By default, track all incoming tokens
        self.discardOffChannelTokens = False

    # The index into the tokens list of the current token (next token
        # to consume).  p==-1 indicates that the tokens list is empty
        self.p = -1

        # Remember last marked position
        self.lastMarker = None


    def setTokenSource(self, tokenSource):
        """Reset this token stream by setting its token source."""

        self.tokenSource = tokenSource
        self.tokens = []
        self.p = -1
        self.channel = DEFAULT_CHANNEL


    def fillBuffer(self):
        """
        Load all tokens from the token source and put in tokens.
    This is done upon first LT request because you might want to
        set some token type / channel overrides before filling buffer.
        """


        index = 0
        t = self.tokenSource.nextToken()
        while t is not None and t.type != EOF:
            discard = False

            if self.discardSet is not None and t.type in self.discardSet:
                discard = True

            elif self.discardOffChannelTokens and t.channel != self.channel:
                discard = True

            # is there a channel override for token type?
            try:
                overrideChannel = self.channelOverrideMap[t.type]

            except KeyError:
                # no override for this type
                pass

            else:
                if overrideChannel == self.channel:
                    t.channel = overrideChannel
                else:
                    discard = True

            if not discard:
                t.index = index
                self.tokens.append(t)
                index += 1

            t = self.tokenSource.nextToken()

        # leave p pointing at first token on channel
        self.p = 0
        self.p = self.skipOffTokenChannels(self.p)


    def consume(self):
        """
        Move the input pointer to the next incoming token.  The stream
        must become active with LT(1) available.  consume() simply
        moves the input pointer so that LT(1) points at the next
        input symbol. Consume at least one token.

        Walk past any token not on the channel the parser is listening to.
        """

        if self.p < len(self.tokens):
            self.p += 1

            self.p = self.skipOffTokenChannels(self.p) # leave p on valid token


    def skipOffTokenChannels(self, i):
        """
        Given a starting index, return the index of the first on-channel
        token.
        """

        n = len(self.tokens)
        while i < n and self.tokens[i].channel != self.channel:
            i += 1

        return i


    def skipOffTokenChannelsReverse(self, i):
        while i >= 0 and self.tokens[i].channel != self.channel:
            i -= 1

        return i


    def setTokenTypeChannel(self, ttype, channel):
        """
        A simple filter mechanism whereby you can tell this token stream
        to force all tokens of type ttype to be on channel.  For example,
        when interpreting, we cannot exec actions so we need to tell
        the stream to force all WS and NEWLINE to be a different, ignored
        channel.
    """

        self.channelOverrideMap[ttype] = channel


    def discardTokenType(self, ttype):
        self.discardSet.add(ttype)


    def getTokens(self, start=None, stop=None, types=None):
        """
        Given a start and stop index, return a list of all tokens in
        the token type set.  Return None if no tokens were found.  This
        method looks at both on and off channel tokens.
        """

        if self.p == -1:
            self.fillBuffer()

        if stop is None or stop >= len(self.tokens):
            stop = len(self.tokens) - 1

        if start is None or stop < 0:
            start = 0

        if start > stop:
            return None

        if isinstance(types, (int, long)):
            # called with a single type, wrap into set
            types = set([types])

        filteredTokens = [
            token for token in self.tokens[start:stop]
            if types is None or token.type in types
            ]

        if len(filteredTokens) == 0:
            return None

        return filteredTokens


    def LT(self, k):
        """
        Get the ith token from the current position 1..n where k=1 is the
        first symbol of lookahead.
        """

        if self.p == -1:
            self.fillBuffer()

        if k == 0:
            return None

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

        if self.p + k - 1 >= len(self.tokens):
            return EOF_TOKEN

        i = self.p
        n = 1
        # find k good tokens
        while n < k:
            # skip off-channel tokens
            i = self.skipOffTokenChannels(i+1) # leave p on valid token
            n += 1

        if i >= len(self.tokens):
            return EOF_TOKEN

        return self.tokens[i]


    def LB(self, k):
        """Look backwards k tokens on-channel tokens"""

        if self.p == -1:
            self.fillBuffer()

        if k == 0:
            return None

        if self.p - k < 0:
            return None

        i = self.p
        n = 1
        # find k good tokens looking backwards
        while n <= k:
            # skip off-channel tokens
            i = self.skipOffTokenChannelsReverse(i-1) # leave p on valid token
            n += 1

        if i < 0:
            return None

        return self.tokens[i]


    def get(self, i):
        """
        Return absolute token i; ignore which channel the tokens are on;
        that is, count all tokens not just on-channel tokens.
        """

        return self.tokens[i]


    def LA(self, i):
        return self.LT(i).type


    def mark(self):
        self.lastMarker = self.index()
        return self.lastMarker


    def release(self, marker=None):
        # no resources to release
        pass


    def size(self):
        return len(self.tokens)


    def index(self):
        return self.p


    def rewind(self, marker=None):
        if marker is None:
            marker = self.lastMarker

        self.seek(marker)


    def seek(self, index):
        self.p = index


    def getTokenSource(self):
        return self.tokenSource


    def toString(self, start=None, stop=None):
        if self.p == -1:
            self.fillBuffer()

        if start is None:
            start = 0
        elif not isinstance(start, int):
            start = start.index

        if stop is None:
            stop = len(self.tokens) - 1
        elif not isinstance(stop, int):
            stop = stop.index

        if stop >= len(self.tokens):
            stop = len(self.tokens) - 1

        return ''.join([t.text for t in self.tokens[start:stop+1]])


class RewriteOperation(object):
    """@brief Internal helper class."""

    def __init__(self, index, text):
        self.index = index
        self.text = text

    def execute(self, buf):
        """Execute the rewrite operation by possibly adding to the buffer.
        Return the index of the next token to operate on.
        """

        return self.index

    def toString(self):
        opName = self.__class__.__name__
        return opName+"@"+self.index+'"'+self.text+'"'

    __str__ = toString


class InsertBeforeOp(RewriteOperation):
    """@brief Internal helper class."""

    def execute(self, buf):
        buf.write(self.text)
        return self.index


class ReplaceOp(RewriteOperation):
    """
    @brief Internal helper class.

    I'm going to try replacing range from x..y with (y-x)+1 ReplaceOp
    instructions.
    """

    def __init__(self, first, last, text):
        RewriteOperation.__init__(self, first, text)
        self.lastIndex = last


    def execute(self, buf):
        if self.text is not None:
            buf.write(self.text)

        return self.lastIndex + 1


class RewriteCardinalityException(RuntimeError):
    """
    @brief Base class for all exceptions thrown during AST rewrite construction.

    This signifies a case where the cardinality of two or more elements
    in a subrule are different: (ID INT)+ where |ID|!=|INT|
    """

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

        self.elementDescription = elementDescription


    def getMessage(self):
        return self.elementDescription


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

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


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

    pass


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

class Tree(object):
    """
    @brief Abstract baseclass for tree nodes.

    What does a tree look like?  ANTLR has a number of support classes
    such as CommonTreeNodeStream that work on these kinds of trees.  You
    don't have to make your trees implement this interface, but if you do,
    you'll be able to use more support code.

    NOTE: When constructing trees, ANTLR can build any kind of tree; it can
    even use Token objects as trees if you add a child list to your tokens.

    This is a tree node without any payload; just navigation and factory stuff.
    """


    def getChild(self, i):
        raise NotImplementedError


    def getChildCount(self):
        raise NotImplementedError


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

        raise NotImplementedError


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

        raise NotImplementedError


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

        raise NotImplementedError


    def setTokenStartIndex(self, index):
        raise NotImplementedError


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

        raise NotImplementedError


    def setTokenStopIndex(self, index):
        raise NotImplementedError


    def dupTree(self):
        raise NotImplementedError


    def dupNode(self):
        raise NotImplementedError


    def getType(self):
        """Return a token type; needed for tree parsing."""

        raise NotImplementedError


    def getText(self):
        raise NotImplementedError


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

        raise NotImplementedError


    def getCharPositionInLine(self):
        raise NotImplementedError


    def toStringTree(self):
        raise NotImplementedError


    def toString(self):
        raise NotImplementedError



class TreeAdaptor(object):
    """
    @brief Abstract baseclass for tree adaptors.

    How to create and navigate trees.  Rather than have a separate factory
    and adaptor, I've merged them.  Makes sense to encapsulate.

    This takes the place of the tree construction code generated in the
    generated code in 2.x and the ASTFactory.

    I do not need to know the type of a tree at all so they are all
    generic Objects.  This may increase the amount of typecasting needed. :(
    """

    # C o n s t r u c t i o n

    def createWithPayload(self, payload):
        """
        Create a tree node from Token object; for CommonTree type trees,
        then the token just becomes the payload.  This is the most
        common create call.
        """

        raise NotImplementedError


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

        raise NotImplementedError


    def dupNode(self, treeNode):
        """Duplicate a single tree node"""

        raise NotImplementedError


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

        raise NotImplementedError


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

        raise NotImplementedError


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

        raise NotImplementedError


    def becomeRoot(self, newRoot, oldRoot):
        """
        If oldRoot is a nil root, just copy or move the children to newRoot.
        If not a nil root, make oldRoot a child of newRoot.

           old=^(nil a b c), new=r yields ^(r a b c)
           old=^(a b c), new=r yields ^(r ^(a b c))

        If newRoot is a nil-rooted single child tree, use the single
        child as the new root node.

           old=^(nil a b c), new=^(nil r) yields ^(r a b c)
           old=^(a b c), new=^(nil r) yields ^(r ^(a b c))

        If oldRoot was null, it's ok, just return newRoot (even if isNil).

           old=null, new=r yields r
           old=null, new=^(nil r) yields ^(nil r)

        Return newRoot.  Throw an exception if newRoot is not a
        simple node or nil root with a single child node--it must be a root
        node.  If newRoot is ^(nil x) return x as newRoot.

        Be advised that it's ok for newRoot to point at oldRoot's
        children; i.e., you don't have to copy the list.  We are
        constructing these nodes so we should have this control for
        efficiency.
        """

        raise NotImplementedError


    def rulePostProcessing(self, root):
        """
        Given the root of the subtree created for this rule, post process
        it to do any simplifications or whatever you want.  A required
        behavior is to convert ^(nil singleSubtree) to singleSubtree
        as the setting of start/stop indexes relies on a single non-nil root
        for non-flat trees.

        Flat trees such as for lists like "idlist : ID+ ;" are left alone
        unless there is only one ID.  For a list, the start/stop indexes
        are set in the nil node.

        This method is executed after all rule tree construction and right
        before setTokenBoundaries().
        """

        raise NotImplementedError


    def getUniqueID(self, node):
        """For identifying trees.

        How to identify nodes so we can say "add node to a prior node"?
        Even becomeRoot is an issue.  Use System.identityHashCode(node)
        usually.
        """

        raise NotImplementedError


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

    def createFromToken(self, tokenType, fromToken, text=None):
        """
        Create a new node derived from a token, with a new token type and
        (optionally) new text.

        This is invoked from an imaginary node ref on right side of a
        rewrite rule as IMAG[$tokenLabel] or IMAG[$tokenLabel "IMAG"].

        This should invoke createToken(Token).
        """

        raise NotImplementedError


    def createFromType(self, tokenType, text):
        """Create a new node derived from a token, with a new token type.

        This is invoked from an imaginary node ref on right side of a
        rewrite rule as IMAG["IMAG"].

        This should invoke createToken(int,String).
        """

        raise NotImplementedError


    # C o n t e n t

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

        raise NotImplementedError


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

        raise NotImplementedError


    def getText(self, t):
        raise NotImplementedError

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

        raise NotImplementedError


    def getToken(self, t):
        """Return the token object from which this node was created.

        Currently used only for printing an error message.
        The error display routine in BaseRecognizer needs to
        display where the input the error occurred. If your
        tree of limitation does not store information that can
        lead you to the token, you can create a token filled with
        the appropriate information and pass that back.  See
        BaseRecognizer.getErrorMessage().
        """

        raise NotImplementedError


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

        raise NotImplementedError


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

        raise NotImplementedError


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

        raise NotImplementedError


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

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

        raise NotImplementedError


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

        raise NotImplementedError


    # Misc

    def create(self, *args):
        """
        Deprecated, use createWithPayload, createFromToken or createFromType.

        This method only exists to mimic the Java interface of TreeAdaptor.

        """

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

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

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

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

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


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


class BaseTree(Tree):
    """
    @brief A generic tree implementation with no payload.

    You must subclass to
    actually have any user data.  ANTLR v3 uses a list of children approach
    instead of the child-sibling approach in v2.  A flat tree (a list) is
    an empty node whose children represent the list.  An empty, but
    non-null node is called "nil".
    """

    # BaseTree is abstract, no need to complain about not implemented abstract
    # methods
    # pylint: disable-msg=W0223

    def __init__(self, node=None):
        """
        Create a new node from an existing node does nothing for BaseTree
        as there are no fields other than the children list, which cannot
        be copied as the children are not considered part of this node.
        """

        Tree.__init__(self)
        self.children = []


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


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

        return None


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


    def addChild(self, childTree):
        """Add t as child of this node.

        Warning: if t has no children, but child does
        and child isNil then this routine moves children to t via
        t.children = child.children; i.e., without copying the array.
        """

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

        if childTree is None:
            return

        if childTree.isNil():
            self.children += childTree.children

        else:
            self.children.append(childTree)



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

        self.children += children


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


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


    def isNil(self):
        return False


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

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

        return newTree


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

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

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

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

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

        return ''.join(buf)


    def getLine(self):
        return 0


    def getCharPositionInLine(self):
        return 0


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

        raise NotImplementedError



class BaseTreeAdaptor(TreeAdaptor):
    """
    @brief A generic tree adaptor implementation.
    """

    # BaseTreeAdaptor is abstract, no need to complain about not implemented
    # abstract methods
    # pylint: disable-msg=W0223

    def nil(self):
        return self.createWithPayload(None)


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


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


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

        #if isinstance(child, Token):
        #    child = self.createWithPayload(child)

        if tree is not None:
            tree.addChild(child)


    def becomeRoot(self, newRoot, oldRoot):
        """
        If oldRoot is a nil root, just copy or move the children to newRoot.
        If not a nil root, make oldRoot a child of newRoot.

          old=^(nil a b c), new=r yields ^(r a b c)
          old=^(a b c), new=r yields ^(r ^(a b c))

        If newRoot is a nil-rooted single child tree, use the single
        child as the new root node.

          old=^(nil a b c), new=^(nil r) yields ^(r a b c)
          old=^(a b c), new=^(nil r) yields ^(r ^(a b c))

        If oldRoot was null, it's ok, just return newRoot (even if isNil).

          old=null, new=r yields r
          old=null, new=^(nil r) yields ^(nil r)

        Return newRoot.  Throw an exception if newRoot is not a
        simple node or nil root with a single child node--it must be a root
        node.  If newRoot is ^(nil x) return x as newRoot.

        Be advised that it's ok for newRoot to point at oldRoot's
        children; i.e., you don't have to copy the list.  We are
        constructing these nodes so we should have this control for
        efficiency.
        """

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

        if oldRoot is None:
            return newRoot

        if not isinstance(newRoot, CommonTree):
            newRoot = self.createWithPayload(newRoot)

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

            newRoot = newRoot.getChild(0)

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


    def rulePostProcessing(self, root):
        """Transform ^(nil x) to x"""

        if root is not None and root.isNil() and root.getChildCount() == 1:
            root = root.getChild(0)

        return root


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


    def createFromType(self, tokenType, text):
        fromToken = self.createToken(tokenType=tokenType, text=text)
        t = self.createWithPayload(fromToken)
        return t


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


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


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


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


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


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


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


    def createToken(self, fromToken=None, tokenType=None, text=None):
        """
        Tell me how to create a token for use with imaginary token nodes.
        For example, there is probably no input symbol associated with imaginary
        token DECL, but you need to create it as a payload or whatever for
        the DECL node as in ^(DECL type ID).

        If you care what the token payload objects' type is, you should
        override this method and any other createToken variant.
        """

        raise NotImplementedError


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


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

    def __init__(self, payload):
        BaseTree.__init__(self)

        # What token indexes bracket all tokens associated with this node
        # and below?
        self.startIndex = -1
        self.stopIndex = -1

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



    def getToken(self):
        return self.token


    def dupNode(self):
        return CommonTree(self)


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


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

        return self.token.getType()


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


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

        return self.token.getLine()


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

        else:
            return self.token.getCharPositionInLine()


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

        return self.startIndex


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


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

        return self.stopIndex


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


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

        else:
            return self.token.text

    __str__ = toString



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

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

        ret += ' '.join([child.toStringTree() for child in self.children])

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

        return ret


INVALID_NODE = CommonTree(INVALID_TOKEN)


class CommonTreeAdaptor(BaseTreeAdaptor):
    """
    @brief A TreeAdaptor that works with any Tree implementation.

    It provides
    really just factory methods; all the work is done by BaseTreeAdaptor.
    If you would like to have different tokens created than ClassicToken
    objects, you need to override this and then set the parser tree adaptor to
    use your subclass.

    To get your parser to build nodes of a different type, override
    create(Token).
    """

    def dupNode(self, treeNode):
        """
        Duplicate a node.  This is part of the factory;
        override if you want another kind of node to be built.

        I could use reflection to prevent having to override this
        but reflection is slow.
        """

        return treeNode.dupNode()


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


    def createToken(self, fromToken=None, tokenType=None, text=None):
        """
        Tell me how to create a token for use with imaginary token nodes.
        For example, there is probably no input symbol associated with imaginary
        token DECL, but you need to create it as a payload or whatever for
        the DECL node as in ^(DECL type ID).

        If you care what the token payload objects' type is, you should
        override this method and any other createToken variant.
        """

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

        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


    def hasUniqueNavigationNodes(self):
        return self.uniqueNavigationNodes


    def setUniqueNavigationNodes(self, uniqueNavigationNodes):
        self.uniqueNavigationNodes = uniqueNavigationNodes


    def consume(self):
        if self.p == -1:
            self.fillBuffer()

        self.p += 1


    def LA(self, i):
        return self.adaptor.getType(self.LT(i))


    def mark(self):
        if self.p == -1:
            self.fillBuffer()


        self.lastMarker = self.index()
        return self.lastMarker


    def release(self, marker=None):
        # no resources to release

        pass


    def index(self):
        return self.p


    def rewind(self, marker=None):
        if marker is None:
            marker = self.lastMarker

        self.seek(marker)


    def seek(self, index):
        if self.p == -1:
            self.fillBuffer()

        self.p = index


    def push(self, index):
        """
        Make stream jump to a new location, saving old location.
        Switch back with pop().  I manage dyanmic array manually
        to avoid creating Integer objects all over the place.
        """

        self.calls.append(self.p) # save current index
        self.seek(index)


    def pop(self):
        """
        Seek back to previous index saved during last push() call.
        Return top of stack (return index).
        """

        ret = self.calls.pop(-1)
        self.seek(ret)
        return ret


    def size(self):
        if self.p == -1:
            self.fillBuffer()

        return len(self.nodes)


    def __str__(self):
        """Used for testing, just return the token type stream"""

        if self.p == -1:
            self.fillBuffer()

        return ' '.join([str(self.adaptor.getType(node))
                         for node in self.nodes
                         ])


    def toString(self, start, stop):
        if start is None or stop is None:
            return None

        if self.p == -1:
            self.fillBuffer()

        #System.out.println("stop: "+stop);
        #if ( start instanceof CommonTree )
        #    System.out.print("toString: "+((CommonTree)start).getToken()+", ");
        #else
        #    System.out.println(start);
        #if ( stop instanceof CommonTree )
        #    System.out.println(((CommonTree)stop).getToken());
        #else
        #    System.out.println(stop);

        # if we have the token stream, use that to dump text in order
        if self.tokens is not None:
            beginTokenIndex = self.adaptor.getTokenStartIndex(start)
            endTokenIndex = self.adaptor.getTokenStopIndex(stop)

            # if it's a tree, use start/stop index from start node
            # else use token range from start/stop nodes
            if self.adaptor.getType(stop) == UP:
                endTokenIndex = self.adaptor.getTokenStopIndex(start)

            elif self.adaptor.getType(stop) == EOF:
                endTokenIndex = self.size() -2 # don't use EOF

            return self.tokens.toString(beginTokenIndex, endTokenIndex)

        # walk nodes looking for start
        t = None
        for i, t in enumerate(self.nodes):
            if t == start:
                break

        # now walk until we see stop, filling string buffer with text
        buf = []
        t = self.nodes[i]
        while t != stop:
            text = self.adaptor.getText(t)
            if text is None:
                text = " " + self.adaptor.getType(t)

            buf.append(text)
            i += 1
            t = self.nodes[i]

        # include stop node too
        text = self.adaptor.getText(stop)
        if text is None:
            text = " " +self.adaptor.getType(stop)

        buf.append(text)

        return ''.join(buf)


    ## iterator interface
    def __iter__(self):
        if self.p == -1:
            self.fillBuffer()

        for node in self.nodes:
            yield node


#############################################################################
#
# tree parser
#
#############################################################################

class TreeParser(BaseRecognizer):
    """@brief Baseclass for generated tree parsers.

    A parser for a stream of tree nodes.  "tree grammars" result in a subclass
    of this.  All the error reporting and recovery is shared with Parser via
    the BaseRecognizer superclass.
    """

    def __init__(self, input):
        BaseRecognizer.__init__(self)

        self.input = None
        self.setTreeNodeStream(input)


    def reset(self):
        BaseRecognizer.reset(self) # reset all recognizer state variables
        if self.input is not None:
            self.input.seek(0) # rewind the input


    def setTreeNodeStream(self, input):
        """Set the input stream"""

        self.input = input


    def getTreeNodeStream(self):
        return self.input


    def matchAny(self, ignore): # ignore stream, copy of this.input
        """
        Match '.' in tree parser has special meaning.  Skip node or
        entire tree if node has children.  If children, scan until
        corresponding UP node.
        """

        self.errorRecovery = False
        self.failed = False

        look = self.input.LT(1)
        if self.input.getTreeAdaptor().getChildCount(look) == 0:
            self.input.consume() # not subtree, consume 1 node and return
            return

        # current node is a subtree, skip to corresponding UP.
        # must count nesting level to get right UP
        level = 0
        tokenType = self.input.getTreeAdaptor().getType(look)
        while tokenType != EOF and not (tokenType == UP and level==0):
            self.input.consume()
            look = self.input.LT(1)
            tokenType = self.input.getTreeAdaptor().getType(look)
            if tokenType == DOWN:
                level += 1

            elif tokenType == UP:
                level -= 1

        self.input.consume() # consume UP


    def mismatch(self, input, ttype, follow):
        """
        We have DOWN/UP nodes in the stream that have no line info; override.
        plus we want to alter the exception type.
        """

        mte = MismatchedTreeNodeException(ttype, input)
        self.recoverFromMismatchedToken(input, mte, ttype, follow)


    def getErrorHeader(self, e):
        """
        Prefix error message with the grammar name because message is
        always intended for the programmer because the parser built
        the input tree not the user.
        """

        return self.getGrammarFileName() \
               + ": node from line " \
               + e.line + ":" + e.charPositionInLine


    def getErrorMessage(self, e, tokenNames):
        """
        Tree parsers parse nodes they usually have a token object as
        payload. Set the exception token and do the default behavior.
        """

        if isinstance(self, TreeParser):
            adaptor = e.input.getTreeAdaptor()
            e.token = adaptor.getToken(e.node)
            if e.token is not None: # could be an UP/DOWN node
                e.token = CommonToken(
                    type=adaptor.getType(e.node),
                    text=adaptor.getText(e.node)
                    )

        return BaseRecognizer.getErrorMessage(e, tokenNames)


    def traceIn(self, ruleName, ruleIndex):
        BaseRecognizer.traceIn(self, ruleName, ruleIndex, self.input.LT(1))


    def traceOut(self, ruleName, ruleIndex):
        BaseRecognizer.traceOut(self, ruleName, ruleIndex, self.input.LT(1))


#############################################################################
#
# streams for rule rewriting
#
#############################################################################

class RewriteRuleElementStream(object):
    """@brief Internal helper class.

    A generic list of elements tracked in an alternative to be used in
    a -> rewrite rule.  We need to subclass to fill in the next() method,
    which returns either an AST node wrapped around a token payload or
    an existing subtree.

    Once you start next()ing, do not try to add more elements.  It will
    break the cursor tracking I believe.

    @see org.antlr.runtime.tree.RewriteRuleSubtreeStream
    @see org.antlr.runtime.tree.RewriteRuleTokenStream

    TODO: add mechanism to detect/puke on modification after reading from
    stream
    """

    def __init__(self, adaptor, elementDescription, elements = None):
        # Cursor 0..n-1.  If singleElement!=null, cursor is 0 until you next(),
        # which bumps it to 1 meaning no more elements.
        self.cursor = 0

        # Track single elements w/o creating a list.  Upon 2nd add, alloc list
        self.singleElement = None

        # The list of tokens or subtrees we are tracking
        self.elements = None

        # The element or stream description; usually has name of the token or
        # rule reference that this list tracks.  Can include rulename too, but
        # the exception would track that info.
        self.elementDescription = elementDescription

        self.adaptor = adaptor

        if isinstance(elements, (list, tuple)):
            # Create a stream, but feed off an existing list
            self.singleElement = None
            self.elements = elements

        else:
            # Create a stream with one element
            self.add(elements)


    def reset(self):
        """
        Reset the condition of this stream so that it appears we have
        not consumed any of its elements.  Elements themselves are untouched.
        """

        self.cursor = 0

    def add(self, el):
        if el is None:
            return

        if self.elements is not None: # if in list, just add
            self.elements.append(el)
            return

        if self.singleElement is None: # no elements yet, track w/o list
            self.singleElement = el
            return

        # adding 2nd element, move to list
        self.elements = []
        self.elements.append(self.singleElement)
        self.singleElement = None
        self.elements.append(el)


    def next(self):
        """
        Return the next element in the stream.  If out of elements, throw
        an exception unless size()==1.  If size is 1, then return elements[0].

        Return a duplicate node/subtree if stream is out of elements and
        size==1.
        """

        if self.cursor >= len(self) and len(self) == 1:
            # if out of elements and size is 1, dup
            el = self._next()
            return self.dup(el)

        # test size above then fetch
        el = self._next()
        return el


    def _next(self):
        """
        do the work of getting the next element, making sure that it's
        a tree node or subtree.  Deal with the optimization of single-
        element list versus list of size > 1.  Throw an exception
        if the stream is empty or we're out of elements and size>1.
        protected so you can override in a subclass if necessary.
        """

        if len(self) == 0:
            raise RewriteEmptyStreamException(self.elementDescription)

        if self.cursor >= len(self): # out of elements?
            if len(self) == 1: # if size is 1, it's ok; return and we'll dup
                return self.singleElement

            # out of elements and size was not 1, so we can't dup
            raise RewriteCardinalityException(self.elementDescription)

        # we have elements
        if self.singleElement is not None:
            self.cursor += 1 # move cursor even for single element list
            return self.toTree(self.singleElement)

        # must have more than one in list, pull from elements
        o = self.toTree(self.elements[self.cursor])
        self.cursor += 1
        return o


    def dup(self, el):
        """
        When constructing trees, sometimes we need to dup a token or AST
        subtree.  Dup'ing a token means just creating another AST node
        around it.  For trees, you must call the adaptor.dupTree().
        """

        raise NotImplementedError


    def toTree(self, el):
        """
        Ensure stream emits trees; tokens must be converted to AST nodes.
        AST nodes can be passed through unmolested.
        """

        return el


    def hasNext(self):
        return ( (self.singleElement is not None and self.cursor < 1)
                 or (self.elements is not None and self.cursor < len(self.elements))
                 )


    def size(self):
        if self.singleElement is not None:
            return 1

        if self.elements is not None:
            return len(self.elements)

        return 0

    __len__ = size


    def getDescription(self):
        """Deprecated. Directly access elementDescription attribute"""

        return self.elementDescription


class RewriteRuleTokenStream(RewriteRuleElementStream):
    """@brief Internal helper class."""

    def toTree(self, el):
        return self.adaptor.createWithPayload(el)


    def dup(self, el):
        return self.adaptor.createWithPayload(el)


class RewriteRuleSubtreeStream(RewriteRuleElementStream):
    """@brief Internal helper class."""

    def nextNode(self):
        """
        Treat next element as a single node even if it's a subtree.
        This is used instead of next() when the result has to be a
        tree root node.  Also prevents us from duplicating recently-added
        children; e.g., ^(type ID)+ adds ID to type and then 2nd iteration
        must dup the type node, but ID has been added.

        Referencing a rule result twice is ok; dup entire tree as
        we can't be adding trees; e.g., expr expr.
        """

        el = self._next()

        if self.cursor >= len(self) and len(self) == 1:
            # if out of elements and size is 1, dup just the node
            el = self.adaptor.dupNode(el)

        return el


    def dup(self, el):
        return self.adaptor.dupTree(el)


