import sys
from annast import *
from TAC_serialize import *
from graphsort import *

#const mapping from AST tokens to TAC tokens
astTacMap = {
    'not' :     'not',
    'negate' :  '~',
    'isvoid' :  'isvoid',
    'plus' :    '+',
    'minus' :   '-',
    'times' :   '*',
    'divide' :  '/',
    'lt' :      '<',
    'le' :      '<=',
    'eq' :      '=',
    'integer' : 'int',
    'string' :  'string',
    'true' :    'bool',
    'false' :   'bool',
}

#manager for all the data global to expression generation function calls
#  using a static class because I have an aversion to many global vars
class TACIndexer:
    cname = ''      #class name for current instructions
    mname = ''      #method name for current instructions
    lind = 0        #counter for labels
    rind = 0        #counter for registers
    varRegMap = {}  #symbol table, map string var => lst of string registers bound to var
    classAttrs = {} #string class name => (string attr names => TACClassAttr obj)
    inslst = []     #list of TACInstruction

    cmap = {}       #class map
    imap = {}       #implementation map
    pmap = {}       #parent map

    returnReg = TACRegister('t0')

    @staticmethod
    def setTypeMaps(cmap, imap, pmap):
        TACIndexer.cmap = cmap
        TACIndexer.imap = imap
        TACIndexer.pmap = pmap

    #resets counters and sets the names for labels
    @staticmethod
    def init(cname, mname):
        #TACIndexer.rind = 0
        TACIndexer.lind = 0
        TACIndexer.cname = cname
        TACIndexer.mname = mname

    @staticmethod
    def addClassAttr(cname, attrname, boxed = True):
        if cname not in TACIndexer.classAttrs:
            TACIndexer.classAttrs[cname] = {}
        TACIndexer.classAttrs[cname][attrname] = boxed

    #increments a counter and returns a string label
    @staticmethod
    def label():
        TACIndexer.lind += 1
        return "." + TACIndexer.cname + '.' + TACIndexer.mname + '_' + str(TACIndexer.lind)

    #increments a counter a returns a register label
    @staticmethod
    def reg():
        TACIndexer.rind += 1
        return TACRegister('t' + str(TACIndexer.rind))

    #looks up the symbol table for var; creates new register if forceNew or not found
    @staticmethod
    def map(var, forceNew = False):
        if var not in TACIndexer.varRegMap:
            TACIndexer.varRegMap[var] = []
        if len(TACIndexer.varRegMap[var]) == 0 or forceNew:
            if not forceNew and var in TACIndexer.classAttrs[TACIndexer.cname]:
                reg= TACClassAttr(TACIndexer.map('self'), TACIndexer.cname, var)
                reg.boxed = TACIndexer.classAttrs[TACIndexer.cname][var]
                return reg
            else:
                reg = TACIndexer.reg()
                TACIndexer.varRegMap[var].append(reg)
        return TACIndexer.varRegMap[var][-1]

    #binds a symbol to an existing register, provided as an arg
    @staticmethod
    def bind(var, reg):
        if var not in TACIndexer.varRegMap:
            TACIndexer.varRegMap[var] = []
        TACIndexer.varRegMap[var].append(reg)

    #unbinds a symbol table entry for var
    @staticmethod
    def pop(var):
        TACIndexer.varRegMap[var].pop()

    #adds a TACInstruction to the list
    @staticmethod
    def pushIns(ins):
        TACIndexer.inslst.append(ins)

