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