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