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