#!/usr/bin/env python

# SAWBONES: Cat's Eye Technologies' reference implementation of SICKBAY.
# This work is in the public domain; see UNLICENSE for more information.

from optparse import OptionParser
import random
import re
import sys


DEBUG = False


class AST(object):
    def __init__(self, type, children=None, value=None):
        self.type = type
        self.value = value
        if children is not None:
            self.children = children
        else:
            self.children = []

    def add_child(self, item):
        self.children.append(item)

    def __repr__(self):
        if self.value is None:
            return 'AST(%r,%r)' % (self.type, self.children)
        if not self.children:
            return 'AST(%r,value=%r)' % (self.type, self.value)
        return 'AST(%r,%r,value=%r)' % (self.type, self.children, self.value)


class Scanner(object):
    """
    >>> a = Scanner("  (++ )  FOO  ")
    >>> a.token
    '('
    >>> a.type
    'goose egg'
    >>> a.scan()
    >>> a.on("+")
    True
    >>> a.on_type('operator')
    True
    >>> a.check_type('identifier')
    Traceback (most recent call last):
    ...
    SyntaxError: Expected identifier, but found operator ('+')
    >>> a.scan()
    >>> a.scan()
    >>> a.consume(".")
    False
    >>> a.consume(")")
    True
    >>> a.expect("FOO")
    >>> a.type
    'EOF'
    >>> a.expect("bar")
    Traceback (most recent call last):
    ...
    SyntaxError: Expected 'bar', but found 'None'

    """
    def __init__(self, text):
        self.text = text
        self.token = None
        self.type = None
        self.scan()

    def scan_pattern(self, pattern, type, token_group=1, rest_group=2):
        pattern = r'^(' + pattern + r')(.*?)$'
        match = re.match(pattern, self.text, re.DOTALL)
        if not match:
            return False
        else:
            self.type = type
            self.token = match.group(token_group)
            self.text = match.group(rest_group)
            # print >>sys.stderr, "(%r/%s->%r)" % (self.token, self.type, self.text)
            return True

    def scan(self):
        self.scan_pattern(r'[ \t]*', 'whitespace')
        if not self.text:
            self.token = None
            self.type = 'EOF'
            return
        if self.scan_pattern(r'REM[^\r\n]*', 'remark'):
            return
        if self.scan_pattern(r'[\r\n]+', 'newline'):
            return
        if self.scan_pattern(r'\*|\/|\+|\-', 'operator'):
            return
        if self.scan_pattern(r':|\;|\(|\)|\=', 'goose egg'):
            return
        if self.scan_pattern(r'\d+', 'integer literal'):
            return
        if self.scan_pattern(r'\"(.*?)\"', 'string literal',
                             token_group=2, rest_group=3):
            return
        if self.scan_pattern(r'[A-Z][A-Z0-9]?\%', 'identifier'):
            return
        if self.scan_pattern(r'[A-Z]+\$?\%?', 'command'):
            return
        if self.scan_pattern(r'.', 'unknown character'):
            return
        else:
            raise ValueError("this should never happen, self.text=(%s)" % self.text)

    def expect(self, token):
        if self.token == token:
            self.scan()
        else:
            raise SyntaxError("Expected '%s', but found '%s'" %
                              (token, self.token))

    def expect_type(self, type):
        self.check_type(type)
        self.scan()

    def on(self, token):
        return self.token == token

    def on_type(self, type):
        return self.type == type

    def check_type(self, type):
        if not self.type == type:
            raise SyntaxError("Expected %s, but found %s ('%s')" %
                              (type, self.type, self.token))

    def consume(self, token):
        if self.token == token:
            self.scan()
            return True
        else:
            return False


