#!/usr/bin/env python

"""

A really simple virtual processor employing a simple set of instructions which

ignore low-level operations and merely concentrate on variable access, structure

access, structure allocation and function invocations.

Copyright (C) 2007, 2008, 2009 Paul Boddie <paul@boddie.org.uk>

This program is free software; you can redistribute it and/or modify it under

the terms of the GNU General Public License as published by the Free Software

Foundation; either version 3 of the License, or (at your option) any later

version.

This program is distributed in the hope that it will be useful, but WITHOUT

ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS

FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more

details.

You should have received a copy of the GNU General Public License along with

this program.  If not, see <http://www.gnu.org/licenses/>.

--------

The execution model of the virtual processor involves the following things:

  * Memory                          contains constants, global variable

                                    references and program code

  * PC (program counter) stack      contains the return address associated

                                    with each function invocation

  * Frame stack                     contains invocation frames in use and in

                                    preparation plus temporary storage

  * Local frame pointer stack       refers to the frames in the frame stack

  * Invocation frame pointer stack

  * Exception handler stack

  * Exception handler locals stack  refers to the state of the local frame

                                    pointer stack

  * Exception handler PC stack      refers to the state of the PC stack

  * Registers: current value,

               boolean status value,

               source value,

               current result,

               current exception,

               current callable

"""

from micropython.program import DataObject # for creating "nice" new objects

class IllegalInstruction(Exception):

    pass

class IllegalAddress(Exception):

    def __init__(self, address):

        self.address = address

    def __repr__(self):

        return "IllegalAddress(%r)" % self.address

    def __str__(self):

        return repr(self)

class EmptyPCStack(Exception):

    pass

class EmptyFrameStack(Exception):

    pass

class BreakpointReached(Exception):

    pass

