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