#recursive routine for generating TAC for expressions
def expConvert(node):

    if node.expr == 'while':
        #emit label for loop start (computing predicate)
        lbp = TACIndexer.label()
        TACIndexer.pushIns(TACLabel(lbp))
        #recurse on predicate expression
        regp = expConvert(node.args[0])
        regp = unbox(regp, node.args[0].type)
        #emit label for loop breakout -- if predicate is false, we jump there
        lbb = TACIndexer.label()
        regpbar = TACIndexer.reg()
        regpbar.boxed = False
        TACIndexer.pushIns(TACOp1(regpbar, 'not', regp))
        TACIndexer.pushIns(TACBT(regpbar, lbb))
        #recurse on body expression
        regb = expConvert(node.args[1])
        #generate jump back to top
        TACIndexer.pushIns(TACJmp(lbp))
        #generate the breakout label
        TACIndexer.pushIns(TACLabel(lbb))
        #create a default (void) as the return value
        reg = TACIndexer.reg()
        TACIndexer.pushIns(TACAllocate(reg, 'default', 'Object'))
        return reg

    elif node.expr == 'if':
        #recurse on predicate expression
        regp = expConvert(node.args[0])
        regp = unbox(regp, 'Bool')
        regpbar = TACIndexer.reg()
        regpbar.boxed = False
        TACIndexer.pushIns(TACAssign(regpbar, regp))
        TACIndexer.pushIns(TACOp1(regpbar, 'not', regpbar))
        #emit label for else and branch there if predicate is false
        #NOTE I generate then first for readability, we can save the not op by doing else first
        lbe = TACIndexer.label()
        TACIndexer.pushIns(TACBT(regpbar, lbe))
        #recurse on then body, emit join label and jump there at end
        #also, place then result into join register
        regt = expConvert(node.args[1])
        regj = TACIndexer.reg()
        # Do auto-boxing of result
        if node.type not in ['Int', 'Bool']:
            regt = box(regt, node.args[1].type)
        else:
            regt = unbox(regt, node.args[1].type)
            regj.boxed = False
        TACIndexer.pushIns(TACAssign(regj, regt))

        lbj = TACIndexer.label()
        TACIndexer.pushIns(TACJmp(lbj))

        #insert label for else
        TACIndexer.pushIns(TACLabel(lbe))
        #recurse on else body
        rege = expConvert(node.args[2])
        # Do auto-boxing of result
        if node.type not in ['Int', 'Bool']:
            rege = box(rege, node.args[2].type)
        else:
            rege = unbox(rege, node.args[2].type)
        #place result into join register
        TACIndexer.pushIns(TACAssign(regj, rege))
        #insert join label
        TACIndexer.pushIns(TACLabel(lbj))
        return regj

    elif node.expr == 'let':
        # Bind the let vars
        for binding in node.args[0]:

            if binding.init is not None:
                # if there is an init, generate the init code
                regi = expConvert(binding.init)

                #create reg here so previous binding holds in init expr
                reg = TACIndexer.map(binding.name.name,True)
                if binding.type.name in ['Int', 'Bool']:
                    reg.boxed = False
                else:
                    reg.boxed = True

                if reg.boxed:
                    regi = box(regi, binding.init.type)
                else:
                    regi = unbox(regi, binding.init.type)
                TACIndexer.pushIns(TACAssign(reg,regi))
            else:

                #create reg here so previous binding holds in init expr
                reg = TACIndexer.map(binding.name.name,True)
                if binding.type.name in ['Int', 'Bool']:
                    reg.boxed = False
                else:
                    reg.boxed = True
                #otherwise generate default init
                if reg.boxed:
                    if binding.type.name == 'String':
                        regn = TACIndexer.reg()
                        TACIndexer.pushIns(TACAllocate(regn, 'default', binding.type.name))
                        TACIndexer.pushIns(TACAssign(reg, regn))
                    else:
                        TACIndexer.pushIns(TACAllocate(reg,'default',binding.type.name))
                else:
                    TACIndexer.pushIns(TACConstant(reg, 'int', 0))
        # Generate the body code
        regr = expConvert(node.args[1])
        # Unbind the let vars
        for binding in node.args[0]:
            TACIndexer.pop(binding.name.name)
        return regr

    elif node.expr == 'case':
        #generate case object expression
        regc = expConvert(node.args[0])
        if isinstance(regc, TACClassAttr):
            attreg = TACIndexer.reg()
            TACIndexer.pushIns(TACAssign(attreg, regc))
            attreg.boxed = regc.boxed
            regc = attreg
        #avoid void check if we know it is primitive or self
        if regc.boxed or node.args[0].type not in ['String', 'Int', 'Bool', 'SELF_TYPE']:
            #fail if case "caller" is void
            regv = TACIndexer.reg()
            regv.boxed = False
            lbc = TACIndexer.label()
            TACIndexer.pushIns(TACAssign(regv, regc))
            TACIndexer.pushIns(TACOp1(regv, 'isvoid', regv))
            TACIndexer.pushIns(TACOp1(regv, 'not', regv))
            TACIndexer.pushIns(TACBT(regv, lbc))
            TACIndexer.pushIns(TACError(node.line, 'casevoid'))
            TACIndexer.pushIns(TACLabel(lbc))
        #box case object
        regc = box(regc, node.args[0].type)
        #find which branch types can be possibly taken based on static type of obj
        btypesall = [branch.type.name for branch in node.args[1]]
        caseobjtype = node.args[0].type
        if node.args[0].type == 'SELF_TYPE':
            caseobjtype = TACIndexer.cname  #we could be more restrictive on subclasses inheriting exp
        #branch types which MUST be taken (static type conforms to branch type)
        btypes1 = [clsname for clsname in btypesall if caseobjtype in subtreeList(clsname, TACIndexer.pmap)]
        #branch types which might be taken (branch type conforms to static type)
        btypes2 = [clsname for clsname in btypesall if clsname in subtreeList(caseobjtype, TACIndexer.pmap) \
            and clsname not in btypes1]
        btypes = btypes1 + btypes2
        #if we only have one branch and it must be taken, omit join label and type checks
        needcheck = not (len(btypes2) == 0 and len(btypes1) == 1)
        if needcheck:
            #generate labels for branches, and record branch types
            blabels = [TACIndexer.label() for i in range(len(btypes))]
            #generate type evaluation to find least type and jump to appropriate label
            #   reverse toposort to get least to greatest order
            usedtypes = set()
            for clsname in reversed(toposort(TACIndexer.pmap)):
                if clsname not in btypes:
                    continue
                ind = btypes.index(clsname)
                sublst = subtreeList(clsname, TACIndexer.pmap)
                for subclsname in sublst:
                    if subclsname in usedtypes:
                        continue
                    usedtypes.add(subclsname)
                    TACIndexer.pushIns(TACBTypeEq(regc, subclsname, blabels[ind]))

        #if no branches that must be taken exist we generate the fallthrough case
        if len(btypes1) == 0:
            #fail if no type found
            TACIndexer.pushIns(TACError(node.line, 'casenomatch'))

        #generate join label
        lbj = TACIndexer.label()
        #create join reg
        regj = TACIndexer.reg()
        #loop over branches: emit label, generate code, result in join reg + jump to join label
        for i in range(len(btypes)):
            btype = btypes[i]
            branch = [br for br in node.args[1] if br.type.name == btype][0]
            if needcheck:
                TACIndexer.pushIns(TACLabel(blabels[i]))
            regci = TACIndexer.map(branch.name.name, True)
            TACIndexer.pushIns(TACAssign(regci, regc))
            regb = expConvert(branch.body)
            if node.type in ['Bool', 'Int']:
                regb = unbox(regb, branch.type.name)
                regj.boxed = False
            else:
                regb = box(regb, branch.type.name)
            TACIndexer.pop(branch.name.name)
            if needcheck:
                TACIndexer.pushIns(TACAssign(regj, regb))
                TACIndexer.pushIns(TACJmp(lbj))
            else:
                return regb
        if needcheck:
            #emit join label
            TACIndexer.pushIns(TACLabel(lbj))
        return regj

    elif node.expr == 'block':
        for sexpr in node.args:
            reg = expConvert(sexpr)
        return reg  #last expression evaluated is the return val

    elif node.expr == 'assign':
        regr = expConvert(node.args[1])
        reg = TACIndexer.map(node.args[0].name)
        if reg.boxed:
            regr = box(regr, node.args[1].type)
        else:
            regr = unbox(regr, node.args[1].type)
        TACIndexer.pushIns(TACAssign(reg, regr))
        return regr

    elif node.expr == 'isvoid':
        regr = expConvert(node.args)

        if isinstance(regr, TACClassAttr):
            attreg = TACIndexer.reg()
            TACIndexer.pushIns(TACAssign(attreg, regr))
            attreg.boxed = regr.boxed
            regr = attreg

        op1 = TACIndexer.reg()
        op1.boxed = False
        if not regr.boxed or node.args.type in ['String', 'Int', 'Bool', 'SELF_TYPE']:
            #isvoid is always false for primitives
            TACIndexer.pushIns(TACConstant(op1, 'bool', 'false'))
        else:
            TACIndexer.pushIns(TACOp1(op1, astTacMap[node.expr], regr))
        return op1

    #for negate and not only
    elif node.expr in ASTExpression.exp1:
        op1 = TACIndexer.reg()
        reg1 = expConvert(node.args)
        TACIndexer.pushIns(TACAssign(op1, reg1))
        op1.boxed = reg1.boxed
        op1 = unbox(op1, node.args.type)

        TACIndexer.pushIns(TACOp1(op1, astTacMap[node.expr], op1))
        return op1

    elif node.expr in ASTExpression.exp2:
        regr1 = expConvert(node.args[0])
        regr2 = expConvert(node.args[1])

        op1 = TACIndexer.reg()
        op2 = TACIndexer.reg()

        TACIndexer.pushIns(TACAssign(op1,regr1))
        TACIndexer.pushIns(TACAssign(op2,regr2))
        op1.boxed = regr1.boxed
        op2.boxed = regr2.boxed

        op1 = unbox(op1, node.args[0].type)
        op2 = unbox(op2, node.args[1].type)

        resreg = TACIndexer.reg()
        #check if divisor is zero, and if so, err and exit
        if node.expr == 'divide':
            regz = TACIndexer.reg()
            regz.boxed = False
            rege = TACIndexer.reg()
            rege.boxed = False
            regebar = TACIndexer.reg()
            regebar.boxed = False
            lba = TACIndexer.label()
            TACIndexer.pushIns(TACConstant(regz, 'int', '0'))
            TACIndexer.pushIns(TACCompare(regz, '=', op2, regz, 'Int'))
            TACIndexer.pushIns(TACOp1(regz, 'not', regz))
            TACIndexer.pushIns(TACBT(regz, lba))
            TACIndexer.pushIns(TACError(node.line, 'dividezero'))
            TACIndexer.pushIns(TACLabel(lba))
        if node.expr in ['plus','minus','times','divide']:
            #abuse of notation - for non-commutative operators, having op2 as 1st operand is useful
            TACIndexer.pushIns(TACOp2(op1, astTacMap[node.expr], op2, op1))
            TACIndexer.pushIns(TACAssign(resreg, op1))
            resreg.boxed = False
        else:
            #must be comparison operator, so use a subclass that captures the static type
            ptype = ''
            if node.args[0].type == 'Int' or node.args[0].type == 'Bool':
                ptype = 'Int'   #ordinary binary compare
            elif node.args[0].type == 'String':
                ptype = 'String'    #lexographical compare
            else:
                ptype = 'Object'    #pointer compare
            TACIndexer.pushIns(TACCompare(op2, astTacMap[node.expr], op1, op2, ptype))
            TACIndexer.pushIns(TACAssign(resreg, op2))
            resreg.boxed = False


        return resreg

    #all dispatch follows form:
    #   generate all explicit parameters of function (regs)
    #   generate the caller of function (regc)
    #   check if caller is void, and if so, err and exit
    #   prepend exec as the self param to regs
    #   find function to call in vtable if necessary
    #   call function and assign result into new register
    elif node.expr == 'dynamic_dispatch':
        # Find method in imap
        cname = node.args[0].type if node.args[0].type != "SELF_TYPE" else TACIndexer.cname
        meth = None
        for m in TACIndexer.imap[cname]:
            if m.name == node.args[1].name:
                meth = m
                break
        # Box Int/Bool args only if they are used for Object parameter
        regs = []
        for i, e in enumerate(node.args[2]):
            r = expConvert(e)
            if meth.formalTypes[i] in ['Int', 'Bool']:
                r = unbox(r, e.type)
            else:
                r = box(r, e.type)
            regs.append(r)

        regc = expConvert(node.args[0])

        if node.args[0].type in ['Int', 'Bool']:
            reg = TACIndexer.reg()
            if node.args[1].name == 'type_name':
                TACIndexer.pushIns(TACConstant(reg, 'string', node.args[0].type))
                return reg
            if node.args[1].name == 'copy':
                TACIndexer.pushIns(TACAssign(reg, regc))
                reg.boxed = regc.boxed
                return reg

        regc = box(regc, node.args[0].type)
        if node.args[0].type not in ['Int', 'Bool', 'String', 'SELF_TYPE']:
            regv = TACIndexer.reg()
            regvbar = TACIndexer.reg()
            lbd = TACIndexer.label()
            TACIndexer.pushIns(TACOp1(regv, 'isvoid', regc))
            TACIndexer.pushIns(TACOp1(regvbar, 'not', regv))
            TACIndexer.pushIns(TACBT(regvbar, lbd))
            TACIndexer.pushIns(TACError(node.line, 'dispatchvoid'))
            TACIndexer.pushIns(TACLabel(lbd))
        regs = [regc] + regs
        if node.args[0].type not in ['Int', 'Bool', 'String']:
            reglb = TACIndexer.reg()
            TACIndexer.pushIns(TACVTable(reglb, regc, cname, node.args[1].name))
            TACIndexer.pushIns(TACCall(TACIndexer.returnReg, reglb, regs))
        else:
            TACIndexer.pushIns(TACCall(TACIndexer.returnReg, meth.orig + '.' + meth.name, regs))
        regr = TACIndexer.reg()
        TACIndexer.pushIns(TACAssign(regr, TACIndexer.returnReg))
        if meth.body.type in ['Int','Bool']:
            regr.boxed = False
        return regr

    elif node.expr == 'static_dispatch':
        # Find method in imap
        cname = node.args[0].type if node.args[0].type != "SELF_TYPE" else TACIndexer.cname
        meth = None
        for m in TACIndexer.imap[cname]:
            if m.name == node.args[2].name:
                meth = m
                break

        # Box Int/Bool args only if they are used for Object parameter
        regs = []
        for i, e in enumerate(node.args[3]):
            r = expConvert(e)
            if meth.formalTypes[i] in ['Int', 'Bool']:
                r = unbox(r, e.type)
            else:
                r = box(r, e.type)
            regs.append(r)

        regc = expConvert(node.args[0])
        if node.args[0].type in ['Int', 'Bool']:
            reg = TACIndexer.reg()
            if node.args[2].name == 'type_name':
                TACIndexer.pushIns(TACConstant(reg, 'string', node.args[0].type))
                return reg
            if node.args[2].name == 'copy':
                TACIndexer.pushIns(TACAssign(reg, regc))
                reg.boxed = regc.boxed
                return reg

        regc = box(regc, node.args[0].type)
        if node.args[0].type not in ['String', 'Int', 'Bool', 'SELF_TYPE']:
            regv = TACIndexer.reg()
            regvbar = TACIndexer.reg()
            lbd = TACIndexer.label()
            TACIndexer.pushIns(TACOp1(regv, 'isvoid', regc))
            TACIndexer.pushIns(TACOp1(regvbar, 'not', regv))
            TACIndexer.pushIns(TACBT(regvbar, lbd))
            TACIndexer.pushIns(TACError(node.line, 'dispatchvoid'))
            TACIndexer.pushIns(TACLabel(lbd))
        regs = [regc] + regs
        # Find base class for given method
        basec = node.args[1].name
        for meth in TACIndexer.imap[node.args[1].name]:
            if meth.name == node.args[2].name:
                basec = meth.orig
                break
        calllb = basec + '.' + node.args[2].name
        TACIndexer.pushIns(TACCall(TACIndexer.returnReg, calllb, regs))
        regr = TACIndexer.reg()
        TACIndexer.pushIns(TACAssign(regr, TACIndexer.returnReg))
        if meth.body.type in ['Int','Bool']:
            regr.boxed = False
        return regr

    #note: no dispatch on void check needed here since "self" is always valid
    elif node.expr == 'self_dispatch':
        # Find method in imap
        cname = TACIndexer.cname
        meth = None
        for m in TACIndexer.imap[cname]:
            if m.name == node.args[0].name:
                meth = m
                break
        # Box Int/Bool args only if they are used for Object parameter
        regs = []
        for i, e in enumerate(node.args[1]):
            r = expConvert(e)
            if meth.formalTypes[i] in ['Int', 'Bool']:
                r = unbox(r, e.type)
            else:
                r = box(r, e.type)
            regs.append(r)

        regc = TACIndexer.map('self')
        regs = [regc] + regs
        reglb = TACIndexer.reg()
        TACIndexer.pushIns(TACVTable(reglb, regc, TACIndexer.cname, node.args[0].name))
        TACIndexer.pushIns(TACCall(TACIndexer.returnReg, reglb, regs))
        regr = TACIndexer.reg()
        TACIndexer.pushIns(TACAssign(regr, TACIndexer.returnReg))
        if meth.body.type in ['Int','Bool']:
            regr.boxed = False
        return regr

    elif node.expr == 'new':
        reg = TACIndexer.reg()
        if node.args.name == 'SELF_TYPE':
            #find constructor through vtable of self
            reglb = TACIndexer.reg()
            TACIndexer.pushIns(TACVTable(reglb, TACIndexer.map('self'), TACIndexer.cname, 'new'))
            TACIndexer.pushIns(TACCall(TACIndexer.returnReg, reglb, []))
            TACIndexer.pushIns(TACAssign(reg, TACIndexer.returnReg))
        else:
            TACIndexer.pushIns(TACAllocate(reg, 'new', node.args.name))
        regr = TACIndexer.reg()
        TACIndexer.pushIns(TACAssign(regr, reg))
        return regr

    elif node.expr == 'identifier':
        reg = TACIndexer.map(node.args.name)
        return reg

    elif node.expr == 'integer' or node.expr == 'string'    \
    or node.expr == 'true' or node.expr == 'false':
        reg = TACIndexer.reg()
        reg.boxed =not (node.expr == 'integer' or node.expr == 'true' or node.expr == 'false')
        constval = node.expr if node.expr in ['true','false'] else str(node.args)
        TACIndexer.pushIns(TACConstant(reg, astTacMap[node.expr], constval))
        return reg

    print "ERROR: tried to convert unhandled case: " + node.expr
    return None

