#!/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, 2010, 2011 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 DataValue, ReplaceableContext, PlaceholderContext, FragmentObject from rsvplib import Library  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, pc=None, debug=0, abort_upon_exception=0):          """         Initialise the processor with a 'memory' (a list of values containing         instructions and data), the object and parameter lists 'objlist' and         'paramlist', 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.library = None          self.pc = pc or 0         self.debug = debug         self.abort_upon_exception = abort_upon_exception          # Profiling.          self.coverage = [0] * len(self.memory)         self.counter = 0         self.cost = 0          # Stacks.          self.pc_stack = []         self.frame_stack = []         self.local_sp_stack = [0]         self.invocation_sp_stack = []          # Exception handler stacks are used to reset the state of the main         # stacks.          self.handler_stack = [len(self.memory) - 1] # final handler is the end of the code         self.handler_local_sp_stack = []         self.handler_invocation_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.          cls = self._get_class("__builtins__", "AttributeError")         self.attr_error = cls.location         self.attr_error_instance = cls.instance_template_location         cls = self._get_class("__builtins__", "TypeError")         self.type_error = cls.location         self.type_error_instance = cls.instance_template_location         cls = self._get_class("__builtins__", "tuple")         self.tuple_class = cls.location         self.tuple_instance = cls.instance_template_location          # Debugging attributes.          self.breakpoints = set()      def _get_class(self, module, name):         attr = self._objlist.access(module, name)         if attr is not None:             return attr.get_value()         else:             return None      # Debugging methods.      def dump(self):         print "PC", self.pc, "->", self.load(self.pc)         print "PC stack", self.pc_stack         print "Frame stack:"         if self.local_sp_stack:             start = self.local_sp_stack[0]             for end in self.local_sp_stack[1:]:                 print "  %2d" % start, self.frame_stack[start:end]                 start = end             else:                 print "  %2d" % start, self.frame_stack[start:]         print         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, start=None, end=None):         self.show_memory(self.memory[start:end], self.coverage[start:end], start or 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]         coverage = self.coverage[start:end]         self.show_memory(memory, coverage, start)      def show_memory(self, memory, coverage, start):         for i, (c, x) in enumerate(map(None, coverage, memory)):             location = start + i             if location == self.pc:                 print "->",             elif location in self.pc_stack:                 print "..",             else:                 print "  ",             print "%-5s %5d %r" % (c or "", 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)      def up(self):         retaddr = self.pc_stack[-1]         self.set_break(retaddr)         self.run()      # 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."          breakpoint = 0          try:             while 1:                 self.execute()         except EmptyPCStack:             pass         except BreakpointReached:             breakpoint = 1          print "Execution terminated",         if self.exception is not None:             ref = self.exception             addr = self.load(ref + Library.instance_data_offset)             print "with exception:", self.load(ref)             print "At address %d: %r" % (addr, self.load(addr))         elif breakpoint:             print "with breakpoint."             print "At address", self.pc         else:             print "successfully."         print "After", self.counter, "instructions at cost", self.cost, "units."      def test(self, module):          """         Test the code in the memory by running the code and investigating the         contents of variables. Use 'module' to identify result variables.         """          self.run()         success = 1          if self.exception is None:             for name in module.keys():                 if name.startswith("result"):                     label, expected = name.split("_")                     attr = module[name]                      # NOTE: Assumptions about headers and content made.                      attr_location = module.location + 1 + attr.position                     value = self.load(attr_location)                      if value is not None:                         content = self.load(value.ref + Library.instance_data_offset)                         print label, expected, content                         success = success and (int(expected) == content)                     else:                         print label, expected, "missing"                         success = 0              return success         else:             return 0      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 coverage.          self.coverage[self.pc] += 1          # 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, is_input=0):          "Perform the 'instruction', returning the next PC value or None."          if not is_input:             self.counter += 1             self.cost += instruction.cost         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, 1)             self.source = self.value         self.value = value         if self.instruction.input is not None:             self.perform(self.instruction.input, 1)      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.library and self.library.native_functions[addr](self.library)             if handler is None:                 return next             else:                 return handler         else:             self.push_pc(self.pc + 1)             return addr      # Instructions.      def LoadConst(self):         self.value = DataValue(self.operand, self.operand)      def LoadClass(self):         self.value = DataValue(PlaceholderContext, self.operand)      def LoadFunction(self):         self.value = DataValue(ReplaceableContext, self.operand)      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 # uses the source value      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):         value = self.load(self.operand)         inst_value = self.value         self.value = DataValue(inst_value.ref, value.ref)      def LoadAddressContextCond(self):         value = self.load(self.operand)         inst_value = self.value         self.value = self._LoadAddressContextCond(value.context, value.ref, inst_value.ref)      def StoreAddress(self):         # Preserve context.         self.save(self.operand, self.source)      def StoreAddressContext(self):         # Overwrite context if null.         context_value = self.value         source_value = self.source         if source_value.context is ReplaceableContext:             context = context_value.ref         else:             context = source_value.context         self.save(self.operand, DataValue(context, source_value.ref))      def MakeInstance(self):         size = self.operand         value = self.value         # NOTE: Referencing the instance template.         addr = self._MakeObject(size, value.ref - Library.instance_template_size)         # Introduce object as context for the new object.         self.value = DataValue(addr, addr)      def MakeFragment(self):         size = self.operand         # Reserve twice the amount of space.         addr = self._MakeFragment(size, size * 2)         # NOTE: Context is not relevant for fragments.         self.value = DataValue(None, addr)      def LoadAttr(self):         value = self.value         # Retrieved context should already be appropriate for the instance.         # NOTE: Adding 1 to skip any header.         self.value = self.load(value.ref + self.operand + 1)      def StoreAttr(self):         value = self.value         # Target should already be an instance.         # NOTE: Adding 1 to skip any header.         self.save(value.ref + self.operand + 1, self.source)      def LoadAttrIndex(self):         value = self.value         data = self.load(value.ref)         element = self.objlist[data.classcode + self.operand]          if element is not None:             attr_index, static_attr, offset = element             if attr_index == self.operand:                 if static_attr:                     self.value = self.load(offset) # offset is address of class/module attribute                 else:                     self.value = self.load(value.ref + offset)                 return          self.exception = self._MakeObject(Library.instance_size, self.attr_error_instance)         return self.RaiseException()      # LoadAttrIndexContext not defined.      def LoadAttrIndexContextCond(self):         inst_value = self.value         data = self.load(inst_value.ref)         element = self.objlist[data.classcode + self.operand]          if element is not None:             attr_index, static_attr, offset = element             if attr_index == self.operand:                 if static_attr:                     loaded_value = self.load(offset) # offset is address of class/module attribute                     if data.attrcode is None: # absent attrcode == class/module                         self.value = loaded_value                     else:                         self.value = self._LoadAddressContextCond(loaded_value.context, loaded_value.ref, inst_value.ref)                 else:                     self.value = self.load(inst_value.ref + offset)                 return          self.exception = self._MakeObject(Library.instance_size, self.attr_error_instance)         return self.RaiseException()      def StoreAttrIndex(self):         value = self.value         data = self.load(value.ref)         element = self.objlist[data.classcode + self.operand]          if element is not None:             attr_index, static_attr, offset = element             if attr_index == self.operand:                 if static_attr:                     self.exception = self._MakeObject(Library.instance_size, self.type_error_instance)                     return self.RaiseException()                 else:                     self.save(value.ref + offset, self.source)                     return          self.exception = self._MakeObject(Library.instance_size, self.attr_error_instance)         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()         del self.frame_stack[frame:] # reset stack before call      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):         value = self.value         frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame         data = self.load(value.ref)         element = self.paramlist[data.funccode + self.operand]          if element is not None:             # 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] = self.source                 return          self.exception = self._MakeObject(Library.instance_size, self.type_error_instance)         return self.RaiseException()      def LoadCallable(self):         value = self.value         data = self.load(value.ref)         self.callable = data.codeaddr      def StoreCallable(self):         value = self.value         # NOTE: Should improve the representation and permit direct saving.         data = self.load(value.ref)         self.save(value.ref, data.with_callable(self.callable))      def LoadContext(self):         value = self.value         # NOTE: Omission of the context of the context would make things like         # NOTE: self() inside methods impossible.         self.value = DataValue(value.context, value.context)      def CheckContext(self):         self.status = self.value.ref is not ReplaceableContext      def CheckClass(self):         value = self.value         if value.ref in (ReplaceableContext, PlaceholderContext):             self.status = 0             return          data = self.load(value.ref)          # Classes are not themselves usable as the self argument.         # NOTE: This may change at some point.         # However, where classes appear as the context, instance         # compatibility is required in the first argument.          self.status = data.attrcode is None # absent attrcode == class      def CheckFrame(self):         (nargs, ndefaults) = self.operand          # The frame is actually installed as the locals.         # Retrieve the context from the first local.          frame = self.local_sp_stack[-1]         nlocals = len(self.frame_stack[frame:])          if not ((nargs - ndefaults) <= nlocals):             raise Exception, "CheckFrame %r (%r <= %r <= %r)" % (self.operand, nargs - ndefaults, nlocals, nargs)             self.exception = self._MakeObject(Library.instance_size, self.type_error_instance)             return self.RaiseException()      def CheckExtra(self):         nargs = self.operand          # The frame is actually installed as the locals.         # Retrieve the context from the first local.          frame = self.local_sp_stack[-1]         nlocals = len(self.frame_stack[frame:])          # Provide the extra star parameter if necessary.          if nlocals == nargs:             self.frame_stack.extend([None]) # ExtendFrame(1)      def FillDefaults(self):         value = self.value         (nargs, ndefaults) = self.operand          # The frame is actually installed as the locals.          frame = self.local_sp_stack[-1]         nlocals = len(self.frame_stack[frame:])          # Support population of defaults.         # This involves copying the "attributes" of a function into the frame.          default = nlocals - (nargs - ndefaults)         self.frame_stack.extend([None] * (nargs - nlocals))         pos = nlocals          while pos < nargs:             self.frame_stack[frame + pos] = self.load(value.ref + default + 1) # skip header             default += 1             pos += 1      def CopyExtra(self):         start = self.operand          # The frame is the source of the extra arguments.          frame = self.local_sp_stack[-1]         nlocals = len(self.frame_stack[frame:])          # Make a tuple to hold the arguments.          ref = self._MakeObject(nlocals - start + 1, self.tuple_instance)          extra = 0         pos = start          while pos < nlocals:             self.save(ref + extra + 1, self.frame_stack[frame + pos]) # skip header when storing             extra += 1             pos += 1          self.value = DataValue(ref, ref)      def CheckInstance(self):         value = self.value         target_value = self.source          # For the 'self' parameter in an invoked function, the proposed context         # ('self') is checked against the target's context.          self.status = self._CheckInstance(value.ref, target_value.ref)      def CheckType(self):         value = self.value         target_value = self.operand         self.status = self._CheckType(value.ref, target_value.ref)      def JumpInFrame(self):         codeaddr = self.callable         return self.jump(codeaddr, self.pc + 1) # return to the instruction after this one      def JumpWithFrame(self):         codeaddr = 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 JumpWithFrameDirect(self):         operand = self.operand         self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame         return self.jump(operand, self.pc + 1) # return to the instruction after this one      def ExtendFrame(self):         self.frame_stack.extend([None] * self.operand)      def AdjustFrame(self):         self.invocation_sp_stack[-1] += 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 = DataValue(self.exception, self.exception)      def StoreException(self):         self.exception = self.value.ref      def ClearException(self):         self.exception = None      def RaiseException(self):         # NOTE: Adding the program counter as the first attribute after __class__.         self.save(self.exception + Library.instance_data_offset, self.pc)         # Jumping to the current handler.         if self.abort_upon_exception:             raise Exception         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_invocation_sp_stack.append(len(self.invocation_sp_stack))         self.handler_pc_stack.append(len(self.pc_stack))      def PopHandler(self):         nframes = self.operand         # Get the new local frame pointer and PC stack references.         local_sp_top = self.handler_local_sp_stack[-nframes]         invocation_sp_top = self.handler_invocation_sp_stack[-nframes]         pc_top = self.handler_pc_stack[-nframes]         # Reduce the local frame pointer stack to refer to the handler's frame.         del self.local_sp_stack[local_sp_top:]         # Reduce the invocation frame pointer stack to refer to an outer frame.         del self.invocation_sp_stack[invocation_sp_top:]         # Reduce the PC stack to discard all superfluous return addresses.         del self.pc_stack[pc_top:]         # Remove elements from the handler stacks.         del self.handler_pc_stack[-nframes:]         del self.handler_local_sp_stack[-nframes:]         del self.handler_invocation_sp_stack[-nframes:]         del self.handler_stack[-nframes:]      def CheckException(self):         self.status = self.exception is not None and self._CheckInstance(self.exception, self.value.ref)      def TestIdentity(self):         self.status = self.value.ref == self.source.ref      def TestIdentityAddress(self):         self.status = self.value.ref == 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 instance vs. class.          if data.attrcode is None: # absent attrcode == class/module             return 0          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]          if element is not None:             attr_index, static_attr, offset = element             return attr_index == data.attrcode         else:             return 0      def _CheckType(self, ref, cls):         data = self.load(ref)         target_data = self.load(cls)          # Insist on instance vs. class.          if data.attrcode is None: # absent attrcode == class/module             return 0          if target_data.attrcode is not None: # present attrcode == instance             return 0          # Return whether the types match.          return data.classcode == target_data.classcode      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 _MakeFragment(self, occupied, size):         addr = self.new(size)         # Save the header, overriding the size.         self.save(addr, FragmentObject(occupied, size))         return addr      def _LoadAddressContextCond(self, context, ref, inst_ref):         # Check the instance context against the target's context.         # This provides the context overriding for methods.         if context is ReplaceableContext or context is not PlaceholderContext and self._CheckInstance(inst_ref, context):             # Replace the context with the instance.             return DataValue(inst_ref, ref)         else:             return DataValue(context, ref)  # Convenience functions.  def machine(program, with_builtins=0, debug=0, abort_upon_exception=0):     print "Making the image..."     code = program.get_image(with_builtins)     print "Getting raw structures..."     ot = program.get_object_table()     pt = program.get_parameter_table()     objlist = ot.as_list()     paramlist = pt.as_list()     print "Getting raw image..."     rc = program.get_raw_image()     print "Initialising the machine..."     importer = program.get_importer()     constants = {}     for x in (True, False, NotImplemented):         constants[x] = importer.get_constant(x).location     rm = RSVPMachine(rc, objlist, paramlist, debug=debug, abort_upon_exception=abort_upon_exception)     library = Library(rm, constants)     rm.library = library     rm.pc = program.code_location     print "Returning program occupying %d locations." % len(rm.memory)     return rm  # vim: tabstop=4 expandtab shiftwidth=4