class Parser(object):
    """
    >>> a = Parser("123")
    >>> a.expr()
    AST('IntLit',value=123)

    >>> a = Parser("A% ( 7 )")
    >>> a.intvar()
    AST('IntVar',[AST('IntLit',value=7)],value='A%')

    >>> a = Parser("(A%/(7+B%(4)))")
    >>> a.expr()
    AST('IntOp',[AST('IntVar',[AST('IntLit',value=0)],value='A%'), AST('IntOp',[AST('IntLit',value=7), AST('IntVar',[AST('IntLit',value=4)],value='B%')],value='+')],value='/')

    >>> a = Parser("(0-100) PRINT 4;:REM YES:PRINT 5")
    >>> a.line()
    AST('Line',[AST('IntOp',[AST('IntLit',value=0), AST('IntLit',value=100)],value='-'), AST('PrintIntExpr',[AST('IntLit',value=4)]), AST('Remark',value='REM YES:PRINT 5')])

    """
    def __init__(self, text):
        self.scanner = Scanner(text)

    def program(self):
        lines = []
        count = 0
        while not self.scanner.on_type('EOF'):
            lines.append((count, self.line()))
            count += 1
        return lines

    def line(self):
        expr = self.expr()
        stmts = []
        stmts.append(self.stmt())
        while self.scanner.consume(':'):
            stmts.append(self.stmt())
        if not self.scanner.on_type('EOF'):
            self.scanner.expect_type('newline')
        return AST('Line', [expr] + stmts)

    def stmt(self):
        if self.scanner.on_type('remark'):
            s = AST('Remark', value=self.scanner.token)
            self.scanner.scan()
            return s
        if self.scanner.consume("PRINT"):
            s = None
            if self.scanner.on_type('string literal'):
                st = self.scanner.token
                self.scanner.scan()
                s = AST('PrintString', value=st)
            elif self.scanner.on("CHR$"):
                self.scanner.scan()
                subj = self.expr()
                s = AST('PrintChar', [subj])
            else:
                subj = self.expr()
                s = AST('PrintIntExpr', [subj])
            if self.scanner.on(';'):
                self.scanner.scan()
            else:
                s = AST('PrintNewline', [s])
            return s
        if self.scanner.consume("INPUT"):
            s = None
            if self.scanner.on("CHR$"):
                self.scanner.scan()
                return AST('InputChar', [self.intvar()])
            else:
                return AST('InputInt', [self.intvar()])
        elif self.scanner.consume("GOTO"):
            dest = self.intlit()
            return AST('Goto', [dest])
        elif self.scanner.consume("GOSUB"):
            dest = self.intlit()
            return AST('Gosub', [dest])
        elif self.scanner.consume("RETURN") or self.scanner.consume("END"):
            return AST('Return')
        elif self.scanner.consume("PROLONG"):
            dest = self.intlit()
            return AST('Prolong', [dest])
        elif self.scanner.consume("CUTSHORT"):
            return AST('Cutshort')
        elif self.scanner.consume("DIM"):
            self.scanner.expect("RING")
            self.scanner.expect("(")
            e = self.expr()
            self.scanner.expect(")")
            return AST('DimRing', [e])
        elif self.scanner.consume("LET"):
            var = self.intvar()
            self.scanner.expect('=')
            subj = self.expr()
            return AST('Assign', [var, subj])
        else:
            raise ValueError("stmt? %s" % self.scanner.token)

    def expr(self):
        if self.scanner.on_type('identifier'):
            return self.intvar()
        elif self.scanner.on_type('integer literal'):
            return self.intlit()
        elif self.scanner.consume('RND%'):
            self.scanner.expect('(')
            e = self.expr()
            self.scanner.expect(')')
            return AST('Random', [e])
        else:
            self.scanner.expect('(')
            e1 = self.expr()
            self.scanner.check_type('operator')
            op = self.scanner.token
            self.scanner.scan()
            e2 = self.expr()
            self.scanner.expect(')')
            return AST('IntOp', [e1, e2], value=op)

    def intlit(self):
        self.scanner.check_type('integer literal')
        s = AST('IntLit', value=int(self.scanner.token))
        self.scanner.scan()
        return s

    def intvar(self):
        self.scanner.check_type('identifier')
        id = self.scanner.token
        self.scanner.scan()
        index = AST('IntLit', value=0)
        if self.scanner.consume('('):
            index = self.expr()
            self.scanner.expect(')')
        return AST('IntVar', [index], value=id)


