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 attr_index, class_attr, replace_context, offset = element 257 if attr_index == self.operand: 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 attr_index, class_attr, replace_context, offset = element 275 if attr_index == self.operand: 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 attr_index, offset = element 306 if attr_index == self.operand: 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 353 # Load the details of the proposed context and the target's context. 354 355 classcode, attrcode, codeaddr, codedetails = self.load(ref) 356 target_classcode, target_attrcode, target_codeaddr, target_codedetails = self.load(target_context) 357 358 # Find the table entry for the descendant. 359 360 element = self.objtable[target_classcode + attrcode] 361 attr_index, class_attr, replace_context, offset = element 362 if attr_index == attrcode: 363 self.status = 1 364 else: 365 self.status = 0 366 367 def JumpWithFrame(self): 368 self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame 369 return self.jump(self.callable, self.pc + 1) # return to the instruction after this one 370 371 def ExtendFrame(self): 372 frame = self.local_sp_stack[-1] 373 frame.extend([None] * self.operand) 374 375 def Return(self): 376 self.pc = self.pull_pc() 377 378 def LoadResult(self): 379 self.value = self.result 380 381 def StoreResult(self): 382 self.result = self.value 383 384 def Jump(self): 385 return self.operand 386 387 def JumpIfTrue(self): 388 if self.status: 389 return self.operand 390 391 def JumpIfFalse(self): 392 if not self.status: 393 return self.operand 394 395 def LoadException(self): 396 self.value = self.exception 397 398 def StoreException(self): 399 self.exception = self.value 400 401 def RaiseException(self): 402 return self.handler_stack.pop() 403 404 def PushHandler(self): 405 self.handler_stack.append(self.operand) 406 407 def PopHandler(self): 408 self.handler_stack.pop() 409 410 def CheckException(self): 411 self.status = self.value[1] == self.exception 412 413 def TestIdentity(self): 414 self.status = self.value[1] == self.source 415 416 def TestIdentityAddress(self): 417 self.status = self.value[1] == self.operand 418 419 # LoadBoolean is implemented in the generated code. 420 # StoreBoolean is implemented by testing against the True value. 421 422 def InvertBoolean(self): 423 self.status = not self.status 424 425 # vim: tabstop=4 expandtab shiftwidth=4