#routine for generating TAC for methods
#special annotations are added to method args so offset is easy to find in ASM gen
def methodConvert(node):
    #emit start label of func
    TACIndexer.pushIns(TACLabel(TACIndexer.cname + '.' + TACIndexer.mname))

    #add the implicit "self" parameter
    reg = TACIndexer.map('self', True)
    TACIndexer.pushIns(TACAssign(reg, TACMethodArg(TACIndexer.cname, TACIndexer.mname, 'self')))
    #assign method args to registers
    for formal in node.formals:
        reg = TACIndexer.map(formal[0].name, True)
        if formal[1].name in ['Int', 'Bool']:
            reg.boxed = False
        TACIndexer.pushIns(TACAssign(reg, TACMethodArg(TACIndexer.cname, TACIndexer.mname, formal[0].name)))
    reg = expConvert(node.body)

    #remove formal -> register mappings
    TACIndexer.pop('self')
    for formal in node.formals:
        TACIndexer.pop(formal[0].name)

    if node.body.type in ['Int', 'Bool']:
        reg = unbox(reg, node.body.type)
    else:
        reg = box(reg, node.body.type)
    retreg = TACIndexer.returnReg
    TACIndexer.pushIns(TACAssign(retreg, reg))
    TACIndexer.pushIns(TACReturn(retreg))