class RSVPMachine:

    "A really simple virtual processor."

    def __init__(self, memory, objlist, paramlist, true_constant, false_constant, pc=None, debug=0):

        """

        Initialise the processor with a 'memory' (a list of values containing

        instructions and data), the object and parameter lists 'objlist' and

        'paramlist', the addresses 'true_constant' and 'false_constant', and the

        optional program counter 'pc'.

        """

        self.memory = memory

        self._objlist = objlist

        self._paramlist = paramlist

        self.objlist = objlist.as_raw()

        self.paramlist = paramlist.as_raw()

        self.true_constant = true_constant

        self.false_constant = false_constant

        self.pc = pc or 0

        self.debug = debug

        # Stacks.

        self.pc_stack = []

        self.frame_stack = []

        self.local_sp_stack = [0]

        self.invocation_sp_stack = []

        self.handler_stack = [len(self.memory) - 1] # final handler is the end of the code

        self.handler_local_sp_stack = []

        self.handler_pc_stack = []

        # Registers.

        self.instruction = None

        self.operand = None

        self.value = None

        self.status = None

        self.source = None

        self.callable = None

        self.result = None

        self.exception = None

        # Constants.

        self.attr_error = objlist.access("__builtins__", "AttributeError").get_value().location

        self.type_error = objlist.access("__builtins__", "TypeError").get_value().location

        # Native class constants.

        cls = objlist.access("__builtins__", "int")

        self.int_class_location = cls and cls.get_value() and cls.get_value().location

        self.int_instance_location = cls and cls.get_value() and cls.get_value().instance_template_location

        cls = objlist.access("__builtins__", "list")

        self.list_instance_location = cls and cls.get_value() and cls.get_value().instance_template_location

        # Debugging attributes.

        self.breakpoints = set()

    # Debugging methods.

    def dump(self):

        print "PC", self.pc, "->", self.load(self.pc)

        print "PC stack", self.pc_stack

        print "Frame stack", self.frame_stack

        print "Local stack pointers", self.local_sp_stack

        print "Invocation stack pointers", self.invocation_sp_stack

        print "Handler stack", self.handler_stack

        print "Handler frame stack", self.handler_local_sp_stack

        print "Handler PC stack", self.handler_pc_stack

        print

        print "Instruction", self.instruction

        print "Operand", self.operand

        print "Value", self.value

        print "Status", self.status

        print "Source", self.source

        print "Callable", self.callable

        print "Result", self.result

        print "Exception", self.exception

    def show(self):

        self.show_memory(self.memory, 0)

    def show_pc(self, run_in=10):

        start = max(0, self.pc - run_in)

        end = self.pc + run_in

        memory = self.memory[start:end]

        self.show_memory(memory, start)

    def show_memory(self, memory, start):

        for i, x in enumerate(memory):

            location = start + i

            if location == self.pc:

                print "->",

            else:

                print "  ",

            print "%5d %r" % (location, x)

    def step(self, dump=0):

        self.execute()

        self.show_pc()

        if dump:

            self.dump()

    def set_break(self, location):

        self.breakpoints.add(location)

    # Internal operations.

    def load(self, address):

        "Return the value at the given 'address'."

        try:

            return self.memory[address]

        except IndexError:

            raise IllegalAddress(address)

        except TypeError:

            raise IllegalAddress(address)

    def save(self, address, value):

        "Save to the given 'address' the specified 'value'."

        try:

            self.memory[address] = value

        except IndexError:

            raise IllegalAddress(address)

        except TypeError:

            raise IllegalAddress(address)

    def new(self, size):

        """

        Allocate space of the given 'size', returning the address of the space.

        """

        addr = len(self.memory)

        for i in range(0, size):

            self.memory.append(None)

        return addr

    def push_pc(self, data):

        "Push 'data' onto the PC stack."

        self.pc_stack.append(data)

    def pull_pc(self):

        "Pull a value from the PC stack and return it."

        try:

            return self.pc_stack.pop()

        except IndexError:

            raise EmptyPCStack

    def run(self):

        "Execute code in the memory, starting from the current PC address."

        try:

            while 1:

                self.execute()

        except EmptyPCStack:

            pass

    def execute(self):

        "Execute code in the memory at the current PC address."

        if self.pc in self.breakpoints:

            self.breakpoints.remove(self.pc)

            raise BreakpointReached

        self.instruction = self.load(self.pc)

        # Process any inputs of the instruction.

        self.process_inputs()

        # Perform the instruction itself.

        next_pc = self.perform(self.instruction)

        # Update the program counter.

        if next_pc is None:

            self.pc += 1

        else:

            self.pc = next_pc

    def get_method(self, instruction):

        "Return the handler method for the given 'instruction'."

        instruction_name = instruction.__class__.__name__

        if self.debug:

            print "%8d %s" % (self.pc, instruction_name)

        method = getattr(self, instruction_name, None)

        if method is None:

            raise IllegalInstruction, (self.pc, instruction_name)

        return method

    def perform(self, instruction):

        "Perform the 'instruction', returning the next PC value or None."

        self.operand = instruction.get_operand()

        method = self.get_method(instruction)

        return method()

    def process_inputs(self):

        """

        Process any inputs of the current instruction. This permits any directly

        connected sub-instructions to produce the effects that separate

        instructions would otherwise have.

        """

        value = self.value

        if self.instruction.source is not None:

            self.perform(self.instruction.source)

            self.source = self.value

        self.value = value

        if self.instruction.input is not None:

            self.perform(self.instruction.input)

    def jump(self, addr, next):

        """

        Jump to the subroutine at (or identified by) 'addr'. If 'addr'

        identifies a library function then invoke the library function and set

        PC to 'next' afterwards; otherwise, set PC to 'addr'.

        """

        # Trap library functions introduced through the use of strings instead

        # of proper locations.

        if isinstance(addr, str):

            handler = self.native_functions[addr](self)

            if handler is None:

                return next

            else:

                return handler

        else:

            self.push_pc(self.pc + 1)

            return addr

    # Instructions.

    def LoadConst(self):

        self.value = None, self.operand # context of constant is not interesting

    def LoadName(self):

        frame = self.local_sp_stack[-1]

        self.value = self.frame_stack[frame + self.operand]

    def StoreName(self):

        frame = self.local_sp_stack[-1]

        self.frame_stack[frame + self.operand] = self.source

    LoadTemp = LoadName

    def StoreTemp(self):

        frame = self.local_sp_stack[-1]

        self.frame_stack[frame + self.operand] = self.value

    def LoadAddress(self):

        # Preserve context (potentially null).

        self.value = self.load(self.operand)

    def LoadAddressContext(self):

        context, ref = self.load(self.operand)

        inst_context, inst_ref = self.value

        self.value = inst_ref, ref

    def LoadAddressContextCond(self):

        context, ref = self.load(self.operand)

        inst_context, inst_ref = self.value

        self.value = self._LoadAddressContextCond(context, ref, inst_context, inst_ref)

    def StoreAddress(self):

        # Preserve context.

        self.save(self.operand, self.source)

    def MakeObject(self):

        size = self.operand

        context, ref = self.value

        # NOTE: Referencing the instance template.

        addr = self._MakeObject(size, ref - 1)

        # Introduce object as context for the new object.

        self.value = addr, addr

    def LoadAttr(self):

        context, ref = self.value

        # Retrieved context should already be appropriate for the instance.

        # NOTE: Adding 1 to skip any header.

        self.value = self.load(ref + self.operand + 1)

    def StoreAttr(self):

        context, ref = self.value

        # Target should already be an instance.

        # NOTE: Adding 1 to skip any header.

        self.save(ref + self.operand + 1, self.source)

    def LoadAttrIndex(self):

        context, ref = self.value

        data = self.load(ref)

        element = self.objlist[data.classcode + self.operand]

        attr_index, class_attr, offset = element

        if attr_index == self.operand:

            if class_attr:

                self.value = self.load(offset) # offset is address of class attribute

            else:

                self.value = self.load(ref + offset)

        else:

            self.exception = self.attr_error

            return self.RaiseException()

    def LoadAttrIndexContext(self):

        context, ref = self.value

        data = self.load(ref)

        element = self.objlist[data.classcode + self.operand]

        attr_index, class_attr, offset = element

        if attr_index == self.operand:

            loaded_context, loaded_ref = self.load(offset) # offset is address of class attribute

            self.value = ref, loaded_ref

        else:

            self.exception = self.attr_error

            return self.RaiseException()

    def LoadAttrIndexContextCond(self):

        context, ref = self.value

        data = self.load(ref)

        element = self.objlist[data.classcode + self.operand]

        attr_index, class_attr, offset = element

        if attr_index == self.operand:

            if class_attr:

                loaded_context, loaded_ref = self.load(offset) # offset is address of class attribute

                self.value = self._LoadAddressContextCond(loaded_context, loaded_ref, context, ref)

            else:

                self.value = self.load(ref + offset)

        else:

            self.exception = self.attr_error

            return self.RaiseException()

    # NOTE: LoadAttrIndexContextCond will test context compatibility.

    def StoreAttrIndex(self):

        context, ref = self.value

        data = self.load(ref)

        element = self.objlist[data.classcode + self.operand]

        attr_index, class_attr, offset = element

        if attr_index == self.operand:

            if class_attr:

                self.exception = self.type_error

                return self.RaiseException()

            else:

                self.save(ref + offset, self.source)

        else:

            self.exception = self.attr_error

            return self.RaiseException()

    # NOTE: LoadAttrIndexContext is a possibility if a particular attribute can always be overridden.

    def MakeFrame(self):

        self.invocation_sp_stack.append(len(self.frame_stack))

        self.frame_stack.extend([None] * self.operand)

    def DropFrame(self):

        self.local_sp_stack.pop()

        frame = self.invocation_sp_stack.pop()

        self.frame_stack = self.frame_stack[:frame] # reset stack before call

    def RecoverFrame(self):

        self.local_sp_stack.pop()

    def StoreFrame(self):

        frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame

        self.frame_stack[frame + self.operand] = self.value

    def StoreFrameIndex(self):

        context, ref = self.value

        frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame

        data = self.load(ref)

        element = self.paramlist[data.funccode + self.operand]

        # NOTE: Need to ensure correct positioning where a context has been generated.

        param_index, offset = element

        if param_index == self.operand:

            self.frame_stack[frame + offset + 1] = self.source # add 1 to skip the context always generated

        else:

            self.exception = self.type_error

            return self.RaiseException()

    def LoadCallable(self):

        context, ref = self.value

        data = self.load(ref)

        self.callable = data.codeaddr, data.codedetails

    def StoreCallable(self):

        context, ref = self.value

        # NOTE: Should improve the representation and permit direct saving.

        data = self.load(ref)

        self.save(ref, (data.classcode, data.attrcode) + self.callable)

    def LoadContext(self):

        context, ref = self.value

        self.value = None, context # context of context is not interesting

    def CheckFrame(self):

        operand = self.operand

        frame = self.invocation_sp_stack[-1]

        context, ref = self.value

        data = self.load(ref)

        # Support sliding of the frame to exclude any inappropriate context.

        if context is None:

            self.invocation_sp_stack[-1] += 1

            operand -= 1

        else:

            context_data = self.load(context)

            if context_data.attrcode is None: # absent attrcode == class

                self.invocation_sp_stack[-1] += 1

                operand -= 1

        # Test the frame size.

        nargs, ndefaults = data.codedetails

        if not ((nargs - ndefaults) <= operand <= nargs):

            raise Exception, "CheckFrame %r (%r <= %r <= %r)" % (self.operand, nargs - ndefaults, operand, nargs)

        # Support population of defaults.

        # This involves copying the "attributes" of a function into the frame.

        default = operand - (nargs - ndefaults)

        self.frame_stack.extend([None] * (nargs - operand))

        pos = self.operand

        while operand < nargs:

            self.frame_stack[frame + pos] = self.load(ref + default + 1) # skip header

            default += 1

            pos += 1

            operand += 1

    def CheckSelf(self):

        context, ref = self.value

        target_context, target_ref = self.source

        # Check the details of the proposed context and the target's context.

        self.status = self._CheckInstance(ref, target_context)

    def JumpWithFrame(self):

        codeaddr, codedetails = self.callable

        self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame

        return self.jump(codeaddr, self.pc + 1) # return to the instruction after this one

    def ExtendFrame(self):

        self.frame_stack.extend([None] * self.operand)

    def AdjustFrame(self):

        if self.operand > 0:

            self.frame_stack.append([None] * self.operand)

        elif self.operand == -1:

            self.invocation_sp_stack[-1] -= 1

        else:

            raise Exception, "AdjustFrame %r" % self.operand

    def Return(self):

        return self.pull_pc()

    def LoadResult(self):

        self.value = self.result

    def StoreResult(self):

        self.result = self.value

    def Jump(self):

        return self.operand

    def JumpIfTrue(self):

        if self.status:

            return self.operand

    def JumpIfFalse(self):

        if not self.status:

            return self.operand

    def LoadException(self):

        self.value = self.exception, self.exception

    def StoreException(self):

        self.exception = self.value[1]

    def RaiseException(self):

        return self.handler_stack[-1]

    def PushHandler(self):

        self.handler_stack.append(self.operand)

        self.handler_local_sp_stack.append(len(self.local_sp_stack))

        self.handler_pc_stack.append(len(self.pc_stack))

    def PopHandler(self):

        # Reduce the local frame pointer stack to refer to the handler's frame.

        self.local_sp_stack = self.local_sp_stack[:self.handler_local_sp_stack.pop()]

        # Reduce the PC stack to discard all superfluous return addresses.

        self.pc_stack = self.pc_stack[:self.handler_pc_stack.pop()]

        self.handler_stack.pop()

    def CheckException(self):

        self.status = self.exception is not None and self._CheckInstance(self.exception, self.value[1])

    def TestIdentity(self):

        self.status = self.value[1] == self.source[1]

    def TestIdentityAddress(self):

        self.status = self.value[1] == self.operand

    # LoadBoolean is implemented in the generated code.

    # StoreBoolean is implemented by testing against the True value.

    def InvertBoolean(self):

        self.status = not self.status

    # Common implementation details.

    def _CheckInstance(self, ref, cls):

        data = self.load(ref)

        target_data = self.load(cls)

        # Insist on a class.

        if target_data.attrcode is not None: # present attrcode == instance

            return 0

        # Find the table entry for the descendant.

        element = self.objlist[target_data.classcode + data.attrcode]

        attr_index, class_attr, offset = element

        return attr_index == data.attrcode

    def _MakeObject(self, size, ref):

        # Load the template.

        data = self.load(ref)

        addr = self.new(size)

        # Save the header, overriding the size.

        self.save(addr, data.with_size(size))

        return addr

    def _LoadAddressContextCond(self, context, ref, inst_context, inst_ref):

        # Check the instance context against the target's context.

        if self._CheckInstance(inst_ref, context):

            # Replace the context with the instance.

            return inst_ref, ref

        else:

            return context, ref

    # Native function implementations.

    def builtins_int_add(self):

        frame = self.local_sp_stack[-1]

        # Get operands addresses.

        left_context, left = self.frame_stack[frame]

        right_context, right = self.frame_stack[frame + 1]

        # Test operand suitability.

        if not self._CheckInstance(left, self.int_class_location) and self._CheckInstance(right, self.int_class_location):

            self.exception = self.type_error

            return self.RaiseException()

        # NOTE: Assume single location for data.

        left_data = left + 1

        right_data = right + 1

        # Make a new object.

        addr = self._MakeObject(2, self.int_instance_location)

        # Store the result.

        # NOTE: The data is considered ready to use.

        self.save(addr + 1, self.load(left_data) + self.load(right_data))

        # Return the new object.

        # Introduce object as context for the new object.

        self.result = addr, addr

    def builtins_int_bool(self):

        frame = self.local_sp_stack[-1]

        # Get operands addresses.

        left_context, left = self.frame_stack[frame]

        # Test operand suitability.

        if not self._CheckInstance(left, self.int_class_location):

            self.exception = self.type_error

            return self.RaiseException()

        # NOTE: Assume single location for data.

        left_data = left + 1

        # Test the data.

        # NOTE: The data is considered ready to use.

        if self.load(left_data) != 0:

            self.result = self.true_constant, self.true_constant

        else:

            self.result = self.false_constant, self.false_constant