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