"""
Simplified VM code which works for some cases.
You need extend/rewrite code to pass all cases.
"""

import builtins
import dis
import types
import typing as tp
import operator
import sys
import collections


class Frame:
    def __init__(self, f_code: types.CodeType,
                 f_locals: tp.Dict[str, tp.Any],
                 f_globals: tp.Dict[str, tp.Any],
                 f_prev: tp.Any):
        self.f_code = f_code
        self.f_globals = f_globals
        self.f_locals = f_locals
        self.f_prev = f_prev
        self.stack: tp.Any = []
        self.block_stack: tp.Any = []

        if f_prev:
            self.builtins = f_prev.builtins
        else:
            self.builtins = builtins.__dict__

        self.cur_idx = 0
        self.co_names = f_code.co_names
        self.co_consts = f_code.co_consts
        self.co_varnames = f_code.co_varnames
        self.instructions = list(dis.get_instructions(f_code))


def equal_type(l: tp.Any, r: tp.Any) -> bool:
    return isinstance(l, type(r))


class Block(object):
    def __init__(self, type: tp.Any, handler: tp.Any, frame: tp.Any) -> None:
        self.type = type
        self.handler = handler
        self.frame = frame


def build_code_object() -> types.CodeType:
    code_str = ''
    return compile(code_str, '', 'exec')


frame_object = Frame(build_code_object(), {}, {}, {})


class VirtualMachine:
    def __init__(self) -> None:
        self.frames: tp.Any = []
        self.frame = frame_object  # Remove it later (change for None)
        self.last_exception: tp.Any = ()
        self.value = None

        self.operations = {
            'POWER': operator.pow,
            'MULTIPLY': operator.mul,
            'MATRIX_MULTIPLY': operator.matmul,
            'FLOOR_DIVIDE': operator.floordiv,
            'TRUE_DIVIDE': operator.truediv,
            'MODULO': operator.mod,
            'ADD': operator.add,
            'SUBTRACT': operator.sub,
            'SUBSCR': operator.getitem,
            'LSHIFT': operator.lshift,
            'RSHIFT': operator.rshift,
            'AND': operator.and_,
            'XOR': operator.xor,
            'OR': operator.or_,
        }

        self.compare_funcs = {
            '<': operator.lt,
            '<=': operator.le,
            '==': operator.eq,
            '!=': operator.ne,
            '>=': operator.ge,
            '>': operator.gt,
            'in': lambda x, y: x in y,
            'not in': lambda x, y: x not in y,
            'is': lambda x, y: x is y,
            'is not': lambda x, y: x is not y,
            'exception match': equal_type,
        }

    def run(self, code: types.CodeType) -> None:
        """
        :param code: code for interpreting
        """
        frame = Frame(code, {}, {}, None)
        self.run_frame(frame)

    def pop_frame(self) -> tp.Any:
        self.frames.pop()
        self.frame = self.frames[-1] if self.frames else None

    def push_frame(self, frame: tp.Any) -> None:
        self.frames.append(frame)
        self.frame = frame

    def push(self, *args: tp.Any) -> tp.Any:
        for arg in args:
            self.frame.stack.append(arg)

    def pop(self) -> tp.Any:
        return self.frame.stack.pop()

    def popn(self, n: int) -> tp.Any:
        return list(reversed([self.pop() for _ in range(n)])) if n else []

    def top(self) -> tp.Any:
        return self.frame.stack[-1]

    def pop_block(self) -> tp.Any:
        return self.frame.block_stack.pop()

    def push_block(self, type: tp.Any, delta: tp.Any = None) -> tp.Any:
        self.frame.block_stack.append(Block(type, delta, self.frame))

    def parse_byte_and_args(self) -> tp.Tuple[str, tp.Optional[int]]:
        instruction = self.frame.instructions[self.frame.cur_idx]
        byte_name = instruction.opname
        arg = instruction.arg
        self.frame.cur_idx += 1
        return byte_name, arg

    def run_func(self, byte_name: str, argument: tp.Optional[int]) -> str:
        try:
            result = ''
            if byte_name.split("_")[0] == "BINARY":
                self.run_binary_operation(byte_name)
            elif byte_name.split("_")[0] == "INPLACE":
                self.run_inplace_operation(byte_name)
            else:
                bytecode_func = getattr(self, byte_name)
                if argument:
                    return bytecode_func(argument)
                else:
                    return bytecode_func()
        except Exception:
            result = 'exception'
            self.last_exception = sys.exc_info()[:2] + (None,)
        return result

    def handle_exception(self) -> bool:
        if self.frame.block_stack:
            cur_block = self.pop_block()
            if cur_block.type == "except":
                self.push_block('except-handler')
                exc_type, value, tb = self.last_exception
                self.push(tb, value, exc_type)
                self.push(tb, value, exc_type)
                self.frame.cur_idx = cur_block.delta
                return True
        return False

    def run_frame(self, frame: tp.Any) -> tp.Any:
        self.push_frame(frame)
        func_result: tp.Any = None
        while len(self.frame.instructions) > frame.cur_idx:
            byte_name, arg = self.parse_byte_and_args()
            func_result = self.run_func(byte_name, arg)
            if func_result == "exception":
                handled = self.handle_exception()
                if not handled:
                    exception, value, traceback = self.last_exception
                    exc = exception(value)
                    exc.__traceback__ = traceback
                    raise exc
            if func_result == "yield":
                func_result = False
                break

        self.pop_frame()
        return func_result

    def find_associated(self, name: str) -> str:
        if name in self.frame.f_locals:
            val = self.frame.f_locals[name]
        elif name in self.frame.co_varnames:
            raise UnboundLocalError("local variable '%s' referenced before assignment" % name)
        elif name in self.frame.f_globals:
            val = self.frame.f_globals[name]
        elif name in self.frame.builtins:
            val = self.frame.builtins[name]
        else:
            raise NameError("variable '%s' is not defined" % name)
        return val

    def run_binary_operation(self, operation: str) -> None:
        arg1, arg2 = self.popn(2)
        operation_name = operation.replace("BINARY_", "")
        self.push(self.operations[operation_name](arg1, arg2))

    def run_inplace_operation(self, operation: str) -> None:
        arg1, arg2 = self.popn(2)
        operation_name = operation.replace("INPLACE_", "")
        self.push(self.operations[operation_name](arg1, arg2))

    def call_func_op(self, arg: int) -> None:
        args = self.popn(arg)
        f = self.pop()
        self.push(f(*args))