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