#!/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 context/value,                source context/value,                current result context/value,                current exception value,                boolean status value,                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.value = None         self.context = None          self.source_value = None         self.source_context = None          self.result_value = None         self.result_context = None          self.exception = None          self.instruction = None         self.status = None         self.callable = 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 "Value", self.value         print "Context", self.context         print         print "Source value", self.source_value         print "Source context", self.source_context         print         print "Result value", self.result_value         print "Result context", self.result_context         print         print "Exception", self.exception         print         print "Instruction", self.instruction         print "Status", self.status         print "Callable", self.callable      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         operand = instruction.get_operand()         method = self.get_method(instruction)         return method(operand)      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, context = self.value, self.context         if self.instruction.source is not None:             self.perform(self.instruction.source, 1)             self.source_value, self.source_context = self.value, self.context         self.value, self.context = value, context         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      # Low-level instructions.      def LoadValue(self, operand):         self.value = operand      def LoadContext(self, operand):         self.context = operand      def LoadSourceValue(self, operand):         self.source_value = operand      def LoadSourceContext(self, operand):         self.source_context = operand      # Instructions.      def LoadConst(self, operand):         self.LoadContext(operand)         self.LoadValue(operand)      def LoadClass(self, operand):         self.LoadContext(PlaceholderContext)         self.LoadValue(operand)      def LoadFunction(self, operand):         self.LoadContext(ReplaceableContext)         self.LoadValue(operand)      def LoadName(self, operand):         frame = self.local_sp_stack[-1]         data = self.frame_stack[frame + operand]         self.LoadContext(data.context)         self.LoadValue(data.ref)      def StoreName(self, operand):         frame = self.local_sp_stack[-1]         self.frame_stack[frame + operand] = DataValue(self.source_context, self.source_value)      LoadTemp = LoadName      def StoreTemp(self, operand):         frame = self.local_sp_stack[-1]         self.frame_stack[frame + operand] = DataValue(self.context, self.value)      def LoadAddress(self, operand):         # Preserve context (potentially null).         data = self.load(operand)         self.LoadContext(data.context)         self.LoadValue(data.ref)      def LoadAddressContext(self, operand):         # Value becomes context.         data = self.load(operand)         self.LoadContext(self.value)         self.LoadValue(data.ref)      def LoadAddressContextCond(self, operand):         data = self.load(operand)         data = self._LoadAddressContextCond(data.context, data.ref, self.value)         self.LoadContext(data.context)         self.LoadValue(data.ref)      def StoreAddress(self, operand):         # Preserve context.         self.save(operand, DataValue(self.source_context, self.source_value))      def StoreAddressContext(self, operand):         # Overwrite context if null.         self._StoreAddressContext(operand, self.context, self.value, self.source_context, self.source_value)      def MakeInstance(self, size):         # NOTE: Referencing the instance template.         addr = self._MakeObject(size, self.value - Library.instance_template_size)         # Introduce object as context for the new object.         self.LoadContext(addr)         self.LoadValue(addr)      def MakeFragment(self, size):         # Reserve twice the amount of space.         addr = self._MakeFragment(size, size * 2)         # NOTE: Context is not relevant for fragments.         self.LoadContext(None)         self.LoadValue(addr)      def LoadAttr(self, pos):         # Retrieved context should already be appropriate for the instance.         # NOTE: Adding 1 to skip any header.         data = self.load(self.value + pos + 1)         self.LoadContext(data.context)         self.LoadValue(data.ref)      def StoreAttr(self, pos):         # Target should already be an instance.         # NOTE: Adding 1 to skip any header.         self.save(self.value + pos + 1, DataValue(self.source_context, self.source_value))      def LoadAttrIndex(self, index):         data = self.load(self.value)         element = self.objlist[data.classcode + index]          if element is not None:             attr_index, static_attr, offset = element             if attr_index == index:                 if static_attr:                     data = self.load(offset) # offset is address of class/module attribute                 else:                     data = self.load(self.value + offset)                 self.LoadContext(data.context)                 self.LoadValue(data.ref)                 return          self.exception = self._MakeObject(Library.instance_size, self.attr_error_instance)         return self.RaiseException()      # LoadAttrIndexContext not defined.      def LoadAttrIndexContextCond(self, index):         data = self.load(self.value)         element = self.objlist[data.classcode + index]          if element is not None:             attr_index, static_attr, offset = element             if attr_index == index:                 if static_attr:                     loaded_data = self.load(offset) # offset is address of class/module attribute                     # Absent attrcode == class/module.                     if data.attrcode is not None:                         loaded_data = self._LoadAddressContextCond(loaded_data.context, loaded_data.ref, self.value)                 else:                     loaded_data = self.load(self.value + offset)                 self.LoadContext(loaded_data.context)                 self.LoadValue(loaded_data.ref)                 return          self.exception = self._MakeObject(Library.instance_size, self.attr_error_instance)         return self.RaiseException()      def StoreAttrIndex(self, index):         data = self.load(self.value)         element = self.objlist[data.classcode + index]          if element is not None:             attr_index, static_attr, offset = element             if attr_index == index:                 if static_attr:                     self._StoreAddressContext(offset, self.context, self.value, self.source_context, self.source_value)                     return                 else:                     self.save(self.value + offset, DataValue(self.source_context, self.source_value))                     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, size):         self.invocation_sp_stack.append(len(self.frame_stack))         self.frame_stack.extend([None] * size)      def DropFrame(self, operand=None):         self.local_sp_stack.pop()         frame = self.invocation_sp_stack.pop()         del self.frame_stack[frame:] # reset stack before call      def StoreFrame(self, pos):         frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame         self.frame_stack[frame + pos] = DataValue(self.context, self.value)      def StoreFrameIndex(self, index):         frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame         data = self.load(self.value)         element = self.paramlist[data.funccode + index]          if element is not None:             # NOTE: Need to ensure correct positioning where a context has been generated.             param_index, offset = element             if param_index == index:                 self.frame_stack[frame + offset] = DataValue(self.source_context, self.source_value)                 return          self.exception = self._MakeObject(Library.instance_size, self.type_error_instance)         return self.RaiseException()      def LoadCallable(self, operand=None):         data = self.load(self.value)         self.callable = data.codeaddr      def StoreCallable(self, operand=None):         # NOTE: Should improve the representation and permit direct saving.         data = self.load(self.value)         self.save(self.value, data.with_callable(self.callable))      def LoadContextIntoValue(self, operand=None):         # NOTE: Omission of the context of the context would make things like         # NOTE: self() inside methods impossible.         self.LoadValue(self.context)      def CheckContext(self, operand=None):         self.status = self.value is not ReplaceableContext      def CheckClass(self, operand=None):         if self.value in (ReplaceableContext, PlaceholderContext):             self.status = 0             return          data = self.load(self.value)          # 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, operand):         (nargs, ndefaults) = 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)" % (operand, nargs - ndefaults, nlocals, nargs)             self.exception = self._MakeObject(Library.instance_size, self.type_error_instance)             return self.RaiseException()      def CheckExtra(self, nargs):          # 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, operand):         (nargs, ndefaults) = 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(self.value + default + 1) # skip header             default += 1             pos += 1      def CopyExtra(self, start):          # 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.LoadContext(ref)         self.LoadValue(ref)      def CheckInstance(self, operand=None):         # For the 'self' parameter in an invoked function, the proposed context         # ('self') is checked against the target's context.         self.status = self._CheckInstance(self.value, self.source_value)      def JumpInFrame(self, operand=None):         codeaddr = self.callable         return self.jump(codeaddr, self.pc + 1) # return to the instruction after this one      def JumpWithFrame(self, operand=None):         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, addr):         self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame         return self.jump(addr, self.pc + 1) # return to the instruction after this one      def ExtendFrame(self, size):         self.frame_stack.extend([None] * size)      def AdjustFrame(self, size):         self.invocation_sp_stack[-1] += size      def Return(self, operand=None):         return self.pull_pc()      def LoadResultIntoValue(self, operand=None):         self.LoadContext(self.result_context)         self.LoadValue(self.result_value)      def LoadValueIntoResult(self, operand=None):         self.result_context = self.context         self.result_value = self.value      def Jump(self, addr):         return addr      def JumpIfTrue(self, addr):         if self.status:             return addr      def JumpIfFalse(self, addr):         if not self.status:             return addr      def LoadException(self, operand=None):         self.LoadContext(self.exception)         self.LoadValue(self.exception)      def StoreException(self, operand=None):         self.exception = self.value      def ClearException(self, operand=None):         self.exception = None      def RaiseException(self, operand=None):         # 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, addr):         self.handler_stack.append(addr)         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):         # 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, operand=None):         self.status = self.exception is not None and self._CheckInstance(self.exception, self.value)      def TestIdentity(self, operand=None):         self.status = self.value == self.source_value      def TestIdentityAddress(self, addr):         self.status = self.value == addr      # LoadBoolean is implemented in the generated code.     # StoreBoolean is implemented by testing against the True value.      def InvertBoolean(self, operand=None):         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 _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, value, inst_value):         # 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_value, context):             # Replace the context with the instance.             return DataValue(inst_value, value)         else:             return DataValue(context, value)      def _StoreAddressContext(self, location, context, value, source_context, source_value):         if source_context is ReplaceableContext:             context = value         else:             context = source_context         self.save(location, DataValue(context, source_value))  # 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