def eval_expr(e, store):
    """
    >>> eval_expr(Parser("123").expr(), {})
    123

    >>> eval_expr(Parser("(((10-3)*7)+1)").expr(), {})
    50

    >>> eval_expr(Parser("A%").expr(), {})
    0

    >>> eval_expr(Parser("A%").expr(), {'A%': {99: 99}})
    0

    >>> eval_expr(Parser("A%").expr(), {'A%': {0: 77}})
    77

    >>> eval_expr(Parser("A% (7)").expr(), {'A%': {7: 88}})
    88

    """
    if e.type == 'IntLit':
        return e.value
    elif e.type == 'IntVar':
        index = eval_expr(e.children[0], store)
        return store.get(e.value, {}).get(index, 0)
    elif e.type == 'Random':
        rg = eval_expr(e.children[0], store)
        return random.randint(0, rg-1)
    elif e.type == 'IntOp':
        lhs = eval_expr(e.children[0], store)
        rhs = eval_expr(e.children[1], store)
        if e.value == '+':
            return lhs + rhs
        elif e.value == '-':
            return lhs - rhs
        elif e.value == '*':
            return lhs * rhs
        elif e.value == '/':
            if rhs == 0:
                return 0
            else:
                return lhs // rhs
        else:
            raise NotImplementedError(e.value)


def eval_ref(e, store):
    """
    >>> eval_ref(Parser("A%(B%)").expr(), {'B%': {0: 88}})
    ('A%', 88)

    """
    if e.type == 'IntVar':
        index = eval_expr(e.children[0], store)
        return (e.value, index)
    else:
        raise NotImplementedError(e.value)


def read_int(infile):
    s = ''
    c = infile.read(1)
    while c in (' ', '\t', '\r', '\n'):
        c = infile.read(1)
    if c == '-':
        s += '-'
        c = infile.read(1)
    while c in ('0', '1', '2', '3', '4', '5', '6', '7', '8', '9'):
        s += c
        c = infile.read(1)
    if c not in (' ', '\t', '\r', '\n'):
        raise ValueError('bad integer')
    return int(s)


