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