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 if self.instruction.source is not None: 261 self.perform(self.instruction.source) 262 self.source = self.value 263 if self.instruction.input is not None: 264 self.perform(self.instruction.input) 265 266 def jump(self, addr, next): 267 268 """ 269 Jump to the subroutine at (or identified by) 'addr'. If 'addr' 270 identifies a library function then invoke the library function and set 271 PC to 'next' afterwards; otherwise, set PC to 'addr'. 272 """ 273 274 if isinstance(addr, str): 275 getattr(self, addr)() 276 return next 277 else: 278 self.push_pc(self.pc + 1) 279 return addr 280 281 # Instructions. 282 283 def LoadConst(self): 284 self.value = None, self.operand 285 286 def LoadName(self): 287 frame = self.local_sp_stack[-1] 288 self.value = self.frame_stack[frame + self.operand] 289 290 def StoreName(self): 291 frame = self.local_sp_stack[-1] 292 self.frame_stack[frame + self.operand] = self.value 293 294 LoadTemp = LoadName 295 StoreTemp = StoreName 296 297 def LoadAddress(self): 298 # Preserve context (potentially null). 299 self.value = self.load(self.operand) 300 301 def LoadAddressContext(self): 302 value = self.load(self.operand) 303 # Replace the context with the current value. 304 self.value = self.value[1], value[1] 305 306 def StoreAddress(self): 307 # Preserve context. 308 self.save(self.operand, self.value) 309 310 def MakeObject(self): 311 size = self.operand 312 context, ref = self.value 313 classcode, attrcode, codeaddr, codedetails, instance = self.load(ref) 314 addr = self.new(size) 315 # Set the header to resemble the class. 316 self.save(addr, (classcode, attrcode, None, None, 1)) # NOTE: __call__ method not yet provided. 317 # Introduce null context for new object. 318 self.value = None, addr 319 320 def LoadAttr(self): 321 context, ref = self.value 322 # Retrieved context should already be appropriate for the instance. 323 self.value = self.load(ref + self.operand + 1) 324 325 def StoreAttr(self): 326 context, ref = self.value 327 # Target should already be an instance. 328 self.save(ref + self.operand + 1, self.source) 329 330 def LoadAttrIndex(self): 331 context, ref = self.value 332 classcode, attrcode, codeaddr, codedetails, instance = self.load(ref) 333 element = self.objlist[classcode + self.operand] 334 attr_index, class_attr, replace_context, offset = element 335 if attr_index == self.operand: 336 if class_attr: 337 loaded_context, loaded_ref = self.load(offset) # offset is address of class attribute 338 if replace_context: 339 self.value = ref, loaded_ref # classes can also replace the context if compatible 340 return 341 self.value = loaded_context, loaded_ref 342 else: 343 self.value = self.load(ref + offset) 344 else: 345 self.exception = self.attr_error 346 347 def StoreAttrIndex(self): 348 context, ref = self.value 349 classcode, attrcode, codeaddr, codedetails, instance = self.load(ref) 350 element = self.objlist[classcode + self.operand] 351 attr_index, class_attr, replace_context, offset = element 352 if attr_index == self.operand: 353 if class_attr: 354 self.exception = self.type_error 355 else: 356 self.save(ref + offset, self.source) 357 else: 358 self.exception = self.attr_error 359 360 # NOTE: LoadAttrIndexContext is a possibility if a particular attribute can always be overridden. 361 362 def MakeFrame(self): 363 self.invocation_sp_stack.append(len(self.frame_stack)) 364 self.frame_stack.extend([None] * self.operand) 365 366 def DropFrame(self): 367 self.local_sp_stack.pop() 368 frame = self.invocation_sp_stack.pop() 369 self.frame_stack = self.frame_stack[:frame] # reset stack before call 370 371 def RecoverFrame(self): 372 self.local_sp_stack.pop() 373 374 def StoreFrame(self): 375 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 376 self.frame_stack[frame + self.operand] = self.value 377 378 def StoreFrameIndex(self): 379 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 380 classcode, attrcode, codeaddr, codedetails, instance = self.load(ref) 381 element = self.objlist[classcode + self.operand] 382 attr_index, offset = element 383 if attr_index == self.operand: 384 self.frame_stack[frame + offset] = self.value 385 else: 386 self.exception = self.type_error 387 388 def LoadCallable(self): 389 context, ref = self.value 390 classcode, attrcode, codeaddr, codedetails, instance = self.load(ref) 391 self.callable = codeaddr, codedetails 392 393 def StoreCallable(self): 394 context, ref = self.value 395 # NOTE: Should improve the representation and permit direct saving. 396 classcode, attrcode, codeaddr, codedetails, instance = self.load(ref) 397 self.save(ref, (classcode, attrcode) + self.callable + (instance,)) 398 399 def LoadContext(self): 400 context, ref = self.value 401 self.value = None, context 402 403 def CheckFrame(self): 404 operand = self.operand 405 frame = self.invocation_sp_stack[-1] 406 context, ref = self.value 407 classcode, attrcode, codeaddr, codedetails, instance = self.load(ref) 408 409 # Support sliding of the frame to exclude any inappropriate context. 410 411 if context is None: 412 self.invocation_sp_stack[-1] += 1 413 operand -= 1 414 else: 415 context_classcode, context_attrcode, context_codeaddr, context_codedetails, context_instance = self.load(context) 416 if not context_instance: 417 self.invocation_sp_stack[-1] += 1 418 operand -= 1 419 420 nargs, ndefaults = codedetails 421 if not (nargs - ndefaults <= operand <= nargs): 422 raise Exception, "CheckFrame %r" % (nargs - ndefaults, self.operand, nargs) 423 424 # NOTE: Support population of defaults. 425 426 def CheckSelf(self): 427 context, ref = self.value 428 target_context, target_ref = self.source 429 430 # Check the details of the proposed context and the target's context. 431 432 self._CheckInstance(ref, target_context) 433 434 def JumpWithFrame(self): 435 codeaddr, codedetails = self.callable 436 self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame 437 return self.jump(codeaddr, self.pc + 1) # return to the instruction after this one 438 439 def ExtendFrame(self): 440 self.frame_stack.extend([None] * self.operand) 441 442 def AdjustFrame(self): 443 if self.operand > 0: 444 self.frame_stack.append([None] * self.operand) 445 elif self.operand == -1: 446 self.invocation_sp_stack[-1] -= 1 447 else: 448 raise Exception, "AdjustFrame %r" % self.operand 449 450 def Return(self): 451 return self.pull_pc() 452 453 def LoadResult(self): 454 self.value = self.result 455 456 def StoreResult(self): 457 self.result = self.value 458 459 def Jump(self): 460 return self.operand 461 462 def JumpIfTrue(self): 463 if self.status: 464 return self.operand 465 466 def JumpIfFalse(self): 467 if not self.status: 468 return self.operand 469 470 def LoadException(self): 471 self.value = None, self.exception 472 473 def StoreException(self): 474 self.exception = self.value[1] 475 476 def RaiseException(self): 477 return self.handler_stack[-1] 478 479 def PushHandler(self): 480 self.handler_stack.append(self.operand) 481 self.handler_local_sp_stack.append(len(self.local_sp_stack)) 482 self.handler_pc_stack.append(len(self.pc_stack)) 483 484 def PopHandler(self): 485 # Reduce the local frame pointer stack to refer to the handler's frame. 486 self.local_sp_stack = self.local_sp_stack[:self.handler_local_sp_stack.pop()] 487 # Reduce the PC stack to discard all superfluous return addresses. 488 self.pc_stack = self.pc_stack[:self.handler_pc_stack.pop()] 489 self.handler_stack.pop() 490 491 def CheckException(self): 492 self._CheckInstance(self.exception, self.value[1]) 493 494 def TestIdentity(self): 495 self.status = self.value[1] == self.source[1] 496 497 def TestIdentityAddress(self): 498 self.status = self.value[1] == self.operand 499 500 # LoadBoolean is implemented in the generated code. 501 # StoreBoolean is implemented by testing against the True value. 502 503 def InvertBoolean(self): 504 self.status = not self.status 505 506 # Common implementation details. 507 508 def _CheckInstance(self, ref, cls): 509 classcode, attrcode, codeaddr, codedetails, instance = self.load(ref) 510 target_classcode, target_attrcode, target_codeaddr, target_codedetails, target_instance = self.load(cls) 511 512 # Find the table entry for the descendant. 513 514 element = self.objlist[target_classcode + attrcode] 515 attr_index, class_attr, replace_context, offset = element 516 if attr_index == attrcode: 517 self.status = 1 518 else: 519 self.status = 0 520 521 # vim: tabstop=4 expandtab shiftwidth=4