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