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