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 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.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 code = self.load(ref) # + 0 (the classcode) 255 element = self.objtable[code + self.operand] 256 found_code, class_attr, replace_context, offset = element 257 if found_code == code: 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 code = self.load(ref) # + 0 (the classcode) 273 element = self.objtable[code + self.operand] 274 found_code, class_attr, replace_context, offset = element 275 if found_code == code: 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 JumpWithFrame(self): 293 self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame 294 context, ref = self.value 295 return self.jump(ref.code_location, self.pc + 1) # return to the instruction after this one 296 297 def DropFrame(self): 298 result = self.pull() 299 self.local_sp_stack.pop() 300 frame = self.invocation_sp_stack.pop() 301 self.frame_stack = self.frame_stack[:frame] # reset stack before call 302 303 def StoreFrame(self): 304 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 305 self.frame_stack[frame + self.operand] = self.value 306 307 def StoreFrameIndex(self): 308 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 309 code = self.load(ref) # + 0 (the functioncode) 310 element = self.objtable[code + self.operand] 311 found_code, offset = element 312 if found_code == code: 313 self.frame_stack[frame + offset] = self.value 314 else: 315 # NOTE: This should cause an argument error. 316 raise Exception, "StoreFrameIndex % r" % element 317 318 def CheckFrame(self): pass 319 320 def CheckSelf(self): pass 321 322 def LoadCallable(self): pass 323 324 def LoadContext(self): 325 context, ref = self.value 326 self.push((None, context)) 327 328 def Return(self): 329 self.pc = self.pull_pc() 330 331 def LoadResult(self): 332 self.value = self.result 333 334 def StoreResult(self): 335 self.result = self.value 336 337 def Jump(self): 338 return self.operand 339 340 def JumpIfTrue(self): 341 if self.status: 342 return self.operand 343 344 def JumpIfFalse(self): 345 if not self.status: 346 return self.operand 347 348 def LoadException(self): 349 self.value = self.exception 350 351 def StoreException(self): 352 self.exception = self.value 353 354 def RaiseException(self): 355 return self.handler_stack.pop() 356 357 def PushHandler(self): 358 self.handler_stack.append(self.operand) 359 360 def PopHandler(self): 361 self.handler_stack.pop() 362 363 def CheckException(self): 364 self.status = self.value[1] == self.exception 365 366 def TestIdentity(self): 367 self.status = self.value[1] == self.source 368 369 def TestIdentityAddress(self): 370 self.status = self.value[1] == self.operand 371 372 # LoadBoolean is implemented in the generated code. 373 # StoreBoolean is implemented by testing against the True value. 374 375 # vim: tabstop=4 expandtab shiftwidth=4