def box(reg, type):
    if type in ['Bool', 'Int'] and not reg.boxed:
        breg = TACIndexer.reg()
        TACIndexer.pushIns(TACAllocate(breg, 'new', type))
        TACIndexer.pushIns(TACAssign(TACClassAttr(breg, type, 'val'), reg))
        reg = breg
    return reg

def unbox(reg, type):
    if type in ['Bool', 'Int']:
        if isinstance(reg, TACClassAttr):
            attreg = TACIndexer.reg()
            TACIndexer.pushIns(TACAssign(attreg, reg))
            attreg.boxed = reg.boxed
            reg = attreg
        if reg.boxed:
            uboxreg = TACIndexer.reg()
            TACIndexer.pushIns(TACAssign(uboxreg, TACClassAttr(reg, type, 'val')))
            uboxreg.boxed=False
            reg = uboxreg
    return reg

#for CA4, go through all methods of user-defined classes and generate TAC for bodies
def implConvert(ast):
    # Prepend entry point function
    meth=ASTMethod('_main', [], 'Object',
                   ASTExpression(0, 'Object', 'dynamic_dispatch',
                                 [ASTExpression(0, 'Main', 'new', ASTIdentifier(0, 'Main')),
                                  ASTIdentifier(0, 'main'),
                                  []])
                   )
    TACIndexer.pushIns(TACLabel('_main'))
    TACIndexer.init('', '_main')
    methodConvert(meth)

    for mclass in ast.classes:
        for feature in mclass.features:
            if isinstance(feature, ASTMethod):
                TACIndexer.init(mclass.name.name, feature.name.name)
                methodConvert(feature)

#define constructors for user-defined classes
def attrConvert(ast):
    #add mappings of attributes so TACIndexer can find them if not in symbol table
    for mclass in TACIndexer.cmap:
        for mattr in TACIndexer.cmap[mclass]:
            TACIndexer.addClassAttr(mclass, mattr.name, mattr.type not in ['Int', 'Bool'])
    #go through user-defined attributes
    for mclass in ast.classes:
        attrlst = TACIndexer.cmap[mclass.name.name]
        TACIndexer.init(mclass.name.name, 'new')
        #emit label for start of constructor
        TACIndexer.pushIns(TACLabel(TACIndexer.cname + '.' + TACIndexer.mname))
        #allocate memory on heap for object
        regm = TACIndexer.reg()
        TACIndexer.pushIns(TACMalloc(regm, mclass.name.name))
        TACIndexer.pushIns(TACAssign(TACIndexer.map('self', True), regm))
        #make first pass to default initialize fields
        for mattr in attrlst:
            reg = TACIndexer.reg()
            if mattr.type in ['Bool', 'Int']:
                TACIndexer.pushIns(TACConstant(reg, 'int', 0))
            else:
                TACIndexer.pushIns(TACAllocate(reg, 'default', mattr.type))
            TACIndexer.pushIns(TACAssign(TACIndexer.map(mattr.name), reg))

        #make second pass for those with initializer expressions
        for mattr in attrlst:
            if mattr.init is not None:
                reg = expConvert(mattr.init)
                if mattr.type in ['Bool', 'Int']:
                    reg = unbox(reg,mattr.init.type)
                else:
                    reg = box(reg,mattr.init.type)
                TACIndexer.pushIns(TACAssign(TACIndexer.map(mattr.name), reg))
        #return pointer to new object
        regr = TACIndexer.reg()
        TACIndexer.pushIns(TACAssign(regr, TACIndexer.map('self')))
        TACIndexer.pushIns(TACReturn(regr))
        TACIndexer.pop('self')

import TAC_serialize
import deadcode
if __name__ == '__main__':
    cmap, imap, pmap, ast = readClType(sys.argv[1])
    TACIndexer.setTypeMaps(cmap, imap, pmap)
    attrConvert(ast)
    implConvert(ast)

    #buffer up stored instructions and print
    outbuf = ''
    for ins in TACIndexer.inslst:
        outbuf += str(ins) + '\n'
    print outbuf

    cfg = TAC_serialize._constructCFG(TACIndexer.inslst)
    print "-----"
    deadcode.globalDeadRemove(cfg)
    print cfg
    print "-----"
    print cfg.verbosestr()

import sys
from annast import *
from TAC_serialize import *
from graphsort import *

#const mapping from AST tokens to TAC tokens
astTacMap = {
    'not' :     'not',
    'negate' :  '~',
    'isvoid' :  'isvoid',
    'plus' :    '+',
    'minus' :   '-',
    'times' :   '*',
    'divide' :  '/',
    'lt' :      '<',
    'le' :      '<=',
    'eq' :      '=',
    'integer' : 'int',
    'string' :  'string',
    'true' :    'bool',
    'false' :   'bool',
}