def exec_stmt(stmt, store, ring, infile=sys.stdin, outfile=sys.stdout):
    r"""
    >>> try:
    ...     # Python 2
    ...     from StringIO import StringIO
    ... except ImportError:
    ...     # Python 3
    ...     from io import StringIO

    >>> out = StringIO()
    >>> exec_stmt(Parser('PRINT "HI"').stmt(), {'B%': {0: 88}}, None, outfile=out)
    >>> out.getvalue()
    'HI\n'

    >>> out = StringIO()
    >>> exec_stmt(Parser('PRINT (2+3);').stmt(), {'B%': {0: 88}}, None, outfile=out)
    >>> out.getvalue()
    '5'

    >>> out = StringIO()
    >>> exec_stmt(Parser('PRINT (B%/4);').stmt(), {'B%': {0: 88}}, None, outfile=out)
    >>> out.getvalue()
    '22'

    >>> out = StringIO()
    >>> exec_stmt(Parser('PRINT CHR$ 65;').stmt(), {'B%': {0: 88}}, None, outfile=out)
    >>> out.getvalue()
    'A'

    >>> store = {}
    >>> exec_stmt(Parser('LET A% = 15').stmt(), store, None)
    >>> store
    {'A%': {0: 15}}

    >>> store = {'B%': {9: 88}}
    >>> inp = StringIO('too')
    >>> exec_stmt(Parser('INPUT CHR$ B%(9)').stmt(), store, None, infile=inp)
    >>> store
    {'B%': {9: 116}}
    >>> exec_stmt(Parser('INPUT CHR$ B%(9)').stmt(), store, None, infile=inp)
    >>> store
    {'B%': {9: 111}}

    >>> store = {}
    >>> inp = StringIO('  -23  A')
    >>> exec_stmt(Parser('INPUT A%').stmt(), store, None, infile=inp)
    >>> store
    {'A%': {0: -23}}
    >>> exec_stmt(Parser('INPUT CHR$ A%').stmt(), store, None, infile=inp)
    >>> store
    {'A%': {0: 32}}
    >>> exec_stmt(Parser('INPUT CHR$ A%').stmt(), store, None, infile=inp)
    >>> store
    {'A%': {0: 65}}

    >>> store = {}
    >>> inp = StringIO('5x')
    >>> exec_stmt(Parser('INPUT A%').stmt(), store, None, infile=inp)
    Traceback (most recent call last):
    ...
    ValueError: bad integer

    """
    if stmt.type == 'PrintNewline':
        exec_stmt(stmt.children[0], store, ring, infile, outfile)
        outfile.write('\n')
    elif stmt.type == 'PrintString':
        outfile.write(stmt.value)
    elif stmt.type == 'PrintChar':
        outfile.write(chr(eval_expr(stmt.children[0], store)))
    elif stmt.type == 'PrintIntExpr':
        outfile.write(str(eval_expr(stmt.children[0], store)))
    elif stmt.type == 'InputChar':
        (name, index) = eval_ref(stmt.children[0], store)
        value = ord(infile.read(1))
        store.setdefault(name, {})[index] = value
    elif stmt.type == 'InputInt':
        (name, index) = eval_ref(stmt.children[0], store)
        value = read_int(infile)
        store.setdefault(name, {})[index] = value
    elif stmt.type == 'Assign':
        value = eval_expr(stmt.children[1], store)
        (name, index) = eval_ref(stmt.children[0], store)
        store.setdefault(name, {})[index] = value
    elif stmt.type == 'Goto':
        return ('goto', eval_expr(stmt.children[0], store))
    elif stmt.type == 'Gosub':
        return ('gosub', eval_expr(stmt.children[0], store))
    elif stmt.type == 'Prolong':
        ring.prolong(eval_expr(stmt.children[0], store))
    elif stmt.type == 'Return':
        return ('return', 0)
    elif stmt.type == 'Cutshort':
        if ring.is_empty():
            return ('return', 0)
        ring.cutshort()
    elif stmt.type == 'DimRing':
        ring.dim(eval_expr(stmt.children[0], store))
    elif stmt.type == 'Remark':
        return None
    else:
        raise NotImplementedError(stmt.type)


def exec_line(line, store, ring, infile=sys.stdin, outfile=sys.stdout):
    r"""
    >>> try:
    ...     # Python 2
    ...     from StringIO import StringIO
    ... except ImportError:
    ...     # Python 3
    ...     from io import StringIO

    >>> out = StringIO()
    >>> exec_line(Parser('10 PRINT "HI";:PRINT "LO"').line(), {}, None, outfile=out)
    >>> out.getvalue()
    'HILO\n'

    >>> out = StringIO()
    >>> exec_line(Parser('(0-50) PRINT "HI":GOTO 50').line(), {}, None, outfile=out)
    ('goto', 50)
    >>> out.getvalue()
    'HI\n'

    >>> out = StringIO()
    >>> exec_line(Parser('10 GOSUB 50:PRINT "HI"').line(), {}, None, outfile=out)
    ('gosub', 50)
    >>> out.getvalue()
    ''

    >>> out = StringIO()
    >>> exec_line(Parser('1 LET A%(23)=5:PRINT A%(23)').line(), {}, None, outfile=out)
    >>> out.getvalue()
    '5\n'

    """
    r = None
    for stmt in line.children[1:]:
        r = exec_stmt(stmt, store, ring, infile=infile, outfile=outfile)
        if r is not None:
            break
    return r


