class Var(Expr):
    '''
    Variable
    '''

    def __init__(self, name, primed=False, *args, **kwargs):
        
        super(Var, self).__init__(*args, **kwargs)

        assert isinstance(name, str), \
            "Variable name should be string or unicode, got '%s'" % (name,)
        assert isinstance(primed, bool), \
            "Variable 'primed' should be bool, got '%s'" % (primed,)
        
        self.name = str(name)
        self.primed = primed

    def copy(self):
        return Var(self.name, self.primed, **self.copyargs())

    def replace(self, var, expr, primedonly=False):
        if self.name == var and ((not primedonly) or self.primed):
            expr = expr.copy()
            return expr
        else:
            return self.copy()

    def replace_vars(self, d):
        if self.name in d:
            v = self.copy()
            v.name = d[self.name]
        else:
            v = self.copy()

        v.replace_original(d)

        return v

    def prime(self, vars):
        if self.name in vars:
            self.primed = True

    def vars(self):
        return set([str(self)])

    def tostr(self):
        if self.primed:
            return "%s'" % (self.name,)
        else:
            return str(self.name)

    def tostring(self):
        return self.expr_original(repr(self))
    
    def __repr__(self):
        if self.primed:
            return "%s'" % (self.name,)
        else:
            return self.name
            
        #return self.expr_original(s)

    def __eq__(self, other):
        if other is None: return False
        if not isinstance(other, Var): return False
        return self.name == other.name and self.primed == other.primed

    def __ne__(self, other):
        return not self == other

    def __hash__(self):
        return hash((self.name, self.primed)) class Const(Expr):
    '''
    Constant
    '''

    def __init__(self, value, *args, **kwargs):

        super(Const, self).__init__(*args, **kwargs)

        assert isinstance(value, str), \
            "Constant value should be string, got '%s'" % (value,)
        
        self.value = str(value)

    def copy(self):
        return Const(self.value, **self.copyargs())

    def replace(self, v, e, primedonly=False):
        return self.copy()

    def replace_vars(self, d):
        e = self.copy()
        e.replace_original(d)
        return e

    def prime(self, vars):
        pass

    def vars(self):
        return set()

    def tostring(self):
        return self.expr_original(repr(self))

    def __repr__(self):
        return self.value
        #return self.expr_original(s)

    def __eq__(self, other):
        if other is None: return False
        if not isinstance(other, Const): return False
        return self.value == other.value

    def __ne__(self, other):
        return not self == other

    def __hash__(self):
        return hash(self.value) class Op(Expr):
    '''
    Operations
    '''

    def __init__(self, name, *args, **kwargs):

        super(Op, self).__init__(**kwargs)

        assert isinstance(name, str), \
            "Operation name should be string, got '%s'" % (name,)
        for i, arg in enumerate(args, 1):
            assert isinstance(arg, Expr), \
                "Operation's argument (#%d) should be Expression, got '%s'" % (
                    i, arg)

        self.name = str(name)
        self.args = list(args)

    def copy(self):
        return Op(self.name,
                  *[x.copy() for x in self.args],
                  **self.copyargs())

    def replace(self, v, e, primedonly=False):
        return Op(self.name,
                  *[x.replace(v, e, primedonly) for x in self.args],
                  **self.copyargs())

    def replace_vars(self, d):
        e = Op(self.name,
               *[x.replace_vars(d) for x in self.args],
               **self.copyargs())
        e.replace_original(d)
        return e

    def prime(self, vars):
        for arg in self.args:
            arg.prime(vars)

    def vars(self):
        args = self.args[1:] if self.name == 'FuncCall' else self.args
        return reduce(lambda x, y: x | y, [x.vars() for x in args],
                      set())

    def tostring(self):
        s = '%s(%s)' % (self.name, ', '.join(
            [x.tostring() for x in self.args]))
        return self.expr_original(s)

    def __repr__(self):
        return '%s(%s)' % (self.name, ', '.join(map(str, self.args)))

    def __eq__(self, other):
        if other is None: return False
        if not isinstance(other, Op): return False
        if self.name != other.name: return False
        if len(self.args) != len(other.args): return False
        for arg1, arg2 in zip(self.args, other.args):
            if arg1 != arg2: return False
        return True

    def __ne__(self, other):
        return not self == other

    def __hash__(self):
        return hash((self.name, tuple(self.args))) class Expr(object):
    '''
    An expression
    '''

    def __init__(self, line=None, statement=False, original=None):
        self.line = line
        self.statement = statement
        self.original = original

    def copyargs(self):
        return {'line': self.line,
                'statement': self.statement,
                'original': self.original}

    def replace_original(self, d):
        if not self.original:
            return
        
        if self.original[0] in d:
            self.original = (d[self.original[0]],
                             self.original[1])

    def expr_original(self, s):
        if self.original:
            return '%s{%s, %d}' % (s, self.original[0], self.original[1],)
        else:
            return s VAR_IN = '$in' VAR_OUT = '$out' VAR_RET = '$ret' class Parser(object):
    '''
    Common stuff for parser for any language
    '''

    def __init__(self, optifs=True, postprocess=True, nobcs=False,
                 slice=False):
        
        self.prog = Program()

        self.fncs = {}
        self.fncsl = []
        self.fnc = None
        self.loc = None

        self.optifs = optifs
        self.postproc = postprocess
        self.slice = slice

        self.loops = []

        self.cnt = 0

        self.warns = []

        self.hasbcs = False
        self.nobcs = nobcs

    def newcnt(self):
        self.cnt += 1
        return self.cnt

    def ssavar(self, var):
        return '%s_&%d&' % (var, self.newcnt())

    def addwarn(self, msg, *args):
        if args:
            msg %= args
        self.prog.addwarn(str(msg))

    def rmemptyfncs(self):
        '''
        Removes empty functions, i.e., declarations only
        '''

        for fnc in self.prog.getfncs():
            if fnc.initloc is None:
                self.prog.rmfnc(fnc.name)

    def rmunreachlocs(self, fnc):
        '''
        Removes unreachable locations from the graph
        '''

        visited = set()
        tovisit = [fnc.initloc]

        while len(tovisit) > 0:
            loc = tovisit.pop()
            if loc in visited:
                continue
            visited.add(loc)

            l1 = fnc.trans(loc, True)
            if l1:
                tovisit.append(l1)
            l2 = fnc.trans(loc, False)
            if l2:
                tovisit.append(l2)

        for loc in fnc.locs():
            if loc not in visited:
                fnc.rmloc(loc)

    def ssa(self, fnc):
        '''
        Converts exprs of each loc to SSA form
        '''

        for loc in fnc.locs():

            # Find last appearance of each var
            last = {}
            for i, (var, _) in enumerate(fnc.exprs(loc)):
                last[var] = i

            # Replace non-last appearance by a fresh var
            m = {}
            exprs = []
            for i, (var, expr) in enumerate(fnc.exprs(loc)):
                
                for v1, v2 in list(m.items()):
                    expr = expr.replace(v1, Var(v2))

                if var == VAR_RET:
                    newvar = var
                else:
                    if last[var] > i:
                        newvar = m[var] = self.ssavar(var)
                    else:
                        m.pop(var, None)
                        newvar = var

                if var != newvar:
                    expr.original = (var, self.cnt)

                exprs.append((newvar, expr))

            fnc.replaceexprs(loc, exprs)

    def rmtmp(self, fnc):
        '''
        Removes (merges) "tmp" or SSA-generated assignments
        '''

        for loc in fnc.locs():

            m = {}
            exprs = []
            primed = set([])
            lastret = None

            # Remember "real" vars and replace temps
            for var, expr in fnc.exprs(loc):

                #expr.statement = True
                
                expr.prime(primed)
                
                for v, e in list(m.items()):
                    expr = expr.replace(v, e)

                    if isinstance(expr, Op) and expr.name == 'ite':
                        expr.args[0].original = None
                        expr.args[1].original = None
                        expr.args[2].original = None

                if var.endswith('&'):
                    m[var] = expr

                else:
                    if var == VAR_RET:
                        lastret = len(exprs)
                        
                    exprs.append((var, expr))
                    
                    if var != VAR_RET:
                        primed.add(var)

            # "Merge" return stmts
            nexprs = []
            retexpr = None
            retcond = None
            for i, (var, expr) in enumerate(exprs):
                if var == VAR_RET:
                    tmpretcond = self.getretcond(expr)
                    if tmpretcond is True or retcond is None:
                        retcond = tmpretcond
                    elif tmpretcond is not None and retcond is not True:
                        retcond = Op(self.OROP, retcond, tmpretcond)
                    if retexpr:
                        retexpr = retexpr.replace(VAR_RET, expr)
                    else:
                        retexpr = expr

                    if i == lastret:
                        nexprs.append((var, retexpr))
                        
                else:
                    if retcond is True:
                        continue
                    elif retcond:
                        expr = Op('ite', Op(self.NOTOP, retcond),
                                  expr, Var(var))
                    nexprs.append((var, expr))

            fnc.replaceexprs(loc, nexprs)

    def getretcond(self, expr):
        if isinstance(expr, Op) and expr.name == 'ite':
            icond = expr.args[0]
            ct = self.getretcond(expr.args[1])
            cf = self.getretcond(expr.args[2])
            cond = []
            if ct is None and cf is None:
                return None
            if ct is True and cf is True:
                return True
            if ct:
                if ct is True:
                    cond.append(icond.copy())
                else:
                    cond.append(Op(self.ANDOP, icond.copy(), ct.copy()))
            if cf:
                nicond = Op(self.NOTOP, icond)
                if cf is True:
                    cond.append(nicond.copy())
                else:
                    cond.append(Op(self.ANDOP, nicond.copy(), cf.copy()))
            if len(cond) == 1:
                return cond[0]
            else:
                return Op(self.OROP, cond[0], cond[1])
            
        elif isinstance(expr, Var) and expr.name == VAR_RET:
            return None
        
        else:
            return True

    def postprocess(self):

        if not self.postproc:
            return

        self.rmemptyfncs()
        for fnc in list(self.prog.fncs.values()):
            self.rmunreachlocs(fnc)
            self.ssa(fnc)
            self.rmtmp(fnc)

    def visit(self, node, name=None):

        # Skip None-node
        if node is None:
            return

        # Name of the node class
        if name is None:
            name = node.__class__.__name__

        # Get method
        meth = getattr(self, 'visit_%s' % (name,), None)
        if meth is None:
            raise NotSupported("Unimplemented visitor: '%s'%s" % (name,
                               " (%s)" % node.value if hasattr(node, "value") else ""))

        # Call visitor method
        return meth(node)

    def visit_expr(self, node, allowlist=False, allownone=False):
        res = self.visit(node)

        if isinstance(res, list) and allowlist:
            ok = True
            for r in res:
                if not isinstance(r, Expr):
                    ok = False
                    break
            if ok:
                return res

        if res and not isinstance(res, Expr):
            raise ParseError("Expected expression, got '%s'" % (res,),
                             line=node.coord.line)

        if (not res) and (not allownone):
            if node:
                self.addwarn("Expression expected at line %s" % (
                    node.coord.line,))
            else:
                self.addwarn("Expression expected")
            res = Const('?')

        return res

    def visit_if(self, node, cond, true, false):

        # Add condition (with new location)
        preloc = self.loc
        condloc = self.addloc('the condition of the if-statement at line %d' % (
            self.getline(cond)
        ))
        condexpr = self.visit_expr(cond, allowlist=True)
        if isinstance(condexpr, list):
            condexpr = self.expr_list_and(condexpr)
        self.addexpr(VAR_COND, condexpr)
        
        # Add true loc
        trueline = self.getline(true) or self.getline(node)
        trueloc = self.addloc('inside the if-branch starting at line %d' % (
            trueline))
        self.visit(true)
        afterloc1 = self.loc

        afterloc = self.addloc('after the if-statement beginning at line %s' % (
            self.getline(node)
        ))

        # Add (general) transitions
        self.addtrans(preloc, True, condloc)
        self.addtrans(condloc, True, trueloc)
        self.addtrans(afterloc1, True, afterloc)

        # Add false loc
        if false:
            falseloc = self.addloc('inside the else-branch starting at line %d' % (
                self.getline(false)))
            self.visit(false)
            afterloc2 = self.loc

            self.addtrans(condloc, False, falseloc)
            self.addtrans(afterloc2, True, afterloc)

        else:
            self.addtrans(condloc, False, afterloc)
            falseloc = None

        # "Loop-less" if-statement
        if trueloc == afterloc1 and ((not false) or falseloc == afterloc2):
            if self.optifs:
                self.optimizeif(preloc, condexpr, trueloc, falseloc)
                return

        self.loc = afterloc

    def optimizeif(self, preloc, condexpr, trueloc, falseloc):
        '''
        Optimized "simple" or "loop-less" if statement
        '''

        # Remove unneded part of the graph
        self.fnc.rmtrans(preloc, True)
        self.loc = preloc

        # Keep track of assigned vars
        varss = set()
        varsl = []
        mt = {}
        mf = {}

        # Add exprs from branches
        def addvars(loc, m):
            for (var, expr) in self.fnc.exprs(loc):
                newvar = self.ssavar(var)

                if var not in varss:
                    varss.add(var)
                    varsl.append(var)

                # Replace vars mapped so far
                for (v1, v2) in list(m.items()):
                    expr = expr.replace(v1, Var(v2))
                expr.original = (var, self.cnt)
                self.addexpr(newvar, expr)

                # Remember replacement
                m[var] = newvar

        addvars(trueloc, mt)
        if falseloc is not None:
            addvars(falseloc, mf)

        # Add condition
        condvar = self.ssavar('$cond')
        self.addexpr(condvar, condexpr.copy())

        # Merge branches
        for var in varsl:
            self.addexpr(var, Op('ite', Var(condvar),
                                 Var(mt.get(var, var)), Var(mf.get(var, var))))

    def expr_list_and(self, exprs):

        if len(exprs) == 0:
            return None
            
        else:
            newexpr = exprs[0]
            for expr in exprs[1:]:
                newexpr = Op('&&', newexpr, expr, line=expr.line)
            return newexpr

    def visit_loop(self, node, init, cond, next, body, do, name, prebody=None):
        
        # Visit init stmts
        if init:
            self.visit(init)

        # Add condition (with new location)
        preloc = self.loc
        if isinstance(cond, Expr):
            condexpr = cond
        else:
            condexpr = self.visit_expr(cond, allowlist=True)
            if isinstance(condexpr, list):
                condexpr = self.expr_list_and(condexpr)
                
        if not condexpr:
            condexpr = Const('1')
        condloc = self.addloc("the condition of the '%s' loop at line %s" % (
            name, condexpr.line or self.getline(node)))
        self.addexpr(VAR_COND, condexpr)

        # Add exit loc
        exitloc = self.addloc("*after* the '%s' loop starting at line %d" % (
            name, self.getline(node)
        ))

        # Add next loc
        if next:
            nextloc = self.addloc("update of the '%s' loop at line %d" % (
                name, self.getline(next)
            ))
            self.visit(next)
        else:
            nextloc = None

        # Add body with (new location)
        bodyloc = self.addloc("inside the body of the '%s' loop beginning at line %d" % (
            name, self.getline(body) or self.getline(node)
        ))
        self.addloop((condloc, exitloc, nextloc))
        if prebody:
            for x in prebody:
                self.addexpr(*x)
        self.visit(body)
        self.poploop()
        afterloc = self.loc

        # Connect transitions
        self.addtrans(preloc, True, bodyloc if do else condloc)
        self.addtrans(condloc, True, bodyloc)
        self.addtrans(condloc, False, exitloc)
        if nextloc:
            self.addtrans(afterloc, True, nextloc)
            self.addtrans(nextloc, True, condloc)
        else:
            self.addtrans(afterloc, True, condloc)

        self.loc = exitloc

    def addfnc(self, name, params, rettype):
        if self.fnc:
            self.fncsl.append((self.fnc, self.loc))
        self.fnc = Function(name, params, rettype)
        self.fncs[name] = self.fnc
        self.prog.addfnc(self.fnc)

    def endfnc(self):
        if self.fncsl:
            self.fnc, self.loc = self.fncsl.pop()
        else:
            self.fnc = None
            self.loc = None

    def addloc(self, desc):
        assert (self.fnc), 'No active fnc!'
        self.loc = self.fnc.addloc(desc=desc)
        return self.loc

    def addexpr(self, name, expr, loc=None, idx=None):
        assert (self.fnc), 'No active fnc!'
        if not loc:
            loc = self.loc
        self.fnc.addexpr(loc, name, expr, idx=idx)

    def numexprs(self, loc=None):
        assert (self.fnc), 'No active fnc!'
        if not loc:
            loc = self.loc
        return self.fnc.numexprs(loc)

    def rmlastexprs(self, loc=None, num=1):
        assert (self.fnc), 'No active fnc!'
        if not loc:
            loc = self.loc
        self.fnc.rmlastexprs(loc, num)
    
    def addtrans(self, loc1, cond, loc2):
        assert (self.fnc), 'No active fnc!'
        self.fnc.addtrans(loc1, cond, loc2)

    def addtype(self, var, type, skiponexist=True):
        assert (self.fnc), 'No active fnc!'
        self.fnc.addtype(var, type, skiponexist)

    def hasvar(self, var):
        assert (self.fnc), 'No active fnc'
        return self.fnc.gettype(var) is not None

    def addloop(self, l):
        self.loops.append(l)

    def poploop(self):
        return self.loops.pop()

    def lastloop(self):
        return self.loops[-1] if len(self.loops) else None

    def isfncname(self, name):
        return name in self.fncs

    @classmethod
    def parse_code(cls, code, *args, **kwargs):
        parser = cls(*args, **kwargs)
        parser.parse(code)
        parser.postprocess()
        if parser.slice:
            parser.prog.slice()
        return parser.prog class ParseError(Exception):
    '''
    Exception denoting that the code cannot be parsed because syntax errors.
    '''

    def __init__(self, msg, line=None):
        super(ParseError, self).__init__(msg) def addlangparser(lang, parser):
    PARSERS[lang] = parser class NotSupported(Exception):
    '''
    Exception denoting that the code being parsed contains unsupported
    elements.
    '''

    def __init__(self, msg, line=None):
        self.line = line
        super(NotSupported, self).__init__(msg) class ParseError(Exception):
    '''
    Exception denoting that the code cannot be parsed because syntax errors.
    '''

    def __init__(self, msg, line=None):
        super(ParseError, self).__init__(msg)