#manager for all the data global to expression generation function calls
#  using a static class because I have an aversion to many global vars
class TACIndexer:
    cname = ''      #class name for current instructions
    mname = ''      #method name for current instructions
    lind = 0        #counter for labels
    rind = 0        #counter for registers
    varRegMap = {}  #symbol table, map string var => lst of string registers bound to var
    classAttrs = {} #string class name => (string attr names => TACClassAttr obj)
    inslst = []     #list of TACInstruction

    cmap = {}       #class map
    imap = {}       #implementation map
    pmap = {}       #parent map

    returnReg = TACRegister('t0')

    @staticmethod
    def setTypeMaps(cmap, imap, pmap):
        TACIndexer.cmap = cmap
        TACIndexer.imap = imap
        TACIndexer.pmap = pmap

    #resets counters and sets the names for labels
    @staticmethod
    def init(cname, mname):
        #TACIndexer.rind = 0
        TACIndexer.lind = 0
        TACIndexer.cname = cname
        TACIndexer.mname = mname

    @staticmethod
    def addClassAttr(cname, attrname, boxed = True):
        if cname not in TACIndexer.classAttrs:
            TACIndexer.classAttrs[cname] = {}
        TACIndexer.classAttrs[cname][attrname] = boxed

    #increments a counter and returns a string label
    @staticmethod
    def label():
        TACIndexer.lind += 1
        return "." + TACIndexer.cname + '.' + TACIndexer.mname + '_' + str(TACIndexer.lind)

    #increments a counter a returns a register label
    @staticmethod
    def reg():
        TACIndexer.rind += 1
        return TACRegister('t' + str(TACIndexer.rind))

    #looks up the symbol table for var; creates new register if forceNew or not found
    @staticmethod
    def map(var, forceNew = False):
        if var not in TACIndexer.varRegMap:
            TACIndexer.varRegMap[var] = []
        if len(TACIndexer.varRegMap[var]) == 0 or forceNew:
            if not forceNew and var in TACIndexer.classAttrs[TACIndexer.cname]:
                reg= TACClassAttr(TACIndexer.map('self'), TACIndexer.cname, var)
                reg.boxed = TACIndexer.classAttrs[TACIndexer.cname][var]
                return reg
            else:
                reg = TACIndexer.reg()
                TACIndexer.varRegMap[var].append(reg)
        return TACIndexer.varRegMap[var][-1]

    #binds a symbol to an existing register, provided as an arg
    @staticmethod
    def bind(var, reg):
        if var not in TACIndexer.varRegMap:
            TACIndexer.varRegMap[var] = []
        TACIndexer.varRegMap[var].append(reg)

    #unbinds a symbol table entry for var
    @staticmethod
    def pop(var):
        TACIndexer.varRegMap[var].pop()

    #adds a TACInstruction to the list
    @staticmethod
    def pushIns(ins):
        TACIndexer.inslst.append(ins)

