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, 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.result = None 90 self.exception = None 91 92 def load(self, address): 93 94 "Return the value at the given 'address'." 95 96 try: 97 return self.memory[address] 98 except IndexError: 99 raise IllegalAddress, address 100 101 def save(self, address, value): 102 103 "Save to the given 'address' the specified 'value'." 104 105 try: 106 self.memory[address] = value 107 except IndexError: 108 raise IllegalAddress, address 109 110 def new(self, size): 111 112 """ 113 Allocate space of the given 'size', returning the address of the space. 114 """ 115 116 addr = len(self.memory) 117 for i in range(0, size): 118 self.memory.append(None) 119 return addr 120 121 def push_pc(self, data): 122 123 "Push 'data' onto the PC stack." 124 125 self.pc_stack.append(data) 126 127 def pull_pc(self): 128 129 "Pull a value from the PC stack and return it." 130 131 try: 132 return self.pc_stack.pop() 133 except IndexError: 134 raise EmptyPCStack 135 136 def run(self): 137 138 "Execute code in the memory, starting from the current PC address." 139 140 try: 141 while 1: 142 self.execute() 143 except EmptyPCStack: 144 pass 145 146 def execute(self): 147 148 "Execute code in the memory at the current PC address." 149 150 self.instruction = self.load(self.pc) 151 self.operand = self.instruction.get_operand() 152 153 instruction_name = self.instruction.__class__.__name__ 154 if self.debug: 155 print "%8d %s" % (self.pc, instruction_name) 156 157 method = self.get_method(instruction_name) 158 159 # Process any inputs of the instruction. 160 161 self.process_inputs() 162 next_pc = method() 163 164 # Update the program counter. 165 166 if next_pc is None: 167 self.pc += 1 168 else: 169 self.pc = next_pc 170 171 def get_method(self, instruction_name): 172 173 "Return the handler method for the given 'instruction_name'." 174 175 method = getattr(self, instruction_name, None) 176 if method is None: 177 raise IllegalInstruction, (self.pc, instruction_name) 178 return method 179 180 def process_inputs(self): 181 182 """ 183 Process any inputs of the current instruction. This permits any directly 184 connected sub-instructions to produce the effects that separate 185 instructions would otherwise have. 186 """ 187 188 for input in (self.instruction.input, self.instruction.source): 189 if input is not None: 190 method = self.get_method(input) 191 method() 192 193 def jump(self, addr, next): 194 195 """ 196 Jump to the subroutine at (or identified by) 'addr'. If 'addr' 197 identifies a library function then invoke the library function and set 198 PC to 'next' afterwards; otherwise, set PC to 'addr'. 199 """ 200 201 if isinstance(addr, str): 202 getattr(self, addr)() 203 return next 204 else: 205 self.push_pc(self.pc + 2) 206 return addr 207 208 # Instructions. 209 210 def LoadConst(self): 211 self.value = None, self.operand 212 213 def LoadName(self): 214 frame = self.local_sp_stack[-1] 215 self.value = self.frame_stack[frame + self.operand] 216 217 def StoreName(self): 218 frame = self.local_sp_stack[-1] 219 self.frame_stack[frame + self.operand] = self.value 220 221 LoadTemp = LoadName 222 StoreTemp = StoreName 223 224 def LoadAddress(self): 225 # Preserve context (potentially null). 226 self.value = self.load(self.operand) 227 228 def LoadAddressContext(self): 229 value = self.load(self.operand) 230 # Replace the context with the current value. 231 self.value = self.value[1], value[1] 232 233 def StoreAddress(self): 234 # Preserve context. 235 self.save(self.operand, self.value) 236 237 def MakeObject(self): 238 # Introduce null context for new object. 239 self.value = None, self.new(self.operand) 240 241 def LoadAttr(self): 242 context, ref = self.value 243 loaded_context, loaded_ref = self.load(ref + self.operand) 244 if loaded_context is None: 245 # Override null context with owning instance. 246 self.value = ref, loaded_ref 247 else: 248 self.value = loaded_context, loaded_ref 249 250 def StoreAttr(self): 251 context, ref = self.value 252 self.save(ref + self.operand, self.source) 253 254 def LoadAttrIndex(self): 255 context, ref = self.value 256 code = self.load(ref) # + 0 (the classcode) 257 element = self.objtable[code + self.operand] 258 found_code, found_attr = element 259 if found_code == code: 260 # NOTE: The found context should be tested against the object's context. 261 # NOTE: Compatibility between contexts should be stored in the table, or 262 # NOTE: an incompatible context should be preserved. 263 self.value = ref, found_ref 264 else: 265 # NOTE: This should cause an attribute error. 266 self.value = None 267 268 def StoreAttrIndex(self): pass 269 270 def MakeFrame(self): 271 self.invocation_sp_stack.append(len(self.frame_stack)) 272 self.frame_stack.extend([None] * self.operand) 273 274 def JumpWithFrame(self): 275 self.local_sp_stack.append(self.invocation_sp_stack[-1]) # adopt the invocation frame 276 context, ref = self.value 277 return self.jump(ref.code_location, self.pc + 1) # return to the instruction after this one 278 279 def DropFrame(self): 280 result = self.pull() 281 self.local_sp_stack.pop() 282 frame = self.invocation_sp_stack.pop() 283 self.frame_stack = self.frame_stack[:frame] # reset stack before call 284 285 def CheckFrame(self): pass 286 287 def LoadCallable(self): pass 288 289 def LoadContext(self): 290 context, ref = self.value 291 self.push((None, context)) 292 293 def CheckSelf(self): pass 294 295 def CheckContext(self): pass 296 297 def Return(self): 298 self.pc = self.pull_pc() 299 300 def LoadResult(self): 301 self.value = self.result 302 303 def StoreResult(self): 304 self.result = self.value 305 306 def LoadException(self): 307 self.value = self.exception 308 309 def StoreException(self): 310 self.exception = self.value 311 312 def LoadBoolean(self): 313 self.value = self.status 314 315 def Jump(self): 316 return self.operand 317 318 def JumpIfTrue(self): 319 if self.status: 320 return self.operand 321 322 def JumpIfFalse(self): 323 if not self.status: 324 return self.operand 325 326 def StoreFrame(self): 327 frame = self.invocation_sp_stack[-1] # different from the current frame after MakeFrame 328 self.frame_stack[frame + self.operand] = self.value 329 330 # vim: tabstop=4 expandtab shiftwidth=4