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, clstable, 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.clstable = clstable 72 self.pc = pc or 0 73 self.debug = debug 74 75 # Stacks. 76 77 self.pc_stack = [] 78 self.frame_stack = [] 79 self.local_sp_stack = [] 80 self.invocation_sp_stack = [] 81 self.handler_stack = [] 82 83 # Registers. 84 85 self.instruction = None 86 self.operand = None 87 self.value = None 88 self.status = None 89 self.source = None 90 self.callable = None 91 self.result = None 92 self.exception = None 93 94 def load(self, address): 95 96 "Return the value at the given 'address'." 97 98 try: 99 return self.memory[address] 100 except IndexError: 101 raise IllegalAddress, address 102 103 def save(self, address, value): 104 105 "Save to the given 'address' the specified 'value'." 106 107 try: 108 self.memory[address] = value 109 except IndexError: 110 raise IllegalAddress, address 111 112 def new(self, size): 113 114 """ 115 Allocate space of the given 'size', returning the address of the space. 116 """ 117 118 addr = len(self.memory) 119 for i in range(0, size): 120 self.memory.append(None) 121 return addr 122 123 def push_pc(self, data): 124 125 "Push 'data' onto the PC stack." 126 127 self.pc_stack.append(data) 128 129 def pull_pc(self): 130 131 "Pull a value from the PC stack and return it." 132 133 try: 134 return self.pc_stack.pop() 135 except IndexError: 136 raise EmptyPCStack 137 138 def run(self): 139 140 "Execute code in the memory, starting from the current PC address." 141 142 try: 143 while 1: 144 self.execute() 145 except EmptyPCStack: 146 pass 147 148 def execute(self): 149 150 "Execute code in the memory at the current PC address." 151 152 self.instruction = self.load(self.pc) 153 self.operand = self.instruction.get_operand() 154 155 instruction_name = self.instruction.__class__.__name__ 156 if self.debug: 157 print "%8d %s" % (self.pc, instruction_name) 158 159 method = self.get_method(instruction_name) 160 161 # Process any inputs of the instruction. 162 163 self.process_inputs() 164 next_pc = method() 165 166 # Update the program counter. 167 168 if next_pc is None: 169 self.pc += 1 170 else: 171 self.pc = next_pc 172 173 def get_method(self, instruction_name): 174 175 "Return the handler method for the given 'instruction_name'." 176 177 method = getattr(self, instruction_name, None) 178 if method is None: 179 raise IllegalInstruction, (self.pc, instruction_name) 180 return method 181 182 def process_inputs(self): 183 184 """ 185 Process any inputs of the current instruction. This permits any directly 186 connected sub-instructions to produce the effects that separate 187 instructions would otherwise have. 188 """ 189 190 for input in (self.instruction.input, self.instruction.source): 191 if input is not None: 192 method = self.get_method(input) 193 method() 194 195 def jump(self, addr, next): 196 197 """ 198 Jump to the subroutine at (or identified by) 'addr'. If 'addr' 199 identifies a library function then invoke the library function and set 200 PC to 'next' afterwards; otherwise, set PC to 'addr'. 201 """ 202 203 if isinstance(addr, str): 204 getattr(self, addr)() 205 return next 206 else: 207 self.push_pc(self.pc + 2) 208 return addr 209 210 # Instructions. 211 212 def LoadConst(self): 213 self.value = None, self.operand 214 215 def LoadName(self): 216 frame = self.local_sp_stack[-1] 217 self.value = self.frame_stack[frame + self.operand] 218 219 def StoreName(self): 220 frame = self.local_sp_stack[-1] 221 self.frame_stack[frame + self.operand] = self.value 222 223 LoadTemp = LoadName 224 StoreTemp = StoreName 225 226 def LoadAddress(self): 227 # Preserve context (potentially null). 228 self.value = self.load(self.operand) 229 230 def LoadAddressContext(self): 231 value = self.load(self.operand) 232 # Replace the context with the current value. 233 self.value = self.value[1], value[1] 234 235 def StoreAddress(self): 236 # Preserve context. 237 self.save(self.operand, self.value) 238 239 def MakeObject(self): 240 # Introduce null context for new object. 241 self.value = None, self.new(self.operand) 242 243 def LoadAttr(self): 244 context, ref = self.value 245 # Retrieved context should already be appropriate for the instance. 246 self.value = self.load(ref + self.operand) 247 248 def StoreAttr(self): 249 context, ref = self.value 250 # Target should already be an instance. 251 self.save(ref + self.operand, self.source) 252 253 def LoadAttrIndex(self): 254 context, ref = self.value 255 code = self.load(ref) # + 0 (the classcode) 256 element = self.objtable[code + self.operand] 257 found_code, class_attr, replace_context, offset = element 258 if found_code == code: 259 if class_attr: 260 loaded_context, loaded_ref = self.load(offset) # offset is address of class attribute 261 if replace_context: 262 self.value = ref, loaded_ref # classes can also replace the context if compatible 263 return 264 self.value = loaded_context, loaded_ref 265 else: 266 self.value = self.load(ref + offset) 267 else: 268 # NOTE: This should cause an attribute error. 269 raise Exception, "LoadAttrIndex % r" % element 270 271 def StoreAttrIndex(self): 272 context, ref = self.value 273 code = self.load(ref) # + 0 (the classcode) 274 element = self.objtable[code + self.operand] 275 found_code, class_attr, replace_context, offset = element 276 if found_code == code: 277 if class_attr: 278 # NOTE: This should cause an attribute or type error. 279 # Class attributes cannot be changed at run-time. 280 raise Exception, "StoreAttrIndex % r" % element 281 else: 282 self.save(ref + offset, self.source) 283 else: 284 # NOTE: This should cause an attribute error. 285 raise Exception, "StoreAttrIndex % r" % element 286 287 # NOTE: LoadAttrIndexContext is a possibility if a particular attribute can always be overridden. 288 289 def MakeFrame(self): 290 self.invocation_sp_stack.append(len(self.frame_stack)) 291 self.frame_stack.extend([None] * self.operand) 292 293 def DropFrame(self): 294 self.local_sp_stack.pop() 295 frame = self.invocation_sp_stack.pop() 296 self.frame_stack = self.frame_stack[:frame] # reset stack before call 297 298 def StoreFrame(self): 299 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 300 self.frame_stack[frame + self.operand] = self.value 301 302 def StoreFrameIndex(self): 303 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 304 code = self.load(ref) # + 0 (the functioncode) 305 element = self.objtable[code + self.operand] 306 found_code, offset = element 307 if found_code == code: 308 self.frame_stack[frame + offset] = self.value 309 else: 310 # NOTE: This should cause an argument error. 311 raise Exception, "StoreFrameIndex % r" % element 312 313 def LoadCallable(self): 314 context, ref = self.value 315 self.callable = self.load(ref + 1) 316 317 def StoreCallable(self): 318 context, ref = self.value 319 self.save(ref + 1, self.callable) 320 321 def LoadContext(self): 322 context, ref = self.value 323 self.value = None, context 324 325 def CheckFrame(self): 326 context, ref = self.value 327 nargs, ndefaults = self.load(ref + 2) 328 if not (nargs - ndefaults <= self.operand <= nargs): 329 raise Exception, "CheckFrame %r" % (nargs - ndefaults, self.operand, nargs) 330 # NOTE: Support population of defaults. 331 # NOTE: Support sliding of the frame to exclude any inappropriate context. 332 333 def CheckSelf(self): pass 334 335 def JumpWithFrame(self): 336 self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame 337 return self.jump(self.callable, self.pc + 1) # return to the instruction after this one 338 339 def ExtendFrame(self): 340 frame = self.local_sp_stack[-1] 341 frame.extend([None] * self.operand) 342 343 def Return(self): 344 self.pc = self.pull_pc() 345 346 def LoadResult(self): 347 self.value = self.result 348 349 def StoreResult(self): 350 self.result = self.value 351 352 def Jump(self): 353 return self.operand 354 355 def JumpIfTrue(self): 356 if self.status: 357 return self.operand 358 359 def JumpIfFalse(self): 360 if not self.status: 361 return self.operand 362 363 def LoadException(self): 364 self.value = self.exception 365 366 def StoreException(self): 367 self.exception = self.value 368 369 def RaiseException(self): 370 return self.handler_stack.pop() 371 372 def PushHandler(self): 373 self.handler_stack.append(self.operand) 374 375 def PopHandler(self): 376 self.handler_stack.pop() 377 378 def CheckException(self): 379 self.status = self.value[1] == self.exception 380 381 def TestIdentity(self): 382 self.status = self.value[1] == self.source 383 384 def TestIdentityAddress(self): 385 self.status = self.value[1] == self.operand 386 387 # LoadBoolean is implemented in the generated code. 388 # StoreBoolean is implemented by testing against the True value. 389 390 def InvertBoolean(self): 391 self.status = not self.status 392 393 # vim: tabstop=4 expandtab shiftwidth=4