class RingBuffer(object):
    """
    >>> r = RingBuffer()
    >>> r.push(100)
    >>> r.push(200)
    >>> r.pop()
    200
    >>> r.push(300)
    >>> r.cutshort()
    100
    >>> r.prolong(90)
    >>> r.pop()
    300
    >>> r.pop()
    90
    >>> r.pop()
    Traceback (most recent call last):
    ...
    ValueError: ring buffer empty

    >>> r = RingBuffer()
    >>> r.push(100)
    >>> r.capacity
    10
    >>> r.capacity = 2
    >>> r.push(200)
    >>> r.push(300)
    Traceback (most recent call last):
    ...
    ValueError: ring buffer full

    """
    def __init__(self):
        # THIS IS SOOOOOO CHEATING
        self.buffer = []
        self.capacity = None

    def is_empty(self):
        return not self.buffer

    def dim(self, capacity):
        if self.capacity is not None:
            raise ValueError("already dim'ed")
        self.capacity = capacity

    def pop(self):
        if not self.capacity:
            self.dim(10)
        if not self.buffer:
            raise ValueError("ring buffer empty")
        x = self.buffer.pop()
        return x

    def push(self, x):
        if not self.capacity:
            self.dim(10)
        self.buffer.append(x)
        if len(self.buffer) > self.capacity:
            raise ValueError("ring buffer full")

    def cutshort(self):
        if not self.capacity:
            self.dim(10)
        if not self.buffer:
            raise ValueError("ring buffer empty")
        return self.buffer.pop(0)

    def prolong(self, x):
        if not self.capacity:
            self.dim(10)
        self.buffer.insert(0, x)
        if len(self.buffer) > self.capacity:
            raise ValueError("ring buffer full")


class Lines(object):
    def __init__(self, prog, store):
        tmp = []
        self.smallest = None
        self.largest = None
        for (text_line, line) in prog:
            line_no = eval_expr(line.children[0], store)
            if self.smallest is None or line_no < self.smallest:
                self.smallest = line_no
            if self.largest is None or line_no > self.largest:
                self.largest = line_no
            tmp.append((line_no, text_line, line))
        self.lines = sorted(tmp)
        if DEBUG:
            for (line_no, text_line, line) in self.lines:
                print(line_no, text_line, str(line.children[1])[:50] + '...')

    def seek_line_number(self, line_number):
        i = 0
        while i < len(self.lines):
            if self.lines[i][0] > line_number:
                return self.lines[i][0]
            i += 1
        return None

    def __getitem__(self, line_number):
        for line in self.lines:
            if line[0] == line_number:
                return line[2]
        raise ValueError("line number %d not present" % line_number)


def exec_program(prog, store, ring, infile=sys.stdin, outfile=sys.stdout):
    def re_tu_rn():
        if ring.is_empty():
            return None
        dest = ring.pop()
        line_number = lines.seek_line_number(dest)
        if line_number is None:
            raise ValueError("line number %d beyond end of program" % dest)
        return line_number

    lines = Lines(prog, store)
    line_number = lines.smallest
    done = False
    while not done:
        line = lines[line_number]
        r = exec_line(line, store, ring, infile=infile, outfile=outfile)
        lines = Lines(prog, store)
        if r is None:
            line_number = lines.seek_line_number(line_number)
            if line_number is None:
                line_number = re_tu_rn()
                if line_number is None:
                    return
        elif r[0] == 'goto':
            line_number = r[1]
        elif r[0] == 'gosub':
            ring.push(line_number + 1)
            line_number = r[1]
        elif r[0] == 'return':
            line_number = re_tu_rn()
            if line_number is None:
                return
        else:
            raise NotImplementedError
        if DEBUG:
            print("AT LINE %d" % line_number)


def main(argv):
    optparser = OptionParser(__doc__)
    optparser.add_option("-a", "--show-ast",
                         action="store_true", dest="show_ast", default=False,
                         help="show parsed AST instead of evaluating")
    optparser.add_option("-t", "--test",
                         action="store_true", dest="test", default=False,
                         help="run test cases and exit")
    (options, args) = optparser.parse_args(argv[1:])
    if options.test:
        import doctest
        (fails, something) = doctest.testmod(verbose=True)
        if fails == 0:
            print("All tests passed.")
            sys.exit(0)
        else:
            sys.exit(1)
    file = open(args[0])
    text = file.read()
    file.close()
    p = Parser(text)
    prog = p.program()
    if options.show_ast:
        from pprint import pprint
        pprint(prog)
        sys.exit(0)
    ring = RingBuffer()
    exec_program(prog, {}, ring)
    sys.exit(0)


if __name__ == "__main__":
    main(sys.argv)