#recursive routine for generating TAC for expressions
def expConvert(node):

    if node.expr == 'while':
        #emit label for loop start (computing predicate)
        lbp = TACIndexer.label()
        TACIndexer.pushIns(TACLabel(lbp))
        #recurse on predicate expression
        regp = expConvert(node.args[0])
        regp = unbox(regp, node.args[0].type)
        #emit label for loop breakout -- if predicate is false, we jump there
        lbb = TACIndexer.label()
        regpbar = TACIndexer.reg()
        regpbar.boxed = False
        TACIndexer.pushIns(TACOp1(regpbar, 'not', regp))
        TACIndexer.pushIns(TACBT(regpbar, lbb))
        #recurse on body expression
        regb = expConvert(node.args[1])
        #generate jump back to top
        TACIndexer.pushIns(TACJmp(lbp))
        #generate the breakout label
        TACIndexer.pushIns(TACLabel(lbb))
        #create a default (void) as the return value
        reg = TACIndexer.reg()
        TACIndexer.pushIns(TACAllocate(reg, 'default', 'Object'))
        return reg

    elif node.expr == 'if':
        #recurse on predicate expression
        regp = expConvert(node.args[0])
        regp = unbox(regp, 'Bool')
        regpbar = TACIndexer.reg()
        regpbar.boxed = False
        TACIndexer.pushIns(TACAssign(regpbar, regp))
        TACIndexer.pushIns(TACOp1(regpbar, 'not', regpbar))
        #emit label for else and branch there if predicate is false
        #NOTE I generate then first for readability, we can save the not op by doing else first
        lbe = TACIndexer.label()
        TACIndexer.pushIns(TACBT(regpbar, lbe))
        #recurse on then body, emit join label and jump there at end
        #also, place then result into join register
        regt = expConvert(node.args[1])
        regj = TACIndexer.reg()
        # Do auto-boxing of result
        if node.type not in ['Int', 'Bool']:
            regt = box(regt, node.args[1].type)
        else:
            regt = unbox(regt, node.args[1].type)
            regj.boxed = False
        TACIndexer.pushIns(TACAssign(regj, regt))

        lbj = TACIndexer.label()
        TACIndexer.pushIns(TACJmp(lbj))

        #insert label for else
        TACIndexer.pushIns(TACLabel(lbe))
        #recurse on else body
        rege = expConvert(node.args[2])
        # Do auto-boxing of result
        if node.type not in ['Int', 'Bool']:
            rege = box(rege, node.args[2].type)
        else:
            rege = unbox(rege, node.args[2].type)
        #place result into join register
        TACIndexer.pushIns(TACAssign(regj, rege))
        #insert join label
        TACIndexer.pushIns(TACLabel(lbj))
        return regj

    elif node.expr == 'let':
        # Bind the let vars
        for binding in node.args[0]:

            if binding.init is not None:
                # if there is an init, generate the init code
                regi = expConvert(binding.init)

                #create reg here so previous binding holds in init expr
                reg = TACIndexer.map(binding.name.name,True)
                if binding.type.name in ['Int', 'Bool']:
                    reg.boxed = False
                else:
                    reg.boxed = True

                if reg.boxed:
                    regi = box(regi, binding.init.type)
                else:
                    regi = unbox(regi, binding.init.type)
                TACIndexer.pushIns(TACAssign(reg,regi))
            else:

                #create reg here so previous binding holds in init expr
                reg = TACIndexer.map(binding.name.name,True)
                if binding.type.name in ['Int', 'Bool']:
                    reg.boxed = False
                else:
                    reg.boxed = True
                #otherwise generate default init
                if reg.boxed:
                    if binding.type.name == 'String':
                        regn = TACIndexer.reg()
                        TACIndexer.pushIns(TACAllocate(regn, 'default', binding.type.name))
                        TACIndexer.pushIns(TACAssign(reg, regn))
                    else:
                        TACIndexer.pushIns(TACAllocate(reg,'default',binding.type.name))
                else:
                    TACIndexer.pushIns(TACConstant(reg, 'int', 0))
        # Generate the body code
        regr = expConvert(node.args[1])
        # Unbind the let vars
        for binding in node.args[0]:
            TACIndexer.pop(binding.name.name)
        return regr

    elif node.expr == 'case':
        #generate case object expression
        regc = expConvert(node.args[0])
        if isinstance(regc, TACClassAttr):
            attreg = TACIndexer.reg()
            TACIndexer.pushIns(TACAssign(attreg, regc))
            attreg.boxed = regc.boxed
            regc = attreg
        #avoid void check if we know it is primitive or self
        if regc.boxed or node.args[0].type not in ['String', 'Int', 'Bool', 'SELF_TYPE']:
            #fail if case "caller" is void
            regv = TACIndexer.reg()
            regv.boxed = False
            lbc = TACIndexer.label()
            TACIndexer.pushIns(TACAssign(regv, regc))
            TACIndexer.pushIns(TACOp1(regv, 'isvoid', regv))
            TACIndexer.pushIns(TACOp1(regv, 'not', regv))
            TACIndexer.pushIns(TACBT(regv, lbc))
            TACIndexer.pushIns(TACError(node.line, 'casevoid'))
            TACIndexer.pushIns(TACLabel(lbc))
        #box case object
        regc = box(regc, node.args[0].type)
        #find which branch types can be possibly taken based on static type of obj
        btypesall = [branch.type.name for branch in node.args[1]]
        caseobjtype = node.args[0].type
        if node.args[0].type == 'SELF_TYPE':
            caseobjtype = TACIndexer.cname  #we could be more restrictive on subclasses inheriting exp
        #branch types which MUST be taken (static type conforms to branch type)
        btypes1 = [clsname for clsname in btypesall if caseobjtype in subtreeList(clsname, TACIndexer.pmap)]
        #branch types which might be taken (branch type conforms to static type)
        btypes2 = [clsname for clsname in btypesall if clsname in subtreeList(caseobjtype, TACIndexer.pmap) \
            and clsname not in btypes1]
        btypes = btypes1 + btypes2
        #if we only have one branch and it must be taken, omit join label and type checks
        needcheck = not (len(btypes2) == 0 and len(btypes1) == 1)
        if needcheck:
            #generate labels for branches, and record branch types
            blabels = [TACIndexer.label() for i in range(len(btypes))]
            #generate type evaluation to find least type and jump to appropriate label
            #   reverse toposort to get least to greatest order
            usedtypes = set()
            for clsname in reversed(toposort(TACIndexer.pmap)):
                if clsname not in btypes:
                    continue
                ind = btypes.index(clsname)
                sublst = subtreeList(clsname, TACIndexer.pmap)
                for subclsname in sublst:
                    if subclsname in usedtypes:
                        continue
                    usedtypes.add(subclsname)
                    TACIndexer.pushIns(TACBTypeEq(regc, subclsname, blabels[ind]))

        #if no branches that must be taken exist we generate the fallthrough case
        if len(btypes1) == 0:
            #fail if no type found
            TACIndexer.pushIns(TACError(node.line, 'casenomatch'))

        #generate join label
        lbj = TACIndexer.label()
        #create join reg
        regj = TACIndexer.reg()
        #loop over branches: emit label, generate code, result in join reg + jump to join label
        for i in range(len(btypes)):
            btype = btypes[i]
            branch = [br for br in node.args[1] if br.type.name == btype][0]
            if needcheck:
                TACIndexer.pushIns(TACLabel(blabels[i]))
            regci = TACIndexer.map(branch.name.name, True)
            TACIndexer.pushIns(TACAssign(regci, regc))
            regb = expConvert(branch.body)
            if node.type in ['Bool', 'Int']:
                regb = unbox(regb, branch.type.name)
                regj.boxed = False
            else:
                regb = box(regb, branch.type.name)
            TACIndexer.pop(branch.name.name)
            if needcheck:
                TACIndexer.pushIns(TACAssign(regj, regb))
                TACIndexer.pushIns(TACJmp(lbj))
            else:
                return regb
        if needcheck:
            #emit join label
            TACIndexer.pushIns(TACLabel(lbj))
        return regj

    elif node.expr == 'block':
        for sexpr in node.args:
            reg = expConvert(sexpr)
        return reg  #last expression evaluated is the return val

    elif node.expr == 'assign':
        regr = expConvert(node.args[1])
        reg = TACIndexer.map(node.args[0].name)
        if reg.boxed:
            regr = box(regr, node.args[1].type)
        else:
            regr = unbox(regr, node.args[1].type)
        TACIndexer.pushIns(TACAssign(reg, regr))
        return regr

    elif node.expr == 'isvoid':
        regr = expConvert(node.args)

        if isinstance(regr, TACClassAttr):
            attreg = TACIndexer.reg()
            TACIndexer.pushIns(TACAssign(attreg, regr))
            attreg.boxed = regr.boxed
            regr = attreg

        op1 = TACIndexer.reg()
        op1.boxed = False
        if not regr.boxed or node.args.type in ['String', 'Int', 'Bool', 'SELF_TYPE']:
            #isvoid is always false for primitives
            TACIndexer.pushIns(TACConstant(op1, 'bool', 'false'))
        else:
            TACIndexer.pushIns(TACOp1(op1, astTacMap[node.expr], regr))
        return op1

    #for negate and not only
    elif node.expr in ASTExpression.exp1:
        op1 = TACIndexer.reg()
        reg1 = expConvert(node.args)
        TACIndexer.pushIns(TACAssign(op1, reg1))
        op1.boxed = reg1.boxed
        op1 = unbox(op1, node.args.type)

        TACIndexer.pushIns(TACOp1(op1, astTacMap[node.expr], op1))
        return op1

    elif node.expr in ASTExpression.exp2:
        regr1 = expConvert(node.args[0])
        regr2 = expConvert(node.args[1])

        op1 = TACIndexer.reg()
        op2 = TACIndexer.reg()

        TACIndexer.pushIns(TACAssign(op1,regr1))
        TACIndexer.pushIns(TACAssign(op2,regr2))
        op1.boxed = regr1.boxed
        op2.boxed = regr2.boxed

        op1 = unbox(op1, node.args[0].type)
        op2 = unbox(op2, node.args[1].type)

        resreg = TACIndexer.reg()
        #check if divisor is zero, and if so, err and exit
        if node.expr == 'divide':
            regz = TACIndexer.reg()
            regz.boxed = False
            rege = TACIndexer.reg()
            rege.boxed = False
            regebar = TACIndexer.reg()
            regebar.boxed = False
            lba = TACIndexer.label()
            TACIndexer.pushIns(TACConstant(regz, 'int', '0'))
            TACIndexer.pushIns(TACCompare(regz, '=', op2, regz, 'Int'))
            TACIndexer.pushIns(TACOp1(regz, 'not', regz))
            TACIndexer.pushIns(TACBT(regz, lba))
            TACIndexer.pushIns(TACError(node.line, 'dividezero'))
            TACIndexer.pushIns(TACLabel(lba))
        if node.expr in ['plus','minus','times','divide']:
            #abuse of notation - for non-commutative operators, having op2 as 1st operand is useful
            TACIndexer.pushIns(TACOp2(op1, astTacMap[node.expr], op2, op1))
            TACIndexer.pushIns(TACAssign(resreg, op1))
            resreg.boxed = False
        else:
            #must be comparison operator, so use a subclass that captures the static type
            ptype = ''
            if node.args[0].type == 'Int' or node.args[0].type == 'Bool':
                ptype = 'Int'   #ordinary binary compare
            elif node.args[0].type == 'String':
                ptype = 'String'    #lexographical compare
            else:
                ptype = 'Object'    #pointer compare
            TACIndexer.pushIns(TACCompare(op2, astTacMap[node.expr], op1, op2, ptype))
            TACIndexer.pushIns(TACAssign(resreg, op2))
            resreg.boxed = False


        return resreg

    #all dispatch follows form:
    #   generate all explicit parameters of function (regs)
    #   generate the caller of function (regc)
    #   check if caller is void, and if so, err and exit
    #   prepend exec as the self param to regs
    #   find function to call in vtable if necessary
    #   call function and assign result into new register
    elif node.expr == 'dynamic_dispatch':
        # Find method in imap
        cname = node.args[0].type if node.args[0].type != "SELF_TYPE" else TACIndexer.cname
        meth = None
        for m in TACIndexer.imap[cname]:
            if m.name == node.args[1].name:
                meth = m
                break
        # Box Int/Bool args only if they are used for Object parameter
        regs = []
        for i, e in enumerate(node.args[2]):
            r = expConvert(e)
            if meth.formalTypes[i] in ['Int', 'Bool']:
                r = unbox(r, e.type)
            else:
                r = box(r, e.type)
            regs.append(r)

        regc = expConvert(node.args[0])

        if node.args[0].type in ['Int', 'Bool']:
            reg = TACIndexer.reg()
            if node.args[1].name == 'type_name':
                TACIndexer.pushIns(TACConstant(reg, 'string', node.args[0].type))
                return reg
            if node.args[1].name == 'copy':
                TACIndexer.pushIns(TACAssign(reg, regc))
                reg.boxed = regc.boxed
                return reg

        regc = box(regc, node.args[0].type)
        if node.args[0].type not in ['Int', 'Bool', 'String', 'SELF_TYPE']:
            regv = TACIndexer.reg()
            regvbar = TACIndexer.reg()
            lbd = TACIndexer.label()
            TACIndexer.pushIns(TACOp1(regv, 'isvoid', regc))
            TACIndexer.pushIns(TACOp1(regvbar, 'not', regv))
            TACIndexer.pushIns(TACBT(regvbar, lbd))
            TACIndexer.pushIns(TACError(node.line, 'dispatchvoid'))
            TACIndexer.pushIns(TACLabel(lbd))
        regs = [regc] + regs
        if node.args[0].type not in ['Int', 'Bool', 'String']:
            reglb = TACIndexer.reg()
            TACIndexer.pushIns(TACVTable(reglb, regc, cname, node.args[1].name))
            TACIndexer.pushIns(TACCall(TACIndexer.returnReg, reglb, regs))
        else:
            TACIndexer.pushIns(TACCall(TACIndexer.returnReg, meth.orig + '.' + meth.name, regs))
        regr = TACIndexer.reg()
        TACIndexer.pushIns(TACAssign(regr, TACIndexer.returnReg))
        if meth.body.type in ['Int','Bool']:
            regr.boxed = False
        return regr

    elif node.expr == 'static_dispatch':
        # Find method in imap
        cname = node.args[0].type if node.args[0].type != "SELF_TYPE" else TACIndexer.cname
        meth = None
        for m in TACIndexer.imap[cname]:
            if m.name == node.args[2].name:
                meth = m
                break

        # Box Int/Bool args only if they are used for Object parameter
        regs = []
        for i, e in enumerate(node.args[3]):
            r = expConvert(e)
            if meth.formalTypes[i] in ['Int', 'Bool']:
                r = unbox(r, e.type)
            else:
                r = box(r, e.type)
            regs.append(r)

        regc = expConvert(node.args[0])
        if node.args[0].type in ['Int', 'Bool']:
            reg = TACIndexer.reg()
            if node.args[2].name == 'type_name':
                TACIndexer.pushIns(TACConstant(reg, 'string', node.args[0].type))
                return reg
            if node.args[2].name == 'copy':
                TACIndexer.pushIns(TACAssign(reg, regc))
                reg.boxed = regc.boxed
                return reg

        regc = box(regc, node.args[0].type)
        if node.args[0].type not in ['String', 'Int', 'Bool', 'SELF_TYPE']:
            regv = TACIndexer.reg()
            regvbar = TACIndexer.reg()
            lbd = TACIndexer.label()
            TACIndexer.pushIns(TACOp1(regv, 'isvoid', regc))
            TACIndexer.pushIns(TACOp1(regvbar, 'not', regv))
            TACIndexer.pushIns(TACBT(regvbar, lbd))
            TACIndexer.pushIns(TACError(node.line, 'dispatchvoid'))
            TACIndexer.pushIns(TACLabel(lbd))
        regs = [regc] + regs
        # Find base class for given method
        basec = node.args[1].name
        for meth in TACIndexer.imap[node.args[1].name]:
            if meth.name == node.args[2].name:
                basec = meth.orig
                break
        calllb = basec + '.' + node.args[2].name
        TACIndexer.pushIns(TACCall(TACIndexer.returnReg, calllb, regs))
        regr = TACIndexer.reg()
        TACIndexer.pushIns(TACAssign(regr, TACIndexer.returnReg))
        if meth.body.type in ['Int','Bool']:
            regr.boxed = False
        return regr

    #note: no dispatch on void check needed here since "self" is always valid
    elif node.expr == 'self_dispatch':
        # Find method in imap
        cname = TACIndexer.cname
        meth = None
        for m in TACIndexer.imap[cname]:
            if m.name == node.args[0].name:
                meth = m
                break
        # Box Int/Bool args only if they are used for Object parameter
        regs = []
        for i, e in enumerate(node.args[1]):
            r = expConvert(e)
            if meth.formalTypes[i] in ['Int', 'Bool']:
                r = unbox(r, e.type)
            else:
                r = box(r, e.type)
            regs.append(r)

        regc = TACIndexer.map('self')
        regs = [regc] + regs
        reglb = TACIndexer.reg()
        TACIndexer.pushIns(TACVTable(reglb, regc, TACIndexer.cname, node.args[0].name))
        TACIndexer.pushIns(TACCall(TACIndexer.returnReg, reglb, regs))
        regr = TACIndexer.reg()
        TACIndexer.pushIns(TACAssign(regr, TACIndexer.returnReg))
        if meth.body.type in ['Int','Bool']:
            regr.boxed = False
        return regr

    elif node.expr == 'new':
        reg = TACIndexer.reg()
        if node.args.name == 'SELF_TYPE':
            #find constructor through vtable of self
            reglb = TACIndexer.reg()
            TACIndexer.pushIns(TACVTable(reglb, TACIndexer.map('self'), TACIndexer.cname, 'new'))
            TACIndexer.pushIns(TACCall(TACIndexer.returnReg, reglb, []))
            TACIndexer.pushIns(TACAssign(reg, TACIndexer.returnReg))
        else:
            TACIndexer.pushIns(TACAllocate(reg, 'new', node.args.name))
        regr = TACIndexer.reg()
        TACIndexer.pushIns(TACAssign(regr, reg))
        return regr

    elif node.expr == 'identifier':
        reg = TACIndexer.map(node.args.name)
        return reg

    elif node.expr == 'integer' or node.expr == 'string'    \
    or node.expr == 'true' or node.expr == 'false':
        reg = TACIndexer.reg()
        reg.boxed =not (node.expr == 'integer' or node.expr == 'true' or node.expr == 'false')
        constval = node.expr if node.expr in ['true','false'] else str(node.args)
        TACIndexer.pushIns(TACConstant(reg, astTacMap[node.expr], constval))
        return reg

    print "ERROR: tried to convert unhandled case: " + node.expr
    return None

