1 #!/usr/bin/env python 2 3 """ 4 A really simple virtual processor employing a simple set of instructions which 5 ignore low-level operations and merely concentrate on variable access, structure 6 access, structure allocation and function invocations. 7 8 Copyright (C) 2007, 2008, 2009 Paul Boddie <paul@boddie.org.uk> 9 10 This program is free software; you can redistribute it and/or modify it under 11 the terms of the GNU General Public License as published by the Free Software 12 Foundation; either version 3 of the License, or (at your option) any later 13 version. 14 15 This program is distributed in the hope that it will be useful, but WITHOUT 16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 17 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 18 details. 19 20 You should have received a copy of the GNU General Public License along with 21 this program. If not, see <http://www.gnu.org/licenses/>. 22 23 -------- 24 25 The execution model of the virtual processor involves the following things: 26 27 * Memory contains constants, global variable 28 references and program code 29 30 * PC (program counter) stack contains the return address associated 31 with each function invocation 32 33 * Frame stack contains invocation frames in use and in 34 preparation plus temporary storage 35 36 * Local frame pointer stack refers to the frames in the frame stack 37 38 * Invocation frame pointer stack 39 40 * Exception handler stack 41 42 * Exception handler locals stack refers to the state of the local frame 43 pointer stack 44 45 * Exception handler PC stack refers to the state of the PC stack 46 47 * Registers: current value, 48 boolean status value, 49 source value, 50 current result, 51 current exception, 52 current callable 53 """ 54 55 from micropython.program import DataValue, ReplaceableContext, PlaceholderContext, FragmentObject 56 from rsvplib import Library 57 58 class IllegalInstruction(Exception): 59 pass 60 61 class IllegalAddress(Exception): 62 def __init__(self, address): 63 self.address = address 64 def __repr__(self): 65 return "IllegalAddress(%r)" % self.address 66 def __str__(self): 67 return repr(self) 68 69 class EmptyPCStack(Exception): 70 pass 71 72 class EmptyFrameStack(Exception): 73 pass 74 75 class BreakpointReached(Exception): 76 pass 77 78 class RSVPMachine: 79 80 "A really simple virtual processor." 81 82 def __init__(self, memory, objlist, paramlist, pc=None, debug=0, abort_upon_exception=0): 83 84 """ 85 Initialise the processor with a 'memory' (a list of values containing 86 instructions and data), the object and parameter lists 'objlist' and 87 'paramlist', and the optional program counter 'pc'. 88 """ 89 90 self.memory = memory 91 self._objlist = objlist 92 self._paramlist = paramlist 93 self.objlist = objlist.as_raw() 94 self.paramlist = paramlist.as_raw() 95 self.library = None 96 97 self.pc = pc or 0 98 self.debug = debug 99 self.abort_upon_exception = abort_upon_exception 100 self.counter = 0 101 102 # Stacks. 103 104 self.pc_stack = [] 105 self.frame_stack = [] 106 self.local_sp_stack = [0] 107 self.invocation_sp_stack = [] 108 self.handler_stack = [len(self.memory) - 1] # final handler is the end of the code 109 self.handler_local_sp_stack = [] 110 self.handler_pc_stack = [] 111 112 # Registers. 113 114 self.instruction = None 115 self.operand = None 116 self.value = None 117 self.status = None 118 self.source = None 119 self.callable = None 120 self.result = None 121 self.exception = None 122 123 # Constants. 124 125 cls = self._get_class("__builtins__", "AttributeError") 126 self.attr_error = cls.location 127 self.attr_error_instance = cls.instance_template_location 128 cls = self._get_class("__builtins__", "TypeError") 129 self.type_error = cls.location 130 self.type_error_instance = cls.instance_template_location 131 cls = self._get_class("__builtins__", "tuple") 132 self.tuple_class = cls.location 133 self.tuple_instance = cls.instance_template_location 134 135 # Debugging attributes. 136 137 self.breakpoints = set() 138 139 def _get_class(self, module, name): 140 return self._objlist.access(module, name).get_value() 141 142 # Debugging methods. 143 144 def dump(self): 145 print "PC", self.pc, "->", self.load(self.pc) 146 print "PC stack", self.pc_stack 147 print "Frame stack", self.frame_stack 148 print "Local stack pointers", self.local_sp_stack 149 print "Invocation stack pointers", self.invocation_sp_stack 150 print "Handler stack", self.handler_stack 151 print "Handler frame stack", self.handler_local_sp_stack 152 print "Handler PC stack", self.handler_pc_stack 153 print 154 print "Instruction", self.instruction 155 print "Operand", self.operand 156 print "Value", self.value 157 print "Status", self.status 158 print "Source", self.source 159 print "Callable", self.callable 160 print "Result", self.result 161 print "Exception", self.exception 162 163 def show(self): 164 self.show_memory(self.memory, 0) 165 166 def show_pc(self, run_in=10): 167 start = max(0, self.pc - run_in) 168 end = self.pc + run_in 169 memory = self.memory[start:end] 170 self.show_memory(memory, start) 171 172 def show_memory(self, memory, start): 173 for i, x in enumerate(memory): 174 location = start + i 175 if location == self.pc: 176 print "->", 177 else: 178 print " ", 179 print "%5d %r" % (location, x) 180 181 def step(self, dump=0): 182 self.execute() 183 self.show_pc() 184 if dump: 185 self.dump() 186 187 def set_break(self, location): 188 self.breakpoints.add(location) 189 190 # Internal operations. 191 192 def load(self, address): 193 194 "Return the value at the given 'address'." 195 196 try: 197 return self.memory[address] 198 except IndexError: 199 raise IllegalAddress(address) 200 except TypeError: 201 raise IllegalAddress(address) 202 203 def save(self, address, value): 204 205 "Save to the given 'address' the specified 'value'." 206 207 try: 208 self.memory[address] = value 209 except IndexError: 210 raise IllegalAddress(address) 211 except TypeError: 212 raise IllegalAddress(address) 213 214 def new(self, size): 215 216 """ 217 Allocate space of the given 'size', returning the address of the space. 218 """ 219 220 addr = len(self.memory) 221 for i in range(0, size): 222 self.memory.append(None) 223 return addr 224 225 def push_pc(self, data): 226 227 "Push 'data' onto the PC stack." 228 229 self.pc_stack.append(data) 230 231 def pull_pc(self): 232 233 "Pull a value from the PC stack and return it." 234 235 try: 236 return self.pc_stack.pop() 237 except IndexError: 238 raise EmptyPCStack 239 240 def run(self): 241 242 "Execute code in the memory, starting from the current PC address." 243 244 breakpoint = 0 245 246 try: 247 while 1: 248 self.execute() 249 except EmptyPCStack: 250 pass 251 except BreakpointReached: 252 breakpoint = 1 253 254 print "Execution terminated", 255 if self.exception is not None: 256 ref = self.exception 257 addr = self.load(ref + 1) 258 print "with exception:", self.load(ref) 259 print "At address %d: %r" % (addr, self.load(addr)) 260 elif breakpoint: 261 print "with breakpoint." 262 print "At address", self.pc 263 else: 264 print "successfully." 265 266 def test(self, module): 267 268 """ 269 Test the code in the memory by running the code and investigating the 270 contents of variables. Use 'module' to identify result variables. 271 """ 272 273 self.run() 274 success = 1 275 276 if self.exception is None: 277 for name in module.keys(): 278 if name.startswith("result"): 279 label, expected = name.split("_") 280 attr = module[name] 281 282 # NOTE: Assumptions about headers and content made. 283 284 attr_location = module.location + 1 + attr.position 285 value = self.load(attr_location) 286 287 if value is not None: 288 content = self.load(value.ref + 1) 289 print label, expected, content 290 success = success and (int(expected) == content) 291 else: 292 print label, expected, "missing" 293 success = 0 294 295 return success 296 else: 297 return 0 298 299 def execute(self): 300 301 "Execute code in the memory at the current PC address." 302 303 if self.pc in self.breakpoints: 304 self.breakpoints.remove(self.pc) 305 raise BreakpointReached 306 307 self.instruction = self.load(self.pc) 308 309 # Process any inputs of the instruction. 310 311 self.process_inputs() 312 313 # Perform the instruction itself. 314 315 next_pc = self.perform(self.instruction) 316 317 # Update the program counter. 318 319 if next_pc is None: 320 self.pc += 1 321 else: 322 self.pc = next_pc 323 324 def get_method(self, instruction): 325 326 "Return the handler method for the given 'instruction'." 327 328 instruction_name = instruction.__class__.__name__ 329 if self.debug: 330 print "%8d %s" % (self.pc, instruction_name) 331 method = getattr(self, instruction_name, None) 332 if method is None: 333 raise IllegalInstruction, (self.pc, instruction_name) 334 return method 335 336 def perform(self, instruction): 337 338 "Perform the 'instruction', returning the next PC value or None." 339 340 self.counter += 1 341 self.operand = instruction.get_operand() 342 method = self.get_method(instruction) 343 return method() 344 345 def process_inputs(self): 346 347 """ 348 Process any inputs of the current instruction. This permits any directly 349 connected sub-instructions to produce the effects that separate 350 instructions would otherwise have. 351 """ 352 353 value = self.value 354 if self.instruction.source is not None: 355 self.perform(self.instruction.source) 356 self.source = self.value 357 self.value = value 358 if self.instruction.input is not None: 359 self.perform(self.instruction.input) 360 361 def jump(self, addr, next): 362 363 """ 364 Jump to the subroutine at (or identified by) 'addr'. If 'addr' 365 identifies a library function then invoke the library function and set 366 PC to 'next' afterwards; otherwise, set PC to 'addr'. 367 """ 368 369 # Trap library functions introduced through the use of strings instead 370 # of proper locations. 371 372 if isinstance(addr, str): 373 handler = self.library and self.library.native_functions[addr](self.library) 374 if handler is None: 375 return next 376 else: 377 return handler 378 else: 379 self.push_pc(self.pc + 1) 380 return addr 381 382 # Instructions. 383 384 def LoadConst(self): 385 self.value = DataValue(self.operand, self.operand) 386 387 def LoadClass(self): 388 self.value = DataValue(PlaceholderContext, self.operand) 389 390 def LoadFunction(self): 391 self.value = DataValue(ReplaceableContext, self.operand) 392 393 def LoadName(self): 394 frame = self.local_sp_stack[-1] 395 self.value = self.frame_stack[frame + self.operand] 396 397 def StoreName(self): 398 frame = self.local_sp_stack[-1] 399 self.frame_stack[frame + self.operand] = self.source # uses the source value 400 401 LoadTemp = LoadName 402 403 def StoreTemp(self): 404 frame = self.local_sp_stack[-1] 405 self.frame_stack[frame + self.operand] = self.value 406 407 def LoadAddress(self): 408 # Preserve context (potentially null). 409 self.value = self.load(self.operand) 410 411 def LoadAddressContext(self): 412 value = self.load(self.operand) 413 inst_value = self.value 414 self.value = DataValue(inst_value.ref, value.ref) 415 416 def LoadAddressContextCond(self): 417 value = self.load(self.operand) 418 inst_value = self.value 419 self.value = self._LoadAddressContextCond(value.context, value.ref, inst_value.ref) 420 421 def StoreAddress(self): 422 # Preserve context. 423 self.save(self.operand, self.source) 424 425 def StoreAddressContext(self): 426 # Overwrite context if null. 427 context_value = self.value 428 source_value = self.source 429 if source_value.context is ReplaceableContext: 430 context = context_value.ref 431 else: 432 context = source_value.context 433 self.save(self.operand, DataValue(context, source_value.ref)) 434 435 def MakeInstance(self): 436 size = self.operand 437 value = self.value 438 # NOTE: Referencing the instance template. 439 addr = self._MakeObject(size, value.ref - 1) 440 # Introduce object as context for the new object. 441 self.value = DataValue(addr, addr) 442 443 def MakeFragment(self): 444 size = self.operand 445 addr = self._MakeFragment(size) 446 # NOTE: Context is not relevant for fragments. 447 self.value = DataValue(None, addr) 448 449 def LoadAttr(self): 450 value = self.value 451 # Retrieved context should already be appropriate for the instance. 452 # NOTE: Adding 1 to skip any header. 453 self.value = self.load(value.ref + self.operand + 1) 454 455 def StoreAttr(self): 456 value = self.value 457 # Target should already be an instance. 458 # NOTE: Adding 1 to skip any header. 459 self.save(value.ref + self.operand + 1, self.source) 460 461 def LoadAttrIndex(self): 462 value = self.value 463 data = self.load(value.ref) 464 element = self.objlist[data.classcode + self.operand] 465 466 if element is not None: 467 attr_index, static_attr, offset = element 468 if attr_index == self.operand: 469 if static_attr: 470 self.value = self.load(offset) # offset is address of class/module attribute 471 else: 472 self.value = self.load(value.ref + offset) 473 return 474 475 self.exception = self._MakeObject(2, self.attr_error_instance) 476 return self.RaiseException() 477 478 # LoadAttrIndexContext not defined. 479 480 def LoadAttrIndexContextCond(self): 481 inst_value = self.value 482 data = self.load(inst_value.ref) 483 element = self.objlist[data.classcode + self.operand] 484 485 if element is not None: 486 attr_index, static_attr, offset = element 487 if attr_index == self.operand: 488 if static_attr: 489 loaded_value = self.load(offset) # offset is address of class/module attribute 490 if data.attrcode is None: # absent attrcode == class/module 491 self.value = loaded_value 492 else: 493 self.value = self._LoadAddressContextCond(loaded_value.context, loaded_value.ref, inst_value.ref) 494 else: 495 self.value = self.load(inst_value.ref + offset) 496 return 497 498 self.exception = self._MakeObject(2, self.attr_error_instance) 499 return self.RaiseException() 500 501 def StoreAttrIndex(self): 502 value = self.value 503 data = self.load(value.ref) 504 element = self.objlist[data.classcode + self.operand] 505 506 if element is not None: 507 attr_index, static_attr, offset = element 508 if attr_index == self.operand: 509 if static_attr: 510 self.exception = self._MakeObject(2, self.type_error_instance) 511 return self.RaiseException() 512 else: 513 self.save(value.ref + offset, self.source) 514 return 515 516 self.exception = self._MakeObject(2, self.attr_error_instance) 517 return self.RaiseException() 518 519 # NOTE: LoadAttrIndexContext is a possibility if a particular attribute can always be overridden. 520 521 def MakeFrame(self): 522 self.invocation_sp_stack.append(len(self.frame_stack)) 523 self.frame_stack.extend([None] * self.operand) 524 525 def DropFrame(self): 526 self.local_sp_stack.pop() 527 frame = self.invocation_sp_stack.pop() 528 del self.frame_stack[frame:] # reset stack before call 529 530 def StoreFrame(self): 531 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 532 self.frame_stack[frame + self.operand] = self.value 533 534 def StoreFrameIndex(self): 535 value = self.value 536 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 537 data = self.load(value.ref) 538 element = self.paramlist[data.funccode + self.operand] 539 540 if element is not None: 541 # NOTE: Need to ensure correct positioning where a context has been generated. 542 param_index, offset = element 543 if param_index == self.operand: 544 self.frame_stack[frame + offset] = self.source 545 return 546 547 self.exception = self._MakeObject(2, self.type_error_instance) 548 return self.RaiseException() 549 550 def LoadCallable(self): 551 value = self.value 552 data = self.load(value.ref) 553 self.callable = data.codeaddr 554 555 def StoreCallable(self): 556 value = self.value 557 # NOTE: Should improve the representation and permit direct saving. 558 data = self.load(value.ref) 559 self.save(value.ref, data.with_callable(self.callable)) 560 561 def LoadContext(self): 562 value = self.value 563 # NOTE: Omission of the context of the context would make things like 564 # NOTE: self() inside methods impossible. 565 self.value = DataValue(value.context, value.context) 566 567 def CheckContext(self): 568 self.status = self.value.ref is not ReplaceableContext 569 570 def CheckClass(self): 571 value = self.value 572 if value.ref in (ReplaceableContext, PlaceholderContext): 573 self.status = 0 574 return 575 576 data = self.load(value.ref) 577 578 # Classes are not themselves usable as the self argument. 579 # NOTE: This may change at some point. 580 # However, where classes appear as the context, instance 581 # compatibility is required in the first argument. 582 583 self.status = data.attrcode is None # absent attrcode == class 584 585 def CheckFrame(self): 586 (nargs, ndefaults) = self.operand 587 588 # The frame is actually installed as the locals. 589 # Retrieve the context from the first local. 590 591 frame = self.local_sp_stack[-1] 592 nlocals = len(self.frame_stack[frame:]) 593 594 if not ((nargs - ndefaults) <= nlocals): 595 raise Exception, "CheckFrame %r (%r <= %r <= %r)" % (self.operand, nargs - ndefaults, nlocals, nargs) 596 self.exception = self._MakeObject(2, self.type_error_instance) 597 return self.RaiseException() 598 599 def CheckExtra(self): 600 nargs = self.operand 601 602 # The frame is actually installed as the locals. 603 # Retrieve the context from the first local. 604 605 frame = self.local_sp_stack[-1] 606 nlocals = len(self.frame_stack[frame:]) 607 608 # Provide the extra star parameter if necessary. 609 610 if nlocals == nargs: 611 self.frame_stack.extend([None]) # ExtendFrame(1) 612 613 def FillDefaults(self): 614 value = self.value 615 (nargs, ndefaults) = self.operand 616 617 # The frame is actually installed as the locals. 618 619 frame = self.local_sp_stack[-1] 620 nlocals = len(self.frame_stack[frame:]) 621 622 # Support population of defaults. 623 # This involves copying the "attributes" of a function into the frame. 624 625 default = nlocals - (nargs - ndefaults) 626 self.frame_stack.extend([None] * (nargs - nlocals)) 627 pos = nlocals 628 629 while pos < nargs: 630 self.frame_stack[frame + pos] = self.load(value.ref + default + 1) # skip header 631 default += 1 632 pos += 1 633 634 def CopyExtra(self): 635 start = self.operand 636 637 # The frame is the source of the extra arguments. 638 639 frame = self.local_sp_stack[-1] 640 nlocals = len(self.frame_stack[frame:]) 641 642 # Make a tuple to hold the arguments. 643 644 ref = self._MakeObject(nlocals - start + 1, self.tuple_instance) 645 646 extra = 0 647 pos = start 648 649 while pos < nlocals: 650 self.save(ref + extra + 1, self.frame_stack[frame + pos]) # skip header when storing 651 extra += 1 652 pos += 1 653 654 self.value = DataValue(ref, ref) 655 656 def CheckInstance(self): 657 value = self.value 658 target_value = self.source 659 660 # For the 'self' parameter in an invoked function, the proposed context 661 # ('self') is checked against the target's context. 662 663 self.status = self._CheckInstance(value.ref, target_value.ref) 664 665 def JumpInFrame(self): 666 codeaddr = self.callable 667 return self.jump(codeaddr, self.pc + 1) # return to the instruction after this one 668 669 def JumpWithFrame(self): 670 codeaddr = self.callable 671 self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame 672 return self.jump(codeaddr, self.pc + 1) # return to the instruction after this one 673 674 def JumpWithFrameDirect(self): 675 operand = self.operand 676 self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame 677 return self.jump(operand, self.pc + 1) # return to the instruction after this one 678 679 def ExtendFrame(self): 680 self.frame_stack.extend([None] * self.operand) 681 682 def AdjustFrame(self): 683 self.invocation_sp_stack[-1] += self.operand 684 685 def Return(self): 686 return self.pull_pc() 687 688 def LoadResult(self): 689 self.value = self.result 690 691 def StoreResult(self): 692 self.result = self.value 693 694 def Jump(self): 695 return self.operand 696 697 def JumpIfTrue(self): 698 if self.status: 699 return self.operand 700 701 def JumpIfFalse(self): 702 if not self.status: 703 return self.operand 704 705 def LoadException(self): 706 self.value = DataValue(self.exception, self.exception) 707 708 def StoreException(self): 709 self.exception = self.value.ref 710 711 def ClearException(self): 712 self.exception = None 713 714 def RaiseException(self): 715 # NOTE: Adding the program counter as the first attribute. 716 self.save(self.exception + 1, self.pc) 717 # Jumping to the current handler. 718 if self.abort_upon_exception: 719 raise Exception 720 return self.handler_stack[-1] 721 722 def PushHandler(self): 723 self.handler_stack.append(self.operand) 724 self.handler_local_sp_stack.append(len(self.local_sp_stack)) 725 self.handler_pc_stack.append(len(self.pc_stack)) 726 727 def PopHandler(self): 728 # Reduce the local frame pointer stack to refer to the handler's frame. 729 del self.local_sp_stack[self.handler_local_sp_stack.pop():] 730 # Reduce the PC stack to discard all superfluous return addresses. 731 self.pc_stack = self.pc_stack[:self.handler_pc_stack.pop()] 732 self.handler_stack.pop() 733 734 def CheckException(self): 735 self.status = self.exception is not None and self._CheckInstance(self.exception, self.value.ref) 736 737 def TestIdentity(self): 738 self.status = self.value.ref == self.source.ref 739 740 def TestIdentityAddress(self): 741 self.status = self.value.ref == self.operand 742 743 # LoadBoolean is implemented in the generated code. 744 # StoreBoolean is implemented by testing against the True value. 745 746 def InvertBoolean(self): 747 self.status = not self.status 748 749 # Common implementation details. 750 751 def _CheckInstance(self, ref, cls): 752 data = self.load(ref) 753 target_data = self.load(cls) 754 755 # Insist on instance vs. class. 756 757 if data.attrcode is None: # absent attrcode == class/module 758 return 0 759 760 if target_data.attrcode is not None: # present attrcode == instance 761 return 0 762 763 # Find the table entry for the descendant. 764 765 element = self.objlist[target_data.classcode + data.attrcode] 766 767 if element is not None: 768 attr_index, static_attr, offset = element 769 return attr_index == data.attrcode 770 else: 771 return 0 772 773 def _MakeObject(self, size, ref): 774 # Load the template. 775 data = self.load(ref) 776 addr = self.new(size) 777 # Save the header, overriding the size. 778 self.save(addr, data.with_size(size)) 779 return addr 780 781 def _MakeFragment(self, size): 782 # Reserve twice the amount of space. 783 addr = self.new(size * 2) 784 # Save the header, overriding the size. 785 self.save(addr, FragmentObject(size, size * 2)) 786 return addr 787 788 def _LoadAddressContextCond(self, context, ref, inst_ref): 789 # Check the instance context against the target's context. 790 # This provides the context overriding for methods. 791 if context is ReplaceableContext or context is not PlaceholderContext and self._CheckInstance(inst_ref, context): 792 # Replace the context with the instance. 793 return DataValue(inst_ref, ref) 794 else: 795 return DataValue(context, ref) 796 797 # Convenience functions. 798 799 def machine(program, with_builtins=0, debug=0, abort_upon_exception=0): 800 print "Making the image..." 801 code = program.get_image(with_builtins) 802 print "Getting raw structures..." 803 ot = program.get_object_table() 804 pt = program.get_parameter_table() 805 objlist = ot.as_list() 806 paramlist = pt.as_list() 807 print "Getting raw image..." 808 rc = program.get_raw_image() 809 print "Initialising the machine..." 810 importer = program.get_importer() 811 true_constant = importer.get_constant(True).location 812 false_constant = importer.get_constant(False).location 813 rm = RSVPMachine(rc, objlist, paramlist, debug=debug, abort_upon_exception=abort_upon_exception) 814 library = Library(rm, true_constant, false_constant) 815 rm.library = library 816 rm.pc = program.code_location 817 print "Returning program occupying %d locations." % len(rm.memory) 818 return rm 819 820 # vim: tabstop=4 expandtab shiftwidth=4