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