import re
from subprocess import Popen, PIPE
from .model import Var, Const, Op, Expr, VAR_IN, VAR_OUT, VAR_RET
from .parser import Parser, ParseError, addlangparser, NotSupported, ParseError
from pycparser import c_ast, c_parser, plyparser
        pipe = Popen(args, stdout=PIPE, stderr=PIPE, stdin=PIPE,
                     universal_newlines=True)
        code, err = pipe.communicate(code)

        # Get AST
        parser = c_parser.CParser()
        try:
            self.ast = parser.parse(code)
        except plyparser.ParseError as e:
            raise ParseError(str(e))
    
        self.visit(self.ast)

    def visit_FileAST(self, node):
        '''
        FileAST - root node
        Attrs: ext (list)
        '''

        # Visit children
        fncs = set()
        for e in node.ext:
            self.visit(e)

    def visit_FuncDef(self, node):
        '''
        FuncDef - function definition
        Attrs: decl, param_decls, body
        '''

        self.fncdef = True
        (name, rtype, _) = self.visit(node.decl.type.type)

        params = []
        if node.decl.type.args:
            for param in node.decl.type.args.params:
                param = self.visit(param)
                if param == 'void':
                    continue
                if isinstance(param, Var):
                    param = (param.name, 'int')
                else:
                    param = param[:2]
                params.append(param)
                
        self.fncdef = False

        self.addfnc(name, params, rtype)
        for v, t in params:
            self.addtype(v, t)
        
        self.addloc(desc="at the beginning of the function '%s'" % (name,))
        self.visit(node.body)

        self.endfnc()

    def visit_FuncDecl(self, node):
        '''
        Function Declaration
        Attrs: args, type
        '''

        self.fncdef = True
        (name, rtype, _) = self.visit(node.type)
        params = []
        if node.args:
            for param in node.args.params:
                param = self.visit(param)
                if param == 'void':
                    continue
                if isinstance(param, Var):
                    param = (param.name, 'int')
                elif isinstance(param, str):
                    param = ('_', param)
                else:
                    param = param[:2]
                params.append(param)
        self.fncdef = False

        self.addfnc(name, params, rtype)
        
        for v, t in params:
            self.addtype(v, t)

        self.endfnc()

        return (name, rtype, None)
        
    def visit_Compound(self, node):
        '''
        Compound - composition of statements
        Attrs: block_items
        '''

        if node.block_items:
            for item in node.block_items:
                res = self.visit(item)

                if isinstance(res, Op) and res.name == 'FuncCall':
                    self.addexpr('_', res)
                
    def visit_Assignment(self, node):
        '''
        Assignment
        Attrs: op, lvalue, rvalue
        '''

        lvalue = self.visit_expr(node.lvalue)
        postincdec = self.postincdec
        self.postincdec = 0
        rvalue = self.visit(node.rvalue)
        postincdec, self.postincdec = self.postincdec, postincdec

        if not rvalue:
            rvalue = Const('?', line=node.coord.line)
        
        # Cases of assignment operator
        if node.op == '=':
            pass
        elif len(node.op) == 2 and node.op[1] == '=':

            rvalue = Op(node.op[0], lvalue.copy(), rvalue, line=rvalue.line)