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 def dump(self): 111 print "PC", self.pc, "->", self.load(self.pc) 112 print "PC stack", self.pc_stack 113 print "Frame stack", self.frame_stack 114 print "Local stack pointers", self.local_sp_stack 115 print "Invocation stack pointers", self.invocation_sp_stack 116 print "Handler stack", self.handler_stack 117 print "Handler frame stack", self.handler_local_sp_stack 118 print "Handler PC stack", self.handler_pc_stack 119 print 120 print "Instruction", self.instruction 121 print "Operand", self.operand 122 print "Value", self.value 123 print "Status", self.status 124 print "Source", self.source 125 print "Callable", self.callable 126 print "Result", self.result 127 print "Exception", self.exception 128 129 def step(self): 130 self.execute() 131 self.dump() 132 133 def load(self, address): 134 135 "Return the value at the given 'address'." 136 137 try: 138 return self.memory[address] 139 except IndexError: 140 raise IllegalAddress, address 141 142 def save(self, address, value): 143 144 "Save to the given 'address' the specified 'value'." 145 146 try: 147 self.memory[address] = value 148 except IndexError: 149 raise IllegalAddress, address 150 151 def new(self, size): 152 153 """ 154 Allocate space of the given 'size', returning the address of the space. 155 """ 156 157 addr = len(self.memory) 158 for i in range(0, size): 159 self.memory.append(None) 160 return addr 161 162 def push_pc(self, data): 163 164 "Push 'data' onto the PC stack." 165 166 self.pc_stack.append(data) 167 168 def pull_pc(self): 169 170 "Pull a value from the PC stack and return it." 171 172 try: 173 return self.pc_stack.pop() 174 except IndexError: 175 raise EmptyPCStack 176 177 def run(self): 178 179 "Execute code in the memory, starting from the current PC address." 180 181 try: 182 while 1: 183 self.execute() 184 except EmptyPCStack: 185 pass 186 187 def execute(self): 188 189 "Execute code in the memory at the current PC address." 190 191 self.instruction = self.load(self.pc) 192 193 # Process any inputs of the instruction. 194 195 self.process_inputs() 196 197 # Perform the instruction itself. 198 199 next_pc = self.perform(self.instruction) 200 201 # Update the program counter. 202 203 if next_pc is None: 204 self.pc += 1 205 else: 206 self.pc = next_pc 207 208 def get_method(self, instruction): 209 210 "Return the handler method for the given 'instruction'." 211 212 instruction_name = instruction.__class__.__name__ 213 if self.debug: 214 print "%8d %s" % (self.pc, instruction_name) 215 method = getattr(self, instruction_name, None) 216 if method is None: 217 raise IllegalInstruction, (self.pc, instruction_name) 218 return method 219 220 def perform(self, instruction): 221 222 "Perform the 'instruction', returning the next PC value or None." 223 224 self.operand = instruction.get_operand() 225 method = self.get_method(instruction) 226 return method() 227 228 def process_inputs(self): 229 230 """ 231 Process any inputs of the current instruction. This permits any directly 232 connected sub-instructions to produce the effects that separate 233 instructions would otherwise have. 234 """ 235 236 for input in (self.instruction.input, self.instruction.source): 237 if input is not None: 238 self.perform(input) 239 240 def jump(self, addr, next): 241 242 """ 243 Jump to the subroutine at (or identified by) 'addr'. If 'addr' 244 identifies a library function then invoke the library function and set 245 PC to 'next' afterwards; otherwise, set PC to 'addr'. 246 """ 247 248 if isinstance(addr, str): 249 getattr(self, addr)() 250 return next 251 else: 252 self.push_pc(self.pc + 1) 253 return addr 254 255 # Instructions. 256 257 def LoadConst(self): 258 self.value = None, self.operand 259 260 def LoadName(self): 261 frame = self.local_sp_stack[-1] 262 self.value = self.frame_stack[frame + self.operand] 263 264 def StoreName(self): 265 frame = self.local_sp_stack[-1] 266 self.frame_stack[frame + self.operand] = self.value 267 268 LoadTemp = LoadName 269 StoreTemp = StoreName 270 271 def LoadAddress(self): 272 # Preserve context (potentially null). 273 self.value = self.load(self.operand) 274 275 def LoadAddressContext(self): 276 value = self.load(self.operand) 277 # Replace the context with the current value. 278 self.value = self.value[1], value[1] 279 280 def StoreAddress(self): 281 # Preserve context. 282 self.save(self.operand, self.value) 283 284 def MakeObject(self): 285 size = self.operand 286 context, ref = self.value 287 classcode, attrcode, codeaddr, codedetails, instance = self.load(ref) 288 addr = self.new(size) 289 # Set the header to resemble the class. 290 self.save(addr, (classcode, attrcode, None, None, 1)) # NOTE: __call__ method not yet provided. 291 # Introduce null context for new object. 292 self.value = None, addr 293 294 def LoadAttr(self): 295 context, ref = self.value 296 # Retrieved context should already be appropriate for the instance. 297 self.value = self.load(ref + self.operand) 298 299 def StoreAttr(self): 300 context, ref = self.value 301 # Target should already be an instance. 302 self.save(ref + self.operand, self.source) 303 304 def LoadAttrIndex(self): 305 context, ref = self.value 306 classcode, attrcode, codeaddr, codedetails, instance = self.load(ref) 307 element = self.objlist[classcode + self.operand] 308 attr_index, class_attr, replace_context, offset = element 309 if attr_index == self.operand: 310 if class_attr: 311 loaded_context, loaded_ref = self.load(offset) # offset is address of class attribute 312 if replace_context: 313 self.value = ref, loaded_ref # classes can also replace the context if compatible 314 return 315 self.value = loaded_context, loaded_ref 316 else: 317 self.value = self.load(ref + offset) 318 else: 319 self.exception = self.attr_error 320 321 def StoreAttrIndex(self): 322 context, ref = self.value 323 classcode, attrcode, codeaddr, codedetails, instance = self.load(ref) 324 element = self.objlist[classcode + self.operand] 325 attr_index, class_attr, replace_context, offset = element 326 if attr_index == self.operand: 327 if class_attr: 328 self.exception = self.type_error 329 else: 330 self.save(ref + offset, self.source) 331 else: 332 self.exception = self.attr_error 333 334 # NOTE: LoadAttrIndexContext is a possibility if a particular attribute can always be overridden. 335 336 def MakeFrame(self): 337 self.invocation_sp_stack.append(len(self.frame_stack)) 338 self.frame_stack.extend([None] * self.operand) 339 340 def DropFrame(self): 341 self.local_sp_stack.pop() 342 frame = self.invocation_sp_stack.pop() 343 self.frame_stack = self.frame_stack[:frame] # reset stack before call 344 345 def RecoverFrame(self): 346 self.local_sp_stack.pop() 347 348 def StoreFrame(self): 349 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 350 self.frame_stack[frame + self.operand] = self.value 351 352 def StoreFrameIndex(self): 353 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 354 classcode, attrcode, codeaddr, codedetails, instance = self.load(ref) 355 element = self.objlist[classcode + self.operand] 356 attr_index, offset = element 357 if attr_index == self.operand: 358 self.frame_stack[frame + offset] = self.value 359 else: 360 self.exception = self.type_error 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