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