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