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 DataObject # for creating "nice" new objects 56 57 class IllegalInstruction(Exception): 58 pass 59 60 class IllegalAddress(Exception): 61 def __init__(self, address): 62 self.address = address 63 def __repr__(self): 64 return "IllegalAddress(%r)" % self.address 65 def __str__(self): 66 return repr(self) 67 68 class EmptyPCStack(Exception): 69 pass 70 71 class EmptyFrameStack(Exception): 72 pass 73 74 class BreakpointReached(Exception): 75 pass 76 77 class RSVPMachine: 78 79 "A really simple virtual processor." 80 81 def __init__(self, memory, objlist, paramlist, true_constant, false_constant, pc=None, debug=0): 82 83 """ 84 Initialise the processor with a 'memory' (a list of values containing 85 instructions and data), the object and parameter lists 'objlist' and 86 'paramlist', the addresses 'true_constant' and 'false_constant', and the 87 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.true_constant = true_constant 96 self.false_constant = false_constant 97 98 self.pc = pc or 0 99 self.debug = debug 100 101 # Stacks. 102 103 self.pc_stack = [] 104 self.frame_stack = [] 105 self.local_sp_stack = [0] 106 self.invocation_sp_stack = [] 107 self.handler_stack = [len(self.memory) - 1] # final handler is the end of the code 108 self.handler_local_sp_stack = [] 109 self.handler_pc_stack = [] 110 111 # Registers. 112 113 self.instruction = None 114 self.operand = None 115 self.value = None 116 self.status = None 117 self.source = None 118 self.callable = None 119 self.result = None 120 self.exception = None 121 122 # Constants. 123 124 self.attr_error = objlist.access("__builtins__", "AttributeError").get_value().location 125 self.type_error = objlist.access("__builtins__", "TypeError").get_value().location 126 self.index_error = objlist.access("__builtins__", "IndexError").get_value().location 127 128 # Native class constants. 129 130 cls = objlist.access("__builtins__", "int") 131 self.int_class_location = cls and cls.get_value() and cls.get_value().location 132 self.int_instance_location = cls and cls.get_value() and cls.get_value().instance_template_location 133 cls = objlist.access("__builtins__", "list") 134 self.list_instance_location = cls and cls.get_value() and cls.get_value().instance_template_location 135 136 # Debugging attributes. 137 138 self.breakpoints = set() 139 140 # Debugging methods. 141 142 def dump(self): 143 print "PC", self.pc, "->", self.load(self.pc) 144 print "PC stack", self.pc_stack 145 print "Frame stack", self.frame_stack 146 print "Local stack pointers", self.local_sp_stack 147 print "Invocation stack pointers", self.invocation_sp_stack 148 print "Handler stack", self.handler_stack 149 print "Handler frame stack", self.handler_local_sp_stack 150 print "Handler PC stack", self.handler_pc_stack 151 print 152 print "Instruction", self.instruction 153 print "Operand", self.operand 154 print "Value", self.value 155 print "Status", self.status 156 print "Source", self.source 157 print "Callable", self.callable 158 print "Result", self.result 159 print "Exception", self.exception 160 161 def show(self): 162 self.show_memory(self.memory, 0) 163 164 def show_pc(self, run_in=10): 165 start = max(0, self.pc - run_in) 166 end = self.pc + run_in 167 memory = self.memory[start:end] 168 self.show_memory(memory, start) 169 170 def show_memory(self, memory, start): 171 for i, x in enumerate(memory): 172 location = start + i 173 if location == self.pc: 174 print "->", 175 else: 176 print " ", 177 print "%5d %r" % (location, x) 178 179 def step(self, dump=0): 180 self.execute() 181 self.show_pc() 182 if dump: 183 self.dump() 184 185 def set_break(self, location): 186 self.breakpoints.add(location) 187 188 # Internal operations. 189 190 def load(self, address): 191 192 "Return the value at the given 'address'." 193 194 try: 195 return self.memory[address] 196 except IndexError: 197 raise IllegalAddress(address) 198 except TypeError: 199 raise IllegalAddress(address) 200 201 def save(self, address, value): 202 203 "Save to the given 'address' the specified 'value'." 204 205 try: 206 self.memory[address] = value 207 except IndexError: 208 raise IllegalAddress(address) 209 except TypeError: 210 raise IllegalAddress(address) 211 212 def new(self, size): 213 214 """ 215 Allocate space of the given 'size', returning the address of the space. 216 """ 217 218 addr = len(self.memory) 219 for i in range(0, size): 220 self.memory.append(None) 221 return addr 222 223 def push_pc(self, data): 224 225 "Push 'data' onto the PC stack." 226 227 self.pc_stack.append(data) 228 229 def pull_pc(self): 230 231 "Pull a value from the PC stack and return it." 232 233 try: 234 return self.pc_stack.pop() 235 except IndexError: 236 raise EmptyPCStack 237 238 def run(self): 239 240 "Execute code in the memory, starting from the current PC address." 241 242 try: 243 while 1: 244 self.execute() 245 except EmptyPCStack: 246 pass 247 248 def execute(self): 249 250 "Execute code in the memory at the current PC address." 251 252 if self.pc in self.breakpoints: 253 self.breakpoints.remove(self.pc) 254 raise BreakpointReached 255 256 self.instruction = self.load(self.pc) 257 258 # Process any inputs of the instruction. 259 260 self.process_inputs() 261 262 # Perform the instruction itself. 263 264 next_pc = self.perform(self.instruction) 265 266 # Update the program counter. 267 268 if next_pc is None: 269 self.pc += 1 270 else: 271 self.pc = next_pc 272 273 def get_method(self, instruction): 274 275 "Return the handler method for the given 'instruction'." 276 277 instruction_name = instruction.__class__.__name__ 278 if self.debug: 279 print "%8d %s" % (self.pc, instruction_name) 280 method = getattr(self, instruction_name, None) 281 if method is None: 282 raise IllegalInstruction, (self.pc, instruction_name) 283 return method 284 285 def perform(self, instruction): 286 287 "Perform the 'instruction', returning the next PC value or None." 288 289 self.operand = instruction.get_operand() 290 method = self.get_method(instruction) 291 return method() 292 293 def process_inputs(self): 294 295 """ 296 Process any inputs of the current instruction. This permits any directly 297 connected sub-instructions to produce the effects that separate 298 instructions would otherwise have. 299 """ 300 301 value = self.value 302 if self.instruction.source is not None: 303 self.perform(self.instruction.source) 304 self.source = self.value 305 self.value = value 306 if self.instruction.input is not None: 307 self.perform(self.instruction.input) 308 309 def jump(self, addr, next): 310 311 """ 312 Jump to the subroutine at (or identified by) 'addr'. If 'addr' 313 identifies a library function then invoke the library function and set 314 PC to 'next' afterwards; otherwise, set PC to 'addr'. 315 """ 316 317 # Trap library functions introduced through the use of strings instead 318 # of proper locations. 319 320 if isinstance(addr, str): 321 handler = self.native_functions[addr](self) 322 if handler is None: 323 return next 324 else: 325 return handler 326 else: 327 self.push_pc(self.pc + 1) 328 return addr 329 330 # Instructions. 331 332 def LoadConst(self): 333 self.value = None, self.operand # context of constant is not interesting 334 335 def LoadName(self): 336 frame = self.local_sp_stack[-1] 337 self.value = self.frame_stack[frame + self.operand] 338 339 def StoreName(self): 340 frame = self.local_sp_stack[-1] 341 self.frame_stack[frame + self.operand] = self.source 342 343 LoadTemp = LoadName 344 345 def StoreTemp(self): 346 frame = self.local_sp_stack[-1] 347 self.frame_stack[frame + self.operand] = self.value 348 349 def LoadAddress(self): 350 # Preserve context (potentially null). 351 self.value = self.load(self.operand) 352 353 def LoadAddressContext(self): 354 context, ref = self.load(self.operand) 355 inst_context, inst_ref = self.value 356 self.value = inst_ref, ref 357 358 def LoadAddressContextCond(self): 359 context, ref = self.load(self.operand) 360 inst_context, inst_ref = self.value 361 self.value = self._LoadAddressContextCond(context, ref, inst_context, inst_ref) 362 363 def StoreAddress(self): 364 # Preserve context. 365 self.save(self.operand, self.source) 366 367 def MakeObject(self): 368 size = self.operand 369 context, ref = self.value 370 # NOTE: Referencing the instance template. 371 addr = self._MakeObject(size, ref - 1) 372 # Introduce object as context for the new object. 373 self.value = addr, addr 374 375 def LoadAttr(self): 376 context, ref = self.value 377 # Retrieved context should already be appropriate for the instance. 378 # NOTE: Adding 1 to skip any header. 379 self.value = self.load(ref + self.operand + 1) 380 381 def StoreAttr(self): 382 context, ref = self.value 383 # Target should already be an instance. 384 # NOTE: Adding 1 to skip any header. 385 self.save(ref + self.operand + 1, self.source) 386 387 def LoadAttrIndex(self): 388 context, ref = self.value 389 data = self.load(ref) 390 element = self.objlist[data.classcode + self.operand] 391 attr_index, class_attr, offset = element 392 if attr_index == self.operand: 393 if class_attr: 394 self.value = self.load(offset) # offset is address of class attribute 395 else: 396 self.value = self.load(ref + offset) 397 else: 398 self.exception = self.attr_error 399 return self.RaiseException() 400 401 def LoadAttrIndexContext(self): 402 context, ref = self.value 403 data = self.load(ref) 404 element = self.objlist[data.classcode + self.operand] 405 attr_index, class_attr, offset = element 406 if attr_index == self.operand: 407 loaded_context, loaded_ref = self.load(offset) # offset is address of class attribute 408 self.value = ref, loaded_ref 409 else: 410 self.exception = self.attr_error 411 return self.RaiseException() 412 413 def LoadAttrIndexContextCond(self): 414 context, ref = self.value 415 data = self.load(ref) 416 element = self.objlist[data.classcode + self.operand] 417 attr_index, class_attr, offset = element 418 if attr_index == self.operand: 419 if class_attr: 420 loaded_context, loaded_ref = self.load(offset) # offset is address of class attribute 421 self.value = self._LoadAddressContextCond(loaded_context, loaded_ref, context, ref) 422 else: 423 self.value = self.load(ref + offset) 424 else: 425 self.exception = self.attr_error 426 return self.RaiseException() 427 428 def StoreAttrIndex(self): 429 context, ref = self.value 430 data = self.load(ref) 431 element = self.objlist[data.classcode + self.operand] 432 attr_index, class_attr, offset = element 433 if attr_index == self.operand: 434 if class_attr: 435 self.exception = self.type_error 436 return self.RaiseException() 437 else: 438 self.save(ref + offset, self.source) 439 else: 440 self.exception = self.attr_error 441 return self.RaiseException() 442 443 # NOTE: LoadAttrIndexContext is a possibility if a particular attribute can always be overridden. 444 445 def MakeFrame(self): 446 self.invocation_sp_stack.append(len(self.frame_stack)) 447 self.frame_stack.extend([None] * self.operand) 448 449 def DropFrame(self): 450 self.local_sp_stack.pop() 451 frame = self.invocation_sp_stack.pop() 452 self.frame_stack = self.frame_stack[:frame] # reset stack before call 453 454 def RecoverFrame(self): 455 self.local_sp_stack.pop() 456 457 def StoreFrame(self): 458 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 459 self.frame_stack[frame + self.operand] = self.value 460 461 def StoreFrameIndex(self): 462 context, ref = self.value 463 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 464 data = self.load(ref) 465 element = self.paramlist[data.funccode + self.operand] 466 # NOTE: Need to ensure correct positioning where a context has been generated. 467 param_index, offset = element 468 if param_index == self.operand: 469 self.frame_stack[frame + offset + 1] = self.source # add 1 to skip the context always generated 470 else: 471 self.exception = self.type_error 472 return self.RaiseException() 473 474 def LoadCallable(self): 475 context, ref = self.value 476 data = self.load(ref) 477 self.callable = data.codeaddr 478 479 def StoreCallable(self): 480 context, ref = self.value 481 # NOTE: Should improve the representation and permit direct saving. 482 data = self.load(ref) 483 self.save(ref, (data.classcode, data.attrcode) + self.callable) 484 485 def LoadContext(self): 486 context, ref = self.value 487 # NOTE: Omission of the context of the context would make things like 488 # NOTE: self() inside methods impossible. 489 self.value = context, context 490 491 def CheckFrame(self): 492 (nargs, ndefaults, has_star) = self.operand 493 494 # The frame is actually installed as the locals. 495 # Retrieve the context from the first local. 496 497 frame = self.local_sp_stack[-1] 498 context_context, context_ref = self.frame_stack[frame] # + 0 499 nlocals = len(self.frame_stack[frame:]) 500 501 # Support sliding of the frame to exclude any inappropriate context. 502 # Since a context will always be present when this instruction is being 503 # used (whether or not it is desired), we can always test the nature of 504 # the context. 505 506 if context_ref is None: 507 self.local_sp_stack[-1] += 1 508 nlocals -= 1 509 else: 510 context_data = self.load(context_ref) 511 512 # Classes are not themselves usable as the self argument. 513 # NOTE: This may change at some point. 514 # However, where classes appear as the context, instance 515 # compatibility is required in the first argument. 516 517 if context_data.attrcode is None: # absent attrcode == class 518 519 # Slide the frame to exclude the context. 520 521 self.local_sp_stack[-1] += 1 522 nlocals -= 1 523 524 # Check the context against the first argument. 525 # NOTE: Raise a proper exception here. 526 527 if nlocals > 0: 528 self_context, self_ref = self.frame_stack[frame + 1] 529 if not self._CheckInstance(self_ref, context_context): 530 raise Exception, "CheckFrame %r (%r vs. %r)" % (self.operand, self.load(self_ref), self.load(context_context)) 531 #self.exception = self.type_error 532 #return self.RaiseException() 533 else: 534 raise Exception, "CheckFrame %r (no self argument)" % self.operand 535 #self.exception = self.type_error 536 #return self.RaiseException() 537 538 # Test the frame size. 539 # NOTE: Raise a proper exception here. 540 541 if not ((nargs - ndefaults) <= nlocals and (nlocals <= nargs or has_star)): 542 raise Exception, "CheckFrame %r (%r <= %r <= %r)" % (self.operand, nargs - ndefaults, nlocals, nargs) 543 #self.exception = self.type_error 544 #return self.RaiseException() 545 546 def FillDefaults(self): 547 # NOTE: Make the get_operand method of the instruction provide the 548 # NOTE: function location. 549 (nargs, ndefaults, fn) = self.operand 550 551 # The frame is actually installed as the locals. 552 553 frame = self.local_sp_stack[-1] 554 nlocals = len(self.frame_stack[frame:]) 555 556 # Support population of defaults. 557 # This involves copying the "attributes" of a function into the frame. 558 559 default = nlocals - (nargs - ndefaults) 560 self.frame_stack.extend([None] * (nargs - nlocals)) 561 pos = nlocals 562 ref = fn.location 563 564 while pos < nargs: 565 self.frame_stack[frame + pos] = self.load(ref + default + 1) # skip header 566 default += 1 567 pos += 1 568 569 def CheckSelf(self): 570 context, ref = self.value 571 target_context, target_ref = self.source 572 573 # Check the details of the proposed context and the target's context. 574 575 self.status = self._CheckInstance(ref, target_context) 576 577 def JumpWithFrame(self): 578 codeaddr = self.callable 579 self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame 580 return self.jump(codeaddr, self.pc + 1) # return to the instruction after this one 581 582 def JumpWithFrameDirect(self): 583 operand = self.operand 584 self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame 585 return self.jump(operand, self.pc + 1) # return to the instruction after this one 586 587 def ExtendFrame(self): 588 self.frame_stack.extend([None] * self.operand) 589 590 def AdjustFrame(self): 591 self.invocation_sp_stack[-1] += self.operand 592 593 def Return(self): 594 return self.pull_pc() 595 596 def LoadResult(self): 597 self.value = self.result 598 599 def StoreResult(self): 600 self.result = self.value 601 602 def Jump(self): 603 return self.operand 604 605 def JumpIfTrue(self): 606 if self.status: 607 return self.operand 608 609 def JumpIfFalse(self): 610 if not self.status: 611 return self.operand 612 613 def LoadException(self): 614 self.value = self.exception, self.exception 615 616 def StoreException(self): 617 self.exception = self.value[1] 618 619 def RaiseException(self): 620 return self.handler_stack[-1] 621 622 def PushHandler(self): 623 self.handler_stack.append(self.operand) 624 self.handler_local_sp_stack.append(len(self.local_sp_stack)) 625 self.handler_pc_stack.append(len(self.pc_stack)) 626 627 def PopHandler(self): 628 # Reduce the local frame pointer stack to refer to the handler's frame. 629 self.local_sp_stack = self.local_sp_stack[:self.handler_local_sp_stack.pop()] 630 # Reduce the PC stack to discard all superfluous return addresses. 631 self.pc_stack = self.pc_stack[:self.handler_pc_stack.pop()] 632 self.handler_stack.pop() 633 634 def CheckException(self): 635 self.status = self.exception is not None and self._CheckInstance(self.exception, self.value[1]) 636 637 def TestIdentity(self): 638 self.status = self.value[1] == self.source[1] 639 640 def TestIdentityAddress(self): 641 self.status = self.value[1] == self.operand 642 643 # LoadBoolean is implemented in the generated code. 644 # StoreBoolean is implemented by testing against the True value. 645 646 def InvertBoolean(self): 647 self.status = not self.status 648 649 # Common implementation details. 650 651 def _CheckInstance(self, ref, cls): 652 data = self.load(ref) 653 target_data = self.load(cls) 654 655 # Insist on a class. 656 657 if target_data.attrcode is not None: # present attrcode == instance 658 return 0 659 660 # Find the table entry for the descendant. 661 662 element = self.objlist[target_data.classcode + data.attrcode] 663 if element is not None: 664 attr_index, class_attr, offset = element 665 return attr_index == data.attrcode 666 else: 667 return 0 668 669 def _MakeObject(self, size, ref): 670 # Load the template. 671 data = self.load(ref) 672 addr = self.new(size) 673 # Save the header, overriding the size. 674 self.save(addr, data.with_size(size)) 675 return addr 676 677 def _LoadAddressContextCond(self, context, ref, inst_context, inst_ref): 678 679 # Check the instance context against the target's context. 680 681 if self._CheckInstance(inst_ref, context): 682 # Replace the context with the instance. 683 return inst_ref, ref 684 else: 685 return context, ref 686 687 # Native function implementations. 688 689 def builtins_int_add(self): 690 frame = self.local_sp_stack[-1] 691 692 # Get operands addresses. 693 694 left_context, left = self.frame_stack[frame] 695 right_context, right = self.frame_stack[frame + 1] 696 697 # Test operand suitability. 698 699 if not self._CheckInstance(left, self.int_class_location) and self._CheckInstance(right, self.int_class_location): 700 self.exception = self.type_error 701 return self.RaiseException() 702 703 # NOTE: Assume single location for data. 704 705 left_data = left + 1 706 right_data = right + 1 707 708 # Make a new object. 709 710 addr = self._MakeObject(2, self.int_instance_location) 711 712 # Store the result. 713 # NOTE: The data is considered ready to use. 714 715 self.save(addr + 1, self.load(left_data) + self.load(right_data)) 716 717 # Return the new object. 718 # Introduce object as context for the new object. 719 720 self.result = addr, addr 721 722 def builtins_int_bool(self): 723 frame = self.local_sp_stack[-1] 724 725 # Get operands addresses. 726 727 left_context, left = self.frame_stack[frame] 728 729 # Test operand suitability. 730 731 if not self._CheckInstance(left, self.int_class_location): 732 self.exception = self.type_error 733 return self.RaiseException() 734 735 # NOTE: Assume single location for data. 736 737 left_data = left + 1 738 739 # Test the data. 740 # NOTE: The data is considered ready to use. 741 742 if self.load(left_data) != 0: 743 self.result = self.true_constant, self.true_constant 744 else: 745 self.result = self.false_constant, self.false_constant 746 747 def builtins_int_neg(self): 748 frame = self.local_sp_stack[-1] 749 750 # Get operands addresses. 751 752 left_context, left = self.frame_stack[frame] 753 754 # Test operand suitability. 755 756 if not self._CheckInstance(left, self.int_class_location): 757 self.exception = self.type_error 758 return self.RaiseException() 759 760 # NOTE: Assume single location for data. 761 762 left_data = left + 1 763 764 # Make a new object. 765 766 addr = self._MakeObject(2, self.int_instance_location) 767 768 # Store the result. 769 # NOTE: The data is considered ready to use. 770 771 self.save(addr + 1, -self.load(left_data)) 772 773 # Return the new object. 774 # Introduce object as context for the new object. 775 776 self.result = addr, addr 777 778 def builtins_bool_bool(self): 779 frame = self.local_sp_stack[-1] 780 781 # Get operands addresses. 782 783 left_context, left = self.frame_stack[frame] 784 self.result = left, left 785 786 def builtins_list_new(self): 787 frame = self.local_sp_stack[-1] 788 789 # NOTE: Specific copying of tuples/lists. 790 791 args_context, args = self.frame_stack[frame] 792 header = self.load(args) 793 794 list = self._MakeObject(header.size, self.list_instance_location) 795 for i in range(1, header.size): 796 self.save(list + i, self.load(args + i)) 797 798 self.result = list, list 799 800 def builtins_list_getitem(self): 801 frame = self.local_sp_stack[-1] 802 803 # Get operands addresses. 804 805 obj_context, obj = self.frame_stack[frame] 806 item_context, item = self.frame_stack[frame + 1] 807 808 header = self.load(obj) 809 nelements = header.size - 1 810 811 # NOTE: Assume single location for data. 812 813 item_pos = self.load(item + 1) 814 if item_pos >= 0 and item_pos < nelements: 815 pass 816 elif item_pos < 0 and item_pos >= -nelements: 817 item_pos = nelements + item_pos 818 else: 819 self.exception = self.index_error 820 return self.RaiseException() 821 822 self.result = self.load(obj + 1 + item_pos) 823 824 def builtins_object_init(self): 825 pass 826 827 native_functions = { 828 "__builtins__.int.__add__" : builtins_int_add, 829 "__builtins__.int.__bool__" : builtins_int_bool, 830 "__builtins__.int.__neg__" : builtins_int_neg, 831 "__builtins__.bool.__bool__" : builtins_bool_bool, 832 "__builtins__.list" : builtins_list_new, 833 "__builtins__.list.__getitem__" : builtins_list_getitem, 834 "__builtins__.object.__init__" : builtins_object_init, 835 } 836 837 # vim: tabstop=4 expandtab shiftwidth=4