#routine for generating TAC for methods
#special annotations are added to method args so offset is easy to find in ASM gen
def methodConvert(node):
    #emit start label of func
    TACIndexer.pushIns(TACLabel(TACIndexer.cname + '.' + TACIndexer.mname))

    #add the implicit "self" parameter
    reg = TACIndexer.map('self', True)
    TACIndexer.pushIns(TACAssign(reg, TACMethodArg(TACIndexer.cname, TACIndexer.mname, 'self')))
    #assign method args to registers
    for formal in node.formals:
        reg = TACIndexer.map(formal[0].name, True)
        if formal[1].name in ['Int', 'Bool']:
            reg.boxed = False
        TACIndexer.pushIns(TACAssign(reg, TACMethodArg(TACIndexer.cname, TACIndexer.mname, formal[0].name)))
    reg = expConvert(node.body)

    #remove formal -> register mappings
    TACIndexer.pop('self')
    for formal in node.formals:
        TACIndexer.pop(formal[0].name)

    if node.body.type in ['Int', 'Bool']:
        reg = unbox(reg, node.body.type)
    else:
        reg = box(reg, node.body.type)
    retreg = TACIndexer.returnReg
    TACIndexer.pushIns(TACAssign(retreg, reg))
    TACIndexer.pushIns(TACReturn(retreg))

def box(reg, type):
    if type in ['Bool', 'Int'] and not reg.boxed:
        breg = TACIndexer.reg()
        TACIndexer.pushIns(TACAllocate(breg, 'new', type))
        TACIndexer.pushIns(TACAssign(TACClassAttr(breg, type, 'val'), reg))
        reg = breg
    return reg

def unbox(reg, type):
    if type in ['Bool', 'Int']:
        if isinstance(reg, TACClassAttr):
            attreg = TACIndexer.reg()
            TACIndexer.pushIns(TACAssign(attreg, reg))
            attreg.boxed = reg.boxed
            reg = attreg
        if reg.boxed:
            uboxreg = TACIndexer.reg()
            TACIndexer.pushIns(TACAssign(uboxreg, TACClassAttr(reg, type, 'val')))
            uboxreg.boxed=False
            reg = uboxreg
    return reg

#for CA4, go through all methods of user-defined classes and generate TAC for bodies
def implConvert(ast):
    # Prepend entry point function
    meth=ASTMethod('_main', [], 'Object',
                   ASTExpression(0, 'Object', 'dynamic_dispatch',
                                 [ASTExpression(0, 'Main', 'new', ASTIdentifier(0, 'Main')),
                                  ASTIdentifier(0, 'main'),
                                  []])
                   )
    TACIndexer.pushIns(TACLabel('_main'))
    TACIndexer.init('', '_main')
    methodConvert(meth)

    for mclass in ast.classes:
        for feature in mclass.features:
            if isinstance(feature, ASTMethod):
                TACIndexer.init(mclass.name.name, feature.name.name)
                methodConvert(feature)

#define constructors for user-defined classes
def attrConvert(ast):
    #add mappings of attributes so TACIndexer can find them if not in symbol table
    for mclass in TACIndexer.cmap:
        for mattr in TACIndexer.cmap[mclass]:
            TACIndexer.addClassAttr(mclass, mattr.name, mattr.type not in ['Int', 'Bool'])
    #go through user-defined attributes
    for mclass in ast.classes:
        attrlst = TACIndexer.cmap[mclass.name.name]
        TACIndexer.init(mclass.name.name, 'new')
        #emit label for start of constructor
        TACIndexer.pushIns(TACLabel(TACIndexer.cname + '.' + TACIndexer.mname))
        #allocate memory on heap for object
        regm = TACIndexer.reg()
        TACIndexer.pushIns(TACMalloc(regm, mclass.name.name))
        TACIndexer.pushIns(TACAssign(TACIndexer.map('self', True), regm))
        #make first pass to default initialize fields
        for mattr in attrlst:
            reg = TACIndexer.reg()
            if mattr.type in ['Bool', 'Int']:
                TACIndexer.pushIns(TACConstant(reg, 'int', 0))
            else:
                TACIndexer.pushIns(TACAllocate(reg, 'default', mattr.type))
            TACIndexer.pushIns(TACAssign(TACIndexer.map(mattr.name), reg))

        #make second pass for those with initializer expressions
        for mattr in attrlst:
            if mattr.init is not None:
                reg = expConvert(mattr.init)
                if mattr.type in ['Bool', 'Int']:
                    reg = unbox(reg,mattr.init.type)
                else:
                    reg = box(reg,mattr.init.type)
                TACIndexer.pushIns(TACAssign(TACIndexer.map(mattr.name), reg))
        #return pointer to new object
        regr = TACIndexer.reg()
        TACIndexer.pushIns(TACAssign(regr, TACIndexer.map('self')))
        TACIndexer.pushIns(TACReturn(regr))
        TACIndexer.pop('self')

import TAC_serialize
import deadcode
if __name__ == '__main__':
    cmap, imap, pmap, ast = readClType(sys.argv[1])
    TACIndexer.setTypeMaps(cmap, imap, pmap)
    attrConvert(ast)
    implConvert(ast)

    #buffer up stored instructions and print
    outbuf = ''
    for ins in TACIndexer.inslst:
        outbuf += str(ins) + '\n'
    print outbuf

    cfg = TAC_serialize._constructCFG(TACIndexer.inslst)
    print "-----"
    deadcode.globalDeadRemove(cfg)
    print cfg
    print "-----"
    print cfg.verbosestr()

#const mapping from AST tokens to TAC tokens #manager for all the data global to expression generation function calls #  using a static class because I have an aversion to many global vars #class name for current instructions #method name for current instructions #counter for labels #counter for registers #symbol table, map string var => lst of string registers bound to var #string class name => (string attr names => TACClassAttr obj) #list of TACInstruction #class map #implementation map #parent map #resets counters and sets the names for labels #TACIndexer.rind = 0 #increments a counter and returns a string label #increments a counter a returns a register label #looks up the symbol table for var; creates new register if forceNew or not found #binds a symbol to an existing register, provided as an arg #unbinds a symbol table entry for var #adds a TACInstruction to the list #recursive routine for generating TAC for expressions #emit label for loop start (computing predicate) #recurse on predicate expression #emit label for loop breakout -- if predicate is false, we jump there #recurse on body expression #generate jump back to top #generate the breakout label #create a default (void) as the return value #recurse on predicate expression #emit label for else and branch there if predicate is false #NOTE I generate then first for readability, we can save the not op by doing else first #recurse on then body, emit join label and jump there at end #also, place then result into join register # Do auto-boxing of result #insert label for else #recurse on else body # Do auto-boxing of result #place result into join register #insert join label # Bind the let vars # if there is an init, generate the init code #create reg here so previous binding holds in init expr #create reg here so previous binding holds in init expr #otherwise generate default init # Generate the body code # Unbind the let vars #generate case object expression #avoid void check if we know it is primitive or self #fail if case "caller" is void #box case object #find which branch types can be possibly taken based on static type of obj #we could be more restrictive on subclasses inheriting exp #branch types which MUST be taken (static type conforms to branch type) #branch types which might be taken (branch type conforms to static type) #if we only have one branch and it must be taken, omit join label and type checks #generate labels for branches, and record branch types #generate type evaluation to find least type and jump to appropriate label #   reverse toposort to get least to greatest order #if no branches that must be taken exist we generate the fallthrough case #fail if no type found #generate join label #create join reg #loop over branches: emit label, generate code, result in join reg + jump to join label #emit join label #last expression evaluated is the return val #isvoid is always false for primitives #for negate and not only #check if divisor is zero, and if so, err and exit #abuse of notation - for non-commutative operators, having op2 as 1st operand is useful #must be comparison operator, so use a subclass that captures the static type #ordinary binary compare #lexographical compare #pointer compare #all dispatch follows form: #   generate all explicit parameters of function (regs) #   generate the caller of function (regc) #   check if caller is void, and if so, err and exit #   prepend exec as the self param to regs #   find function to call in vtable if necessary #   call function and assign result into new register # Find method in imap # Box Int/Bool args only if they are used for Object parameter # Find method in imap # Box Int/Bool args only if they are used for Object parameter # Find base class for given method #note: no dispatch on void check needed here since "self" is always valid # Find method in imap # Box Int/Bool args only if they are used for Object parameter #find constructor through vtable of self #routine for generating TAC for methods #special annotations are added to method args so offset is easy to find in ASM gen #emit start label of func #add the implicit "self" parameter #assign method args to registers #remove formal -> register mappings #for CA4, go through all methods of user-defined classes and generate TAC for bodies # Prepend entry point function #define constructors for user-defined classes #add mappings of attributes so TACIndexer can find them if not in symbol table #go through user-defined attributes #emit label for start of constructor #allocate memory on heap for object #make first pass to default initialize fields #make second pass for those with initializer expressions #return pointer to new object #buffer up stored instructions and print